From e22db94a8f5d5ae6bbfecdd1a340924d7067a584 Mon Sep 17 00:00:00 2001
From: Geoff Berry <gberry@codeaurora.org>
Date: Thu, 9 Feb 2017 18:28:17 +0000
Subject: [PATCH] [SelectionDAG] Fix bugs in inverted condition splitting code.

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.

Reviewers: bogner, MatzeB, qcolombet

Subscribers: mcrosier, uabelho, llvm-commits

Differential Revision: https://reviews.llvm.org/D29680

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@294605 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../SelectionDAG/SelectionDAGBuilder.cpp      | 10 +--
 test/CodeGen/AArch64/br-cond-not-merge.ll     | 70 +++++++++++++++++--
 2 files changed, 72 insertions(+), 8 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 1cd4b48f3d6..5966069d31b 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -1638,10 +1638,12 @@ void SelectionDAGBuilder::FindMergedConditions(const Value *Cond,
   // 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,
-                         !InvertCond);
-    return;
+    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);
diff --git a/test/CodeGen/AArch64/br-cond-not-merge.ll b/test/CodeGen/AArch64/br-cond-not-merge.ll
index be8797176e6..bf21ef30790 100644
--- a/test/CodeGen/AArch64/br-cond-not-merge.ll
+++ b/test/CodeGen/AArch64/br-cond-not-merge.ll
@@ -1,14 +1,17 @@
-; 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:
@@ -28,5 +31,64 @@ bb3:
   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
+}
 
-- 
2.50.1