[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 ↗

(On Diff #197289)

Please add comment

[fhahn]

Remove ValueLattice changes from the diff.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

39 ↗

(On Diff #197289)

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

1867

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

2102

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 ↗

(On Diff #235423)

This is just a drive-by fix?

llvm/lib/Transforms/Scalar/SCCP.cpp

333–334

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

401

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

708

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 ↗

(On Diff #235423)

Yes, I moved that out to D73240

llvm/lib/Transforms/Scalar/SCCP.cpp

333–334

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).

401

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.

708

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/lib/Transforms/Scalar/SCCP.cpp

 STATISTIC(NumInstRemoved, "Number of instructions removed");
 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
 
 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
 
 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();
+/// Helper to return a Constant if \p IV is either a constant or a constant
+/// range with a single element.
+static Constant *getConstant(const ValueLatticeElement &IV, Type *T) {
+  if (IV.isConstant()) {
+    return IV.getConstant();
+  }
+  if (IV.isConstantRange()) {
+    auto &CR = IV.getConstantRange();
+    if (CR.getSingleElement())
+      return ConstantInt::get(T, *CR.getSingleElement());
   }
-
-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;
-    }
-
-    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;
-  }
-
-  /// 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;
-  }
-
-  /// 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();
-  }
-};
+//
+/// Helper to check if \p IV is either a constant or a constant
+/// range.
+bool isConstant(const ValueLatticeElement &IV) {
+  return IV.isConstant() ||
+         (IV.isConstantRange() && IV.getConstantRange().isSingleElement());
 
 //===----------------------------------------------------------------------===//
 //
 /// 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.
-  // The state each parameter is in.
-  DenseMap<Value *, ValueLatticeElement> ParamState;
+  DenseMap<Value *, ValueLatticeElement>
+      ValueState; // The state each value 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;
+  DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement> 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
   /// overdefined, it's entry is simply removed from this map.
-  DenseMap<GlobalVariable *, LatticeVal> TrackedGlobals;
+  DenseMap<GlobalVariable *, ValueLatticeElement> TrackedGlobals;
 
   /// TrackedRetVals - If we are tracking arguments into and the return
   /// value out of a function, it will have an entry in this map, indicating
   /// what the known return value for the function is.
-  DenseMap<Function *, LatticeVal> TrackedRetVals;
+  DenseMap<Function *, ValueLatticeElement> TrackedRetVals;
 
   /// TrackedMultipleRetVals - Same as TrackedRetVals, but used for functions
   /// that return multiple values.
-  DenseMap<std::pair<Function *, unsigned>, LatticeVal> TrackedMultipleRetVals;
+  DenseMap<std::pair<Function *, unsigned>, ValueLatticeElement>
+      TrackedMultipleRetVals;
 
   /// MRVFunctionsTracked - Each function in TrackedMultipleRetVals is
   /// represented here for efficient lookup.
   SmallPtrSet<Function *, 16> MRVFunctionsTracked;
 
   /// MustTailFunctions - Each function here is a callee of non-removable
   /// musttail call site.
   SmallPtrSet<Function *, 16> MustTailCallees;
public:
 
   /// TrackValueOfGlobalVariable - Clients can use this method to
   /// inform the SCCPSolver that it should track loads and stores to the
   /// specified global variable if it can.  This is only legal to call if
   /// performing Interprocedural SCCP.
   void TrackValueOfGlobalVariable(GlobalVariable *GV) {
     // We only track the contents of scalar globals.
     if (GV->getValueType()->isSingleValueType()) {
-      LatticeVal &IV = TrackedGlobals[GV];
+      ValueLatticeElement &IV = TrackedGlobals[GV];
       if (!isa<UndefValue>(GV->getInitializer()))
         IV.markConstant(GV->getInitializer());
     }
   }
 
   /// AddTrackedFunction - If the SCCP solver is supposed to track calls into
   /// and out of the specified function (which cannot have its address taken),
   /// this method must be called.
   void AddTrackedFunction(Function *F) {
     // Add an entry, F -> undef.
     if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
       MRVFunctionsTracked.insert(F);
       for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
-        TrackedMultipleRetVals.insert(std::make_pair(std::make_pair(F, i),
-                                                     LatticeVal()));
+        TrackedMultipleRetVals.insert(
+            std::make_pair(std::make_pair(F, i), ValueLatticeElement()));
     } else
-      TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
+      TrackedRetVals.insert(std::make_pair(F, ValueLatticeElement()));
   }
 
   /// AddMustTailCallee - If the SCCP solver finds that this function is called
   /// from non-removable musttail call site.
   void AddMustTailCallee(Function *F) {
     MustTailCallees.insert(F);
   }
 
