cfg.c File Reference

Data Structures
struct	htab_bb_copy_original_entry
struct	bb_copy_hasher

Functions
void	init_flow ()
static void	free_edge ()
void	clear_edges ()
basic_block	alloc_block ()
void	link_block ()
void	unlink_block ()
void	compact_blocks ()
void	expunge_block ()
static void	connect_src ()
static void	connect_dest ()
static void	disconnect_src ()
static void	disconnect_dest ()
edge	unchecked_make_edge ()
edge	cached_make_edge ()
edge	make_edge ()
edge	make_single_succ_edge ()
void	remove_edge_raw ()
void	redirect_edge_succ ()
void	redirect_edge_pred ()
void	clear_bb_flags ()
static void	check_bb_profile ()
void	dump_edge_info ()
DEBUG_FUNCTION void	debug ()
static void	alloc_aux_for_block ()
void	alloc_aux_for_blocks ()
void	clear_aux_for_blocks ()
void	free_aux_for_blocks ()
void	alloc_aux_for_edge ()
void	alloc_aux_for_edges ()
void	clear_aux_for_edges ()
void	free_aux_for_edges ()
DEBUG_FUNCTION void	debug_bb ()
DEBUG_FUNCTION basic_block	debug_bb_n ()
void	dump_bb_info (FILE *outf, basic_block bb, int indent, int flags, bool do_header, bool do_footer)
void	brief_dump_cfg ()
void	update_bb_profile_for_threading (basic_block bb, int edge_frequency, gcov_type count, edge taken_edge)
void	scale_bbs_frequencies_int ()
void	scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num, gcov_type den)
void	initialize_original_copy_tables ()
void	free_original_copy_tables ()
static void	copy_original_table_clear ()
static void	copy_original_table_set (hash_table< bb_copy_hasher > tab, unsigned obj, unsigned val)
void	set_bb_original ()
basic_block	get_bb_original ()
void	set_bb_copy ()
basic_block	get_bb_copy ()
void	set_loop_copy ()
struct loop *	get_loop_copy ()

Variables
static struct obstack	block_aux_obstack
static void *	first_block_aux_obj = 0
static struct obstack	edge_aux_obstack
static void *	first_edge_aux_obj = 0
static hash_table< bb_copy_hasher >	bb_original
static hash_table< bb_copy_hasher >	bb_copy
static hash_table< bb_copy_hasher >	loop_copy
static alloc_pool	original_copy_bb_pool

---

Function Documentation

static void alloc_aux_for_block ( )

static

   Allocate a memory block of SIZE as BB->aux.  The obstack must
   be first initialized by alloc_aux_for_blocks.  

     Verify that aux field is clear.  

References basic_block_def::aux.

void alloc_aux_for_blocks

(

)

   Initialize the block_aux_obstack and if SIZE is nonzero, call
   alloc_aux_for_block for each basic block.  

       Check whether AUX data are still allocated.  

References block_aux_obstack, and clear_aux_for_blocks().

void alloc_aux_for_edge

(

)

   Allocate a memory edge of SIZE as E->aux.  The obstack must
   be first initialized by alloc_aux_for_edges.  

     Verify that aux field is clear.  

References edge_def::aux, and basic_block_def::succs.

void alloc_aux_for_edges

(

)

   Initialize the edge_aux_obstack and if SIZE is nonzero, call
   alloc_aux_for_edge for each basic edge.  

       Check whether AUX data are still allocated.  

References clear_aux_for_edges(), and edge_aux_obstack.

basic_block alloc_block

(

void

)

   Allocate memory for basic_block.  

References basic_block_def::next_bb, and basic_block_def::prev_bb.

void brief_dump_cfg

(

)

   Dumps a brief description of cfg to FILE.  

edge cached_make_edge

(

)

   Create an edge connecting SRC and DST with FLAGS optionally using
   edge cache CACHE.  Return the new edge, NULL if already exist.  

     Does the requested edge already exist?  

         The edge does not exist.  Create one and update the
         cache.  

     At this point, we know that the requested edge exists.  Adjust
     flags if necessary.  

References find_edge(), and edge_def::flags.

static void check_bb_profile ( )

static

   Check the consistency of profile information.  We can't do that
   in verify_flow_info, as the counts may get invalid for incompletely
   solved graphs, later eliminating of conditionals or roundoff errors.
   It is still practical to have them reported for debugging of simple
   testcases.  

         Warn about inconsistencies in the partitioning that are
         currently caused by profile insanities created via optimization.  

