Lines Matching full:loop
92 * Loop Analysis and Representation:: Analysis and representation of loops
3411 This pass transforms tail recursion into a loop. It is located in
3438 * Loop optimization
3440 The main driver of the pass is placed in `tree-ssa-loop.c' and
3445 Loop invariant motion. This pass moves only invariants that would
3449 loop, so that we can use just trivial invariantness analysis in
3450 loop unswitching. The pass also includes store motion. The pass
3451 is implemented in `tree-ssa-loop-im.c'.
3454 counter for number of iterations of the loop and replaces the exit
3455 condition of the loop using it, in case when a complicated
3458 pass is implemented in `tree-ssa-loop-ivcanon.c'.
3463 The pass is implemented in `tree-ssa-loop-ivopts.c'.
3465 Loop unswitching. This pass moves the conditional jumps that are
3467 loop is created for each possible outcome of conditional jump(s).
3468 The pass is implemented in `tree-ssa-loop-unswitch.c'. This pass
3469 loop unswitching in
3470 `loop-unswitch.c', but currently the rtl-level pass is not
3475 `tree-ssa-loop-manip.c', `cfgloop.c', `cfgloopanal.c' and
3479 types instead of scalar types. Data parallelism across loop
3482 Depending on available target support the loop is conceptually
3486 vector operation. Additional loop transformations such as peeling
3488 and to align the memory accesses in the loop. The pass is
3497 basic blocks in one big block. The idea is to present loop in such
3630 * Loop invariant motion
3632 This pass removes expensive loop-invariant computations out of
3633 loops. The pass is located in `tree-ssa-loop.c' and described by
3636 * Loop nest optimizations
3638 This is a family of loop transformations that works on loop nests.
3639 It includes loop interchange, scaling, skewing and reversal and
3642 optimizations such as loop parallelization and vectorization. The
3643 pass is located in `tree-loop-linear.c' and described by
3649 in `tree-ssa-loop-ivcanon.c' and described by `pass_empty_loop'.
3654 is located in `tree-ssa-loop-ivcanon.c' and described by
3660 loops. The pass is located in `tree-ssa-loop-prefetch.c' and
3737 loops--that is left to the loop optimization pass. If MR PRE
3741 Knoop, Ruthing, and Steffen. LCM based GCSE also does loop
3748 * Loop optimization
3750 This pass performs several loop related optimizations. The source
3751 files `cfgloopanal.c' and `cfgloopmanip.c' contain generic loop
3753 of loop structures is handled by `loop-init.c'. A loop invariant
3754 motion pass is implemented in `loop-invariant.c'. Basic block
3756 are implemented in `loop-unswitch.c' and `loop-unroll.c'.
3758 machine-dependent instructions is handled by `loop-doloop.c'.
5228 loop will have a body, which is itself a statement. If the substatement
5332 Used to represent a `do' loop. The body of the loop is given by
5333 `DO_BODY' while the termination condition for the loop is given by
5348 initialization statement for the loop. The `FOR_COND' is the
5350 right before the `FOR_COND' on each loop
5351 expression increments a counter. The body of the loop is given by
5439 Used to represent a `while' loop. The `WHILE_COND' is the
5440 termination condition for the loop. See the documentation for an
5444 The `WHILE_BODY' is the body of the loop.
6001 represents the body of the loop. It should be executed forever,
6007 nonzero, then the loop should be exited. An `EXIT_EXPR' will only
6137 Operand `OMP_FOR_BODY' contains the loop body.
6142 Operand `OMP_FOR_INIT' is the loop initialization code of the form
6145 Operand `OMP_FOR_COND' is the loop conditional expression of the
6148 Operand `OMP_FOR_INCR' is the loop index increment of the form
6154 before the start of loop body.
6156 The loop index variable `VAR' must be a signed integer variable,
6158 and the increment expression `INCR' are required to be loop
6195 executed in the sequential order dictated by the loop index
6215 place where the code needs to loop to the next iteration (in the
6233 compare-and-swap loop is attempted. If that also fails, a regular
6257 File: gccint.info, Node: Tree SSA, Next: Loop Analysis and Representation, Prev: Control Flow, Up: Top
6808 loop:;
6820 goto loop;
7155 matching 'flags'. This actually executes a loop to perform the
7186 in, and an ssa_op_iter structure which serves as the loop
7335 loop is terminated early. The macro `BREAK_FROM_IMM_USE_SAFE' is
7350 break from the loop without using this macro. It is safe to simply
7367 utilizes a loop to count the uses.
7391 This is done with a simple loop over the instruction stream:
7885 File: gccint.info, Node: Loop Analysis and Representation, Next: Machine Desc, Prev: Tree SSA, Up: Top
7893 RTL, as well as the interfaces to loop-related analyses (induction
7898 * Loop representation:: Representation and analysis of loops.
7899 * Loop querying:: Getting information about loops.
7900 * Loop manipulation:: Loop manipulation functions.
7901 * LCSSA:: Loop-closed SSA form.
7903 * loop-iv:: Induction variables on RTL.
7906 * Lambda:: Linear loop transformations framework.
7909 File: gccint.info, Node: Loop representation, Next: Loop querying, Up: Loop Analysis and Representation
7911 11.1 Loop representation
7917 the moment, loop structures are analyzed and this information is
7922 In general, a natural loop has one entry block (header) and possibly
7924 the loop. Loops with several latches may appear if several loops share
7925 a single header, or if there is a branching in the middle of the loop.
7927 single latch. During loop analysis, headers of such loops are split and
7930 the latches correspond to sub-loops or to control flow in a single loop.
7935 Body of the loop is the set of blocks that are dominated by its header,
7938 loops immediately contained inside loop L are the children of L in the
7940 root of this tree is a fake loop that contains all blocks in the
7941 function. Each of the loops is represented in a `struct loop'
7942 structure. Each loop is assigned an index (`num' field of the `struct
7943 loop' structure), and the pointer to the loop is stored in the
7945 Index of a sub-loop is always greater than the index of its super-loop.
7947 entries in the `parray' created by deleting loops. The index of a loop
7951 Each basic block contains the reference to the innermost loop it
7955 contain the `struct loops' structure, especially if the loop structures
7956 are updated throughout several passes. Many of the loop manipulation
7961 bitmask. These flags specify what other properties of the loop
7965 way that each loop has only one entry edge, and additionally, the
7968 loop, and ensures that the entry edge of the loop leads from its
7969 immediate super-loop.
7972 the latch block of each loop to have only one successor. This
7973 ensures that the latch of the loop does not belong to any of its
7975 easier. Most of the loop manipulation functions assume that the
7977 loop without any control flow inside and with one exit consists of
7986 such a loop, if they lead to/from this region).
7988 * `LOOPS_HAVE_MARKED_SINGLE_EXITS': If a loop has exactly one exit
7989 edge, this edge is stored in `single_exit' field of the loop
7999 The CFG manipulation functions in general do not update loop
8006 File: gccint.info, Node: Loop querying, Next: Loop manipulation, Prev: Loop representation, Up: Loop Analysis and Representation
8008 11.2 Loop querying
8014 innermost loop to that the block belongs. The most useful fields of
8015 loop structure (that are kept up-to-date at all times) are:
8017 * `header', `latch': Header and latch basic blocks of the loop.
8019 * `num_nodes': Number of basic blocks in the loop (including the
8022 * `depth': The depth of the loop in the loops tree, i.e., the number
8023 of super-loops of the loop.
8025 * `outer', `inner', `next': The super-loop, the first sub-loop, and
8026 the sibling of the loop in the loops tree.
8028 * `single_exit': The exit edge of the loop, if the loop has exactly
8032 There are other fields in the loop structures, many of them used only
8036 The most important functions to query loop structures are:
8040 * `verify_loop_structure': Checks consistency of the loop structures.
8042 * `loop_latch_edge': Returns the latch edge of a loop.
8045 preheader edge of a loop.
8047 * `flow_loop_nested_p': Tests whether loop is a sub-loop of another
8048 loop.
8051 loop (including its sub-loops).
8053 * `find_common_loop': Finds the common super-loop of two loops.
8055 * `superloop_at_depth': Returns the super-loop of a loop with the
8059 insns in the loop, on GIMPLE and on RTL.
8061 * `loop_exit_edge_p': Tests whether edge is an exit from a loop.
8068 loop in depth-first search order in reversed CFG, ordered by
8071 * `get_loop_exit_edges': Enumerates the exit edges of a loop.
8074 executed exactly once during each iteration of a loop (that is, it
8075 does not belong to a sub-loop, and it dominates the latch of the
8076 loop).
8079 File: gccint.info, Node: Loop manipulation, Next: LCSSA, Prev: Loop querying, Up: Loop Analysis and Representation
8081 11.3 Loop manipulation
8090 * `add_bb_to_loop': Adds a basic block to a loop.
8095 update loop structures are provided:
8110 * `split_loop_exit_edge': Splits exit edge of the loop, ensuring
8111 that PHI node arguments remain in the loop (this ensures that
8112 loop-closed SSA form is preserved). Only useful on GIMPLE.
8114 Finally, there are some higher-level loop transformations implemented.
8125 on GIMPLE) duplicate the body of the loop prescribed number of
8126 times on one of the edges entering loop header, thus performing
8127 either loop unrolling or loop peeling. `can_duplicate_loop_p'
8129 loop.
8132 copy of a loop, and a branch before them that selects one of them
8135 of the copies of the loop is usually left unchanged, while the
8138 * `tree_unroll_loop': Unrolls the loop, including peeling the extra
8144 File: gccint.info, Node: LCSSA, Next: Scalar evolutions, Prev: Loop manipulation, Up: Loop Analysis and Representation
8146 11.4 Loop-closed SSA form
8149 Throughout the loop optimizations on tree level, one extra condition is
8150 enforced on the SSA form: No SSA name is used outside of the loop in
8152 "loop-closed SSA form" - LCSSA. To enforce LCSSA, PHI nodes must be
8160 are interested in the values that are defined in the loop and used
8165 loop in that the analysis should be performed - the scalar
8167 loop in that the SSA name is defined.
8169 * It makes updating of SSA form during loop transformations simpler.
8170 Without LCSSA, operations like loop unrolling may force creation
8171 of PHI nodes arbitrarily far from the loop, while in LCSSA, the
8179 straightforward, unless you create a new value in loop and use it
8180 outside, or unless you manipulate loop exit edges (functions are
8187 File: gccint.info, Node: Scalar evolutions, Next: loop-iv, Prev: LCSSA, Up: Loop Analysis and Representation
8200 memory. This cache however is made invalid by most of the loop
8207 SSA names defined in the loop. To resolve these (potentially
8212 their SCEV in all loops, including the super-loops of the current loop,
8214 variable in the loop nest. `resolve_mixers' is useful if you work with
8215 only one loop at a time, and if you possibly need to create code based
8217 names defined in the current loop, leaving the SSA names defined
8224 and loop (both base and step may contain further polynomial chrecs).
8226 variable has evolution `POLYNOMIAL_CHREC(base, step, loop)' if it is
8227 (in the specified loop) equivalent to `x_1' in the following example
8239 overflow (which restricts the number of iterations of such a loop).
8245 loop-invariant base and step.
8248 File: gccint.info, Node: loop-iv, Next: Number of iterations, Prev: Scalar evolutions, Up: Loop Analysis and Representation
8254 affine induction variables, and only in one loop at once. The interface
8256 loop L, `iv_analysis_loop_init' function must be called on L. After
8291 File: gccint.info, Node: Number of iterations, Next: Dependency analysis, Prev: loop-iv, Up: Loop Analysis and Representation
8297 the number of iterations of a loop, with a similar interface. In many
8309 condition is true, the loop exits in the first iteration.
8311 * `infinite': If this condition is true, the loop is infinite. This
8313 finiteness of the loop are included in `assumptions'.
8317 number of executions of the loop latch.
8320 analysis framework to be initialized (SCEV on GIMPLE, loop-iv on RTL).
8322 structure. Number of iterations before the loop is exited through a
8326 There are also functions that pass through all the exits of a loop and
8340 exit statement, not of the loop latch).
8343 File: gccint.info, Node: Dependency analysis, Next: Lambda, Prev: Number of iterations, Up: Loop Analysis and Representation
8351 for all the array and pointer references for a given loop is
8353 by the linear loop transform and the vectorization passes. Before
8356 analyzed loop body, and the second vector will contain the dependence
8359 relations will contain `n*n' elements. However if the analyzed loop
8361 with the data references in the current analyzed loop, the analysis
8362 stops while scanning the loop body for data references, and inserts a
8366 scanning of the loop body: the loop body is analyzed in execution order,
8372 queries to the loop body representation.
8382 represent the evolution of the data reference in the loop relative
8390 location accessed by the data reference in the loop and about the
8395 location accessed in the loop. For example:
8469 File: gccint.info, Node: Lambda, Prev: Dependency analysis, Up: Loop Analysis and Representation
8471 11.9 Linear loop transformations framework
8476 loop bounds. This allows compositions of skewing, scaling, interchange,
8478 improve cache behavior or remove inner loop dependencies to allow
8484 is provided. If the loop cannot be transformed using lambda, this
8490 verify that the transformation matrix is legal to apply to the loop
9213 contained within the test expression of some loop.
9219 outside the innermost loop containing the insn in which the
11096 and end of a `while' or `for' loop. They enable the loop
11100 Appears at the place in a loop that `continue' statements
11104 This note indicates the place in a loop where the exit test
11107 the loop when considering loop invariants.
11333 common subexpression elimination and loop optimization) to tell
11364 Loop optimization uses this note to treat such a sequence as a
11932 both decrease (for instance by loop unrolling) or grow (for instance by
12169 File: gccint.info, Node: Machine Desc, Next: Target Macros, Prev: Loop Analysis and Representation, Up: Top
15998 typically for loops reversed by the loop optimizer when strength
16005 1 is the number of loop iterations as a `const_int' or
16009 `const_int' (an innermost loop has a value of 1); operand 4 is the
16014 with low-overhead looping instructions as the loop optimizer will
16639 provide low-overhead loop support. For example, the TI TMS320C3x/C4x
16641 mark the top and end of a loop and to count the number of loop
16651 loop optimizer, using information collected during strength reduction,
16652 to reverse a loop to count down to zero. Some targets also require the
16653 loop optimizer to add a `REG_NONNEG' note to indicate that the
16655 performs a signed loop termination test. For example, the 68000 uses a
16694 `doloop_end', are emitted by the loop optimizer for certain
16695 well-behaved loops with a finite number of loop iterations using
16704 emitted at the top of the loop (e.g., the TMS320C3x/C4x DSPs). Emitting
16705 the true RTL for a looping instruction at the top of the loop can cause
16707 emitted at the end of the loop. The machine dependent reorg pass checks
16709 top of the loop, where it inserts the true looping insn (provided there
16710 are no instructions in the loop which would cause problems). Any
16717 and the `doloop_end' patterns is that the loop optimizer allocates an
16719 This pseudo register cannot be used within the loop (i.e., general
16721 the loop induction variable may become redundant and removed by the
27292 inappropriate on targets that would require a loop. By default,
27912 low-overhead loop, otherwise return a string why doloop could not
27918 By default, the RTL loop optimizer does not use a present doloop
29944 loop optimizations, etc.
30011 * Zdenek Dvorak for a new loop unroller and various fixes.
30017 loop changes, doing the entire AIX port of libstdc++ with his bare
30096 the c30/c40 ports functional. Lots of loop and unroll
30105 work, loop opts, and generally fixing lots of old problems we've
30393 * Joern Rennecke for maintaining the sh port, loop, regmove & reload
30583 on, strength reduction and other loop optimizations.
32760 * IV analysis on RTL: loop-iv. (line 6)
32840 * Linear loop transformations framework: Lambda. (line 6)
32868 * Loop analysis: Loop representation.
32870 * Loop manipulation: Loop manipulation. (line 6)
32871 * Loop querying: Loop querying. (line 6)
32872 * Loop representation: Loop representation.
32874 * Loop-closed SSA form: LCSSA. (line 6)
34413 Node: Loop Analysis and Representation332287
34414 Node: Loop representation333283
34415 Node: Loop querying338550
34416 Node: Loop manipulation341336
34419 Node: loop-iv349430
