Lines Matching defs:loop
1 /* Functions to determine/estimate number of iterations of a loop.
70 #include "tree-ssa-loop-ivopts.h"
71 #include "tree-ssa-loop-niter.h"
72 #include "tree-ssa-loop.h"
90 of loop header copies we use for simplifying a conditional
155 determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
174 edge e = loop_preheader_edge (loop);
180 /* Or for PHI results in loop->header where VAR is used as
181 PHI argument from the loop preheader edge. */
182 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
473 comparisons before the loop (usually created by loop header copying). */
476 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
517 determine_value_range (loop, type, varx, offx, minx, maxx);
518 determine_value_range (loop, type, vary, offy, miny, maxy);
532 /* Now walk the dominators of the loop header and use the entry
534 for (bb = loop->header;
650 /* Derives the upper bound BND on the number of executions of loop with exit
652 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
653 that the loop ends through this exit, i.e., the induction variable ever
657 initial value of the actual induction variable in the analysed loop. BNDS
684 the induction variable overflows (unless the loop is exited in some
686 loop (which ranges from base to final instead of from 0 to C) may
703 /* Now we know that the induction variable does not overflow, so the loop
725 /* Determines number of iterations of loop whose ending condition
782 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
813 of the loop with ending condition IV0 < IV1 (computed in TYPE).
936 /* Add assertions to NITER that ensure that the control variable of the loop
1006 /* Add an assumption to NITER that a loop whose ending condition
1031 we have a condition of the form iv0->base - step < iv1->base before the loop,
1033 iv0->base < iv1->base + step, due to loop header copying, which enable us
1131 /* Determines number of iterations of loop whose ending condition
1219 otherwise the loop does not roll. */
1241 /* Determines number of iterations of loop whose ending condition
1261 equal to this value, the loop rolls forever. We do not check
1322 inside loop) which compares two induction variables using comparison
1328 LOOP is the loop whose number of iterations we are determining.
1330 ONLY_EXIT is true if we are sure this is the only way the loop could be
1338 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1343 number_of_iterations_cond (struct loop *loop,
1364 if may_be_zero then the loop does not roll, even if
1394 from the loop is the one that we analyze, we know it must be taken
1420 /* If the result of the comparison is a constant, the loop is weird. More
1436 /* If the loop exits immediately, there is nothing to do. */
1445 /* OK, now we know we have a senseful loop. Handle several cases, depending
1447 bound_difference (loop, iv1->base, iv0->base, &bnds);
1452 "Analyzing # of iterations of loop %d\n", loop->num);
1622 /* Avoid propagating through loop exit phi nodes, which
1623 could break loop-closed SSA form restrictions. */
1795 the loop do not cause us to fail. */
1810 simplify_using_initial_conditions (struct loop *loop, tree expr)
1824 for (bb = loop->header;
1849 /* Tries to simplify EXPR using the evolutions of the loop invariants
1854 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1869 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1873 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1879 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1897 e = instantiate_parameters (loop, expr);
1907 loop_only_exit_p (const struct loop *loop, const_edge exit)
1914 if (exit != single_exit (loop))
1917 body = get_loop_body (loop);
1918 for (i = 0; i < loop->num_nodes; i++)
1943 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1946 every iteration are considered (i.e. only test that alone bounds the loop).
1950 number_of_iterations_exit (struct loop *loop, edge exit,
1962 safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
1975 /* We want the condition for staying inside loop. */
2001 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
2003 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
2012 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
2013 loop_only_exit_p (loop, exit), safe))
2021 niter->assumptions = simplify_using_outer_evolutions (loop,
2023 niter->may_be_zero = simplify_using_outer_evolutions (loop,
2025 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
2029 = simplify_using_initial_conditions (loop,
2032 = simplify_using_initial_conditions (loop,
2044 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
2046 behavior, ignore the loop even with -funsafe-loop-optimizations. */
2047 if (integer_zerop (niter->assumptions) || !single_exit (loop))
2066 ? N_("assuming that the loop is not infinite")
2071 ? N_("assuming that the loop counter does not overflow")
2072 : N_("cannot optimize loop, the loop counter may overflow");
2087 find_loop_niter (struct loop *loop, edge *exit)
2090 vec<edge> exits = get_loop_exit_edges (loop);
2098 if (!number_of_iterations_exit (loop, ex, &desc, false))
2146 /* Return true if loop is known to have bounded number of iterations. */
2149 finite_loop_p (struct loop *loop)
2160 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2161 loop->num);
2165 if (loop->any_upper_bound
2166 || max_loop_iterations (loop, &nit))
2169 fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
2170 loop->num);
2178 Analysis of a number of iterations of a loop by a brute-force evaluation.
2187 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2192 chain_of_csts_start (struct loop *loop, tree x)
2200 || !flow_bb_inside_loop_p (loop, bb))
2205 if (bb == loop->header)
2226 return chain_of_csts_start (loop, use);
2240 get_base_for (struct loop *loop, tree x)
2248 phi = chain_of_csts_start (loop, x);
2252 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2253 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2261 if (chain_of_csts_start (loop, next) != phi)
2270 * otherwise X is a SSA name, whose value in the considered loop is derived
2272 the header of the loop. Then we return value of X when the value of the
2323 condition at EXIT in first few iterations of the loop (assuming that
2329 loop_niter_by_eval (struct loop *loop, edge exit)
2372 phi = get_base_for (loop, op[j]);
2375 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2376 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2394 "Proved that loop %d iterates %d times using brute force.\n",
2395 loop->num, i);
2415 /* Finds the exit of the LOOP by that the loop exits after a constant
2423 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2426 vec<edge> exits = get_loop_exit_edges (loop);
2442 if (!just_once_each_iteration_p (loop, ex->src))
2445 aniter = loop_niter_by_eval (loop, ex);
2463 Analysis of upper bounds on number of iterations of a loop.
2637 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2640 do_warn_aggressive_loop_optimizations (struct loop *loop,
2643 /* Don't warn if the loop doesn't have known constant bound. */
2644 if (!loop->nb_iterations
2645 || TREE_CODE (loop->nb_iterations) != INTEGER_CST
2647 /* To avoid warning multiple times for the same loop,
2650 /* Only warn once per loop. */
2651 || loop->warned_aggressive_loop_optimizations
2654 || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0
2656 || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
2659 edge e = single_exit (loop);
2666 wide_int_to_tree (TREE_TYPE (loop->nb_iterations),
2668 inform (gimple_location (estmt), "containing loop");
2669 loop->warned_aggressive_loop_optimizations = true;
2673 is true if the loop is exited immediately after STMT, and this exit
2676 of iterations. UPPER is true if we are sure the loop iterates at most
2680 record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
2694 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2708 at_stmt) in a loop with known constant number of iterations. */
2711 || loop->nb_iterations == NULL_TREE
2712 || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
2719 elt->next = loop->bounds;
2720 loop->bounds = elt;
2723 /* If statement is executed on every path to the loop latch, we can directly
2724 infer the upper bound on the # of iterations of the loop. */
2725 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
2729 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2743 do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt);
2744 record_niter_bound (loop, new_i_bound, realistic, upper);
2754 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2774 fprintf (dump_file, " in loop %d.\n", loop->num);
2793 loop->latch, gimple_bb (stmt)))
2810 loop->latch, gimple_bb (stmt)))
2819 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2829 struct loop *loop;
2840 struct loop *loop = data->loop;
2855 struct loop *dloop = loop_containing_stmt (data->stmt);
2860 ev = instantiate_parameters (loop, ev);
2862 step = evolution_part_in_loop_num (ev, loop->num);
2869 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2915 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
2916 && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
2917 step, data->stmt, loop, true))
2920 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
2929 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref)
2933 data.loop = loop;
2943 infer_loop_bounds_from_array (struct loop *loop, gimple stmt)
2951 and record a bound on the loop iteration domain. */
2953 infer_loop_bounds_from_ref (loop, stmt, op0);
2956 infer_loop_bounds_from_ref (loop, stmt, op1);
2965 infer_loop_bounds_from_ref (loop, stmt, lhs);
2971 infer_loop_bounds_from_ref (loop, stmt, arg);
2980 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2998 if (!expr_invariant_in_loop_p (loop, ptr))
3005 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
3009 base = initial_condition_in_loop_num (scev, loop->num);
3010 step = evolution_part_in_loop_num (scev, loop->num);
3015 || chrec_contains_symbols_defined_in_loop (base, loop->num))
3031 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3038 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
3055 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
3059 base = initial_condition_in_loop_num (scev, loop->num);
3060 step = evolution_part_in_loop_num (scev, loop->num);
3065 || chrec_contains_symbols_defined_in_loop (base, loop->num))
3071 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3084 infer_loop_bounds_from_undefined (struct loop *loop)
3092 bbs = get_loop_body (loop);
3094 for (i = 0; i < loop->num_nodes; i++)
3098 /* If BB is not executed in each iteration of the loop, we cannot
3100 # of iterations of the loop. However, we can use it as a guess.
3102 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
3108 infer_loop_bounds_from_array (loop, stmt);
3112 infer_loop_bounds_from_signedness (loop, stmt);
3113 infer_loop_bounds_from_pointer_arith (loop, stmt);
3157 /* We recorded loop bounds only for statements dominating loop latch (and thus
3158 executed each loop iteration). If there are any bounds on statements not
3159 dominating the loop latch we can improve the estimate by walking the loop
3160 body and seeing if every path from loop header to loop latch contains
3164 discover_iteration_bound_by_body_walk (struct loop *loop)
3174 for (elt = loop->bounds; elt; elt = elt->next)
3178 /* Exit terminates loop at given iteration, while non-exits produce undefined
3188 if (!loop->any_upper_bound
3189 || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3198 fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
3204 terminate the loop. */
3207 for (elt = loop->bounds; elt; elt = elt->next)
3218 if (!loop->any_upper_bound
3219 || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3232 /* Perform shortest path discovery loop->header ... loop->latch.
3234 The "distance" is given by the smallest loop bound of basic block
3248 /* Start walk in loop header with index set to infinite bound. */
3251 queue.safe_push (loop->header);
3253 block_priority.put (loop->header, queue_index);
3284 if (loop_exit_edge_p (loop, e))
3287 if (e == loop_latch_edge (loop)
3314 fprintf (dump_file, "Found better loop bound ");
3318 record_niter_bound (loop, bounds[latch_index], false, true);
3325 /* See if every path cross the loop goes through a statement that is known
3330 maybe_lower_iteration_bound (struct loop *loop)
3343 also statements not dominating the loop latch and update the walk bellow
3345 for (elt = loop->bounds; elt; elt = elt->next)
3348 && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
3358 /* Start DFS walk in the loop header and see if we can reach the
3359 loop latch or any of the exits (including statements with side
3360 effects that may terminate the loop otherwise) without visiting
3363 queue.safe_push (loop->header);
3365 bitmap_set_bit (visited, loop->header->index);
3400 if (loop_exit_edge_p (loop, e)
3401 || e == loop_latch_edge (loop))
3413 /* If every path through the loop reach bounding statement before exit,
3414 then we know the last iteration of the loop will have undefined effect
3420 fprintf (dump_file, "Reducing loop iteration estimate by 1; "
3422 record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
3435 estimate_numbers_of_iterations_loop (struct loop *loop)
3446 if (loop->estimate_state != EST_NOT_COMPUTED)
3449 loop->estimate_state = EST_AVAILABLE;
3451 loop->any_estimate = false;
3453 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3455 diagnose those loops with -Waggressive-loop-optimizations. */
3456 number_of_latch_executions (loop);
3458 exits = get_loop_exit_edges (loop);
3459 likely_exit = single_likely_exit (loop);
3462 if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
3471 record_estimate (loop, niter, niter_desc.max,
3478 infer_loop_bounds_from_undefined (loop);
3480 discover_iteration_bound_by_body_walk (loop);
3482 maybe_lower_iteration_bound (loop);
3486 if (loop->header->count != 0)
3488 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3490 record_niter_bound (loop, bound, true, false);
3493 /* If we know the exact number of iterations of this loop, try to
3496 if (loop->nb_iterations
3497 && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
3499 loop->any_upper_bound = true;
3500 loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations);
3510 estimated_loop_iterations (struct loop *loop, widest_int *nit)
3512 /* When SCEV information is available, try to update loop iterations
3515 estimate_numbers_of_iterations_loop (loop);
3517 return (get_estimated_loop_iterations (loop, nit));
3525 estimated_loop_iterations_int (struct loop *loop)
3530 if (!estimated_loop_iterations (loop, &nit))
3546 max_loop_iterations (struct loop *loop, widest_int *nit)
3548 /* When SCEV information is available, try to update loop iterations
3551 estimate_numbers_of_iterations_loop (loop);
3553 return get_max_loop_iterations (loop, nit);
3561 max_loop_iterations_int (struct loop *loop)
3566 if (!max_loop_iterations (loop, &nit))
3577 in the LOOP. For statements before the loop exit, this exceeds
3581 estimated_stmt_executions_int (struct loop *loop)
3583 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
3600 max_stmt_executions (struct loop *loop, widest_int *nit)
3604 if (!max_loop_iterations (loop, nit))
3619 estimated_stmt_executions (struct loop *loop, widest_int *nit)
3623 if (!estimated_loop_iterations (loop, nit))
3638 struct loop *loop;
3641 loop iteration estimates. */
3644 FOR_EACH_LOOP (loop, 0)
3646 estimate_numbers_of_iterations_loop (loop);
3684 STMT in the loop is at most NITER, according to the bound on
3746 before NITER_BOUND->STMT. Still need to test that the loop
3792 gimple at_stmt, struct loop *loop,
3830 /* To be able to use estimates on number of iterations of the loop,
3839 bound of the type, and verify that the loop is exited before this
3862 estimate_numbers_of_iterations_loop (loop);
3864 if (max_loop_iterations (loop, &niter)
3875 for (bound = loop->bounds; bound; bound = bound->next)
3894 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3898 loop->nb_iterations = NULL;
3899 loop->estimate_state = EST_NOT_COMPUTED;
3900 for (bound = loop->bounds; bound; bound = next)
3906 loop->bounds = NULL;
3914 struct loop *loop;
3916 FOR_EACH_LOOP (loop, 0)
3918 free_numbers_of_iterations_estimates_loop (loop);
3926 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3928 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);