[IPSCCP] Use ValueLatticeElement instead of LatticeVal (NFCI)

[fhahn]

Summary

This patch switches SCCP to use ValueLatticeElement for lattice values,
instead of the local LatticeVal, as first step to enable integer range support.

This patch does not make use of constant ranges for additional operations
and the only difference for now is that integer constants are represented by
single element ranges. To preserve the existing behavior, the following helpers
are used

• isConstant(LV): returns true when LV is either a constant or a constant range with a single element. This should return true in the same cases where LV.isConstant() returned true previously.
• getConstant(LV): returns a constant if LV is either a constant or a constant range with a single element. This should return a constant in the same cases as LV.getConstant() previously.
• getConstantInt(LV): same as getConstant, but additionally casted to ConstantInt.

[fhahn]

For now I would appreciate any high-level input, like is this the right place to do this or should we have a separate range propagation pass? I think we might be able to use this as a replacement for (parts) of CorrelatedValuePropagation, to avoid a few instances of recursively walking the IR.

Some initial statistics for -O3 -flto

Tests: 243
Same hash: 209 (filtered out)
Remaining: 34
Metric: sccp.IPNumInstRemoved

Program base range diff
test-suite...marks/SciMark2-C/scimark2.test 13.00 25.00 92.3%
test-suite...peg2/mpeg2dec/mpeg2decode.test 23.00 35.00 52.2%
test-suite...ngs-C/assembler/assembler.test 7.00 9.00 28.6%
test-suite...CFP2000/177.mesa/177.mesa.test 155.00 178.00 14.8%
test-suite...ks/Prolangs-C/agrep/agrep.test 24.00 27.00 12.5%
test-suite.../CINT2000/254.gap/254.gap.test 117.00 127.00 8.5%
test-suite...urce/Applications/lua/lua.test 260.00 273.00 5.0%
test-suite...ce/Benchmarks/PAQ8p/paq8p.test 87.00 91.00 4.6%
test-suite...langs-C/football/football.test 78.00 80.00 2.6%
test-suite...lications/sqlite3/sqlite3.test 471.00 483.00 2.5%
test-suite...5/124.m88ksim/124.m88ksim.test 163.00 167.00 2.5%
test-suite...lications/ClamAV/clamscan.test 839.00 857.00 2.1%
test-suite...CFP2006/433.milc/433.milc.test 197.00 201.00 2.0%
test-suite...nal/skidmarks10/skidmarks.test 504.00 513.00 1.8%
test-suite...0.perlbench/400.perlbench.test 1551.00 1578.00 1.7%
test-suite...arks/mafft/pairlocalalign.test 237.00 241.00 1.7%
test-suite...T2006/456.hmmer/456.hmmer.test 120.00 122.00 1.7%
test-suite.../CINT2000/176.gcc/176.gcc.test 978.00 994.00 1.6%
test-suite...0/253.perlbmk/253.perlbmk.test 937.00 950.00 1.4%
test-suite...T2006/445.gobmk/445.gobmk.test 1567.00 1588.00 1.3%
test-suite.../CINT95/134.perl/134.perl.test 86.00 87.00 1.2%
test-suite.../CINT2006/403.gcc/403.gcc.test 3625.00 3656.00 0.9%
test-suite...000/186.crafty/186.crafty.test 282.00 284.00 0.7%
test-suite.../Applications/SPASS/SPASS.test 2007.00 2020.00 0.6%
test-suite...3.xalancbmk/483.xalancbmk.test 3898.00 3915.00 0.4%
test-suite...T95/147.vortex/147.vortex.test 3770.00 3783.00 0.3%
test-suite...000/255.vortex/255.vortex.test 3771.00 3784.00 0.3%
test-suite :: External/Nurbs/nurbs.test 367.00 368.00 0.3%
test-suite...006/453.povray/453.povray.test 1616.00 1618.00 0.1%
test-suite...-typeset/consumer-typeset.test 3158.00 3161.00 0.1%
test-suite...ications/JM/lencod/lencod.test 8348.00 8354.00 0.1%

Tests: 243
Same hash: 209 (filtered out)
Remaining: 34
Metric: sccp.NumInstRemoved

Program base range diff
test-suite...peg2/mpeg2dec/mpeg2decode.test 75.00 164.00 118.7%
test-suite...urce/Applications/lua/lua.test 381.00 717.00 88.2%
test-suite...CFP2000/177.mesa/177.mesa.test 349.00 523.00 49.9%
test-suite...ks/Prolangs-C/agrep/agrep.test 25.00 29.00 16.0%
test-suite.../Applications/SPASS/SPASS.test 1913.00 2105.00 10.0%
test-suite...5/124.m88ksim/124.m88ksim.test 62.00 68.00 9.7%
test-suite...T2006/445.gobmk/445.gobmk.test 1067.00 1147.00 7.5%
test-suite...lications/ClamAV/clamscan.test 1046.00 1101.00 5.3%
test-suite.../CINT2000/176.gcc/176.gcc.test 2966.00 3068.00 3.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 6985.00 7087.00 1.5%
test-suite...ications/JM/lencod/lencod.test 1253.00 1270.00 1.4%
test-suite...CFP2006/444.namd/444.namd.test 174.00 175.00 0.6%
test-suite...marks/7zip/7zip-benchmark.test 1078.00 1084.00 0.6%
test-suite...T95/147.vortex/147.vortex.test 5896.00 5920.00 0.4%
test-suite...000/255.vortex/255.vortex.test 5896.00 5920.00 0.4%
test-suite...3.xalancbmk/483.xalancbmk.test 2969.00 2981.00 0.4%
test-suite...006/453.povray/453.povray.test 590.00 592.00 0.3%
test-suite...6/464.h264ref/464.h264ref.test 2222.00 2228.00 0.3%
test-suite...nal/skidmarks10/skidmarks.test 1444.00 1447.00 0.2%
test-suite...0.perlbench/400.perlbench.test 1153.00 1155.00 0.2%
test-suite...arks/mafft/pairlocalalign.test 3360.00 3364.00 0.1%
test-suite...-typeset/consumer-typeset.test 2988.00 2990.00 0.1%

llvm/test/Transforms/SCCP/ipsccp-notnull.ll

66 ↗

