[SCCP] Propagate integer range info for parameters in IPSCCP.

[fhahn]

Summary

This updates the SCCP solver to use of the ValueElement lattice for
parameters, which provides integer range information. The range
information is used to remove unneeded icmp instructions.

For the following function, f() can be optimized to ret i32 2 with
this change

source_filename = "sccp.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: norecurse nounwind readnone uwtable
define i32 @main() local_unnamed_addr #0 {
entry:
  %call = tail call fastcc i32 @f(i32 1)
  %call1 = tail call fastcc i32 @f(i32 47)
  %add3 = add nsw i32 %call, %call1
  ret i32 %add3
}

; Function Attrs: noinline norecurse nounwind readnone uwtable
define internal fastcc i32 @f(i32 %x) unnamed_addr #1 {
entry:
  %c1 = icmp sle i32 %x, 100

  %cmp = icmp sgt i32 %x, 300
  %. = select i1 %cmp, i32 1, i32 2
  ret i32 %.
}

attributes #1 = { noinline }

[sanjoy]

lib/Transforms/Scalar/SCCP.cpp

84

Use llvm::ConstantRange here.

1889–1890

Design-wise I personally think it would be better if you instead had a second tryToReplaceWithConstantRange helper that propagated the range information and folded ICmps etc. wherever possible; instead of creating assumes.

But let's see what other folks think.

[• dberlin]

Thanks for working on this!

I think, in practice, what we should do is some combination of assumes and IPSCCP doing what it can.
I don't think we should throw away IPA info because the more local optimizations may still be able to do something better with it.
(IE i don't think IPSCCP will get everything, and so i feel we should expose what it discovers some way that is not ephemeral)

[efriedma]

Should we use range/nonnull metadata or assumptions to generate ranges?

Should IPSCCP itself try to fold operations based on ranges?

Inserting a bunch of "llvm.assume" calls is probably not a good idea; it's likely to be a big performance sink, and block other optimizations. (Not sure what the right answer looks like here, though; it's a hard problem.)

lib/Transforms/Scalar/SCCP.cpp

120

cast<>, not dyn_cast<>

1641

?

[• dberlin]

In D36656#841247, @efriedma wrote:

Should we use range/nonnull metadata or assumptions to generate ranges?

If we have such metadata, yes

Should IPSCCP itself try to fold operations based on ranges?

This is a definite yes for me, regardless of anything else. Even if it only does it to cut down on metadata generated.
I don't think it should go crazy trying to do so (IE Put another way, this pass is currently linear. We should not make it N^2 by trying to fold range operations)

Inserting a bunch of "llvm.assume" calls is probably not a good idea; it's likely to be a big performance sink, and block other optimizations. (Not sure what the right answer looks like here, though; it's a hard problem.)

FWIW: I'm curious what performance problems you see. It would seem bad to have an intrinsic that we can't use a lot :)
I also thought Hal had taken care of most performance issues with assume?

[efriedma]

There have been improvements, but we still have a lot of transforms that aren't assume-aware; essentially every call to hasOneUse() does the wrong thing, etc.

And this transform in particular is creating up to four new IR instructions per existing instruction in the IR, which is going to be a general drain on performance for anything examining the IR; we need some sort of rule for figuring out what's worth annotating.

[mssimpso]

In D36656#841247, @efriedma wrote:

Should we use range/nonnull metadata or assumptions to generate ranges?

Should IPSCCP itself try to fold operations based on ranges?

Inserting a bunch of "llvm.assume" calls is probably not a good idea; it's likely to be a big performance sink, and block other optimizations. (Not sure what the right answer looks like here, though; it's a hard problem.)

An alternative would be to just attach range metadata to arguments/calls, and then rely on LVI for the intraprocedural work.

[davide]

Thanks for your work!
FWIW, I agree with Eli/Sanjoy that we shouldn't rely on assumptions.
Another comment that I have is: instead of using a single lattice for constants and ranges [and *], have you considered looking at something akin to what GCC does? https://github.com/gcc-mirror/gcc/blob/master/gcc/ipa-cp.c#L307
They have different lattices for constants/aggregates/bits/ranges. I find their code easier to read/reason about than LLVM's.

[fhahn]

Thanks for all the feedback! I'll update the patch soon.

In D36656#843034, @davide wrote:

Thanks for your work!
FWIW, I agree with Eli/Sanjoy that we shouldn't rely on assumptions.
Another comment that I have is: instead of using a single lattice for constants and ranges [and *], have you considered looking at something akin to what GCC does? https://github.com/gcc-mirror/gcc/blob/master/gcc/ipa-cp.c#L307
They have different lattices for constants/aggregates/bits/ranges. I find their code easier to read/reason about than LLVM's.

Thanks for pointing me to that. I'll look into adding a separate range lattice.

re using assume: It shouldn't be to hard to use the range lattice to eliminate compare instructions in the IPSCCP pass.

[fhahn]

Updated the patch to use LVILatticeValue (which I moved to a separate header file for now, I'd move it out in a separate patch if we decide to use it) for tracking function parameter values and updated tryToReplaceWithConstant to use range information to removed ICmp instructions.

I think it makes sense to use LVILatticeValue for parameters, as it already contains most of the functionality needed

This patch only uses constant ranges for function parameters. This is good enough to fix PR33253, but I think using constant range for all values in the solver would make it more useful for real programs.

[fhahn]

Update the patch to support all predicates through ConstantRange functions and use a SmallPtrSet to keep track of ICmp instructions to delete (deleting them straight away would invalidate iterators). It would be great if you could have another look now. If that approach is sensible I'll add another review that moves LVILatticeVal to a separate module properly.

[fhahn]

ping, any thoughts?

[davide]

I think this is on the right direction (for me), but let's see what other think.
If we agree, it will probably make sense revamping the general semilattice engine to plug arbitrary lattices in (and move the constant semilattice out).
This will enable future improvements (i.e. support for IPA bitwise CP, see, e.g. https://patchwork.ozlabs.org/patch/657644/)

include/llvm/Analysis/ValueLattice.h

123–125

Are you expecting the resolver to plug the correct value here?

lib/Transforms/Scalar/SCCP.cpp

1587

I think it's better to split this in two APIs (tryToReplaceWithConstant & tryToReplaceWithConstantRange)

[fhahn]

Added D37591 to move LVILatticeVal to separate file and moved code to replace ICmp instructions to separate function

[fhahn]

include/llvm/Analysis/ValueLattice.h

123–125

I am not sure what you mean here. Are you referring to the assert? The caller is responsible to make sure that markConstant is not called with different constant values (e.g. in mergeIn).

lib/Transforms/Scalar/SCCP.cpp

1587

Yes and it makes the code quite a bit simpler too

[fhahn]

Ping. The commit moving the LVI lattice out to a separate file is ready to go in ( D37591 ). I would go ahead and commit the change soon, if you think it's a good idea to use it in SCCP for range tracking.

[• dberlin]

FWIW: I think this is a good approach to start with (and is small enough that if we decide to go another way, it doesn't hurt anything).

[davide]

I think the same.

[fhahn]

Rebased after D37591 was committed

[fhahn]

ping. Seems like there is agreement that this is a good start. If that is still the case, it would be great if someone could formally approve the patch :)

[• dberlin]

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

90

Is there a reason not to track ranges for variables who uses appear as arguments?
IE start with each function call, and for the arguments, mark them so they get a bigger lattice.
It can be done as a followup, i'm just trying to understand.

[fhahn]

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

90

I thought it would be better to be conservative to start with and using ValueLatticeElement as general lattice value type seemed to slightly too heavy handed. I was thinking looking into some of the suggestions made in https://bugs.llvm.org/show_bug.cgi?id=26921 to reduce the memory consumption of ValueLatticeElement.

What do you think?

[• dberlin]

Sounds reasonable to start with.

[davide]

Minors, otherwise, looks good. Feel free to submit once you addressed them without another round of review.

lib/Transforms/Scalar/SCCP.cpp

28

Unsorted.

1599

If would be nicer if you broke earlier to reduced the indentation, but, I mean, I/you can probably clean this up as a follow up.

1605

unformatted.

1610

can you please clang format?

[fhahn]

Fixed formatting and renamed toLVI to toValueLattice. Thanks for the reviews, I will commit it tomorrow morning, unless there are any further objections.

[fhahn]

another small update. Use early exit and continue in tryToReplaceWithConstantRange as @davide suggested

[fhahn]

There was a problem with this patch in combination with LTO and it has been reverted. I will investigate soon.

[• dberlin]

I suspect at least one of your bugs is that the param state lattice doesn't get updated when the value state lattice changes.

lib/Transforms/Scalar/SCCP.cpp

304

Use find so you aren't doing this lookup twice.
Or even better, please use insert to make space if it doesn't exist, it won't screw up your assert.

308

This seems wrong.
What happens if the value state lattice value changes?
This will never update it.

311

Then you can just return the result of the insert here.

447

Ditto above on how to do this without repeated lookups

448

Ditto above, if the value changes you will never update it from the value state.

1597

You already assert it's an integer type above?
Choose a single place to do it ;)

[fhahn]

Thanks for having another look and for your comments. I'll address them soon. I am not sure about ValueState and ParamState entries diverging (I responded with details inline), but I am probably missing something.

lib/Transforms/Scalar/SCCP.cpp

308

My understanding was that this function only gets called after the solver finished, meaning the value in ValueState should not change.

448

Hm, this function is only used to get the state for function parameters. I thought the only place where we change the state for function parameters is at line 1194 and there is no other place where the ValueState entries of function parameters could be changed. At least that was what I intended :)

