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

[fhahn]

Summary

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

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

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

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

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

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

attributes #1 = { noinline }

[sanjoy]

lib/Transforms/Scalar/SCCP.cpp

105

Use llvm::ConstantRange here.

1867

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

But let's see what other folks think.

[• dberlin]

Thanks for working on this!

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

[efriedma]

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

Should IPSCCP itself try to fold operations based on ranges?

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

lib/Transforms/Scalar/SCCP.cpp

143

cast<>, not dyn_cast<>

1643

?

[• dberlin]

In D36656#841247, @efriedma wrote:

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

If we have such metadata, yes

Should IPSCCP itself try to fold operations based on ranges?

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

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

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

[efriedma]

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

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

[mssimpso]

In D36656#841247, @efriedma wrote:

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

Should IPSCCP itself try to fold operations based on ranges?

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

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

[davide]

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

[fhahn]

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

In D36656#843034, @davide wrote:

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

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

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

[fhahn]

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

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

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

[fhahn]

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

[fhahn]

ping, any thoughts?

[davide]

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

include/llvm/Analysis/ValueLattice.h

123–125 ↗

(On Diff #112577)

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

lib/Transforms/Scalar/SCCP.cpp

1636

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

[fhahn]

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

[fhahn]

include/llvm/Analysis/ValueLattice.h

123–125 ↗

(On Diff #112577)

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

lib/Transforms/Scalar/SCCP.cpp

1636

Yes and it makes the code quite a bit simpler too

[fhahn]

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

[• dberlin]

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

[davide]

I think the same.

[fhahn]

Rebased after D37591 was committed

[fhahn]

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

[• dberlin]

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

90

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

[fhahn]

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

90

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

What do you think?

[• dberlin]

Sounds reasonable to start with.

[davide]

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

lib/Transforms/Scalar/SCCP.cpp

31

Unsorted.

1611

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

1617

unformatted.

1658

can you please clang format?

[fhahn]

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

[fhahn]

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

[fhahn]

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

[• dberlin]

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

lib/Transforms/Scalar/SCCP.cpp

329

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

333

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

336

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

471

Ditto above on how to do this without repeated lookups

472

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

1609

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

[fhahn]

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

lib/Transforms/Scalar/SCCP.cpp

333

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

472

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

[fhahn]

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

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

lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"

 #define DEBUG_TYPE "sccp"
 
 STATISTIC(NumInstRemoved, "Number of instructions removed");
 STATISTIC(NumDeadBlocks , "Number of basic blocks unreachable");
 
 STATISTIC(IPNumInstRemoved, "Number of instructions removed by IPSCCP");
 STATISTIC(IPNumArgsElimed ,"Number of arguments constant propagated by IPSCCP");
 STATISTIC(IPNumGlobalConst, "Number of globals found to be constant by IPSCCP");
+STATISTIC(IPNumRangeInfoUsed, "Number of times constant range info was used by"
+                              "IPSCCP");
 
 namespace {
 
 /// LatticeVal class - This class represents the different lattice values that
 /// an LLVM value may occupy.  It is a simple class with value semantics.
 ///
 class LatticeVal {
   enum LatticeValueTy {
enum LatticeValueTy {
     /// it has a value.
     overdefined
   };
 
   /// Val: This stores the current lattice value along with the Constant* for
   /// the constant if this is a 'constant' or 'forcedconstant' value.
   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
 
   LatticeValueTy getLatticeValue() const {
     return Val.getInt();
   }
 
 public:
   LatticeVal() : Val(nullptr, unknown) {}
 
   bool isUnknown() const { return getLatticeValue() == unknown; }
 
public:
   bool markConstant(Constant *V) {
     if (getLatticeValue() == constant) { // Constant but not forcedconstant.
       assert(getConstant() == V && "Marking constant with different value");
       return false;
     }
 
     if (isUnknown()) {
       Val.setInt(constant);
       assert(V && "Marking constant with NULL");
       Val.setPointer(V);
     } else {
       assert(getLatticeValue() == forcedconstant &&
              "Cannot move from overdefined to constant!");
       // Stay at forcedconstant if the constant is the same.
       if (V == getConstant()) return false;
 
       // Otherwise, we go to overdefined.  Assumptions made based on the
BlockAddress *getBlockAddress() const {
     return nullptr;
   }
 
   void markForcedConstant(Constant *V) {
     assert(isUnknown() && "Can't force a defined value!");
     Val.setInt(forcedconstant);
     Val.setPointer(V);
   }
+
+  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;
   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;
 
   /// 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
std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     return StructValues;
   }
 
-  LatticeVal getLatticeValueFor(Value *V) const {
+  ValueLatticeElement getLatticeValueFor(Value *V) {
+    std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
+        PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
+    ValueLatticeElement &LV = PI.first->second;
+    if (PI.second) {
       DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
-    assert(I != ValueState.end() && "V is not in valuemap!");
-    return I->second;
+      assert(I != ValueState.end() &&
+             "V not found in ValueState nor Paramstate map!");
+      LV = I->second.toValueLattice();
+    }
+
+    return LV;
   }
 
   /// getTrackedRetVals - Get the inferred return value map.
   const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
     return TrackedRetVals;
   }
 
   /// getTrackedGlobals - Get and return the set of inferred initializers for
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 #");
 
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
       }
 
       if (auto *STy = dyn_cast<StructType>(AI->getType())) {
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           LatticeVal CallArg = getStructValueState(*CAI, i);
           mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg);
         }
       } else {
+        // Most other parts of the Solver still only use the simpler value
+        // lattice, so we propagate changes for parameters to both lattices.
+        getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL);
         mergeInValue(&*AI, getValueState(*CAI));
       }
     }
   }
 
   // If this is a single/zero retval case, see if we're tracking the function.
   if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
     if (!MRVFunctionsTracked.count(F))
