This condition is only available on RTL@.  On GIMPLE, conditions forfiniteness of the loop are included in @code{assumptions}.@item @code{niter_expr} on RTL, @code{niter} on GIMPLE: The expressionthat gives number of iterations.  The number of iterations is defined asthe number of executions of the loop latch.@end itemizeBoth on GIMPLE and on RTL, it necessary for the induction variableanalysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).On GIMPLE, the results are stored to @code{struct tree_niter_desc}structure.  Number of iterations before the loop is exited through agiven exit can be determined using @code{number_of_iterations_exit}function.  On RTL, the results are returned in @code{struct niter_desc}structure.  The corresponding function is named@code{check_simple_exit}.  There are also functions that pass throughall the exits of a loop and try to find one with easy to determinenumber of iterations -- @code{find_loop_niter} on GIMPLE and@code{find_simple_exit} on RTL@.  Finally, there are functions thatprovide the same information, but additionally cache it, so thatrepeated calls to number of iterations are not so costly --@code{number_of_latch_executions} on GIMPLE and @code{get_simple_loop_desc}on RTL.Note that some of these functions may behave slightly differently thanothers -- some of them return only the expression for the number ofiterations, and fail if there are some assumptions.  The function@code{number_of_latch_executions} works only for single-exit loops.The function @code{number_of_cond_exit_executions} can be used todetermine number of executions of the exit condition of a single-exitloop (i.e., the @code{number_of_latch_executions} increased by one).@node Dependency analysis@section Data Dependency Analysis@cindex Data Dependency AnalysisThe code for the data dependence analysis can be found in@file{tree-data-ref.c} and its interface and data structures aredescribed in @file{tree-data-ref.h}.  The function that computes thedata dependences for all the array and pointer references for a givenloop is @code{compute_data_dependences_for_loop}.  This function iscurrently used by the linear loop transform and the vectorizationpasses.  Before calling this function, one has to allocate two vectors:a first vector will contain the set of data references that arecontained in the analyzed loop body, and the second vector will containthe dependence relations between the data references.  Thus if thevector of data references is of size @code{n}, the vector containing thedependence relations will contain @code{n*n} elements.  However if theanalyzed loop contains side effects, such as calls that potentially caninterfere with the data references in the current analyzed loop, theanalysis stops while scanning the loop body for data references, andinserts a single @code{chrec_dont_know} in the dependence relationarray.The data references are discovered in a particular order during thescanning 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 thedata reference array.  Two data references syntactically occur in theprogram in the same order as in the array of data references.  Thissyntactic order is important in some classical data dependence tests,and mapping this order to the elements of this array avoids costlyqueries 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 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: @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 have base objects). Pointer accesses are represented as a one-dimensionalaccess that starts from the first location accessed in the loop. For example:@smallexample      for1 i         for2 j          *((int *)p + i + j) = a[i][j];@end smallexampleThe 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. 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 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 base_objects).Else if both @code{a} and @code 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 are represented differently, only try to prove that the bases are definitely different.@item Aliasing information.@item Alignment information.@end itemizeThe structure describing the relation between two data references is@code{data_dependence_relation} and the shorter name for a pointer tosuch a structure is @code{ddr_p}.  This structure contains:@itemize@item a pointer to each data reference,@item a tree node @code{are_dependent} that is set to @code{chrec_known}if the analysis has proved that there is no dependence between these twodata references, @code{chrec_dont_know} if the analysis was not able todetermine any useful result and potentially there could exist adependence between these data references, and @code{are_dependent} isset to @code{NULL_TREE} if there exist a dependence relation between thedata references, and the description of this dependence relation isgiven in the @code{subscripts}, @code{dir_vects}, and @code{dist_vects}arrays,@item a boolean that determines whether the dependence relation can berepresented by a classical distance vector, @item an array @code{subscripts} that contains a description of eachsubscript of the data references.  Given two array accesses asubscript is the tuple composed of the access functions for a givendimension.  For example, given @code{A[f1][f2][f3]} and@code{B[g1][g2][g3]}, there are three subscripts: @code{(f1, g1), (f2,g2), (f3, g3)}.@item two arrays @code{dir_vects} and @code{dist_vects} that containclassical representations of the data dependences under the form ofdirection and distance dependence vectors,@item an array of loops @code{loop_nest} that contains the loops towhich the distance and direction vectors refer to.@end itemizeSeveral functions for pretty printing the information extracted by thedata dependence analysis are available: @code{dump_ddrs} prints with amaximum verbosity the details of a data dependence relations array,@code{dump_dist_dir_vectors} prints only the classical distance anddirection vectors for a data dependence relations array, and@code{dump_data_references} prints the details of the data referencescontained in a data reference array.@node Lambda@section Linear loop transformations framework@cindex Linear loop transformations frameworkLambda is a framework that allows transformations of loops usingnon-singular matrix based transformations of the iteration space andloop bounds. This allows compositions of skewing, scaling, interchange,and reversal transformations.  These transformations are often used toimprove cache behavior or remove inner loop dependencies to allowparallelization and vectorization to take place.To perform these transformations, Lambda requires that the loopnest beconverted 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 cannotbe 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}, whichtakes a transformation matrix to apply.  Note that it is up to thecaller to verify that the transformation matrix is legal to apply to theloop (dependence respecting, etc).  Lambda simply applies whatevermatrix it is told to provide.  It can be extended to make legal matricesout 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 theloops so that they match the transformed loopnest.@node Omega@section Omega a solver for linear programming problems@cindex Omega a solver for linear programming problemsThe data dependence analysis contains several solvers triggeredsequentially from the less complex ones to the more sophisticated.For ensuring the consistency of the results of these solvers, a datadependence check pass has been implemented based on two differentsolvers.  The second method that has been integrated to GCC is basedon the Omega dependence solver, written in the 1990's by William Pughand David Wonnacott.  Data dependence tests can be formulated using asubset of the Presburger arithmetics that can be translated to linearconstraint systems.  These linear constraint systems can then besolved using the Omega solver.The Omega solver is using Fourier-Motzkin's algorithm for variableelimination: a linear constraint system containing @code{n} variablesis reduced to a linear constraint system with @code{n-1} variables.The Omega solver can also be used for solving other problems that canbe expressed under the form of a system of linear equalities andinequalities.  The Omega solver is known to have an exponential worstcase, also known under the name of ``omega nightmare'' in theliterature, but in practice, the omega test is known to be efficientfor the common data dependence tests.The interface used by the Omega solver for describing the linearprogramming problems is described in @file{omega.h}, and the solver is@code{omega_solve_problem}.