--- a/gcc/doc/loop.texi	Sun Aug 21 07:07:55 2011 +0900
+++ b/gcc/doc/loop.texi	Fri Oct 27 22:46:09 2017 +0900
@@ -1,4 +1,4 @@
-@c Copyright (c) 2006, 2007, 2008 Free Software Foundation, Inc.
+@c Copyright (C) 2006-2017 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.
@@ -25,8 +25,6 @@
 * 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
@@ -37,10 +35,13 @@
 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
@@ -139,9 +140,13 @@
 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
@@ -149,6 +154,10 @@
 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
@@ -164,8 +173,6 @@
 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
@@ -177,6 +184,8 @@
 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
@@ -249,12 +258,11 @@
 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
@@ -467,6 +475,32 @@
 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
@@ -498,28 +532,28 @@
 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
@@ -528,27 +562,27 @@
           *((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.
@@ -571,7 +605,7 @@
 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
@@ -592,64 +626,3 @@
 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 an 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}.