AArch64FastISel: Use cbz/cbnz to branch on i1

[MatzeB]

Summary

In the case of a conditional branch without a preceding cmp or similar we
used to emit a "and; cmp; b.eq/b.ne" sequence, use tbz/tbnz instead.

rdar://18783875

[t.p.northover]

I don't think this is quite right. The i1 content of a register is only the low bit, isn't it? This is most easily seen outside Darwin (we're the only ones that extend incoming paramters in the caller), but I think this gets miscompiled even for us:

define i32 @foo(i32 %in) {
entry:
  %val = trunc i32 %in to i1
  br label %do_test

do_test:
  %tst = phi i1 [%val, %entry]
  br i1 %tst, label %true, label %false

true:

  ret i32 0

false:
  ret i32 1
}

So I think we really do need the TBZ for correctness.

[MatzeB]

In D15122#299704, @t.p.northover wrote:

I don't think this is quite right. The i1 content of a register is only the low bit, isn't it? This is most easily seen outside Darwin (we're the only ones that extend incoming paramters in the caller), but I think this gets miscompiled even for us:

define i32 @foo(i32 %in) {
entry:
  %val = trunc i32 %in to i1
  br label %do_test

do_test:
  %tst = phi i1 [%val, %entry]
  br i1 %tst, label %true, label %false

true:

  ret i32 0

false:
  ret i32 1
}

So I think we really do need the TBZ for correctness.

I tried your example and even the non-fast-isel produce by "llc -march arm64 -O0" seems to use plain cbz, is this a bug?

I was looking at TargetLowering::getBooleanContents() comments: "For targets without i1 registers, this gives the nature of the high-bits of boolean values held in types wider than i1." for aarch64 this is "ZeroOrOneBooleanContent".
Is it wrong to rely on this in this context? I admit this warrants an assert(getBooleanContents() != UndefinedBooleanContents) to express my reasoning.

[MatzeB]

After discussing this with Tim, I realized that the "getBooleanContents() properties" are only guaranteed only for the usual boolean inputs of branches/selects/... and only after selection DAG legalization. So we shouldn't rely on that in the FastISel variants and I changed the code to use tbz/tbnz which should be as efficient anyway.

This new version also removes a BrCond(Trunc) special case which was creating more complicated code than the default case now.

(I also see no regressions on the test-suite with this patch).

[t.p.northover]

This looks fine to me. Thanks for updating the patch!

Tim.

lib/Target/AArch64/AArch64FastISel.cpp

bool AArch64FastISel::selectBranch(const Instruction *I) {
 
   // We've been divorced from our compare!  Our block was split, and
   // now our compare lives in a predecessor block.  We musn't
   // re-compare here, as the children of the compare aren't guaranteed
   // live across the block boundary (we *could* check for this).
   // Regardless, the compare has been done in the predecessor block,
   // and it left a value for us in a virtual register.  Ergo, we test
   // the one-bit value left in the virtual register.
-  //
-  // FIXME: Optimize this with TBZW/TBZNW.
-  unsigned ANDReg = emitAnd_ri(MVT::i32, CondReg, CondRegIsKill, 1);
-  assert(ANDReg && "Unexpected AND instruction emission failure.");
-  emitICmp_ri(MVT::i32, ANDReg, /*IsKill=*/true, 0);
 
+  // i1 conditions come as an i32 value which we can use as input for cbnzw.
+  assert(CC == AArch64CC::NE);
+  unsigned Opcode = AArch64::CBNZW;
   if (FuncInfo.MBB->isLayoutSuccessor(TBB)) {
     std::swap(TBB, FBB);
-    CC = AArch64CC::EQ;
+    Opcode = AArch64::CBZW;
   }
 
-  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AArch64::Bcc))
-      .addImm(CC)
+  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(Opcode))
+      .addReg(CondReg, getKillRegState(CondRegIsKill))
       .addMBB(TBB);
 
   finishCondBranch(BI->getParent(), TBB, FBB);
   return true;
 }
 
 bool AArch64FastISel::selectIndirectBr(const Instruction *I) {
   const IndirectBrInst *BI = cast<IndirectBrInst>(I);

test/CodeGen/AArch64/fast-isel-branch-cond-split.ll

 ; If the branch is unpredictable, don't add another branch.
 
 ; CHECK-LABEL: test_or_unpredictable
 ; CHECK:       cmp   w0, #0
 ; CHECK-NEXT:  cset  w8, eq
 ; CHECK-NEXT:  cmp   w1, #0
 ; CHECK-NEXT:  cset  w9, eq
 ; CHECK-NEXT:  orr   w8, w8, w9
-; CHECK-NEXT:  and   w8, w8, #0x1
-; CHECK-NEXT:  cmp   w8, #0
-; CHECK-NEXT:  b.ne 
+; CHECK-NEXT:  cbnz w8
 define i64 @test_or_unpredictable(i32 %a, i32 %b) {
 bb1:
   %0 = icmp eq i32 %a, 0
   %1 = icmp eq i32 %b, 0
   %or.cond = or i1 %0, %1
   br i1 %or.cond, label %bb3, label %bb4, !unpredictable !2
 
 bb3:
   ret i64 0
 
 bb4:
   %2 = call i64 @bar()
   ret i64 %2
 }
 
 ; CHECK-LABEL: test_and_unpredictable
 ; CHECK:       cmp   w0, #0
 ; CHECK-NEXT:  cset  w8, ne
 ; CHECK-NEXT:  cmp   w1, #0
 ; CHECK-NEXT:  cset  w9, ne
 ; CHECK-NEXT:  and   w8, w8, w9
-; CHECK-NEXT:  and   w8, w8, #0x1
-; CHECK-NEXT:  cmp   w8, #0
-; CHECK-NEXT:  b.eq 
+; CHECK-NEXT:  cbz w8
 define i64 @test_and_unpredictable(i32 %a, i32 %b) {
 bb1:
   %0 = icmp ne i32 %a, 0
   %1 = icmp ne i32 %b, 0
   %or.cond = and i1 %0, %1
   br i1 %or.cond, label %bb4, label %bb3, !unpredictable !2
 
 bb3: