Lines Matching defs:loop
24 This pass analyzes the evolution of scalar variables in loop
26 and on the loop hierarchy tree. This algorithm is not based on
35 when entering in the loop_1 and has a step 2 in this loop, in other
62 - When the definition is a loop-phi-node: determine its initial
63 condition, that is the SSA edge defined in an outer loop, and
65 in the body of the loop. Follow the inner edges until ending on
66 another loop-phi-node of the same analyzed loop. If the reached
67 loop-phi-node is not the starting loop-phi-node, then we keep
69 loop-phi-node is the same as the starting one, then we compute a
91 Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92 c)", where the initial condition is "a", and the inner loop edge
96 loop-phi-node). The update edge is followed to the end of the
97 loop, and until reaching again the starting loop-phi-node: b -> c
99 which we compute the stride in the loop: in this example it is
108 and take the smallest iteration number for which the loop is
109 exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110 there are 8 iterations. In terms of loop normalization, we have
112 and all the other analyzed scalars of the loop are defined in
140 the SSA edge into the loop's body: "a -> b". "b" is an inner
141 loop-phi-node, and its analysis as in Example 1, gives:
147 + 2", and then on the starting loop-phi-node "a". From this point,
148 the loop stride is computed: back on "c = a + 2" we get a "+2" in
149 the loop_1, then on the loop-phi-node "b" we compute the overall
150 effect of the inner loop that is "b = c + 30", and we get a "+30"
212 Note that this syntax is close to the syntax of the loop-phi-node:
307 #include "tree-ssa-loop-ivopts.h"
308 #include "tree-ssa-loop-manip.h"
309 #include "tree-ssa-loop-niter.h"
310 #include "tree-ssa-loop.h"
321 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
322 static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
433 loop_p def_loop, loop;
440 loop = get_loop (cfun, loop_nb);
445 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
459 /* Return true when PHI is a loop-phi-node. */
465 property: "all the loop-phi-nodes of a loop are contained in the
466 loop's header basic block". */
496 This loop has the same effect as:
501 The overall effect of the loop, "i_0 + 20" in the previous example,
507 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
516 struct loop *inner_loop = get_chrec_loop (evolution_fn);
518 if (inner_loop == loop
519 || flow_loop_nested_p (loop, inner_loop))
533 if (chrec_contains_symbols_defined_in_loop (res, loop->num))
534 res = instantiate_parameters (loop, res);
537 return compute_overall_effect_of_inner_loop (loop, res);
545 else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
640 part for this loop. */
647 struct loop *loop = get_loop (cfun, loop_nb), *chloop;
653 if (chloop == loop
654 || flow_loop_nested_p (chloop, loop))
660 /* When there is no evolution part in this loop, build it. */
661 if (chloop != loop)
683 gcc_assert (flow_loop_nested_p (loop, chloop));
695 /* These nodes do not depend on a loop. */
714 reconstructed the overall tree expression for a loop, there are only
717 1. a = loop-phi (init, a + expr)
718 2. a = loop-phi (init, expr)
721 loop (this is a degree 0 polynomial), or an expression containing
722 other loop-phi definitions (these are higher degree polynomials).
744 that is, there is a loop index "x" that determines the scalar value
745 of the variable during the loop execution. During the first
757 close to the syntax of a loop-phi-node:
765 When EXPR is a constant with respect to the analyzed loop, or in
767 the variable A in the loop is an affine function with an initial
888 loop nests we could analyze. */
890 /* For a loop with a single exit edge, return the COND_EXPR that
895 get_loop_exit_condition (const struct loop *loop)
898 edge exit_edge = single_exit (loop);
932 static t_bool follow_ssa_edge (struct loop *loop, gimple, gphi *,
939 follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
965 (loop->num,
969 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
975 (loop->num,
979 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
996 (loop->num, chrec_convert (type, *evolution_of_loop,
1000 (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1014 (loop->num, chrec_convert (type, *evolution_of_loop,
1018 (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1047 (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1049 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1074 follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
1095 res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
1108 (loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1120 res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1134 res = follow_ssa_edge_binary (loop, at_stmt, type,
1147 res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1165 follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
1177 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1188 res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1194 res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1226 struct loop *loop,
1235 /* Do not follow back edges (they must belong to an irreducible loop, which
1243 return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1258 loop. */
1261 follow_ssa_edge_in_condition_phi (struct loop *loop,
1269 t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1288 res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1302 /* Follow an SSA edge in an inner loop. It computes the overall
1303 effect of the loop, and following the symbolic initial conditions,
1304 it follows the edges in the parent loop. The inner loop is
1308 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1313 struct loop *loop = loop_containing_stmt (loop_phi_node);
1314 tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1316 /* Sometimes, the inner loop is too difficult to analyze, and the
1328 /* Follow the edges that exit the inner loop. */
1330 if (!flow_bb_inside_loop_p (loop, bb))
1338 /* If the path crosses this loop-phi, give up. */
1345 /* Otherwise, compute the overall effect of the inner loop. */
1346 ev = compute_overall_effect_of_inner_loop (loop, ev);
1351 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1355 follow_ssa_edge (struct loop *loop, gimple def, gphi *halting_phi,
1358 struct loop *def_loop;
1378 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1383 the halting_phi to itself in the loop. */
1388 on the evolution of another loop-phi-node, i.e. the
1390 if (def_loop == loop)
1393 /* Inner loop. */
1394 if (flow_loop_nested_p (loop, def_loop))
1396 (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1399 /* Outer loop. */
1403 return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1431 simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1437 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1453 return build_polynomial_chrec (loop->num, init_cond, right);
1470 return build_polynomial_chrec (loop->num, init_cond, right);
1476 function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
1484 struct loop *loop = loop_containing_stmt (loop_phi_node);
1503 /* Select the edges that enter the loop body. */
1505 if (!flow_bb_inside_loop_p (loop, bb))
1516 res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1518 /* If ev_fn has no evolution in the inner loop, and the
1523 && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1546 ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1551 /* When there are multiple back edges of the loop (which in fact never
1566 /* Given a loop-phi-node, return the initial conditions of the
1567 variable on entry of the loop. When the CCP has propagated
1568 constants into the loop-phi-node, the initial condition is
1571 loop, and leaves this task to the on-demand tree reconstructor. */
1578 struct loop *loop = loop_containing_stmt (loop_phi_node);
1594 /* When the branch is oriented to the loop's body, it does
1596 if (flow_bb_inside_loop_p (loop, bb))
1614 /* Ooops -- a loop without an entry??? */
1618 /* During early loop unrolling we do not have fully constant propagated IL.
1628 loop-closed SSA form. */
1647 interpret_loop_phi (struct loop *loop, gphi *loop_phi_node)
1650 struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1653 if (phi_loop != loop)
1655 struct loop *subloop;
1660 subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
1667 /* Otherwise really interpret the loop phi. */
1692 contained in the outermost loop, and whose arguments are already
1696 interpret_condition_phi (struct loop *loop, gphi *condition_phi)
1712 (loop, PHI_ARG_DEF (condition_phi, i));
1722 either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1725 analyze the effect of an inner loop: see interpret_loop_phi. */
1728 interpret_rhs_expr (struct loop *loop, gimple at_stmt,
1740 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1746 return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1774 chrec1 = analyze_scalar_evolution (loop, rhs1);
1775 chrec2 = analyze_scalar_evolution (loop, rhs2);
1778 chrec1 = instantiate_parameters (loop, chrec1);
1779 chrec2 = instantiate_parameters (loop, chrec2);
1784 chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1791 chrec2 = analyze_scalar_evolution (loop, offset);
1793 chrec2 = instantiate_parameters (loop, chrec2);
1802 chrec3 = analyze_scalar_evolution (loop, unitpos);
1804 chrec3 = instantiate_parameters (loop, chrec3);
1813 chrec1 = analyze_scalar_evolution (loop, rhs1);
1814 chrec2 = analyze_scalar_evolution (loop, rhs2);
1817 chrec1 = instantiate_parameters (loop, chrec1);
1818 chrec2 = instantiate_parameters (loop, chrec2);
1823 chrec1 = analyze_scalar_evolution (loop, rhs1);
1824 chrec2 = analyze_scalar_evolution (loop, rhs2);
1831 && ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1836 chrec1 = instantiate_parameters (loop, chrec1);
1837 chrec2 = instantiate_parameters (loop, chrec2);
1844 chrec1 = analyze_scalar_evolution (loop, rhs1);
1845 chrec2 = analyze_scalar_evolution (loop, rhs2);
1853 loop->latch, gimple_bb (at_stmt)))
1857 chrec1 = instantiate_parameters (loop, chrec1);
1858 chrec2 = instantiate_parameters (loop, chrec2);
1865 chrec1 = analyze_scalar_evolution (loop, rhs1);
1873 loop->latch, gimple_bb (at_stmt)))
1877 chrec1 = instantiate_parameters (loop, chrec1);
1886 chrec1 = analyze_scalar_evolution (loop, rhs1);
1888 chrec1 = instantiate_parameters (loop, chrec1);
1895 chrec1 = analyze_scalar_evolution (loop, rhs1);
1896 chrec2 = analyze_scalar_evolution (loop, rhs2);
1904 loop->latch, gimple_bb (at_stmt)))
1908 chrec1 = instantiate_parameters (loop, chrec1);
1909 chrec2 = instantiate_parameters (loop, chrec2);
1932 chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1938 chrec1 = analyze_scalar_evolution (loop, rhs1);
1953 interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
1967 return interpret_rhs_expr (loop, at_stmt, type,
1974 interpret_gimple_assign (struct loop *loop, gimple stmt)
1979 return interpret_rhs_expr (loop, stmt, type,
1997 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1998 struct loop *def_loop,
2019 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
2024 struct loop *def_loop;
2026 if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
2030 return interpret_expr (loop, NULL, var);
2037 || !flow_bb_inside_loop_p (loop, bb))
2046 if (loop != bb->loop_father)
2048 (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
2053 if (loop != def_loop)
2056 res = compute_scalar_evolution_in_loop (loop, def_loop, res);
2064 res = interpret_gimple_assign (loop, def);
2069 res = interpret_loop_phi (loop, as_a <gphi *> (def));
2071 res = interpret_condition_phi (loop, as_a <gphi *> (def));
2085 if (loop == def_loop)
2086 set_scalar_evolution (block_before_loop (loop), var, res);
2092 LOOP. LOOP is the loop in which the variable is used.
2099 loop_p loop = loop_containing_stmt (stmt);
2100 tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2101 tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2105 analyze_scalar_evolution (struct loop *loop, tree var)
2112 fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2118 res = get_scalar_evolution (block_before_loop (loop), var);
2119 res = analyze_scalar_evolution_1 (loop, var, res);
2130 analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2132 return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2145 for (i = 0; i < 100; i++) -- loop 1
2147 for (j = 0; j < 100; j++) -- loop 2
2154 for (t = 0; t < 100; t++) -- loop 3
2166 usage in loop 3 or loop 2, hence
2172 Similarly for their evolutions with respect to loop 1. The values of K2
2173 in the use in loop 2 vary independently on loop 1, thus we cannot express
2174 the evolution with respect to loop 1:
2180 The value of k2 in the use in loop 1 is known, though:
2186 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2204 and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
2206 value in loop 3.
2208 Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2209 each time checking that there is no evolution in the inner loop. */
2224 /* If the value of the use changes in the inner loop, we cannot express
2225 its value in the outer loop (we might try to return interval chrec,
2317 struct loop *loop;
2326 loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2327 exit = single_exit (loop);
2341 static tree instantiate_scev_r (basic_block, struct loop *, struct loop *,
2360 struct loop *evolution_loop, struct loop *inner_loop,
2366 struct loop *def_loop;
2369 /* A parameter (or loop invariant and we do not want to include
2404 /* Don't instantiate loop-closed-ssa phi nodes. */
2415 variable is not used after the loop: try to still compute the
2416 value of the variable when exiting the loop. */
2419 loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2420 res = analyze_scalar_evolution (loop, chrec);
2421 res = compute_overall_effect_of_inner_loop (loop, res);
2436 /* ??? We could try to compute the overall effect of the loop here. */
2465 struct loop *evolution_loop, struct loop *,
2509 struct loop *evolution_loop, struct loop *inner_loop,
2567 struct loop *evolution_loop, struct loop *inner_loop,
2604 struct loop *evolution_loop, struct loop *inner_loop,
2652 struct loop *evolution_loop, struct loop *inner_loop,
2702 struct loop *evolution_loop, struct loop *inner_loop,
2750 struct loop *evolution_loop, struct loop *inner_loop,
2790 struct loop *evolution_loop, struct loop *inner_loop,
2823 struct loop *evolution_loop, struct loop *inner_loop,
2927 instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
2974 resolve_mixers (struct loop *loop, tree chrec)
2983 tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL,
2997 the loop will run. When this property is not decidable at compile
3004 Example of analysis: suppose that the loop has an exit condition:
3014 variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
3016 the loop body has been executed 6 times. */
3019 number_of_latch_executions (struct loop *loop)
3026 /* Determine whether the number of iterations in loop has already
3028 res = loop->nb_iterations;
3038 exit = single_exit (loop);
3040 if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
3066 loop->nb_iterations = res;
3226 struct loop *loop;
3232 FOR_EACH_LOOP (loop, 0)
3234 loop->nb_iterations = NULL_TREE;
3259 in the hash table and in the loop->nb_iterations. */
3264 struct loop *loop;
3268 FOR_EACH_LOOP (loop, 0)
3270 loop->nb_iterations = NULL_TREE;
3296 simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
3413 struct loop *loop, *ex_loop;
3423 loop = bb->loop_father;
3439 ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
3477 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3483 /* If we do not know exact number of iterations of the loop, we cannot
3485 exit = single_exit (loop);
3489 niter = number_of_latch_executions (loop);
3498 ex_loop = superloop_at_depth (loop,
3520 def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3525 /* Moving the computation from the loop may prolong life range
3549 the loop. */