[fhahn]

I finally managed to track down the crash with the clang-stage2-configure-Rlto bot, thanks to @bruno. The problem was that tryToReplaceWithConstantRange iterates over all the users of a value, and calls Solver.getLatticeValueFor for the operands of ICmp instructions (which asserts the operand has been added to the lattice). For Icmp instructions in unreachable blocks, this is not the case.

I've updated tryToReplaceWithConstantRange to only consider Icmp instructions in executable blocks. This fixes the crash. I also updated the code to use insert, as suggested by @dberlin. I think with the crash addressed, the patch should be ready for re-committing, unless there are any remaining objections.

include/llvm/Analysis/ValueLattice.h

+//===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the interface for lazy computation of value constraint
+// information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VALUELATTICE_H
+#define LLVM_ANALYSIS_VALUELATTICE_H
+
+#include "llvm/IR/ConstantRange.h"
+#include "llvm/IR/Constants.h"
+
+namespace llvm {
+class LVILatticeVal {
+  enum LatticeValueTy {
+    /// This Value has no known value yet.  As a result, this implies the
+    /// producing instruction is dead.  Caution: We use this as the starting
+    /// state in our local meet rules.  In this usage, it's taken to mean
+    /// "nothing known yet".
+    undefined,
+
+    /// This Value has a specific constant value.  (For constant integers,
+    /// constantrange is used instead.  Integer typed constantexprs can appear
+    /// as constant.)
+    constant,
+
+    /// This Value is known to not have the specified value.  (For constant
+    /// integers, constantrange is used instead.  As above, integer typed
+    /// constantexprs can appear here.)
+    notconstant,
+
+    /// The Value falls within this range. (Used only for integer typed values.)
+    constantrange,
+
+    /// We can not precisely model the dynamic values this value might take.
+    overdefined
+  };
+
+  /// Val: This stores the current lattice value along with the Constant* for
+  /// the constant if this is a 'constant' or 'notconstant' value.
+  LatticeValueTy Tag;
+  Constant *Val;
+  ConstantRange Range;
+
+public:
+  LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
+
+  static LVILatticeVal get(Constant *C) {
+    LVILatticeVal Res;
+    if (!isa<UndefValue>(C))
+      Res.markConstant(C);
+    return Res;
+  }
+  static LVILatticeVal getNot(Constant *C) {
+    LVILatticeVal Res;
+    if (!isa<UndefValue>(C))
+      Res.markNotConstant(C);
+    return Res;
+  }
+  static LVILatticeVal getRange(ConstantRange CR) {
+    LVILatticeVal Res;
+    Res.markConstantRange(std::move(CR));
+    return Res;
+  }
+  static LVILatticeVal getOverdefined() {
+    LVILatticeVal Res;
+    Res.markOverdefined();
+    return Res;
+  }
+
+  bool isUndefined() const     { return Tag == undefined; }
+  bool isConstant() const      { return Tag == constant; }
+  bool isNotConstant() const   { return Tag == notconstant; }
+  bool isConstantRange() const { return Tag == constantrange; }
+  bool isOverdefined() const   { return Tag == overdefined; }
+
+  Constant *getConstant() const {
+    assert(isConstant() && "Cannot get the constant of a non-constant!");
+    return Val;
+  }
+
+  Constant *getNotConstant() const {
+    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
+    return Val;
+  }
+
+  const ConstantRange &getConstantRange() const {
+    assert(isConstantRange() &&
+           "Cannot get the constant-range of a non-constant-range!");
+    return Range;
+  }
+
+  Optional<APInt> asConstantInteger() const {
+    if (isConstant() && isa<ConstantInt>(Val)) {
+      return cast<ConstantInt>(Val)->getValue();
+    } else if (isConstantRange() && Range.isSingleElement()) {
+      return *Range.getSingleElement();
+    }
+    return None;
+  }
+
+private:
+  void markOverdefined() {
+    if (isOverdefined())
+      return;
+    Tag = overdefined;
+  }
+
+  void markConstant(Constant *V) {
+    assert(V && "Marking constant with NULL");
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
+      markConstantRange(ConstantRange(CI->getValue()));
+      return;
+    }
+    if (isa<UndefValue>(V))
+      return;
+
+    assert((!isConstant() || getConstant() == V) &&
+           "Marking constant with different value");
+    assert(isUndefined());
+    Tag = constant;
+    Val = V;
+  }
+
+  void markNotConstant(Constant *V) {
+    assert(V && "Marking constant with NULL");
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
+      markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
+      return;
+    }
+    if (isa<UndefValue>(V))
+      return;
+
+    assert((!isConstant() || getConstant() != V) &&
+           "Marking constant !constant with same value");
+    assert((!isNotConstant() || getNotConstant() == V) &&
+           "Marking !constant with different value");
+    assert(isUndefined() || isConstant());
+    Tag = notconstant;
+    Val = V;
+  }
+
+  void markConstantRange(ConstantRange NewR) {
+    if (isConstantRange()) {
+      if (NewR.isEmptySet())
+        markOverdefined();
+      else {
+        Range = std::move(NewR);
+      }
+      return;
+    }
+
+    assert(isUndefined());
+    if (NewR.isEmptySet())
+      markOverdefined();
+    else {
+      Tag = constantrange;
+      Range = std::move(NewR);
+    }
+  }
+
+public:
+
+  /// Merge the specified lattice value into this one, updating this
+  /// one and returning true if anything changed.
+  bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
+    if (RHS.isUndefined() || isOverdefined())
+      return false;
+    if (RHS.isOverdefined()) {
+      markOverdefined();
+      return true;
+    }
+
+    if (isUndefined()) {
+      *this = RHS;
+      return !RHS.isUndefined();
+    }
+
+    if (isConstant()) {
+      if (RHS.isConstant() && Val == RHS.Val)
+          return false;
+      markOverdefined();
+      return true;
+    }
+
+    if (isNotConstant()) {
+      if (RHS.isNotConstant() && Val == RHS.Val)
+          return false;
+      markOverdefined();
+      return true;
+    }
+
+    assert(isConstantRange() && "New LVILattice type?");
+    if (!RHS.isConstantRange()) {
+      // We can get here if we've encountered a constantexpr of integer type
+      // and merge it with a constantrange.
+      markOverdefined();
+      return true;
+    }
+    ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
+    if (NewR.isFullSet())
+      markOverdefined();
+    else
+      markConstantRange(std::move(NewR));
+    return true;
+  }
+
+  ConstantInt *getConstantInt() const {
+    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
+           "No integer constant");
+    return cast<ConstantInt>(getConstant());
+  }
+
+  bool satisfiesPredicate(CmpInst::Predicate Pred,
+                          const LVILatticeVal &Other) const {
+    // TODO: share with LVI getPredicateResult.
+    // Integer constants are represented as ConstantRanges with single
+    // elements.
+    if (!isConstantRange() || !Other.isConstantRange())
+      return false;
+
+    const auto &CR = getConstantRange();
+    const auto &OtherCR = Other.getConstantRange();
+    switch (Pred) {
+    case CmpInst::ICMP_NE:
+      return CR.intersectWith(OtherCR).isEmptySet();
+    case CmpInst::ICMP_EQ:
+      return CR.isSingleElement() && OtherCR.isSingleElement() &&
+             CR == OtherCR;
+    default:
+      return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
+    }
+  }
+
+};
+raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
+    LLVM_ATTRIBUTE_USED;
+raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
+  if (Val.isUndefined())
+    return OS << "undefined";
+  if (Val.isOverdefined())
+    return OS << "overdefined";
+
+  if (Val.isNotConstant())
+    return OS << "notconstant<" << *Val.getNotConstant() << '>';
+  if (Val.isConstantRange())
+    return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
+              << Val.getConstantRange().getUpper() << '>';
+  return OS << "constant<" << *Val.getConstant() << '>';
+}
+
+
+}  // end namespace llvm
+
+#endif

lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
enum LatticeValueTy {
     /// it has a value.
     overdefined
   };
 
   /// Val: This stores the current lattice value along with the Constant* for
   /// the constant if this is a 'constant' or 'forcedconstant' value.
   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
 
   LatticeValueTy getLatticeValue() const {
     return Val.getInt();
   }
 
 public:
   LatticeVal() : Val(nullptr, unknown) {}
 
   bool isUnknown() const { return getLatticeValue() == unknown; }
   bool isConstant() const {
public:
   bool markConstant(Constant *V) {
     if (getLatticeValue() == constant) { // Constant but not forcedconstant.
       assert(getConstant() == V && "Marking constant with different value");
       return false;
     }
 
     if (isUnknown()) {
       Val.setInt(constant);
       assert(V && "Marking constant with NULL");
       Val.setPointer(V);
     } else {
       assert(getLatticeValue() == forcedconstant &&
              "Cannot move from overdefined to constant!");
       // Stay at forcedconstant if the constant is the same.
       if (V == getConstant()) return false;
 
       // Otherwise, we go to overdefined.  Assumptions made based on the
BlockAddress *getBlockAddress() const {
     return nullptr;
   }
 
   void markForcedConstant(Constant *V) {
     assert(isUnknown() && "Can't force a defined value!");
     Val.setInt(forcedconstant);
     Val.setPointer(V);
   }
+
+  LVILatticeVal toLVI() const {
+    if (isOverdefined())
+      return LVILatticeVal::getOverdefined();
+    if (isConstant())
+      return LVILatticeVal::get(getConstant());
+    return LVILatticeVal();
+  }
 };
 } // end anonymous namespace.
 
 
 namespace {
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
 ///
 class SCCPSolver : public InstVisitor<SCCPSolver> {
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   SmallPtrSet<BasicBlock*, 8> BBExecutable; // The BBs that are executable.
   DenseMap<Value*, LatticeVal> ValueState;  // The state each value is in.
+  DenseMap<Value*, LVILatticeVal> ParamState;  // The state each parameter is in.
 
   /// StructValueState - This maintains ValueState for values that have
   /// StructType, for example for formal arguments, calls, insertelement, etc.
   ///
   DenseMap<std::pair<Value*, unsigned>, LatticeVal> StructValueState;
 
   /// GlobalValue - If we are tracking any values for the contents of a global
   /// variable, we keep a mapping from the constant accessor to the element of
std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     return StructValues;
   }
 
-  LatticeVal getLatticeValueFor(Value *V) const {
+  LVILatticeVal getLatticeValueFor(Value *V) {
+    if (ParamState.count(V) == 0) {
       DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
-    assert(I != ValueState.end() && "V is not in valuemap!");
-    return I->second;
+      assert(I != ValueState.end() &&
+             "V not found in ValueState nor Paramstate map!");
+      ParamState[V] = I->second.toLVI();
+    }
+
+    return ParamState[V];
   }
 
   /// getTrackedRetVals - Get the inferred return value map.
   ///
   const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
     return TrackedRetVals;
   }
 
if (auto *C = dyn_cast<Constant>(V)) {
       if (!isa<UndefValue>(V))
         LV.markConstant(C);          // Constants are constant
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
+  LVILatticeVal &getParamState(Value *V) {
+    assert(!V->getType()->isStructTy() && "Should use getStructValueState");
+
+    if (ParamState.count(V) == 0)
+      ParamState[V] = getValueState(V).toLVI();
+
+    return ParamState[V];
+  }
+
   /// getStructValueState - Return the LatticeVal object that corresponds to the
   /// value/field pair.  This function handles the case when the value hasn't
   /// been seen yet by properly seeding constants etc.
   LatticeVal &getStructValueState(Value *V, unsigned i) {
     assert(V->getType()->isStructTy() && "Should use getValueState");
     assert(i < cast<StructType>(V->getType())->getNumElements() &&
            "Invalid element #");
 
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
       }
 
       if (auto *STy = dyn_cast<StructType>(AI->getType())) {
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           LatticeVal CallArg = getStructValueState(*CAI, i);
           mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg);
         }
       } else {
+        // Most other parts of the Solver still only use the simpler value
+        // lattice, so we propagate changes for parameters to both lattices.
+        getParamState(&*AI).mergeIn(getValueState(*CAI).toLVI(), DL);
         mergeInValue(&*AI, getValueState(*CAI));
       }
     }
   }
 
   // If this is a single/zero retval case, see if we're tracking the function.
   if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
     if (!MRVFunctionsTracked.count(F))