References basic_block_def::count, basic_block_def::frequency, and basic_block_def::preds.

void clear_aux_for_blocks

(

void

)

   Clear AUX pointers of all blocks.  

References edge_aux_obstack.

Referenced by alloc_aux_for_blocks(), and duplicate_computed_gotos().

void clear_aux_for_edges

(

void

)

   Clear AUX pointers of all edges.  

References first, and memset().

Referenced by alloc_aux_for_edges().

void clear_bb_flags

(

void

)

   Clear all basic block flags that do not have to be preserved.  

Referenced by reorder_basic_blocks().

void clear_edges

(

void

)

   Free the memory associated with the edge structures.  

References free_edge(), basic_block_def::preds, basic_block_def::succs, and vec_safe_truncate().

void compact_blocks

(

void

)

   Sequentially order blocks and compact the arrays.  

References basic_block_def::index.

Referenced by cleanup_tree_cfg_1().

static void connect_dest ( )

inlinestatic

   Connect E to E->dest.  

References df_mark_solutions_dirty(), edge_iterator::index, and basic_block_def::succs.

Referenced by disconnect_dest(), and make_single_succ_edge().

static void connect_src ( )

inlinestatic

   Connect E to E->src.  

Referenced by disconnect_dest().

static void copy_original_table_clear ( )

static

   Removes the value associated with OBJ from table TAB.  

References copy_original_table_set(), and basic_block_def::index.

static void copy_original_table_set ( hash_table< bb_copy_hasher >  tab, unsigned  obj, unsigned  val  )

static

   Sets the value associated with OBJ in table TAB to VAL.
   Do nothing when data structures are not initialized.  

Referenced by copy_original_table_clear().

DEBUG_FUNCTION void debug

(

)

     FIXME (crowl): Is this desireable?  

DEBUG_FUNCTION void debug_bb

(

)

DEBUG_FUNCTION basic_block debug_bb_n

(

)

static void disconnect_dest ( )

inlinestatic

   Disconnect edge E from E->dest.  

     If we removed an edge in the middle of the edge vector, we need
     to update dest_idx of the edge that moved into the "hole".  

References connect_dest(), connect_src(), edge_def::dest, execute_on_growing_pred(), edge_def::flags, and edge_def::src.

Referenced by make_single_succ_edge().

static void disconnect_src ( )

inlinestatic

   Disconnect edge E from E->src.  

void dump_bb_info	(	FILE *	outf,
		basic_block	bb,
		int	indent,
		int	flags,
		bool	do_header,
		bool	do_footer
	)

   Dumps cfg related information about basic block BB to OUTF.
   If HEADER is true, dump things that appear before the instructions
   contained in BB.  If FOOTER is true, dump things that appear after.
   Flags are the TDF_* masks as documented in dumpfile.h.
   NB: With TDF_DETAILS, it is assumed that cfun is available, so
   that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.  

void dump_edge_info

(

)

     ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
     Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency.  

void expunge_block

(

)

   Remove block B from the basic block array.  

     We should be able to ggc_free here, but we are not.
     The dead SSA_NAMES are left pointing to dead statements that are pointing
     to dead basic blocks making garbage collector to die.
     We should be able to release all dead SSA_NAMES and at the same time we should
     clear out BB pointer of dead statements consistently.  

void free_aux_for_blocks

(

void

)

   Free data allocated in block_aux_obstack and clear AUX pointers
   of all blocks.  

References alloc_aux_for_edge(), and basic_block_def::succs.

void free_aux_for_edges

(

void

)

   Free data allocated in edge_aux_obstack and clear AUX pointers
   of all edges.  

static void free_edge ( )

static

   Helper function for remove_edge and clear_edges.  Frees edge structure
   without actually removing it from the pred/succ arrays.  

Referenced by clear_edges().

void free_original_copy_tables

(

void

)

   Free the data structures to maintain mapping between blocks and
   its copies.  

References hash_table< Descriptor, Allocator >::find(), basic_block_def::index, htab_bb_copy_original_entry::index1, and htab_bb_copy_original_entry::index2.

Referenced by ssa_name_has_uses_outside_loop_p(), vect_create_cond_for_alias_checks(), and vect_update_ivs_after_vectorizer().