(On Diff #194752)

Will clean up the test case.

[fhahn]

Fix remaining issues, now passes LTO bootstrap of llvm/clang and the test-suite with various externals

[xbolva00]

llvm/include/llvm/Analysis/ValueLattice.h

39

Please add comment

[fhahn]

Remove ValueLattice changes from the diff.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

39

The ValueLattice changes have been added by accident to this review, sorry! They are in D60581 and forcedconstant might get removed as part of this series.

[fhahn]

ping

[fhahn]

ping

[fhahn]

ping

[davide]

Sorry for the long delay. I'm happy with this going in. @efriedma ?

[fhahn]

Ping. @efriedma do you have any thoughts about the general direction of this patch?

[fhahn]

ping. Eli, do you have any thoughts about the direction of the patch?

[efriedma]

Sorry about the delayed response.

So currently, this is essentially a three-patch series; D60581, D60582, and D61314. D61314 proposes to get rid of "forced" constants, and use plain constants instead. I'm a little confused how that works; are you just getting rid of the assertion that a constant can't have two different values?

How do constant ranges work with loops? It seems like under a naive implementation, an induction variable would start a 0, then grow to 0-1, then grow to 0-2, etc., until it covers the full integer range. That clearly doesn't happen, since it would take forever, but I'm not sure I understand the limiting factor. There's a comment in visitBinaryOperator about this, but does that cover all possible loops?

I'm a little wary of adding complexity to the lattice given the issues we currently have reasoning about the semantics of "undef"/ResolveUndefsIn.

llvm/lib/Transforms/Scalar/SCCP.cpp

1910

Does this change actually have an effect? An unconditional branch should always flow to its successor.

2149

This assertion makes no sense.

[fhahn]

In D60582#1611337, @efriedma wrote:

Sorry about the delayed response.

No worries, thank you very much for taking the time to take a look!

So currently, this is essentially a three-patch series; D60581, D60582, and D61314. D61314 proposes to get rid of "forced" constants, and use plain constants instead. I'm a little confused how that works; are you just getting rid of the assertion that a constant can't have two different values?

Sorry for not better organizing things. I wanted to make sure the overall direction makes sense (remove forcedconstant, use integer ranges) before re-arranging things. I'll rebase things and bring them in order and link them in Phab.

The idea here is to use the fact that integer constants are represented via a range, so they can have multiple values, and SCCP must take care of updating dependent instructions, if a range changes. This should allow us to get the same (or slightly more precise) behavior as forcedconstant: assume an arbitrary value and be sound when we later discover a different constant value for the same value.

When we used to assume a value through forcedconstant, we now just create a singleton integer range. Should we later discover a different constant value, instead of going to overdefined, we extend the range to include the new value and update the dependent instructions. I think for integer constants we can construct ranges for, that should work out fine.

For constants we cannot construct ranges for (e.g. floats or constants without specific integer value), we should still have the assertion (ValueLatticeElement should have the same assertions as the removed code from the ValueLattice in this file). Thinking about it again now, there might be some scenarios where we might hit it. It did not surface on a bootstrap build of LLVM with LTO, but I'll see if I can construct one.

How do constant ranges work with loops? It seems like under a naive implementation, an induction variable would start a 0, then grow to 0-1, then grow to 0-2, etc., until it covers the full integer range. That clearly doesn't happen, since it would take forever, but I'm not sure I understand the limiting factor. There's a comment in visitBinaryOperator about this, but does that cover all possible loops?

For operations where the original lattice value is a non-singleton range and the result of an operation is different (larger) range, we go to overdefined (around line 913). That should be the most conservative form of widening and should handle binary ops in loops, because we never extend a range more than once before going to overdefined. With might be able to use slightly more involved widening approaches later on.

We need this for all operators, I'll double check to make sure we do that for all operators.

I'm a little wary of adding complexity to the lattice given the issues we currently have reasoning about the semantics of "undef"/ResolveUndefsIn.

Understood, this change is quite disruptive. Is there anything in particular you are worried about/ anything I could do to sort out any issues there?

[fhahn]

Rebase and reduce diff as much as possible.

[merge_guards_bot]

Unit tests: pass. 61088 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[fhahn]

ping :)

I finally found some time to rebase this and I also tried to reduce the diff as far as possible!

This patch now just replaces SCCP's LatticeVal with ValueLatticeElement, without making additional use of constant ranges (besides for function arguments) just yet. As follow-up, I'll add patches making use of range information for various kinds of instructions. This patch itself should be a NFC (compiling test-suite & SPEC produces equal binaries with and without this change for -O3) and uses the following helpers to preserve the current behavior when constant ranges are used for integers:

• isConstant(LV): returns true when LV is either a constant or a constant range with a single element. This should return true in the same cases where LV.isConstant() returned true previously.
• getConstant(LV): returns a constant if LV is either a constant or a constant range with a single element. This should return a constant in the same cases as LV.getConstant() previously.
• getConstantInt(LV): same as getConstant, but additionally casted to ConstantInt.

In D60582#1612809, @fhahn wrote:

In D60582#1611337, @efriedma wrote:

How do constant ranges work with loops? It seems like under a naive implementation, an induction variable would start a 0, then grow to 0-1, then grow to 0-2, etc., until it covers the full integer range. That clearly doesn't happen, since it would take forever, but I'm not sure I understand the limiting factor. There's a comment in visitBinaryOperator about this, but does that cover all possible loops?

I've moved the widening to mergeInValue. This guarantees we set/extend a range at most once and go to overdefined otherwise. That should cover all loops. The one exception is when merging function argument values, but that should be fine, because the concrete argument value ranges can only extended at most once.

I'm a little wary of adding complexity to the lattice given the issues we currently have reasoning about the semantics of "undef"/ResolveUndefsIn.

The updated patches break things down much better I think and allow it to more carefully review the changes. I don't think there's an impact on ResolveUndefsIn at the moment, although begin more powerful might expose additional issues. But I think we could look at the issues as they appear.

[merge_guards_bot]

Unit tests: fail. 61129 tests passed, 3 failed and 728 were skipped.

failed: Clang.SemaOpenCL/numbered-address-space.cl
failed: libc++.std/thread/thread_mutex/thread_mutex_requirements/thread_timedmutex_requirements/thread_timedmutex_class/lock.pass.cpp
failed: lld.COFF/fixed.test

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[fhahn]

ping

[fhahn]

ping. Eli, do you think the updated approach makes more sense?

[efriedma]

I'm skeptical of the way this stack is handling forcedconstant... but probably makes more sense to discuss on D61314.

llvm/include/llvm/Analysis/ValueLattice.h

250

This is just a drive-by fix?

llvm/lib/Transforms/Scalar/SCCP.cpp

345–346

Is the IV.isConstant() here actually useful? Don't we always resolve constant integers to a ConstantRange?

409

This probably could be refined to handle cases that aren't actually loops, but probably fine as a first shot.

723

The point of "!isUnknownOrConstant()" instead of isOverdefined() is to exclude constant ranges? If that's right, could you use a positive name like "isOverdefinedOrConstantRange"?

[fhahn]

Address Eli's comments:

• change name of isUnknownOrConstant to isOverdefined
• simplify getConstantInt.

[fhahn]

ping

llvm/include/llvm/Analysis/ValueLattice.h

250

Yes, I moved that out to D73240

llvm/lib/Transforms/Scalar/SCCP.cpp

345–346

Is the IV.isConstant() here actually useful?

Not really, the check is not required, as getConstant() already handles that already.

Don't we always resolve constant integers to a ConstantRange?

I *think* I encountered some cases with integer constant expressions that do not resolve to a concrete integer (e.g. involving ptrtoint).

409

Agreed, I am planning on improving that as another follow-up, once the series of changes in in, so we have a better chance to spot issues through testing.

723

It excludes constant ranges with more than a single element and should cover exactly the same cases as the original LatticeVal::isOverdefined. I've changed the name to isOverdefined and also updated the comments for the helper functions.

[fhahn]

In D60582#1835258, @fhahn wrote:

ping

^ that was a stale comment that got accidentally submitted, when I just wanted to submit the responses to the inline comments. Sorry about that.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[fhahn]

rebase

[efriedma]

LGTM

[fhahn]

Thanks Eli! I'll try to land this at the end of next week, unless there are any regressions due to D61314.

[fhahn]

