1 @c Copyright (c) 2006 Free Software Foundation, Inc.
2 @c Free Software Foundation, Inc.
3 @c This is part of the GCC manual.
4 @c For copying conditions, see the file gcc.texi.
6 @c ---------------------------------------------------------------------
8 @c ---------------------------------------------------------------------
10 @node Loop Representation
11 @chapter Analysis and Representation of Loops
13 GCC provides extensive infrastructure for work with natural loops, i.e.,
14 strongly connected components of CFG with only one entry block. This
15 chapter describes representation of loops in GCC, both on GIMPLE and in
16 RTL, as well as the interfaces to loop-related analyses (induction
17 variable analysis and number of iterations analysis).
20 * Loop representation:: Representation and analysis of loops.
21 * Loop querying:: Getting information about loops.
22 * Loop manipulation:: Loop manipulation functions.
23 * LCSSA:: Loop-closed SSA form.
24 * Scalar evolutions:: Induction variables on GIMPLE.
25 * loop-iv:: Induction variables on RTL.
26 * Number of iterations:: Number of iterations analysis.
27 * Dependency analysis:: Data dependency analysis.
28 * Lambda:: Linear loop transformations framework.
31 @node Loop representation
32 @section Loop representation
33 @cindex Loop representation
36 This chapter describes the representation of loops in GCC, and functions
37 that can be used to build, modify and analyze this representation. Most
38 of the interfaces and data structures are declared in @file{cfgloop.h}.
39 At the moment, loop structures are analyzed and this information is
40 updated only by the optimization passes that deal with loops, but some
41 efforts are being made to make it available throughout most of the
44 In general, a natural loop has one entry block (header) and possibly
45 several back edges (latches) leading to the header from the inside of
46 the loop. Loops with several latches may appear if several loops share
47 a single header, or if there is a branching in the middle of the loop.
48 The representation of loops in GCC however allows only loops with a
49 single latch. During loop analysis, headers of such loops are split and
50 forwarder blocks are created in order to disambiguate their structures.
51 A heuristic based on profile information is used to determine whether
52 the latches correspond to sub-loops or to control flow in a single loop.
53 This means that the analysis sometimes changes the CFG, and if you run
54 it in the middle of an optimization pass, you must be able to deal with
57 Body of the loop is the set of blocks that are dominated by its header,
58 and reachable from its latch against the direction of edges in CFG. The
59 loops are organized in a containment hierarchy (tree) such that all the
60 loops immediately contained inside loop L are the children of L in the
61 tree. This tree is represented by the @code{struct loops} structure.
62 The root of this tree is a fake loop that contains all blocks in the
63 function. Each of the loops is represented in a @code{struct loop}
64 structure. Each loop is assigned an index (@code{num} field of the
65 @code{struct loop} structure), and the pointer to the loop is stored in
66 the corresponding field of the @code{larray} vector in the loops
67 structure. Index of a sub-loop is always greater than the index of its
68 super-loop. The indices do not have to be continuous, there may be
69 empty (@code{NULL}) entries in the @code{larray} created by deleting
70 loops. The index of a loop never changes.
72 The entries of the @code{larray} field should not be accessed directly.
73 The function @code{get_loop} returns the loop description for a loop with
74 the given index. @code{number_of_loops} function returns number of
75 loops in the function. To traverse all loops, use @code{FOR_EACH_LOOP}
76 macro. The @code{flags} argument of the macro is used to determine
77 the direction of traversal and the set of loops visited.
79 Each basic block contains the reference to the innermost loop it belongs
80 to (@code{loop_father}). For this reason, it is only possible to have
81 one @code{struct loops} structure initialized at the same time for each
82 CFG. The global variable @code{current_loops} contains the
83 @code{struct loops} structure. Many of the loop manipulation functions
84 assume that dominance information is up-to-date.
86 The loops are analyzed through @code{loop_optimizer_init} function. The
87 argument of this function is a set of flags represented in an integer
88 bitmask. These flags specify what other properties of the loop
89 structures should be calculated/enforced and preserved later:
92 @item @code{LOOPS_HAVE_PREHEADERS}: Forwarder blocks are created in such
93 a way that each loop has only one entry edge, and additionally, the
94 source block of this entry edge has only one successor. This creates a
95 natural place where the code can be moved out of the loop, and ensures
96 that the entry edge of the loop leads from its immediate super-loop.
97 @item @code{LOOPS_HAVE_SIMPLE_LATCHES}: Forwarder blocks are created to
98 force the latch block of each loop to have only one successor. This
99 ensures that the latch of the loop does not belong to any of its
100 sub-loops, and makes manipulation with the loops significantly easier.
101 Most of the loop manipulation functions assume that the loops are in
102 this shape. Note that with this flag, the ``normal'' loop without any
103 control flow inside and with one exit consists of two basic blocks.
104 @item @code{LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS}: Basic blocks and
105 edges in the strongly connected components that are not natural loops
106 (have more than one entry block) are marked with
107 @code{BB_IRREDUCIBLE_LOOP} and @code{EDGE_IRREDUCIBLE_LOOP} flags. The
108 flag is not set for blocks and edges that belong to natural loops that
109 are in such an irreducible region (but it is set for the entry and exit
110 edges of such a loop, if they lead to/from this region).
111 @item @code{LOOPS_HAVE_MARKED_SINGLE_EXITS}: If a loop has exactly one
112 exit edge, this edge is recorded in the loop structure. @code{single_exit}
113 function can be used to retrieve this edge.
116 These properties may also be computed/enforced later, using functions
117 @code{create_preheaders}, @code{force_single_succ_latches},
118 @code{mark_irreducible_loops} and @code{mark_single_exit_loops}.
120 The memory occupied by the loops structures should be freed with
121 @code{loop_optimizer_finalize} function.
123 The CFG manipulation functions in general do not update loop structures.
124 Specialized versions that additionally do so are provided for the most
125 common tasks. On GIMPLE, @code{cleanup_tree_cfg_loop} function can be
126 used to cleanup CFG while updating the loops structures if
127 @code{current_loops} is set.
130 @section Loop querying
131 @cindex Loop querying
133 The functions to query the information about loops are declared in
134 @file{cfgloop.h}. Some of the information can be taken directly from
135 the structures. @code{loop_father} field of each basic block contains
136 the innermost loop to that the block belongs. The most useful fields of
137 loop structure (that are kept up-to-date at all times) are:
140 @item @code{header}, @code{latch}: Header and latch basic blocks of the
142 @item @code{num_nodes}: Number of basic blocks in the loop (including
143 the basic blocks of the sub-loops).
144 @item @code{depth}: The depth of the loop in the loops tree, i.e., the
145 number of super-loops of the loop.
146 @item @code{outer}, @code{inner}, @code{next}: The super-loop, the first
147 sub-loop, and the sibling of the loop in the loops tree.
150 There are other fields in the loop structures, many of them used only by
151 some of the passes, or not updated during CFG changes; in general, they
152 should not be accessed directly.
154 The most important functions to query loop structures are:
157 @item @code{flow_loops_dump}: Dumps the information about loops to a
159 @item @code{verify_loop_structure}: Checks consistency of the loop
161 @item @code{loop_latch_edge}: Returns the latch edge of a loop.
162 @item @code{loop_preheader_edge}: If loops have preheaders, returns
163 the preheader edge of a loop.
164 @item @code{flow_loop_nested_p}: Tests whether loop is a sub-loop of
166 @item @code{flow_bb_inside_loop_p}: Tests whether a basic block belongs
167 to a loop (including its sub-loops).
168 @item @code{find_common_loop}: Finds the common super-loop of two loops.
169 @item @code{superloop_at_depth}: Returns the super-loop of a loop with
171 @item @code{tree_num_loop_insns}, @code{num_loop_insns}: Estimates the
172 number of insns in the loop, on GIMPLE and on RTL.
173 @item @code{loop_exit_edge_p}: Tests whether edge is an exit from a
175 @item @code{mark_loop_exit_edges}: Marks all exit edges of all loops
176 with @code{EDGE_LOOP_EXIT} flag.
177 @item @code{get_loop_body}, @code{get_loop_body_in_dom_order},
178 @code{get_loop_body_in_bfs_order}: Enumerates the basic blocks in the
179 loop in depth-first search order in reversed CFG, ordered by dominance
180 relation, and breath-first search order, respectively.
181 @item @code{single_exit}: Returns the single exit edge of the loop, or
182 @code{NULL} if the loop has more than one exit. You can only use this
183 function if LOOPS_HAVE_MARKED_SINGLE_EXITS property is used.
184 @item @code{get_loop_exit_edges}: Enumerates the exit edges of a loop.
185 @item @code{just_once_each_iteration_p}: Returns true if the basic block
186 is executed exactly once during each iteration of a loop (that is, it
187 does not belong to a sub-loop, and it dominates the latch of the loop).
190 @node Loop manipulation
191 @section Loop manipulation
192 @cindex Loop manipulation
194 The loops tree can be manipulated using the following functions:
197 @item @code{flow_loop_tree_node_add}: Adds a node to the tree.
198 @item @code{flow_loop_tree_node_remove}: Removes a node from the tree.
199 @item @code{add_bb_to_loop}: Adds a basic block to a loop.
200 @item @code{remove_bb_from_loops}: Removes a basic block from loops.
203 Most low-level CFG functions update loops automatically. The following
204 functions handle some more complicated cases of CFG manipulations:
207 @item @code{remove_path}: Removes an edge and all blocks it dominates.
208 @item @code{split_loop_exit_edge}: Splits exit edge of the loop,
209 ensuring that PHI node arguments remain in the loop (this ensures that
210 loop-closed SSA form is preserved). Only useful on GIMPLE.
213 Finally, there are some higher-level loop transformations implemented.
214 While some of them are written so that they should work on non-innermost
215 loops, they are mostly untested in that case, and at the moment, they
216 are only reliable for the innermost loops:
219 @item @code{create_iv}: Creates a new induction variable. Only works on
220 GIMPLE. @code{standard_iv_increment_position} can be used to find a
221 suitable place for the iv increment.
222 @item @code{duplicate_loop_to_header_edge},
223 @code{tree_duplicate_loop_to_header_edge}: These functions (on RTL and
224 on GIMPLE) duplicate the body of the loop prescribed number of times on
225 one of the edges entering loop header, thus performing either loop
226 unrolling or loop peeling. @code{can_duplicate_loop_p}
227 (@code{can_unroll_loop_p} on GIMPLE) must be true for the duplicated
229 @item @code{loop_version}, @code{tree_ssa_loop_version}: These function
230 create a copy of a loop, and a branch before them that selects one of
231 them depending on the prescribed condition. This is useful for
232 optimizations that need to verify some assumptions in runtime (one of
233 the copies of the loop is usually left unchanged, while the other one is
234 transformed in some way).
235 @item @code{tree_unroll_loop}: Unrolls the loop, including peeling the
236 extra iterations to make the number of iterations divisible by unroll
237 factor, updating the exit condition, and removing the exits that now
238 cannot be taken. Works only on GIMPLE.
242 @section Loop-closed SSA form
244 @cindex Loop-closed SSA form
246 Throughout the loop optimizations on tree level, one extra condition is
247 enforced on the SSA form: No SSA name is used outside of the loop in
248 that it is defined. The SSA form satisfying this condition is called
249 ``loop-closed SSA form'' -- LCSSA. To enforce LCSSA, PHI nodes must be
250 created at the exits of the loops for the SSA names that are used
251 outside of them. Only the real operands (not virtual SSA names) are
252 held in LCSSA, in order to save memory.
254 There are various benefits of LCSSA:
257 @item Many optimizations (value range analysis, final value
258 replacement) are interested in the values that are defined in the loop
259 and used outside of it, i.e., exactly those for that we create new PHI
261 @item In induction variable analysis, it is not necessary to specify the
262 loop in that the analysis should be performed -- the scalar evolution
263 analysis always returns the results with respect to the loop in that the
265 @item It makes updating of SSA form during loop transformations simpler.
266 Without LCSSA, operations like loop unrolling may force creation of PHI
267 nodes arbitrarily far from the loop, while in LCSSA, the SSA form can be
268 updated locally. However, since we only keep real operands in LCSSA, we
269 cannot use this advantage (we could have local updating of real
270 operands, but it is not much more efficient than to use generic SSA form
271 updating for it as well; the amount of changes to SSA is the same).
274 However, it also means LCSSA must be updated. This is usually
275 straightforward, unless you create a new value in loop and use it
276 outside, or unless you manipulate loop exit edges (functions are
277 provided to make these manipulations simple).
278 @code{rewrite_into_loop_closed_ssa} is used to rewrite SSA form to
279 LCSSA, and @code{verify_loop_closed_ssa} to check that the invariant of
282 @node Scalar evolutions
283 @section Scalar evolutions
284 @cindex Scalar evolutions
285 @cindex IV analysis on GIMPLE
287 Scalar evolutions (SCEV) are used to represent results of induction
288 variable analysis on GIMPLE. They enable us to represent variables with
289 complicated behavior in a simple and consistent way (we only use it to
290 express values of polynomial induction variables, but it is possible to
291 extend it). The interfaces to SCEV analysis are declared in
292 @file{tree-scalar-evolution.h}. To use scalar evolutions analysis,
293 @code{scev_initialize} must be used. To stop using SCEV,
294 @code{scev_finalize} should be used. SCEV analysis caches results in
295 order to save time and memory. This cache however is made invalid by
296 most of the loop transformations, including removal of code. If such a
297 transformation is performed, @code{scev_reset} must be called to clean
300 Given an SSA name, its behavior in loops can be analyzed using the
301 @code{analyze_scalar_evolution} function. The returned SCEV however
302 does not have to be fully analyzed and it may contain references to
303 other SSA names defined in the loop. To resolve these (potentially
304 recursive) references, @code{instantiate_parameters} or
305 @code{resolve_mixers} functions must be used.
306 @code{instantiate_parameters} is useful when you use the results of SCEV
307 only for some analysis, and when you work with whole nest of loops at
308 once. It will try replacing all SSA names by their SCEV in all loops,
309 including the super-loops of the current loop, thus providing a complete
310 information about the behavior of the variable in the loop nest.
311 @code{resolve_mixers} is useful if you work with only one loop at a
312 time, and if you possibly need to create code based on the value of the
313 induction variable. It will only resolve the SSA names defined in the
314 current loop, leaving the SSA names defined outside unchanged, even if
315 their evolution in the outer loops is known.
317 The SCEV is a normal tree expression, except for the fact that it may
318 contain several special tree nodes. One of them is
319 @code{SCEV_NOT_KNOWN}, used for SSA names whose value cannot be
320 expressed. The other one is @code{POLYNOMIAL_CHREC}. Polynomial chrec
321 has three arguments -- base, step and loop (both base and step may
322 contain further polynomial chrecs). Type of the expression and of base
323 and step must be the same. A variable has evolution
324 @code{POLYNOMIAL_CHREC(base, step, loop)} if it is (in the specified
325 loop) equivalent to @code{x_1} in the following example
330 x_1 = phi (base, x_2);
335 Note that this includes the language restrictions on the operations.
336 For example, if we compile C code and @code{x} has signed type, then the
337 overflow in addition would cause undefined behavior, and we may assume
338 that this does not happen. Hence, the value with this SCEV cannot
339 overflow (which restricts the number of iterations of such a loop).
341 In many cases, one wants to restrict the attention just to affine
342 induction variables. In this case, the extra expressive power of SCEV
343 is not useful, and may complicate the optimizations. In this case,
344 @code{simple_iv} function may be used to analyze a value -- the result
345 is a loop-invariant base and step.
348 @section IV analysis on RTL
349 @cindex IV analysis on RTL
351 The induction variable on RTL is simple and only allows analysis of
352 affine induction variables, and only in one loop at once. The interface
353 is declared in @file{cfgloop.h}. Before analyzing induction variables
354 in a loop L, @code{iv_analysis_loop_init} function must be called on L.
355 After the analysis (possibly calling @code{iv_analysis_loop_init} for
356 several loops) is finished, @code{iv_analysis_done} should be called.
357 The following functions can be used to access the results of the
361 @item @code{iv_analyze}: Analyzes a single register used in the given
362 insn. If no use of the register in this insn is found, the following
363 insns are scanned, so that this function can be called on the insn
364 returned by get_condition.
365 @item @code{iv_analyze_result}: Analyzes result of the assignment in the
367 @item @code{iv_analyze_expr}: Analyzes a more complicated expression.
368 All its operands are analyzed by @code{iv_analyze}, and hence they must
369 be used in the specified insn or one of the following insns.
372 The description of the induction variable is provided in @code{struct
373 rtx_iv}. In order to handle subregs, the representation is a bit
374 complicated; if the value of the @code{extend} field is not
375 @code{UNKNOWN}, the value of the induction variable in the i-th
379 delta + mult * extend_@{extend_mode@} (subreg_@{mode@} (base + i * step)),
382 with the following exception: if @code{first_special} is true, then the
383 value in the first iteration (when @code{i} is zero) is @code{delta +
384 mult * base}. However, if @code{extend} is equal to @code{UNKNOWN},
385 then @code{first_special} must be false, @code{delta} 0, @code{mult} 1
386 and the value in the i-th iteration is
389 subreg_@{mode@} (base + i * step)
392 The function @code{get_iv_value} can be used to perform these
395 @node Number of iterations
396 @section Number of iterations analysis
397 @cindex Number of iterations analysis
399 Both on GIMPLE and on RTL, there are functions available to determine
400 the number of iterations of a loop, with a similar interface. The
401 number of iterations of a loop in GCC is defined as the number of
402 executions of the loop latch. In many cases, it is not possible to
403 determine the number of iterations unconditionally -- the determined
404 number is correct only if some assumptions are satisfied. The analysis
405 tries to verify these conditions using the information contained in the
406 program; if it fails, the conditions are returned together with the
407 result. The following information and conditions are provided by the
411 @item @code{assumptions}: If this condition is false, the rest of
412 the information is invalid.
413 @item @code{noloop_assumptions} on RTL, @code{may_be_zero} on GIMPLE: If
414 this condition is true, the loop exits in the first iteration.
415 @item @code{infinite}: If this condition is true, the loop is infinite.
416 This condition is only available on RTL. On GIMPLE, conditions for
417 finiteness of the loop are included in @code{assumptions}.
418 @item @code{niter_expr} on RTL, @code{niter} on GIMPLE: The expression
419 that gives number of iterations. The number of iterations is defined as
420 the number of executions of the loop latch.
423 Both on GIMPLE and on RTL, it necessary for the induction variable
424 analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).
425 On GIMPLE, the results are stored to @code{struct tree_niter_desc}
426 structure. Number of iterations before the loop is exited through a
427 given exit can be determined using @code{number_of_iterations_exit}
428 function. On RTL, the results are returned in @code{struct niter_desc}
429 structure. The corresponding function is named
430 @code{check_simple_exit}. There are also functions that pass through
431 all the exits of a loop and try to find one with easy to determine
432 number of iterations -- @code{find_loop_niter} on GIMPLE and
433 @code{find_simple_exit} on RTL. Finally, there are functions that
434 provide the same information, but additionally cache it, so that
435 repeated calls to number of iterations are not so costly --
436 @code{number_of_latch_executions} on GIMPLE and @code{get_simple_loop_desc}
439 Note that some of these functions may behave slightly differently than
440 others -- some of them return only the expression for the number of
441 iterations, and fail if there are some assumptions. The function
442 @code{number_of_latch_executions} works only for single-exit loops.
443 The function @code{number_of_cond_exit_executions} can be used to
444 determine number of executions of the exit condition of a single-exit
445 loop (i.e., the @code{number_of_latch_executions} increased by one).
447 @node Dependency analysis
448 @section Data Dependency Analysis
449 @cindex Data Dependency Analysis
451 The code for the data dependence analysis can be found in
452 @file{tree-data-ref.c} and its interface and data structures are
453 described in @file{tree-data-ref.h}. The function that computes the
454 data dependences for all the array and pointer references for a given
455 loop is @code{compute_data_dependences_for_loop}. This function is
456 currently used by the linear loop transform and the vectorization
457 passes. Before calling this function, one has to allocate two vectors:
458 a first vector will contain the set of data references that are
459 contained in the analyzed loop body, and the second vector will contain
460 the dependence relations between the data references. Thus if the
461 vector of data references is of size @code{n}, the vector containing the
462 dependence relations will contain @code{n*n} elements. However if the
463 analyzed loop contains side effects, such as calls that potentially can
464 interfere with the data references in the current analyzed loop, the
465 analysis stops while scanning the loop body for data references, and
466 inserts a single @code{chrec_dont_know} in the dependence relation
469 The data references are discovered in a particular order during the
470 scanning of the loop body: the loop body is analyzed in execution order,
471 and the data references of each statement are pushed at the end of the
472 data reference array. Two data references syntactically occur in the
473 program in the same order as in the array of data references. This
474 syntactic order is important in some classical data dependence tests,
475 and mapping this order to the elements of this array avoids costly
476 queries to the loop body representation.
478 Three types of data references are currently handled: ARRAY_REF,
479 INDIRECT_REF and COMPONENT_REF. The data structure for the data reference
480 is @code{data_reference}, where @code{data_reference_p} is a name of a
481 pointer to the data reference structure. The structure contains the
485 @item @code{base_object_info}: Provides information about the base object
486 of the data reference and its access functions. These access functions
487 represent the evolution of the data reference in the loop relative to
488 its base, in keeping with the classical meaning of the data reference
489 access function for the support of arrays. For example, for a reference
490 @code{a.b[i][j]}, the base object is @code{a.b} and the access functions,
491 one for each array subscript, are:
492 @code{@{i_init, + i_step@}_1, @{j_init, +, j_step@}_2}.
494 @item @code{first_location_in_loop}: Provides information about the first
495 location accessed by the data reference in the loop and about the access
496 function used to represent evolution relative to this location. This data
497 is used to support pointers, and is not used for arrays (for which we
498 have base objects). Pointer accesses are represented as a one-dimensional
499 access that starts from the first location accessed in the loop. For
505 *((int *)p + i + j) = a[i][j];
508 The access function of the pointer access is @code{@{0, + 4B@}_for2}
509 relative to @code{p + i}. The access functions of the array are
510 @code{@{i_init, + i_step@}_for1} and @code{@{j_init, +, j_step@}_for2}
511 relative to @code{a}.
513 Usually, the object the pointer refers to is either unknown, or we can't
514 prove that the access is confined to the boundaries of a certain object.
516 Two data references can be compared only if at least one of these two
517 representations has all its fields filled for both data references.
519 The current strategy for data dependence tests is as follows:
520 If both @code{a} and @code{b} are represented as arrays, compare
521 @code{a.base_object} and @code{b.base_object};
522 if they are equal, apply dependence tests (use access functions based on
524 Else if both @code{a} and @code{b} are represented as pointers, compare
525 @code{a.first_location} and @code{b.first_location};
526 if they are equal, apply dependence tests (use access functions based on
528 However, if @code{a} and @code{b} are represented differently, only try
529 to prove that the bases are definitely different.
531 @item Aliasing information.
532 @item Alignment information.
535 The structure describing the relation between two data references is
536 @code{data_dependence_relation} and the shorter name for a pointer to
537 such a structure is @code{ddr_p}. This structure contains:
540 @item a pointer to each data reference,
541 @item a tree node @code{are_dependent} that is set to @code{chrec_known}
542 if the analysis has proved that there is no dependence between these two
543 data references, @code{chrec_dont_know} if the analysis was not able to
544 determine any useful result and potentially there could exist a
545 dependence between these data references, and @code{are_dependent} is
546 set to @code{NULL_TREE} if there exist a dependence relation between the
547 data references, and the description of this dependence relation is
548 given in the @code{subscripts}, @code{dir_vects}, and @code{dist_vects}
550 @item a boolean that determines whether the dependence relation can be
551 represented by a classical distance vector,
552 @item an array @code{subscripts} that contains a description of each
553 subscript of the data references. Given two array accesses a
554 subscript is the tuple composed of the access functions for a given
555 dimension. For example, given @code{A[f1][f2][f3]} and
556 @code{B[g1][g2][g3]}, there are three subscripts: @code{(f1, g1), (f2,
558 @item two arrays @code{dir_vects} and @code{dist_vects} that contain
559 classical representations of the data dependences under the form of
560 direction and distance dependence vectors,
561 @item an array of loops @code{loop_nest} that contains the loops to
562 which the distance and direction vectors refer to.
565 Several functions for pretty printing the information extracted by the
566 data dependence analysis are available: @code{dump_ddrs} prints with a
567 maximum verbosity the details of a data dependence relations array,
568 @code{dump_dist_dir_vectors} prints only the classical distance and
569 direction vectors for a data dependence relations array, and
570 @code{dump_data_references} prints the details of the data references
571 contained in a data reference array.
574 @section Linear loop transformations framework
575 @cindex Linear loop transformations framework
577 Lambda is a framework that allows transformations of loops using
578 non-singular matrix based transformations of the iteration space and
579 loop bounds. This allows compositions of skewing, scaling, interchange,
580 and reversal transformations. These transformations are often used to
581 improve cache behavior or remove inner loop dependencies to allow
582 parallelization and vectorization to take place.
584 To perform these transformations, Lambda requires that the loopnest be
585 converted into a internal form that can be matrix transformed easily.
586 To do this conversion, the function
587 @code{gcc_loopnest_to_lambda_loopnest} is provided. If the loop cannot
588 be transformed using lambda, this function will return NULL.
590 Once a @code{lambda_loopnest} is obtained from the conversion function,
591 it can be transformed by using @code{lambda_loopnest_transform}, which
592 takes a transformation matrix to apply. Note that it is up to the
593 caller to verify that the transformation matrix is legal to apply to the
594 loop (dependence respecting, etc). Lambda simply applies whatever
595 matrix it is told to provide. It can be extended to make legal matrices
596 out of any non-singular matrix, but this is not currently implemented.
597 Legality of a matrix for a given loopnest can be verified using
598 @code{lambda_transform_legal_p}.
600 Given a transformed loopnest, conversion back into gcc IR is done by
601 @code{lambda_loopnest_to_gcc_loopnest}. This function will modify the
602 loops so that they match the transformed loopnest.