gccint: Loop representation

1 
1 16.1 Loop representation
1 ========================
1 
1 This chapter describes the representation of loops in GCC, and functions
1 that can be used to build, modify and analyze this representation.  Most
1 of the interfaces and data structures are declared in 'cfgloop.h'.  Loop
1 structures are analyzed and this information disposed or updated at the
1 discretion of individual passes.  Still most of the generic CFG
1 manipulation routines are aware of loop structures and try to keep them
1 up-to-date.  By this means an increasing part of the compilation
1 pipeline is setup to maintain loop structure across passes to allow
1 attaching meta information to individual loops for consumption by later
1 passes.
1 
1  In general, a natural loop has one entry block (header) and possibly
1 several back edges (latches) leading to the header from the inside of
1 the loop.  Loops with several latches may appear if several loops share
1 a single header, or if there is a branching in the middle of the loop.
1 The representation of loops in GCC however allows only loops with a
1 single latch.  During loop analysis, headers of such loops are split and
1 forwarder blocks are created in order to disambiguate their structures.
1 Heuristic based on profile information and structure of the induction
1 variables in the loops is used to determine whether the latches
1 correspond to sub-loops or to control flow in a single loop.  This means
1 that the analysis sometimes changes the CFG, and if you run it in the
1 middle of an optimization pass, you must be able to deal with the new
1 blocks.  You may avoid CFG changes by passing
1 'LOOPS_MAY_HAVE_MULTIPLE_LATCHES' flag to the loop discovery, note
1 however that most other loop manipulation functions will not work
1 correctly for loops with multiple latch edges (the functions that only
1 query membership of blocks to loops and subloop relationships, or
1 enumerate and test loop exits, can be expected to work).
1 
1  Body of the loop is the set of blocks that are dominated by its header,
1 and reachable from its latch against the direction of edges in CFG.  The
1 loops are organized in a containment hierarchy (tree) such that all the
1 loops immediately contained inside loop L are the children of L in the
1 tree.  This tree is represented by the 'struct loops' structure.  The
1 root of this tree is a fake loop that contains all blocks in the
1 function.  Each of the loops is represented in a 'struct loop'
1 structure.  Each loop is assigned an index ('num' field of the 'struct
1 loop' structure), and the pointer to the loop is stored in the
1 corresponding field of the 'larray' vector in the loops structure.  The
1 indices do not have to be continuous, there may be empty ('NULL')
1 entries in the 'larray' created by deleting loops.  Also, there is no
1 guarantee on the relative order of a loop and its subloops in the
1 numbering.  The index of a loop never changes.
1 
1  The entries of the 'larray' field should not be accessed directly.  The
1 function 'get_loop' returns the loop description for a loop with the
1 given index.  'number_of_loops' function returns number of loops in the
1 function.  To traverse all loops, use 'FOR_EACH_LOOP' macro.  The
1 'flags' argument of the macro is used to determine the direction of
1 traversal and the set of loops visited.  Each loop is guaranteed to be
1 visited exactly once, regardless of the changes to the loop tree, and
1 the loops may be removed during the traversal.  The newly created loops
1 are never traversed, if they need to be visited, this must be done
1 separately after their creation.  The 'FOR_EACH_LOOP' macro allocates
1 temporary variables.  If the 'FOR_EACH_LOOP' loop were ended using break
1 or goto, they would not be released; 'FOR_EACH_LOOP_BREAK' macro must be
1 used instead.
1 
1  Each basic block contains the reference to the innermost loop it
1 belongs to ('loop_father').  For this reason, it is only possible to
1 have one 'struct loops' structure initialized at the same time for each
1 CFG.  The global variable 'current_loops' contains the 'struct loops'
1 structure.  Many of the loop manipulation functions assume that
1 dominance information is up-to-date.
1 
1  The loops are analyzed through 'loop_optimizer_init' function.  The
1 argument of this function is a set of flags represented in an integer
1 bitmask.  These flags specify what other properties of the loop
1 structures should be calculated/enforced and preserved later:
1 
1    * 'LOOPS_MAY_HAVE_MULTIPLE_LATCHES': If this flag is set, no changes
1      to CFG will be performed in the loop analysis, in particular, loops
1      with multiple latch edges will not be disambiguated.  If a loop has
1      multiple latches, its latch block is set to NULL.  Most of the loop
1      manipulation functions will not work for loops in this shape.  No
1      other flags that require CFG changes can be passed to
1      loop_optimizer_init.
1    * 'LOOPS_HAVE_PREHEADERS': Forwarder blocks are created in such a way
1      that each loop has only one entry edge, and additionally, the
1      source block of this entry edge has only one successor.  This
1      creates a natural place where the code can be moved out of the
1      loop, and ensures that the entry edge of the loop leads from its
1      immediate super-loop.
1    * 'LOOPS_HAVE_SIMPLE_LATCHES': Forwarder blocks are created to force
1      the latch block of each loop to have only one successor.  This
1      ensures that the latch of the loop does not belong to any of its
1      sub-loops, and makes manipulation with the loops significantly
1      easier.  Most of the loop manipulation functions assume that the
1      loops are in this shape.  Note that with this flag, the "normal"
1      loop without any control flow inside and with one exit consists of
1      two basic blocks.
1    * 'LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS': Basic blocks and edges in
1      the strongly connected components that are not natural loops (have
1      more than one entry block) are marked with 'BB_IRREDUCIBLE_LOOP'
1      and 'EDGE_IRREDUCIBLE_LOOP' flags.  The flag is not set for blocks
1      and edges that belong to natural loops that are in such an
1      irreducible region (but it is set for the entry and exit edges of
1      such a loop, if they lead to/from this region).
1    * 'LOOPS_HAVE_RECORDED_EXITS': The lists of exits are recorded and
1      updated for each loop.  This makes some functions (e.g.,
1      'get_loop_exit_edges') more efficient.  Some functions (e.g.,
1      'single_exit') can be used only if the lists of exits are recorded.
1 
1  These properties may also be computed/enforced later, using functions
1 'create_preheaders', 'force_single_succ_latches',
1 'mark_irreducible_loops' and 'record_loop_exits'.  The properties can be
1 queried using 'loops_state_satisfies_p'.
1 
1  The memory occupied by the loops structures should be freed with
1 'loop_optimizer_finalize' function.  When loop structures are setup to
1 be preserved across passes this function reduces the information to be
1 kept up-to-date to a minimum (only 'LOOPS_MAY_HAVE_MULTIPLE_LATCHES'
1 set).
1 
1  The CFG manipulation functions in general do not update loop
1 structures.  Specialized versions that additionally do so are provided
1 for the most common tasks.  On GIMPLE, 'cleanup_tree_cfg_loop' function
1 can be used to cleanup CFG while updating the loops structures if
1 'current_loops' is set.
1 
1  At the moment loop structure is preserved from the start of GIMPLE loop
1 optimizations until the end of RTL loop optimizations.  During this time
1 a loop can be tracked by its 'struct loop' and number.
1