public:
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
   // block to the 'To' basic block is currently feasible.
   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
 
-  std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
-    std::vector<LatticeVal> StructValues;
+  std::vector<ValueLatticeElement>
+  getStructValueLatticeElementFor(Value *V) const {
+    std::vector<ValueLatticeElement> StructValues;
     auto *STy = dyn_cast<StructType>(V->getType());
-    assert(STy && "getStructLatticeValueFor() can be called only on structs");
+    assert(STy &&
+           "getStructValueLatticeElementueFor() can be called only on structs");
     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;
   }
 
-  const LatticeVal &getLatticeValueFor(Value *V) const {
+  ValueLatticeElement &getValueLatticeElementFor(Value *V) {
     assert(!V->getType()->isStructTy() &&
-           "Should use getStructLatticeValueFor");
-    DenseMap<Value *, LatticeVal>::const_iterator I = ValueState.find(V);
+           "Should use getStructValueLatticeElementueFor");
+    DenseMap<Value *, ValueLatticeElement>::iterator I = ValueState.find(V);
     assert(I != ValueState.end() &&
            "V not found in ValueState nor Paramstate map!");
     return I->second;
   }
 
   /// getTrackedRetVals - Get the inferred return value map.
-  const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
+  const DenseMap<Function *, ValueLatticeElement> &getTrackedRetVals() {
     return TrackedRetVals;
   }
 
   /// getTrackedGlobals - Get and return the set of inferred initializers for
   /// global variables.
-  const DenseMap<GlobalVariable*, LatticeVal> &getTrackedGlobals() {
+  const DenseMap<GlobalVariable *, ValueLatticeElement> &getTrackedGlobals() {
     return TrackedGlobals;
   }
 
   /// getMRVFunctionsTracked - Get the set of functions which return multiple
   /// values tracked by the pass.
   const SmallPtrSet<Function *, 16> getMRVFunctionsTracked() {
     return MRVFunctionsTracked;
   }
public:
 
   // isStructLatticeConstant - Return true if all the lattice values
   // corresponding to elements of the structure are not overdefined,
   // 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())
+      ValueLatticeElement LV = It->second;
+      if (!isConstant(LV))
         return false;
     }
     return true;
   }
 
 private:
+  ConstantInt *getConstantInt(const ValueLatticeElement &IV, Value *V) const {
+    if (IV.isConstant() || IV.isForcedConstant())
+      return IV.getConstantInt();
+
+    if (IV.isConstantRange()) {
+      auto &CR = IV.getConstantRange();
+      if (CR.getSingleElement())
+        return ConstantInt::get(V->getContext(), *CR.getSingleElement());
+    }
+    return nullptr;
+  }
   // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
