[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

1463

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)

1464

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

1473

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

[mkazantsev]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1463

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

1464

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

1462–1467

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) {
   CmpInst::Predicate Pred = Cmp.getPredicate();
   Value *A, *B;
   ConstantInt *CI2; // I = icmp ugt (add (add A, B), CI2), CI
   if (Pred == ICmpInst::ICMP_UGT &&
       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, ...), CI) -> phi(icmp(C1, CI), icmp(C2, CI), ...).
+  if (auto *Phi = dyn_cast<PHINode>(Op0))
+    if (Phi->hasOneUse() &&
+        all_of(Phi->operands(), [](Value *V) { return isa<ConstantInt>(V); })) {
+      Type *Ty = Cmp.getType();
+      Builder.SetInsertPoint(Phi);
+      PHINode *NewPhi =
+          Builder.CreatePHI(Ty, Phi->getNumOperands(), Cmp.getName());
+      const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+      for (BasicBlock *Predecessor : predecessors(Phi->getParent())) {
+        auto *Input =
+            cast<ConstantInt>(Phi->getIncomingValueForBlock(Predecessor));
+        auto *BoolInput = SimplifyICmpInst(Pred, Input, CI, Q);
+        NewPhi->addIncoming(BoolInput, Predecessor);
+      }
+      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:    [[COMPARE1:%.*]] = 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]]
+; CHECK-NEXT:    ret i1 [[COMPARE1]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

 ; 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:    [[COMPARE1:%.*]] = 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]]
+; CHECK-NEXT:    ret i1 [[COMPARE1]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false:

 ; 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:    [[COMPARE1:%.*]] = 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]]
+; CHECK-NEXT:    ret i1 [[COMPARE1]]
 ;
 entry:
   br i1 %cond, label %if.true, label %if.false
 
 if.true:
   br label %merge
 
 if.false: