-@c Copyright (c) 2006, 2007, 2008 Free Software Foundation, Inc.
+@c Copyright (C) 2006-2023 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.
variable 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.
+* 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.
@end menu
@node 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 @file{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.
+Loop structures are analyzed and this information disposed or updated
+at the discretion of individual passes. Still most of the generic
+CFG manipulation routines are aware of loop structures and try to
+keep them up-to-date. By this means an increasing part of the
+compilation pipeline is setup to maintain loop structure across
+passes to allow attaching meta information to individual loops
+for consumption by later 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
enumerate 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. The
+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 @code{struct loops} structure.
The entries of the @code{larray} field should not be accessed directly.
The function @code{get_loop} returns the loop description for a loop with
-the given index. @code{number_of_loops} function returns number of
-loops in the function. To traverse all loops, use @code{FOR_EACH_LOOP}
-macro. The @code{flags} argument of the macro is used to determine
-the direction of traversal and the set of loops visited. Each loop is
+the given index. @code{number_of_loops} function returns number of loops
+in the function. To traverse all loops, use a range-based for loop with
+class @code{loops_list} instance. The @code{flags} argument passed to the
+constructor function of class @code{loops_list} is used to determine the
+direction of traversal and the set of loops visited. Each loop is
guaranteed to be visited exactly once, regardless of the changes to the
loop tree, and the loops may be removed during the traversal. The newly
-created loops are never traversed, if they need to be visited, this
-must be done separately after their creation. The @code{FOR_EACH_LOOP}
-macro allocates temporary variables. If the @code{FOR_EACH_LOOP} loop
-were ended using break or goto, they would not be released;
-@code{FOR_EACH_LOOP_BREAK} macro must be used instead.
+created loops are never traversed, if they need to be visited, this must
+be done separately after their creation.
Each basic block contains the reference to the innermost loop it belongs
to (@code{loop_father}). For this reason, it is only possible to have
one @code{struct loops} structure initialized at the same time for each
-CFG. The global variable @code{current_loops} contains the
+CFG@. The global variable @code{current_loops} contains the
@code{struct loops} structure. Many of the loop manipulation functions
assume that dominance information is up-to-date.
@item @code{LOOPS_MAY_HAVE_MULTIPLE_LATCHES}: If this flag is set, no
changes to CFG will be performed in the loop analysis, in particular,
loops with multiple latch edges will not be disambiguated. If a loop
-has multiple latches, its latch block is set to NULL. Most of
+has multiple latches, its latch block is set to NULL@. Most of
the loop manipulation functions will not work for loops in this shape.
No other flags that require CFG changes can be passed to
loop_optimizer_init.
These 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 properties can be queried using @code{loops_state_satisfies_p}.
The memory occupied by the loops structures should be freed with
-@code{loop_optimizer_finalize} function.
+@code{loop_optimizer_finalize} function. When loop structures are
+setup to be preserved across passes this function reduces the
+information to be kept up-to-date to a minimum (only
+@code{LOOPS_MAY_HAVE_MULTIPLE_LATCHES} set).
The CFG manipulation functions in general do not update loop structures.
Specialized versions that additionally do so are provided for the most
used to cleanup CFG while updating the loops structures if
@code{current_loops} is set.
+At the moment loop structure is preserved from the start of GIMPLE
+loop optimizations until the end of RTL loop optimizations. During
+this time a loop can be tracked by its @code{struct loop} and number.
+
@node Loop querying
@section Loop querying
@cindex Loop querying
loop.
@item @code{num_nodes}: Number of basic blocks in the loop (including
the basic blocks of the sub-loops).
-@item @code{depth}: The depth of the loop in the loops tree, i.e., the
-number of super-loops of the loop.
@item @code{outer}, @code{inner}, @code{next}: The super-loop, the first
sub-loop, and the sibling of the loop in the loops tree.
@end itemize
The most important functions to query loop structures are:
@itemize
+@item @code{loop_depth}: The depth of the loop in the loops tree, i.e., the
+number of super-loops of the loop.
@item @code{flow_loops_dump}: Dumps the information about loops to a
file.
@item @code{verify_loop_structure}: Checks consistency of the loop
relation, 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 this
-function if LOOPS_HAVE_MARKED_SINGLE_EXITS property is used.
+function if @code{LOOPS_HAVE_RECORDED_EXITS} 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 block
is executed exactly once during each iteration of a loop (that is, it
@itemize
@item @code{create_iv}: Creates a new induction variable. Only works on
-GIMPLE. @code{standard_iv_increment_position} can be used to find a
+GIMPLE@. @code{standard_iv_increment_position} can be used to find a
suitable place for the iv increment.
-@item @code{duplicate_loop_to_header_edge},
-@code{tree_duplicate_loop_to_header_edge}: These functions (on RTL and
+@item @code{duplicate_loop_body_to_header_edge},
+@code{tree_duplicate_loop_body_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. @code{can_duplicate_loop_p}
(@code{can_unroll_loop_p} on GIMPLE) must be true for the duplicated
loop.
-@item @code{loop_version}, @code{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).
+@item @code{loop_version}: This function creates 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).
@item @code{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
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
+``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.
@cindex IV analysis on GIMPLE
Scalar evolutions (SCEV) are used to represent results of induction
-variable analysis on GIMPLE. They enable us to represent variables with
+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
loop) equivalent to @code{x_1} in the following example
@smallexample
-while (...)
+while (@dots{})
@{
x_1 = phi (base, x_2);
x_2 = x_1 + step;
@item @code{noloop_assumptions} on RTL, @code{may_be_zero} on GIMPLE: If
this condition is true, the loop exits in the first iteration.
@item @code{infinite}: If this condition is true, the loop is infinite.
-This condition is only available on RTL. On GIMPLE, conditions for
+This condition is only available on RTL@. On GIMPLE, conditions for
finiteness of the loop are included in @code{assumptions}.
@item @code{niter_expr} on RTL, @code{niter} on GIMPLE: The expression
that gives number of iterations. The number of iterations is defined as
@code{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 -- @code{find_loop_niter} on GIMPLE and
-@code{find_simple_exit} on RTL. Finally, there are functions that
+@code{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 --
@code{number_of_latch_executions} on GIMPLE and @code{get_simple_loop_desc}
determine number of executions of the exit condition of a single-exit
loop (i.e., the @code{number_of_latch_executions} increased by one).
+On GIMPLE, below constraint flags affect semantics of some APIs of number
+of iterations analyzer:
+
+@itemize
+@item @code{LOOP_C_INFINITE}: If this constraint flag is set, the loop
+is known to be infinite. APIs like @code{number_of_iterations_exit} can
+return false directly without doing any analysis.
+@item @code{LOOP_C_FINITE}: If this constraint flag is set, the loop is
+known to be finite, in other words, loop's number of iterations can be
+computed with @code{assumptions} be true.
+@end itemize
+
+Generally, the constraint flags are set/cleared by consumers which are
+loop optimizers. It's also the consumers' responsibility to set/clear
+constraints correctly. Failing to do that might result in hard to track
+down bugs in scev/niter consumers. One typical use case is vectorizer:
+it drives number of iterations analyzer by setting @code{LOOP_C_FINITE}
+and vectorizes possibly infinite loop by versioning loop with analysis
+result. In return, constraints set by consumers can also help number of
+iterations analyzer in following optimizers. For example, @code{niter}
+of a loop versioned under @code{assumptions} is valid unconditionally.
+
+Other constraints may be added in the future, for example, a constraint
+indicating that loops' latch must roll thus @code{may_be_zero} would be
+false unconditionally.
+
@node Dependency analysis
@section Data Dependency Analysis
@cindex Data Dependency Analysis
The code for the data dependence analysis can be found in
-@file{tree-data-ref.c} and its interface and data structures are
+@file{tree-data-ref.cc} and its interface and data structures are
described in @file{tree-data-ref.h}. The function that computes the
data dependences for all the array and pointer references for a given
loop is @code{compute_data_dependences_for_loop}. This function is
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 @code{data_reference}, where @code{data_reference_p} is a name of a
-pointer to the data reference structure. The structure contains the
+Three types of data references are currently handled: ARRAY_REF,
+INDIRECT_REF and COMPONENT_REF@. The data structure for the data reference
+is @code{data_reference}, where @code{data_reference_p} is a name of a
+pointer to the data reference structure. The structure contains the
following elements:
@itemize
-@item @code{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
-@code{a.b[i][j]}, the base object is @code{a.b} and the access functions,
-one for each array subscript, are:
+@item @code{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
+@code{a.b[i][j]}, the base object is @code{a.b} and the access functions,
+one for each array subscript, are:
@code{@{i_init, + i_step@}_1, @{j_init, +, j_step@}_2}.
-@item @code{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
+@item @code{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
+access that starts from the first location accessed in the loop. For
example:
@smallexample
*((int *)p + i + j) = a[i][j];
@end smallexample
-The access function of the pointer access is @code{@{0, + 4B@}_for2}
-relative to @code{p + i}. The access functions of the array are
-@code{@{i_init, + i_step@}_for1} and @code{@{j_init, +, j_step@}_for2}
+The access function of the pointer access is @code{@{0, + 4B@}_for2}
+relative to @code{p + i}. The access functions of the array are
+@code{@{i_init, + i_step@}_for1} and @code{@{j_init, +, j_step@}_for2}
relative to @code{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.
+Usually, the object the pointer refers to is either unknown, or we cannot
+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.
+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 @code{a} and @code{b} are represented as arrays, compare
+The current strategy for data dependence tests is as follows:
+If both @code{a} and @code{b} are represented as arrays, compare
@code{a.base_object} and @code{b.base_object};
-if they are equal, apply dependence tests (use access functions based on
+if they are equal, apply dependence tests (use access functions based on
base_objects).
-Else if both @code{a} and @code{b} are represented as pointers, compare
-@code{a.first_location} and @code{b.first_location};
-if they are equal, apply dependence tests (use access functions based on
+Else if both @code{a} and @code{b} are represented as pointers, compare
+@code{a.first_location} and @code{b.first_location};
+if they are equal, apply dependence tests (use access functions based on
first location).
-However, if @code{a} and @code{b} are represented differently, only try
+However, if @code{a} and @code{b} are represented differently, only try
to prove that the bases are definitely different.
@item Aliasing information.
given in the @code{subscripts}, @code{dir_vects}, and @code{dist_vects}
arrays,
@item a boolean that determines whether the dependence relation can be
-represented by a classical distance vector,
+represented by a classical distance vector,
@item an array @code{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
direction vectors for a data dependence relations array, and
@code{dump_data_references} prints the details of the data references
contained in a data reference array.
-
-@node Lambda
-@section Linear loop transformations framework
-@cindex 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
-@code{gcc_loopnest_to_lambda_loopnest} is provided. If the loop cannot
-be transformed using lambda, this function will return NULL.
-
-Once a @code{lambda_loopnest} is obtained from the conversion function,
-it can be transformed by using @code{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
-@code{lambda_transform_legal_p}.
-
-Given a transformed loopnest, conversion back into gcc IR is done by
-@code{lambda_loopnest_to_gcc_loopnest}. This function will modify the
-loops so that they match the transformed loopnest.
-
-
-@node Omega
-@section Omega a solver for linear programming problems
-@cindex Omega a solver for linear programming problems
-
-The data dependence analysis contains several solvers triggered
-sequentially from the less complex ones to the more sophisticated.
-For ensuring the consistency of the results of these solvers, a data
-dependence check pass has been implemented based on two different
-solvers. The second method that has been integrated to GCC is based
-on the Omega dependence solver, written in the 1990's by William Pugh
-and David Wonnacott. Data dependence tests can be formulated using a
-subset of the Presburger arithmetics that can be translated to linear
-constraint systems. These linear constraint systems can then be
-solved using the Omega solver.
-
-The Omega solver is using Fourier-Motzkin's algorithm for variable
-elimination: a linear constraint system containing @code{n} variables
-is reduced to a linear constraint system with @code{n-1} variables.
-The Omega solver can also be used for solving other problems that can
-be expressed under the form of a system of linear equalities and
-inequalities. The Omega solver is known to have an exponential worst
-case, also known under the name of ``omega nightmare'' in the
-literature, but in practice, the omega test is known to be efficient
-for the common data dependence tests.
-
-The interface used by the Omega solver for describing the linear
-programming problems is described in @file{omega.h}, and the solver is
-@code{omega_solve_problem}.
projects / thirdparty / gcc.git / blobdiff