Analysis and Representation of Loops
************************************

GCC provides extensive infrastructure for work with natural loops, i.e., strongly connected components of CFG with only one entry block.  This chapter describes representation of loops in GCC, both on GIMPLE and in RTL, as well as the interfaces to loop-related analyses (induction variable analysis and number of iterations analysis).

Loop representation
===================

This chapter describes the representation of loops in GCC, and functions that can be used to build, modify and analyze this representation.  Most of the interfaces and data structures are declared in cfgloop.h. At the moment, loop structures are analyzed and this information is updated only by the optimization passes that deal with loops, but some efforts are being made to make it available throughout most of the optimization passes.

In general, a natural loop has one entry block (header) and possibly several back edges (latches) leading to the header from the inside of the loop.  Loops with several latches may appear if several loops share a 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 a single latch.  During loop analysis, headers of such loops are split and forwarder blocks are created in order to disambiguate their structures. A heuristic based on profile information is used to determine whether the latches correspond to sub-loops or to control flow in a single loop. This means that the analysis sometimes changes the CFG, and if you run it in the middle of an optimization pass, you must be able to deal with the new blocks.

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.  The loops are organized in a containment hierarchy (tree) such that all the loops immediately contained inside loop L are the children of L in the tree.  This tree is represented by the struct loops structure. The root of this tree is a fake loop that contains all blocks in the function.  Each of the loops is represented in a struct loop structure.  Each loop is assigned an index (num field of the struct loop structure), and the pointer to the loop is stored in the corresponding field of the parray field of the loops structure.  Index of a sub-loop is always greater than the index of its super-loop.  The indices do not have to be continuous, there may be empty (NULL) entries in the parray created by deleting loops.  The index of a loop never changes.  The first unused index is stored in the num field of the loops structure.

Each basic block contains the reference to the innermost loop it belongs to (loop_father).  For this reason, it is only possible to have one struct loops structure initialized at the same time for each CFG.  It is recommended to use the global variable current_loops to contain the struct loops structure, especially if the loop structures are updated throughout several passes.  Many of the loop manipulation functions assume that dominance information is up-to-date.

The loops are analyzed through loop_optimizer_init function.  The argument of this function is a set of flags represented in an integer bitmask.  These flags specify what other properties of the loop structures should be calculated/enforced and preserved later:

  * LOOPS_HAVE_PREHEADERS: Forwarder blocks are created in such a way that each loop has only one entry edge, and additionally, the source block of this entry edge has only one successor.  This creates a natural place where the code can be moved out of the loop, and ensures that the entry edge of the loop leads from its immediate super-loop.

  * LOOPS_HAVE_SIMPLE_LATCHES: Forwarder blocks are created to force the latch block of each loop to have only one successor.  This ensures that the latch of the loop does not belong to any of its sub-loops, and makes manipulation with the loops significantly easier. Most of the loop manipulation functions assume that the loops are in this shape.  Note that with this flag, the ``normal'' loop without any control flow inside and with one exit consists of two basic blocks.

  * LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS: Basic blocks and edges in the strongly connected components that are not natural loops (have more than one entry block) are marked with BB_IRREDUCIBLE_LOOP and EDGE_IRREDUCIBLE_LOOP flags.  The flag is not set for blocks and edges that belong to natural loops that are in such an irreducible region (but it is set for the entry and exit edges of such a loop, if they lead to/from this region).

  * LOOPS_HAVE_MARKED_SINGLE_EXITS: If a loop has exactly one exit edge, this edge is stored in single_exit field of the loop structure.  NULL is stored there otherwise.

These properties may also be computed/enforced later, using functions create_preheaders, force_single_succ_latches, mark_irreducible_loops and mark_single_exit_loops.

The memory occupied by the loops structures should be freed with 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 most common tasks.  On GIMPLE, cleanup_tree_cfg_loop function can be used to cleanup CFG while updating the loops structures if current_loops is set.

Loop querying
=============

