#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "profile.h"
#include "cfganal.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa.h"
#include "tree-inline.h"
#include "cfgloop.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "tracer.h"

Include dependency graph for tracer.cc:

Functions
static void	analyze_bb (basic_block, int *)

static bool	better_p (const_edge, const_edge)

static edge	find_best_successor (basic_block)

static edge	find_best_predecessor (basic_block)

static int	find_trace (basic_block, basic_block *)

static void	mark_bb_seen (basic_block bb)

static bool	bb_seen_p (basic_block bb)

static void	cache_can_duplicate_bb_p (const_basic_block bb, bool val)

static bool	cached_can_duplicate_bb_p (const_basic_block bb)

bool	ignore_bb_p (const_basic_block bb)

basic_block	transform_duplicate (basic_block bb, basic_block bb2)

static bool	tail_duplicate (void)

gimple_opt_pass *	make_pass_tracer (gcc::context *ctxt)

Variables
static int	probability_cutoff

static int	branch_ratio_cutoff

static sbitmap	bb_seen

static sbitmap	can_duplicate_bb

Function Documentation

◆ analyze_bb()

static void analyze_bb	(	basic_block	bb,
		int *	count )

static

The tracer pass for the GNU compiler.
Contributed by Jan Hubicka, SuSE Labs.
Adapted to work on GIMPLE instead of RTL by Robert Kidd, UIUC.
Copyright (C) 2001-2024 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.

This pass performs the tail duplication needed for superblock formation.
For more information see:

  Design and Analysis of Profile-Based Optimization in Compaq's
  Compilation Tools for Alpha; Journal of Instruction-Level
  Parallelism 3 (2000) 1-25

Unlike Compaq's implementation we don't do the loop peeling as most
probably a better job can be done by a special pass and we don't
need to worry too much about the code size implications as the tail
duplicates are crossjumped again if optimizations are not
performed.

Return number of instructions in the block.

References cache_can_duplicate_bb_p(), can_duplicate_block_p(), CONST_CAST_BB, count, eni_size_weights, estimate_num_insns(), gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().

Referenced by tail_duplicate().

◆ bb_seen_p()

static bool bb_seen_p ( basic_block bb )

inlinestatic

References bb_seen, bitmap_bit_p, and basic_block_def::index.

Referenced by find_trace(), and tail_duplicate().

◆ better_p()

static bool better_p	(	const_edge	e1,
		const_edge	e2 )

static

Return true if E1 is more frequent than E2.

Referenced by find_best_predecessor(), and find_best_successor().

◆ cache_can_duplicate_bb_p()

static void cache_can_duplicate_bb_p	(	const_basic_block	bb,
		bool	val )

inlinestatic

Cache VAL as value of can_duplicate_bb_p for BB.

References bitmap_set_bit, can_duplicate_bb, and basic_block_def::index.

Referenced by analyze_bb().

◆ cached_can_duplicate_bb_p()

static bool cached_can_duplicate_bb_p ( const_basic_block bb )

static

Return cached value of can_duplicate_bb_p for BB.

References bitmap_bit_p, can_duplicate_bb, can_duplicate_block_p(), basic_block_def::index, and SBITMAP_SIZE.

Referenced by ignore_bb_p().

◆ find_best_predecessor()

static edge find_best_predecessor ( basic_block bb )

static

Return most frequent predecessor of basic block BB.

References better_p(), branch_ratio_cutoff, cfun, basic_block_def::count, FOR_EACH_EDGE, ignore_bb_p(), profile_count::initialized_p(), NULL, basic_block_def::preds, REG_BR_PROB_BASE, and profile_count::to_frequency().

Referenced by find_trace().

◆ find_best_successor()

static edge find_best_successor ( basic_block bb )

static

Return most frequent successor of basic block BB.

References better_p(), FOR_EACH_EDGE, ignore_bb_p(), NULL, probability_cutoff, and basic_block_def::succs.

Referenced by find_trace().

◆ find_trace()

static int find_trace	(	basic_block	bb,
		basic_block *	trace )

static