Given the progress with the ValueLatticeElement improvements with respect to dealing with undef and ranges and due to the fact that the problems only become practical issues with the follow up patches, do you think it is fine to land this initial change in the following days?

[efriedma]

Sure, I'm fine with landing this first.

[fhahn]

Rebased

llvm/include/llvm/Analysis/ValueLattice.h

enum ValueLatticeElementTy {
     /// "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,
 
     forcedconstant,
 
     /// 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,
public:
   }
   static ValueLatticeElement getOverdefined() {
     ValueLatticeElement Res;
     Res.markOverdefined();
     return Res;
   }
 
   bool isUndefined() const { return Tag == undefined; }
+  bool isUnknown() const { return Tag == undefined; }
   bool isConstant() const { return Tag == constant || Tag == forcedconstant; }
   bool isForcedConstant() const { return Tag == forcedconstant; }
   bool isNotConstant() const { return Tag == notconstant; }
   bool isConstantRange() const { return Tag == constantrange; }
   bool isOverdefined() const { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert((isConstant() || isForcedConstant()) &&
bool markNotConstant(Constant *V) {
     Tag = notconstant;
     ConstVal = V;
     return true;
   }
 
   bool markConstantRange(ConstantRange NewR) {
     if (isConstantRange()) {
       if (NewR.isEmptySet())
         markOverdefined();
       else {
         assert(getConstantRange().difference(NewR).isEmptySet());
         Range = std::move(NewR);
       }
       return true;
     }
 
     assert(isUndefined());

llvm/lib/Transforms/Scalar/SCCP.cpp

 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");
 
 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 {
-    /// unknown - This LLVM Value has no known value yet.
-    unknown,
-
-    /// constant - This LLVM Value has a specific constant value.
-    constant,
-
-    /// forcedconstant - This LLVM Value was thought to be undef until
-    /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
-    /// with another (different) constant, it goes to overdefined, instead of
-    /// asserting.
-    forcedconstant,
-
-    /// overdefined - This instruction is not known to be constant, and we know
-    /// 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 {
-    return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
-  }
-
-  bool isOverdefined() const { return getLatticeValue() == overdefined; }
-
-  Constant *getConstant() const {
-    assert(isConstant() && "Cannot get the constant of a non-constant!");
-    return Val.getPointer();
-  }
-
-  /// markOverdefined - Return true if this is a change in status.
-  bool markOverdefined() {
-    if (isOverdefined())
-      return false;
-
-    Val.setInt(overdefined);
-    return true;
-  }
-
-  /// markConstant - Return true if this is a change in status.
-  bool markConstant(Constant *V) {
-    if (getLatticeValue() == constant) { // Constant but not forcedconstant.
-      assert(getConstant() == V && "Marking constant with different value");
-      return false;
-    }
+// Use ValueLatticeElement as LatticeVal.
+using LatticeVal = ValueLatticeElement;
 
-    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
-      // forced value are possibly wrong.  Assuming this is another constant
-      // could expose a contradiction.
-      Val.setInt(overdefined);
-    }
-    return true;
-  }
+/// Helper to check if \p LV is either a constant or a constant
+/// range with a single element.
+bool isConstant(const LatticeVal &LV) {
+  return LV.isConstant() ||
+         (LV.isConstantRange() && LV.getConstantRange().isSingleElement());
 
-  /// getConstantInt - If this is a constant with a ConstantInt value, return it
-  /// otherwise return null.
-  ConstantInt *getConstantInt() const {
-    if (isConstant())
-      return dyn_cast<ConstantInt>(getConstant());
-    return nullptr;
-  }
+/// Helper to check if \p LV is either unknown, a constant or a constant range
+/// with a single element.
+bool isUnknownOrConstant(const LatticeVal &LV) {
+  return LV.isUnknown() || isConstant(LV);
 
-  /// getBlockAddress - If this is a constant with a BlockAddress value, return
-  /// it, otherwise return null.
-  BlockAddress *getBlockAddress() const {
-    if (isConstant())
-      return dyn_cast<BlockAddress>(getConstant());
-    return nullptr;
-  }
-
-  void markForcedConstant(Constant *V) {
-    assert(isUnknown() && "Can't force a defined value!");
-    Val.setInt(forcedconstant);
-    Val.setPointer(V);
-  }
-
-  ValueLatticeElement toValueLattice() const {
-    if (isOverdefined())
-      return ValueLatticeElement::getOverdefined();
-    if (isConstant())
-      return ValueLatticeElement::get(getConstant());
-    return ValueLatticeElement();
-  }
-};
-
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
 ///
 class SCCPSolver : public InstVisitor<SCCPSolver> {
   const DataLayout &DL;
   std::function<const TargetLibraryInfo &(Function &)> GetTLI;
   SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
   DenseMap<Value *, LatticeVal> ValueState;  // The state each value is in.
-  // The state each parameter is in.
-  DenseMap<Value *, ValueLatticeElement> ParamState;
 
   /// 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
   /// the global, to the currently known value.  If the value becomes
class SCCPSolver : public InstVisitor<SCCPSolver> {
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   DenseSet<Edge> KnownFeasibleEdges;
 
   DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
   DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
 
+  LLVMContext &Ctx;
+
 public:
   void addAnalysis(Function &F, AnalysisResultsForFn A) {
     AnalysisResults.insert({&F, std::move(A)});
   }
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
     auto A = AnalysisResults.find(I->getParent()->getParent());
     if (A == AnalysisResults.end())
       return nullptr;
     return A->second.PredInfo->getPredicateInfoFor(I);
   }
 
   DomTreeUpdater getDTU(Function &F) {
     auto A = AnalysisResults.find(&F);
     assert(A != AnalysisResults.end() && "Need analysis results for function.");
     return {A->second.DT, A->second.PDT, DomTreeUpdater::UpdateStrategy::Lazy};
   }
 
   SCCPSolver(const DataLayout &DL,
-             std::function<const TargetLibraryInfo &(Function &)> GetTLI)
-      : DL(DL), GetTLI(std::move(GetTLI)) {}
+             std::function<const TargetLibraryInfo &(Function &)> GetTLI,
+             LLVMContext &Ctx)
+      : DL(DL), GetTLI(std::move(GetTLI)), Ctx(Ctx) {}
 
   /// MarkBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   ///
   /// This returns true if the block was not considered live before.
   bool MarkBlockExecutable(BasicBlock *BB) {
     if (!BBExecutable.insert(BB).second)
       return false;
void markOverdefined(Value *V) {
     if (auto *STy = dyn_cast<StructType>(V->getType()))
       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
         markOverdefined(getStructValueState(V, i), V);
     else
       markOverdefined(ValueState[V], V);
   }
 
   // isStructLatticeConstant - Return true if all the lattice values
-  // corresponding to elements of the structure are not overdefined,
+  // corresponding to elements of the structure are constants,
   // false otherwise.
   bool isStructLatticeConstant(Function *F, StructType *STy) {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       const auto &It = TrackedMultipleRetVals.find(std::make_pair(F, i));
       assert(It != TrackedMultipleRetVals.end());
       LatticeVal LV = It->second;
-      if (LV.isOverdefined())
+      if (!isConstant(LV))
         return false;
     }
     return true;
   }
 
+  /// Helper to return a Constant if \p LV is either a constant or a constant
+  /// range with a single element.
+  Constant *getConstant(const LatticeVal &LV) const {
+    if (LV.isConstant())
+      return LV.getConstant();
+
+    if (LV.isConstantRange()) {
+      auto &CR = LV.getConstantRange();
+      if (CR.getSingleElement())
+        return ConstantInt::get(Ctx, *CR.getSingleElement());
+    }
+    return nullptr;
+  }
+
 private:
+  ConstantInt *getConstantInt(const LatticeVal &IV) const {
+    if (IV.isConstant())
+      return IV.getConstantInt();
+    return cast_or_null<ConstantInt>(getConstant(IV));
+  }
+
   // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
   void pushToWorkList(LatticeVal &IV, Value *V) {
     if (IV.isOverdefined())
       return OverdefinedInstWorkList.push_back(V);
     InstWorkList.push_back(V);
   }
 
+  // Helper to push \p V to the worklist, after updating it to \p IV. Also
+  // prints a debug message with the updated value.
+  void pushToWorkListMsg(LatticeVal &IV, Value *V) {
+    LLVM_DEBUG(dbgs() << "updated " << IV << ": " << *V << '\n');
+    if (IV.isOverdefined())
+      return OverdefinedInstWorkList.push_back(V);
+    InstWorkList.push_back(V);
+  }
+
   // markConstant - Make a value be marked as "constant".  If the value
   // is not already a constant, add it to the instruction work list so that
   // the users of the instruction are updated later.
   bool markConstant(LatticeVal &IV, Value *V, Constant *C) {
     if (!IV.markConstant(C)) return false;
     LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
     return true;
LLVM_DEBUG(dbgs() << "markOverdefined: ";
                << "Function '" << F->getName() << "'\n";
                else dbgs() << *V << '\n');
     // Only instructions go on the work list
     pushToWorkList(IV, V);
     return true;
   }
 
   bool mergeInValue(LatticeVal &IV, Value *V, LatticeVal MergeWithV) {
-    if (IV.isOverdefined() || MergeWithV.isUnknown())
-      return false; // Noop.
-    if (MergeWithV.isOverdefined())
-      return markOverdefined(IV, V);
-    if (IV.isUnknown())
-      return markConstant(IV, V, MergeWithV.getConstant());
-    if (IV.getConstant() != MergeWithV.getConstant())
-      return markOverdefined(IV, V);
+    // Do a simple form of widening, to avoid extending a range repeatedly in a
+    // loop. If IV is a constant range, it means we already set it once. If
+    // MergeWithV would extend IV, mark V as overdefined.
+    if (IV.isConstantRange() && !IV.getConstantRange().isSingleElement() &&
+        MergeWithV.isConstantRange()) {
+      const auto &IVRange = IV.getConstantRange();
+      const auto &MergeRange = MergeWithV.getConstantRange();
+      if (IVRange.contains(MergeRange))
+        return false;
+      markOverdefined(IV, V);
+      return true;
+    }
+    if (IV.mergeIn(MergeWithV, DL)) {
+      pushToWorkList(IV, V);
+      LLVM_DEBUG(dbgs() << "Merged " << MergeWithV << " into " << *V << " : "
+                        << IV << "\n");
+      return true;
+    }
     return false;
   }
 
   bool mergeInValue(Value *V, LatticeVal MergeWithV) {
     assert(!V->getType()->isStructTy() &&
            "non-structs should use markConstant");
     return mergeInValue(ValueState[V], V, MergeWithV);
   }
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;
   }
 
-  ValueLatticeElement &getParamState(Value *V) {
-    assert(!V->getType()->isStructTy() && "Should use getStructValueState");
-
-    std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
-        PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
-    ValueLatticeElement &LV = PI.first->second;
-    if (PI.second)
-      LV = getValueState(V).toValueLattice();
-
-    return LV;
-  }
-
   /// 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 #");
 
void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
   Succs.resize(TI.getNumSuccessors());
   if (auto *BI = dyn_cast<BranchInst>(&TI)) {
     if (BI->isUnconditional()) {
       Succs[0] = true;
       return;
     }
 
     LatticeVal BCValue = getValueState(BI->getCondition());
-    ConstantInt *CI = BCValue.getConstantInt();
+    ConstantInt *CI = getConstantInt(BCValue);
     if (!CI) {
       // Overdefined condition variables, and branches on unfoldable constant
       // conditions, mean the branch could go either way.
       if (!BCValue.isUnknown())
         Succs[0] = Succs[1] = true;
       return;
     }
 
void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
   }
 
   if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
     if (!SI->getNumCases()) {
       Succs[0] = true;
       return;
     }
     LatticeVal SCValue = getValueState(SI->getCondition());
-    ConstantInt *CI = SCValue.getConstantInt();
+    ConstantInt *CI = getConstantInt(SCValue);
 
     if (!CI) {   // Overdefined or unknown condition?
       // All destinations are executable!
       if (!SCValue.isUnknown())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
     return;
   }
 
   // In case of indirect branch and its address is a blockaddress, we mark
   // the target as executable.
   if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
     // Casts are folded by visitCastInst.
     LatticeVal IBRValue = getValueState(IBR->getAddress());
-    BlockAddress *Addr = IBRValue.getBlockAddress();
+    BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
     if (!Addr) {   // Overdefined or unknown condition?
       // All destinations are executable!
       if (!IBRValue.isUnknown())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     BasicBlock* T = Addr->getBasicBlock();

 void SCCPSolver::visitPHINode(PHINode &PN) {
   // If this PN returns a struct, just mark the result overdefined.
   // TODO: We could do a lot better than this if code actually uses this.
   if (PN.getType()->isStructTy())
     return (void)markOverdefined(&PN);
 
   if (getValueState(&PN).isOverdefined())
     return;  // Quick exit
 
   // Super-extra-high-degree PHI nodes are unlikely to ever be marked constant,
   // and slow us down a lot.  Just mark them overdefined.
   if (PN.getNumIncomingValues() > 64)
     return (void)markOverdefined(&PN);
 
   // Look at all of the executable operands of the PHI node.  If any of them
   // are overdefined, the PHI becomes overdefined as well.  If they are all
   // constant, and they agree with each other, the PHI becomes the identical
   // constant.  If they are constant and don't agree, the PHI is overdefined.
   // If there are no executable operands, the PHI remains unknown.
-  Constant *OperandVal = nullptr;
+  bool Changed = false;
   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     LatticeVal IV = getValueState(PN.getIncomingValue(i));
     if (IV.isUnknown()) continue;  // Doesn't influence PHI node.
 
     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
       continue;
 
-    if (IV.isOverdefined())    // PHI node becomes overdefined!
-      return (void)markOverdefined(&PN);
-
-    if (!OperandVal) {   // Grab the first value.
-      OperandVal = IV.getConstant();
-      continue;
-    }
-
-    // There is already a reachable operand.  If we conflict with it,
-    // then the PHI node becomes overdefined.  If we agree with it, we
-    // can continue on.
+    LatticeVal &Res = getValueState(&PN);
+    Changed |= Res.mergeIn(IV, DL);
 
-    // Check to see if there are two different constants merging, if so, the PHI
-    // node is overdefined.
-    if (IV.getConstant() != OperandVal)
-      return (void)markOverdefined(&PN);
+    if (Res.isOverdefined())
+      break;
   }
-
-  // If we exited the loop, this means that the PHI node only has constant
-  // arguments that agree with each other(and OperandVal is the constant) or
-  // OperandVal is null because there are no defined incoming arguments.  If
-  // this is the case, the PHI remains unknown.
-  if (OperandVal)
-    markConstant(&PN, OperandVal);      // Acquire operand value
+  if (Changed)
+    pushToWorkListMsg(ValueState[&PN], &PN);
 }
 
 void SCCPSolver::visitReturnInst(ReturnInst &I) {
   if (I.getNumOperands() == 0) return;  // ret void
 
   Function *F = I.getParent()->getParent();
   Value *ResultOp = I.getOperand(0);
 
void SCCPSolver::visitTerminator(Instruction &TI) {
   // Mark all feasible successors executable.
   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
     if (SuccFeasible[i])
       markEdgeExecutable(BB, TI.getSuccessor(i));
 }
 
 void SCCPSolver::visitCastInst(CastInst &I) {
   LatticeVal OpSt = getValueState(I.getOperand(0));
-  if (OpSt.isOverdefined())          // Inherit overdefinedness of operand
-    markOverdefined(&I);
-  else if (OpSt.isConstant()) {
+  if (Constant *OpC = getConstant(OpSt)) {
     // Fold the constant as we build.
-    Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(),
-                                          I.getType(), DL);
+    Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpC, I.getType(), DL);
     if (isa<UndefValue>(C))
       return;
     // Propagate constant value
     markConstant(&I, C);
-  }
+  } else if (!OpSt.isUnknown())
+    markOverdefined(&I);
 }
 
 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
   // If this returns a struct, mark all elements over defined, we don't track
   // structs in structs.
   if (EVI.getType()->isStructTy())
     return (void)markOverdefined(&EVI);
 
void SCCPSolver::visitSelectInst(SelectInst &I) {
   // TODO: We could do a lot better than this if code actually uses this.
   if (I.getType()->isStructTy())
     return (void)markOverdefined(&I);
 
   LatticeVal CondValue = getValueState(I.getCondition());
   if (CondValue.isUnknown())
     return;
 
-  if (ConstantInt *CondCB = CondValue.getConstantInt()) {
+  if (ConstantInt *CondCB = getConstantInt(CondValue)) {
     Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
     mergeInValue(&I, getValueState(OpVal));
     return;
   }
 
   // Otherwise, the condition is overdefined or a constant we can't evaluate.
   // See if we can produce something better than overdefined based on the T/F
   // value.
   LatticeVal TVal = getValueState(I.getTrueValue());
   LatticeVal FVal = getValueState(I.getFalseValue());
 
-  // select ?, C, C -> C.
-  if (TVal.isConstant() && FVal.isConstant() &&
-      TVal.getConstant() == FVal.getConstant())
-    return (void)markConstant(&I, FVal.getConstant());
-
-  if (TVal.isUnknown())   // select ?, undef, X -> X.
-    return (void)mergeInValue(&I, FVal);
-  if (FVal.isUnknown())   // select ?, X, undef -> X.
-    return (void)mergeInValue(&I, TVal);
-  markOverdefined(&I);
+  bool Changed = ValueState[&I].mergeIn(TVal, DL);
+  Changed |= ValueState[&I].mergeIn(FVal, DL);
+  if (Changed)
+    pushToWorkListMsg(ValueState[&I], &I);
 }
 
 // Handle Unary Operators.
 void SCCPSolver::visitUnaryOperator(Instruction &I) {
   LatticeVal V0State = getValueState(I.getOperand(0));
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;

 // Handle Binary Operators.
 void SCCPSolver::visitBinaryOperator(Instruction &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()) {
+  // If something is undef, wait for it to resolve.
+  if (V1State.isUnknown() || V2State.isUnknown())
+    return;
+
+  // TODO: could do better than that in some cases.
+  if (V1State.isNotConstant() || V2State.isNotConstant())
+    return (void)markOverdefined(&I);
+
+  if (V1State.isOverdefined() && V2State.isOverdefined())
+    return (void)markOverdefined(&I);
+
+  if (isConstant(V1State) && isConstant(V2State)) {
+    Constant *C = ConstantExpr::get(I.getOpcode(), getConstant(V1State),
+                                    getConstant(V2State));
+    if (isa<UndefValue>(C))
+      return;
+    return (void)markConstant(IV, &I, C);
+  }
+
+  if (!V1State.isOverdefined() && !V2State.isOverdefined()) {
+    // Deal with operands that are ranges.
+    if (V1State.isConstantRange() || V2State.isConstantRange()) {
+      ConstantRange A =
+          ConstantRange::getFull(I.getType()->getScalarSizeInBits());
+      ConstantRange B =
+          ConstantRange::getFull(I.getType()->getScalarSizeInBits());
+      if (V1State.isConstantRange())
+        A = V1State.getConstantRange();
+      if (V2State.isConstantRange())
+        B = V2State.getConstantRange();
+
+      ConstantRange R = A.binaryOp(cast<BinaryOperator>(&I)->getOpcode(), B);
+
+      mergeInValue(&I, LatticeVal::getRange(R));
+      return;
+    }
+
+    // Deal with non-integer constants.
+    assert(V1State.isConstant() && V2State.isConstant() &&
+           "Non-constants should be handled elsewhere");
+
     Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
                                     V2State.getConstant());
     // X op Y -> undef.
     if (isa<UndefValue>(C))
       return;
     return (void)markConstant(IV, &I, C);
   }
 
-  // If something is undef, wait for it to resolve.
-  if (!V1State.isOverdefined() && !V2State.isOverdefined())
-    return;
-
   // Otherwise, one of our operands is overdefined.  Try to produce something
   // better than overdefined with some tricks.
   // If this is 0 / Y, it doesn't matter that the second operand is
   // overdefined, and we can replace it with zero.
   if (I.getOpcode() == Instruction::UDiv || I.getOpcode() == Instruction::SDiv)
-    if (V1State.isConstant() && V1State.getConstant()->isNullValue())
-      return (void)markConstant(IV, &I, V1State.getConstant());
+    if (isConstant(V1State) && getConstant(V1State)->isNullValue())
+      return (void)markConstant(IV, &I, getConstant(V1State));
 
   // If this is:
   // -> AND/MUL with 0
   // -> OR with -1
   // it doesn't matter that the other operand is overdefined.
   if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
       I.getOpcode() == Instruction::Or) {
     LatticeVal *NonOverdefVal = nullptr;
-    if (!V1State.isOverdefined())
+    if (isUnknownOrConstant(V1State))
       NonOverdefVal = &V1State;
-    else if (!V2State.isOverdefined())
+    else if (isUnknownOrConstant(V2State))
       NonOverdefVal = &V2State;
 
     if (NonOverdefVal) {
       if (NonOverdefVal->isUnknown())
         return;
 
       if (I.getOpcode() == Instruction::And ||
           I.getOpcode() == Instruction::Mul) {
         // X and 0 = 0
         // X * 0 = 0
-        if (NonOverdefVal->getConstant()->isNullValue())
-          return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
+        if (getConstant(*NonOverdefVal)->isNullValue())
+          return (void)markConstant(IV, &I, getConstant(*NonOverdefVal));
       } else {
         // X or -1 = -1
-        if (ConstantInt *CI = NonOverdefVal->getConstantInt())
+        if (ConstantInt *CI = getConstantInt(*NonOverdefVal))
           if (CI->isMinusOne())
-            return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
+            return (void)markConstant(IV, &I, CI);
       }
     }
   }
 
   markOverdefined(&I);
 }
 
 // Handle ICmpInst instruction.
 void SCCPSolver::visitCmpInst(CmpInst &I) {
   // Do not cache this lookup, getValueState calls later in the function might
   // invalidate the reference.
   if (ValueState[&I].isOverdefined()) return;
 
   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();
+  LatticeVal V1State = getValueState(Op1);
+
+  LatticeVal V2State = getValueState(Op2);
+
+  // If operands are still unknown, wait for it to resolve.
+  if ((V1State.isUnknown() || V2State.isUnknown()))
+    return;
 
   Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
   if (C) {
     if (isa<UndefValue>(C))
       return;
     LatticeVal CV;
     CV.markConstant(C);
     mergeInValue(&I, CV);
     return;
   }
 
-  // If operands are still unknown, wait for it to resolve.
-  if (!V1State.isOverdefined() && !V2State.isOverdefined() &&
-      !ValueState[&I].isConstant())
-    return;
-
   markOverdefined(&I);
 }
 
 // Handle getelementptr instructions.  If all operands are constants then we
 // can turn this into a getelementptr ConstantExpr.
 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
   if (ValueState[&I].isOverdefined()) return;
 
   SmallVector<Constant*, 8> Operands;
   Operands.reserve(I.getNumOperands());
 
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
     LatticeVal State = getValueState(I.getOperand(i));
     if (State.isUnknown())
       return;  // Operands are not resolved yet.
 
     if (State.isOverdefined())
       return (void)markOverdefined(&I);
 
-    assert(State.isConstant() && "Unknown state!");
-    Operands.push_back(State.getConstant());
+    if (Constant *C = getConstant(State)) {
+      Operands.push_back(C);
+      continue;
+    }
+
+    return (void)markOverdefined(&I);
   }
 
   Constant *Ptr = Operands[0];
   auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
   Constant *C =
       ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
   if (isa<UndefValue>(C))
       return;
   markConstant(&I, C);
 }
 
 void SCCPSolver::visitStoreInst(StoreInst &SI) {
   // If this store is of a struct, ignore it.
   if (SI.getOperand(0)->getType()->isStructTy())
     return;
 
   if (TrackedGlobals.empty() || !isa<GlobalVariable>(SI.getOperand(1)))
     return;
 
   GlobalVariable *GV = cast<GlobalVariable>(SI.getOperand(1));
   DenseMap<GlobalVariable*, LatticeVal>::iterator I = TrackedGlobals.find(GV);
-  if (I == TrackedGlobals.end() || I->second.isOverdefined()) return;
+  if (I == TrackedGlobals.end()) return;
 
   // Get the value we are storing into the global, then merge it.
   mergeInValue(I->second, GV, getValueState(SI.getOperand(0)));
   if (I->second.isOverdefined())
     TrackedGlobals.erase(I);      // No need to keep tracking this!
 }
 
 // Handle load instructions.  If the operand is a constant pointer to a constant
 // global, we can replace the load with the loaded constant value!
 void SCCPSolver::visitLoadInst(LoadInst &I) {
   // If this load is of a struct, just mark the result overdefined.
   if (I.getType()->isStructTy())
     return (void)markOverdefined(&I);
 
   LatticeVal PtrVal = getValueState(I.getOperand(0));
   if (PtrVal.isUnknown()) return;   // The pointer is not resolved yet!
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
-  if (!PtrVal.isConstant() || I.isVolatile())
+  if (!isConstant(PtrVal) || I.isVolatile())
     return (void)markOverdefined(IV, &I);
 
-  Constant *Ptr = PtrVal.getConstant();
+  Constant *Ptr = getConstant(PtrVal);
 
   // load null is undefined.
   if (isa<ConstantPointerNull>(Ptr)) {
     if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
       return (void)markOverdefined(IV, &I);
     else
       return;
   }
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (CmpOp0 != CopyOf)
         std::swap(CmpOp0, CmpOp1);
 
       LatticeVal OriginalVal = getValueState(CopyOf);
       LatticeVal EqVal = getValueState(CmpOp1);
       LatticeVal &IV = ValueState[I];
       if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) {
         addAdditionalUser(CmpOp1, I);
-        if (OriginalVal.isConstant())
+        if (isConstant(OriginalVal))
           mergeInValue(IV, I, OriginalVal);
         else
           mergeInValue(IV, I, EqVal);
         return;
       }
       if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) {
         addAdditionalUser(CmpOp1, I);
-        if (OriginalVal.isConstant())
+        if (isConstant(OriginalVal))
           mergeInValue(IV, I, OriginalVal);
         else
           mergeInValue(IV, I, EqVal);
         return;
       }
 
       return (void)mergeInValue(IV, I, getValueState(CopyOf));
     }