The functions to query the information about loops are declared in cfgloop.h.  Some of the information can be taken directly from the structures.  loop_father field of each basic block contains the innermost loop to that the block belongs.  The most useful fields of loop structure (that are kept up-to-date at all times) are:

  * header, latch: Header and latch basic blocks of the loop.

  * num_nodes: Number of basic blocks in the loop (including the basic blocks of the sub-loops).

  * depth: The depth of the loop in the loops tree, i.e., the number of super-loops of the loop.

  * outer, inner, next: The super-loop, the first sub-loop, and the sibling of the loop in the loops tree.

  * single_exit: The exit edge of the loop, if the loop has exactly one exit and the loops were analyzed with LOOPS_HAVE_MARKED_SINGLE_EXITS.

There are other fields in the loop structures, many of them used only by some of the passes, or not updated during CFG changes; in general, they should not be accessed directly.

The most important functions to query loop structures are:

  * flow_loops_dump: Dumps the information about loops to a file.

  * verify_loop_structure: Checks consistency of the loop structures.

  * loop_latch_edge: Returns the latch edge of a loop.

  * loop_preheader_edge: If loops have preheaders, returns the preheader edge of a loop.

  * flow_loop_nested_p: Tests whether loop is a sub-loop of another loop.

  * flow_bb_inside_loop_p: Tests whether a basic block belongs to a loop (including its sub-loops).

  * find_common_loop: Finds the common super-loop of two loops.

  * superloop_at_depth: Returns the super-loop of a loop with the given depth.

  * tree_num_loop_insns, num_loop_insns: Estimates the number of insns in the loop, on GIMPLE and on RTL.

  * loop_exit_edge_p: Tests whether edge is an exit from a loop.

  * mark_loop_exit_edges: Marks all exit edges of all loops with EDGE_LOOP_EXIT flag.

  * get_loop_body, get_loop_body_in_dom_order, get_loop_body_in_bfs_order: Enumerates the basic blocks in the loop in depth-first search order in reversed CFG, ordered by dominance relation, and breath-first search order, respectively.

  * get_loop_exit_edges: Enumerates the exit edges of a loop.

  * just_once_each_iteration_p: Returns true if the basic block is executed exactly once during each iteration of a loop (that is, it does not belong to a sub-loop, and it dominates the latch of the loop).

Loop manipulation
=================

The loops tree can be manipulated using the following functions:

  * flow_loop_tree_node_add: Adds a node to the tree.

  * flow_loop_tree_node_remove: Removes a node from the tree.

  * add_bb_to_loop: Adds a basic block to a loop.

  * remove_bb_from_loops: Removes a basic block from loops.

The specialized versions of several low-level CFG functions that also update loop structures are provided:

  * loop_split_edge_with: Splits an edge, and places a specified RTL code on it.  On GIMPLE, the function can still be used, but the code must be NULL.

  * bsi_insert_on_edge_immediate_loop: Inserts code on edge, splitting it if necessary.  Only works on GIMPLE.

  * remove_path: Removes an edge and all blocks it dominates.

  * loop_commit_inserts: Commits insertions scheduled on edges, and sets loops for the new blocks.  This function can only be used on GIMPLE.

  * split_loop_exit_edge: Splits exit edge of the loop, ensuring that PHI node arguments remain in the loop (this ensures that loop-closed SSA form is preserved).  Only useful on GIMPLE.

Finally, there are some higher-level loop transformations implemented. While some of them are written so that they should work on non-innermost loops, they are mostly untested in that case, and at the moment, they are only reliable for the innermost loops:

  * create_iv: Creates a new induction variable.  Only works on GIMPLE.  standard_iv_increment_position can be used to find a suitable place for the iv increment.

  * duplicate_loop_to_header_edge, tree_duplicate_loop_to_header_edge: These functions (on RTL and on GIMPLE) duplicate the body of the loop prescribed number of times on one of the edges entering loop header, thus performing either loop unrolling or loop peeling.  can_duplicate_loop_p (can_unroll_loop_p on GIMPLE) must be true for the duplicated loop.

  * loop_version, tree_ssa_loop_version: These function create a copy of a loop, and a branch before them that selects one of them depending on the prescribed condition.  This is useful for optimizations that need to verify some assumptions in runtime (one of the copies of the loop is usually left unchanged, while the other one is transformed in some way).

  * tree_unroll_loop: Unrolls the loop, including peeling the extra iterations to make the number of iterations divisible by unroll factor, updating the exit condition, and removing the exits that now cannot be taken.  Works only on GIMPLE.

Loop-closed SSA form
====================

