* [PATCH] Disable unroll loop that has header count less than iteration count.
@ 2014-05-22 21:36 Dehao Chen
2014-05-23 8:55 ` Richard Biener
0 siblings, 1 reply; 5+ messages in thread
From: Dehao Chen @ 2014-05-22 21:36 UTC (permalink / raw)
To: GCC Patches; +Cc: Jan Hubicka, David Li
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?
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))
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Disable unroll loop that has header count less than iteration count.
2014-05-22 21:36 [PATCH] Disable unroll loop that has header count less than iteration count Dehao Chen
@ 2014-05-23 8:55 ` Richard Biener
2014-05-23 17:26 ` Jan Hubicka
0 siblings, 1 reply; 5+ messages in thread
From: Richard Biener @ 2014-05-23 8:55 UTC (permalink / raw)
To: Dehao Chen; +Cc: GCC Patches, Jan Hubicka, David Li
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))
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Disable unroll loop that has header count less than iteration count.
2014-05-23 8:55 ` Richard Biener
@ 2014-05-23 17:26 ` Jan Hubicka
2014-05-23 17:39 ` Richard Biener
0 siblings, 1 reply; 5+ messages in thread
From: Jan Hubicka @ 2014-05-23 17:26 UTC (permalink / raw)
To: Richard Biener; +Cc: Dehao Chen, GCC Patches, Jan Hubicka, David Li
> 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))
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Disable unroll loop that has header count less than iteration count.
2014-05-23 17:26 ` Jan Hubicka
@ 2014-05-23 17:39 ` Richard Biener
2014-05-23 17:48 ` Jan Hubicka
0 siblings, 1 reply; 5+ messages in thread
From: Richard Biener @ 2014-05-23 17:39 UTC (permalink / raw)
To: Jan Hubicka; +Cc: Dehao Chen, GCC Patches, David Li
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))
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] Disable unroll loop that has header count less than iteration count.
2014-05-23 17:39 ` Richard Biener
@ 2014-05-23 17:48 ` Jan Hubicka
0 siblings, 0 replies; 5+ messages in thread
From: Jan Hubicka @ 2014-05-23 17:48 UTC (permalink / raw)
To: Richard Biener; +Cc: Jan Hubicka, Dehao Chen, GCC Patches, David Li
> >
> > 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))
>
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2014-05-23 17:48 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-22 21:36 [PATCH] Disable unroll loop that has header count less than iteration count Dehao Chen
2014-05-23 8:55 ` Richard Biener
2014-05-23 17:26 ` Jan Hubicka
2014-05-23 17:39 ` Richard Biener
2014-05-23 17:48 ` Jan Hubicka
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).