if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
            AI != E; ++AI) {
         if (AI->get()->getType()->isStructTy())
           return markOverdefined(I); // Can't handle struct args.
         LatticeVal State = getValueState(*AI);
 
         if (State.isUnknown())
           return;  // Operands are not resolved yet.
-        if (State.isOverdefined())
+        if (!isConstant(State))
           return (void)markOverdefined(I);
-        assert(State.isConstant() && "Unknown state!");
-        Operands.push_back(State.getConstant());
+        Operands.push_back(getConstant(State));
       }
 
       if (getValueState(I).isOverdefined())
         return;
 
       // If we can constant fold this, mark the result of the call as a
       // constant.
       if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()), F,
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
         continue;
       }
 
       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.
-        LatticeVal ConcreteArgument = getValueState(*CAI);
-        bool ParamChanged =
-            getParamState(&*AI).mergeIn(ConcreteArgument.toValueLattice(), DL);
-         bool ValueChanged = mergeInValue(&*AI, ConcreteArgument);
-        // Add argument to work list, if the state of a parameter changes but
-        // ValueState does not change (because it is already overdefined there),
-        // We have to take changes in ParamState into account, as it is used
-        // when evaluating Cmp instructions.
-        if (!ValueChanged && ParamChanged)
-          pushToWorkList(ValueState[&*AI], &*AI);
-      }
+      } else
+        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))
       goto CallOverdefined;  // Not tracking this callee.
 