Throughout the loop optimizations on tree level, one extra condition is enforced on the SSA form:  No SSA name is used outside of the loop in that it is defined.  The SSA form satisfying this condition is called ``loop-closed SSA form'' -- LCSSA.  To enforce LCSSA, PHI nodes must be created at the exits of the loops for the SSA names that are used outside of them.  Only the real operands (not virtual SSA names) are held in LCSSA, in order to save memory.

There are various benefits of LCSSA:

  * Many optimizations (value range analysis, final value replacement) are interested in the values that are defined in the loop and used outside of it, i.e., exactly those for that we create new PHI nodes.

  * In induction variable analysis, it is not necessary to specify the loop in that the analysis should be performed -- the scalar evolution analysis always returns the results with respect to the loop in that the SSA name is defined.

  * It makes updating of SSA form during loop transformations simpler. Without LCSSA, operations like loop unrolling may force creation of PHI nodes arbitrarily far from the loop, while in LCSSA, the SSA form can be updated locally.  However, since we only keep real operands in LCSSA, we cannot use this advantage (we could have local updating of real operands, but it is not much more efficient than to use generic SSA form updating for it as well; the amount of changes to SSA is the same).

However, it also means LCSSA must be updated.  This is usually straightforward, unless you create a new value in loop and use it outside, or unless you manipulate loop exit edges (functions are provided to make these manipulations simple). rewrite_into_loop_closed_ssa is used to rewrite SSA form to LCSSA, and verify_loop_closed_ssa to check that the invariant of LCSSA is preserved.

Scalar evolutions
=================

Scalar evolutions (SCEV) are used to represent results of induction variable analysis on GIMPLE.  They enable us to represent variables with complicated behavior in a simple and consistent way (we only use it to express values of polynomial induction variables, but it is possible to extend it).  The interfaces to SCEV analysis are declared in tree-scalar-evolution.h.  To use scalar evolutions analysis, scev_initialize must be used.  To stop using SCEV, scev_finalize should be used.  SCEV analysis caches results in order to save time and memory.  This cache however is made invalid by most of the loop transformations, including removal of code.  If such a transformation is performed, scev_reset must be called to clean the caches.

Given an SSA name, its behavior in loops can be analyzed using the analyze_scalar_evolution function.  The returned SCEV however does not have to be fully analyzed and it may contain references to other SSA names defined in the loop.  To resolve these (potentially recursive) references, instantiate_parameters or resolve_mixers functions must be used. instantiate_parameters is useful when you use the results of SCEV only for some analysis, and when you work with whole nest of loops at once.  It will try replacing all SSA names by their SCEV in all loops, including the super-loops of the current loop, thus providing a complete information about the behavior of the variable in the loop nest. resolve_mixers is useful if you work with only one loop at a time, and if you possibly need to create code based on the value of the induction variable.  It will only resolve the SSA names defined in the current loop, leaving the SSA names defined outside unchanged, even if their evolution in the outer loops is known.

The SCEV is a normal tree expression, except for the fact that it may contain several special tree nodes.  One of them is SCEV_NOT_KNOWN, used for SSA names whose value cannot be expressed.  The other one is POLYNOMIAL_CHREC.  Polynomial chrec has three arguments -- base, step and loop (both base and step may contain further polynomial chrecs).  Type of the expression and of base and step must be the same.  A variable has evolution POLYNOMIAL_CHREC(base, step, loop) if it is (in the specified loop) equivalent to x_1 in the following example

     while (...)
       {
         x_1 = phi (base, x_2);
         x_2 = x_1 + step;
       }

Note that this includes the language restrictions on the operations. For example, if we compile C code and x has signed type, then the overflow in addition would cause undefined behavior, and we may assume that this does not happen.  Hence, the value with this SCEV cannot overflow (which restricts the number of iterations of such a loop).

In many cases, one wants to restrict the attention just to affine induction variables.  In this case, the extra expressive power of SCEV is not useful, and may complicate the optimizations.  In this case, simple_iv function may be used to analyze a value -- the result is a loop-invariant base and step.

IV analysis on RTL
==================

