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

[xbolva00]

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.

[ebrevnov]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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.

971

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]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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

971

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

[xbolva00]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

971

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]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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?

971

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.

971

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]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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]

New logic

[xbolva00]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

Ok, see updated patch.

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

[xbolva00]

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

[ebrevnov]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

882–883

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.

912

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

935

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

[ebrevnov]

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

llvm/lib/Analysis/BranchProbabilityInfo.cpp

bool BranchProbabilityInfo::calcIntegerHeuristics(const BasicBlock *BB,
   };
 
   BranchProbability TakenProb(INTH_TAKEN_WEIGHT,
                               INTH_TAKEN_WEIGHT + INTH_NONTAKEN_WEIGHT);
   BranchProbability UntakenProb(INTH_NONTAKEN_WEIGHT,
                                 INTH_TAKEN_WEIGHT + INTH_NONTAKEN_WEIGHT);
   Value *RHS = CI->getOperand(1);
   ConstantInt *CV = GetConstantInt(RHS);
   if (!CV) {
+    if (CI->isEquality()) {
       // X == Y -> Unlikely
-    // Otherwise -> Likely
+      // X != Y -> Likely
       if (CI->isTrueWhenEqual())
         std::swap(TakenProb, UntakenProb);
       setEdgeProbability(
           BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
       return true;
+    } else {
+      return false;
+    }
   }
 
   // If the LHS is the result of AND'ing a value with a single bit bitmask,
   // we don't have information about probabilities.
   if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
     if (LHS->getOpcode() == Instruction::And)
       if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
         if (AndRHS->getValue().isPowerOf2())
           return false;
 
   // Check if the LHS is the return value of a library function
   LibFunc Func = NumLibFuncs;
   if (TLI)
     if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
       if (Function *CalledFn = Call->getCalledFunction())
         TLI->getLibFunc(*CalledFn, Func);
 
   bool isProb;
   if (Func == LibFunc_strcasecmp ||
       Func == LibFunc_strcmp ||
       Func == LibFunc_strncasecmp ||
       Func == LibFunc_strncmp ||
       Func == LibFunc_memcmp ||
       Func == LibFunc_bcmp) {
     // strcmp and similar functions return zero, negative, or positive, if the
     // first string is equal, less, or greater than the second. We consider it
     // likely that the strings are not equal, so a comparison with zero is
     // probably false, but also a comparison with any other number is also
     // probably false given that what exactly is returned for nonzero values is
     // not specified. Any kind of comparison other than equality we know
     // nothing about.
     switch (CI->getPredicate()) {
     case CmpInst::ICMP_EQ:
       isProb = false;
       break;
     case CmpInst::ICMP_NE:
       isProb = true;
       break;
     default:
       return false;
     }
+  } else if (CI->isEquality()) {
+    // X == C -> Unlikely
+    // X != C -> Likely
+    isProb = !CI->isTrueWhenEqual();
   } else if (CV->isZero()) {
     switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      // X == 0   ->  Unlikely
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      // X != 0   ->  Likely
-      isProb = true;
-      break;
     case CmpInst::ICMP_SLT:
       // X < 0   ->  Unlikely
       isProb = false;
       break;
     case CmpInst::ICMP_SGT:
       // X > 0   ->  Likely
       isProb = true;
       break;
     default:
       return false;
     }
   } else if (CV->isOne()) {
     if (CI->getPredicate() == CmpInst::ICMP_SLT)
       // InstCombine canonicalizes X <= 0 into X < 1.
       // X <= 0   ->  Unlikely
       isProb = false;
     else
       return false;
   } else if (CV->isMinusOne()) {
     switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      // X == -1  ->  Unlikely
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      // X != -1  ->  Likely
-      isProb = true;
-      break;
     case CmpInst::ICMP_SGT:
       // InstCombine canonicalizes X >= 0 into X > -1.
       // X >= 0   ->  Likely
       isProb = true;
       break;
     default:
       return false;
     }
   } else {
-    // X == C -> Unlikely
-    // X != C -> Likely
-    switch (CI->getPredicate()) {
-    case CmpInst::ICMP_EQ:
-      isProb = false;
-      break;
-    case CmpInst::ICMP_NE:
-      isProb = true;
-      break;
-    default:
-      return false;
-    }
-  }
 
   if (!isProb)
     std::swap(TakenProb, UntakenProb);
 
   setEdgeProbability(
       BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
   return true;
 }

llvm/test/Analysis/BranchProbabilityInfo/integer_heuristics.ll

else:
   ret i32 %r
 }
 
 ; CHECK-LABEL: foo3
 define i32 @foo3(i32 %x, i32 %y, i8 signext %z, i8 signext %w) {
 entry: 
   %c = icmp ult i32 %x, %y
   br i1 %c, label %then, label %else
-; CHECK: edge entry -> then probability is 0x50000000 / 0x80000000 = 62.50%
-; CHECK: edge entry -> else probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge entry -> then probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge entry -> else probability is 0x40000000 / 0x80000000 = 50.00%
 then:
   br label %else
 ; CHECK: edge then -> else probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 else:
   %v = phi i8 [ %z, %then ], [ %w, %entry ]
   %r = sext i8 %v to i32
   ret i32 %r
 }