for (Instruction &I : BB) {
       // Anything taking a struct is conservatively assumed to require
       // overdefined markings.
       if (I.getOperand(0)->getType()->isStructTy()) {
         markOverdefined(&I);
         return true;
       }
       LatticeVal Op0LV = getValueState(I.getOperand(0));
       LatticeVal Op1LV;
+      Constant *C1 = nullptr;
       if (I.getNumOperands() == 2) {
         if (I.getOperand(1)->getType()->isStructTy()) {
           markOverdefined(&I);
           return true;
         }
 
         Op1LV = getValueState(I.getOperand(1));
+        C1 = getConstant(Op1LV);
       }
+
       // If this is an instructions whose result is defined even if the input is
       // not fully defined, propagate the information.
       Type *ITy = I.getType();
       switch (I.getOpcode()) {
       case Instruction::Add:
       case Instruction::Sub:
       case Instruction::Trunc:
       case Instruction::FPTrunc:
for (Instruction &I : BB) {
       case Instruction::SRem:
       case Instruction::URem:
         // X / undef -> undef.  No change.
         // X % undef -> undef.  No change.
         if (Op1LV.isUnknown()) break;
 
         // X / 0 -> undef.  No change.
         // X % 0 -> undef.  No change.
-        if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())
+        if (C1 && C1->isZeroValue())
           break;
 
         // undef / X -> 0.   X could be maxint.
         // undef % X -> 0.   X could be 1.
         markForcedConstant(&I, Constant::getNullValue(ITy));
         return true;
       case Instruction::AShr:
         // X >>a undef -> undef.
         if (Op1LV.isUnknown()) break;
 
         // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
+        if (auto *ShiftAmt = getConstantInt(Op1LV))
 
         // undef >>a X -> 0
         markForcedConstant(&I, Constant::getNullValue(ITy));
         return true;
       case Instruction::LShr:
       case Instruction::Shl:
         // X << undef -> undef.
         // X >> undef -> undef.
         if (Op1LV.isUnknown()) break;
 
         // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
+        if (auto *ShiftAmt = getConstantInt(Op1LV))
 
         // undef << X -> 0
         // undef >> X -> 0
         markForcedConstant(&I, Constant::getNullValue(ITy));
         return true;
       case Instruction::Select:
         Op1LV = getValueState(I.getOperand(1));
         // undef ? X : Y  -> X or Y.  There could be commonality between X/Y.
         if (Op0LV.isUnknown()) {
-          if (!Op1LV.isConstant())  // Pick the constant one if there is any.
+          if (!isConstant(Op1LV)) // Pick the constant one if there is any.
             Op1LV = getValueState(I.getOperand(2));
         } else if (Op1LV.isUnknown()) {
           // c ? undef : undef -> undef.  No change.
           Op1LV = getValueState(I.getOperand(2));
           if (Op1LV.isUnknown())
             break;
           // Otherwise, c ? undef : x -> x.
         } else {
           // Leave Op1LV as Operand(1)'s LatticeValue.
         }
 
-        if (Op1LV.isConstant())
-          markForcedConstant(&I, Op1LV.getConstant());
+        if (Constant *C = getConstant(Op1LV))
+          markForcedConstant(&I, C);
         else
           markOverdefined(&I);
         return true;
       case Instruction::Load:
         // A load here means one of two things: a load of undef from a global,
         // a load from an unknown pointer.  Either way, having it return undef
         // is okay.
         break;
bool SCCPSolver::ResolvedUndefsIn(Function &F) {
 
   return false;
 }
 
 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(); }))
