Re: [tree-ssa] cfg.texi needs reviewing by a native speaker (Was: Re: "Documentation by paper")

[law at redhat dot com]

In message <20040209231001.GQ20341@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> And if you insert it (carefully making sure that it only applies to user
 >> written gotos) then it still loses badly.  I haven't investigated why.
 >
 >How did you get the trick?
Ignore jumps to targets with DECL_ARTIFICIAL set.

 >The high level predictions needs to be lowered before CFG is cleaned up
 >and optimized in general, so if we do some pretty aggressive
 >optimizations before doing so, we can expect surprises.
 >It don't lose on mainline at all (I dimply recall that perl has been one
 >of benchmarks benefiting a lot from highlevel predictors, but it is long
 >ago and my memory is biassed)
About 40% of perl's dynamic branches are _not_ predicted.  Those fall into
a few key categories:

  1. We need to predict the branch which checks for the range on a switch
     table.  My gut tells me that this branch is going to be rarely taken
     (ie, choose the fallthru path with the indirect jump for the switch rather
     than the branch around the switch).  That gut feeling certainly
     applies to perl, but I haven't checked it on a wider codebase and I
     haven't seen any papers which discuss this issue.

  2. We need to predict bit comparisons -- basically you predict that any
     specific bit is off.  This is discussed in the paper from Deitrich,
     Cheng and Hwu.    I cobbled together some code to do this and it's
     reasonably effective.

  3. We need to handle FP comparisons.  Right now GT, GE, LT, LE against
     the common constants such as -1, 0, 1 are only predicted for integer
     comparisons.  This is made somewhat more difficult by the fact that
     some architectures (ia32) don't include the FP constant in the
     comparison -- you have to walk backwards to determine that the
     second register in the comparison is actually holding one of these
     special values (and that tidbit of knowledge might be buried in a
     REG_EQUAL note).  I cobbled together some code to do this and it's
     quite effective.


Those changes radically improve the coverage of the predictors and also raise
also raise the overall hit rate from ~60% to ~75%.

There's a tree-ssa specific issue that also needs to be addressed.  tree-ssa
marks a lot more things with REG_POINTER -- particularly registers holding
pointer types which were loaded from structure fields, but which are
never dereferenced.  These are then checked against null quite often, problem
is these values are null.  So the pointer-nonnull heuristic needs some work --
note this dovetails with the findings of Deitrich, that pointers loaded from
arrays have a much higher likelihood of being null.

Now if we wanted to get really good hit rates and coverage, there is a guarded
store into an array that we do not predict, but which is taken 99% of the time.
The trick to predicting this is that the guard is a bounds check.    While
the store heuristics are rather controversial in the general form, I
wouldn't be terribly surprised to find that a bounds check guard can be
accurately predicted.


 >But probably we need to analyze_brprob both mainline and tree-ssa to see
 >how scores looks like.  Perhaps just editing predictors.def and feeding
 >in the tree-ssa values will make scores better.
Well, the biggest issue for tree-ssa at this time is the pointer heuristic
and simply having more branches which are not predictable than mainline.
Having analyze_brbrob has been quite useful.

I've got a change I'm testing which cuts down on the number of dynamic
branches for tree-ssa (making it better than mainline).  Then I've got
to figure out how to deal with the pointer problem.

jeff