Backport 4878aa36d4a [ValueLattice] Add new state for undef constants.

[fhahn]

Summary

NOTE: I mostly put it on Phabricator to make it easy for other people to fetch & check if that fixes a bug.

This patch backports 4878aa36d4a and required earlier patches onto
the release/10.x branch.

It includes the following patches:

aa5ebfdf205de6d599c1fed3161da3b63b6f0bef [ValueLattice] Make mark* functions public, return if value changed.

c1943b42c5b7feff5d0e0c1358d02889e2be165f [ValueLattice] Update markConstantRange to return false equal ranges.

e30c257811f62fea21704caa961c61e4559de202 [CVP,SCCP] Precommit test for D75055.

4878aa36d4aa27df644430139fab2734fde4a000 [ValueLattice] Add new state for undef constants.

All patches except the last one apply cleanly. For the last one, the
changes to SCCP.cpp were stripped, because SCCP does not yet use
ValueLattice on release/10.x. Otherwise we would have to pull in more
additional changes.

[tstellar]

llvm/include/llvm/Analysis/ValueLattice.h

37

I'm fairly certain this is an API and ABI breaking change, I'm fixing up the abi check job on GitHub actions to try to confirm this.

142

Removing this is an ABI breaking change, so the patch would need to be modified to keep this in.

[fhahn]

Move new undef value to bottom, bring back isUndefined.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

37

I moved the new value to the end. Maybe that helps for existing clients?

142

I kept isUndefined, which should just be isUnknownOrUndef.

[fhahn]

Use isUnknownOrUndef for isUndefined().

[fhahn]

@tstellar merged this onto the 10.0.1 branch using a Github PR

llvm/include/llvm/Analysis/ValueLattice.h

 
 namespace llvm {
 class ValueLatticeElement {
   enum ValueLatticeElementTy {
     /// This Value has no known value yet.  As a result, this implies the
     /// producing instruction is dead.  Caution: We use this as the starting
     /// state in our local meet rules.  In this usage, it's taken to mean
     /// "nothing known yet".
-    undefined,
+    unknown,
 
     /// This Value has a specific constant value.  (For constant integers,
     /// constantrange is used instead.  Integer typed constantexprs can appear
     /// as constant.)
     constant,
 
     /// This Value is known to not have the specified value.  (For constant
     /// integers, constantrange is used instead.  As above, integer typed
     /// constantexprs can appear here.)
     notconstant,
 
     /// The Value falls within this range. (Used only for integer typed values.)
     constantrange,
 
     /// We can not precisely model the dynamic values this value might take.
-    overdefined
+    overdefined,
+
+    /// 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.
+    undef
   };
 
   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(undefined) {}
+  ValueLatticeElement() : Tag(unknown) {}
 
   /// Custom destructor to ensure Range is properly destroyed, when the object
   /// is deallocated.
   ~ValueLatticeElement() {
     switch (Tag) {
     case overdefined:
-    case undefined:
+    case unknown:
+    case undef:
     case constant:
     case notconstant:
       break;
     case constantrange:
       Range.~ConstantRange();
       break;
     };
   }
 
   /// Custom copy constructor, to ensure Range gets initialized when
   /// copying a constant range lattice element.
-  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
+  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) {
     *this = Other;
   }
 
   /// Custom assignment operator, to ensure Range gets initialized when
   /// assigning a constant range lattice element.
   ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
     // If we change the state of this from constant range to non constant range,
     // destroy Range.
case constantrange:
       else
         Range = Other.Range;
       break;
     case constant:
     case notconstant:
       ConstVal = Other.ConstVal;
       break;
     case overdefined:
-    case undefined:
+    case unknown:
+    case undef:
       break;
     }
     Tag = Other.Tag;
     return *this;
   }
 
   static ValueLatticeElement get(Constant *C) {
     ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
+    if (isa<UndefValue>(C))
+      Res.markUndef();
+    else
       Res.markConstant(C);
     return Res;
   }
   static ValueLatticeElement getNot(Constant *C) {
     ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
-      Res.markNotConstant(C);
+    assert(!isa<UndefValue>(C) && "!= undef is not supported");
     return Res;
   }
   static ValueLatticeElement getRange(ConstantRange CR) {
     ValueLatticeElement Res;
     Res.markConstantRange(std::move(CR));
     return Res;
   }
   static ValueLatticeElement getOverdefined() {
     ValueLatticeElement Res;
     Res.markOverdefined();
     return Res;
   }
 
