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