[SelectionDAG] Fix bugs in inverted condition splitting code.

[gberry]

Summary

Fix two bugs in SelectionDAGBuilder::FindMergedConditions reported by
Mikael Holmen. Handle non-canonicalized xor not operation
correctly (was assuming operand 0 was always the non-constant operand)
and check that the negated condition is also in the same block as the
original and/or instruction (as is done for and/or operands already)
before proceeding with optimization.

[hans]

Are there PRs for the reported bugs, or where were they reported? I'm trying to understand whether this is fixing a regression from 3.9 or not.

[gberry]

In D29680#669885, @hans wrote:

Are there PRs for the reported bugs, or where were they reported? I'm trying to understand whether this is fixing a regression from 3.9 or not.

@hans Sorry for the noise, but I just checked and these bugs were introduced after the release_40 branch, so you can ignore my request to include this patch.

[hans]

In D29680#669897, @gberry wrote:

In D29680#669885, @hans wrote:

Are there PRs for the reported bugs, or where were they reported? I'm trying to understand whether this is fixing a regression from 3.9 or not.

@hans Sorry for the noise, but I just checked and these bugs were introduced after the release_40 branch, so you can ignore my request to include this patch.

OK, thanks.

[uabelho]

I tried the patch and it solves the problem I saw.

[nemanjai]

This also fixes https://llvm.org/bugs/show_bug.cgi?id=31914.

[gberry]

I'm going to go ahead and check this in as an obvious fix since it fixes breakages for at least two targets.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::FindMergedConditions(const Value *Cond,
                                                MachineBasicBlock *SwitchBB,
                                                Instruction::BinaryOps Opc,
                                                BranchProbability TProb,
                                                BranchProbability FProb,
                                                bool InvertCond) {
   // Skip over not part of the tree and remember to invert op and operands at
   // next level.
   if (BinaryOperator::isNot(Cond) && Cond->hasOneUse()) {
-    Cond = cast<Instruction>(Cond)->getOperand(0);
-    FindMergedConditions(Cond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
+    const Value *CondOp = BinaryOperator::getNotArgument(Cond);
+    if (InBlock(CondOp, CurBB->getBasicBlock())) {
+      FindMergedConditions(CondOp, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
                            !InvertCond);
       return;
     }
+  }
 
   const Instruction *BOp = dyn_cast<Instruction>(Cond);
   // Compute the effective opcode for Cond, taking into account whether it needs
   // to be inverted, e.g.
   //   and (not (or A, B)), C
   // gets lowered as
   //   and (and (not A, not B), C)
   unsigned BOpc = 0;

test/CodeGen/AArch64/br-cond-not-merge.ll

-; RUN: llc -mtriple=aarch64 -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -mtriple=aarch64 -verify-machineinstrs < %s | FileCheck --check-prefix=CHECK --check-prefix=OPT %s
+; RUN: llc -mtriple=aarch64 -verify-machineinstrs -O0 -fast-isel=0 < %s | FileCheck --check-prefix=CHECK --check-prefix=NOOPT %s
 
 declare void @foo()
 
 ; Check that the inverted or doesn't inhibit the splitting of the
 ; complex conditional into three branch instructions.
-; CHECK-LABEL: test_and_not
+; CHECK-LABEL: test_and_not:
 ; CHECK:       cbz w0, [[L:\.LBB[0-9_]+]]
-; CHECK:       cmp w1, #2
+; OPT:         cmp w1, #2
+; NOOPT:       subs w{{[0-9]+}}, w{{[0-9]+}}, #2
 ; CHECK:       b.lo [[L]]
-; CHECK:       cmp w2, #2
+; OPT:         cmp w2, #2
+; NOOPT:       subs w{{[0-9]+}}, w{{[0-9]+}}, #2
 ; CHECK:       b.hi [[L]]
 define void @test_and_not(i32 %a, i32 %b, i32 %c) {
 bb1:
   %cmp1 = icmp ult i32 %a, 1
   %cmp2 = icmp ult i32 %b, 2
   %cmp3 = icmp ult i32 %c, 3
   %or = or i1 %cmp1, %cmp2
   %not.or = xor i1 %or, -1
   %and = and i1 %not.or, %cmp3
   br i1 %and, label %bb2, label %bb3
 
 bb2:
   ret void
 
 bb3:
   call void @foo()
   ret void
 }
 
+; Check that non-canonicalized xor not is handled correctly by FindMergedConditions.
+; CHECK-LABEL: test_and_not2:
+; CHECK:       cbz w0, [[L:\.LBB[0-9_]+]]
+; OPT:         cmp w1, #2
+; NOOPT:       subs w{{[0-9]+}}, w{{[0-9]+}}, #2
+; CHECK:       b.lo [[L]]
+; OPT:         cmp w2, #2
+; NOOPT:       subs w{{[0-9]+}}, w{{[0-9]+}}, #2
+; CHECK:       b.hi [[L]]
+define void @test_and_not2(i32 %a, i32 %b, i32 %c) {
+bb1:
+  %cmp1 = icmp ult i32 %a, 1
+  %cmp2 = icmp ult i32 %b, 2
+  %cmp3 = icmp ult i32 %c, 3
+  %or = or i1 %cmp1, %cmp2
+  %not.or = xor i1 -1, %or
+  %and = and i1 %not.or, %cmp3
+  br i1 %and, label %bb2, label %bb3
+
+bb2:
+  ret void
+
+bb3:
+  call void @foo()
+  ret void
+}
+
+; Check that cmps in different blocks are handled correctly by FindMergedConditions.
+; CHECK-LABEL: test_cmp_other_block:
+; OPT: cmp w{{[0-9]+}}, #0
+; OPT: b.gt [[L:\.LBB[0-9_]+]]
+; OPT: tbz w1, #0, [[L]]
+;
+; NOOPT: subs w{{[0-9]+}}, w{{[0-9]+}}, #0
+; NOOPT: cset [[R1:w[0-9]+]], gt
+; NOOPT: str w1, [sp, #[[SLOT2:[0-9]+]]]
+; NOOPT: str [[R1]], [sp, #[[SLOT1:[0-9]+]]]
+; NOOPT: b .LBB
+; NOOPT: ldr [[R2:w[0-9]+]], [sp, #[[SLOT1]]]
+; NOOPT: tbnz [[R2]], #0, [[L:\.LBB[0-9_]+]]
+; NOOPT: ldr [[R3:w[0-9]+]], [sp, #[[SLOT2]]]
+; NOOPT: tbz [[R3]], #0, [[L]]
+define void @test_cmp_other_block(i32* %p, i1 %c) {
+entry:
+  %l = load i32, i32* %p
+  %cmp = icmp sgt i32 %l, 0
+  br label %bb1
+
+bb1:
+  %cmp.i = xor i1 %cmp, true
+  %or.cond1.i = and i1 %cmp.i, %c
+  br i1 %or.cond1.i, label %bb2, label %bb3
 
+bb2:
+  ret void
+
+bb3:
+  call void @foo()
+  ret void
+}