-  bool isUndefined() const { return Tag == undefined; }
+  bool isUndef() const { return Tag == undef; }
+  bool isUnknown() const { return Tag == unknown; }
+  bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; }
+  bool isUndefined() const { return isUnknownOrUndef(); }
   bool isConstant() const { return Tag == constant; }
   bool isNotConstant() const { return Tag == notconstant; }
   bool isConstantRange() const { return Tag == constantrange; }
   bool isOverdefined() const { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return ConstVal;
Optional<APInt> asConstantInteger() const {
     if (isConstant() && isa<ConstantInt>(getConstant())) {
       return cast<ConstantInt>(getConstant())->getValue();
     } else if (isConstantRange() && getConstantRange().isSingleElement()) {
       return *getConstantRange().getSingleElement();
     }
     return None;
   }
 
-private:
-  void markOverdefined() {
+  bool markOverdefined() {
     if (isOverdefined())
-      return;
+      return false;
     if (isConstant() || isNotConstant())
       ConstVal = nullptr;
     if (isConstantRange())
       Range.~ConstantRange();
     Tag = overdefined;
+    return true;
   }
 
-  void markConstant(Constant *V) {
-    assert(V && "Marking constant with NULL");
-    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue()));
-      return;
-    }
+  bool markUndef() {
+    if (isUndef())
+      return false;
+
+    assert(isUnknown());
+    Tag = undef;
+    return true;
+
+  bool markConstant(Constant *V) {
     if (isa<UndefValue>(V))
-      return;
+      return markUndef();
 
-    assert((!isConstant() || getConstant() == V) &&
-           "Marking constant with different value");
-    assert(isUndefined());
+    if (isConstant()) {
+      assert(getConstant() == V && "Marking constant with different value");
+      return false;
+    }
+
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+      return markConstantRange(ConstantRange(CI->getValue()));
+
+    assert(isUnknown() || isUndef());
     Tag = constant;
     ConstVal = V;
+    return true;
   }
 
-  void markNotConstant(Constant *V) {
+  bool markNotConstant(Constant *V) {
     assert(V && "Marking constant with NULL");
-    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
-      return;
-    }
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
+      return markConstantRange(
+          ConstantRange(CI->getValue() + 1, CI->getValue()));
+
     if (isa<UndefValue>(V))
-      return;
+      return false;
 
-    assert((!isConstant() || getConstant() != V) &&
-           "Marking constant !constant with same value");
-    assert((!isNotConstant() || getNotConstant() == V) &&
-           "Marking !constant with different value");
-    assert(isUndefined() || isConstant());
+    if (isNotConstant()) {
+      assert(getNotConstant() == V && "Marking !constant with different value");
+      return false;
+    }
+
+    assert(isUnknown());
     Tag = notconstant;
     ConstVal = V;
+    return true;
   }
 
-  void markConstantRange(ConstantRange NewR) {
+  /// 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;
+
       if (NewR.isEmptySet())
-        markOverdefined();
-      else {
-        Range = std::move(NewR);
-      }
-      return;
+        return markOverdefined();
+
+      assert(NewR.contains(getConstantRange()) &&
+             "Existing range must be a subset of NewR");
+      return true;
     }
 
-    assert(isUndefined());
+    assert(isUnknown() || isUndef());
     if (NewR.isEmptySet())
-      markOverdefined();
-    else {
-      Tag = constantrange;
-      new (&Range) ConstantRange(std::move(NewR));
-    }
+      return markOverdefined();
+
+    return true;
   }
 
-public:
   /// 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.isUndefined() || isOverdefined())
+    if (RHS.isUnknown() || isOverdefined())
       return false;
     if (RHS.isOverdefined()) {
       markOverdefined();
       return true;
     }
 