-  void pushToWorkList(LatticeVal &IV, Value *V) {
+  void pushToWorkList(ValueLatticeElement &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(ValueLatticeElement &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) {
+  bool markConstant(ValueLatticeElement &IV, Value *V, Constant *C) {
     if (!IV.markConstant(C)) return false;
     LLVM_DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
     return true;
   }
 
   bool markConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
     return markConstant(ValueState[V], V, C);
   }
 
   void markForcedConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
-    LatticeVal &IV = ValueState[V];
+    ValueLatticeElement &IV = ValueState[V];
     IV.markForcedConstant(C);
     LLVM_DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
   }
 
   // markOverdefined - Make a value be marked as "overdefined". If the
   // value is not already overdefined, add it to the overdefined instruction
   // work list so that the users of the instruction are updated later.
-  bool markOverdefined(LatticeVal &IV, Value *V) {
+  bool markOverdefined(ValueLatticeElement &IV, Value *V) {
     if (!IV.markOverdefined()) return false;
 
     LLVM_DEBUG(dbgs() << "markOverdefined: ";
                if (auto *F = dyn_cast<Function>(V)) dbgs()
                << "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);
+  bool mergeInValue(ValueLatticeElement &IV, Value *V,
+                    ValueLatticeElement MergeWithV) {
+    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) {
+  bool mergeInValue(Value *V, ValueLatticeElement MergeWithV) {
     assert(!V->getType()->isStructTy() &&
            "non-structs should use markConstant");
     return mergeInValue(ValueState[V], V, MergeWithV);
   }
 
-  /// getValueState - Return the LatticeVal object that corresponds to the
-  /// value.  This function handles the case when the value hasn't been seen yet
-  /// by properly seeding constants etc.
-  LatticeVal &getValueState(Value *V) {
+  /// getValueState - Return the ValueLatticeElement object that corresponds to
+  /// the value.  This function handles the case when the value hasn't been seen
+  /// yet by properly seeding constants etc.
+  ValueLatticeElement &getValueState(Value *V) {
     assert(!V->getType()->isStructTy() && "Should use getStructValueState");
 
-    std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
-      ValueState.insert(std::make_pair(V, LatticeVal()));
-    LatticeVal &LV = I.first->second;
+    std::pair<DenseMap<Value *, ValueLatticeElement>::iterator, bool> I =
+        ValueState.insert(std::make_pair(V, ValueLatticeElement()));
+    ValueLatticeElement &LV = I.first->second;
 
     if (!I.second)
       return LV;  // Common case, already in the map.
 
     if (auto *C = dyn_cast<Constant>(V)) {
       // Undef values remain unknown.
       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) {
+  /// getStructValueState - Return the ValueLatticeElement 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.
+  ValueLatticeElement &getStructValueState(Value *V, unsigned i) {
     assert(V->getType()->isStructTy() && "Should use getValueState");
     assert(i < cast<StructType>(V->getType())->getNumElements() &&
            "Invalid element #");
 
-    std::pair<DenseMap<std::pair<Value*, unsigned>, LatticeVal>::iterator,
-              bool> I = StructValueState.insert(
-                        std::make_pair(std::make_pair(V, i), LatticeVal()));
-    LatticeVal &LV = I.first->second;
+    std::pair<
+        DenseMap<std::pair<Value *, unsigned>, ValueLatticeElement>::iterator,
+        bool>
+        I = StructValueState.insert(
+            std::make_pair(std::make_pair(V, i), ValueLatticeElement()));
+    ValueLatticeElement &LV = I.first->second;
 
     if (!I.second)
       return LV;  // Common case, already in the map.
 
     if (auto *C = dyn_cast<Constant>(V)) {
       Constant *Elt = C->getAggregateElement(i);
 
       if (!Elt)
void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
                                        SmallVectorImpl<bool> &Succs) {
   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();
+    ValueLatticeElement BCValue = getValueState(BI->getCondition());
+    ConstantInt *CI = getConstantInt(BCValue, BI->getCondition());
     if (!CI) {
       // Overdefined condition variables, and branches on unfoldable constant
       // conditions, mean the branch could go either way.
-      if (!BCValue.isUnknown())
+      if (!BCValue.isUndefined())
         Succs[0] = Succs[1] = true;
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way.
     Succs[CI->isZero()] = true;
     return;
   }
 
   // Unwinding instructions successors are always executable.
   if (TI.isExceptionalTerminator()) {
     Succs.assign(TI.getNumSuccessors(), true);
     return;
   }
 
   if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
     if (!SI->getNumCases()) {
       Succs[0] = true;
       return;
     }
-    LatticeVal SCValue = getValueState(SI->getCondition());
-    ConstantInt *CI = SCValue.getConstantInt();
+    ValueLatticeElement SCValue = getValueState(SI->getCondition());
+    ConstantInt *CI = getConstantInt(SCValue, SI->getCondition());
 
     if (!CI) {   // Overdefined or unknown condition?
       // All destinations are executable!
-      if (!SCValue.isUnknown())
+      if (!SCValue.isUndefined())
         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();
+    ValueLatticeElement IBRValue = getValueState(IBR->getAddress());
+    BlockAddress *Addr = IBRValue.isConstant()
+                             ? dyn_cast<BlockAddress>(IBRValue.getConstant())
+                             : nullptr;
     if (!Addr) {   // Overdefined or unknown condition?
       // All destinations are executable!
-      if (!IBRValue.isUnknown())
+      if (!IBRValue.isUndefined())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     BasicBlock* T = Addr->getBasicBlock();
     assert(Addr->getFunction() == T->getParent() &&
            "Block address of a different function ?");
     for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {

 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.
+    ValueLatticeElement IV = getValueState(PN.getIncomingValue(i));
+    if (IV.isUndefined())
+      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;
-    }
+    ValueLatticeElement &Res = getValueState(&PN);
+    Changed |= Res.mergeIn(IV, DL);
 
-    // 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.
-
-    // 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);
 
   // If we are tracking the return value of this function, merge it in.
   if (!TrackedRetVals.empty() && !ResultOp->getType()->isStructTy()) {
-    DenseMap<Function*, LatticeVal>::iterator TFRVI =
+    DenseMap<Function *, ValueLatticeElement>::iterator TFRVI =
         TrackedRetVals.find(F);
     if (TFRVI != TrackedRetVals.end()) {
       mergeInValue(TFRVI->second, F, getValueState(ResultOp));
       return;
     }
   }
 
   // Handle functions that return multiple values.
   if (!TrackedMultipleRetVals.empty()) {
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()) {
+  ValueLatticeElement OpSt = getValueState(I.getOperand(0));
+  if (Constant *OpC = getConstant(OpSt, I.getOperand(0)->getType())) {
     // 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.isUndefined())
+    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);
 
   // If this is extracting from more than one level of struct, we don't know.
   if (EVI.getNumIndices() != 1)
     return (void)markOverdefined(&EVI);
 
   Value *AggVal = EVI.getAggregateOperand();
   if (AggVal->getType()->isStructTy()) {
     unsigned i = *EVI.idx_begin();
-    LatticeVal EltVal = getStructValueState(AggVal, i);
+    ValueLatticeElement EltVal = getStructValueState(AggVal, i);
     mergeInValue(getValueState(&EVI), &EVI, EltVal);
   } else {
     // Otherwise, must be extracting from an array.
     return (void)markOverdefined(&EVI);
   }
 }
 
 void SCCPSolver::visitInsertValueInst(InsertValueInst &IVI) {
   auto *STy = dyn_cast<StructType>(IVI.getType());
   if (!STy)
     return (void)markOverdefined(&IVI);
 
   // If this has more than one index, we can't handle it, drive all results to
   // undef.
   if (IVI.getNumIndices() != 1)
     return (void)markOverdefined(&IVI);
 
   Value *Aggr = IVI.getAggregateOperand();
   unsigned Idx = *IVI.idx_begin();
 
   // Compute the result based on what we're inserting.
   for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
     // This passes through all values that aren't the inserted element.
     if (i != Idx) {
-      LatticeVal EltVal = getStructValueState(Aggr, i);
+      ValueLatticeElement EltVal = getStructValueState(Aggr, i);
       mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
       continue;
     }
 
     Value *Val = IVI.getInsertedValueOperand();
     if (Val->getType()->isStructTy())
       // We don't track structs in structs.
       markOverdefined(getStructValueState(&IVI, i), &IVI);
     else {
-      LatticeVal InVal = getValueState(Val);
+      ValueLatticeElement InVal = getValueState(Val);
       mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
     }
   }
 }
 
 void SCCPSolver::visitSelectInst(SelectInst &I) {
   // If this select returns a struct, just mark the result overdefined.
   // 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())
+  ValueLatticeElement CondValue = getValueState(I.getCondition());
+  if (CondValue.isUndefined())
     return;
 
-  if (ConstantInt *CondCB = CondValue.getConstantInt()) {
+  if (ConstantInt *CondCB = getConstantInt(CondValue, &I)) {
     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());
+  ValueLatticeElement TVal = getValueState(I.getTrueValue());
+  ValueLatticeElement 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 Binary Operators.
 void SCCPSolver::visitBinaryOperator(Instruction &I) {
-  LatticeVal V1State = getValueState(I.getOperand(0));
-  LatticeVal V2State = getValueState(I.getOperand(1));
+  ValueLatticeElement V1State = getValueState(I.getOperand(0));
+  ValueLatticeElement V2State = getValueState(I.getOperand(1));
 
-  LatticeVal &IV = ValueState[&I];
+  ValueLatticeElement &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
-  if (V1State.isConstant() && V2State.isConstant()) {
+  // If something is undef, wait for it to resolve.
+  if (V1State.isUndefined() || V2State.isUndefined())
+    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, I.getOperand(0)->getType()),
+        getConstant(V2State, I.getOperand(1)->getType()));
+    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);
+
+      // Very simple widening. If we set a range twice, go to overdefined.
+      if (!IV.isConstantRange() || IV.getConstantRange() == R)
+        mergeInValue(&I, ValueLatticeElement::getRange(R));
+      else
+        markOverdefined(&I);
+      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 (Constant *C = getConstant(V1State, I.getOperand(0)->getType()))
+      if (C->isNullValue())
+        return (void)mergeInValue(&I, ValueLatticeElement::get(C));
 
   // 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())
+    ValueLatticeElement *NonOverdefVal = nullptr;
+    if (isConstant(V1State))
       NonOverdefVal = &V1State;
-    else if (!V2State.isOverdefined())
+    else if (isConstant(V2State))
       NonOverdefVal = &V2State;
 
     if (NonOverdefVal) {
-      if (NonOverdefVal->isUnknown())
+      Constant *CNonOver = getConstant(*NonOverdefVal, I.getType());
+      if (NonOverdefVal->isUndefined() || !CNonOver)
         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, I.getType())->isNullValue())
+          return (void)mergeInValue(&I, *NonOverdefVal);
       } else {
         // X or -1 = -1
-        if (ConstantInt *CI = NonOverdefVal->getConstantInt())
+        if (ConstantInt *CI = getConstantInt(*NonOverdefVal, &I))
           if (CI->isMinusOne())
-            return (void)markConstant(IV, &I, NonOverdefVal->getConstant());
+            return (void)mergeInValue(&I, *NonOverdefVal);
       }
     }
   }
 
   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();
+  ValueLatticeElement V1State = getValueState(Op1);
+
+  ValueLatticeElement V2State = getValueState(Op2);
+
+  // If operands are still unknown, wait for it to resolve.
+  if ((V1State.isUndefined() || V2State.isUndefined()))
+    return;
 
   Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
   if (C) {
     if (isa<UndefValue>(C))
       return;
-    LatticeVal CV;
+    ValueLatticeElement 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())
+    ValueLatticeElement State = getValueState(I.getOperand(i));
+    if (State.isUndefined())
       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, I.getOperand(i)->getType())) {
+      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);
+  mergeInValue(&I, ValueLatticeElement::get(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;
+  DenseMap<GlobalVariable *, ValueLatticeElement>::iterator I =
+      TrackedGlobals.find(GV);
+  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!
+  ValueLatticeElement PtrVal = getValueState(I.getOperand(0));
+  if (PtrVal.isUndefined())
+    return; // The pointer is not resolved yet!
 
-  LatticeVal &IV = ValueState[&I];
+  ValueLatticeElement &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, I.getType());
 
   // load null is undefined.
   if (isa<ConstantPointerNull>(Ptr)) {
     if (NullPointerIsDefined(I.getFunction(), I.getPointerAddressSpace()))
       return (void)markOverdefined(IV, &I);
     else
       return;
   }
 
   // Transform load (constant global) into the value loaded.
   if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
     if (!TrackedGlobals.empty()) {
       // If we are tracking this global, merge in the known value for it.
-      DenseMap<GlobalVariable*, LatticeVal>::iterator It =
+      DenseMap<GlobalVariable *, ValueLatticeElement>::iterator It =
           TrackedGlobals.find(GV);
       if (It != TrackedGlobals.end()) {
-        mergeInValue(IV, &I, It->second);
+        mergeInValue(&I, It->second);
         return;
       }
     }
   }
 
   // Transform load from a constant into a constant if possible.
   if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
     if (isa<UndefValue>(C))
if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
       if (CopyOf != CmpOp0 && CopyOf != CmpOp1) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
       if (CmpOp0 != CopyOf)
         std::swap(CmpOp0, CmpOp1);
 
-      LatticeVal OriginalVal = getValueState(CopyOf);
-      LatticeVal EqVal = getValueState(CmpOp1);
-      LatticeVal &IV = ValueState[I];
+      ValueLatticeElement OriginalVal = getValueState(CopyOf);
+      ValueLatticeElement EqVal = getValueState(CmpOp1);
+      ValueLatticeElement &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));
     }
CallOverdefined:
     // a declaration, maybe we can constant fold it.
     if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
         canConstantFoldCallTo(cast<CallBase>(CS.getInstruction()), F)) {
       SmallVector<Constant*, 8> Operands;
       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);
+        ValueLatticeElement State = getValueState(*AI);
 
-        if (State.isUnknown())
+        if (State.isUndefined())
           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, (*AI)->getType()));
       }
 
       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();
       // will be an implicit copy formed of the input aggregate.
       if (AI->hasByValAttr() && !F->onlyReadsMemory()) {
         markOverdefined(&*AI);
         continue;
       }
 
       if (auto *STy = dyn_cast<StructType>(AI->getType())) {
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
-          LatticeVal CallArg = getStructValueState(*CAI, i);
+          ValueLatticeElement 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);
+        ValueLatticeElement ConcreteArgument = getValueState(*CAI);
+        // dbgs() << "Concrete " << ConcreteArgument << "\n";
+        mergeInValue(&*AI, ConcreteArgument);
       }
     }
   }
 
   // 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.
 
     // If we are tracking this callee, propagate the result of the function
     // into this call site.
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
       mergeInValue(getStructValueState(I, i), I,
                    TrackedMultipleRetVals[std::make_pair(F, i)]);
   } else {
-    DenseMap<Function*, LatticeVal>::iterator TFRVI = TrackedRetVals.find(F);
+    DenseMap<Function *, ValueLatticeElement>::iterator TFRVI =
+        TrackedRetVals.find(F);
     if (TFRVI == TrackedRetVals.end())
       goto CallOverdefined;  // Not tracking this callee.
 
     // If so, propagate the return value of the callee into this call result.
     mergeInValue(I, TFRVI->second);
   }
 }
 
