[ValueLattice] Add new state for undef constants.

[fhahn]

Summary

This patch adds a new undef lattice state, which is used to represent
UndefValue constants or instructions producing undef.

The main difference to the unknown state is that merging undef values
with constants (or single element constant ranges) produces the
constant/constant range, assuming all uses of the merge result will be
replaced by the found constant.

Contrary, merging non-single element ranges with undef needs to go to
overdefined. Using unknown for UndefValues currently causes mis-compiles
in CVP/LVI (PR44949) and will become problematic once we use
ValueLatticeElement for SCCP.

[efriedma]

I'm not quite sure the merge function here is right. I think constant_merged_with_undef has to be a different state from constant. It's basically the same as constant, except that merging it with a different constant or constantrange produces overdefined.

llvm/lib/Transforms/Scalar/SCCP.cpp

439

Not sure about this change; do we not need to markUndef?

[fhahn]

In D75120#1892449, @efriedma wrote:

I'm not quite sure the merge function here is right. I think constant_merged_with_undef has to be a different state from constant. It's basically the same as constant, except that merging it with a different constant or constantrange produces overdefined.

Yes it still misses that case. I see it as the first step of the transition. To address the undef -> constant -> constant range merge issue there are a few options I think:

1. let caller deal with it, e.g. by passing in whether one of the merge operands is undefined.
2. Differentiate between constants that started out as undefined in ValueLattice, e.g. by adding another state like constant_from_undef (that would be a bit like forcedconstant, with the difference being that it cannot be marked as a different constant - which would go to overdefined for forced constant) or by using undefined + Constant pointer set.

Maybe there are other options? What would your preference be?

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

439

markConstant used to be a no-op for UndefValue constants. I've updated it to use markUndefined for UndefValue constants, it might be clearer to do it explicitly here though?

[efriedma]

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

llvm/lib/Transforms/Scalar/SCCP.cpp

439

Oh, right, that makes sense.

[efriedma]

And yes, I guess the new lattice state is very similar to the old forcedconstant. We could even port the various tricks involving arithmetic on undef from the old ResolveUndefsIn.

[fhahn]

In D75120#1893937, @efriedma wrote:

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

Thanks Eli (and sorry for the late response, I somehow missed your response).

I *think* the callers of the mergeIn functions should the information, but I agree it would be much better to model it explicitly. I'll put up a patch soon.

[fhahn]

Rebased with additional tests, fix formatting.

[fhahn]

In D75120#1906427, @fhahn wrote:

In D75120#1893937, @efriedma wrote:

If you don't have all the relevant states represented in the ValueLattice, where are you storing the "possibly undef" bit? I think having all the states in the ValueLattice is simpler, at least conceptually.

I've put up a patch that adds a new lattice state for single element constant ranges that started out/merged with undef: D75845. I hope that's along the lines you suggested.

I worked on an SCCP test case for that, but the way we currently handle PHIs means we merge all incoming values in the existing state for a PHI, which means that if the result is a constant range and any operands is undef, we will merge CR & undef, going to overdefined.

With an additional patch skipping some unnecessary updates (D75846), I managed to get a SCCP test case (llvm/test/Transforms/SCCP/range-and-ip.ll) in D75845. There's also a test case that shows the issue with CorrelatedValuePropagation.

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

135

I'm not sure I understand how getNot(undef) is supposed to work.

295

We already checked RHS.isUnknown() earlier?

[fhahn]

Remove unnecessary RHS.isUnknown() check.

[fhahn]

Add test case where LVI uses getNot(undef). Add comment it should be fine to assume undef from x != undef. Alive seems to agree (I would post a link, but rise4fun.com is terrible slow to respond)

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

135

I think it should be fine to assume x != undef => undef. Alive seems to agree. Granted, it is probably not very useful. I tried to replace it with an assert ruling out undef here, but we hit this case in practice in LVI via JumpThreading.

295

Done, thanks! I've added an assertion to guard against accidentally breaking the assumption by changes.

