[ValueLattice] Distinguish between constant ranges with/without undef.

[fhahn]

Summary

This patch updates ValueLattice to distinguish between ranges that are
guaranteed to not include undef and ranges that may include undef.

A constant range guaranteed to not contain undef can be used to simplify
instructions to arbitrary values. A constant range that may contain
undef can only be used to simplify to a constant. If the value can be
undef, it might take a value outside the range. For example, consider
the snipped below

define i32 @f(i32 %a, i1 %c) {

br i1 %c, label %true, label %false

true:

%a.255 = and i32 %a, 255
br label %exit

false:

br label %exit

exit:

%p = phi i32 [ %a.255, %true ], [ undef, %false ]
%f.1 = icmp eq i32 %p, 300
call void @use(i1 %f.1)
%res = and i32 %p, 255
ret i32 %res

}

In the exit block, %p would be a constant range [0, 256) including undef as
%p could be undef. We can use the range information to replace %f.1 with
false because we remove the compare, effectively forcing the use of the
constant to be != 300. We cannot replace %res with %p however, because
if %a would be undef %cond may be true but the second use might not be
< 256.

Currently LazyValueInfo uses the new behavior just when simplifying AND
instructions and does not distinguish between constant ranges with and
without undef otherwise. I think we should address the remaining issues
in LVI incrementally.

[nikic]

As we have somewhat recently defined that branch on poison is UB, I wonder whether it's possible to also make branch on undef UB. It so happens that currently all the things we define as UB for poison are also UB for undef, and branching is the only distinction. Is there a reason for that? It would be really great if we could stop thinking about undef when it comes to conditions implied by branches.

[aqjune]

Hi,
The semantics of whether br undef is nondet. choice or UB really has been a topic between me and Nuno too.
As @nikic said, we can define it as UB if which branch to take depends on an undef value.
And I think this semantics explains many more optimizations in LLVM as well (including the CVP example that removes and 255 :) ).
It seems this is not explicitly stated at LangRef; it would be great if it is mentioned to avoid further confusion.

[fhahn]

In D76931#1946483, @aqjune wrote:

Hi,
The semantics of whether br undef is nondet. choice or UB really has been a topic between me and Nuno too.
As @nikic said, we can define it as UB if which branch to take depends on an undef value.

Yes, the example in the description is just the tip of the iceberg. If branch on undef would not be UB, there are many more cases that CVP would miss I think, unless we teach it to insert freeze I guess

[efriedma]

The natural definition of undef extends to branches without any special extensions. It might make sense to redefine it to have some poison-like characteristics if that would make our life easier; I don't think any frontends would care. But I think really, you're just trading one set of problems for another. For example, if you have a switch on "x & -2", right now we can eliminate the "&". If branching on poison is UB, that requires freezing x.

Ultimately, I'm think trying to redefine undef at this point would act as a distraction for the poison work. That seems worse than whatever minor improvement we might get from redefining it.

[efriedma]

If branching on poison is UB, that requires freezing x.

Err, I meant "branching on undef".

[nikic]

In D76931#1946577, @efriedma wrote:

The natural definition of undef extends to branches without any special extensions. It might make sense to redefine it to have some poison-like characteristics if that would make our life easier; I don't think any frontends would care. But I think really, you're just trading one set of problems for another. For example, if you have a switch on "x & -2", right now we can eliminate the "&". If branching on poison is UB, that requires freezing x.

I didn't really get your example, could you maybe spell it out in more detail?

I believe we already have a simple upper bound on which optimizations we're going to lose if we make this change: MSan already considers branching on undef to be UB, and we already block optimizations that have the potential to introduce branch on undef where it did not exist before if MSan is enabled. From a quick look, there currently seem to be only two places related to branching:

https://github.com/llvm/llvm-project/blob/8896d123154c4606d11f6b6f97c33d5a455cd9ea/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L3809-L3812
https://github.com/llvm/llvm-project/blob/ee7510dc86656b739881466fddd59253d008139d/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp#L719-L727

So there seem to be just two transforms that are potentially affected (and iirc LoopUnswitch was one of the motivating cases for freezing, so probably that would go away once that is done?)

On the other hand we have any code that is inferring information from predicates. If branch on undef is not UB, I suspect that most of CVP is rendered unsound/useless. Probably parts of SCEV that reason about branch conditions as well. And probably parts of ValueTracking, e.g. we use dominating conditions for non-zero checks. Thankfully at least assumes are not affected.