for (Instruction &I : BB) {
         // extractvalue and insertvalue don't need to be marked; they are
         // tracked as precisely as their operands.
         if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
           continue;
 
         // Send the results of everything else to overdefined.  We could be
         // more precise than this but it isn't worth bothering.
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
-          LatticeVal &LV = getStructValueState(&I, i);
-          if (LV.isUnknown())
+          ValueLatticeElement &LV = getStructValueState(&I, i);
+          if (LV.isUndefined())
             markOverdefined(LV, &I);
         }
         continue;
       }
 
-      LatticeVal &LV = getValueState(&I);
-      if (!LV.isUnknown()) continue;
+      ValueLatticeElement &LV = getValueState(&I);
+      if (!LV.isUndefined())
+        continue;
 
       // extractvalue is safe; check here because the argument is a struct.
       if (isa<ExtractValueInst>(I))
         continue;
 
-      // Compute the operand LatticeVals, for convenience below.
+      // Compute the operand ValueLatticeElements, for convenience below.
       // 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;
+      ValueLatticeElement Op0LV = getValueState(I.getOperand(0));
+      ValueLatticeElement 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, I.getOperand(1)->getType());
       }
+
       // 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:
       case Instruction::BitCast:
         break; // Any undef -> undef
       case Instruction::FSub:
       case Instruction::FAdd:
       case Instruction::FMul:
       case Instruction::FDiv:
       case Instruction::FRem:
         // Floating-point binary operation: be conservative.
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
+        if (Op0LV.isUndefined() && Op1LV.isUndefined())
           markForcedConstant(&I, Constant::getNullValue(ITy));
         else
           markOverdefined(&I);
         return true;
       case Instruction::ZExt:
       case Instruction::SExt:
       case Instruction::FPToUI:
       case Instruction::FPToSI:
       case Instruction::FPExt:
       case Instruction::PtrToInt:
       case Instruction::IntToPtr:
       case Instruction::SIToFP:
       case Instruction::UIToFP:
         // undef -> 0; some outputs are impossible
         markForcedConstant(&I, Constant::getNullValue(ITy));
         return true;
       case Instruction::Mul:
       case Instruction::And:
         // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
+        if (Op0LV.isUndefined() && Op1LV.isUndefined())
           break;
         // undef * X -> 0.   X could be zero.
         // undef & X -> 0.   X could be zero.
         markForcedConstant(&I, Constant::getNullValue(ITy));
         return true;
       case Instruction::Or:
         // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
+        if (Op0LV.isUndefined() && Op1LV.isUndefined())
           break;
         // undef | X -> -1.   X could be -1.
         markForcedConstant(&I, Constant::getAllOnesValue(ITy));
         return true;
       case Instruction::Xor:
         // undef ^ undef -> 0; strictly speaking, this is not strictly
         // necessary, but we try to be nice to people who expect this
         // behavior in simple cases
-        if (Op0LV.isUnknown() && Op1LV.isUnknown()) {
+        if (Op0LV.isUndefined() && Op1LV.isUndefined()) {
           markForcedConstant(&I, Constant::getNullValue(ITy));
           return true;
         }
         // undef ^ X -> undef
         break;
       case Instruction::SDiv:
       case Instruction::UDiv:
       case Instruction::SRem:
       case Instruction::URem:
         // X / undef -> undef.  No change.
         // X % undef -> undef.  No change.
-        if (Op1LV.isUnknown()) break;
+        if (Op1LV.isUndefined())
+          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;
+        if (Op1LV.isUndefined())
+          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, &I))
 
         // 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;
