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

385

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

387

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

385

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

383–390

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) {
 
   Value *RHS = CI->getOperand(1);
   ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
   if (!CV)
     return false;
 
   bool isProb;
   if (CV->isZero()) {
     switch (CI->getPredicate()) {
     case CmpInst::ICMP_EQ:
+      {
+        Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0));
+        if (LHS && LHS->getOpcode() == Instruction::And)
+          return false;
+      }
       // X == 0   ->  Unlikely
       isProb = false;
       break;
     case CmpInst::ICMP_NE:
       // X != 0   ->  Likely
       isProb = true;
       break;
     case CmpInst::ICMP_SLT:
       // X < 0   ->  Unlikely

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

test/CodeGen/X86/atom-bypass-slow-division-64.ll

 ; RUN: llc < %s -mcpu=atom -march=x86-64 | FileCheck %s
 
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Additional tests for 64-bit divide bypass
 
 define i64 @Test_get_quotient(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient:
 ; CHECK: movq %rdi, %rax
 ; CHECK: orq %rsi, %rax
 ; CHECK-NEXT: testq $-65536, %rax
-; CHECK-NEXT: je
-; CHECK: idivq
-; CHECK: ret
+; CHECK-NEXT: jne
 ; CHECK: divw
 ; CHECK: ret
+; CHECK: idivq
+; CHECK: ret
   %result = sdiv i64 %a, %b
   ret i64 %result
 }
 
 define i64 @Test_get_remainder(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_remainder:
 ; CHECK: movq %rdi, %rax
 ; CHECK: orq %rsi, %rax
 ; CHECK-NEXT: testq $-65536, %rax
-; CHECK-NEXT: je
-; CHECK: idivq
-; CHECK: ret
+; CHECK-NEXT: jne
 ; CHECK: divw
 ; CHECK: ret
+; CHECK: idivq
+; CHECK: ret
   %result = srem i64 %a, %b
   ret i64 %result
 }
 
 define i64 @Test_get_quotient_and_remainder(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient_and_remainder:
 ; CHECK: movq %rdi, %rax
 ; CHECK: orq %rsi, %rax
 ; CHECK-NEXT: testq $-65536, %rax
-; CHECK-NEXT: je
-; CHECK: idivq
+; CHECK-NEXT: jne
 ; CHECK: divw
+; CHECK: idivq
 ; CHECK: addq
 ; CHECK: ret
 ; CHECK-NOT: idivq
 ; CHECK-NOT: divw
   %resultdiv = sdiv i64 %a, %b
   %resultrem = srem i64 %a, %b
   %result = add i64 %resultdiv, %resultrem
   ret i64 %result
 }

test/CodeGen/X86/atom-bypass-slow-division.ll

 ; RUN: llc < %s -mcpu=atom -mtriple=i686-linux | FileCheck %s
 
 define i32 @Test_get_quotient(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient:
 ; CHECK: orl %ecx, %edx
 ; CHECK-NEXT: testl $-256, %edx
-; CHECK-NEXT: je
-; CHECK: idivl
-; CHECK: ret
+; CHECK-NEXT: jne
 ; CHECK: divb
 ; CHECK: ret
+; CHECK: idivl
+; CHECK: ret
   %result = sdiv i32 %a, %b
   ret i32 %result
 }
 
 define i32 @Test_get_remainder(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: Test_get_remainder:
 ; CHECK: orl %ecx, %edx
 ; CHECK-NEXT: testl $-256, %edx
-; CHECK-NEXT: je
-; CHECK: idivl
-; CHECK: ret
+; CHECK-NEXT: jne
 ; CHECK: divb
 ; CHECK: ret
+; CHECK: idivl
+; CHECK: ret
   %result = srem i32 %a, %b
   ret i32 %result
 }
 
 define i32 @Test_get_quotient_and_remainder(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: Test_get_quotient_and_remainder:
 ; CHECK: orl %ecx, %edx
 ; CHECK-NEXT: testl $-256, %edx
-; CHECK-NEXT: je
-; CHECK: idivl
+; CHECK-NEXT: jne
 ; CHECK: divb
+; CHECK: idivl
 ; CHECK: addl
 ; CHECK: ret
 ; CHECK-NOT: idivl
 ; CHECK-NOT: divb
   %resultdiv = sdiv i32 %a, %b
   %resultrem = srem i32 %a, %b
   %result = add i32 %resultdiv, %resultrem
   ret i32 %result
 }
 
 define i32 @Test_use_div_and_idiv(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: Test_use_div_and_idiv:
+; CHECK: divb
 ; CHECK: idivl
 ; CHECK: divb
 ; CHECK: divl
-; CHECK: divb
 ; CHECK: addl
 ; CHECK: ret
   %resultidiv = sdiv i32 %a, %b
   %resultdiv = udiv i32 %a, %b
   %result = add i32 %resultidiv, %resultdiv
   ret i32 %result
 }
 
; CHECK-NOT: divb
   %resultrem = srem i32 %a, 33
   %result = add i32 %resultdiv, %resultrem
   ret i32 %result
 }
 
 define i32 @Test_use_div_imm_reg(i32 %a) nounwind {
 ; CHECK-LABEL: Test_use_div_imm_reg:
 ; CHECK: test
-; CHECK: idiv
 ; CHECK: divb
+; CHECK: idiv
   %resultdiv = sdiv i32 4, %a
   ret i32 %resultdiv
 }
 
 define i32 @Test_use_rem_imm_reg(i32 %a) nounwind {
 ; CHECK-LABEL: Test_use_rem_imm_reg:
 ; CHECK: test
-; CHECK: idiv
 ; CHECK: divb
+; CHECK: idiv
   %resultdiv = sdiv i32 4, %a
   ret i32 %resultdiv
 }

test/CodeGen/X86/peep-test-4.ll

 define zeroext i1 @sbb(i128 %x, i128 %y) nounwind {
   %sub = sub i128 %x, %y
   %cmp = icmp sge i128 %sub, 0
   ret i1 %cmp
 }
 
 ; CHECK-LABEL: andn:
 ; CHECK: andnl   %esi, %edi, %edi
-; CHECK-NEXT: je
-; CHECK: jmp foo
+; CHECK-NEXT: jne
 ; CHECK: ret
+; CHECK: jmp foo
 define void @andn(i32 %x, i32 %y) nounwind {
   %not = xor i32 %x, -1
   %andn = and i32 %y, %not
   %cmp = icmp eq i32 %andn, 0
   br i1 %cmp, label %return, label %bb
 
 bb:
   tail call void @foo(i32 %andn)