Message ID | CAO2gOZVZm2Va3JeHp3P3Nd=Em+EAWDPM3_xL3pJLTVggJa-wsw@mail.gmail.com |
---|---|
State | New |
Headers | show |
On Thu, May 22, 2014 at 11:36 PM, Dehao Chen <dehao@google.com> wrote: > If a loop's header count is less than iteration count, the iteration > estimation is apparently incorrect for this loop. Thus disable > unrolling of such loops. > > Testing on going. OK for trunk if test pass? No. Why don't you instead plug the hole in expected_loop_iterations ()? That is, why may not loop->header be bogus? Isn't it maybe the bounding you run into? /* Returns expected number of LOOP iterations. The returned value is bounded by REG_BR_PROB_BASE. */ unsigned expected_loop_iterations (const struct loop *loop) { gcov_type expected = expected_loop_iterations_unbounded (loop); return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); } I miss a testcase as well. Richard. > Thanks, > Dehao > > gcc/ChangeLog: > 2014-05-21 Dehao Chen <dehao@google.com> > > * cfgloop.h (expected_loop_iterations_reliable_p): New func. > * cfgloopanal.c (expected_loop_iterations_reliable_p): Likewise. > * loop-unroll.c (decide_unroll_runtime_iterations): Disable unroll > loop that has unreliable iteration counts. > > Index: gcc/cfgloop.h > =================================================================== > --- gcc/cfgloop.h (revision 210717) > +++ gcc/cfgloop.h (working copy) > @@ -307,8 +307,8 @@ extern bool just_once_each_iteration_p (const stru > gcov_type expected_loop_iterations_unbounded (const struct loop *); > extern unsigned expected_loop_iterations (const struct loop *); > extern rtx doloop_condition_get (rtx); > +extern bool expected_loop_iterations_reliable_p (const struct loop *); > > - > /* Loop manipulation. */ > extern bool can_duplicate_loop_p (const struct loop *loop); > > Index: gcc/cfgloopanal.c > =================================================================== > --- gcc/cfgloopanal.c (revision 210717) > +++ gcc/cfgloopanal.c (working copy) > @@ -285,6 +285,15 @@ expected_loop_iterations (const struct loop *loop) > return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); > } > > +/* Returns true if the loop header's profile count is smaller than expected > + loop iteration. */ > + > +bool > +expected_loop_iterations_reliable_p (const struct loop *loop) > +{ > + return expected_loop_iterations (loop) < loop->header->count; > +} > + > /* Returns the maximum level of nesting of subloops of LOOP. */ > > unsigned > Index: gcc/loop-unroll.c > =================================================================== > --- gcc/loop-unroll.c (revision 210717) > +++ gcc/loop-unroll.c (working copy) > @@ -988,6 +988,15 @@ decide_unroll_runtime_iterations (struct loop *loo > return; > } > > + if (profile_status_for_fn (cfun) == PROFILE_READ > + && expected_loop_iterations_reliable_p (loop)) > + { > + if (dump_file) > + fprintf (dump_file, ";; Not unrolling loop, loop iteration " > + "not reliable."); > + return; > + } > + > /* Check whether the loop rolls. */ > if ((get_estimated_loop_iterations (loop, &iterations) > || get_max_loop_iterations (loop, &iterations))
> On Thu, May 22, 2014 at 11:36 PM, Dehao Chen <dehao@google.com> wrote: > > If a loop's header count is less than iteration count, the iteration > > estimation is apparently incorrect for this loop. Thus disable > > unrolling of such loops. > > > > Testing on going. OK for trunk if test pass? > > No. Why don't you instead plug the hole in expected_loop_iterations ()? > That is, why may not loop->header be bogus? Isn't it maybe the bounding It is autoFDO thing. Dehao is basically pushing out changes that should make compiler more sane about bogus profiles. At the moment we have tests bb->count != 0 to figure out if the profile is reliable. I.e. we assume that profile feedback is always good, guessed profile is never good. Loop optimizers then do not trust guessed profile to give realistic estimates on number of iterations and bail out into simple heuristics for estimated profiles that are usually not good on this job - i.e. int niters = 0; if (desc->const_iter) niters = desc->niter; else if (loop->header->count) niters = expected_loop_iterations (loop); ... With FDO this change, as the FDO profiles are sometimes bogus (and there is not much to do about it). I would say that for loop optimization, we want a flag whether expected number of iterations is reliable. We probably want if (expected_loop_iterations_reliable_p (loop)) niters = expected_loop_iterations (loop); We probably also want to store this information into loop structure rather than computing it all the time from profile, since the profile may get inaccurate and we already know how to maintain upper bounds on numbers of iterations, so it should be easy to implement. This would allow us to preserve info like for (i=0 ;i < __bulitin_expect (n,10); i++) that would be nice feature to have. Honza > you run into? > > /* Returns expected number of LOOP iterations. The returned value is bounded > by REG_BR_PROB_BASE. */ > > unsigned > expected_loop_iterations (const struct loop *loop) > { > gcov_type expected = expected_loop_iterations_unbounded (loop); > return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); > } > > I miss a testcase as well. > > Richard. > > > Thanks, > > Dehao > > > > gcc/ChangeLog: > > 2014-05-21 Dehao Chen <dehao@google.com> > > > > * cfgloop.h (expected_loop_iterations_reliable_p): New func. > > * cfgloopanal.c (expected_loop_iterations_reliable_p): Likewise. > > * loop-unroll.c (decide_unroll_runtime_iterations): Disable unroll > > loop that has unreliable iteration counts. > > > > Index: gcc/cfgloop.h > > =================================================================== > > --- gcc/cfgloop.h (revision 210717) > > +++ gcc/cfgloop.h (working copy) > > @@ -307,8 +307,8 @@ extern bool just_once_each_iteration_p (const stru > > gcov_type expected_loop_iterations_unbounded (const struct loop *); > > extern unsigned expected_loop_iterations (const struct loop *); > > extern rtx doloop_condition_get (rtx); > > +extern bool expected_loop_iterations_reliable_p (const struct loop *); > > > > - > > /* Loop manipulation. */ > > extern bool can_duplicate_loop_p (const struct loop *loop); > > > > Index: gcc/cfgloopanal.c > > =================================================================== > > --- gcc/cfgloopanal.c (revision 210717) > > +++ gcc/cfgloopanal.c (working copy) > > @@ -285,6 +285,15 @@ expected_loop_iterations (const struct loop *loop) > > return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); > > } > > > > +/* Returns true if the loop header's profile count is smaller than expected > > + loop iteration. */ > > + > > +bool > > +expected_loop_iterations_reliable_p (const struct loop *loop) > > +{ > > + return expected_loop_iterations (loop) < loop->header->count; > > +} > > + > > /* Returns the maximum level of nesting of subloops of LOOP. */ > > > > unsigned > > Index: gcc/loop-unroll.c > > =================================================================== > > --- gcc/loop-unroll.c (revision 210717) > > +++ gcc/loop-unroll.c (working copy) > > @@ -988,6 +988,15 @@ decide_unroll_runtime_iterations (struct loop *loo > > return; > > } > > > > + if (profile_status_for_fn (cfun) == PROFILE_READ > > + && expected_loop_iterations_reliable_p (loop)) > > + { > > + if (dump_file) > > + fprintf (dump_file, ";; Not unrolling loop, loop iteration " > > + "not reliable."); > > + return; > > + } > > + > > /* Check whether the loop rolls. */ > > if ((get_estimated_loop_iterations (loop, &iterations) > > || get_max_loop_iterations (loop, &iterations))
On May 23, 2014 7:26:04 PM CEST, Jan Hubicka <hubicka@ucw.cz> wrote: >> On Thu, May 22, 2014 at 11:36 PM, Dehao Chen <dehao@google.com> >wrote: >> > If a loop's header count is less than iteration count, the >iteration >> > estimation is apparently incorrect for this loop. Thus disable >> > unrolling of such loops. >> > >> > Testing on going. OK for trunk if test pass? >> >> No. Why don't you instead plug the hole in expected_loop_iterations >()? >> That is, why may not loop->header be bogus? Isn't it maybe the >bounding > >It is autoFDO thing. Dehao is basically pushing out changes that >should make compiler >more sane about bogus profiles. > >At the moment we have tests bb->count != 0 to figure out if the profile >is >reliable. I.e. we assume that profile feedback is always good, guessed >profile >is never good. Loop optimizers then do not trust guessed profile to >give >realistic estimates on number of iterations and bail out into simple >heuristics >for estimated profiles that are usually not good on this job - i.e. > > int niters = 0; > > if (desc->const_iter) > niters = desc->niter; > else if (loop->header->count) > niters = expected_loop_iterations (loop); > ... > >With FDO this change, as the FDO profiles are sometimes bogus (and >there is not much >to do about it). >I would say that for loop optimization, we want a flag whether expected >number >of iterations is reliable. We probably want > > if (expected_loop_iterations_reliable_p (loop)) > niters = expected_loop_iterations (loop); But why not simply never return bogus values from expected-loop-iterations? We probably want a flag in the .gcda file on whether it was from auto-fdo and only not trust profiles from those. Richard. >We probably also want to store this information into loop structure >rather than computing >it all the time from profile, since the profile may get inaccurate and >we already know >how to maintain upper bounds on numbers of iterations, so it should be >easy to implement. > >This would allow us to preserve info like >for (i=0 ;i < __bulitin_expect (n,10); i++) > >that would be nice feature to have. > >Honza > >> you run into? >> >> /* Returns expected number of LOOP iterations. The returned value is >bounded >> by REG_BR_PROB_BASE. */ >> >> unsigned >> expected_loop_iterations (const struct loop *loop) >> { >> gcov_type expected = expected_loop_iterations_unbounded (loop); >> return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); >> } >> >> I miss a testcase as well. >> >> Richard. >> >> > Thanks, >> > Dehao >> > >> > gcc/ChangeLog: >> > 2014-05-21 Dehao Chen <dehao@google.com> >> > >> > * cfgloop.h (expected_loop_iterations_reliable_p): New >func. >> > * cfgloopanal.c (expected_loop_iterations_reliable_p): >Likewise. >> > * loop-unroll.c (decide_unroll_runtime_iterations): Disable >unroll >> > loop that has unreliable iteration counts. >> > >> > Index: gcc/cfgloop.h >> > =================================================================== >> > --- gcc/cfgloop.h (revision 210717) >> > +++ gcc/cfgloop.h (working copy) >> > @@ -307,8 +307,8 @@ extern bool just_once_each_iteration_p (const >stru >> > gcov_type expected_loop_iterations_unbounded (const struct loop >*); >> > extern unsigned expected_loop_iterations (const struct loop *); >> > extern rtx doloop_condition_get (rtx); >> > +extern bool expected_loop_iterations_reliable_p (const struct loop >*); >> > >> > - >> > /* Loop manipulation. */ >> > extern bool can_duplicate_loop_p (const struct loop *loop); >> > >> > Index: gcc/cfgloopanal.c >> > =================================================================== >> > --- gcc/cfgloopanal.c (revision 210717) >> > +++ gcc/cfgloopanal.c (working copy) >> > @@ -285,6 +285,15 @@ expected_loop_iterations (const struct loop >*loop) >> > return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : >expected); >> > } >> > >> > +/* Returns true if the loop header's profile count is smaller than >expected >> > + loop iteration. */ >> > + >> > +bool >> > +expected_loop_iterations_reliable_p (const struct loop *loop) >> > +{ >> > + return expected_loop_iterations (loop) < loop->header->count; >> > +} >> > + >> > /* Returns the maximum level of nesting of subloops of LOOP. */ >> > >> > unsigned >> > Index: gcc/loop-unroll.c >> > =================================================================== >> > --- gcc/loop-unroll.c (revision 210717) >> > +++ gcc/loop-unroll.c (working copy) >> > @@ -988,6 +988,15 @@ decide_unroll_runtime_iterations (struct loop >*loo >> > return; >> > } >> > >> > + if (profile_status_for_fn (cfun) == PROFILE_READ >> > + && expected_loop_iterations_reliable_p (loop)) >> > + { >> > + if (dump_file) >> > + fprintf (dump_file, ";; Not unrolling loop, loop iteration " >> > + "not reliable."); >> > + return; >> > + } >> > + >> > /* Check whether the loop rolls. */ >> > if ((get_estimated_loop_iterations (loop, &iterations) >> > || get_max_loop_iterations (loop, &iterations))
> > > > if (expected_loop_iterations_reliable_p (loop)) > > niters = expected_loop_iterations (loop); > > But why not simply never return bogus values from expected-loop-iterations? Hmm, actually we do have: /* If we have a measured profile, use it to estimate the number of iterations. */ if (loop->header->count != 0) { gcov_type nit = expected_loop_iterations_unbounded (loop) + 1; bound = gcov_type_to_wide_int (nit); record_niter_bound (loop, bound, true, false); } and get_estimated_loop_iterations that has the behaviour intended. Forgot about this. So probably we want to revisit remaining uses of expected_loop_iterations and use get_estimated_loop_iterations (most of compiler actually does that). I did some of these changes in past, so there are not many left. I would move the logic setting the actual estimate based on profile from estimate_numbers_of_iterations_loop into tree-profile pass (i.e. do it once at profile load time and maintain it all the way through compilation them, such as in inlining). AtoFDO can do its own analysis: I suppose loop count is known to autoFDO when it can find source line that is always executed in the loop and source line that is known to have same count as header. This may be implementable as a separate analysis rather than having heuristic based on overall sanity of the profile around the loop. Honza > We probably want a flag in the .gcda file on whether it was from auto-fdo and only not trust profiles from those. > > Richard. > > >We probably also want to store this information into loop structure > >rather than computing > >it all the time from profile, since the profile may get inaccurate and > >we already know > >how to maintain upper bounds on numbers of iterations, so it should be > >easy to implement. > > > >This would allow us to preserve info like > >for (i=0 ;i < __bulitin_expect (n,10); i++) > > > >that would be nice feature to have. > > > >Honza > > > >> you run into? > >> > >> /* Returns expected number of LOOP iterations. The returned value is > >bounded > >> by REG_BR_PROB_BASE. */ > >> > >> unsigned > >> expected_loop_iterations (const struct loop *loop) > >> { > >> gcov_type expected = expected_loop_iterations_unbounded (loop); > >> return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); > >> } > >> > >> I miss a testcase as well. > >> > >> Richard. > >> > >> > Thanks, > >> > Dehao > >> > > >> > gcc/ChangeLog: > >> > 2014-05-21 Dehao Chen <dehao@google.com> > >> > > >> > * cfgloop.h (expected_loop_iterations_reliable_p): New > >func. > >> > * cfgloopanal.c (expected_loop_iterations_reliable_p): > >Likewise. > >> > * loop-unroll.c (decide_unroll_runtime_iterations): Disable > >unroll > >> > loop that has unreliable iteration counts. > >> > > >> > Index: gcc/cfgloop.h > >> > =================================================================== > >> > --- gcc/cfgloop.h (revision 210717) > >> > +++ gcc/cfgloop.h (working copy) > >> > @@ -307,8 +307,8 @@ extern bool just_once_each_iteration_p (const > >stru > >> > gcov_type expected_loop_iterations_unbounded (const struct loop > >*); > >> > extern unsigned expected_loop_iterations (const struct loop *); > >> > extern rtx doloop_condition_get (rtx); > >> > +extern bool expected_loop_iterations_reliable_p (const struct loop > >*); > >> > > >> > - > >> > /* Loop manipulation. */ > >> > extern bool can_duplicate_loop_p (const struct loop *loop); > >> > > >> > Index: gcc/cfgloopanal.c > >> > =================================================================== > >> > --- gcc/cfgloopanal.c (revision 210717) > >> > +++ gcc/cfgloopanal.c (working copy) > >> > @@ -285,6 +285,15 @@ expected_loop_iterations (const struct loop > >*loop) > >> > return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : > >expected); > >> > } > >> > > >> > +/* Returns true if the loop header's profile count is smaller than > >expected > >> > + loop iteration. */ > >> > + > >> > +bool > >> > +expected_loop_iterations_reliable_p (const struct loop *loop) > >> > +{ > >> > + return expected_loop_iterations (loop) < loop->header->count; > >> > +} > >> > + > >> > /* Returns the maximum level of nesting of subloops of LOOP. */ > >> > > >> > unsigned > >> > Index: gcc/loop-unroll.c > >> > =================================================================== > >> > --- gcc/loop-unroll.c (revision 210717) > >> > +++ gcc/loop-unroll.c (working copy) > >> > @@ -988,6 +988,15 @@ decide_unroll_runtime_iterations (struct loop > >*loo > >> > return; > >> > } > >> > > >> > + if (profile_status_for_fn (cfun) == PROFILE_READ > >> > + && expected_loop_iterations_reliable_p (loop)) > >> > + { > >> > + if (dump_file) > >> > + fprintf (dump_file, ";; Not unrolling loop, loop iteration " > >> > + "not reliable."); > >> > + return; > >> > + } > >> > + > >> > /* Check whether the loop rolls. */ > >> > if ((get_estimated_loop_iterations (loop, &iterations) > >> > || get_max_loop_iterations (loop, &iterations)) >
Index: gcc/cfgloop.h =================================================================== --- gcc/cfgloop.h (revision 210717) +++ gcc/cfgloop.h (working copy) @@ -307,8 +307,8 @@ extern bool just_once_each_iteration_p (const stru gcov_type expected_loop_iterations_unbounded (const struct loop *); extern unsigned expected_loop_iterations (const struct loop *); extern rtx doloop_condition_get (rtx); +extern bool expected_loop_iterations_reliable_p (const struct loop *); - /* Loop manipulation. */ extern bool can_duplicate_loop_p (const struct loop *loop); Index: gcc/cfgloopanal.c =================================================================== --- gcc/cfgloopanal.c (revision 210717) +++ gcc/cfgloopanal.c (working copy) @@ -285,6 +285,15 @@ expected_loop_iterations (const struct loop *loop) return (expected > REG_BR_PROB_BASE ? REG_BR_PROB_BASE : expected); } +/* Returns true if the loop header's profile count is smaller than expected + loop iteration. */ + +bool +expected_loop_iterations_reliable_p (const struct loop *loop) +{ + return expected_loop_iterations (loop) < loop->header->count; +} + /* Returns the maximum level of nesting of subloops of LOOP. */ unsigned Index: gcc/loop-unroll.c =================================================================== --- gcc/loop-unroll.c (revision 210717) +++ gcc/loop-unroll.c (working copy) @@ -988,6 +988,15 @@ decide_unroll_runtime_iterations (struct loop *loo return; } + if (profile_status_for_fn (cfun) == PROFILE_READ + && expected_loop_iterations_reliable_p (loop)) + { + if (dump_file) + fprintf (dump_file, ";; Not unrolling loop, loop iteration " + "not reliable."); + return; + } + /* Check whether the loop rolls. */ if ((get_estimated_loop_iterations (loop, &iterations) || get_max_loop_iterations (loop, &iterations))