GCC Middle and Back End API Reference
basic-block.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  edge_def
union  edge_def::edge_def_insns
struct  profile_record
struct  rtl_bb_info
struct  gimple_bb_info
struct  basic_block_def
union  basic_block_def::basic_block_il_dependent
struct  control_flow_graph
struct  ce_if_block
struct  edge_list
class  control_dependences
struct  edge_iterator


typedef int __assert_gimple_bb_smaller_rtl_bb [(int) sizeof(struct rtl_bb_info)-(int) sizeof(struct gimple_bb_info)]
typedef struct ce_if_block ce_if_block_t
typedef struct


enum  cfg_edge_flags { LAST_CFG_EDGE_FLAG }
enum  cfg_bb_flags { LAST_CFG_BB_FLAG }
enum  dom_state { DOM_NONE, DOM_NO_FAST_QUERY, DOM_OK }
enum  replace_direction { dir_none, dir_forward, dir_backward, dir_both }
enum  cdi_direction { CDI_DOMINATORS = 1, CDI_POST_DOMINATORS = 2 }


void gt_ggc_mx (edge_def *e)
void gt_pch_nx (edge_def *e)
void gt_pch_nx (edge_def *e, gt_pointer_operator, void *)
void compute_bb_for_insn (void)
unsigned int free_bb_for_insn (void)
void update_bb_for_insn (basic_block)
void insert_insn_on_edge (rtx, edge)
basic_block split_edge_and_insert (edge, rtx)
void commit_one_edge_insertion (edge e)
void commit_edge_insertions (void)
edge unchecked_make_edge (basic_block, basic_block, int)
edge cached_make_edge (sbitmap, basic_block, basic_block, int)
edge make_edge (basic_block, basic_block, int)
edge make_single_succ_edge (basic_block, basic_block, int)
void remove_edge_raw (edge)
void redirect_edge_succ (edge, basic_block)
edge redirect_edge_succ_nodup (edge, basic_block)
void redirect_edge_pred (edge, basic_block)
basic_block create_basic_block_structure (rtx, rtx, rtx, basic_block)
void clear_bb_flags (void)
void dump_bb_info (FILE *, basic_block, int, int, bool, bool)
void dump_edge_info (FILE *, edge, int, int)
void debug (edge_def &ref)
void debug (edge_def *ptr)
void brief_dump_cfg (FILE *, int)
void clear_edges (void)
void scale_bbs_frequencies_int (basic_block *, int, int, int)
void scale_bbs_frequencies_gcov_type (basic_block *, int, gcov_type, gcov_type)
static bool single_succ_p ()
static bool single_pred_p ()
static edge single_succ_edge ()
static edge single_pred_edge ()
static basic_block single_succ ()
static basic_block single_pred ()
static vec< edge, va_gc > * ei_container ()
static edge_iterator ei_start_1 ()
static edge_iterator ei_last_1 ()
static bool ei_end_p ()
static bool ei_one_before_end_p ()
static void ei_next ()
static void ei_prev ()
static edge ei_edge ()
static edge ei_safe_edge ()
static bool ei_cond ()
void bitmap_intersection_of_succs (sbitmap, sbitmap *, basic_block)
void bitmap_intersection_of_preds (sbitmap, sbitmap *, basic_block)
void bitmap_union_of_succs (sbitmap, sbitmap *, basic_block)
void bitmap_union_of_preds (sbitmap, sbitmap *, basic_block)
struct edge_listpre_edge_lcm (int, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap **, sbitmap **)
struct edge_listpre_edge_rev_lcm (int, sbitmap *, sbitmap *, sbitmap *, sbitmap *, sbitmap **, sbitmap **)
void compute_available (sbitmap *, sbitmap *, sbitmap *, sbitmap *)
bool maybe_hot_bb_p (struct function *, const_basic_block)
bool maybe_hot_edge_p (edge)
bool probably_never_executed_bb_p (struct function *, const_basic_block)
bool probably_never_executed_edge_p (struct function *, edge)
bool optimize_bb_for_size_p (const_basic_block)
bool optimize_bb_for_speed_p (const_basic_block)
bool optimize_edge_for_size_p (edge)
bool optimize_edge_for_speed_p (edge)
bool optimize_loop_for_size_p (struct loop *)
bool optimize_loop_for_speed_p (struct loop *)
bool optimize_loop_nest_for_size_p (struct loop *)
bool optimize_loop_nest_for_speed_p (struct loop *)
bool gimple_predicted_by_p (const_basic_block, enum br_predictor)
bool rtl_predicted_by_p (const_basic_block, enum br_predictor)
void gimple_predict_edge (edge, enum br_predictor, int)
void rtl_predict_edge (edge, enum br_predictor, int)
void predict_edge_def (edge, enum br_predictor, enum prediction)
void guess_outgoing_edge_probabilities (basic_block)
void remove_predictions_associated_with_edge (edge)
bool edge_probability_reliable_p (const_edge)
bool br_prob_note_reliable_p (const_rtx)
bool predictable_edge_p (edge)
void init_flow (struct function *)
void debug_bb (basic_block)
basic_block debug_bb_n (int)
void dump_flow_info (FILE *, int)
void expunge_block (basic_block)
void link_block (basic_block, basic_block)
void unlink_block (basic_block)
void compact_blocks (void)
basic_block alloc_block (void)
void alloc_aux_for_blocks (int)
void clear_aux_for_blocks (void)
void free_aux_for_blocks (void)
void alloc_aux_for_edge (edge, int)
void alloc_aux_for_edges (int)
void clear_aux_for_edges (void)
void free_aux_for_edges (void)
void find_unreachable_blocks (void)
bool mark_dfs_back_edges (void)
struct edge_listcreate_edge_list (void)
void free_edge_list (struct edge_list *)
void print_edge_list (FILE *, struct edge_list *)
void verify_edge_list (FILE *, struct edge_list *)
int find_edge_index (struct edge_list *, basic_block, basic_block)
edge find_edge (basic_block, basic_block)
void remove_fake_edges (void)
void remove_fake_exit_edges (void)
void add_noreturn_fake_exit_edges (void)
void connect_infinite_loops_to_exit (void)
int post_order_compute (int *, bool, bool)
basic_block dfs_find_deadend (basic_block)
int inverted_post_order_compute (int *)
int pre_and_rev_post_order_compute_fn (struct function *, int *, int *, bool)
int pre_and_rev_post_order_compute (int *, int *, bool)
int dfs_enumerate_from (basic_block, int, bool(*)(const_basic_block, const void *), basic_block *, int, const void *)
void compute_dominance_frontiers (struct bitmap_head_def *)
bitmap compute_idf (bitmap, struct bitmap_head_def *)
basic_blocksingle_pred_before_succ_order (void)
rtx block_label (basic_block)
rtx bb_note (basic_block)
bool purge_all_dead_edges (void)
bool purge_dead_edges (basic_block)
bool fixup_abnormal_edges (void)
basic_block force_nonfallthru_and_redirect (edge, basic_block, rtx)
bool contains_no_active_insn_p (const_basic_block)
bool forwarder_block_p (const_basic_block)
bool can_fallthru (basic_block, basic_block)
void emit_barrier_after_bb (basic_block bb)
void fixup_partitions (void)
void find_many_sub_basic_blocks (sbitmap)
void rtl_make_eh_edge (sbitmap, basic_block, rtx)
bool cleanup_cfg (int)
int flow_find_cross_jump (basic_block, basic_block, rtx *, rtx *, enum replace_direction *)
int flow_find_head_matching_sequence (basic_block, basic_block, rtx *, rtx *, int)
bool delete_unreachable_blocks (void)
void update_br_prob_note (basic_block)
bool inside_basic_block_p (const_rtx)
bool control_flow_insn_p (const_rtx)
rtx get_last_bb_insn (basic_block)
enum dom_state dom_info_state (enum cdi_direction)
void set_dom_info_availability (enum cdi_direction, enum dom_state)
bool dom_info_available_p (enum cdi_direction)
void calculate_dominance_info (enum cdi_direction)
void free_dominance_info (enum cdi_direction)
basic_block nearest_common_dominator (enum cdi_direction, basic_block, basic_block)
basic_block nearest_common_dominator_for_set (enum cdi_direction, bitmap)
void set_immediate_dominator (enum cdi_direction, basic_block, basic_block)
basic_block get_immediate_dominator (enum cdi_direction, basic_block)
bool dominated_by_p (enum cdi_direction, const_basic_block, const_basic_block)
vec< basic_blockget_dominated_by (enum cdi_direction, basic_block)
vec< basic_blockget_dominated_by_region (enum cdi_direction, basic_block *, unsigned)
vec< basic_blockget_dominated_to_depth (enum cdi_direction, basic_block, int)
vec< basic_blockget_all_dominated_blocks (enum cdi_direction, basic_block)
void add_to_dominance_info (enum cdi_direction, basic_block)
void delete_from_dominance_info (enum cdi_direction, basic_block)
basic_block recompute_dominator (enum cdi_direction, basic_block)
void redirect_immediate_dominators (enum cdi_direction, basic_block, basic_block)
void iterate_fix_dominators (enum cdi_direction, vec< basic_block >, bool)
void verify_dominators (enum cdi_direction)
basic_block first_dom_son (enum cdi_direction, basic_block)
basic_block next_dom_son (enum cdi_direction, basic_block)
unsigned bb_dom_dfs_in (enum cdi_direction, basic_block)
unsigned bb_dom_dfs_out (enum cdi_direction, basic_block)
edge try_redirect_by_replacing_jump (edge, basic_block, bool)
void break_superblocks (void)
void relink_block_chain (bool)
void update_bb_profile_for_threading (basic_block, int, gcov_type, edge)
void init_rtl_bb_info (basic_block)
void initialize_original_copy_tables (void)
void free_original_copy_tables (void)
void set_bb_original (basic_block, basic_block)
basic_block get_bb_original (basic_block)
void set_bb_copy (basic_block, basic_block)
basic_block get_bb_copy (basic_block)
void set_loop_copy (struct loop *, struct loop *)
struct loopget_loop_copy (struct loop *)
static bool bb_has_eh_pred ()
static bool bb_has_abnormal_pred ()
static edge find_fallthru_edge ()
bool mfb_keep_just (edge)
void rtl_profile_for_bb (basic_block)
void rtl_profile_for_edge (edge)
void default_rtl_profile (void)
gcov_working_set_tfind_working_set (unsigned pct_times_10)
static void check_probability ()
static int combine_probabilities ()
static gcov_type apply_scale ()
static gcov_type apply_probability ()
static int inverse_probability ()


