GCC Middle and Back End API Reference
cfgloop.c File Reference


static void flow_loops_cfg_dump (FILE *)
static void flow_loops_cfg_dump ()
bool flow_loop_nested_p ()
struct loopsuperloop_at_depth ()
static vec< edgeget_loop_latch_edges ()
void flow_loop_dump (const struct loop *loop, FILE *file, void(*loop_dump_aux)(const struct loop *, FILE *, int), int verbose)
void flow_loops_dump (FILE *file, void(*loop_dump_aux)(const struct loop *, FILE *, int), int verbose)
void flow_loop_free ()
void flow_loops_free ()
int flow_loop_nodes_find ()
static void establish_preds ()
void flow_loop_tree_node_add ()
void flow_loop_tree_node_remove ()
struct loopalloc_loop ()
void init_loops_structure (struct function *fn, struct loops *loops, unsigned num_loops)
bool bb_loop_header_p ()
struct loopsflow_loops_find ()
static edge find_subloop_latch_edge_by_profile ()
static edge find_subloop_latch_edge_by_ivs ()
static edge find_subloop_latch_edge ()
static bool mfb_redirect_edges_in_set ()
static void form_subloop ()
static void merge_latch_edges ()
static void disambiguate_multiple_latches ()
void disambiguate_loops_with_multiple_latches ()
bool flow_bb_inside_loop_p ()
static bool glb_enum_p ()
unsigned get_loop_body_with_size (const struct loop *loop, basic_block *body, unsigned max_size)
basic_blockget_loop_body ()
static void fill_sons_in_loop (const struct loop *loop, basic_block bb, basic_block *tovisit, int *tv)
basic_blockget_loop_body_in_dom_order ()
basic_blockget_loop_body_in_custom_order (const struct loop *loop, int(*bb_comparator)(const void *, const void *))
basic_blockget_loop_body_in_bfs_order ()
static hashval_t loop_exit_hash ()
static int loop_exit_eq ()
static void loop_exit_free ()
static struct loop_exitget_exit_descriptions ()
void rescan_loop_exit ()
void record_loop_exits ()
static int dump_recorded_exit ()
void dump_recorded_exits (FILE *)
void dump_recorded_exits ()
void release_recorded_exits ()
vec< edgeget_loop_exit_edges ()
unsigned num_loop_branches ()
void add_bb_to_loop ()
void remove_bb_from_loops ()
struct loopfind_common_loop ()
void delete_loop ()
static void cancel_loop ()
void cancel_loop_tree ()
DEBUG_FUNCTION void verify_loop_structure ()
edge loop_latch_edge ()
edge loop_preheader_edge ()
bool loop_exit_edge_p ()
edge single_exit ()
bool loop_exits_to_bb_p ()
bool loop_exits_from_bb_p ()
location_t get_loop_location ()
void record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, bool upper)
HOST_WIDE_INT get_estimated_loop_iterations_int ()
HOST_WIDE_INT max_stmt_executions_int ()
bool get_estimated_loop_iterations ()
bool get_max_loop_iterations ()
HOST_WIDE_INT get_max_loop_iterations_int ()
int bb_loop_depth ()


static struct pointer_set_tmfb_reis_set

Function Documentation

void add_bb_to_loop ( )
struct loop* alloc_loop ( void  )
int bb_loop_depth ( )
   Returns the loop depth of the loop BB belongs to.  

Referenced by memref_referenced_p(), and select_best_block().

bool bb_loop_header_p ( )
   Returns whether HEADER is a loop header.  
     If we have an abnormal predecessor, do not consider the
     loop (not worth the problems).  
     Look for back edges where a predecessor is dominated
     by this block.  A natural loop has a single entry
     node (header) that dominates all the nodes in the
     loop.  It also has single back edge to the header
     from a latch node.  
static void cancel_loop ( )
   Cancels the LOOP; it must be innermost one.  
     Move blocks up one level (they should be removed as soon as possible).  

References error(), get_loop_body_with_size(), loop::header, loop::num, and loop::num_nodes.