Ultimately, I'm think trying to redefine undef at this point would act as a distraction for the poison work. That seems worse than whatever minor improvement we might get from redefining it.

I'm not sure why this would be a distraction from the poison work. Aligning the UB definitions for undef and poison seems like something that would make that work more straightforward, as we have less different semantics to deal with.

[efriedma]

I didn't really get your example, could you maybe spell it out in more detail?

http://volta.cs.utah.edu:8080/z/i-K25Q

Aligning the UB definitions for undef and poison seems like something that would make that work more straightforward, as we have less different semantics to deal with.

If they really align, without causing other problems, it might be okay, I guess.

[nikic]

I just realized that we already treat branch on undef as UB in isGuaranteedNotToBeUndefOrPoison(): https://github.com/llvm/llvm-project/blob/0ab5b5b8581d9f2951575f7245824e6e4fc57dec/llvm/lib/Analysis/ValueTracking.cpp#L4655-L4673

[aqjune]

In D76931#1946577, @efriedma wrote:

Ultimately, I'm think trying to redefine undef at this point would act as a distraction for the poison work. That seems worse than whatever minor improvement we might get from redefining it.

I agree, but removing undef value seems to be a pretty big work. Before that happens, making existing optimizations work consistently w.r.t undef might be an important job.

I made a LangRef change patch to make the semantics of branching on undef explicit here: https://reviews.llvm.org/D76973

[fhahn]

I've adjusted the defaults after rG05f0e598ab26: per default, markConstantRange & co assume that the constant range does not contain undef (existing behavior) and isConstantRange/getConstantRange allow constant ranges including undef (existing behavior).

mergeIn automatically marks constant ranges as containing undef based on the merged values. Clients that manually construct ValueLatticeElements are responsible for marking them as containing undef accordingly and also update isConstantRange/getConstantRange calls to exclude ranges including undef where it is not safe. One example is processAnd in CorrelatedValuePropagation, but there will be future changes needed to update all places in LVI that construct lattice elements manually. Currently it uses a helper that returns an optional constant range in multiple places so there's no easy way to recover the information if it may be undef.

I'll also update the example in the description shortly to the code below. %p will be represented as constantrange_including_undef [0, 256) and it would not be allowed to replace %res with %p. Simplifying the condition %f.1 based on range information including undef is allowed, if we replace it with a constant (and remove the original instruction that contained the use of the potentially undef value).

define i32 @f(i32 %a, i1 %c) {
  br i1 %c, label %true, label %false
true:
  %a.255 = and i32 %a, 255
  br label %exit
false:
  br label %exit
exit:
  %p = phi i32 [ %a.255, %true ], [ undef, %false ]
  %f.1 = icmp eq i32 %p, 300
  call void @use(i1 %f.1)
  %res = and i32 %p, 255
  ret i32 %res
}

The changed test cases should give a good idea of the kind of improvements this gives over the singlecr approach.

[efriedma]

LGTM

(On a side note, we can probably also simplify ResolvedUndefsIn given the new rule.)

llvm/include/llvm/Analysis/LazyValueInfo.h

