@c Copyright (c) 2006, 2007, 2008 Free Software Foundation, Inc.@c Free Software Foundation, Inc.@c This is part of the GCC manual.@c For copying conditions, see the file gcc.texi.@c ---------------------------------------------------------------------@c Loop Representation@c ---------------------------------------------------------------------@node Loop Analysis and Representation@chapter Analysis and Representation of LoopsGCC provides extensive infrastructure for work with natural loops, i.e.,strongly connected components of CFG with only one entry block.  Thischapter describes representation of loops in GCC, both on GIMPLE and inRTL, as well as the interfaces to loop-related analyses (inductionvariable analysis and number of iterations analysis).@menu* Loop representation::		Representation and analysis of loops.* Loop querying::		Getting information about loops.* Loop manipulation::		Loop manipulation functions.* LCSSA::			Loop-closed SSA form.* Scalar evolutions::   	Induction variables on GIMPLE.* loop-iv::			Induction variables on RTL.* Number of iterations::	Number of iterations analysis.* Dependency analysis::		Data dependency analysis.* Lambda::			Linear loop transformations framework.* Omega::			A solver for linear programming problems.@end menu@node Loop representation@section Loop representation@cindex Loop representation@cindex Loop analysisThis chapter describes the representation of loops in GCC, and functionsthat can be used to build, modify and analyze this representation.  Mostof the interfaces and data structures are declared in @file{cfgloop.h}.At the moment, loop structures are analyzed and this information isupdated only by the optimization passes that deal with loops, but someefforts are being made to make it available throughout most of theoptimization passes.In general, a natural loop has one entry block (header) and possiblyseveral back edges (latches) leading to the header from the inside ofthe loop.  Loops with several latches may appear if several loops sharea single header, or if there is a branching in the middle of the loop.The representation of loops in GCC however allows only loops with asingle latch.  During loop analysis, headers of such loops are split andforwarder blocks are created in order to disambiguate their structures.Heuristic based on profile information and structure of the inductionvariables in the loops is used to determine whether the latchescorrespond to sub-loops or to control flow in a single loop.  This meansthat the analysis sometimes changes the CFG, and if you run it in themiddle of an optimization pass, you must be able to deal with the newblocks.  You may avoid CFG changes by passing@code{LOOPS_MAY_HAVE_MULTIPLE_LATCHES} flag to the loop discovery,note however that most other loop manipulation functions will not workcorrectly for loops with multiple latch edges (the functions that onlyquery membership of blocks to loops and subloop relationships, orenumerate and test loop exits, can be expected to work).Body of the loop is the set of blocks that are dominated by its header,and reachable from its latch against the direction of edges in CFG@.  Theloops are organized in a containment hierarchy (tree) such that all theloops immediately contained inside loop L are the children of L in thetree.  This tree is represented by the @code{struct loops} structure.The root of this tree is a fake loop that contains all blocks in thefunction.  Each of the loops is represented in a @code{struct loop}structure.  Each loop is assigned an index (@code{num} field of the@code{struct loop} structure), and the pointer to the loop is stored inthe corresponding field of the @code{larray} vector in the loopsstructure.  The indices do not have to be continuous, there may beempty (@code{NULL}) entries in the @code{larray} created by deletingloops.  Also, there is no guarantee on the relative order of a loopand its subloops in the numbering.  The index of a loop never changes.The entries of the @code{larray} field should not be accessed directly.The function @code{get_loop} returns the loop description for a loop withthe given index.  @code{number_of_loops} function returns number ofloops in the function.  To traverse all loops, use @code{FOR_EACH_LOOP}macro.  The @code{flags} argument of the macro is used to determinethe direction of traversal and the set of loops visited.  Each loop isguaranteed to be visited exactly once, regardless of the changes to theloop tree, and the loops may be removed during the traversal.  The newlycreated loops are never traversed, if they need to be visited, thismust be done separately after their creation.  The @code{FOR_EACH_LOOP}macro allocates temporary variables.  If the @code{FOR_EACH_LOOP} loopwere ended using break or goto, they would not be released;@code{FOR_EACH_LOOP_BREAK} macro must be used instead.Each basic block contains the reference to the innermost loop it belongsto (@code{loop_father}).  For this reason, it is only possible to haveone @code{struct loops} structure initialized at the same time for eachCFG@.  The global variable @code{current_loops} contains the@code{struct loops} structure.  Many of the loop manipulation functionsassume that dominance information is up-to-date.The loops are analyzed through @code{loop_optimizer_init} function.  Theargument of this function is a set of flags represented in an integerbitmask.  These flags specify what other properties of the loopstructures should be calculated/enforced and preserved later:@itemize@item @code{LOOPS_MAY_HAVE_MULTIPLE_LATCHES}: If this flag is set, nochanges to CFG will be performed in the loop analysis, in particular,loops with multiple latch edges will not be disambiguated.  If a loophas multiple latches, its latch block is set to NULL@.  Most ofthe loop manipulation functions will not work for loops in this shape.No other flags that require CFG changes can be passed toloop_optimizer_init.@item @code{LOOPS_HAVE_PREHEADERS}: Forwarder blocks are created in sucha way that each loop has only one entry edge, and additionally, thesource block of this entry edge has only one successor.  This creates anatural place where the code can be moved out of the loop, and ensuresthat the entry edge of the loop leads from its immediate super-loop.@item @code{LOOPS_HAVE_SIMPLE_LATCHES}: Forwarder blocks are created toforce the latch block of each loop to have only one successor.  Thisensures that the latch of the loop does not belong to any of itssub-loops, and makes manipulation with the loops significantly easier.Most of the loop manipulation functions assume that the loops are inthis shape.  Note that with this flag, the ``normal'' loop without anycontrol flow inside and with one exit consists of two basic blocks.@item @code{LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS}: Basic blocks andedges in the strongly connected components that are not natural loops(have more than one entry block) are marked with@code{BB_IRREDUCIBLE_LOOP} and @code{EDGE_IRREDUCIBLE_LOOP} flags.  Theflag is not set for blocks and edges that belong to natural loops thatare in such an irreducible region (but it is set for the entry and exitedges of such a loop, if they lead to/from this region).@item @code{LOOPS_HAVE_RECORDED_EXITS}: The lists of exits are recordedand updated for each loop.  This makes some functions (e.g.,@code{get_loop_exit_edges}) more efficient.  Some functions (e.g.,@code{single_exit}) can be used only if the lists of exits arerecorded.@end itemizeThese properties may also be computed/enforced later, using functions@code{create_preheaders}, @code{force_single_succ_latches},@code{mark_irreducible_loops} and @code{record_loop_exits}.The memory occupied by the loops structures should be freed with@code{loop_optimizer_finalize} function.The CFG manipulation functions in general do not update loop structures.Specialized versions that additionally do so are provided for the mostcommon tasks.  On GIMPLE, @code{cleanup_tree_cfg_loop} function can beused to cleanup CFG while updating the loops structures if@code{current_loops} is set.@node Loop querying@section Loop querying@cindex Loop queryingThe functions to query the information about loops are declared in@file{cfgloop.h}.  Some of the information can be taken directly fromthe structures.  @code{loop_father} field of each basic block containsthe innermost loop to that the block belongs.  The most useful fields ofloop structure (that are kept up-to-date at all times) are:@itemize@item @code{header}, @code{latch}: Header and latch basic blocks of theloop.@item @code{num_nodes}: Number of basic blocks in the loop (includingthe basic blocks of the sub-loops).@item @code{depth}: The depth of the loop in the loops tree, i.e., thenumber of super-loops of the loop.@item @code{outer}, @code{inner}, @code{next}: The super-loop, the firstsub-loop, and the sibling of the loop in the loops tree.@end itemizeThere are other fields in the loop structures, many of them used only bysome of the passes, or not updated during CFG changes; in general, theyshould not be accessed directly.The most important functions to query loop structures are:@itemize@item @code{flow_loops_dump}: Dumps the information about loops to afile.@item @code{verify_loop_structure}: Checks consistency of the loopstructures.@item @code{loop_latch_edge}: Returns the latch edge of a loop.@item @code{loop_preheader_edge}: If loops have preheaders, returnsthe preheader edge of a loop.@item @code{flow_loop_nested_p}: Tests whether loop is a sub-loop ofanother loop.@item @code{flow_bb_inside_loop_p}: Tests whether a basic block belongsto a loop (including its sub-loops).@item @code{find_common_loop}: Finds the common super-loop of two loops.@item @code{superloop_at_depth}: Returns the super-loop of a loop withthe given depth.@item @code{tree_num_loop_insns}, @code{num_loop_insns}: Estimates thenumber of insns in the loop, on GIMPLE and on RTL.@item @code{loop_exit_edge_p}: Tests whether edge is an exit from aloop.@item @code{mark_loop_exit_edges}: Marks all exit edges of all loopswith @code{EDGE_LOOP_EXIT} flag.@item @code{get_loop_body}, @code{get_loop_body_in_dom_order},@code{get_loop_body_in_bfs_order}: Enumerates the basic blocks in theloop in depth-first search order in reversed CFG, ordered by dominancerelation, and breath-first search order, respectively.@item @code{single_exit}: Returns the single exit edge of the loop, or@code{NULL} if the loop has more than one exit.  You can only use thisfunction if LOOPS_HAVE_MARKED_SINGLE_EXITS property is used.@item @code{get_loop_exit_edges}: Enumerates the exit edges of a loop.@item @code{just_once_each_iteration_p}: Returns true if the basic blockis executed exactly once during each iteration of a loop (that is, itdoes not belong to a sub-loop, and it dominates the latch of the loop).@end itemize@node Loop manipulation@section Loop manipulation@cindex Loop manipulationThe loops tree can be manipulated using the following functions:@itemize