The induction variable on RTL is simple and only allows analysis of affine induction variables, and only in one loop at once.  The interface is declared in cfgloop.h.  Before analyzing induction variables in a loop L, iv_analysis_loop_init function must be called on L. After the analysis (possibly calling iv_analysis_loop_init for several loops) is finished, iv_analysis_done should be called. The following functions can be used to access the results of the analysis:

  * iv_analyze: Analyzes a single register used in the given insn.  If no use of the register in this insn is found, the following insns are scanned, so that this function can be called on the insn returned by get_condition.

  * iv_analyze_result: Analyzes result of the assignment in the given insn.

  * iv_analyze_expr: Analyzes a more complicated expression. All its operands are analyzed by iv_analyze, and hence they must be used in the specified insn or one of the following insns.

The description of the induction variable is provided in struct rtx_iv.  In order to handle subregs, the representation is a bit complicated; if the value of the extend field is not UNKNOWN, the value of the induction variable in the i-th iteration is

     delta + mult * extend_{extend_mode} (subreg_{mode} (base + i * step)),

with the following exception:  if first_special is true, then the value in the first iteration (when i is zero) is delta + mult * base.  However, if extend is equal to UNKNOWN, then first_special must be false, delta 0, mult 1 and the value in the i-th iteration is

     subreg_{mode} (base + i * step)

The function get_iv_value can be used to perform these calculations.

Number of iterations analysis
=============================

Both on GIMPLE and on RTL, there are functions available to determine the number of iterations of a loop, with a similar interface.  In many cases, it is not possible to determine number of iterations unconditionally -- the determined number is correct only if some assumptions are satisfied.  The analysis tries to verify these conditions using the information contained in the program; if it fails, the conditions are returned together with the result.  The following information and conditions are provided by the analysis:

  * assumptions: If this condition is false, the rest of the information is invalid.

  * noloop_assumptions on RTL, may_be_zero on GIMPLE: If this condition is true, the loop exits in the first iteration.

  * infinite: If this condition is true, the loop is infinite. This condition is only available on RTL.  On GIMPLE, conditions for finiteness of the loop are included in assumptions.

  * niter_expr on RTL, niter on GIMPLE: The expression that gives number of iterations.  The number of iterations is defined as the number of executions of the loop latch.

Both on GIMPLE and on RTL, it necessary for the induction variable analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL). On GIMPLE, the results are stored to struct tree_niter_desc structure.  Number of iterations before the loop is exited through a given exit can be determined using number_of_iterations_exit function.  On RTL, the results are returned in struct niter_desc structure.  The corresponding function is named check_simple_exit.  There are also functions that pass through all the exits of a loop and try to find one with easy to determine number of iterations -- find_loop_niter on GIMPLE and find_simple_exit on RTL.  Finally, there are functions that provide the same information, but additionally cache it, so that repeated calls to number of iterations are not so costly -- number_of_iterations_in_loop on GIMPLE and get_simple_loop_desc on RTL.

Note that some of these functions may behave slightly differently than others -- some of them return only the expression for the number of iterations, and fail if there are some assumptions.  The function number_of_iterations_in_loop works only for single-exit loops, and it returns the value for number of iterations higher by one with respect to all other functions (i.e., it returns number of executions of the exit statement, not of the loop latch).

Data Dependency Analysis
========================

The code for the data dependence analysis can be found in tree-data-ref.c and its interface and data structures are described in tree-data-ref.h.  The function that computes the data dependences for all the array and pointer references for a given loop is compute_data_dependences_for_loop.  This function is currently used by the linear loop transform and the vectorization passes.  Before calling this function, one has to allocate two vectors: a first vector will contain the set of data references that are contained in the analyzed loop body, and the second vector will contain the dependence relations between the data references.  Thus if the vector of data references is of size n, the vector containing the dependence relations will contain n*n elements.  However if the analyzed loop contains side effects, such as calls that potentially can interfere with the data references in the current analyzed loop, the analysis stops while scanning the loop body for data references, and inserts a single chrec_dont_know in the dependence relation array.

The data references are discovered in a particular order during the scanning of the loop body: the loop body is analyzed in execution order, and the data references of each statement are pushed at the end of the data reference array.  Two data references syntactically occur in the program in the same order as in the array of data references.  This syntactic order is important in some classical data dependence tests, and mapping this order to the elements of this array avoids costly queries to the loop body representation.