if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       markForcedConstant(SI->getCondition(), SI->case_begin()->getCaseValue());
       return true;
     }
   }
 
   return false;
 }
 
+static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) {
+  bool Changed = false;
+
+  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+  if (IV.isOverdefined())
+    return false;
+
+  // Currently we only use range information for integer values.
+  if (!(V->getType()->isIntegerTy() && IV.isConstantRange()))
+    return false;
+
+  for (auto UI = V->uses().begin(), E = V->uses().end(); UI != E;) {
+    const Use &U = *UI++;
+    auto *Icmp = dyn_cast<ICmpInst>(U.getUser());
+    if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent()))
+      continue;
+
+    auto A = Solver.getLatticeValueFor(Icmp->getOperand(0));
+    auto B = Solver.getLatticeValueFor(Icmp->getOperand(1));
+    Constant *C = nullptr;
+    if (A.satisfiesPredicate(Icmp->getPredicate(), B))
+      C = ConstantInt::getTrue(Icmp->getType());
+    else if (A.satisfiesPredicate(Icmp->getInversePredicate(), B))
+      C = ConstantInt::getFalse(Icmp->getType());
+
+    if (C) {
+      Icmp->replaceAllUsesWith(C);
+      DEBUG(dbgs() << "Replacing " << *Icmp << " with " << *C
+                   << ", because of range information " << A << " " << B
+                   << "\n");
+      Icmp->eraseFromParent();
+      Changed = true;
+    }
+  }
+  return Changed;
+}
+
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
     std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
     if (llvm::any_of(IVs,
                      [](const LatticeVal &LV) { return LV.isOverdefined(); }))
       return false;
     std::vector<Constant *> ConstVals;
     auto *ST = dyn_cast<StructType>(V->getType());
     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
       LatticeVal V = IVs[i];
       ConstVals.push_back(V.isConstant()
                               ? V.getConstant()
                               : UndefValue::get(ST->getElementType(i)));
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
-    LatticeVal IV = Solver.getLatticeValueFor(V);
+    const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
     if (IV.isOverdefined())
       return false;
-    Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
+
+    if (IV.isConstantRange()) {
+      if (IV.getConstantRange().isSingleElement())
+        Const =
+            ConstantInt::get(V->getType(), IV.asConstantInteger().getValue());
+      else
+        return false;
+    } else
+      Const =
+          IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType());
   }
   assert(Const && "Constant is nullptr here!");
   DEBUG(dbgs() << "  Constant: " << *Const << " = " << *V << '\n');
 
   // Replaces all of the uses of a variable with uses of the constant.
   V->replaceAllUsesWith(Const);
   return true;
 }
for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
       Instruction *Inst = &*BI++;
       if (Inst->getType()->isVoidTy() || isa<TerminatorInst>(Inst))
         continue;
 
       if (tryToReplaceWithConstant(Solver, Inst)) {
         if (isInstructionTriviallyDead(Inst))
           Inst->eraseFromParent();
         // Hey, we just changed something!
         MadeChanges = true;
         ++NumInstRemoved;
       }
     }
   }
 
   return MadeChanges;
 }
 
static bool runIPSCCP(Module &M, const DataLayout &DL,
   SmallVector<BasicBlock*, 512> BlocksToErase;
 
   for (Function &F : M) {
     if (F.isDeclaration())
       continue;
 
     if (Solver.isBlockExecutable(&F.front()))
       for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;
-           ++AI)
+           ++AI) {
         if (!AI->use_empty() && tryToReplaceWithConstant(Solver, &*AI))
           ++IPNumArgsElimed;
 
+        if (!AI->use_empty() && tryToReplaceWithConstantRange(Solver, &*AI))
+          ++IPNumRangeInfoUsed;
+      }
+
     for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
       if (!Solver.isBlockExecutable(&*BB)) {
         DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
 
         ++NumDeadBlocks;
         NumInstRemoved +=
             changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false);
 

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