-    if (isUndefined()) {
+    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 markOverdefined();
+    }
+
+    if (isUnknown()) {
+      assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier");
       *this = RHS;
-      return !RHS.isUndefined();
+      return true;
     }
 
     if (isConstant()) {
       if (RHS.isConstant() && getConstant() == RHS.getConstant())
         return false;
+      if (RHS.isUndef())
+        return false;
       markOverdefined();
       return true;
     }
 
     if (isNotConstant()) {
       if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
         return false;
       markOverdefined();
       return true;
     }
 
     assert(isConstantRange() && "New ValueLattice type?");
+    if (RHS.isUndef() && getConstantRange().isSingleElement())
+      return false;
+
     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 (NewR.isFullSet())
-      markOverdefined();
+      return markOverdefined();
     else if (NewR == getConstantRange())
       return false;
     else
-      markConstantRange(std::move(NewR));
-    return true;
-  }
-
-  ConstantInt *getConstantInt() const {
-    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
-           "No integer constant");
-    return cast<ConstantInt>(getConstant());
+      return markConstantRange(std::move(NewR));
   }
 
   /// 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 (isUndefined() || Other.isUndefined())
+    if (isUnknownOrUndef() || Other.isUnknownOrUndef())
       return UndefValue::get(Ty);
 
     if (isConstant() && Other.isConstant())
       return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
 
     // Integer constants are represented as ConstantRanges with single
     // elements.
     if (!isConstantRange() || !Other.isConstantRange())

llvm/lib/Analysis/LazyValueInfo.cpp

 /// * Due to unreachable code, the intersection of two lattice values could be
 ///   contradictory.  If this happens, we return some valid lattice value so as
 ///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
 ///   we do not make this guarantee.  TODO: This would be a useful enhancement.
 static ValueLatticeElement intersect(const ValueLatticeElement &A,
                                      const ValueLatticeElement &B) {
   // Undefined is the strongest state.  It means the value is known to be along
   // an unreachable path.
-  if (A.isUndefined())
+  if (A.isUnknown())
     return A;
-  if (B.isUndefined())
+  if (B.isUnknown())
     return B;
 
   // If we gave up for one, but got a useable fact from the other, use it.
   if (A.isOverdefined())
     return B;
   if (B.isOverdefined())
     return A;
 
static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
   CmpInst::Predicate Predicate = ICI->getPredicate();
 
   if (isa<Constant>(RHS)) {
     if (ICI->isEquality() && LHS == Val) {
       // We know that V has the RHS constant if this is a true SETEQ or
       // false SETNE.
       if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ))
         return ValueLatticeElement::get(cast<Constant>(RHS));
-      else
+      else if (!isa<UndefValue>(RHS))
         return ValueLatticeElement::getNot(cast<Constant>(RHS));
     }
   }
 
   if (!Val->getType()->isIntegerTy())
     return ValueLatticeElement::getOverdefined();
 
   // Use ConstantRange::makeAllowedICmpRegion in order to determine the possible

 
 ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
                                               Instruction *CxtI) {
   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.isUndefined())
+  if (Result.isUnknown())
     return ConstantRange::getEmpty(Width);
   if (Result.isConstantRange())
     return Result.getConstantRange();
   // 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);
