[InstCombine] Simplify compare of Phi with constant inputs against a constant

[mkazantsev]

Summary

We can simplify

icmp <pred> phi(C1, C2, ...), C

with

phi(icmp(C1, C), icmp(C2, C), ...)

provided that all comparison of constants are constants themselves.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1457

I don't think you need one-use check - you produce a single instruction,
and root icmp from which you started matching always goes away (is replaced by new phi)

1458

Why ConstantInt? What would be wrong with vector of integers? What about undef? Constant exprs?

1467

I'd think you simply want ConstantExpr::getCompare()

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1457

Yeah, I wasn't sure if it's ok to change icmp for a phi, but it should be (phis are free if RA makes good job).

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1458

Undefs are handled in other place (I will add tests showing that).
Vectors of integers and floats should be fine, I'll add some tests on this.
Constant exprs -- not sure what you mean, but they should become constants at some point, shouldn't they?

[mkazantsev]

Addressed comments:

• Removed single use requirement;
• Added more tests;
• Added support for vectors.

[mkazantsev]

Updated other tests.

[lebedev.ri]

LGTM, thanks.

[thakis]

This breaks tests check-clang: http://45.33.8.238/linux/19487/step_7.txt

Please take a look and revert for now if it takes a while to fix.

[lebedev.ri]

In D81151#2075928, @thakis wrote:

This breaks tests check-clang: http://45.33.8.238/linux/19487/step_7.txt

Please take a look and revert for now if it takes a while to fix.

And as is tradition, an overstepping end-to-end test..

[RKSimon]

This looks like its responsible for the exceptions.m test failures on some bots: http://lab.llvm.org:8011/builders/llvm-avr-linux/builds/2189

/home/buildbot-worker/llvm-avr-linux/llvm-avr-linux/llvm/clang/test/CodeGenObjC/exceptions.m:100:12: error: CHECK: expected string not found in input
 // CHECK: [[DEST1:%.*]] = phi i32 [ 0, {{%.*}} ], [ 3, {{%.*}} ]
           ^
<stdin>:195:37: note: scanning from here
 call void @objc_exception_try_exit(%struct._objc_exception_data* nonnull %exceptiondata.ptr) #5
                                    ^
<stdin>:219:2: note: possible intended match here
 %1 = load i32, i32* %x, align 4, !tbaa !7
 ^

[fhahn]

It looks like this may introduce a dead-code elimination regression with -Oz: https://github.com/llvm/llvm-project/issues/53318

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1456–1461

Passing-by comment: i strongly suspect these don't actually want to deal with constant *expressions*,
only immediate constants. I missed that originally i guess.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) {
   Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
   Value *A, *B;
   ConstantInt *CI, *CI2; // I = icmp ugt (add (add A, B), CI2), CI
   if (Pred == ICmpInst::ICMP_UGT && match(Op1, m_ConstantInt(CI)) &&
       match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
     if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this))
       return Res;
 