if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue());
       return true;
     }
   }
 
   return false;
 }
 
-static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
+static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V, SmallPtrSet<Instruction*,4> &ToRemove) {
   Constant *Const = nullptr;
+  bool Changed = false;
   if (V->getType()->isStructTy()) {
     std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
     if (any_of(IVs, [](const LatticeVal &LV) { return LV.isOverdefined(); }))
       return false;
     std::vector<Constant *> ConstVals;
     auto *ST = dyn_cast<StructType>(V->getType());
     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
       LatticeVal V = IVs[i];
       ConstVals.push_back(V.isConstant()
                               ? V.getConstant()
                               : UndefValue::get(ST->getElementType(i)));
     }
     Const = ConstantStruct::get(ST, ConstVals);
+    Changed = true;
   } else {
-    LatticeVal IV = Solver.getLatticeValueFor(V);
+    const LVILatticeVal &IV = Solver.getLatticeValueFor(V);
     if (IV.isOverdefined())
       return false;
-    Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
+
+    if (V->getType()->isIntegerTy() &&
+        (IV.isConstantRange())) {
+      for (auto &Use : V->uses()) {
+        if (auto *Icmp = dyn_cast<ICmpInst>(Use.getUser())) {
+          auto A = Solver.getLatticeValueFor(Icmp->getOperand(0));
+          auto B = Solver.getLatticeValueFor(Icmp->getOperand(1));
+          Constant *C = nullptr;
+          if (A.satisfiesPredicate(Icmp->getPredicate(), B))
+            C = ConstantInt::getTrue(Icmp->getType());
+          else if(A.satisfiesPredicate(Icmp->getInversePredicate(), B))
+            C = ConstantInt::getFalse(Icmp->getType());
+
+          if (C) {
+            Icmp->replaceAllUsesWith(C);
+            DEBUG(dbgs() << "Replacing " << *Icmp << " with " << *C
+                         << ", because of range information " << A << " " << B
+                         << "\n");
+            ToRemove.insert(Icmp);
+            Changed = true;
+          }
+        }
+      }
+    }
+    if (IV.isConstantRange()) {
+      if(IV.getConstantRange().isSingleElement())
+        Const = ConstantInt::get(V->getType(), IV.asConstantInteger().getValue());
+      else
+        return Changed;
+    } else
+      Const = IV.isConstant() ? IV.getConstant() :
+                                UndefValue::get(V->getType());
+
+    Changed = true;
   }
   assert(Const && "Constant is nullptr here!");
   DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