void cancel_loop_tree ( )
   Cancels LOOP and all its subloops.  

References error(), and loop::num.

void delete_loop ( )
   Removes LOOP from structures and frees its data.  
     Remove the loop from structure.  
     Remove loop from loops array.  
     Free loop data.  
void disambiguate_loops_with_multiple_latches ( void  )
   Split loops with multiple latch edges.  
static void disambiguate_multiple_latches ( )
   LOOP may have several latch edges.  Transform it into (possibly several)
   loops with single latch edge.  
     We eliminate the multiple latches by splitting the header to the forwarder
     block F and the rest R, and redirecting the edges.  There are two cases:

     1) If there is a latch edge E that corresponds to a subloop (we guess
        that based on profile -- if it is taken much more often than the
        remaining edges; and on trees, using the information about induction
        variables of the loops), we redirect E to R, all the remaining edges to
        F, then rescan the loops and try again for the outer loop.
     2) If there is no such edge, we redirect all latch edges to F, and the
        entry edges to R, thus making F the single latch of the loop.  
     During latch merging, we may need to redirect the entry edges to a new
     block.  This would cause problems if the entry edge was the one from the
     entry block.  To avoid having to handle this case specially, split
     such entry edge.  

References flow_loop_nested_p(), and basic_block_def::loop_father.

static int dump_recorded_exit ( )
   Dumps information about the exit in *SLOT to FILE.
   Callback for htab_traverse.  

References free(), get_loop_body(), loop::latch, and loop::num_nodes.

void dump_recorded_exits ( FILE *  )
   Dumps the recorded exits of loops to FILE.  
void dump_recorded_exits ( )
static void establish_preds ( )
   Records the vector of superloops of the loop LOOP, whose immediate
   superloop is FATHER.  