ConstantRange LazyValueInfo::getConstantRangeOnEdge(Value *V,
                                                     BasicBlock *FromBB,
                                                     BasicBlock *ToBB,
                                                     Instruction *CxtI) {
   unsigned Width = V->getType()->getIntegerBitWidth();
   const DataLayout &DL = FromBB->getModule()->getDataLayout();
   ValueLatticeElement Result =
       getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
 
-  if (Result.isUndefined())
+  if (Result.isUnknown())
     return ConstantRange::getEmpty(Width);
   if (Result.isConstantRange())
     return Result.getConstantRange();
   // 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);

 // Print the LVI for the function arguments at the start of each basic block.
 void LazyValueInfoAnnotatedWriter::emitBasicBlockStartAnnot(
     const BasicBlock *BB, formatted_raw_ostream &OS) {
   // Find if there are latticevalues defined for arguments of the function.
   auto *F = BB->getParent();
   for (auto &Arg : F->args()) {
     ValueLatticeElement Result = LVIImpl->getValueInBlock(
         const_cast<Argument *>(&Arg), const_cast<BasicBlock *>(BB));
-    if (Result.isUndefined())
+    if (Result.isUnknown())
       continue;
     OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n";
   }
 }
 
 // This function prints the LVI analysis for the instruction I at the beginning
 // of various basic blocks. It relies on calculated values that are stored in
 // the LazyValueInfoCache, and in the absence of cached values, recalculate the

llvm/lib/Analysis/ValueLattice.cpp

 //===- ValueLattice.cpp - Value constraint analysis -------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ValueLattice.h"
 
 namespace llvm {
 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) {
-  if (Val.isUndefined())
-    return OS << "undefined";
+  if (Val.isUnknown())
+    return OS << "unknown";
+  if (Val.isUndef())
+    return OS << "undef";
   if (Val.isOverdefined())
     return OS << "overdefined";
 
   if (Val.isNotConstant())
     return OS << "notconstant<" << *Val.getNotConstant() << ">";
   if (Val.isConstantRange())
     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
 } // end namespace llvm

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -correlated-propagation %s | FileCheck %s
+
+; Test case for PR44949.
+
+; We can remove `%res = and i64 %p, 255`, because %r = 0 and we can eliminate
+; %p as well.
+define i64 @constant_and_undef(i1 %c1, i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 0
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 0
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Check that we go to overdefined when merging a constant range with undef. We
+; cannot remove '%res = and i64 %p, 255'.
+; FIXME: should not remove '%res = and i64 %p, 255'
+define i64 @constant_range_and_undef(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef(
+; CHECK-NEXT:  entry:
+; 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:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+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:    [[V1:%.*]] = add i64 undef, undef
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V2:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[V1]], [[BB1]] ], [ [[V2]], [[BB2]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[V3:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[P]], [[BB4]] ], [ [[V3]], [[BB5]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P2]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %v1 = add i64 undef, undef
+  br label %bb3
+
+bb2:
+  %v2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %v1, %bb1 ], [ %v2, %bb2 ]
+  br i1 %c2, label %bb4, label %bb5
+
+bb4:
+  br label %bb6
+
+bb5:
+  %v3 = and i64 %a, 255
+  br label %bb6
+
+bb6:
+  %p2 = phi i64 [ %p, %bb4 ], [ %v3, %bb5 ]
+  %res = and i64 %p2, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_undef_3(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3(
+; CHECK-NEXT:  entry:
+; 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]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+; Same as @constant_range_and_undef, but with 3 incoming
+; values: undef, a constant and a constant range.
+define i64 @constant_range_and_undef_3_incoming_v1(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       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:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ 10, %bb2], [ undef, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], 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:    ret i64 [[P]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ undef, %bb1 ], [ 10, %bb2], [ %r, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v3(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       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]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2], [ 10, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+
+define i64 @constant_range_and_phi_constant_undef(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_phi_constant_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB4]] ]
+; CHECK-NEXT:    ret i64 [[P]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb5
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p.1 = phi i64 [ 10, %bb2 ], [ undef, %bb3]
+  br label %bb5
+
+bb5:
+  %p = phi i64 [ %r, %bb1 ], [ %p.1, %bb4]
+  %res = and i64 %p, 255
+  ret i64 %res
+}

llvm/test/Transforms/JumpThreading/ne-undef.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -jump-threading -S %s | FileCheck %s
+
+declare i1 @cond()
+
+define hidden void @hoge(i1 %c1, i32 %x)  {
+; CHECK-LABEL: @hoge(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB13:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP7:%.*]], undef
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB5:%.*]], label [[BB13]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[TMP7]] = phi i32 [ [[TMP7]], [[BB5]] ], [ [[X:%.*]], [[BB8:%.*]] ]
+; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C]], label [[BB4:%.*]], label [[BB8]]
+; CHECK:       bb8:
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb13:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br i1 false, label %bb1, label %bb13
+
+bb1:                                              ; preds = %bb
+  br label %bb2
+
+bb2:                                              ; preds = %bb12, %bb1
+  %tmp = phi i32 [ 10, %bb1 ], [ %tmp7, %bb12 ]
+  %tmp3 = icmp ne i32 %tmp, undef
+  br label %bb4
+
+bb4:                                              ; preds = %bb2
+  br i1 %tmp3, label %bb5, label %bb13
+
+bb5:                                              ; preds = %bb4
+  br label %bb6
+
+bb6:                                              ; preds = %bb8, %bb5
+  %tmp7 = phi i32 [ %tmp, %bb5 ], [ %x, %bb8 ]
+  %c = call i1 @cond()
+  br i1 %c, label %bb9, label %bb8
+
+bb8:                                              ; preds = %bb6
+  br label %bb6
+
+bb9:                                              ; preds = %bb6
+  br label %bb10
+
+bb10:                                             ; preds = %bb9
+  br label %bb12
+
+bb12:                                             ; preds = %bb10
+  br label %bb2
+
+bb13:                                             ; preds = %bb4
+  ret void
+
+}