+    if (any_of(IVs,
+               [](const LatticeVal &LV) { return !isUnknownOrConstant(LV); }))
       return false;
     std::vector<Constant *> ConstVals;
     auto *ST = 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()
+      ConstVals.push_back(isConstant(V)
+                              ? Solver.getConstant(V)
                               : UndefValue::get(ST->getElementType(i)));
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
     const LatticeVal &IV = Solver.getLatticeValueFor(V);
-    if (IV.isOverdefined())
+    if (!isUnknownOrConstant(IV))
       return false;
 
-    Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
+    Const = isConstant(IV) ? Solver.getConstant(IV)
+                           : UndefValue::get(V->getType());
   }
   assert(Const && "Constant is nullptr here!");
 
   // Replacing `musttail` instructions with constant breaks `musttail` invariant
   // unless the call itself can be removed
   CallInst *CI = dyn_cast<CallInst>(V);
   if (CI && CI->isMustTailCall() && !CI->isSafeToRemove()) {
     CallSite CS(CI);

 }
 
 // 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) {
   LLVM_DEBUG(dbgs() << "SCCP on function '" << F.getName() << "'\n");
   SCCPSolver Solver(
-      DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; });
+      DL, [TLI](Function &F) -> const TargetLibraryInfo & { return *TLI; },
+      F.getContext());
 
   // Mark the first block of the function as being executable.
   Solver.MarkBlockExecutable(&F.front());
 
   // Mark all arguments to the function as being overdefined.
   for (Argument &AI : F.args())
     Solver.markOverdefined(&AI);
 