Find the trace using bb and record it in the TRACE array.
Return number of basic blocks recorded.

References bb_seen_p(), cfun, basic_block_def::count, dump_file, EDGE_COMPLEX, find_best_predecessor(), find_best_successor(), i, basic_block_def::index, NULL, and profile_count::to_frequency().

Referenced by tail_duplicate().

◆ ignore_bb_p()

bool ignore_bb_p ( const_basic_block bb )

Return true if we should ignore the basic block for purposes of tracing.

References cached_can_duplicate_bb_p(), basic_block_def::index, NUM_FIXED_BLOCKS, and optimize_bb_for_size_p().

Referenced by find_best_predecessor(), find_best_successor(), find_block_to_duplicate_for_splitting_paths(), and tail_duplicate().

◆ make_pass_tracer()

gimple_opt_pass * make_pass_tracer ( gcc::context * ctxt )

◆ mark_bb_seen()

static void mark_bb_seen ( basic_block bb )

inlinestatic

References bb_seen, bitmap_set_bit, basic_block_def::index, sbitmap_resize(), and SBITMAP_SIZE.

Referenced by tail_duplicate().

◆ tail_duplicate()

static bool tail_duplicate ( void )

static

Look for basic blocks in frequency order, construct traces and tail duplicate
if profitable.

References analyze_bb(), bb_seen, bb_seen_p(), bitmap_clear(), branch_ratio_cutoff, can_duplicate_bb, can_duplicate_block_p(), cfun, changed, basic_block_def::count, fibonacci_heap< K, V >::delete_node(), dump_file, EDGE_COUNT, fibonacci_heap< K, V >::empty(), fibonacci_heap< K, V >::extract_min(), find_trace(), FOR_EACH_BB_FN, free(), free_original_copy_tables(), gcc_assert, loop::header, ignore_bb_p(), basic_block_def::index, initialize_original_copy_tables(), fibonacci_heap< K, V >::insert(), last_basic_block_for_fn, LONG_MIN, basic_block_def::loop_father, mark_bb_seen(), n_basic_blocks_for_fn, NULL, basic_block_def::preds, probability_cutoff, profile_info, PROFILE_READ, profile_status_for_fn, REG_BR_PROB_BASE, sbitmap_alloc(), sbitmap_free(), profile_count::to_frequency(), and transform_duplicate().

◆ transform_duplicate()

basic_block transform_duplicate	(	basic_block	bb,
		basic_block	bb2 )

Duplicate block BB2, placing it after BB in the CFG.  Return the
newly created block.

References add_phi_args_after_copy(), duplicate_block(), find_edge(), flush_pending_stmts(), and NULL.

Referenced by split_paths(), and tail_duplicate().

Variable Documentation

◆ bb_seen

sbitmap bb_seen

static

A bit BB->index is set if BB has already been seen, i.e. it is
connected to some trace already.

Referenced by bb_seen_p(), mark_bb_seen(), and tail_duplicate().

◆ branch_ratio_cutoff

int branch_ratio_cutoff

static

Referenced by find_best_predecessor(), and tail_duplicate().

◆ can_duplicate_bb

sbitmap can_duplicate_bb

static

Referenced by cache_can_duplicate_bb_p(), cached_can_duplicate_bb_p(), and tail_duplicate().

◆ probability_cutoff

int probability_cutoff

static

Minimal outgoing edge probability considered for superblock formation.

Referenced by find_best_successor(), and tail_duplicate().

Functions

Variables

Function Documentation

◆ analyze_bb()

◆ bb_seen_p()

◆ better_p()

◆ cache_can_duplicate_bb_p()

◆ cached_can_duplicate_bb_p()

◆ find_best_predecessor()

◆ find_best_successor()

◆ find_trace()

◆ ignore_bb_p()

◆ make_pass_tracer()

◆ mark_bb_seen()

◆ tail_duplicate()

◆ transform_duplicate()

Variable Documentation

◆ bb_seen

◆ branch_ratio_cutoff

◆ can_duplicate_bb

◆ probability_cutoff