Three types of data references are currently handled: ARRAY_REF, INDIRECT_REF and COMPONENT_REF. The data structure for the data reference is data_reference, where data_reference_p is a name of a pointer to the data reference structure. The structure contains the following elements:

  * base_object_info: Provides information about the base object of the data reference and its access functions. These access functions represent the evolution of the data reference in the loop relative to its base, in keeping with the classical meaning of the data reference access function for the support of arrays. For example, for a reference a.b[i][j], the base object is a.b and the access functions, one for each array subscript, are: {i_init, + i_step}_1, {j_init, +, j_step}_2.

  * first_location_in_loop: Provides information about the first location accessed by the data reference in the loop and about the access function used to represent evolution relative to this location. This data is used to support pointers, and is not used for arrays (for which we have base objects). Pointer accesses are represented as a one-dimensional access that starts from the first location accessed in the loop. For example:

                for1 i
                   for2 j
                    *((int *)p + i + j) = a[i][j];

     The access function of the pointer access is {0, + 4B}_for2 relative to p + i. The access functions of the array are {i_init, + i_step}_for1 and {j_init, +, j_step}_for2 relative to a.

     Usually, the object the pointer refers to is either unknown, or we can't prove that the access is confined to the boundaries of a certain object.

     Two data references can be compared only if at least one of these two representations has all its fields filled for both data references.

     The current strategy for data dependence tests is as follows: If both a and b are represented as arrays, compare a.base_object and b.base_object; if they are equal, apply dependence tests (use access functions based on base_objects). Else if both a and b are represented as pointers, compare a.first_location and b.first_location; if they are equal, apply dependence tests (use access functions based on first location). However, if a and b are represented differently, only try to prove that the bases are definitely different.

  * Aliasing information.

  * Alignment information.

The structure describing the relation between two data references is data_dependence_relation and the shorter name for a pointer to such a structure is ddr_p.  This structure contains:

  * a pointer to each data reference,

  * a tree node are_dependent that is set to chrec_known if the analysis has proved that there is no dependence between these two data references, chrec_dont_know if the analysis was not able to determine any useful result and potentially there could exist a dependence between these data references, and are_dependent is set to NULL_TREE if there exist a dependence relation between the data references, and the description of this dependence relation is given in the subscripts, dir_vects, and dist_vects arrays,

  * a boolean that determines whether the dependence relation can be represented by a classical distance vector,

  * an array subscripts that contains a description of each subscript of the data references.  Given two array accesses a subscript is the tuple composed of the access functions for a given dimension.  For example, given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts: (f1, g1), (f2, g2), (f3, g3).

  * two arrays dir_vects and dist_vects that contain classical representations of the data dependences under the form of direction and distance dependence vectors,

  * an array of loops loop_nest that contains the loops to which the distance and direction vectors refer to.

Several functions for pretty printing the information extracted by the data dependence analysis are available: dump_ddrs prints with a maximum verbosity the details of a data dependence relations array, dump_dist_dir_vectors prints only the classical distance and direction vectors for a data dependence relations array, and dump_data_references prints the details of the data references contained in a data reference array.

Linear loop transformations framework
=====================================

Lambda is a framework that allows transformations of loops using non-singular matrix based transformations of the iteration space and loop bounds. This allows compositions of skewing, scaling, interchange, and reversal transformations.  These transformations are often used to improve cache behavior or remove inner loop dependencies to allow parallelization and vectorization to take place.

To perform these transformations, Lambda requires that the loopnest be converted into a internal form that can be matrix transformed easily. To do this conversion, the function gcc_loopnest_to_lambda_loopnest is provided.  If the loop cannot be transformed using lambda, this function will return NULL.

Once a lambda_loopnest is obtained from the conversion function, it can be transformed by using lambda_loopnest_transform, which takes a transformation matrix to apply.  Note that it is up to the caller to verify that the transformation matrix is legal to apply to the loop (dependence respecting, etc).  Lambda simply applies whatever matrix it is told to provide.  It can be extended to make legal matrices out of any non-singular matrix, but this is not currently implemented. Legality of a matrix for a given loopnest can be verified using lambda_transform_legal_p.

Given a transformed loopnest, conversion back into gcc IR is done by lambda_loopnest_to_gcc_loopnest.  This function will modify the loops so that they match the transformed loopnest.