static void fill_sons_in_loop ( const struct loop loop,
basic_block  bb,
basic_block tovisit,
int *  tv 
   Fills dominance descendants inside LOOP of the basic block BB into
   array TOVISIT from index *TV.  

References bitmap_set_bit(), edge_def::dest, flow_bb_inside_loop_p(), loop::header, basic_block_def::index, loop::latch, loop::num_nodes, basic_block_def::succs, and visited.

Referenced by get_loop_body().

struct loop* find_common_loop ( )
   Finds nearest common ancestor in loop tree for given loops.  

Referenced by compute_always_reached(), fix_loop_placement(), gbb_loop(), redirect_edge_succ_nodup(), and tidy_fallthru_edges().

static edge find_subloop_latch_edge ( )
   If we can determine that one of the several latch edges of LOOP behaves
   as a latch edge of a separate subloop, returns this edge.  Otherwise
   returns NULL.  
             We consider ivs to guess the latch edge only in SSA.  Perhaps we
             should use cfghook for this, but it is hard to imagine it would
             be useful elsewhere.  
static edge find_subloop_latch_edge_by_ivs ( )
   Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
   on the structure of induction variables.  Returns this edge, or NULL if we
   do not find any.

   We are quite conservative, and look just for an obvious simple innermost
   loop (which is the case where we would lose the most performance by not
   disambiguating the loop).  More precisely, we look for the following
   situation: The source of the chosen latch edge dominates sources of all
   the other latch edges.  Additionally, the header does not contain a phi node
   such that the argument from the chosen edge is equal to the argument from
   another edge.  
     Find the candidate for the latch edge.  
     Verify that it dominates all the latch edges.  
     Check for a phi node that would deny that this is a latch edge of
     a subloop.  
         Ignore the values that are not changed inside the subloop.  
static edge find_subloop_latch_edge_by_profile ( )
   If the profile info is available, finds an edge in LATCHES that much more
   frequent than the remaining edges.  Returns such an edge, or NULL if we do
   not find one.

   We do not use guessed profile here, only the measured one.  The guessed
   profile is usually too flat and unreliable for this (and it is mostly based
   on the loop structure of the program, so it does not make much sense to
   derive the loop structure from it).  

References CDI_DOMINATORS, dominated_by_p(), dump_file, flow_bb_inside_loop_p(), gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, and edge_def::src.

void flow_loop_dump ( const struct loop loop,
FILE *  file,
void(*)(const struct loop *, FILE *, int)  loop_dump_aux,
int  verbose 
   Dump the loop information specified by LOOP to the stream FILE
   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  

Referenced by rewrite_uses().

void flow_loop_free ( )
   Free data allocated for LOOP.  
     Break the list of the loop exit records.  They will be freed when the
     corresponding edge is rescanned or removed, and this avoids
     accessing the (already released) head of the list stored in the
     loop structure.  

References loop_exit::next, and loop_exit::prev.

int flow_loop_nodes_find ( )
   Find the nodes contained within the LOOP with header HEADER.
   Return the number of nodes within the loop.  

References loop_exit::e, basic_block_def::loop_father, basic_block_def::preds, and edge_def::src.

void flow_loop_tree_node_add ( )
   Add LOOP to the loop hierarchy tree where FATHER is father of the
   added loop.  If LOOP has some children, take care of that their
   pred field will be initialized correctly.  
void flow_loop_tree_node_remove ( )
   Remove LOOP from the loop hierarchy tree.  
     Remove loop from the list of sons.  
static void flow_loops_cfg_dump ( FILE *  )

Natural loop discovery code for GNU compiler. Copyright (C) 2000-2013 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/.

static void flow_loops_cfg_dump ( )
   Dump loop related CFG information.  

References edge_def::dest, basic_block_def::index, and basic_block_def::succs.

void flow_loops_dump ( FILE *  file,
void(*)(const struct loop *, FILE *, int)  loop_dump_aux,
int  verbose 
   Dump the loop information about loops to the stream FILE,
   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  

Referenced by analyze_function().

struct loops* flow_loops_find ( )
   Find all the natural loops in the function and save in LOOPS structure and
   recalculate loop_father information in basic block structures.
   If LOOPS is non-NULL then the loop structures for already recorded loops
   will be re-used and their number will not change.  We assume that no
   stale loops exist in LOOPS.
   When LOOPS is NULL it is allocated and re-built from scratch.
   Return the built LOOPS structure.  
     Ensure that the dominators are computed.  
     Ensure that loop exits were released.  
     Taking care of this degenerate case makes the rest of
     this code simpler.  
     The root loop node contains all basic-blocks.  
     Compute depth first search order of the CFG so that outer
     natural loops will be found before inner natural loops.  
     Gather all loop headers in reverse completion order and allocate
     loop structures for loops that are not already present.  
             The current active loop tree has valid loop-fathers for
             header blocks.  
                 If we found an existing loop remove it from the
                 loop tree.  It is going to be inserted again
                 Otherwise allocate a new loop structure for the loop.  
                 ???  We could re-use unused loop slots here.  
             Reset latch, we recompute it below.  
         Make blocks part of the loop root node at start.  
     Now iterate over the loops found, insert them into the loop tree
     and assign basic-block ownership.  
         Look for the latch for this header block, if it has just a
         single one.  
                     More than one latch edge.  
void flow_loops_free ( )
   Free all the memory allocated for LOOPS.  
         Free the loop descriptors.  
static void form_subloop ( )
   Creates a subloop of LOOP with latch edge LATCH.  
     Find the blocks and subloops that belong to the new loop, and add it to
     the appropriate place in the loop tree.  

References dump_file.

bool get_estimated_loop_iterations ( )
   Sets NIT to the estimated number of executions of the latch of the
   LOOP.  If we have no reliable estimate, the function returns false, otherwise
   returns true.  
     Even if the bound is not recorded, possibly we can derrive one from
HOST_WIDE_INT get_estimated_loop_iterations_int ( )
   Similar to get_estimated_loop_iterations, but returns the estimate only
   if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
   on the number of iterations of LOOP could not be derived, returns -1.  
static struct loop_exit* get_exit_descriptions ( )
   Returns the list of records for E as an exit of a loop.  
basic_block* get_loop_body ( )
   Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
   order against direction of edges from latch.  Specially, if
   header != latch, latch is the 1-st block.  
         There may be blocks unreachable from EXIT_BLOCK, hence we need to
         special-case the fake loop that contains the whole function.  

References fill_sons_in_loop(), loop::header, loop::latch, and loop::num_nodes.

Referenced by copy_loop_info(), dump_recorded_exit(), generate_prolog_epilog(), num_loop_insns(), record_loop_exits(), rewrite_use_compare(), and split_edge_and_insert().

basic_block* get_loop_body_in_bfs_order ( )
   Get body of a LOOP in breadth first sort order.  
           This basic block is now visited 

References ggc_free(), loop_exit::next, loop_exit::next_e, and loop_exit::prev.

basic_block* get_loop_body_in_custom_order ( const struct loop loop,
int(*)(const void *, const void *)  bb_comparator 
   Gets body of a LOOP sorted via provided BB_COMPARATOR.  

References loop_exit::e.

basic_block* get_loop_body_in_dom_order ( )
   Gets body of a LOOP (that must be different from the outermost loop)
   sorted by dominance relation.  Additionally, if a basic block s dominates
   the latch, then only blocks dominated by s are be after it.  

Referenced by clear_iv_info(), create_loop_fn(), new_bb_pbb_def(), and ref_indep_loop_p().

unsigned get_loop_body_with_size ( const struct loop loop,
basic_block body,
unsigned  max_size 
   Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
   order against direction of edges from latch.  Specially, if
   header != latch, latch is the 1-st block.  LOOP cannot be the fake
   loop tree root, and its size must be at most MAX_SIZE.  The blocks
   in the LOOP body are stored to BODY, and the size of the LOOP is

Referenced by cancel_loop().

vec<edge> get_loop_exit_edges ( )
   Returns the list of the exit edges of a LOOP.  
     If we maintain the lists of exits, use them.  Otherwise we must
     scan the body of the loop.  

Referenced by add_exit_phis(), delete_allocno_from_bucket(), estimated_unrolled_size(), nontemporal_store_p(), and ref_indep_loop_p_2().

static vec<edge> get_loop_latch_edges ( )
   Returns the list of the latch edges of LOOP.  

References CDI_DOMINATORS, dominated_by_p(), loop::header, and edge_def::src.

location_t get_loop_location ( )
   Return location corresponding to the loop control condition if possible.  
     For a for or while loop, we would like to return the location
     of the for or while statement, if possible.  To do this, look
     for the branch guarding the loop back-edge.  
     If this is a simple loop with an in_edge, then the loop control
     branch is typically at the end of its source.  
     If loop has a single exit, then the loop control branch
     must be at the end of its source.  
     Next check the latch, to see if it is non-empty.  
     Finally, if none of the above identifies the loop control branch,
     return the first location in the loop header.  
     If all else fails, simply return the current function location.  

References get_max_loop_iterations_int(), and HOST_WIDE_INT.

Referenced by loop_exit_at_end_p().

bool get_max_loop_iterations ( )
   Sets NIT to an upper bound for the maximum number of executions of the
   latch of the LOOP.  If we have no reliable estimate, the function returns
   false, otherwise returns true.  
HOST_WIDE_INT get_max_loop_iterations_int ( )
   Similar to get_max_loop_iterations, but returns the estimate only
   if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
   on the number of iterations of LOOP could not be derived, returns -1.  

Referenced by get_loop_location().

static bool glb_enum_p ( )
   Enumeration predicate for get_loop_body_with_size.  

References CDI_DOMINATORS, dominated_by_p(), first_dom_son(), flow_bb_inside_loop_p(), and next_dom_son().

void init_loops_structure ( struct function fn,
struct loops loops,
unsigned  num_loops 
   Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
   (including the root of the loop tree).  
     Dummy loop containing whole function.  
bool loop_exit_edge_p ( )
   Returns true if E is an exit of LOOP.  

Referenced by redirection_block_p(), and remove_conditions_and_labels().

static int loop_exit_eq ( )
   Equality function for struct loop_exit.  Compares with edge.  
static void loop_exit_free ( )
   Frees the list of loop exit descriptions EX.  

References loop::exits.

static hashval_t loop_exit_hash ( )
   Hash function for struct loop_exit.  

References loop::exits, loop_exit::next, and loop_exit::prev.

bool loop_exits_from_bb_p ( )
   Returns true when BB has an outgoing edge exiting LOOP.  
bool loop_exits_to_bb_p ( )
   Returns true when BB has an incoming edge exiting LOOP.  
edge loop_latch_edge ( )
HOST_WIDE_INT max_stmt_executions_int ( )
   Returns an upper bound on the number of executions of statements
   in the LOOP.  For statements before the loop exit, this exceeds
   the number of execution of the latch by one.  
     If the computation overflows, return -1.  

Referenced by initialize_matrix_A(), and lambda_vector_equal().

static void merge_latch_edges ( )
   Make all the latch edges of LOOP to go to a single forwarder block --
   a new latch of LOOP.  
static bool mfb_redirect_edges_in_set ( )
unsigned num_loop_branches ( )
   Counts the number of conditional branches inside LOOP.  
void record_loop_exits ( void  )
void record_niter_bound ( struct loop loop,
double_int  i_bound,
bool  realistic,
bool  upper 
   Records that every statement in LOOP is executed I_BOUND times.
   REALISTIC is true if I_BOUND is expected to be close to the real number
   of iterations.  UPPER is true if we are sure the loop iterates at most
   I_BOUND times.  
     Update the bounds only when there is no previous estimation, or when the
     current estimation is smaller.  
     If an upper bound is smaller than the realistic estimate of the
     number of iterations, use the upper bound instead.  

Referenced by vect_update_ivs_after_vectorizer().

void release_recorded_exits ( void  )
   Releases lists of loop exits.  

References rescan_loop_exit().

void remove_bb_from_loops ( )
   Remove basic block BB from loops.  

Referenced by predicted_by_p().

void rescan_loop_exit ( )
   Updates the lists of loop exits in that E appears.
   If REMOVED is true, E is being removed, and we
   just remove it from the lists of exits.
   If NEW_EDGE is true and E is not a loop exit, we
   do not try to remove it from loop exit lists.  

Referenced by copy_phi_args(), redirect_edge_succ_nodup(), release_recorded_exits(), remove_branch(), and tidy_fallthru_edges().

edge single_exit ( )
   Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
   or more than one exit.  If loops do not have the exits recorded, NULL
   is returned always.  

References loop::any_upper_bound, and loop::nb_iterations_upper_bound.

Referenced by create_empty_if_region_on_edge(), get_bb_type(), graphite_create_new_loop_guard(), print_graphite_scop_statistics(), vect_can_advance_ivs_p(), vect_create_cond_for_alias_checks(), vect_create_epilog_for_reduction(), and vect_update_ivs_after_vectorizer().

struct loop* superloop_at_depth ( )
   Returns the loop such that LOOP is nested DEPTH (indexed from zero)
   loops within LOOP.  

Referenced by set_ifsese_condition().

DEBUG_FUNCTION void verify_loop_structure ( void  )
   Checks that information about loops is correct
     -- sizes of loops are all right
     -- results of get_loop_body really belong to the loop
     -- loop header have just single entry edge and single latch edge
     -- loop latches have only single successor that is header of their loop
     -- irreducible loops are correctly marked
     -- the cached loop depth and loop father of each bb is correct
     We need up-to-date dominators, compute or verify them.  
     Check the headers.  
     Check the recorded loop father and sizes of loops.  
             Ignore this block if it is in an inner loop.  
     Check headers and latches.  
     Check irreducible loops.  
         Record old info.  
         Recount it.  
     Check the recorded loop exits.  
             Check that the list forms a cycle, and all elements except
             for the head are nonnull.  
                      When a loop exit is also an entry edge which
                      can happen when avoiding CFG manipulations
                      then the last loop exited is the outer loop
                      of the loop entered.  

Variable Documentation

struct pointer_set_t* mfb_reis_set
   Callback for make_forwarder_block.  Returns true if the edge E is marked
   in the set MFB_REIS_SET.