+; RUN: opt < %s -ipsccp -S | FileCheck %s
+
+; Constant range for %a is [1, 48) and for %b is [301, 1000)
+; CHECK-LABEL: f1
+; CHECK-NOT: icmp
+; CHECK: %a.1 = select i1 false, i32 1, i32 2
+; CHECK: %b.1 = select i1 true, i32 1, i32 2
+; CHECK: %a.2 = select i1 false, i32 1, i32 2
+; CHECK: %b.2 = select i1 true, i32 1, i32 2
+define internal i32 @f1(i32 %a, i32 %b) {
+entry:
+  %cmp.a = icmp sgt i32 %a, 300
+  %cmp.b = icmp sgt i32 %b, 300
+  %cmp.a2 = icmp ugt i32 %a, 300
+  %cmp.b2 = icmp ugt i32 %b, 300
+
+  %a.1 = select i1 %cmp.a, i32 1, i32 2
+  %b.1 = select i1 %cmp.b, i32 1, i32 2
+  %a.2 = select i1 %cmp.a2, i32 1, i32 2
+  %b.2 = select i1 %cmp.b2, i32 1, i32 2
+  %res1 = add i32 %a.1, %b.1
+  %res2 = add i32 %a.2, %b.2
+  %res3 = add i32 %res1, %res2
+  ret i32 %res3
+}
+
+; Constant range for %x is [47, 302)
+; CHECK-LABEL: f2
+; CHECK: %cmp = icmp sgt i32 %x, 300
+; CHECK: %res1 = select i1 %cmp, i32 1, i32 2
+; CHECK-NEXT: %res2 = select i1 true, i32 3, i32 4
+; CHECK-NEXT: %res3 = select i1 true, i32 5, i32 6
+; CHECK-NEXT: %res4 = select i1 %cmp4, i32 3, i32 4
+; CHECK-NEXT: %res5 = select i1 true, i32 5, i32 6
+define internal i32 @f2(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  %cmp2 = icmp ne i32 %x, 10
+  %cmp3 = icmp sge i32 %x, 47
+  %cmp4 = icmp ugt i32 %x, 300
+  %cmp5 = icmp uge i32 %x, 47
+  %res1 = select i1 %cmp, i32 1, i32 2
+  %res2 = select i1 %cmp2, i32 3, i32 4
+  %res3 = select i1 %cmp3, i32 5, i32 6
+  %res4 = select i1 %cmp4, i32 3, i32 4
+  %res5 = select i1 %cmp5, i32 5, i32 6
+
+  %res6 = add i32 %res1, %res2
+  %res7 = add i32 %res3, %res4
+  %res = add i32 %res6, %res5
+  ret i32 %res
+}
+
+define i32 @caller1() {
+entry:
+  %call1 = tail call i32 @f1(i32 1, i32 301)
+  %call2 = tail call i32 @f1(i32 47, i32 999)
+  %call3 = tail call i32 @f2(i32 47)
+  %call4 = tail call i32 @f2(i32 301)
+  %res = add nsw i32 %call1, %call2
+  %res.1 = add nsw i32 %res, %call3
+  %res.2 = add nsw i32 %res.1, %call4
+  ret i32 %res.2
+}
+
+; x is overdefined, because constant ranges are only used for parameter
+; values.
+; CHECK-LABEL: f3
+; CHECK: %cmp = icmp sgt i32 %x, 300
+; CHECK: %res = select i1 %cmp, i32 1, i32 2
+; CHECK: ret i32 %res
+define internal i32 @f3(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  %res = select i1 %cmp, i32 1, i32 2
+  ret i32 %res
+}
+
+; The phi node could be converted in a ConstantRange.
+define i32 @caller2(i1 %cmp) {
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %res = phi i32 [ 0, %entry], [ 1, %if.true ]
+  %call1 = tail call i32 @f3(i32 %res)
+  ret i32 %call1
+}
+
+; CHECK-LABEL: f4
+; CHECK: %cmp = icmp sgt i32 %x, 300
+; CHECK: %res = select i1 %cmp, i32 1, i32 2
+; CHECK: ret i32 %res
+define internal i32 @f4(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  %res = select i1 %cmp, i32 1, i32 2
+  ret i32 %res
+}
+
+; ICmp could introduce bounds on ConstantRanges.
+define i32 @caller3(i32 %x) {
+entry:
+  %cmp = icmp sgt i32 %x, 300
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  %x.1 = tail call i32 @f4(i32 %x)
+  br label %end
+
+end:
+  %res = phi i32 [ 0, %entry], [ %x.1, %if.true ]
+  ret i32 %res
+}
+
+; Check to make sure we do not attempt to access lattice values in unreachable
+; blocks.
+define i32 @test_unreachable() {
+entry:
+  call i1 @test_unreachable_callee(i32 1)
+  call i1 @test_unreachable_callee(i32 2)
+  ret i32 1
+}
+
+define internal i1 @test_unreachable_callee(i32 %a) {
+entry:
+  ret i1 true
+
+unreachablebb:
+  %cmp = icmp eq i32 undef, %a
+  unreachable
+}