+        if (Op1LV.isUndefined())
+          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, &I))
 
         // 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 (Op0LV.isUndefined()) {
+          if (!isConstant(Op1LV)) // Pick the constant one if there is any.
             Op1LV = getValueState(I.getOperand(2));
-        } else if (Op1LV.isUnknown()) {
+        } else if (Op1LV.isUndefined()) {
           // c ? undef : undef -> undef.  No change.
           Op1LV = getValueState(I.getOperand(2));
-          if (Op1LV.isUnknown())
+          if (Op1LV.isUndefined())
             break;
           // Otherwise, c ? undef : x -> x.
         } else {
-          // Leave Op1LV as Operand(1)'s LatticeValue.
+          // Leave Op1LV as Operand(1)'s ValueLatticeElementue.
         }
 
-        if (Op1LV.isConstant())
-          markForcedConstant(&I, Op1LV.getConstant());
+        if (Constant *C = getConstant(Op1LV, I.getOperand(1)->getType()))
+          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;
       case Instruction::ICmp:
         // X == undef -> undef.  Other comparisons get more complicated.
         Op0LV = getValueState(I.getOperand(0));
         Op1LV = getValueState(I.getOperand(1));
 
-        if ((Op0LV.isUnknown() || Op1LV.isUnknown()) &&
+        if ((Op0LV.isUndefined() || Op1LV.isUndefined()) &&
             cast<ICmpInst>(&I)->isEquality())
           break;
         markOverdefined(&I);
         return true;
       case Instruction::Call:
       case Instruction::Invoke:
       case Instruction::CallBr:
         // There are two reasons a call can have an undef result
for (BasicBlock &BB : F) {
     }
 
     // Check to see if we have a branch or switch on an undefined value.  If so
     // we force the branch to go one way or the other to make the successor
     // values live.  It doesn't really matter which way we force it.
     Instruction *TI = BB.getTerminator();
     if (auto *BI = dyn_cast<BranchInst>(TI)) {
       if (!BI->isConditional()) continue;
-      if (!getValueState(BI->getCondition()).isUnknown())
+      if (!getValueState(BI->getCondition()).isUndefined())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // false.
       if (isa<UndefValue>(BI->getCondition())) {
         BI->setCondition(ConstantInt::getFalse(BI->getContext()));
         markEdgeExecutable(&BB, TI->getSuccessor(1));
         return true;
for (BasicBlock &BB : F) {
     }
 
    if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
       // Indirect branch with no successor ?. Its ok to assume it branches
       // to no target.
       if (IBR->getNumSuccessors() < 1)
         continue;
 
-      if (!getValueState(IBR->getAddress()).isUnknown())
+      if (!getValueState(IBR->getAddress()).isUndefined())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // the first successor of the indirect branch.
       if (isa<UndefValue>(IBR->getAddress())) {
         IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
         markEdgeExecutable(&BB, IBR->getSuccessor(0));
         return true;
       }
 
       // Otherwise, it is a branch on a symbolic value which is currently
       // considered to be undef.  Make sure some edge is executable, so a
       // branch on "undef" always flows somewhere.
       // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
       // we can assume the branch has undefined behavior instead.
       BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
       if (markEdgeExecutable(&BB, DefaultSuccessor))
         return true;
 
       continue;
     }
 
     if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-      if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
+      if (!SI->getNumCases() ||
+          !getValueState(SI->getCondition()).isUndefined())
         continue;
 
       // If the input to SCCP is actually switch on undef, fix the undef to
       // the first constant.
       if (isa<UndefValue>(SI->getCondition())) {
         SI->setCondition(SI->case_begin()->getCaseValue());
         markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
         return true;
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(); }))
+    std::vector<ValueLatticeElement> IVs =
+        Solver.getStructValueLatticeElementFor(V);
+    if (llvm::any_of(IVs, [](const ValueLatticeElement &LV) {
+          return !LV.isUndefined() && !isConstant(LV);
+        }))
       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)));