+  // icmp(phi(C1, C2, ...), C) -> phi(icmp(C1, C), icmp(C2, C), ...).
+  Constant *C = dyn_cast<Constant>(Op1);
+  if (!C)
+    return nullptr;
+
+  if (auto *Phi = dyn_cast<PHINode>(Op0))
+    if (all_of(Phi->operands(), [](Value *V) { return isa<Constant>(V); })) {
+      Type *Ty = Cmp.getType();
+      Builder.SetInsertPoint(Phi);
+      PHINode *NewPhi =
+          Builder.CreatePHI(Ty, Phi->getNumOperands());
+      for (BasicBlock *Predecessor : predecessors(Phi->getParent())) {
+        auto *Input =
+            cast<Constant>(Phi->getIncomingValueForBlock(Predecessor));
+        auto *BoolInput = ConstantExpr::getCompare(Pred, Input, C);
+        NewPhi->addIncoming(BoolInput, Predecessor);
+      }
+      NewPhi->takeName(&Cmp);
+      return replaceInstUsesWith(Cmp, NewPhi);
+    }
+
   return nullptr;
 }
 
 /// Canonicalize icmp instructions based on dominating conditions.
 Instruction *InstCombiner::foldICmpWithDominatingICmp(ICmpInst &Cmp) {
   // This is a cheap/incomplete check for dominance - just match a single
   // predecessor with a conditional branch.
   BasicBlock *CmpBB = Cmp.getParent();

llvm/test/Transforms/InstCombine/icmp-constant-phi.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
-; TODO: Replace with boolean Phi.
-
 define i1 @test_eq(i1 %cond) {
 ; CHECK-LABEL: @test_eq(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 123, [[IF_TRUE]] ], [ 456, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ true, [[IF_FALSE]] ], [ false, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[COMPARE:%.*]] = icmp eq i32 [[PHI]], 456
 ; CHECK-NEXT:    ret i1 [[COMPARE]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 

 ; CHECK-LABEL: @test_slt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 123, [[IF_TRUE]] ], [ 456, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[COMPARE:%.*]] = icmp ult i32 [[PHI]], 456
 ; CHECK-NEXT:    ret i1 [[COMPARE]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 

 ; CHECK-LABEL: @test_ne(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br label [[MERGE:%.*]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br label [[MERGE]]
 ; CHECK:       merge:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ 123, [[IF_TRUE]] ], [ 456, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[COMPARE:%.*]] = phi i1 [ false, [[IF_FALSE]] ], [ true, [[IF_TRUE]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[COMPARE:%.*]] = icmp ne i32 [[PHI]], 456
 ; CHECK-NEXT:    ret i1 [[COMPARE]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:
   br label %merge
 
 merge:
   %phi = phi i32 [123, %if.true], [456, %if.false]
   br label %exit
 
 exit:
   %compare = icmp ne i32 %phi, 456
   ret i1 %compare
 }
+
+define i1 @test_ne_undef(i1 %cond) {
+; CHECK-LABEL: @test_ne_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %phi = phi i32 [undef, %if.true], [456, %if.false]
+  br label %exit
+
+exit:
+  %compare = icmp ne i32 %phi, 456
+  ret i1 %compare
+}
+
+define <2 x i1> @test_ne_int_vector(i1 %cond) {
+; CHECK-LABEL: @test_ne_int_vector(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[COMPARE:%.*]] = phi <2 x i1> [ <i1 true, i1 false>, [[IF_FALSE]] ], [ <i1 false, i1 true>, [[IF_TRUE]] ]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret <2 x i1> [[COMPARE]]
+;
+entry:
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %phi = phi <2 x i32> [<i32 123, i32 123>, %if.true], [<i32 456, i32 456>, %if.false]
+  br label %exit
+
+exit:
+  %compare = icmp ne <2 x i32> %phi, <i32 123, i32 456>
+  ret <2 x i1> %compare
+}
+
+; TODO: We can also constant-fold this comparison for floats.
+define i1 @test_ne_float(i1 %cond) {
+; CHECK-LABEL: @test_ne_float(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[PHI:%.*]] = phi float [ 1.000000e+00, [[IF_TRUE]] ], [ 1.250000e+00, [[IF_FALSE]] ]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[COMPARE:%.*]] = fcmp one float [[PHI]], 1.250000e+00
+; CHECK-NEXT:    ret i1 [[COMPARE]]
+;
+entry:
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %phi = phi float [1.0, %if.true], [1.25, %if.false]
+  br label %exit
+
+exit:
+  %compare = fcmp one float %phi, 1.25
+  ret i1 %compare
+}
+
+define i1 @test_ne_float_undef(i1 %cond) {
+; CHECK-LABEL: @test_ne_float_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %phi = phi float [1.0, %if.true], [undef, %if.false]
+  br label %exit
+
+exit:
+  %compare = fcmp one float %phi, 1.25
+  ret i1 %compare
+}
+
+define <2 x i1> @test_ne_float_vector(i1 %cond) {
+; CHECK-LABEL: @test_ne_float_vector(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[MERGE:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[MERGE]]
+; CHECK:       merge:
+; CHECK-NEXT:    [[PHI:%.*]] = phi <2 x float> [ <float 1.232500e+02, float 1.232500e+02>, [[IF_TRUE]] ], [ <float 4.562500e+02, float 4.562500e+02>, [[IF_FALSE]] ]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[COMPARE:%.*]] = fcmp one <2 x float> [[PHI]], <float 1.232500e+02, float 4.562500e+02>
+; CHECK-NEXT:    ret <2 x i1> [[COMPARE]]
+;
+entry:
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  br label %merge
+
+if.false:
+  br label %merge
+
+merge:
+  %phi = phi <2 x float> [<float 123.25, float 123.25>, %if.true], [<float 456.25, float 456.25>, %if.false]
+  br label %exit
+
+exit:
+  %compare = fcmp one <2 x float> %phi, <float 123.25, float 456.25>
+  ret <2 x i1> %compare
+}

llvm/test/Transforms/InstCombine/indexed-gep-compares.ll

bb7:                                              ; preds = %bb10, %entry-block
   %phi = phi i64* [ @pr30402, %entry ], [ getelementptr inbounds (i64, i64* @pr30402, i32 1), %bb7 ]
   %cmp = icmp eq i64* %phi, getelementptr inbounds (i64, i64* @pr30402, i32 1)
   br i1 %cmp, label %bb10, label %bb7
 
 bb10:
   ret i1 %cmp
 }
 ; CHECK-LABEL: @test7(
-; CHECK:  %[[phi:.*]] = phi i64* [ @pr30402, %entry ], [ getelementptr inbounds (i64, i64* @pr30402, i32 1), %bb7 ]
-; CHECK:  %[[cmp:.*]] = icmp eq i64* %[[phi]], getelementptr inbounds (i64, i64* @pr30402, i32 1)
+; CHECK:  %[[cmp:.*]] = phi i1 [ true, %bb7 ], [ false, %entry ]
 ; CHECK: ret i1 %[[cmp]]
 
 
 declare i32 @__gxx_personality_v0(...)
 
 define i1 @test8(i64* %in, i64 %offset) {
 entry:
 

llvm/test/Transforms/InstCombine/zext-or-icmp.ll

block2:
   %m.1.op = lshr i32 1, %m.011
   %sext.mask = and i32 %m.1.op, 65535
   %cmp115 = icmp ne i32 %sext.mask, 0
   %cmp1 = or i1 %cmp.i, %cmp115
   %conv2 = zext i1 %cmp1 to i32
   ret i32 %conv2
 
 ; CHECK-LABEL: dont_widen_undef(
-; CHECK:         %m.011 = phi i32 [ 33, %entry ], [ 0, %block1 ]
-; CHECK-NEXT:    %cmp.i = icmp ugt i32 %m.011, 1
+; CHECK:         %cmp.i = phi i1 [ false, %block1 ], [ true, %entry ]
+; CHECK-NEXT:    %m.011 = phi i32 [ 0, %block1 ], [ 33, %entry ]
 ; CHECK-NEXT:    %m.1.op = lshr i32 1, %m.011
 ; CHECK-NEXT:    %sext.mask = and i32 %m.1.op, 65535
 ; CHECK-NEXT:    %cmp115 = icmp ne i32 %sext.mask, 0
 ; CHECK-NEXT:    %cmp1 = or i1 %cmp.i, %cmp115
 ; CHECK-NEXT:    %conv2 = zext i1 %cmp1 to i32
 ; CHECK-NEXT:    ret i32 %conv2
 }