This is an archive of the discontinued LLVM Phabricator instance.

[BPI] Improve static heuristics for integer comparisons with CST and non-CST
Needs RevisionPublic

Authored by xbolva00 on Aug 15 2020, 3:31 AM.

Details

Reviewers
ebrevnov
Summary

For integers a == B/CST is usually false.

This heuristic is part of many papers about static branch prediction. GCC also uses this heuristic for C \ {0, 1}, since 0, 1 constants are often used as bools.

Tested with zstd bench, decompression speed was improved a bit.

Diff Detail

Event Timeline

xbolva00 created this revision.Aug 15 2020, 3:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 15 2020, 3:31 AM
xbolva00 requested review of this revision.Aug 15 2020, 3:31 AM
ebrevnov added inline comments.Aug 16 2020, 11:18 PM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

Looks like I misread this code originally. I thought the intent was to set "likely" if equal and "unlikely" if not. But as I understand now isTrueWhenEqual does completely different thing. I would suggest reverting this ASAP and rework.

980

Looks like we want to set "likely" for equal and "unlikely" not equal regardless of actual value of a constant, right? In that case I would suggest to just check that case before processing specific constant values. Moreover recently added code at line 882 should be checking exactly the same condition for not constant values, right?

xbolva00 added inline comments.Aug 17 2020, 12:29 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

All perf inprovement is gone when only == is unlikely. So atleast the comment should be fixed.

980

I got perf regression when I used same condition from line 882.

xbolva00 added inline comments.Aug 17 2020, 12:53 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
980

Looks like we want to set "likely" for equal and "unlikely" not equal regardless of actual value of a constant, right? In that case I would suggest to just check that case before processing specific constant values.

Probably we should leave special cases 0, 1, -1.

For example, X <= 0 -> Unlikely, but X >= 0 -> Likely.

ebrevnov added inline comments.Aug 17 2020, 1:38 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

It should be not only == is unlikely, but != is likely as well. Doesn't this help?
What exact condition you have for which you need to set probabilities?

980

Probably we should leave special cases 0, 1, -1.

Sure, we shouldn't touch anything except EQ and NE at least in this patch. I don't see any difference how 0, 1, -1 are handled fro EQ and NE.

For example, X <= 0 -> Unlikely, but X >= 0 -> Likely.

That looks I bit strange to me that positive numbers is more likely than negative....but anyway this is existing heuristic we should not touch with out strong arguments.

980

Let me clarify. I'm not suggesting to use the same condition as it is at line 882. Quite opposite. I think condition at line 882 is not correct in its current form. It should be fixed to handle EQ and NE cases only. If you don't get expected improvements with that let's look at what type of comparison you want to set probabilities for.

xbolva00 added inline comments.Aug 17 2020, 1:52 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

if (CI->isTrueWhenEqual())

so in this case
X == Y / X >= Y / X <= Y -> Unlikely

Otherwise likely.

When I used
if (Pred == EQ) then unlikely else likely, I got perf problems. So I think that LT/GT are key predicates which helps us here.

ebrevnov added inline comments.Aug 17 2020, 2:13 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

if (CI->isTrueWhenEqual())

so in this case
X == Y / X >= Y / X <= Y -> Unlikely

You set unlikely to both X>=Y and X<=Y. That doesn't make any sense to me. Moreover I don't see prerequisites to predict any of these to be more or less likely. If in you case that happen to be the case you probably can come up with an extra analysis to match the pattern. Another thing to consider is balance between complexity of analysis and expected gain.

Otherwise likely.

When I used
if (Pred == EQ) then unlikely else likely, I got perf problems.

Don't do "else likely" part. What I'm suggesting is:
if (Pred == EQ) unlikely;
else if (Pred == NE) likely;
else unset;

So I think that LT/GT are key predicates which helps us here.

You can't predict which one holds in general. In other words why a>b is more likely than a< b? Is there any specific in your application which can help to favor one but not the other?

xbolva00 updated this revision to Diff 285945.Aug 17 2020, 2:24 AM

New logic

xbolva00 added inline comments.Aug 17 2020, 2:25 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

Ok, see updated patch.

Decompression speed is now smaller a bit, but compression speed was improved a bit.

(I will update all codegen tests after we all agree with direction of this patch)

ebrevnov added inline comments.Aug 17 2020, 4:58 AM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
885

Last thing I'm asking for is to merge processing of EQ & NE for constant and non-constant cases. In other words you should be able to do the following:

if (CI->isEquality()) {
  if (CI->getPredicate() == CmpInst::ICMP_EQ)
    std::swap(TakenProb, UntakenProb);
  setEdgeProbability(
        BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
  return true;
}

if (!CV)
  return false;

And remove all the following code dealing with EQ & NE.

908

This branch shouldn't be needed if we handle EQ & NE for arbitrary integers above.

931

Shouldn't be needed if we handle EQ & NE for arbitrary integers above.

xbolva00 updated this revision to Diff 285994.Aug 17 2020, 6:05 AM
xbolva00 retitled this revision from [BPI] Improve static heuristics for integer comparisons with CST to [BPI] Improve static heuristics for integer comparisons with CST and non-CST.
xbolva00 edited the summary of this revision. (Show Details)
xbolva00 marked 3 inline comments as done.

I think this should be put on hold until D85781 reworked and relanded again.

ebrevnov requested changes to this revision.Dec 23 2020, 7:24 AM
This revision now requires changes to proceed.Dec 23 2020, 7:24 AM