static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) {
   Constant *C = nullptr;
   if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
     if (!isa<ConstantInt>(SI->getCondition())) {
       // Indeterminate switch; use first case value.
       Dest = SI->case_begin()->getCaseSuccessor();
       C = SI->case_begin()->getCaseValue();
     }
   } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
     if (!isa<ConstantInt>(BI->getCondition())) {
       // Indeterminate branch; use false.
       Dest = BI->getSuccessor(1);
       C = ConstantInt::getFalse(BI->getContext());
     }
   } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
     if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) {
       // Indeterminate indirectbr; use successor 0.
       Dest = IBR->getSuccessor(0);
if (C) {
 
     I->setOperand(0, C);
   }
 }
 
 bool llvm::runIPSCCP(
     Module &M, const DataLayout &DL,
     std::function<const TargetLibraryInfo &(Function &)> GetTLI,
     function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
-  SCCPSolver Solver(DL, GetTLI);
+  SCCPSolver Solver(DL, GetTLI, M.getContext());
 
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
     Solver.addAnalysis(F, getAnalysis(F));
bool llvm::runIPSCCP(
   // if the address of the function isn't taken.  In cases where a return is the
   // last use of a function, the order of processing functions would affect
   // whether other functions are optimizable.
   SmallVector<ReturnInst*, 8> ReturnsToZap;
 
   const MapVector<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     Function *F = I.first;
-    if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
+    if (!isUnknownOrConstant(I.second) || F->getReturnType()->isVoidTy())
       continue;
     findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   for (const auto &F : Solver.getMRVFunctionsTracked()) {
     assert(F->getReturnType()->isStructTy() &&
            "The return type should be a struct");
     StructType *STy = cast<StructType>(F->getReturnType());
     if (Solver.isStructLatticeConstant(F, STy))
       findReturnsToZap(*F, ReturnsToZap, Solver);
   }
 
   // Zap all returns which we've identified as zap to change.
   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
     Function *F = ReturnsToZap[i]->getParent()->getParent();
     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
   }
 
   // If we inferred constant or undef values for globals variables, we can
   // delete the global and any stores that remain to it.
   const DenseMap<GlobalVariable*, LatticeVal> &TG = Solver.getTrackedGlobals();
   for (DenseMap<GlobalVariable*, LatticeVal>::const_iterator I = TG.begin(),
          E = TG.end(); I != E; ++I) {
     GlobalVariable *GV = I->first;
-    assert(!I->second.isOverdefined() &&
-           "Overdefined values should have been taken out of the map!");
+    if (!isUnknownOrConstant(I->second))
+      continue;
     LLVM_DEBUG(dbgs() << "Found that GV '" << GV->getName()
                       << "' is constant!\n");
     while (!GV->use_empty()) {
       StoreInst *SI = cast<StoreInst>(GV->user_back());
       SI->eraseFromParent();
     }
     M.getGlobalList().erase(GV);
     ++IPNumGlobalConst;
   }
 
   return MadeChanges;
 }

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

entry:
   %call4 = tail call i32 @f2(i32 301)
   %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
-; CHECK: %res = select i1 %cmp, i32 1, i32 2
-; CHECK: ret i32 %res
+; CHECK-LABEL: define internal i32 @f3
+; CHECK: ret i32 undef
 define internal i32 @f3(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, 300
   %res = select i1 %cmp, i32 1, i32 2
   ret i32 %res
 }
 