public:
 
   /// Determine whether the specified value is known to be a
   /// constant at the end of the specified block.  Return null if not.
   Constant *getConstant(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
 
   /// Return the ConstantRange constraint that is known to hold for the
   /// specified value at the end of the specified block. This may only be called
   /// on integer-typed Values.
-  ConstantRange getConstantRange(Value *V, BasicBlock *BB, Instruction *CxtI = nullptr);
+  ConstantRange getConstantRange(Value *V, BasicBlock *BB,
+                                 Instruction *CxtI = nullptr,
+                                 bool UndefAllowed = true);
 
   /// Determine whether the specified value is known to be a
   /// constant on the specified edge.  Return null if not.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                               Instruction *CxtI = nullptr);
 
   /// Return the ConstantRage constraint that is known to hold for the
   /// specified value on the specified edge. This may be only be called

llvm/include/llvm/Analysis/ValueLattice.h

enum ValueLatticeElementTy {
     /// Transition to any other state allowed.
     unknown,
 
     /// This Value is an UndefValue constant or produces undef. Undefined values
     /// can be merged with constants (or single element constant ranges),
     /// assuming all uses of the result will be replaced.
     /// Transition allowed to the following states:
     ///  constant
-    ///  singlecrfromundef
+    ///  constantrange_including_undef
     ///  overdefined
     undef,
 
     /// This Value has a specific constant value.  The constant cannot be undef.
     /// (For constant integers, constantrange is used instead. Integer typed
     /// constantexprs can appear as constant.) Note that the constant state
     /// can be reached by merging undef & constant states.
     /// Transition allowed to the following states:
     ///  overdefined
     constant,
 
     /// This Value is known to not have the specified value. (For constant
     /// integers, constantrange is used instead.  As above, integer typed
     /// constantexprs can appear here.)
     /// Transition allowed to the following states:
     ///  overdefined
     notconstant,
 
     /// The Value falls within this range. (Used only for integer typed values.)
     /// Transition allowed to the following states:
     ///  constantrange (new range must be a superset of the existing range)
-    ///  singlecrfromundef (range must stay a single element range)
+    ///  constantrange_including_undef
     ///  overdefined
     constantrange,
 
-    /// This Value contains a single element constant range that was merged with
-    /// an Undef value. Merging it with other constant ranges results in
-    /// overdefined, unless they match the single element constant range.
+    /// This Value falls within this range, but also may be undef.
+    /// Merging it with other constant ranges results in
+    /// constantrange_including_undef.
     /// Transition allowed to the following states:
     ///  overdefined
-    singlecrfromundef,
+    constantrange_including_undef,
 
     /// We can not precisely model the dynamic values this value might take.
     /// No transitions are allowed after reaching overdefined.
-    overdefined
+    overdefined,
   };
 
   ValueLatticeElementTy Tag;
 
   /// The union either stores a pointer to a constant or a constant range,
   /// associated to the lattice element. We have to ensure that Range is
   /// initialized or destroyed when changing state to or from constantrange.
   union {
     Constant *ConstVal;
     ConstantRange Range;
   };
 
 public:
   // Const and Range are initialized on-demand.
   ValueLatticeElement() : Tag(unknown) {}
 
   /// Custom destructor to ensure Range is properly destroyed, when the object
   /// is deallocated.
   ~ValueLatticeElement() {
     switch (Tag) {
     case overdefined:
     case unknown:
     case undef:
     case constant:
-    case singlecrfromundef:
     case notconstant:
       break;
+    case constantrange_including_undef:
     case constantrange:
       Range.~ConstantRange();
       break;
     };
   }
 
   /// Custom copy constructor, to ensure Range gets initialized when
   /// copying a constant range lattice element.
ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
     // If we change the state of this from a valid ConstVal to another a state
     // without a valid ConstVal, zero the pointer.
     if ((isConstant() || isNotConstant()) && !Other.isConstant() &&
         !Other.isNotConstant())
       ConstVal = nullptr;
 
     switch (Other.Tag) {
     case constantrange:
-    case singlecrfromundef:
+    case constantrange_including_undef:
       if (!isConstantRange())
         new (&Range) ConstantRange(Other.Range);
       else
         Range = Other.Range;
       break;
     case constant:
     case notconstant:
       ConstVal = Other.ConstVal;
static ValueLatticeElement get(Constant *C) {
     return Res;
   }
   static ValueLatticeElement getNot(Constant *C) {
     ValueLatticeElement Res;
     assert(!isa<UndefValue>(C) && "!= undef is not supported");
     Res.markNotConstant(C);
     return Res;
   }
-  static ValueLatticeElement getRange(ConstantRange CR) {
+  static ValueLatticeElement getRange(ConstantRange CR,
+                                      bool MayIncludeUndef = false) {
     if (CR.isFullSet())
       return getOverdefined();
 
     ValueLatticeElement Res;
-    Res.markConstantRange(std::move(CR));
+    Res.markConstantRange(std::move(CR), MayIncludeUndef);
     return Res;
   }
   static ValueLatticeElement getOverdefined() {
     ValueLatticeElement Res;
     Res.markOverdefined();
     return Res;
   }
 
   bool isUndef() const { return Tag == undef; }
   bool isUnknown() const { return Tag == unknown; }
   bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
   bool isConstant() const { return Tag == constant; }
-  bool isSingleCRFromUndef() const { return Tag == singlecrfromundef; }
   bool isNotConstant() const { return Tag == notconstant; }
-  bool isConstantRange() const {
-    return Tag == constantrange || Tag == singlecrfromundef;
+  bool isConstantRangeIncludingUndef() const {
+    return Tag == constantrange_including_undef;
+  }
+  /// Returns true if this value is a constant range. Use \p UndefAllowed to
+  /// exclude non-singleton constant ranges that may also be undef. Note that
+  /// this function also returns true if the range may include undef, but only
+  /// contains a single element. In that case, it can be replaced by a constant.
+  bool isConstantRange(bool UndefAllowed = true) const {
+    return Tag == constantrange || (Tag == constantrange_including_undef &&
+                                    (UndefAllowed || Range.isSingleElement()));
   }
   bool isOverdefined() const { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return ConstVal;
   }
 
   Constant *getNotConstant() const {
     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
     return ConstVal;
   }
 
-  const ConstantRange &getConstantRange() const {
-    assert(isConstantRange() &&
+  /// Returns the constant range for this value. Use \p UndefAllowed to exclude
+  /// non-singleton constant ranges that may also be undef. Note that this
+  /// function also returns a range if the range may include undef, but only
+  /// contains a single element. In that case, it can be replaced by a constant.
+  const ConstantRange &getConstantRange(bool UndefAllowed = true) const {
+    assert(isConstantRange(UndefAllowed) &&
            "Cannot get the constant-range of a non-constant-range!");
     return Range;
   }
 
   Optional<APInt> asConstantInteger() const {
     if (isConstant() && isa<ConstantInt>(getConstant())) {
       return cast<ConstantInt>(getConstant())->getValue();
     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
bool markUndef() {
     if (isUndef())
       return false;
 
     assert(isUnknown());
     Tag = undef;
     return true;
   }
 
-  bool markConstant(Constant *V) {
+  bool markConstant(Constant *V, bool MayIncludeUndef = false) {
     if (isa<UndefValue>(V))
       return markUndef();
 
     if (isConstant()) {
       assert(getConstant() == V && "Marking constant with different value");
       return false;
     }
 
     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
-      return markConstantRange(ConstantRange(CI->getValue()));
+      return markConstantRange(ConstantRange(CI->getValue()), MayIncludeUndef);
 
     assert(isUnknown() || isUndef());
     Tag = constant;
     ConstVal = V;
     return true;
   }
 
   bool markNotConstant(Constant *V) {
bool markNotConstant(Constant *V) {
     assert(isUnknown());
     Tag = notconstant;
     ConstVal = V;
     return true;
   }
 
   /// Mark the object as constant range with \p NewR. If the object is already a
   /// constant range, nothing changes if the existing range is equal to \p
-  /// NewR. Otherwise \p NewR must be a superset of the existing range or the
-  /// object must be undef.
-  bool markConstantRange(ConstantRange NewR) {
-    if (isConstantRange()) {
-      if (getConstantRange() == NewR)
-        return false;
-
-      assert(!isSingleCRFromUndef());
+  /// NewR and the tag. Otherwise \p NewR must be a superset of the existing
+  /// range or the object must be undef. The tag is set to
+  /// constant_range_including_undef if either the existing value or the new
+  /// range may include undef.
+  bool markConstantRange(ConstantRange NewR, bool MayIncludeUndef = false) {
+    if (NewR.isFullSet())
+      return markOverdefined();
 
+    ValueLatticeElementTy OldTag = Tag;
+    ValueLatticeElementTy NewTag =
+        (isUndef() || isConstantRangeIncludingUndef() || MayIncludeUndef)
+            ? constantrange_including_undef
+            : constantrange;
+    if (isConstantRange()) {
       if (NewR.isEmptySet())
         return markOverdefined();
 
+      Tag = NewTag;
+      if (getConstantRange() == NewR)
+        return Tag != OldTag;
+
       assert(NewR.contains(getConstantRange()) &&
              "Existing range must be a subset of NewR");
       Range = std::move(NewR);
       return true;
     }
 
-    assert(isUnknown() || (isUndef() && NewR.isSingleElement()));
+    assert(isUnknown() || isUndef());
     if (NewR.isEmptySet())
       return markOverdefined();
 
-    Tag = isUnknown() ? constantrange : singlecrfromundef;
+    Tag = NewTag;
     new (&Range) ConstantRange(std::move(NewR));
     return true;
   }
 
   /// Updates this object to approximate both this object and RHS. Returns
   /// true if this object has been changed.
   bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
     if (RHS.isUnknown() || isOverdefined())
       return false;
     if (RHS.isOverdefined()) {
       markOverdefined();
       return true;
     }
 
     if (isUndef()) {
       assert(!RHS.isUnknown());
       if (RHS.isUndef())
         return false;
       if (RHS.isConstant())
-        return markConstant(RHS.getConstant());
-      if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement())
-        return markConstantRange(RHS.getConstantRange());
+        return markConstant(RHS.getConstant(), /*MayIncludeUndef=*/true);
+      if (RHS.isConstantRange())
+        return markConstantRange(RHS.getConstantRange(true),
+                                 /*MayIncludeUndef=*/true);
       return markOverdefined();
     }
 
     if (isUnknown()) {
       assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
       *this = RHS;
       return true;
     }
bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
 
     if (isNotConstant()) {
       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
         return false;
       markOverdefined();
       return true;
     }
 
+    auto OldTag = Tag;
     assert(isConstantRange() && "New ValueLattice type?");
-    if (RHS.isUndef() && getConstantRange().isSingleElement())
-      return false;
+    if (RHS.isUndef()) {
+      Tag = constantrange_including_undef;
+      return OldTag != Tag;
+    }
 
     if (!RHS.isConstantRange()) {
       // We can get here if we've encountered a constantexpr of integer type
       // and merge it with a constantrange.
       markOverdefined();
       return true;
     }
 
     ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
-
-    if (isSingleCRFromUndef() || RHS.isSingleCRFromUndef()) {
-      if (NewR.isSingleElement()) {
-        assert(getConstantRange() == NewR);
-        return false;
-      }
-      markOverdefined();
-      return true;
-    }
-    if (NewR.isFullSet())
-      return markOverdefined();
-    else if (NewR == getConstantRange())
-      return false;
-    else
-      return markConstantRange(std::move(NewR));
+    return markConstantRange(
+        std::move(NewR),
+        /*MayIncludeUndef=*/RHS.isConstantRangeIncludingUndef());
   }
 
   // Compares this symbolic value with Other using Pred and returns either
   /// true, false or undef constants, or nullptr if the comparison cannot be
   /// evaluated.
   Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
                        const ValueLatticeElement &Other) const {
     if (isUnknownOrUndef() || Other.isUnknownOrUndef())

llvm/lib/Analysis/LazyValueInfo.cpp

static ValueLatticeElement intersect(const ValueLatticeElement &A,
   // Could be either constant range or not constant here.
   if (!A.isConstantRange() || !B.isConstantRange()) {
     // TODO: Arbitrary choice, could be improved
     return A;
   }
 
   // Intersect two constant ranges
   ConstantRange Range =
       A.getConstantRange().intersectWith(B.getConstantRange());
   // Note: An empty range is implicitly converted to overdefined internally.
   // TODO: We could instead use Undefined here since we've proven a conflict
   // and thus know this path must be unreachable.
-  return ValueLatticeElement::getRange(std::move(Range));
+  return ValueLatticeElement::getRange(
+      std::move(Range), /*MayIncludeUndef=*/A.isConstantRangeIncludingUndef() |
+                            B.isConstantRangeIncludingUndef());
 }
 
 //===----------------------------------------------------------------------===//
 //                          LazyValueInfoCache Decl
 //===----------------------------------------------------------------------===//
 
 namespace {
   /// A callback value handle updates the cache when values are erased.
if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
         case SPF_UMIN:                   /// Unsigned minimum
           return TrueCR.umin(FalseCR);
         case SPF_SMAX:                   /// Signed maximum
           return TrueCR.smax(FalseCR);
         case SPF_UMAX:                   /// Unsigned maximum
           return TrueCR.umax(FalseCR);
         };
       }();
-      BBLV = ValueLatticeElement::getRange(ResultCR);
+      BBLV = ValueLatticeElement::getRange(
+          ResultCR, TrueVal.isConstantRangeIncludingUndef() |
+                        FalseVal.isConstantRangeIncludingUndef());
       return true;
     }
 
     if (SPR.Flavor == SPF_ABS) {
       if (LHS == SI->getTrueValue()) {
-        BBLV = ValueLatticeElement::getRange(TrueCR.abs());
+        BBLV = ValueLatticeElement::getRange(
+            TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
         return true;
       }
       if (LHS == SI->getFalseValue()) {
-        BBLV = ValueLatticeElement::getRange(FalseCR.abs());
+        BBLV = ValueLatticeElement::getRange(
+            FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
         return true;
       }
     }
 
     if (SPR.Flavor == SPF_NABS) {
       ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth()));
       if (LHS == SI->getTrueValue()) {
-        BBLV = ValueLatticeElement::getRange(Zero.sub(TrueCR.abs()));
+        BBLV = ValueLatticeElement::getRange(
+            Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
         return true;
       }
       if (LHS == SI->getFalseValue()) {
-        BBLV = ValueLatticeElement::getRange(Zero.sub(FalseCR.abs()));
+        BBLV = ValueLatticeElement::getRange(
+            Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
         return true;
       }
     }
   }
 
   // Can we constrain the facts about the true and false values by using the
   // condition itself?  This shows up with idioms like e.g. select(a > 5, a, 5).
   // TODO: We could potentially refine an overdefined true value above.
if (Result.isConstantRange()) {
     const ConstantRange &CR = Result.getConstantRange();
     if (const APInt *SingleVal = CR.getSingleElement())
       return ConstantInt::get(V->getContext(), *SingleVal);
   }
   return nullptr;
 }
 
 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
-                                              Instruction *CxtI) {
+                                              Instruction *CxtI,
+                                              bool UndefAllowed) {
   assert(V->getType()->isIntegerTy());
   unsigned Width = V->getType()->getIntegerBitWidth();
   const DataLayout &DL = BB->getModule()->getDataLayout();
   ValueLatticeElement Result =
       getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
   if (Result.isUnknown())
     return ConstantRange::getEmpty(Width);
-  if (Result.isConstantRange())
-    return Result.getConstantRange();
+  if (Result.isConstantRange(UndefAllowed))
+    return Result.getConstantRange(UndefAllowed);
   // We represent ConstantInt constants as constant ranges but other kinds
   // of integer constants, i.e. ConstantExpr will be tagged as constants
   assert(!(Result.isConstant() && isa<ConstantInt>(Result.getConstant())) &&
          "ConstantInt value must be represented as constantrange");
   return ConstantRange::getFull(Width);
 }
 
 /// Determine whether the specified value is known to be a

llvm/lib/Analysis/ValueLattice.cpp

raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) {
   if (Val.isUndef())
     return OS << "undef";
   if (Val.isOverdefined())
     return OS << "overdefined";
 
   if (Val.isNotConstant())
     return OS << "notconstant<" << *Val.getNotConstant() << ">";
 
-  if (Val.isSingleCRFromUndef())
-    return OS << "constantrange (from undef)<"
-              << Val.getConstantRange().getLower() << ", "
-              << Val.getConstantRange().getUpper() << ">";
+  if (Val.isConstantRangeIncludingUndef())
+    return OS << "constantrange incl. undef <"
+              << Val.getConstantRange(true).getLower() << ", "
+              << Val.getConstantRange(true).getUpper() << ">";
 
   if (Val.isConstantRange())
     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
 } // end namespace llvm

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool processAnd(BinaryOperator *BinOp, LazyValueInfo *LVI) {
   // Pattern match (and lhs, C) where C includes a superset of bits which might
   // be set in lhs.  This is a common truncation idiom created by instcombine.
   BasicBlock *BB = BinOp->getParent();
   Value *LHS = BinOp->getOperand(0);
   ConstantInt *RHS = dyn_cast<ConstantInt>(BinOp->getOperand(1));
   if (!RHS || !RHS->getValue().isMask())
     return false;
 
-  ConstantRange LRange = LVI->getConstantRange(LHS, BB, BinOp);
+  // We can only replace the AND with LHS based on range info if the range does
+  // not include undef.
+  ConstantRange LRange =
+      LVI->getConstantRange(LHS, BB, BinOp, /*UndefAllowed=*/false);
   if (!LRange.getUnsignedMax().ule(RHS->getValue()))
     return false;
 
   BinOp->replaceAllUsesWith(LHS);
   BinOp->eraseFromParent();
   NumAnd++;
   return true;
 }

llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll

 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
 ; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   br label %bb3
 

 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   br label %bb3
 
 bb2:

 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB2]] ], [ undef, [[BB3]] ]
 ; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   %r = and i64 %a, 255
   br label %bb4

 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ 10, [[BB2]] ], [ [[R]], [[BB3]] ]
 ; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   br label %bb4
 

 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ]
 ; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i64 [[P]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i64 [[RES]]
 ;
 entry:
   br i1 %c1, label %bb1, label %bb2
 
 bb1:
   %r = and i64 %a, 255
   br label %bb4

llvm/test/Transforms/SCCP/phi-cycle.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -ipsccp -S %s | FileCheck %s
+
+declare i1 @cond()
+
+define i32 @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[C_1:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP]], label [[LATCH_2:%.*]]
+; CHECK:       latch.2:
+; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %loop
+
+loop:
+  %p = phi i32 [ undef, %entry ], [ 0, %latch.2 ], [ %p, %loop]
+  %c.1 = call i1 @cond()
+  br i1 %c.1, label %loop, label %latch.2
+
+latch.2:
+  %c.2 = call i1 @cond()
+  br i1 %c.2, label %loop, label %exit
+
+exit:
+  ret i32 %p
+}

