Don't pretend to have probability information if the result of a bitwise and is compared against 0

[djasper]

Summary

The code that originally made me discover this is:

if ((a & 0x1) == 0x1) {
  ..
}

In this case we don't actually have any branch probability information and should not assume to have any. LLVM transforms this into:

%and = and i32 %a, 1
%tobool = icmp eq i32 %and, 0

So, in this case, the result of a bitwise and is compared against 0. Again, we don't really have information. We could make this check more narrow, e.g. by testing whether the other and-operand is 1 or whether it has a single bit set.

[chandlerc]

This definitely seems like a good patch. A couple of high-level thoughts:

1. You can test this directly by printing the analysis. I think we have a few tests like that.

2. You should comment what is going on here and why.

3. I feel like you need to handle more cases - != 0 at least, and maybe a few others maybe with a few other math operations?

lib/Analysis/BranchProbabilityInfo.cpp

397

If you need braces, just put them around the entire case.

399

I would use o two-level if with a condition expression. I find the && trick awkward.

[djasper]

• Addressed review comments
• Extended change to look at more comparisons
• Narrowed check to only trigger on single bit bitmasks
• Added specific branch probability tests

All test changes now seem correct.

[djasper]

Ping?

lib/Analysis/BranchProbabilityInfo.cpp

397

Done.

[chandlerc]

This looks fine.

I feel like it should also be handling explicit 'i1' values as well, but that can be a separate patch.

lib/Analysis/BranchProbabilityInfo.cpp

384–391

I don't think these braces are useful, I'd omit all of them.

[djasper]

Finally submitted in r234979.

lib/Analysis/BranchProbabilityInfo.cpp

bool BranchProbabilityInfo::calcZeroHeuristics(BasicBlock *BB) {
   if (!CI)
     return false;
 
   Value *RHS = CI->getOperand(1);
   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
   if (!CV)
     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->getUniqueInteger().isPowerOf2())
+          return false;
+      }
+    }
+  }
+
   bool isProb;
   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;

test/Analysis/BranchProbabilityInfo/basic.ll

 else:
   br label %exit
 
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
 }
 
+define i32 @zero3(i32 %i, i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'zero3'
+entry:
+; AND'ing with a single bit bitmask essentially leads to a bool comparison,
+; meaning we don't have probability information.
+  %and = and i32 %i, 2
+  %tobool = icmp eq i32 %and, 0
+  br i1 %tobool, label %then, label %else
+; CHECK: edge entry -> then probability is 16 / 32
+; CHECK: edge entry -> else probability is 16 / 32
+
+then:
+; AND'ing with other bitmask might be something else, so we still assume the
+; usual probabilities.
+  %and2 = and i32 %i, 5
+  %tobool2 = icmp eq i32 %and2, 0
+  br i1 %tobool2, label %else, label %exit
+; CHECK: edge then -> else probability is 12 / 32
+; CHECK: edge then -> exit probability is 20 / 32
+
+else:
+  br label %exit
+
+exit:
+  %result = phi i32 [ %a, %then ], [ %b, %else ]
+  ret i32 %result
+}
+

test/CodeGen/AArch64/arm64-call-tailcalls.ll

 
 bb:                                               ; preds = %entry
   tail call void @foo() nounwind
   ret void
 }
 
 define i32 @t8(i32 %x) nounwind ssp {
 ; CHECK-LABEL: t8:
+; CHECK: b  _c
 ; CHECK: b  _a
 ; CHECK: b  _b
-; CHECK: b  _c
   %and = and i32 %x, 1
   %tobool = icmp eq i32 %and, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   %call = tail call i32 @a(i32 %x) nounwind
   br label %return
 

test/CodeGen/Mips/octeon.ll

; MIPS64: dsrl   $2, $[[T3]], 32
   ret i64 %res2
 }
 
 define i64 @bbit0(i64 %a) nounwind {
 entry:
 ; ALL-LABEL: bbit0:
 ; OCTEON: bbit0   $4, 3, $[[BB0:BB[0-9_]+]]
 ; MIPS64: andi  $[[T0:[0-9]+]], $4, 8
-; MIPS64: beqz  $[[T0]], $[[BB0:BB[0-9_]+]]
+; MIPS64: bnez  $[[T0]], $[[BB0:BB[0-9_]+]]
   %bit = and i64 %a, 8
   %res = icmp eq i64 %bit, 0
   br i1 %res, label %endif, label %if
 if:
   ret i64 48
 
 endif:
   ret i64 12
 }
 
 define i64 @bbit032(i64 %a) nounwind {
 entry:
 ; ALL-LABEL: bbit032:
 ; OCTEON: bbit032 $4, 3, $[[BB0:BB[0-9_]+]]
 ; MIPS64: daddiu  $[[T0:[0-9]+]], $zero, 1
 ; MIPS64: dsll    $[[T1:[0-9]+]], $[[T0]], 35
 ; MIPS64: and     $[[T2:[0-9]+]], $4, $[[T1]]
-; MIPS64: beqz    $[[T2]], $[[BB0:BB[0-9_]+]]
+; MIPS64: bnez    $[[T2]], $[[BB0:BB[0-9_]+]]
   %bit = and i64 %a, 34359738368
   %res = icmp eq i64 %bit, 0
   br i1 %res, label %endif, label %if
 if:
   ret i64 48
 
 endif:
   ret i64 12