[IPSCCP] Use constant range information for comparisons of parameters.

[fhahn]

Summary

For comparisons with parameters, we can use the ParamState lattice
elements which also provide constant range information. This improves
the code for PR33253 further and gets us closer to use
ValueLatticeElement for all values.

Also, as we are using the range information in the solver directly, we
do not need tryToReplaceWithConstantRange afterwards anymore.

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[mssimpso]

test/Transforms/SCCP/ip-constant-ranges.ll

5

Hi Florian,

I'm not understanding why we end up with undef here. Can you help me out?

[mssimpso]

test/Transforms/SCCP/ip-constant-ranges.ll

5

Ah, it's because the function becomes dead after the simplification in @caller1. Right?

[fhahn]

Removed tryToReplaceWithConstantRange. It's not needed anymore, as we use the constant range info directly in the solver.

[fhahn]

test/Transforms/SCCP/ip-constant-ranges.ll

5

Yep. And the selects are removed, because now the range info is used directly in the solver and is used to simplify the function further.

[mssimpso]

LGTM.

[fhahn]

Slightly restructured to only call getValueState when we failed to find a value in ParamState.

[fhahn]

I had to revert this patch a while ago in rL328312 because it did a few things wrong. Most issues are fixed now, there is still one failure I need to track down. I will share the updated patches soon.

[fhahn]

I've finally had some time to come back to this change (sorry for the long delay!) and committed an updated version of this patch as rL336098.

The change to the original patch is that we have to add values to the worklist if merging in an argument changes the ParamState for it, but there has been no change in ValueState (e.g. ValueState is overdefined, but in ParamState we have a value range that changed). It would be great if could have a quick look at the committed change as a sanity check I did not miss anything.

lib/Transforms/Scalar/SCCP.cpp

 #define DEBUG_TYPE "sccp"
 
 STATISTIC(NumInstRemoved, "Number of instructions removed");
 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
 
 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
-STATISTIC(IPNumRangeInfoUsed, "Number of times constant range info was used by"
-                              "IPSCCP");
 
 namespace {
 
 /// LatticeVal class - This class represents the different lattice values that
 /// an LLVM value may occupy.  It is a simple class with value semantics.
 ///
 class LatticeVal {
   enum LatticeValueTy {
if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
     }
   }
 
   markOverdefined(&I);
 }
 
 // Handle ICmpInst instruction.
 void SCCPSolver::visitCmpInst(CmpInst &I) {
-  LatticeVal V1State = getValueState(I.getOperand(0));
-  LatticeVal V2State = getValueState(I.getOperand(1));
-
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
-  if (V1State.isConstant() && V2State.isConstant()) {
-    Constant *C = ConstantExpr::getCompare(
-        I.getPredicate(), V1State.getConstant(), V2State.getConstant());
+  Value *Op1 = I.getOperand(0);
+  Value *Op2 = I.getOperand(1);
+
+  // For parameters, use ParamState which includes constant range info if
+  // available.
+  auto V1Param = ParamState.find(Op1);
+  ValueLatticeElement V1State = (V1Param != ParamState.end())
+                                    ? V1Param->second
+                                    : getValueState(Op1).toValueLattice();
+
+  auto V2Param = ParamState.find(Op2);
+  ValueLatticeElement V2State = V2Param != ParamState.end()
+                                    ? V2Param->second
+                                    : getValueState(Op2).toValueLattice();
+
+  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
+  if (C) {
     if (isa<UndefValue>(C))
       return;
     return markConstant(IV, &I, C);
   }
 
   // If operands are still unknown, wait for it to resolve.
   if (!V1State.isOverdefined() && !V2State.isOverdefined())
     return;
if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue());
       return true;
     }
   }
 
   return false;
 }
 
-static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) {
-  bool Changed = false;
-
-  // Currently we only use range information for integer values.
-  if (!V->getType()->isIntegerTy())
-    return false;
-
-  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
-  if (!IV.isConstantRange())
-    return false;
-
-  for (auto UI = V->uses().begin(), E = V->uses().end(); UI != E;) {
-    const Use &U = *UI++;
-    auto *Icmp = dyn_cast<ICmpInst>(U.getUser());
-    if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent()))
-      continue;
-
-    auto getIcmpLatticeValue = [&](Value *Op) {
-      if (auto *C = dyn_cast<Constant>(Op))
-        return ValueLatticeElement::get(C);
-      return Solver.getLatticeValueFor(Op);
-    };
-
-    ValueLatticeElement A = getIcmpLatticeValue(Icmp->getOperand(0));
-    ValueLatticeElement B = getIcmpLatticeValue(Icmp->getOperand(1));
-
-    Constant *C = A.getCompare(Icmp->getPredicate(), Icmp->getType(), B);
-    if (C) {
-      Icmp->replaceAllUsesWith(C);
-      DEBUG(dbgs() << "Replacing " << *Icmp << " with " << *C
-                   << ", because of range information " << A << " " << B
-                   << "\n");
-      Icmp->eraseFromParent();
-      Changed = true;
-    }
-  }
-  return Changed;
-}
-
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
     std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
     if (llvm::any_of(IVs,
                      [](const LatticeVal &LV) { return LV.isOverdefined(); }))
       return false;
     std::vector<Constant *> ConstVals;
