contrib/gcc/tree-scalar-evolution.c

25    This pass analyzes the evolution of scalar variables in loop
27    and on the loop hierarchy tree.  This algorithm is not based on
36    when entering in the loop_1 and has a step 2 in this loop, in other
63    - When the definition is a loop-phi-node: determine its initial
64    condition, that is the SSA edge defined in an outer loop, and
66    in the body of the loop.  Follow the inner edges until ending on
67    another loop-phi-node of the same analyzed loop.  If the reached
68    loop-phi-node is not the starting loop-phi-node, then we keep
70    loop-phi-node is the same as the starting one, then we compute a
92    Following the SSA edge, we end on a loop-phi-node "b = phi (a,
93    c)", where the initial condition is "a", and the inner loop edge
97    loop-phi-node).  The update edge is followed to the end of the
98    loop, and until reaching again the starting loop-phi-node: b -> c
100    which we compute the stride in the loop: in this example it is
109    and take the smallest iteration number for which the loop is
110    exited: x = 7.  This loop runs from x = 0 to x = 7, and in total
111    there are 8 iterations.  In terms of loop normalization, we have
113    and all the other analyzed scalars of the loop are defined in
141    the SSA edge into the loop's body: "a -> b".  "b" is an inner
142    loop-phi-node, and its analysis as in Example 1, gives:
148    + 2", and then on the starting loop-phi-node "a".  From this point,
149    the loop stride is computed: back on "c = a + 2" we get a "+2" in
150    the loop_1, then on the loop-phi-node "b" we compute the overall
151    effect of the inner loop that is "b = c + 30", and we get a "+30"
190    Note that this syntax is close to the syntax of the loop-phi-node:
256 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
257 static tree resolve_mixers (struct loop *, tree);
378       struct loop *def_loop = loop_containing_stmt (def);
379       struct loop *loop = current_loops->parray[loop_nb];
384       if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
412 /* Return true when PHI is a loop-phi-node.  */
418      property: "all the loop-phi-nodes of a loop are contained in the
419      loop's header basic block".  */
449    This loop has the same effect as:
454    The overall effect of the loop, "i_0 + 20" in the previous example,
460 compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
469       if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
471 	  struct loop *inner_loop =
492 	      return compute_overall_effect_of_inner_loop (loop, res);
500   else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
533 	 changes during the execution of the loop, from 0 to
534 	 loop->nb_iterations.  */
655    part for this loop.  */
672 	  /* When there is no evolution part in this loop, build it.  */
705       /* These nodes do not depend on a loop.  */
724    reconstructed the overall tree expression for a loop, there are only
727    1. a = loop-phi (init, a + expr)
728    2. a = loop-phi (init, expr)
731    loop (this is a degree 0 polynomial), or an expression containing
732    other loop-phi definitions (these are higher degree polynomials).
754    that is, there is a loop index "x" that determines the scalar value
755    of the variable during the loop execution.  During the first
767    close to the syntax of a loop-phi-node:
775    When EXPR is a constant with respect to the analyzed loop, or in
777    the variable A in the loop is an affine function with an initial
896 set_nb_iterations_in_loop (struct loop *loop,
904      count of the loop in order to be compatible with the other
905      nb_iter computations in loop-iv.  This also allows the
919   loop->nb_iterations = res;
928    loop nests we could analyze.  */
963 /* For a loop with a single exit edge, return the COND_EXPR that
968 get_loop_exit_condition (struct loop *loop)
971   edge exit_edge = loop->single_exit;
995 /* Recursively determine and enqueue the exit conditions for a loop.  */
998 get_exit_conditions_rec (struct loop *loop,
1001   if (!loop)
1005   get_exit_conditions_rec (loop->inner, exit_conditions);
1006   get_exit_conditions_rec (loop->next, exit_conditions);
1008   if (loop->single_exit)
1010       tree loop_condition = get_loop_exit_condition (loop);
1017 /* Select the candidate loop nests for the analysis.  This function
1024   struct loop *function_body = loops->parray[0];
1040 static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
1046 follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
1065       res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
1079 	(loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
1097 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1102 		  (loop->num,
1109 		    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1114 		      (loop->num,
1131 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1135 		  (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1149 	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
1153 	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
1180 	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1184 	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
1204 	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
1242 					 struct loop *loop,
1251   /* Do not follow back edges (they must belong to an irreducible loop, which
1259       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1274    loop.  */
1277 follow_ssa_edge_in_condition_phi (struct loop *loop,
1285   t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
1301       res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1315 /* Follow an SSA edge in an inner loop.  It computes the overall
1316    effect of the loop, and following the symbolic initial conditions,
1317    it follows the edges in the parent loop.  The inner loop is
1321 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1326   struct loop *loop = loop_containing_stmt (loop_phi_node);
1327   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1329   /* Sometimes, the inner loop is too difficult to analyze, and the
1341 	  /* Follow the edges that exit the inner loop.  */
1343 	  if (!flow_bb_inside_loop_p (loop, bb))
1351       /* If the path crosses this loop-phi, give up.  */
1358   /* Otherwise, compute the overall effect of the inner loop.  */
1359   ev = compute_overall_effect_of_inner_loop (loop, ev);
1364 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
1368 follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
1371   struct loop *def_loop;
1391 	  (loop, def, halting_phi, evolution_of_loop, limit);
1395 	 the halting_phi to itself in the loop.  */
1400 	 on the evolution of another loop-phi-node, i.e. the
1402       if (def_loop == loop)
1405       /* Inner loop.  */
1406       if (flow_loop_nested_p (loop, def_loop))
1408 	  (loop, def, halting_phi, evolution_of_loop, limit);
1410       /* Outer loop.  */
1414       return follow_ssa_edge_in_rhs (loop, def,
1431    function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop.  */
1439   struct loop *loop = loop_containing_stmt (loop_phi_node);
1456       /* Select the edges that enter the loop body.  */
1458       if (!flow_bb_inside_loop_p (loop, bb))
1467 	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
1481       /* When there are multiple back edges of the loop (which in fact never
1496 /* Given a loop-phi-node, return the initial conditions of the
1497    variable on entry of the loop.  When the CCP has propagated
1498    constants into the loop-phi-node, the initial condition is
1501    loop, and leaves this task to the on-demand tree reconstructor.  */
1508   struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
1523       /* When the branch is oriented to the loop's body, it does
1525       if (flow_bb_inside_loop_p (loop, bb))
1543   /* Ooops -- a loop without an entry???  */
1560 interpret_loop_phi (struct loop *loop, tree loop_phi_node)
1563   struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1566   if (phi_loop != loop)
1568       struct loop *subloop;
1573       subloop = superloop_at_depth (phi_loop, loop->depth + 1);
1580   /* Otherwise really interpret the loop phi.  */
1588    contained in the outermost loop, and whose arguments are already
1592 interpret_condition_phi (struct loop *loop, tree condition_phi)
1608 	(loop, PHI_ARG_DEF (condition_phi, i));
1618    either on an analyzed modify_expr, or on a loop-phi-node.  On the
1621    analyze the effect of an inner loop: see interpret_loop_phi.  */
1624 interpret_rhs_modify_expr (struct loop *loop, tree at_stmt,
1637       chrec10 = analyze_scalar_evolution (loop, opnd10);
1638       chrec11 = analyze_scalar_evolution (loop, opnd11);
1647       chrec10 = analyze_scalar_evolution (loop, opnd10);
1648       chrec11 = analyze_scalar_evolution (loop, opnd11);
1656       chrec10 = analyze_scalar_evolution (loop, opnd10);
1666       chrec10 = analyze_scalar_evolution (loop, opnd10);
1667       chrec11 = analyze_scalar_evolution (loop, opnd11);
1674       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
1680       res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
1687       chrec10 = analyze_scalar_evolution (loop, opnd10);
1712 compute_scalar_evolution_in_loop (struct loop *wrto_loop,
1713 				  struct loop *def_loop,
1911 analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
1915   struct loop *def_loop;
1917   if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
1921     return interpret_rhs_modify_expr (loop, NULL_TREE, var, type);
1928       || !flow_bb_inside_loop_p (loop, bb))
1937       if (loop != bb->loop_father)
1939 	    (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
1944   if (loop != def_loop)
1947       res = compute_scalar_evolution_in_loop (loop, def_loop, res);
1955       res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
1965 	res = interpret_loop_phi (loop, def);
1967 	res = interpret_condition_phi (loop, def);
1981   if (loop == def_loop)
1989    LOOP_NB is the identifier number of the loop in which the variable
2004 analyze_scalar_evolution (struct loop *loop, tree var)
2011       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2017   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
2037 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
2056       /* If the value of the use changes in the inner loop, we cannot express
2057 	 its value in the outer loop (we might try to return interval chrec,
2106   struct loop *loop;
2114   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2115   exit = loop->single_exit;
2143 instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
2148   struct loop *def_loop;
2164       /* A parameter (or loop invariant and we do not want to include
2168 	      && !flow_bb_inside_loop_p (loop, def_bb)))
2185 	 is defined outside of the loop, we may just leave it in symbolic
2187 	 inside the loop.  */
2188       res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
2199       def_loop = find_common_loop (loop, def_bb->loop_father);
2206       /* Don't instantiate loop-closed-ssa phi nodes.  */
2222 	res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
2231       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
2236       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
2250       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2255       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2270       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2275       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2290       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2295       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2312       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2348       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2353       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2358       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
2372       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2377       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
2388       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
2408    symbolic form.  LOOP is the loop in which symbolic names have to
2412 instantiate_parameters (struct loop *loop,
2421       fprintf (dump_file, "  (loop_nb = %d)\n", loop->num);
2427   res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
2448 resolve_mixers (struct loop *loop, tree chrec)
2451   tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
2458    the loop will run.  When this property is not decidable at compile
2462    Example of analysis: suppose that the loop has an exit condition:
2472    variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2474    the loop body has been executed 6 times.  */
2477 number_of_iterations_in_loop (struct loop *loop)
2485   res = loop->nb_iterations;
2493   exit = loop->single_exit;
2497   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
2509   return set_nb_iterations_in_loop (loop, res);
2661    defined as loop phi nodes in one of the loops from the
2664    TODO Optimization: A loop is in canonical form if it contains only
2665    a single scalar loop phi node.  All the other scalars that have an
2666    evolution in the loop are rewritten in function of this single
2667    index.  This allows the parallelization of the loop.  */
2680       struct loop *loop;
2684       loop = loop_containing_stmt (cond);
2685       bb = loop->header;
2691 	      (loop,
2692 	       analyze_scalar_evolution (loop, PHI_RESULT (phi)));
2778   struct loop *loop;
2786       loop = current_loops->parray[i];
2787       if (loop)
2788 	loop->nb_iterations = NULL_TREE;
2799 simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
2815   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
2821       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
2829       || CHREC_VARIABLE (ev) != (unsigned) loop->num)
2836 	  || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
2844       || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
2898   struct loop *loop, *ex_loop;
2907       loop = bb->loop_father;
2922 	  ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
2964       loop = current_loops->parray[i];
2965       if (!loop)
2968       /* If we do not know exact number of iterations of the loop, we cannot
2970       exit = loop->single_exit;
2974       niter = number_of_iterations_in_loop (loop);
2987       ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
3001 	  def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
3005 	      /* Moving the computation from the loop may prolong life range
3012 	     the loop.  */