basic_block get_bb_copy

(

)

   Get the copy of basic block.  

basic_block get_bb_original

(

)

   Get the original basic block.  

struct loop* get_loop_copy ( )

read

   Get the copy of LOOP.  

void init_flow

(

)

   Called once at initialization time.  

void initialize_original_copy_tables

(

void

)

   Initialize the data structures to maintain mapping between blocks
   and its copies.  

Referenced by ssa_name_has_uses_outside_loop_p(), vect_create_cond_for_alias_checks(), and vect_update_ivs_after_vectorizer().

void link_block

(

)

   Link block B to chain after AFTER.  

References basic_block_def::next_bb, and basic_block_def::prev_bb.

edge make_edge

(

)

   Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
   created edge or NULL if already exist.  

     Make sure we don't add duplicate edges.  

edge make_single_succ_edge

(

)

   Create an edge connecting SRC to DEST and set probability by knowing
   that it is the single edge leaving SRC.  

References connect_dest(), edge_def::dest, disconnect_dest(), and execute_on_shrinking_pred().

void redirect_edge_pred

(

)

   Redirect an edge's predecessor from one block to another.  

     Reconnect the edge to the new predecessor block.  

void redirect_edge_succ

(

)

   Redirect an edge's successor from one block to another.  

     Reconnect the edge to the new successor block.  

References basic_block_def::flags.

void remove_edge_raw

(

)

   This function will remove an edge from the flow graph.  

void scale_bbs_frequencies_gcov_type	(	basic_block *	bbs,
		int	nbbs,
		gcov_type	num,
		gcov_type	den
	)

   Multiply all frequencies of basic blocks in array BBS of length NBBS
   by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
   function but considerably slower.  

void scale_bbs_frequencies_int

(

)

   Multiply all frequencies of basic blocks in array BBS of length NBBS
   by NUM/DEN, in int arithmetic.  May lose some accuracy.  

     Scale NUM and DEN to avoid overflows.  Frequencies are in order of
     10^4, if we make DEN <= 10^3, we can afford to upscale by 100
     and still safely fit in int during calculations.  

         Make sure the frequencies do not grow over BB_FREQ_MAX.  

void set_bb_copy

(

)

   Set copy for basic block.  Do nothing when data structures are not
   initialized so passes not needing this don't need to care.  

void set_bb_original

(

)

   Set original for basic block.  Do nothing when data structures are not
   initialized so passes not needing this don't need to care.  

void set_loop_copy

(

)

   Set copy for LOOP to COPY.  Do nothing when data structures are not
   initialized so passes not needing this don't need to care.  

edge unchecked_make_edge

(

)

   Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
   created edge.  Use this only if you are sure that this edge can't
   possibly already exist.  

References bitmap_bit_p(), bitmap_set_bit(), basic_block_def::index, make_edge(), and unchecked_make_edge().

void unlink_block

(

)

   Unlink block B from chain.  

References df, and df_compact_blocks().

void update_bb_profile_for_threading	(	basic_block	bb,
		int	edge_frequency,
		gcov_type	count,
		edge	taken_edge
	)

   An edge originally destinating BB of FREQUENCY and COUNT has been proved to
   leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
   redirected to destination of TAKEN_EDGE.

   This function may leave the profile inconsistent in the case TAKEN_EDGE
   frequency or count is believed to be lower than FREQUENCY or COUNT
   respectively.  

     Compute the probability of TAKEN_EDGE being reached via threaded edge.
     Watch for overflows.  

     Now rescale the probabilities.  

             Protect from overflow due to additional scaling.  

References edge_def::probability, and basic_block_def::succs.

---

Variable Documentation

hash_table<bb_copy_hasher> bb_copy

static

hash_table<bb_copy_hasher> bb_original

static

   Data structures used to maintain mapping between basic blocks and
   copies.  

struct obstack block_aux_obstack

static

   Simple routines to easily allocate AUX fields of basic blocks.  

Referenced by alloc_aux_for_blocks().

struct obstack edge_aux_obstack

static

Referenced by alloc_aux_for_edges(), and clear_aux_for_blocks().

void* first_block_aux_obj = 0

static

void* first_edge_aux_obj = 0

static

hash_table<bb_copy_hasher> loop_copy

static

   And between loops and copies.  

alloc_pool original_copy_bb_pool

static