[InstCombine] Determine the result of a select based on a dominating condition.

[mcrosier]

Summary

This patch attempts to determine the result of a select based on a dominating condition. This is similar to what is done in JumpThreading and SimplifyCFG, except those passes only consider conditional branches and not selects.

AFAICT, the transformation in pr21210.ll is safe, but the comments in the lit test seem to indicate otherwise.

@Gerolf - Would you mind helping me better understand what pr21210.ll is trying to test?

I didn't run into any correctness issues with the test-suite or SPEC200X.

This also addresses PR23333.

Please take a look,
Chad

[mcrosier]

@bmakam reminded me that this will also fix PR23333.
-Add a test case accordingly.

[Gerolf]

test/Transforms/InstCombine/pr21210.ll

44 ↗

(On Diff #55068)

cond can be different from len, so you cannot replace it.
bb-> bb1 vs entry -> b1.

I think this test covers self-build issues I had ran into when I missed some cases in the icmp->select->icmp optimization which removes the select in some narrow cases.

[reames]

Mostly minor comments, once addressed should be ready to go in.

lib/Analysis/ValueTracking.cpp

3970 ↗

(On Diff #55068)

I'm confused by this bit. How do we get here? Do we have a select with a non-i1 condition? If so, maybe the check should be in the caller and we should assert both are i1s?

test/Transforms/InstCombine/pr21210.ll

34 ↗

(On Diff #55068)

Add a check that shows this select disappears.

44 ↗

(On Diff #55068)

I believe the optimization as posted is correct. Geroff, were you trying to say it wasn't? If so, I didn't understand your point. Could you explain again?

[llvm-commits]

• msg-5793-513.txt162 BDownload

[mcrosier]

Address Philip's comments:
-Added CHECK-NOT: select to all test cases
-Move the test case from pr21210.ll into select-implied.ll as I believe we all agree the test case is valid to transform and it isn't likely representative of the problem described in PR21210.
-Added a comment about why we might have a mismatch. In the 30+ examples I reviewed all were cases where we were comparing a scalar cmp against a vector compare. I imagine this case will occur in the future, so I somewhat prefer we keep the check in the callee unless you strongly object.

[mcrosier]

test/Transforms/InstCombine/pr21210.ll

25 ↗

(On Diff #55229)

I'm not exactly sure how to fix this test case so it exhibits the original problem as I don't fully understand the original problem. Therefore, I move the test case into my new test case. I can file a PR to make sure we follow up on this, but I'd prefer this issue not block this patch.

[Gerolf]

I sharpened the test case.

-Gerolf

[mcrosier]

Update patch now that pr21210.ll has been updated. Thanks, Gerolf.

[reames]

LGTM w/optional minor comment.

lib/Transforms/InstCombine/InstCombineSelect.cpp

1219 ↗

(On Diff #55268)

Minor, but this would be easier to read as:
if (BasicBlock *Dom = Parent->getSinglePredecessor()) {

auto *PBI = dyn_cast<BranchInst>(Dom->getTerminator());
if (PBI && PBI->isConditional() &&
    PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
    (PBI->getSuccessor(0) == Parent || PBI->getSuccessor(1) == Parent)) {

[bmakam]

test/Transforms/InstCombine/select-implied.ll

84 ↗

(On Diff #55229)

D18841 broke this test, because the icmp now can be folded as false. I reverted rL268521 because of this failure.
Is it reasonable to reapply rL268521 by fixing this test to reflect the new change?
So instead of CHECK: %cmp11 = icmp eq i32 %len, 8 we will now have
CHECK-NOT: %cmp11 = icmp eq i32 %{{.*}}, 8
CHECK: br i1 false, label %b0, label %b1

llvm/trunk/lib/Analysis/ValueTracking.cpp

static Optional<bool> isImpliedCondMatchingOperands(CmpInst::Predicate APred,
   return None;
 }
 
 Optional<bool> llvm::isImpliedCondition(Value *LHS, Value *RHS,
                                         const DataLayout &DL, bool InvertAPred,
                                         unsigned Depth, AssumptionCache *AC,
                                         const Instruction *CxtI,
                                         const DominatorTree *DT) {
-  assert(LHS->getType() == RHS->getType() && "mismatched type");
+  // A mismatch occurs when we compare a scalar cmp to a vector cmp, for example.
+  if (LHS->getType() != RHS->getType())
+    return None;
+
   Type *OpTy = LHS->getType();
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
   if (!InvertAPred && LHS == RHS)
     return true;
 
   if (OpTy->isVectorTy())

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (Value *V = SimplifyDemandedVectorElts(&SI, AllOnesEltMask, UndefElts)) {
       return &SI;
     }
 
     if (isa<ConstantAggregateZero>(CondVal)) {
       return replaceInstUsesWith(SI, FalseVal);
     }
   }
 
+  // See if we can determine the result of this select based on a dominating
+  // condition.
+  BasicBlock *Parent = SI.getParent();
+  if (BasicBlock *Dom = Parent->getSinglePredecessor()) {
+    auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator());
+    if (PBI && PBI->isConditional() &&
+        PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
+        (PBI->getSuccessor(0) == Parent || PBI->getSuccessor(1) == Parent)) {
+      bool CondIsFalse = PBI->getSuccessor(1) == Parent;
+      Optional<bool> Implication = isImpliedCondition(
+        PBI->getCondition(), SI.getCondition(), DL, CondIsFalse);
+      if (Implication) {
+        Value *V = *Implication ? TrueVal : FalseVal;
+        return replaceInstUsesWith(SI, V);
+      }
+    }
+  }
+
   return nullptr;
 }

llvm/trunk/test/Transforms/InstCombine/select-implied.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; A == B implies A >u B is false.
+; CHECK-LABEL: @test1
+; CHECK-NOT: select
+; CHECK: call void @foo(i32 10)
+define void @test1(i32 %a, i32 %b) {
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ugt i32 %a, %b
+  %c = select i1 %cmp2, i32 0, i32 10
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; If A == B is false then A != B is true.
+; CHECK-LABEL: @test2
+; CHECK-NOT: select
+; CHECK: call void @foo(i32 20)
+define void @test2(i32 %a, i32 %b) {
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %end, label %taken
+
+taken:
+  %cmp2 = icmp ne i32 %a, %b
+  %c = select i1 %cmp2, i32 20, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; A >u 10 implies A >u 10 is true.
+; CHECK-LABEL: @test3
+; CHECK-NOT: select
+; CHECK: call void @foo(i32 30)
+define void @test3(i32 %a, i32 %b) {
+  %cmp1 = icmp ugt i32 %a, 10
+  br i1 %cmp1, label %taken, label %end
+
+taken:
+  %cmp2 = icmp ugt i32 %a, 10
+  %c = select i1 %cmp2, i32 30, i32 0
+  call void @foo(i32 %c)
+  br label %end
+
+end:
+  ret void
+}
+
+; CHECK-LABEL: @PR23333
+; CHECK-NOT: select
+; CHECK: ret i8 1
+define i8 @PR23333(i8 addrspace(1)* %ptr) {
+   %cmp = icmp eq i8 addrspace(1)* %ptr, null
+   br i1 %cmp, label %taken, label %end
+
+taken:
+   %cmp2 = icmp ne i8 addrspace(1)* %ptr, null
+   %res = select i1 %cmp2, i8 2, i8 1
+   ret i8 %res
+
+end:
+   ret i8 0
+}
+
+; We know the condition of the select is true based on a dominating condition.
+; Therefore, we can replace %cond with %len.
+; CHECK-LABEL: @test4
+; CHECK-NOT: select
+define void @test4(i32 %len) {
+entry:
+  %0 = call i32 @bar(i32 %len);
+  %cmp = icmp ult i32 %len, 4
+  br i1 %cmp, label %bb, label %b1
+bb:
+  %cond = select i1 %cmp, i32 %len, i32 8
+; CHECK:  %cmp11 = icmp eq i32 %len, 8
+  %cmp11 = icmp eq i32 %cond, 8
+  br i1 %cmp11, label %b0, label %b1
+
+b0:
+  call void @foo(i32 %len)
+  br label %b1
+
+b1:
+; CHECK: phi i32 [ %len, %bb ], [ undef, %b0 ], [ %0, %entry ]
+  %1 = phi i32 [ %cond, %bb ], [ undef, %b0 ], [ %0, %entry ]
+  br label %ret
+
+ret:
+  call void @foo(i32 %1)
+  ret void
+}
+
+declare void @foo(i32)
+declare i32 @bar(i32)