Hi, while looking into sudoku solving benchark, I noticed that we incorrectly estimate loop to iterate 10 times just because the array it traverses is of dimension 10. This of course is just upper bound and not realistic bound. Realistically those loops iterates once most of time.
It turns out this bug was introduced by me in https://gcc.gnu.org/ml/gcc-patches/2013-01/msg00444.html While I do not recall doing that patch, it seems like a thinko about reliable (name of the variable) and realistic (name of the parameter it is passed to). Fixing this caused one testsuite fallout in predictive commoning testcase because loop unswitching previously disabled itself having an estimated number of iterations 1 (I am not sure if that is not supposed to be 0, with 1 iteration unswithcing may pay back, little bit, I suppose it wants to test number of stmt executions of the condtional to be at least 2 which depends on whether the conditional is before or after the loop exits). This made me notice that some loop passes that want to give up on low trip count uses combination of estimated number of iterations and max number of iterations while other don't which is fixed here. The code combining both realistic and max counts is same as i.e. in unroller and other passes already. I also wonder if predictive comming is a win for loops with very low trip count, but that is for separate patch, too, anyway. Bootstrapped/regtested x86_64-linux, OK? Honza * tree-ssa-loop-niter.c (idx_infer_loop_bounds): We can't get realistic estimates here. * tree-ssa-loop-unswitch.c (tree_unswitch_single_loop): Use also max_loop_iterations_int. * tree-ssa-loop-ivopts.c (avg_loop_niter): Likewise. * tree-vect-loop.c (vect_analyze_loop_2): Likewise. Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 234516) +++ tree-ssa-loop-niter.c (working copy) @@ -3115,7 +3115,6 @@ idx_infer_loop_bounds (tree base, tree * tree low, high, type, next; bool sign, upper = true, at_end = false; struct loop *loop = data->loop; - bool reliable = true; if (TREE_CODE (base) != ARRAY_REF) return true; @@ -3187,14 +3186,14 @@ idx_infer_loop_bounds (tree base, tree * && tree_int_cst_compare (next, high) <= 0) return true; - /* If access is not executed on every iteration, we must ensure that overlow may - not make the access valid later. */ + /* If access is not executed on every iteration, we must ensure that overlow + may not make the access valid later. */ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)) && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num), step, data->stmt, loop, true)) - reliable = false; + upper = false; - record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper); + record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper); return true; } Index: tree-ssa-loop-unswitch.c =================================================================== --- tree-ssa-loop-unswitch.c (revision 234516) +++ tree-ssa-loop-unswitch.c (working copy) @@ -223,6 +223,8 @@ tree_unswitch_single_loop (struct loop * /* If the loop is not expected to iterate, there is no need for unswitching. */ iterations = estimated_loop_iterations_int (loop); + if (iterations < 0) + iterations = max_loop_iterations_int (loop); if (iterations >= 0 && iterations <= 1) { if (dump_file && (dump_flags & TDF_DETAILS)) Index: tree-ssa-loop-ivopts.c =================================================================== --- tree-ssa-loop-ivopts.c (revision 234516) +++ tree-ssa-loop-ivopts.c (working copy) @@ -121,7 +121,11 @@ avg_loop_niter (struct loop *loop) { HOST_WIDE_INT niter = estimated_stmt_executions_int (loop); if (niter == -1) - return AVG_LOOP_NITER (loop); + { + niter = max_stmt_executions_int (loop); + if (niter == -1 || niter > AVG_LOOP_NITER (loop)) + return AVG_LOOP_NITER (loop); + } return niter; } Index: tree-vect-loop.c =================================================================== --- tree-vect-loop.c (revision 234516) +++ tree-vect-loop.c (working copy) @@ -2063,6 +2063,9 @@ start_over: estimated_niter = estimated_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo)); + if (estimated_niter != -1) + estimated_niter + = max_stmt_executions_int (LOOP_VINFO_LOOP (loop_vinfo)); if (estimated_niter != -1 && ((unsigned HOST_WIDE_INT) estimated_niter <= MAX (th, (unsigned)min_profitable_estimate)))