llvm/test/Transforms/SCCP/float-phis.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
+
+declare void @use(i1)
+
+define void @test(i1 %c) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    br label [[DO_BODY:%.*]]
+; CHECK:       do.body:
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[DO_BODY]], label [[FOR_COND41:%.*]]
+; CHECK:       for.cond41:
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    br label [[FOR_COND41]]
+;
+  br label %do.body
+
+do.body:                                          ; preds = %do.body, %entry
+  br i1 %c, label %do.body, label %for.cond41
+
+for.cond41:                                       ; preds = %for.cond41, %do.body
+  %mid.0 = phi float [ 0.000000e+00, %for.cond41 ], [ undef, %do.body ]
+  %fc = fcmp oeq float %mid.0, 0.000000e+00
+  call void @use(i1 %fc)
+
+  br label %for.cond41
+}

llvm/test/Transforms/SCCP/int-phis.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -sccp -S | FileCheck %s
+
+declare void @use(i1)
+
+define void @read_dmatrix() #0 {
+; CHECK-LABEL: @read_dmatrix(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[HEIGHT:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[HEIGHT]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 0, [[TMP0]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_COND6:%.*]], label [[FOR_END16:%.*]]
+; CHECK:       for.cond6:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end16:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %height = alloca i32, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond6, %entry
+  %j.0 = phi i32 [ undef, %entry ], [ 0, %for.cond6 ]
+  %0 = load i32, i32* %height, align 4
+  %cmp = icmp slt i32 0, %0
+  br i1 %cmp, label %for.cond6, label %for.end16
+
+for.cond6:                                        ; preds = %for.cond
+  br label %for.cond
+
+for.end16:                                        ; preds = %for.cond
+  %sub21 = sub nsw i32 %j.0, 1
+  ret void
+}
+
+declare i1 @cond()
+
+define void @emptyTT() #0 {
+; CHECK-LABEL: @emptyTT(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[C:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br i1 [[C]], label [[FOR_COND]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %.compoundliteral.sroa.0.0 = phi i64 [ undef, %entry ], [ 0, %for.cond ]
+  %bf.clear = and i64 %.compoundliteral.sroa.0.0, -67108864
+  %c = call i1 @cond()
+  br i1 %c, label %for.cond, label %exit
+
+exit:
+  ret void
+}

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]]
+;
+  %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]]
+;
+  %c = icmp ult i64 %r, 256
+  call void @sideeffect(i1 %c, i64 %r)
+  ret i1 %c
+}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -sccp %s | FileCheck %s
+
+; Test case for PR44949.
+
+; We can remove `%res = and i64 %p, 255`, because %r = 0 and we can eliminate
+; %p as well.
+define i64 @constant_and_undef(i1 %c1, i64 %a) {
+; CHECK-LABEL: @constant_and_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i64 0
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 0
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Check that we go to overdefined when merging a constant range with undef. We
+; cannot remove '%res = and i64 %p, 255'.
+define i64 @constant_range_and_undef(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef(
+; CHECK-NEXT:  entry:
+; 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:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef, with the undef coming from the other
+; block.
+define i64 @constant_range_and_undef_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_switched_incoming(
+; CHECK-NEXT:  entry:
+; 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:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+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) {
+; 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:    [[C:%.*]] = icmp ult i64 [[P_AND]], 256
+; CHECK-NEXT:    ret i1 [[C]]
+;
+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
+}
+
+
+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 label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[V2:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[V2]], [[BB2]] ]
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB4:%.*]], label [[BB5:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[V3:%.*]] = and i64 [[A]], 255
+; CHECK-NEXT:    br label [[BB6]]
+; CHECK:       bb6:
+; CHECK-NEXT:    [[P2:%.*]] = phi i64 [ [[P]], [[BB4]] ], [ [[V3]], [[BB5]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P2]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %v1 = add i64 undef, undef
+  br label %bb3
+
+bb2:
+  %v2 = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %v1, %bb1 ], [ %v2, %bb2 ]
+  br i1 %c2, label %bb4, label %bb5
+
+bb4:
+  br label %bb6
+
+bb5:
+  %v3 = and i64 %a, 255
+  br label %bb6
+
+bb6:
+  %p2 = phi i64 [ %p, %bb4 ], [ %v3, %bb5 ]
+  %res = and i64 %p2, 255
+  ret i64 %res
+}
+
+define i1 @constant_range_and_undef_3(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3(
+; CHECK-NEXT:  entry:
+; 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]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ undef, %bb1 ], [ %r, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+define i1 @constant_range_and_undef_3_switched_incoming(i1 %cond, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_switched_incoming(
+; CHECK-NEXT:  entry:
+; 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]]
+;
+entry:
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2 ]
+  %c = icmp ult i64 %p, 256
+  ret i1 %c
+}
+
+; Same as @constant_range_and_undef, but with 3 incoming
+; values: undef, a constant and a constant range.
+define i64 @constant_range_and_undef_3_incoming_v1(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       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:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ 10, %bb2], [ undef, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v2(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], 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:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ undef, %bb1 ], [ 10, %bb2], [ %r, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+; Same as @constant_range_and_undef_3_incoming_v1, but with different order of
+; incoming values.
+define i64 @constant_range_and_undef_3_incoming_v3(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_undef_3_incoming_v3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       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]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb4
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p = phi i64 [ %r, %bb1 ], [ undef, %bb2], [ 10, %bb3 ]
+  %res = and i64 %p, 255
+  ret i64 %res
+}
+
+
+define i64 @constant_range_and_phi_constant_undef(i1 %c1, i1 %c2, i64 %a) {
+; CHECK-LABEL: @constant_range_and_phi_constant_undef(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[R:%.*]] = and i64 [[A:%.*]], 255
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB4]] ]
+; CHECK-NEXT:    [[RES:%.*]] = and i64 [[P]], 255
+; CHECK-NEXT:    ret i64 [[RES]]
+;
+entry:
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  %r = and i64 %a, 255
+  br label %bb5
+
+bb2:
+  br i1 %c2, label %bb3, label %bb4
+
+bb3:
+  br label %bb4
+
+bb4:
+  %p.1 = phi i64 [ 10, %bb2 ], [ undef, %bb3]
+  br label %bb5
+
+bb5:
+  %p = phi i64 [ %r, %bb1 ], [ %p.1, %bb4]
+  %res = and i64 %p, 255
+  ret i64 %res
+}