struct gcov_ctr_summaryprofile_info
edge mfb_kj_edge

Typedef Documentation

typedef int __assert_gimple_bb_smaller_rtl_bb[(int) sizeof(struct rtl_bb_info)-(int) sizeof(struct gimple_bb_info)]
   This ensures that struct gimple_bb_info is smaller than
   struct rtl_bb_info, so that inlining the former into basic_block_def
   is the better choice.  
typedef struct ce_if_block ce_if_block_t
   Structure to group all of the information to process IF-THEN and
   IF-THEN-ELSE blocks for the conditional execution support.  This
   needs to be in a public file in case the IFCVT macros call
   functions passing the ce_if_block data structure.  
   In profile.c.  

Enumeration Type Documentation

   In dominance.c 
enum dom_state
   State of dominance information.  
   What sort of profiling information we have.  

Function Documentation

void add_noreturn_fake_exit_edges ( void  )
   This function will add a fake edge between any block which has no
   successors, and the exit block. Some data flow equations require these
   edges to exist.  

Referenced by output_location(), and pre_insert_copies().

void add_to_dominance_info ( enum  cdi_direction,
void alloc_aux_for_blocks ( int  )
void alloc_aux_for_edge ( edge  ,

Referenced by free_aux_for_blocks().

void alloc_aux_for_edges ( int  )
basic_block alloc_block ( void  )
   Allocate memory for basic_block.  

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

static gcov_type apply_probability ( )
   Apply probability PROB on frequency or count FREQ.  

Referenced by cgraph_clone_edge(), and expand_transaction().

static gcov_type apply_scale ( )
   Apply scale factor SCALE on frequency or count FREQ. Use this
   interface when potentially scaling up, so that SCALE is not
   constrained to be < REG_BR_PROB_BASE.  

Referenced by input_cfg(), and input_profile_summary().

unsigned bb_dom_dfs_in ( enum  cdi_direction,

Referenced by cmp_dfsnum().

unsigned bb_dom_dfs_out ( enum  cdi_direction,

Referenced by cmp_dfsnum().

static bool bb_has_abnormal_pred ( )
   Return true when one of the predecessor edges of BB is marked with EDGE_ABNORMAL.  

Referenced by replace_pseudos_in().

static bool bb_has_eh_pred ( )
   Return true when one of the predecessor edges of BB is marked with EDGE_EH.  

Referenced by mark_regno_birth_or_death().

rtx bb_note ( basic_block  )
void bitmap_intersection_of_preds ( sbitmap  ,
sbitmap ,

Referenced by compute_available().

void bitmap_intersection_of_succs ( sbitmap  ,
sbitmap ,
   In cfganal.c 
void bitmap_union_of_preds ( sbitmap  ,
sbitmap ,

Referenced by compute_kill(), and compute_out().

void bitmap_union_of_succs ( sbitmap  ,
sbitmap ,
bool br_prob_note_reliable_p ( const_rtx  )
void break_superblocks ( void  )
   Splits superblocks.  
void brief_dump_cfg ( FILE *  ,
edge cached_make_edge ( sbitmap  ,
basic_block  ,
basic_block  ,
void calculate_dominance_info ( enum  cdi_direction)
bool can_fallthru ( basic_block  ,
static void check_probability ( )
   Check tha probability is sane.  
bool cleanup_cfg ( int  )
   In cfgcleanup.c.  

Referenced by migrate_btr_defs(), and remove_death().

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().

static int combine_probabilities ( )
   Given PROB1 and PROB2, return PROB1*PROB2/REG_BR_PROB_BASE. 
   Used to combine BB probabilities.  

Referenced by estimate_ipcp_clone_size_and_time().

void commit_edge_insertions ( void  )
   Update the CFG for all queued instructions.  
     Optimization passes that invoke this routine can cause hot blocks
     previously reached by both hot and cold blocks to become dominated only
     by cold blocks. This will cause the verification below to fail,
     and lead to now cold code in the hot section. In some cases this
     may only be visible after newly unreachable blocks are deleted,
     which will be done by fixup_partitions.  

Referenced by cfg_layout_can_merge_blocks_p().

void commit_one_edge_insertion ( edge  e)
void compact_blocks ( void  )
   Sequentially order blocks and compact the arrays.  

References basic_block_def::index.

Referenced by cleanup_tree_cfg_1().

void compute_available ( sbitmap avloc,
sbitmap kill,
sbitmap avout,
sbitmap avin 
   Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
   Return the number of passes we performed to iterate to a solution.  
     Allocate a worklist array/queue.  Entries are only added to the
     list if they were not already on the list.  So the size is
     bounded by the number of basic blocks.  
     We want a maximal solution.  
     Put every block on the worklist; this is necessary because of the
     optimistic initialization of AVOUT above.  
     Mark blocks which are successors of the entry block so that we
     can easily identify them below.  
     Iterate until the worklist is empty.  
         Take the first entry off the worklist.  
         If one of the predecessor blocks is the ENTRY block, then the
         intersection of avouts is the null set.  We can identify such blocks
         by the special value in the AUX field in the block structure.  
           Do not clear the aux field for blocks which are successors of the
           ENTRY block.  That way we never add then to the worklist again.  
             Clear the aux field of this block so that it can be added to
             the worklist again if necessary.  
           If the out state of this block changed, then we need
           to add the successors of this block to the worklist
           if they are not already on the worklist.  

References basic_block_def::aux, bitmap_clear(), bitmap_intersection_of_preds(), bitmap_ior_and_compl(), edge_def::dest, basic_block_def::index, basic_block_def::succs, and worklist.

Referenced by compute_insert_delete(), and free_cprop_mem().

void compute_bb_for_insn ( void  )
   Records the basic block struct in BLOCK_FOR_INSN for every insn.  

References df_analyze(), df_note_add_problem(), free_bb_for_insn(), and insert_section_boundary_note().

void compute_dominance_frontiers ( struct bitmap_head_def )
bitmap compute_idf ( bitmap  ,
struct bitmap_head_def  
void connect_infinite_loops_to_exit ( void  )
   This function adds a fake edge between any infinite loops to the
   exit block.  Some optimizations require a path from each node to
   the exit node.

   See also Morgan, Figure 3.10, pp. 82-83.

   The current implementation is ugly, not attempting to minimize the
   number of inserted fake edges.  To reduce the number of fake edges
   to insert, add fake edges from _innermost_ loops containing only
   nodes not reachable from the exit block.  
     Perform depth-first search in the reverse graph to find nodes
     reachable from the exit block.  
     Repeatedly add fake edges, updating the unreachable nodes.  
bool contains_no_active_insn_p ( const_basic_block  )
bool control_flow_insn_p ( const_rtx  )
basic_block create_basic_block_structure ( rtx  ,
rtx  ,
rtx  ,
struct edge_list* create_edge_list ( void  )
   Functions to access an edge list with a vector representation.
   Enough data is kept such that given an index number, the
   pred and succ that edge represents can be determined, or
   given a pred and a succ, its index number can be returned.
   This allows algorithms which consume a lot of memory to
   represent the normally full matrix of edge (pred,succ) with a
   single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
   wasted space in the client code due to sparse flow graphs.  
   This functions initializes the edge list. Basically the entire
   flowgraph is processed, and all edges are assigned a number,
   and the data structure is filled in.  
     Determine the number of edges in the flow graph by counting successor
     edges on each basic block.  
     Follow successors of blocks, and register these edges.  

References free().

Referenced by compute_insert_delete().

void debug ( edge_def ref)
void debug ( edge_def ptr)
void debug_bb ( basic_block  )
basic_block debug_bb_n ( int  )
void default_rtl_profile ( void  )
   Set RTL expansion to default mode (i.e. when profile info is not known).  

References pointer_map_contains().

Referenced by blocks_nreverse().

void delete_from_dominance_info ( enum  cdi_direction,
bool delete_unreachable_blocks ( void  )
   Delete all unreachable basic blocks.  
     When we're in GIMPLE mode and there may be debug insns, we should
     delete blocks in reverse dominator order, so as to get a chance
     to substitute all released DEFs into debug stmts.  If we don't
     have dominators information, walking blocks backward gets us a
     better chance of retaining most debug information than
                 Speed up the removal of blocks that don't dominate
                 others.  Walking backwards, this should be the common

Referenced by cleanup_empty_eh_unsplit(), cleanup_tree_cfg_1(), and split_live_ranges_for_shrink_wrap().

int dfs_enumerate_from ( basic_block  bb,
int  reverse,
bool(*)(const_basic_block, const void *)  predicate,
basic_block rslt,
int  rslt_max,
const void *  data 
   Performs dfs search from BB over vertices satisfying PREDICATE;
   if REVERSE, go against direction of edges.  Returns number of blocks
   found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  
     A bitmap to keep track of visited blocks.  Allocating it each time
     this function is called is not possible, since dfs_enumerate_from
     is often used on small (almost) disjoint parts of cfg (bodies of
     loops), and allocating a large sbitmap would lead to quadratic
     Resize the VISITED sbitmap if necessary.  
         Ensure that we increase the size of the sbitmap exponentially.  

References bitmap_set_bit(), CDI_DOMINATORS, get_immediate_dominator(), basic_block_def::index, basic_block_def::preds, and edge_def::src.

Referenced by thread_single_edge().

basic_block dfs_find_deadend ( basic_block  )

Referenced by remove_fake_exit_edges().

bool dom_info_available_p ( enum  cdi_direction)
enum dom_state dom_info_state ( enum  cdi_direction)
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 ( FILE *  ,
edge  ,
int  ,
void dump_flow_info ( FILE *  ,

Referenced by dump_flow_info().

bool edge_probability_reliable_p ( const_edge  )
static bool ei_cond ( )
   Return 1 if we should continue to iterate.  Return 0 otherwise.
   *Edge P is set to the next edge if we are to continue to iterate
   and NULL otherwise.  
static vec<edge, va_gc>* ei_container ( )

Referenced by insert_store().

static edge ei_edge ( )
   Return the edge pointed to by the iterator `i'.  

Referenced by insert_store(), and link_roots().

static bool ei_end_p ( )
   Is the iterator `i' at the end of the sequence?  

Referenced by insert_store(), and link_roots().

static edge_iterator ei_last_1 ( )
   Return an iterator pointing to the last element of an edge
static bool ei_one_before_end_p ( )
   Is the iterator `i' at one position before the end of the

Referenced by post_order_compute().

static void ei_prev ( )
   Move the iterator to the previous element.  
static edge ei_safe_edge ( )
   Return an edge pointed to by the iterator.  Do it safely so that
   NULL is returned when the iterator is pointing at the end of the

Referenced by find_edge(), find_implicit_sets(), gimple_expand_cfg(), and move_stmt_r().

static edge_iterator ei_start_1 ( )
   Return an iterator pointing to the start of an edge vector.  
void emit_barrier_after_bb ( basic_block  bb)
void expunge_block ( basic_block  )
int find_edge_index ( struct edge_list ,
basic_block  ,
static edge find_fallthru_edge ( )
   Return the fallthru edge in EDGES if it exists, NULL otherwise.  

Referenced by cfg_layout_initialize(), and find_active_insn_after().

void find_many_sub_basic_blocks ( sbitmap  )
   In cfgbuild.c.  
void find_unreachable_blocks ( void  )
   In cfganal.c  
   Find unreachable blocks.  An unreachable block will have 0 in
   the reachable bit in block->flags.  A nonzero value indicates the
   block is reachable.  
     Clear all the reachability flags.  
     Add our starting points to the worklist.  Almost always there will
     be only one.  It isn't inconceivable that we might one day directly
     support Fortran alternate entry points.  
         Mark the block reachable.  
     Iterate: find everything reachable from what we've already seen.  

References basic_block_def::flags.

Referenced by replace_locals_op().

gcov_working_set_t* find_working_set ( unsigned  pct_times_10)
basic_block first_dom_son ( enum  cdi_direction,
bool fixup_abnormal_edges ( void  )
   This is used by a few passes that emit some instructions after abnormal
   calls, moving the basic block's end, while they in fact do want to emit
   them on the fallthru edge.  Look for abnormal call edges, find backward
   the call in the block and insert the instructions on the edge instead.

   Similarly, handle instructions throwing exceptions internally.

   Return true when instructions have been found and inserted on edges.  
         Look for cases we are interested in - calls or instructions causing
             Get past the new insns generated.  Allow notes, as the insns
             may be already deleted.  
                         Sometimes there's still the return value USE.
                         If it's placed after a trapping call (i.e. that
                         call is the last insn anyway), we have no fallthru
                         edge.  Simply delete this use and don't try to insert
                         on the non-existent edge.  
                             We're not deleting it, we're moving it.  
             It may be that we don't find any trapping insn.  In this
             case we discovered quite late that the insn that had been
             marked as can_throw_internal in fact couldn't trap at all.
             So we should in fact delete the EH edges out of the block.  
void fixup_partitions ( void  )
   Perform cleanup on the hot/cold bb partitioning after optimization
   passes that modify the cfg.  
     Delete any blocks that became unreachable and weren't
     already cleaned up, for example during edge forwarding
     and convert_jumps_to_returns. This will expose more
     opportunities for fixing the partition boundaries here.
     Also, the calculation of the dominance graph during verification
     will assert if there are unreachable nodes.  
     If there are partitions, do a sanity check on them: A basic block in
     a cold partition cannot dominate a basic block in a hot partition.
     Fixup any that now violate this requirement, as a result of edge
     forwarding and unreachable block deletion.  
     Do the partition fixup after all necessary blocks have been converted to
     cold, so that we only update the region crossings the minimum number of
     places, which can require forcing edges to be non fallthru.  

References error(), get_insns(), basic_block_def::index, and print_rtl_with_bb().

int flow_find_cross_jump ( basic_block  bb1,
basic_block  bb2,
rtx f1,
rtx f2,
enum replace_direction dir_p 
   Look through the insns at the end of BB1 and BB2 and find the longest
   sequence that are either equivalent, or allow forward or backward
   replacement.  Store the first insns for that sequence in *F1 and *F2 and
   return the sequence length.

   DIR_P indicates the allowed replacement direction on function entry, and
   the actual replacement direction on function exit.  If NULL, only equivalent
   sequences are allowed.

   To simplify callers of this function, if the blocks match exactly,
   store the head of the blocks in *F1 and *F2.  
     Skip simple jumps at the end of the blocks.  Complex jumps still
     need to be compared for equivalence, which we'll do below.  
         Count everything except for unconditional jump as insn.  
         In the following example, we can replace all jumps to C by jumps to A.

         This removes 4 duplicate insns.
         [bb A] insn1            [bb C] insn1
                insn2                   insn2
         [bb B] insn3                   insn3
                insn4                   insn4
                jump_insn               jump_insn

         We could also replace all jumps to A by jumps to C, but that leaves B
         alive, and removes only 2 duplicate insns.  In a subsequent crossjump
         step, all jumps to B would be replaced with jumps to the middle of C,
         achieving the same result with more effort.
         So we allow only the first possibility, which means that we don't allow
         fallthru in the block that's being replaced.  
         Don't begin a cross-jump with a NOTE insn.  
     Don't allow the insn after a compare to be shared by
     cross-jumping unless the compare is also shared.  
     Include preceding notes and labels in the cross-jump.  One,
     this may bring us to the head of the blocks as requested above.
     Two, it keeps line number notes as matched as may be.  
int flow_find_head_matching_sequence ( basic_block  bb1,
basic_block  bb2,
rtx f1,
rtx f2,
int  stop_after 
   Like flow_find_cross_jump, except start looking for a matching sequence from
   the head of the two blocks.  Do not include jumps at the end.
   If STOP_AFTER is nonzero, stop after finding that many matching
         Ignore notes, except NOTE_INSN_EPILOGUE_BEG.  
         A sanity check to make sure we're not merging insns with different
         effects on EH.  If only one of them ends a basic block, it shouldn't
         have an EH edge; if both end a basic block, there should be the same
         number of EH edges.  
         Don't begin a cross-jump with a NOTE insn.  
     Don't allow a compare to be shared by cross-jumping unless the insn
     after the compare is also shared.  
basic_block force_nonfallthru_and_redirect ( edge  ,
basic_block  ,
bool forwarder_block_p ( const_basic_block  )

Referenced by add_forwarder_blocks().

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.  
unsigned int free_bb_for_insn ( void  )
   Release the basic_block_for_insn array.  

References RTL_PASS, and TV_NONE.

Referenced by compute_bb_for_insn().

void free_edge_list ( struct edge_list )

Referenced by pre_insert_copies().

void free_original_copy_tables ( void  )
vec<basic_block> get_all_dominated_blocks ( enum  cdi_direction,
basic_block get_bb_copy ( basic_block  )
basic_block get_bb_original ( basic_block  )
vec<basic_block> get_dominated_by ( enum  cdi_direction,

Referenced by split_edge_and_insert().

vec<basic_block> get_dominated_by_region ( enum cdi_direction  dir,
basic_block region,
unsigned  n_region 
   Returns the list of basic blocks that are immediately dominated (in
   direction DIR) by some block between N_REGION ones stored in REGION,
   except for blocks in the REGION itself.  

References basic_block_def::dom, dom_convert_dir_to_idx(), DOM_NO_FAST_QUERY, DOM_OK, et_set_father(), et_split(), and et_node::son.

Referenced by move_stmt_r().

vec<basic_block> get_dominated_to_depth ( enum  cdi_direction,
basic_block  ,
basic_block get_immediate_dominator ( enum  cdi_direction,
rtx get_last_bb_insn ( basic_block  )
struct loop* get_loop_copy ( struct loop )
void gimple_predict_edge ( edge  ,
enum  br_predictor,
bool gimple_predicted_by_p ( const_basic_block  ,
enum  br_predictor 
void gt_ggc_mx ( edge_def e)
   Garbage collection and PCH support for edge_def.  
void gt_pch_nx ( edge_def e)
void gt_pch_nx ( edge_def e,
gt_pointer_operator  ,
void *   
void guess_outgoing_edge_probabilities ( basic_block  )
void init_flow ( struct function )
   In cfg.c  
void init_rtl_bb_info ( basic_block  )
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().

bool inside_basic_block_p ( const_rtx  )
static int inverse_probability ( )
   Return inverse probability for PROB.  
int inverted_post_order_compute ( int *  )

Referenced by dom_walker::walk().

void iterate_fix_dominators ( enum cdi_direction  dir,
vec< basic_block bbs,
bool  conservative 
   Recompute dominance information for basic blocks in the set BBS.  The
   function assumes that the immediate dominators of all the other blocks
   in CFG are correct, and that there are no unreachable blocks.

   If CONSERVATIVE is true, we additionally assume that all the ancestors of
   a block of BBS in the current dominance tree dominate it.  
     We only support updating dominators.  There are some problems with
     updating postdominators (need to add fake edges from infinite loops
     and noreturn functions), and since we do not currently use
     iterate_fix_dominators for postdominators, any attempt to handle these
     problems would be unused, untested, and almost surely buggy.  We keep
     the DIR argument for consistency with the rest of the dominator analysis
     The algorithm we use takes inspiration from the following papers, although
     the details are quite different from any of them:

     [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
         Dominator Tree of a Reducible Flowgraph
     [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
          dominator trees
     [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance

     First, we use the following heuristics to decrease the size of the BBS
       a) if BB has a single predecessor, then its immediate dominator is this
       additionally, if CONSERVATIVE is true:
       b) if all the predecessors of BB except for one (X) are dominated by BB,
          then X is the immediate dominator of BB
       c) if the nearest common ancestor of the predecessors of BB is X and
          X -> BB is an edge in CFG, then X is the immediate dominator of BB

     Then, we need to establish the dominance relation among the basic blocks
     in BBS.  We split the dominance tree by removing the immediate dominator
     edges from BBS, creating a forest F.  We form a graph G whose vertices
     are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
     X' -> Y in CFG such that X' belongs to the tree of the dominance forest
     whose root is X.  We then determine dominance tree of G.  Note that
     for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
     In this step, we can use arbitrary algorithm to determine dominators.
     We decided to prefer the algorithm [3] to the algorithm of
     Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
     10 during gcc bootstrap), and [3] should perform better in this case.

     Finally, we need to determine the immediate dominators for the basic
     blocks of BBS.  If the immediate dominator of X in G is Y, then
     the immediate dominator of X in CFG belongs to the tree of F rooted in
     Y.  We process the dominator tree T of G recursively, starting from leaves.
     Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
     subtrees of the dominance tree of CFG rooted in X_i are already correct.
     Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
     the following observations:
       (i) the immediate dominator of all blocks in a strongly connected
           component of G' is the same
       (ii) if X has no predecessors in G', then the immediate dominator of X
            is the nearest common ancestor of the predecessors of X in the
            subtree of F rooted in Y
     Therefore, it suffices to find the topological ordering of G', and
     process the nodes X_i in this order using the rules (i) and (ii).
     Then, we contract all the nodes X_i with Y in G, so that the further
     steps work correctly.  
         Split the tree now.  If the idoms of blocks in BBS are not
         conservatively correct, setting the dominators using the
         heuristics in prune_bbs_to_update_dominators could
         create cycles in the dominance "tree", and cause ICE.  
     Construct the graph G.  
         If the dominance tree is conservatively correct, split it now.  
             Do not include parallel edges to G.  
     Find the dominator tree of G.  
     Finally, traverse the tree and find the immediate dominators.  
void link_block ( basic_block  ,

Referenced by create_check_block_twin().

edge make_single_succ_edge ( basic_block  ,
basic_block  ,
bool mark_dfs_back_edges ( void  )
   Mark the back edges in DFS traversal.
   Return nonzero if a loop (natural or otherwise) is present.
   Inspired by Depth_First_Search_PP described in:

     Advanced Compiler Design and Implementation
     Steven Muchnick
     Morgan Kaufmann, 1997

   and heavily borrowed from pre_and_rev_post_order_compute.  
     Allocate the preorder and postorder number arrays.  
     Allocate stack for back-tracking up CFG.  
     Allocate bitmap to track nodes that have been visited.  
     None of the nodes in the CFG have been visited yet.  
     Push the first edge on to the stack.  
         Look at the edge on the top of the stack.  
         Check if the edge destination has been visited yet.  
             Mark that we have visited the destination.  
                 Since the DEST node has been visited for the first
                 time, check its successors.  

Referenced by draw_cfg_nodes().

bool maybe_hot_bb_p ( struct function ,
   In predict.c 
bool maybe_hot_edge_p ( edge  )
bool mfb_keep_just ( edge  )
basic_block nearest_common_dominator ( enum  cdi_direction,
basic_block  ,
basic_block nearest_common_dominator_for_set ( enum  cdi_direction,

Referenced by same_phi_alternatives_1().

basic_block next_dom_son ( enum  cdi_direction,
bool optimize_bb_for_size_p ( const_basic_block  )

Referenced by create_outofssa_var_map().

bool optimize_edge_for_size_p ( edge  )

Referenced by optimize_bb_for_size_p().

bool optimize_edge_for_speed_p ( edge  )

Referenced by find_traces_1_round().

bool optimize_loop_for_size_p ( struct loop )

Referenced by tree_ssa_unswitch_loops().

bool optimize_loop_for_speed_p ( struct loop )
bool optimize_loop_nest_for_size_p ( struct loop )
bool optimize_loop_nest_for_speed_p ( struct loop )
int post_order_compute ( int *  post_order,
bool  include_entry_exit,
bool  delete_unreachable 
   Compute reverse top sort order.  This is computing a post order
   numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then
   true, unreachable blocks are deleted.  
     Allocate stack for back-tracking up CFG.  
     Allocate bitmap to track nodes that have been visited.  
     None of the nodes in the CFG have been visited yet.  
     Push the first edge on to the stack.  
         Look at the edge on the top of the stack.  
         Check if the edge destination has been visited yet.  
             Mark that we have visited the destination.  
               Since the DEST node has been visited for the first
               time, check its successors.  
     Delete the unreachable blocks if some were found and we are
     supposed to do it.  

References ei_next(), ei_one_before_end_p(), and basic_block_def::index.

int pre_and_rev_post_order_compute ( int *  pre_order,
int *  rev_post_order,
bool  include_entry_exit 
   Like pre_and_rev_post_order_compute_fn but operating on the
   current function and asserting that all nodes were visited.  
       The number of nodes visited should be the number of blocks.  
       The number of nodes visited should be the number of blocks minus
       the entry and exit blocks which are not visited here.  

References bitmap_bit_p(), flow_dfs_compute_reverse_add_bb(), basic_block_def::index, basic_block_def::preds, depth_first_search_dsS::sp, edge_def::src, depth_first_search_dsS::stack, and depth_first_search_dsS::visited_blocks.

int pre_and_rev_post_order_compute_fn ( struct function fn,
int *  pre_order,
int *  rev_post_order,
bool  include_entry_exit 
   Compute the depth first search order of FN and store in the array
   PRE_ORDER if nonzero.  If REV_POST_ORDER is nonzero, return the
   reverse completion number for each node.  Returns the number of nodes
   visited.  A depth first search tries to get as far away from the starting
   point as quickly as possible.

   In case the function has unreachable blocks the number of nodes
   visited does not include them.

   pre_order is a really a preorder numbering of the graph.
   rev_post_order is really a reverse postorder numbering of the graph.  
     Allocate stack for back-tracking up CFG.  
     Allocate bitmap to track nodes that have been visited.  
     None of the nodes in the CFG have been visited yet.  
     Push the first edge on to the stack.  
         Look at the edge on the top of the stack.  
         Check if the edge destination has been visited yet.  
             Mark that we have visited the destination.  
               Since the DEST node has been visited for the first
               time, check its successors.  
               There are no successors for the DEST node so assign
               its reverse completion number.  
               There are no more successors for the SRC node
               so assign its reverse completion number.  
struct edge_list* pre_edge_lcm ( int  n_exprs,
sbitmap transp,
sbitmap avloc,
sbitmap antloc,
sbitmap kill,
sbitmap **  insert,
sbitmap **  del 
   In lcm.c 
   Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
   delete vectors for edge based LCM.  Returns an edgelist which is used to
   map the insert vector to what edge an expression should be inserted on.  
     Compute global availability.  
     Compute global anticipatability.  
     Compute earliestness.  
     Allocate an extra element for the exit block in the laterin vector.  
struct edge_list* pre_edge_rev_lcm ( int  n_exprs,
sbitmap transp,
sbitmap st_avloc,
sbitmap st_antloc,
sbitmap kill,
sbitmap **  insert,
sbitmap **  del 
   Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
   insert and delete vectors for edge based reverse LCM.  Returns an
   edgelist which is used to map the insert vector to what edge
   an expression should be inserted on.  
     Compute global anticipatability.  
     Compute farthestness.  
     Allocate an extra element for the entry block.  
void predict_edge_def ( edge  e,
enum br_predictor  predictor,
enum prediction  taken 
   Predict edge E by given predictor if possible.  

Referenced by apply_return_prediction(), and tree_bb_level_predictions().

bool predictable_edge_p ( edge  )
void print_edge_list ( FILE *  ,
struct edge_list  

Referenced by compute_insert_delete().

bool probably_never_executed_bb_p ( struct function ,

Referenced by sanitize_hot_paths().

bool probably_never_executed_edge_p ( struct function ,

Referenced by sanitize_hot_paths().

bool purge_all_dead_edges ( void  )
   Search all basic blocks for potentially dead edges and purge them.  Return
   true if some edge has been eliminated.  

Referenced by split_live_ranges_for_shrink_wrap().

bool purge_dead_edges ( basic_block  )
basic_block recompute_dominator ( enum  cdi_direction,
void redirect_edge_pred ( edge  ,

Referenced by expand_transaction().

void redirect_edge_succ ( edge  ,
edge redirect_edge_succ_nodup ( edge  ,
void redirect_immediate_dominators ( enum cdi_direction  dir,
basic_block  bb,
basic_block  to 
   Redirect all edges pointing to BB to TO.  
void relink_block_chain ( bool  )
void remove_edge_raw ( edge  )

Referenced by remove_branch().

void remove_fake_edges ( void  )
   This routine will remove all fake edges from the flow graph.  If
   we remove all fake successors, it will automatically remove all
   fake predecessors.  

References flow_dfs_compute_reverse_add_bb(), and flow_dfs_compute_reverse_init().

void remove_fake_exit_edges ( void  )
   This routine will remove all fake edges to the EXIT_BLOCK.  

References dfs_find_deadend(), flow_dfs_compute_reverse_add_bb(), flow_dfs_compute_reverse_execute(), and make_edge().

Referenced by pre_insert_copies().

void remove_predictions_associated_with_edge ( edge  )
void rtl_make_eh_edge ( sbitmap  ,
basic_block  ,
void rtl_predict_edge ( edge  ,
enum  br_predictor,
bool rtl_predicted_by_p ( const_basic_block  ,
enum  br_predictor 
void rtl_profile_for_bb ( basic_block  )
   In cfgexpand.c.  

Referenced by move_insn_for_shrink_wrap().

void rtl_profile_for_edge ( edge  )
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 ( basic_block ,
int  ,
int  ,
void set_bb_copy ( basic_block  ,
void set_bb_original ( basic_block  ,
void set_dom_info_availability ( enum  cdi_direction,
enum  dom_state 
void set_loop_copy ( struct loop ,
struct loop  
static basic_block single_pred ( )
basic_block* single_pred_before_succ_order ( void  )
   Returns the list of basic blocks in the function in an order that guarantees
   that if a block X has just a single predecessor Y, then Y is after X in the
         Walk the predecessors of x as long as they have precisely one
         predecessor and add them to the list, so that they get stored
         after x.  
static edge single_pred_edge ( )
   Returns the single predecessor edge of basic block BB.  Aborts
   if BB does not have exactly one predecessor.  

Referenced by create_if_region_on_edge(), rewrite_trees(), and single_pred_cond_non_loop_exit().

basic_block split_edge_and_insert ( edge  ,
edge try_redirect_by_replacing_jump ( edge  ,
basic_block  ,
edge unchecked_make_edge ( basic_block  ,
basic_block  ,
void unlink_block ( basic_block  )

Referenced by create_check_block_twin().

void update_bb_for_insn ( basic_block  )

Referenced by create_check_block_twin().

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
     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.

void update_br_prob_note ( basic_block  )
void verify_dominators ( enum  cdi_direction)

Referenced by cleanup_tree_cfg_1().

void verify_edge_list ( FILE *  ,
struct edge_list  

Referenced by compute_insert_delete().

Variable Documentation

edge mfb_kj_edge
   In cfgloopmanip.c.  
   A callback for make_forwarder block, to redirect all edges except for
   MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
   whether to redirect it.  
struct gcov_ctr_summary* profile_info
   Counter summary from the last set of coverage counts read by
   Counter summary from the last set of coverage counts read.  

Referenced by bb_in_region_p().