[BPI] Improve static heuristics for integer comparisons

[xbolva00]

Summary

Similarly as for pointers, even for integers a == b is usually false.

GCC also uses this heuristic.

[ebrevnov]

Any perf data?

llvm/lib/Analysis/BranchProbabilityInfo.cpp

880

I think we better avoid extending the scope of 'isProb' variable. Please either introduce scope local variable or just use CI->isTrueWhenEqual directly in the 'if'.

[xbolva00]

In D85781#2212243, @ebrevnov wrote:

Any perf data?

I observed nice improvement for zstd with silesia dataset.

Perf data: https://pastebin.com/N1JEzCMm

Decompression speed was improved quite significatly. ~ 940 MB/s -> 970 - 980 MB/s

[xbolva00]

Addressed review notes.

[ebrevnov]

LGTM

[davidxl]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

876

Perhaps change ZH_TAKEN_WEIGHT to IH_TAKEN_WEIGHT. Similarly for ZH_NONTAKEN_WEIGHT

[ebrevnov]

How your last commit differs from the approved one? Why you have so many additional changes in the tests?

[xbolva00]

In D85781#2220576, @ebrevnov wrote:

How your last commit differs from the approved one? Why you have so many additional changes in the tests?

Patch affects many codegen tests so I updated them mostly with updater scripts.

[ebrevnov]

In D85781#2220627, @xbolva00 wrote:

In D85781#2220576, @ebrevnov wrote:

How your last commit differs from the approved one? Why you have so many additional changes in the tests?

Patch affects many codegen tests so I updated them mostly with updater scripts.

The question is why changes for these tests were not part of original review? Did you just missed to upload them or changes appeared later?

[xbolva00]

Missed. Some files were adjusted to be regenerated with update scripts, so some changes are bigger than needed.

[MaskRay]

Some tests have non-trivial changes. Some tests are actually enhanced. In this case, it'd be nice if a separate review (or just a commit, depending on the nature of the updates) to improve the tests first. Then this review can show the differences. It would be easier for a reader to understand the improvement (and also makes reverts easier if this turns out to be insufficient)

[lebedev.ri]

In D85781#2221997, @MaskRay wrote:

Some tests have non-trivial changes. Some tests are actually enhanced. In this case, it'd be nice if a separate review (or just a commit, depending on the nature of the updates) to improve the tests first. Then this review can show the differences. It would be easier for a reader to understand the improvement (and also makes reverts easier if this turns out to be insufficient)

FWIW i've already previously provided such feedback at least in https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20200810/819028.html,
before https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20200810/819138.html happened, and i *think* before that too.
But it seems like the feedback isn't being heard. I'm not sure what the problem is.

[xbolva00]

Feedback arrived after things landed. Should I revert everything and split it to many patches and reland?

https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20200810/819028.html

Strange (?). I did not receive this mail. Next time please comment on Phab.

[davidxl]

I suggest the following steps to commit this patch:

1. add an internal option to turn on the new heuristics with default to

false;

2. commit the patch with minimal test changes;

3. for each target affected, explicitly modify the tests with the option

turned on and ask the target owner to examine the changes

4. once all tests are fixed (with option explicitly turned on), flip the

option on by default;

5. remove the explicit option added in step 3).

[xbolva00]

In D85781#2222094, @davidxl wrote:

I suggest the following steps to commit this patch:

1. add an internal option to turn on the new heuristics with default to

false;

2. commit the patch with minimal test changes;

3. for each target affected, explicitly modify the tests with the option

turned on and ask the target owner to examine the changes

4. once all tests are fixed (with option explicitly turned on), flip the

option on by default;

5. remove the explicit option added in step 3).

Good idea, thanks!

[lebedev.ri]

In D85781#2222087, @xbolva00 wrote:

Feedback arrived after things landed. Should I revert everything and split it to many patches and reland?

https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20200810/819028.html

Strange (?). I did not receive this mail.

Hm, are you not subscribed to/looking through llvm-commits mails?

Next time please comment on Phab.

[xbolva00]

No. But I got mails from Eli or Tom.

Dňa 17. 8. 2020 o 21:06 užívateľ Roman Lebedev via Phabricator <[e-mail]> napísal:

lebedev.ri added a comment.

In D85781#2222087 https://reviews.llvm.org/D85781#2222087, @xbolva00 wrote:

Feedback arrived after things landed. Should I revert everything and split it to many patches and reland?

https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20200810/819028.html

Strange (?). I did not receive this mail.

Hm, are you not subscribed to/looking through llvm-commits mails?

Next time please comment on Phab.

Repository:
rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D85781/new/

https://reviews.llvm.org/D85781

llvm/include/llvm/Analysis/BranchProbabilityInfo.h

void computePostDominatedByUnreachable(const Function &F,
                                          PostDominatorTree *PDT);
   void computePostDominatedByColdCall(const Function &F,
                                       PostDominatorTree *PDT);
   bool calcUnreachableHeuristics(const BasicBlock *BB);
   bool calcMetadataWeights(const BasicBlock *BB);
   bool calcColdCallHeuristics(const BasicBlock *BB);
   bool calcPointerHeuristics(const BasicBlock *BB);
   bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI);
-  bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
+  bool calcIntegerHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
   bool calcFloatingPointHeuristics(const BasicBlock *BB);
   bool calcInvokeHeuristics(const BasicBlock *BB);
 };
 
 /// Analysis pass which computes \c BranchProbabilityInfo.
 class BranchProbabilityAnalysis
     : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
   friend AnalysisInfoMixin<BranchProbabilityAnalysis>;

