This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Optimize n?rotate(x,n):x
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: Marc Glisse <marc dot glisse at inria dot fr>
- Cc: Jan Hubicka <hubicka at ucw dot cz>, GCC Patches <gcc-patches at gcc dot gnu dot org>, Richard Biener <richard dot guenther at gmail dot com>
- Date: Wed, 23 Apr 2014 23:19:26 +0200
- Subject: Re: Optimize n?rotate(x,n):x
- Authentication-results: sourceware.org; auth=none
- References: <alpine dot DEB dot 2 dot 02 dot 1403011240500 dot 28536 at stedding dot saclay dot inria dot fr> <CAFiYyc2wWfrV4kMMewyBzz6m55jZW2TxmiD6x0sqtombs+OLYA at mail dot gmail dot com> <alpine dot DEB dot 2 dot 10 dot 1404131432090 dot 3577 at laptop-mg dot saclay dot inria dot fr> <CAFiYyc0grD-PGzgt3GQ5H76JnMFnsQy=pPicMu3sqjehtKU6Fw at mail dot gmail dot com> <alpine dot DEB dot 2 dot 10 dot 1404141703140 dot 3714 at laptop-mg dot saclay dot inria dot fr> <CAFiYyc3kcrmuw468kDp1fsRGDHTfQ376fovTKB5LYcnnQ3dzEg at mail dot gmail dot com> <alpine dot DEB dot 2 dot 10 dot 1404232021490 dot 4018 at laptop-mg dot saclay dot inria dot fr>
> Honza, any comment on Richard's question?
>
> On Tue, 15 Apr 2014, Richard Biener wrote:
>
> >On Mon, Apr 14, 2014 at 6:40 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> >>On Mon, 14 Apr 2014, Richard Biener wrote:
> >>
> >>>>+ /* If the special case has a high probability, keep it. */
> >>>>+ if (EDGE_PRED (middle_bb, 0)->probability < PROB_EVEN)
> >>>
> >>>
> >>>I suppose Honza has a comment on how to test this properly
> >>>(not sure if ->probability or ->frequency is always initialized properly).
> >>>for example single_likely_edge tests profile_status_for_fn !=
> >>>PROFILE_ABSENT (and uses a fixed probability value ...).
> >>>Anyway, the comparison looks backwards to me, but maybe I'm
> >>>missing sth - I'd use >= PROB_LIKELY ;)
> >>
> >>
> >>Maybe the comment is confusing? middle_bb contains the expensive operation
> >>(say a/b) that the special case skips entirely. If the division happens in
> >>less than 50% of cases (that's the proba of the edge going from cond to
> >>middle_bb), then doing the comparison+jump may be cheaper and I abort the
> >>optimization. At least the testcase with __builtin_expect should prove that
> >>I didn't do it backwards.
> >
> >Ah, indeed. My mistake.
> >
> >>value-prof seems to use 50% as the cut-off where it may become interesting
> >>to special case division, hence my choice of PROB_EVEN. I am not sure which
> >>way you want to use PROB_LIKELY (80%). If we have more than 80% chances of
> >>executing the division, always perform it? Or if we have more than 80%
> >>chances of skipping the division, keep the branch?
> >
> >Ok, if it's from value-prof then that's fine.
> >
> >The patch is ok if Honza doesn't have any comments on whether it's ok
> >to look at ->probability unconditionally.
> >
> >Thanks,
> >Richard.
> >
> >>+
> >>+ /* Now optimize (x != 0) ? x + y : y to just y.
> >>+ The following condition is too restrictive, there can easily be
> >>another
> >>+ stmt in middle_bb, for instance a CONVERT_EXPR for the second
> >>argument. */
> >>+ gimple assign = last_and_only_stmt (middle_bb);
> >>+ if (!assign || gimple_code (assign) != GIMPLE_ASSIGN
> >>+ || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
> >>+ || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
> >>+ && !POINTER_TYPE_P (TREE_TYPE (arg0))))
> >>+ return 0;
> >>+
> >>+ /* assign may call a libgcc routine, which is slow. */
> >>+ if (!is_cheap_stmt (assign) && is_cheap_stmt (cond))
> >>+ return 0;
> >>+
> >>+ /* If the special case has a high probability, keep it. */
> >>+ if (EDGE_PRED (middle_bb, 0)->probability < PROB_EVEN)
> >>+ return 0;
Well, I would expect this transformation to be win always, + operation
is virtually for free.
Concerning profile - you must consider two cases. If the profile is guessed
then the probability is most probably 71% to the non-zero case unless user used
an expect (since I would expect only PRED_OPCODE_NONEQUAL to match). This is
data dependent branch unless this sits in a loop and those are badly predicted
statically.
If the probability is read, then probabilities over (say) 10% and less than 90%
means that the branch is likely not very well predictable (it still may be on
advanced architectures if it is predictable from context) and getting rid of it
is a good idea.
So if you want to disable the optimization for x being likely zero, I guess
testing that probability is over PROV_LIKELY is a resonable threshold - it will
handle both builtin_expect and the (very) badly predictable branches.
Maybe for FDO it should be higher, but we would need to do some research on it
that is probably not worth the effort.
The division transformation is bit different story, since cost of division is
more than cost of branch and the 50% threshold is a limit for one value
counter to be reliable.
Honza