-  return true;
+  return Changed;
 }
 
 // runSCCP() - Run the Sparse Conditional Constant Propagation algorithm,
 // and return true if the function was modified.
 //
 static bool runSCCP(Function &F, const DataLayout &DL,
                     const TargetLibraryInfo *TLI) {
   DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
if (!Solver.isBlockExecutable(&BB)) {
 
       MadeChanges = true;
       continue;
     }
 
     // Iterate over all of the instructions in a function, replacing them with
     // constants if we have found them to be of constant values.
     //
+    SmallPtrSet<Instruction*, 4> ToRemove;
     for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
       Instruction *Inst = &*BI++;
       if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst))
         continue;
 
-      if (tryToReplaceWithConstant(Solver, Inst)) {
+      if (tryToReplaceWithConstant(Solver, Inst, ToRemove)) {
         if (isInstructionTriviallyDead(Inst))
-          Inst->eraseFromParent();
-        // Hey, we just changed something!
-        MadeChanges = true;
-        ++NumInstRemoved;
-      }
+          ToRemove.insert(Inst);
+      }
+    }
+    for (auto *Inst : ToRemove) {
+      ++IPNumInstRemoved;
     }
   }
 
   return MadeChanges;
 }
 
 PreservedAnalyses SCCPPass::run(Function &F, FunctionAnalysisManager &AM) {
   const DataLayout &DL = F.getParent()->getDataLayout();
static bool runIPSCCP(Module &M, const DataLayout &DL,
   // constants if we have found them to be of constant values.
   //
   SmallVector<BasicBlock*, 512> BlocksToErase;
 
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
-    if (Solver.isBlockExecutable(&F.front()))
+    if (Solver.isBlockExecutable(&F.front())) {
+      SmallPtrSet<Instruction*, 4> ToRemove;
       for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
            ++AI)
-        if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI))
+        if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI,
+                                                         ToRemove))
           ++IPNumArgsElimed;
 