for (Function &F : M) {
 
     if (Solver.isBlockExecutable(&F.front()))
       for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
            ++AI) {
         if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI)) {
           ++IPNumArgsElimed;
           continue;
         }
-
-        if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI))
-          ++IPNumRangeInfoUsed;
       }
 
     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
       if (!Solver.isBlockExecutable(&*BB)) {
         DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
 
         ++NumDeadBlocks;
         NumInstRemoved +=

test/Transforms/SCCP/ip-constant-ranges.ll

 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 ; Constant range for %a is [1, 48) and for %b is [301, 1000)
 ; CHECK-LABEL: f1
-; CHECK-NOT: icmp
-; CHECK: %a.1 = select i1 false, i32 1, i32 2
-; CHECK: %b.1 = select i1 true, i32 1, i32 2
-; CHECK: %a.2 = select i1 false, i32 1, i32 2
-; CHECK: %b.2 = select i1 true, i32 1, i32 2
+; CHECK: ret i32 undef
 define internal i32 @f1(i32 %a, i32 %b) {
 entry:
   %cmp.a = icmp sgt i32 %a, 300
   %cmp.b = icmp sgt i32 %b, 300
   %cmp.a2 = icmp ugt i32 %a, 300
   %cmp.b2 = icmp ugt i32 %b, 300
 
   %a.1 = select i1 %cmp.a, i32 1, i32 2
   %b.1 = select i1 %cmp.b, i32 1, i32 2
   %a.2 = select i1 %cmp.a2, i32 1, i32 2
   %b.2 = select i1 %cmp.b2, i32 1, i32 2
   %res1 = add i32 %a.1, %b.1
   %res2 = add i32 %a.2, %b.2
   %res3 = add i32 %res1, %res2
   ret i32 %res3
 }
 
 ; Constant range for %x is [47, 302)
 ; CHECK-LABEL: f2
 ; CHECK: %cmp = icmp sgt i32 %x, 300
 ; CHECK: %res1 = select i1 %cmp, i32 1, i32 2
-; CHECK-NEXT: %res2 = select i1 true, i32 3, i32 4
-; CHECK-NEXT: %res3 = select i1 true, i32 5, i32 6
 ; CHECK-NEXT: %res4 = select i1 %cmp4, i32 3, i32 4
-; CHECK-NEXT: %res5 = select i1 true, i32 5, i32 6
+; CHECK-NEXT: %res6 = add i32 %res1, 3
+; CHECK-NEXT: %res7 = add i32 5, %res4
+; CHECK-NEXT: %res = add i32 %res6, 5
+; CHECK-NEXT: ret i32 %res
 define internal i32 @f2(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, 300
   %cmp2 = icmp ne i32 %x, 10
   %cmp3 = icmp sge i32 %x, 47
   %cmp4 = icmp ugt i32 %x, 300
   %cmp5 = icmp uge i32 %x, 47
   %res1 = select i1 %cmp, i32 1, i32 2

 }
 
 define i32 @caller1() {
 entry:
   %call1 = tail call i32 @f1(i32 1, i32 301)
   %call2 = tail call i32 @f1(i32 47, i32 999)
   %call3 = tail call i32 @f2(i32 47)
   %call4 = tail call i32 @f2(i32 301)
-  %res = add nsw i32 %call1, %call2
-  %res.1 = add nsw i32 %res, %call3
+  %res.1 = add nsw i32 12, %call3
   %res.2 = add nsw i32 %res.1, %call4
   ret i32 %res.2
 }
 
 ; x is overdefined, because constant ranges are only used for parameter
 ; values.
 ; CHECK-LABEL: f3
 ; CHECK: %cmp = icmp sgt i32 %x, 300
define double @test_struct({ double, double } %test) {
     %v = extractvalue { double, double } %test, 0
     %r = fmul double %v, %v
     ret double %r
 }
 
 ; Constant range for %x is [47, 302)
 ; CHECK-LABEL: @f5
 ; CHECK-NEXT: entry:
-; CHECK-NEXT: %res1 = select i1 undef, i32 1, i32 2
-; CHECK-NEXT: %res2 = select i1 undef, i32 3, i32 4
-; CHECK-NEXT: %res = add i32 %res1, %res2
+; CHECK-NEXT: %cmp = icmp sgt i32 %x, undef
+; CHECK-NEXT: %res1 = select i1 %cmp, i32 1, i32 2
+; CHECK-NEXT: %res = add i32 %res1, 3
 ; CHECK-NEXT: ret i32 %res
 define internal i32 @f5(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, undef
   %cmp2 = icmp ne i32 undef, %x
   %res1 = select i1 %cmp, i32 1, i32 2
   %res2 = select i1 %cmp2, i32 3, i32 4