+; CHECK-LABEL: @caller2
+; CHECK-LABEL: end:
+; CHECK-NEXT: %res = phi i32 [ 0, %entry ], [ 1, %if.true ]
+; CHECK-NEXT: %call1 = tail call i32 @f3(i32 %res)
+; CHECK-NEXT: ret i32 2
 ; 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
 

llvm/test/Transforms/SCCP/ipsccp-range-crashes.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -ipsccp -S %s | FileCheck %s
+
+; A few test cases exposing crashes with the initial range implementation.
+
+@global.2 = external dso_local unnamed_addr constant [25 x i8], align 1
+@global = internal local_unnamed_addr global i32 0, align 4
+@global.3 = internal local_unnamed_addr global i32 0, align 4
+
+define void @main(i8** %arg) {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds i8*, i8** [[ARG:%.*]], i64 undef
+; CHECK-NEXT:    [[TMP1:%.*]] = load i8*, i8** [[TMP]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = load i8, i8* [[TMP1]], align 1
+; CHECK-NEXT:    [[TMP3:%.*]] = sext i8 [[TMP2]] to i32
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP3]], 45
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i32 2, i32 4
+; CHECK-NEXT:    ret void
+;
+bb:
+  %tmp = getelementptr inbounds i8*, i8** %arg, i64 undef
+  %tmp1 = load i8*, i8** %tmp, align 8
+  %tmp2 = load i8, i8* %tmp1, align 1
+  %tmp3 = sext i8 %tmp2 to i32
+  %tmp4 = icmp ne i32 %tmp3, 45
+  %tmp5 = select i1 %tmp4, i32 2, i32 4
+  ret void
+}
+
+define void @ham() local_unnamed_addr {
+; CHECK-LABEL: @ham(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = icmp slt i32 undef, 40
+; CHECK-NEXT:    br i1 [[TMP]], label [[BB2:%.*]], label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB7:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i64 [ 0, [[BB1]] ], [ 15, [[BB3:%.*]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = add i64 [[TMP5]], add (i64 xor (i64 ptrtoint ([25 x i8]* @global.2 to i64), i64 -1), i64 1)
+; CHECK-NEXT:    unreachable
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB3]]
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  %tmp = icmp slt i32 undef, 40
+  br i1 %tmp, label %bb2, label %bb4
+
+bb2:                                              ; preds = %bb1
+  br label %bb7
+
+bb3:                                              ; preds = %bb7
+  br label %bb4
+
+bb4:                                              ; preds = %bb3, %bb1
+  %tmp5 = phi i64 [ 0, %bb1 ], [ %tmp10, %bb3 ]
+  %tmp6 = add i64 %tmp5, add (i64 xor (i64 ptrtoint ([25 x i8]* @global.2 to i64), i64 -1), i64 1)
+  unreachable
+
+bb7:                                              ; preds = %bb2
+  %tmp8 = add i64 0, 15
+  %tmp9 = add i64 %tmp8, 0
+  %tmp10 = add i64 %tmp9, 0
+  br label %bb3
+}
+
+declare i32 @barney.4()
+
+define void @wobble() {
+; CHECK-LABEL: @wobble(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* @global, align 4
+; CHECK-NEXT:    store i32 [[TMP]], i32* @global.3, align 4
+; CHECK-NEXT:    ret void
+;
+bb:
+  %tmp = load i32, i32* @global, align 4
+  store i32 %tmp, i32* @global.3, align 4
+  ret void
+}
+
+define i32 @wobble.5(i32 %arg) {
+bb:
+  %tmp = load i32, i32* @global.3, align 4
+  %tmp1 = sdiv i32 0, %tmp
+  ret i32 %tmp1
+}
+
+define void @eggs() {
+; CHECK-LABEL: @eggs(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[TMP2:%.*]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP2]] = add nsw i32 [[TMP]], 1
+; CHECK-NEXT:    [[TMP3:%.*]] = call i32 @barney.4()
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 1
+; CHECK-NEXT:    br i1 [[TMP4]], label [[BB1]], label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    store i32 [[TMP2]], i32* @global, align 4
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp = phi i32 [ 0, %bb ], [ %tmp2, %bb1 ]
+  %tmp2 = add nsw i32 %tmp, 1
+  %tmp3 = call i32 @barney.4()
+  %tmp4 = icmp eq i32 %tmp3, 1
+  br i1 %tmp4, label %bb1, label %bb5
+
+bb5:                                              ; preds = %bb1
+  store i32 %tmp2, i32* @global, align 4
+  ret void
+}

llvm/test/Transforms/SCCP/ipsccp-range-structs.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -sccp -S %s | FileCheck %s
+
+declare i32* @bar(i32) local_unnamed_addr #3
+
+; Function Attrs: nounwind ssp uwtable
+define { i8, i32* } @_ZN4llvm3EVT12getIntegerVTERNS_11LLVMContextEj(i32 %BitWidth) local_unnamed_addr #0 align 2 {
+; CHECK-LABEL: @_ZN4llvm3EVT12getIntegerVTERNS_11LLVMContextEj(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i32 [[BITWIDTH:%.*]], label [[IF_END:%.*]] [
+; CHECK-NEXT:    i32 1, label [[CLEANUP:%.*]]
+; CHECK-NEXT:    i32 8, label [[SW_BB1_I:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       sw.bb1.i:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CALL_I:%.*]] = tail call i32* @bar(i32 [[BITWIDTH]])
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[V1:%.*]] = phi i32* [ [[CALL_I]], [[IF_END]] ], [ null, [[SW_BB1_I]] ], [ null, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[V2:%.*]] = phi i8 [ 0, [[IF_END]] ], [ 3, [[SW_BB1_I]] ], [ 2, [[ENTRY]] ]
+; CHECK-NEXT:    [[DOTFCA_0_INSERT:%.*]] = insertvalue { i8, i32* } undef, i8 [[V2]], 0
+; CHECK-NEXT:    [[DOTFCA_1_INSERT:%.*]] = insertvalue { i8, i32* } [[DOTFCA_0_INSERT]], i32* [[V1]], 1
+; CHECK-NEXT:    ret { i8, i32* } [[DOTFCA_1_INSERT]]
+;
+entry:
+  switch i32 %BitWidth, label %if.end [
+  i32 1, label %cleanup
+  i32 8, label %sw.bb1.i
+  ]
+
+sw.bb1.i:                                         ; preds = %entry
+  br label %cleanup
+
+if.end:                                           ; preds = %entry
+  %call.i = tail call i32* @bar(i32 %BitWidth)
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %sw.bb1.i, %sw.bb2.i, %sw.bb3.i, %sw.bb4.i, %sw.bb5.i, %if.end
+  %v1 = phi i32* [ %call.i, %if.end ], [ null, %sw.bb1.i ], [ null, %entry ]
+  %v2 = phi i8 [ 0, %if.end ], [ 3, %sw.bb1.i ], [ 2, %entry ]
+  %.fca.0.insert = insertvalue { i8, i32* } undef, i8 %v2, 0
+  %.fca.1.insert = insertvalue { i8, i32* } %.fca.0.insert, i32* %v1, 1
+  ret { i8, i32* } %.fca.1.insert
+}