llvm/unittests/Analysis/ValueLatticeTest.cpp

TEST_F(ValueLatticeTest, ValueLatticeGetters) {
   EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined());
 
   auto FloatTy = Type::getFloatTy(Context);
   auto *C2 = ConstantFP::get(FloatTy, 1.1);
   EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant());
   EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant());
 }
 
+TEST_F(ValueLatticeTest, MarkConstantRange) {
+  auto LV1 =
+      ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)});
+
+  // Test markConstantRange() with an equal range.
+  EXPECT_FALSE(
+      LV1.markConstantRange({APInt(32, 10, true), APInt(32, 20, true)}));
+
+  // Test markConstantRange() with supersets of existing range.
+  EXPECT_TRUE(LV1.markConstantRange({APInt(32, 5, true), APInt(32, 20, true)}));
+  EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 5U);
+  EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 20U);
+  EXPECT_TRUE(LV1.markConstantRange({APInt(32, 5, true), APInt(32, 23, true)}));
+  EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 5U);
+  EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 23U);
+}
+
 TEST_F(ValueLatticeTest, MergeIn) {
   auto I32Ty = IntegerType::get(Context, 32);
   auto *C1 = ConstantInt::get(I32Ty, 1);
 
   // Merge to lattice values with equal integer constant.
   auto LV1 = ValueLatticeElement::get(C1);
   EXPECT_FALSE(LV1.mergeIn(ValueLatticeElement::get(C1), M.getDataLayout()));
   EXPECT_TRUE(LV1.isConstantRange());