This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Optimize n?rotate(x,n):x


> 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]