llvm/test/Transforms/SCCP/range-and-ip.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -ipsccp %s | FileCheck %s
 
 ; Make sure IPSCCP does not assume %r < 256 for @f1. Undef is passed at a call
 ; site, which won't be eliminated.
 
 define i1 @constant_and_undef(i64 %a) {
 ; CHECK-LABEL: @constant_and_undef(
 ; CHECK-NEXT:    [[C_1:%.*]] = call i1 @f1(i64 undef)
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = call i1 @f1(i64 10)
 ; CHECK-NEXT:    br label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[RANGE:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    [[C_3:%.*]] = call i1 @f1(i64 [[RANGE]])
-; CHECK-NEXT:    [[R_1:%.*]] = and i1 [[C_1]], [[C_2]]
-; CHECK-NEXT:    [[R_2:%.*]] = and i1 [[R_1]], [[C_3]]
-; CHECK-NEXT:    ret i1 [[R_2]]
+; CHECK-NEXT:    ret i1 true
 ;
   %c.1 = call i1 @f1(i64 undef)
   br label %bb1
 
 bb1:
   %c.2 = call i1 @f1(i64 10)
   br label %bb2
 
 bb2:
   %range = and i64 %a, 255
   %c.3 = call i1 @f1(i64 %range)
   %r.1 = and i1 %c.1, %c.2
   %r.2 = and i1 %r.1, %c.3
   ret i1 %r.2
 }
 
 declare void @sideeffect(i1, i64 %a)
 
 define internal i1 @f1(i64 %r) {
 ; CHECK-LABEL: define {{.*}} @f1(
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[R:%.*]], 256
-; CHECK-NEXT:    call void @sideeffect(i1 [[C]], i64 [[R]])
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    call void @sideeffect(i1 true, i64 [[R:%.*]])
+; CHECK-NEXT:    ret i1 undef
 ;
   %c = icmp ult i64 %r, 256
   call void @sideeffect(i1 %c, i64 %r)
   ret i1 %c
 }

llvm/test/Transforms/SCCP/range-and.ll

bb2:
   br label %bb3
 
 bb3:
   %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
   %res = and i64 %p, 255
   ret i64 %res
 }
 
-define i1 @constant_range_and_255_100(i1 %cond, i64 %a) {
+define i64 @constant_range_and_255_100(i1 %cond, i64 %a) {
 ; CHECK-LABEL: @constant_range_and_255_100(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[R_1:%.*]] = and i64 [[A:%.*]], 100
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[R_2:%.*]] = and i64 [[A]], 255
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R_1]], [[BB1]] ], [ [[R_2]], [[BB2]] ]
 ; CHECK-NEXT:    [[P_AND:%.*]] = and i64 [[P]], 512
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    ret i64 [[P_AND]]
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   %r.1 = and i64 %a, 100
   br label %bb3
 
 bb2:
   %r.2 = and i64 %a, 255
   br label %bb3
 
 bb3:
   %p = phi i64 [ %r.1, %bb1 ], [ %r.2, %bb2 ]
   %p.and = and i64 %p, 512
   %c = icmp ult i64 %p.and, 256
-  ret i1 %c
+  call void @use(i1 %c)
+  ret i64 %p.and
 }
 
 
 define i64 @constant_range_and_undef2(i1 %c1, i1 %c2, i64 %a) {
 ; CHECK-LABEL: @constant_range_and_undef2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:

 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ]
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   br label %bb3
 
 bb2:

 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ]
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i64 [[P]], 256
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 true
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2
 
 bb1:
   %r = and i64 %a, 255
   br label %bb3