llvm/lib/Analysis/BranchProbabilityInfo.cpp

if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
     for (unsigned SuccIdx : UnlikelyEdges)
       EdgeProbabilities[SuccIdx] = Prob;
   }
 
   setEdgeProbability(BB, EdgeProbabilities);
   return true;
 }
 
-bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
+bool BranchProbabilityInfo::calcIntegerHeuristics(const BasicBlock *BB,
                                                const TargetLibraryInfo *TLI) {
   const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();
   ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
   if (!CI)
     return false;
 
   auto GetConstantInt = [](Value *V) {
     if (auto *I = dyn_cast<BitCastInst>(V))
       return dyn_cast<ConstantInt>(I->getOperand(0));
     return dyn_cast<ConstantInt>(V);
   };
 
+  BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
+                              ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+  BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT,
+                                ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+  bool isProb;
   Value *RHS = CI->getOperand(1);
   ConstantInt *CV = GetConstantInt(RHS);
-  if (!CV)
-    return false;
+  if (!CV) {
+    // X == Y -> Unlikely
+    // X != Y -> Likely
+    isProb = !CI->isTrueWhenEqual();
+
+    if (!isProb)
+      std::swap(TakenProb, UntakenProb);
+    setEdgeProbability(
+        BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+    return true;
+  }
 
   // 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
case CmpInst::ICMP_SGT:
       break;
     default:
       return false;
     }
   } else {
     return false;
   }
 
-  BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
-                              ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
-  BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT,
-                                ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
   if (!isProb)
     std::swap(TakenProb, UntakenProb);
 
   setEdgeProbability(
       BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
   return true;
 }
 
for (auto BB : post_order(&F.getEntryBlock())) {
     if (calcUnreachableHeuristics(BB))
       continue;
     if (calcColdCallHeuristics(BB))
       continue;
     if (calcLoopBranchHeuristics(BB, LI))
       continue;
     if (calcPointerHeuristics(BB))
       continue;
-    if (calcZeroHeuristics(BB, TLI))
+    if (calcIntegerHeuristics(BB, TLI))
       continue;
     if (calcFloatingPointHeuristics(BB))
       continue;
   }
 
   PostDominatedByUnreachable.clear();
   PostDominatedByColdCall.clear();
   SccI.reset();

llvm/test/Analysis/BranchProbabilityInfo/integer_heuristics.ll

for.inc:
   %tmp7 = phi i32 [ %tmp4, %for.body ], [ %lnot.ext, %if.then ]
   %inc = add nuw nsw i32 %inc.iv, 1
   %cmp9 = icmp ult i32 %inc, 401
   br i1 %cmp9, label %for.body, label %exit
 
 exit:
   ret void
 }
+
+declare void @foo() 
+
+define i32 @foo1(i32 %x, i32 %y, i8 signext %z, i8 signext %w) {
+entry: 
+  %c = icmp eq i32 %x, %y
+  br i1 %c, label %then, label %else
+; CHECK: edge entry -> then probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge entry -> else probability is 0x50000000 / 0x80000000 = 62.50%
+then:
+  tail call void @foo()
+  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
+}
+
+define i32 @foo2(i32 %x, i32 %y, i8 signext %z, i8 signext %w) {
+entry: 
+  %c = icmp ne 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%
+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
+}

llvm/test/Analysis/BranchProbabilityInfo/loop.ll

for.body.lr.ph:
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.body:
   %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
   %0 = load i32, i32* %c, align 4
   %cmp1 = icmp eq i32 %0, %i.011
   br i1 %cmp1, label %for.inc5, label %if.end
-; CHECK: edge for.body -> for.inc5 probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge for.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge for.body -> for.inc5 probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge for.body -> if.end probability is 0x50000000 / 0x80000000 = 62.50%
 
 if.end:
   call void @g1()
   br i1 %cmp38, label %for.body4, label %for.end
 ; CHECK: edge if.end -> for.body4 probability is 0x50000000 / 0x80000000 = 62.50%
 ; CHECK: edge if.end -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body4:

 ; CHECK: edge for.body -> for.body3 probability is 0x50000000 / 0x80000000 = 62.50%
 ; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
 
 for.body3:
   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %0 = load i32, i32* %c, align 4
   %cmp4 = icmp eq i32 %0, %j.017
   br i1 %cmp4, label %for.inc, label %if.end
-; CHECK: edge for.body3 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge for.body3 -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge for.body3 -> for.inc probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge for.body3 -> if.end probability is 0x50000000 / 0x80000000 = 62.50%
 
 if.end:
   %1 = load i32, i32* %arrayidx5, align 4
   %cmp6 = icmp eq i32 %1, %j.017
   br i1 %cmp6, label %for.inc, label %if.end8
-; CHECK: edge if.end -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge if.end -> if.end8 probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge if.end -> for.inc probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge if.end -> if.end8 probability is 0x50000000 / 0x80000000 = 62.50%
 
 if.end8:
   %2 = load i32, i32* %arrayidx9, align 4
   %cmp10 = icmp eq i32 %2, %j.017
   br i1 %cmp10, label %for.inc, label %if.end12
-; CHECK: edge if.end8 -> for.inc probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge if.end8 -> if.end12 probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge if.end8 -> for.inc probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge if.end8 -> if.end12 probability is 0x50000000 / 0x80000000 = 62.50%
 
 if.end12:
   call void @g2()
   br label %for.inc
 ; CHECK: edge if.end12 -> for.inc probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 for.inc:
   %inc = add nsw i32 %j.017, 1