+      ValueLatticeElement V = IVs[i];
+      if (Constant *C = getConstant(V, ST->getElementType(i)))
+        Const = C;
+      else
+        Const = UndefValue::get(ST->getElementType(i));
+      ConstVals.push_back(Const);
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
-    const LatticeVal &IV = Solver.getLatticeValueFor(V);
-    if (IV.isOverdefined())
+    const ValueLatticeElement &IV = Solver.getValueLatticeElementFor(V);
+    if (!IV.isUndefined() && !isConstant(IV))
       return false;
 
-    Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
+    if (Constant *C = getConstant(IV, V->getType()))
+      Const = C;
+    else
+      Const = 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);
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())) {
+    if (BI->isConditional() && !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 (!Solver.isBlockExecutable(&F.front()))
       NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
                                             /*UseLLVMTrap=*/false,
                                             /*PreserveLCSSA=*/false, &DTU);
 
     // Now that all instructions in the function are constant folded,
     // use ConstantFoldTerminator to get rid of in-edges, record DT updates and
     // delete dead BBs.
     for (BasicBlock *DeadBB : BlocksToErase) {
+
       // If there are any PHI nodes in this successor, drop entries for BB now.
       for (Value::user_iterator UI = DeadBB->user_begin(),
                                 UE = DeadBB->user_end();
            UI != UE;) {
         // Grab the user and then increment the iterator early, as the user
         // will be deleted. Step past all adjacent uses from the same user.
         auto *I = dyn_cast<Instruction>(*UI);
         do { ++UI; } while (UI != UE && *UI == I);
bool llvm::runIPSCCP(
   //
   // Do this in two stages: first identify the functions we should process, then
   // actually zap their returns.  This is important because we can only do this
   // 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 DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
+  const DenseMap<Function *, ValueLatticeElement> &RV =
+      Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     Function *F = I.first;
-    if (I.second.isOverdefined() || F->getReturnType()->isVoidTy())
+    if (!(I.second.isUndefined() || isConstant(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) {
+  const DenseMap<GlobalVariable *, ValueLatticeElement> &TG =
+      Solver.getTrackedGlobals();
+  for (DenseMap<GlobalVariable *, ValueLatticeElement>::const_iterator
+           I = TG.begin(),
+           E = TG.end();
+       I != E; ++I) {
     GlobalVariable *GV = I->first;
-    assert(!I->second.isOverdefined() &&
+    if (!isConstant(I->second))
+      continue;
+    assert(isConstant(I->second) &&
            "Overdefined values should have been taken out of the map!");
     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
+}