+      for (auto *Inst : ToRemove) {
+        Inst->eraseFromParent();
+        ++IPNumInstRemoved;
+      }
+    }
+
     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
       if (!Solver.isBlockExecutable(&*BB)) {
         DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
 
         ++NumDeadBlocks;
         NumInstRemoved +=
             changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false);
 
         MadeChanges = true;
 
         if (&*BB != &F.front())
           BlocksToErase.push_back(&*BB);
         continue;
       }
 
+
+      SmallPtrSet<Instruction*, 4> ToRemove;
       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
         Instruction *Inst = &*BI++;
         if (Inst->getType()->isVoidTy())
           continue;
-        if (tryToReplaceWithConstant(Solver, Inst)) {
+        if (tryToReplaceWithConstant(Solver, Inst, ToRemove)) {
           if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
-            Inst->eraseFromParent();
-          // Hey, we just changed something!
-          MadeChanges = true;
-          ++IPNumInstRemoved;
-        }
-      }
-    }
+            ToRemove.insert(Inst);
+        }
+      }
+      for (auto *Inst : ToRemove) {
 
     // Now that all instructions in the function are constant folded, erase dead
     // blocks, because we can now use ConstantFoldTerminator to get rid of
     // in-edges.
     for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
       // If there are any PHI nodes in this successor, drop entries for BB now.
       BasicBlock *DeadBB = BlocksToErase[i];
       for (Value::user_iterator UI = DeadBB->user_begin(),

test/Transforms/SCCP/ip-constan-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
+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
+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
+  %res2 = select i1 %cmp2, i32 3, i32 4
+  %res3 = select i1 %cmp3, i32 5, i32 6
+  %res4 = select i1 %cmp4, i32 3, i32 4
+  %res5 = select i1 %cmp5, i32 5, i32 6
+
+  %res6 = add i32 %res1, %res2
+  %res7 = add i32 %res3, %res4
+  %res = add i32 %res6, %res5
+  ret i32 %res
+}
+
+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.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
+; CHECK: %res = select i1 %cmp, i32 1, i32 2
+; CHECK: ret i32 %res
+define internal i32 @f3(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  %res = select i1 %cmp, i32 1, i32 2
+  ret i32 %res
+}
+
+; The phi node could be converted in a ConstantRange.
+define i32 @caller2(i1 %cmp) {
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %res = phi i32 [ 0, %entry], [ 1, %if.true ]
+  %call1 = tail call i32 @f3(i32 %res)
+  ret i32 %call1
+}
+
+; CHECK-LABEL: f4
+; CHECK: %cmp = icmp sgt i32 %x, 300
+; CHECK: %res = select i1 %cmp, i32 1, i32 2
+; CHECK: ret i32 %res
+define internal i32 @f4(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  %res = select i1 %cmp, i32 1, i32 2
+  ret i32 %res
+}
+
+; ICmp could introduce bounds on ConstantRanges.
+define i32 @caller3(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  %x.1 = tail call i32 @f4(i32 %x)
+  br label %end
+
+end:
+  %res = phi i32 [ 0, %entry], [ %x.1, %if.true ]
+  ret i32 %res
+}