contrib/gcc/tree-ssa-loop-niter.c

1 /* Functions to determine/estimate number of iterations of a loop.
129 /* Determines number of iterations of loop whose ending condition
172   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
186       /* If we cannot assume that the loop is not infinite, record the
203    of the loop with ending condition IV0 < IV1 (computed in TYPE).
277 /* Add assertions to NITER that ensure that the control variable of the loop
347 /* Add an assumption to NITER that a loop whose ending condition
405 /* Determines number of iterations of loop whose ending condition
482      otherwise the loop does not roll.  */
492 /* Determines number of iterations of loop whose ending condition
508      equal to this value, the loop rolls forever.  */
536    inside loop) which compares two induction variables using comparison
542    ONLY_EXIT is true if we are sure this is the only way the loop could be
562      if may_be_zero then the loop does not roll, even if
583       /* If this is not the only possible exit from the loop, the information
586 	 following way:  given loop for (i = 0; i <= n; i++), if i is
587 	 signed, it cannot overflow, thus this loop is equivalent to
588 	 for (i = 0; i < n + 1; i++);  however, if n == MAX, but the loop
590 	 is incorrect (the new loop exits immediately).  */
609   /* If the control induction variable does not overflow, the loop obviously
633   /* If the result of the comparison is a constant,  the loop is weird.  More
649   /* If the loop exits immediately, there is nothing to do.  */
656   /* OK, now we know we have a senseful loop.  Handle several cases, depending
886    the loop do not cause us to fail.  */
897    of loop header copies we use for simplifying a conditional
907 simplify_using_initial_conditions (struct loop *loop, tree expr,
921   for (bb = loop->header;
950 /* Tries to simplify EXPR using the evolutions of the loop invariants
955 simplify_using_outer_evolutions (struct loop *loop, tree expr)
970       e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
974       e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
980 	  e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
998   e = instantiate_parameters (loop, expr);
1008 loop_only_exit_p (struct loop *loop, edge exit)
1015   if (exit != loop->single_exit)
1018   body = get_loop_body (loop);
1019   for (i = 0; i < loop->num_nodes; i++)
1041    -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1045 number_of_iterations_exit (struct loop *loop, edge exit,
1054   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1062   /* We want the condition for staying inside loop.  */
1089   if (!simple_iv (loop, stmt, op0, &iv0, false))
1091   if (!simple_iv (loop, stmt, op1, &iv1, false))
1101 				  loop_only_exit_p (loop, exit)))
1109       niter->assumptions = simplify_using_outer_evolutions (loop,
1111       niter->may_be_zero = simplify_using_outer_evolutions (loop,
1113       niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1118 	  = simplify_using_initial_conditions (loop,
1122 	  = simplify_using_initial_conditions (loop,
1131   /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1133      behavior, ignore the loop even with -funsafe-loop-optimizations.  */
1154           ? N_("assuming that the loop is not infinite")
1159 	  ? N_("assuming that the loop counter does not overflow")
1160 	  : N_("cannot optimize loop, the loop counter may overflow");
1177 find_loop_niter (struct loop *loop, edge *exit)
1180   edge *exits = get_loop_exit_edges (loop, &n_exits);
1189       if (!just_once_each_iteration_p (loop, ex->src))
1192       if (!number_of_iterations_exit (loop, ex, &desc, false))
1242    Analysis of a number of iterations of a loop by a brute-force evaluation.
1251 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1256 chain_of_csts_start (struct loop *loop, tree x)
1263       || !flow_bb_inside_loop_p (loop, bb))
1268       if (bb == loop->header)
1286   return chain_of_csts_start (loop, use);
1301 get_base_for (struct loop *loop, tree x)
1308   phi = chain_of_csts_start (loop, x);
1312   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1313   next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1321   if (chain_of_csts_start (loop, next) != phi)
1330    * otherwise X is a SSA name, whose value in the considered loop is derived
1332      the header of the loop.  Then we return value of X when the value of the
1358       /* only iterate loop once.  */
1368    condition at EXIT in first few iterations of the loop (assuming that
1374 loop_niter_by_eval (struct loop *loop, edge exit)
1408       phi[j] = get_base_for (loop, op[j]);
1417 	  val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1418 	  next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1442 		     "Proved that loop %d iterates %d times using brute force.\n",
1443 		     loop->num, i);
1463 /* Finds the exit of the LOOP by that the loop exits after a constant
1471 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1474   edge *exits = get_loop_exit_edges (loop, &n_exits);
1482       if (!just_once_each_iteration_p (loop, ex->src))
1485       aniter = loop_niter_by_eval (loop, ex);
1503    Analysis of upper bounds on number of iterations of a loop.
1683 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
1698       fprintf (dump_file, ") times in loop %d.\n", loop->num);
1703   elt->next = loop->bounds;
1704   loop->bounds = elt;
1711 compute_estimated_nb_iterations (struct loop *loop)
1715   for (bound = loop->bounds; bound; bound = bound->next)
1722       if (chrec_contains_undetermined (loop->estimated_nb_iterations)
1723 	  || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
1724 	loop->estimated_nb_iterations = bound->bound;
1738 infer_loop_bounds_from_undefined (struct loop *loop)
1744   bbs = get_loop_body (loop);
1746   for (i = 0; i < loop->num_nodes; i++)
1750       /* If BB is not executed in each iteration of the loop, we cannot
1752 	 # of iterations of the loop.  */
1753       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1768 		   and record a bound on the loop iteration domain.  */
1778 		   scalar evolution and record a bound of the loop
1784 		      (loop, analyze_scalar_evolution (loop, op0));
1791 		    init = initial_condition_in_loop_num (scev, loop->num);
1792 		    step = evolution_part_in_loop_num (scev, loop->num);
1816 			record_estimate (loop,
1844   compute_estimated_nb_iterations (loop);
1851 estimate_numbers_of_iterations_loop (struct loop *loop)
1859   if (loop->estimated_nb_iterations == chrec_dont_know
1861       || (loop->estimated_nb_iterations != NULL_TREE
1862 	  && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
1865     loop->estimated_nb_iterations = chrec_dont_know;
1867   exits = get_loop_exit_edges (loop, &n_exits);
1870       if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
1880       record_estimate (loop, niter,
1886   if (chrec_contains_undetermined (loop->estimated_nb_iterations))
1887     infer_loop_bounds_from_undefined (loop);
1896   struct loop *loop;
1899      loop iteration estimates.  */
1904       loop = loops->parray[i];
1905       if (loop)
1906 	estimate_numbers_of_iterations_loop (loop);
1938    STMT in the loop is at most NITER, according to the fact
2001 		       tree at_stmt, struct loop *loop,
2042      bound of the type, and verify that the loop is exited before this
2065   estimate_numbers_of_iterations_loop (loop);
2066   for (bound = loop->bounds; bound; bound = bound->next)
2085 free_numbers_of_iterations_estimates_loop (struct loop *loop)
2089   loop->nb_iterations = NULL;
2090   loop->estimated_nb_iterations = NULL;
2091   for (bound = loop->bounds; bound; bound = next)
2097   loop->bounds = NULL;
2106   struct loop *loop;
2110       loop = loops->parray[i];
2111       if (loop)
2112 	free_numbers_of_iterations_estimates_loop (loop);
2120 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2122   loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
2123   loop->estimated_nb_iterations
2124 	  = simplify_replace_tree (loop->estimated_nb_iterations, name, val);