[nikic]

llvm/include/llvm/Analysis/ValueLattice.h

198

Nit: Should be markUndef() for consistency.

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

135

If you prove x != undef, x can't be any specific value... including undef, I think. So actually you could just treat it as unknown, I think?

[fhahn]

Rename markUndefined -> markUndef as suggested.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

135

Looking at the uses in LVI, it seems like it is used for information coming from things like %x = icmp ne %a, CONST; %y = select %x, %a, 10 and LVI would use getNot(CONST) and use that to mark %y as != CONST if 10 != Const . (https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/LazyValueInfo.cpp#L953)

I'm not sure if that allows saying that %a cannot be any specific value including undef, if CONST is undef. Couldn't the use in %a be any value, by choosing something like %a+1 for undef in the icmp?

Because IIUC we can only chose a single concrete value for the undef in the icmp per execution.

Another way to think about it might be a constant range with a single value missing. The missing value can be arbitrarily chosen per use/execution. I think what's allowed and dis-allowed would heavily depend on how it is used exactly. Maybe it would be best to start out with overdefined in this patch and refine it if required later on?

[efriedma]

llvm/include/llvm/Analysis/ValueLattice.h

135

Oh, I see, code being analyzed is not actually assuming it like an llvm.assume; it's just using it in the condition of a select.

I guess that a == undef ? 0 : undef+1 is in fact undef... but I don't think that generalizes in any useful way to other places we might use getNot(). I'd prefer to explicitly bail out in LVI, as opposed to handling it here.

[fhahn]

Assert on getNot(undef), avoid in LVI.

[fhahn]

llvm/include/llvm/Analysis/ValueLattice.h

135

Sounds good! I've updated LVI to not use getNot for undef constants and added an assertion to getNot().

[efriedma]

LGTM

[fhahn]

Rebased after recent changes landed.

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 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,
 
     /// 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
class ValueLatticeElement {
   /// 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.markUndefined();
+    else
       Res.markConstant(C);
     return Res;
   }
   static ValueLatticeElement getNot(Constant *C) {
     ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
+    if (isa<UndefValue>(C))
+      Res.markUndefined();
+    else
       Res.markNotConstant(C);
     return Res;
   }
   static ValueLatticeElement getRange(ConstantRange CR) {
+    if (CR.isFullSet())
+      return getOverdefined();
+
     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 isUnknown() 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 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;
bool markOverdefined() {
     if (isConstant() || isNotConstant())
       ConstVal = nullptr;
     if (isConstantRange())
       Range.~ConstantRange();
     Tag = overdefined;
     return true;
   }
 
+  bool markUndefined() {
+    if (isUndef())
+      return false;
+
+    assert(isUnknown());
+    Tag = undef;
+    return true;
+  }
+
   bool markConstant(Constant *V) {
     if (isa<UndefValue>(V))
-      return false;
+      return markUndefined();
 
     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(isUndefined());
+    assert(isUnknown() || isUndef());
     Tag = constant;
     ConstVal = V;
     return true;
   }
 
   bool markNotConstant(Constant *V) {
     assert(V && "Marking constant with NULL");
     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
       return markConstantRange(
           ConstantRange(CI->getValue() + 1, CI->getValue()));
 
     if (isa<UndefValue>(V))
       return false;
 
     if (isNotConstant()) {
       assert(getNotConstant() == V && "Marking !constant with different value");
       return false;
     }
 
-    assert(isUndefined());
+    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 undefined.
+  /// object must be undef.
   bool markConstantRange(ConstantRange NewR) {
     if (isConstantRange()) {
       if (getConstantRange() == NewR)
         return false;
 
       if (NewR.isEmptySet())
         return markOverdefined();
 
       assert(NewR.contains(getConstantRange()) &&
              "Existing range must be a subset of NewR");
       Range = std::move(NewR);
       return true;
     }
 
-    assert(isUndefined());
+    assert(isUnknown() || isUndef());
     if (NewR.isEmptySet())
       return markOverdefined();
 
     Tag = constantrange;
     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.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()) {
       *this = RHS;
-      return !RHS.isUndefined();
+      return !RHS.isUnknown();
     }
 
     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())
       return markOverdefined();
     else if (NewR == getConstantRange())
       return false;
     else
       return markConstantRange(std::move(NewR));
   }
 
-  /// Compares this symbolic value with Other using Pred and returns either
+  // 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 (isUnknown() || Other.isUnknown())
       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;
 

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

LatticeVal &getValueState(Value *V) {
     std::pair<DenseMap<Value*, LatticeVal>::iterator, bool> I =
       ValueState.insert(std::make_pair(V, LatticeVal()));
     LatticeVal &LV = I.first->second;
 
     if (!I.second)
       return LV;  // Common case, already in the map.
 
     if (auto *C = dyn_cast<Constant>(V)) {
-      // Undef values remain unknown.
-      if (!isa<UndefValue>(V))
         LV.markConstant(C);          // Constants are constant
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
   LatticeVal toLatticeVal(const ValueLatticeElement &V, Type *T) {
     LatticeVal Res;
-    if (V.isUndefined())
+    if (V.isUnknownOrUndef())
       return Res;
 
     if (V.isConstant()) {
       Res.markConstant(V.getConstant());
       return Res;
     }
     if (V.isConstantRange() && V.getConstantRange().isSingleElement()) {
       Res.markConstant(
if (BI->isUnconditional()) {
       return;
     }
 
     LatticeVal BCValue = getValueState(BI->getCondition());
     ConstantInt *CI = getConstantInt(BCValue);
     if (!CI) {
       // Overdefined condition variables, and branches on unfoldable constant
       // conditions, mean the branch could go either way.
-      if (!BCValue.isUnknown())
+      if (!BCValue.isUnknownOrUndef())
         Succs[0] = Succs[1] = true;
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way.
     Succs[CI->isZero()] = true;
     return;
   }
if (!SI->getNumCases()) {
       Succs[0] = true;
       return;
     }
     LatticeVal SCValue = getValueState(SI->getCondition());
     ConstantInt *CI = getConstantInt(SCValue);
 
     if (!CI) {   // Overdefined or unknown condition?
       // All destinations are executable!
-      if (!SCValue.isUnknown())
+      if (!SCValue.isUnknownOrUndef())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     Succs[SI->findCaseValue(CI)->getSuccessorIndex()] = true;
     return;
   }
 
   // In case of indirect branch and its address is a blockaddress, we mark
   // the target as executable.
   if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
     // Casts are folded by visitCastInst.
     LatticeVal IBRValue = getValueState(IBR->getAddress());
     BlockAddress *Addr = dyn_cast_or_null<BlockAddress>(getConstant(IBRValue));
     if (!Addr) {   // Overdefined or unknown condition?
       // All destinations are executable!
-      if (!IBRValue.isUnknown())
+      if (!IBRValue.isUnknownOrUndef())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     BasicBlock* T = Addr->getBasicBlock();
     assert(Addr->getFunction() == T->getParent() &&
            "Block address of a different function ?");
     for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
if (Constant *OpC = getConstant(OpSt)) {
     markConstant(&I, C);
   } else if (OpSt.isConstantRange() && I.getDestTy()->isIntegerTy()) {
     LatticeVal &LV = getValueState(&I);
     ConstantRange OpRange = OpSt.getConstantRange();
     Type *DestTy = I.getDestTy();
     ConstantRange Res =
         OpRange.castOp(I.getOpcode(), DL.getTypeSizeInBits(DestTy));
     mergeInValue(LV, &I, LatticeVal::getRange(Res));
-  } else if (!OpSt.isUnknown())
+  } else if (!OpSt.isUnknownOrUndef())
     markOverdefined(&I);
 }
 
 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (ValueState[&EVI].isOverdefined())
     return;
if (I.getType()->isStructTy())
     return (void)markOverdefined(&I);
 
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (ValueState[&I].isOverdefined())
     return;
 
   LatticeVal CondValue = getValueState(I.getCondition());
-  if (CondValue.isUnknown())
+  if (CondValue.isUnknownOrUndef())
     return;
 
   if (ConstantInt *CondCB = getConstantInt(CondValue)) {
     Value *OpVal = CondCB->isZero() ? I.getFalseValue() : I.getTrueValue();
     mergeInValue(&I, getValueState(OpVal));
     return;
   }
 
void SCCPSolver::visitBinaryOperator(Instruction &I) {
   LatticeVal V1State = getValueState(I.getOperand(0));
   LatticeVal V2State = getValueState(I.getOperand(1));
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined())
     return;
 
   // If something is undef, wait for it to resolve.
-  if (V1State.isUnknown() || V2State.isUnknown())
+  if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef())
     return;
 
   // TODO: could do better than that in some cases.
   if (V1State.isNotConstant() || V2State.isNotConstant())
     return (void)markOverdefined(&I);
 
   if (V1State.isOverdefined() && V2State.isOverdefined())
     return (void)markOverdefined(&I);
if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
       I.getOpcode() == Instruction::Or) {
     LatticeVal *NonOverdefVal = nullptr;
     if (!isOverdefined(V1State))
       NonOverdefVal = &V1State;
 
     else if (!isOverdefined(V2State))
       NonOverdefVal = &V2State;
     if (NonOverdefVal) {
-      if (NonOverdefVal->isUnknown())
+      if (!isConstant(*NonOverdefVal))
         return;
 
       if (I.getOpcode() == Instruction::And ||
           I.getOpcode() == Instruction::Mul) {
         // X and 0 = 0
         // X * 0 = 0
         if (getConstant(*NonOverdefVal)->isNullValue())
           return (void)markConstant(IV, &I, getConstant(*NonOverdefVal));
if (isa<UndefValue>(C))
       return;
     LatticeVal CV;
     CV.markConstant(C);
     mergeInValue(&I, CV);
     return;
   }
 
   // If operands are still unknown, wait for it to resolve.
-  if ((V1State.isUnknown() || V2State.isUnknown()) &&
+  if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) &&
       !isConstant(ValueState[&I]))
     return;
 
   markOverdefined(&I);
 }
 
 // Handle getelementptr instructions.  If all operands are constants then we
 // can turn this into a getelementptr ConstantExpr.
 void SCCPSolver::visitGetElementPtrInst(GetElementPtrInst &I) {
   if (ValueState[&I].isOverdefined()) return;
 
   SmallVector<Constant*, 8> Operands;
   Operands.reserve(I.getNumOperands());
 
   for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
     LatticeVal State = getValueState(I.getOperand(i));
-    if (State.isUnknown())
+    if (State.isUnknownOrUndef())
       return;  // Operands are not resolved yet.
 
     if (State.isOverdefined())
       return (void)markOverdefined(&I);
 
     if (Constant *C = getConstant(State)) {
       Operands.push_back(C);
       continue;
if (I.getType()->isStructTy())
     return (void)markOverdefined(&I);
 
   // ResolvedUndefsIn might mark I as overdefined. Bail out, even if we would
   // discover a concrete value later.
   if (ValueState[&I].isOverdefined())
     return;
 
   LatticeVal PtrVal = getValueState(I.getOperand(0));
-  if (PtrVal.isUnknown()) return;   // The pointer is not resolved yet!
+  if (PtrVal.isUnknownOrUndef())
+    return; // The pointer is not resolved yet!
 
   LatticeVal &IV = ValueState[&I];
 
   if (!isConstant(PtrVal) || I.isVolatile())
     return (void)markOverdefined(IV, &I);
 
   Constant *Ptr = getConstant(PtrVal);
 
if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
         canConstantFoldCallTo(cast<CallBase>(CS.getInstruction()), F)) {
       SmallVector<Constant*, 8> Operands;
       for (CallSite::arg_iterator AI = CS.arg_begin(), E = CS.arg_end();
            AI != E; ++AI) {
         if (AI->get()->getType()->isStructTy())
           return markOverdefined(I); // Can't handle struct args.
         LatticeVal State = getValueState(*AI);
 
-        if (State.isUnknown())
+        if (State.isUnknownOrUndef())
           return;  // Operands are not resolved yet.
         if (!isConstant(State))
           return (void)markOverdefined(I);
         Operands.push_back(getConstant(State));
       }
 
       if (getValueState(I).isOverdefined())
         return;
for (Instruction &I : BB) {
         // extractvalue and insertvalue don't need to be marked; they are
         // tracked as precisely as their operands.
         if (isa<ExtractValueInst>(I) || isa<InsertValueInst>(I))
           continue;
         // Send the results of everything else to overdefined.  We could be
         // more precise than this but it isn't worth bothering.
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           LatticeVal &LV = getStructValueState(&I, i);
-          if (LV.isUnknown())
+          if (LV.isUnknownOrUndef())
             markOverdefined(LV, &I);
         }
         continue;
       }
 
       LatticeVal &LV = getValueState(&I);
-      if (!LV.isUnknown())
+      if (!LV.isUnknownOrUndef())
         continue;
 
       // There are two reasons a call can have an undef result
       // 1. It could be tracked.
       // 2. It could be constant-foldable.
       // Because of the way we solve return values, tracked calls must
       // never be marked overdefined in ResolvedUndefsIn.
       if (CallSite CS = CallSite(&I))
for (BasicBlock &BB : F) {
     }
 
     // Check to see if we have a branch or switch on an undefined value.  If so
     // we force the branch to go one way or the other to make the successor
     // values live.  It doesn't really matter which way we force it.
     Instruction *TI = BB.getTerminator();
     if (auto *BI = dyn_cast<BranchInst>(TI)) {
       if (!BI->isConditional()) continue;
-      if (!getValueState(BI->getCondition()).isUnknown())
+      if (!getValueState(BI->getCondition()).isUnknownOrUndef())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // false.
       if (isa<UndefValue>(BI->getCondition())) {
         BI->setCondition(ConstantInt::getFalse(BI->getContext()));
         markEdgeExecutable(&BB, TI->getSuccessor(1));
         return true;
for (BasicBlock &BB : F) {
     }
 
    if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
       // Indirect branch with no successor ?. Its ok to assume it branches
       // to no target.
       if (IBR->getNumSuccessors() < 1)
         continue;
 
-      if (!getValueState(IBR->getAddress()).isUnknown())
+      if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
         continue;
 
       // If the input to SCCP is actually branch on undef, fix the undef to
       // the first successor of the indirect branch.
       if (isa<UndefValue>(IBR->getAddress())) {
         IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
         markEdgeExecutable(&BB, IBR->getSuccessor(0));
         return true;
       }
 
       // Otherwise, it is a branch on a symbolic value which is currently
       // considered to be undef.  Make sure some edge is executable, so a
       // branch on "undef" always flows somewhere.
       // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
       // we can assume the branch has undefined behavior instead.
       BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
       if (markEdgeExecutable(&BB, DefaultSuccessor))
         return true;
 
       continue;
     }
 
     if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-      if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
+      if (!SI->getNumCases() ||
+          !getValueState(SI->getCondition()).isUnknownOrUndef())
         continue;
 
       // If the input to SCCP is actually switch on undef, fix the undef to
       // the first constant.
       if (isa<UndefValue>(SI->getCondition())) {
         SI->setCondition(SI->case_begin()->getCaseValue());
         markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
         return true;

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

 ; 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:    ret i64 [[P]]
+; 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 nuw nsw i64 undef, undef
+; 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:

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

 ; 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:    ret i1 true
+; 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:

 ; 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:    ret i1 true
+; 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
 }