[SCCP] Integrate `undef` in the solver

[davide]

Summary

Trying to fix https://llvm.org/bugs/show_bug.cgi?id=30448 and another bunch of latent bugs in SCCP.
I'm going to send a detailed mails about the motivations to llvm-dev in a bit, but I wanted a review to link to first.

[davide]

Link of the llvm-dev proposal:
http://lists.llvm.org/pipermail/llvm-dev/2016-December/108588.html

[efriedma]

Code looks fine.

lib/Transforms/Scalar/SCCP.cpp

529

Did you mean to special-case undef here?

[davide]

This is ancient history. Florian (@fhahn) did a bunch of work in the area and can probably pick some of this up if he wants to.

lib/Transforms/Scalar/SCCP.cpp

 class LatticeVal {
   enum LatticeValueTy {
     /// unknown - This LLVM Value has no known value yet.
     unknown,
 
     /// constant - This LLVM Value has a specific constant value.
     constant,
 
-    /// forcedconstant - This LLVM Value was thought to be undef until
-    /// ResolvedUndefsIn.  This is treated just like 'constant', but if merged
-    /// with another (different) constant, it goes to overdefined, instead of
-    /// asserting.
-    forcedconstant,
-
     /// overdefined - This instruction is not known to be constant, and we know
     /// it has a value.
     overdefined
   };
 
   /// Val: This stores the current lattice value along with the Constant* for
-  /// the constant if this is a 'constant' or 'forcedconstant' value.
+  /// the constant if this is a 'constant' value.
   PointerIntPair<Constant *, 2, LatticeValueTy> Val;
 
   LatticeValueTy getLatticeValue() const {
     return Val.getInt();
   }
 
 public:
   LatticeVal() : Val(nullptr, unknown) {}
 
   bool isUnknown() const { return getLatticeValue() == unknown; }
-  bool isConstant() const {
-    return getLatticeValue() == constant || getLatticeValue() == forcedconstant;
-  }
+  bool isConstant() const { return getLatticeValue() == constant; }
   bool isOverdefined() const { return getLatticeValue() == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
     return Val.getPointer();
   }
 
   /// markOverdefined - Return true if this is a change in status.
   bool markOverdefined() {
     if (isOverdefined())
       return false;
 
     Val.setInt(overdefined);
     return true;
   }
 
   /// markConstant - Return true if this is a change in status.
   bool markConstant(Constant *V) {
-    if (getLatticeValue() == constant) { // Constant but not forcedconstant.
+    if (getLatticeValue() == constant) {
       assert(getConstant() == V && "Marking constant with different value");
       return false;
     }
 
     if (isUnknown()) {
       Val.setInt(constant);
       assert(V && "Marking constant with NULL");
       Val.setPointer(V);
-    } else {
-      assert(getLatticeValue() == forcedconstant &&
-             "Cannot move from overdefined to constant!");
-      // Stay at forcedconstant if the constant is the same.
-      if (V == getConstant()) return false;
-
-      // Otherwise, we go to overdefined.  Assumptions made based on the
-      // forced value are possibly wrong.  Assuming this is another constant
-      // could expose a contradiction.
-      Val.setInt(overdefined);
     }
     return true;
   }
 
   /// getConstantInt - If this is a constant with a ConstantInt value, return it
   /// otherwise return null.
   ConstantInt *getConstantInt() const {
     if (isConstant())
       return dyn_cast<ConstantInt>(getConstant());
     return nullptr;
   }
-
-  void markForcedConstant(Constant *V) {
-    assert(isUnknown() && "Can't force a defined value!");
-    Val.setInt(forcedconstant);
-    Val.setPointer(V);
-  }
 };
 } // end anonymous namespace.
 
 
 namespace {
 
 //===----------------------------------------------------------------------===//
 //
public:
   void AddArgumentTrackedFunction(Function *F) {
     TrackingIncomingArguments.insert(F);
   }
 
   /// Solve - Solve for constants and executable blocks.
   ///
   void Solve();
 
-  /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
-  /// that branches on undef values cannot reach any of their successors.
-  /// However, this is not a safe assumption.  After we solve dataflow, this
-  /// method should be use to handle this.  If this returns true, the solver
-  /// should be rerun.
-  bool ResolvedUndefsIn(Function &F);
-
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
   std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
     std::vector<LatticeVal> StructValues;
     auto *STy = dyn_cast<StructType>(V->getType());
     assert(STy && "getStructLatticeValueFor() can be called only on structs");
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       LatticeVal LV = It->second;
       if (LV.isOverdefined())
         return false;
     }
     return true;
   }
 
 private:
-  // pushToWorkList - Helper for markConstant/markForcedConstant/markOverdefined
+  // pushToWorkList - Helper for markConstant/markOverdefined
   void pushToWorkList(LatticeVal &IV, Value *V) {
     if (IV.isOverdefined())
       return OverdefinedInstWorkList.push_back(V);
     InstWorkList.push_back(V);
   }
 
   // markConstant - Make a value be marked as "constant".  If the value
   // is not already a constant, add it to the instruction work list so that
   // the users of the instruction are updated later.
   //
   void markConstant(LatticeVal &IV, Value *V, Constant *C) {
     if (!IV.markConstant(C)) return;
     DEBUG(dbgs() << "markConstant: " << *C << ": " << *V << '\n');
     pushToWorkList(IV, V);
   }
 
   void markConstant(Value *V, Constant *C) {
     assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
     markConstant(ValueState[V], V, C);
   }
 
-  void markForcedConstant(Value *V, Constant *C) {
-    assert(!V->getType()->isStructTy() && "structs should use mergeInValue");
-    LatticeVal &IV = ValueState[V];
-    IV.markForcedConstant(C);
-    DEBUG(dbgs() << "markForcedConstant: " << *C << ": " << *V << '\n');
-    pushToWorkList(IV, V);
-  }
-
-
   // markOverdefined - Make a value be marked as "overdefined". If the
   // value is not already overdefined, add it to the overdefined instruction
   // work list so that the users of the instruction are updated later.
   void markOverdefined(LatticeVal &IV, Value *V) {
     if (!IV.markOverdefined()) return;
 
     DEBUG(dbgs() << "markOverdefined: ";
           if (auto *F = dyn_cast<Function>(V))
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
-    }
+    // We found a value that's constant, so we set its lattice
+    // value to constant accordingly.
+    if (auto *C = dyn_cast<Constant>(V))
+      LV.markConstant(C);
 
     // All others are underdefined by default.
     return LV;
   }
 
   /// getStructValueState - Return the LatticeVal object that corresponds to the
   /// value/field pair.  This function handles the case when the value hasn't
   /// been seen yet by properly seeding constants etc.
LatticeVal &getStructValueState(Value *V, unsigned i) {
     if (!I.second)
       return LV;  // Common case, already in the map.
 
     if (auto *C = dyn_cast<Constant>(V)) {
       Constant *Elt = C->getAggregateElement(i);
 
       if (!Elt)
         LV.markOverdefined();      // Unknown sort of constant.
-      else if (isa<UndefValue>(Elt))
-        ; // Undef values remain unknown.
       else
         LV.markConstant(Elt);      // Constants are constant.
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
private:
   // Terminators
   void visitReturnInst(ReturnInst &I);
   void visitTerminatorInst(TerminatorInst &TI);
 
   void visitCastInst(CastInst &I);
   void visitSelectInst(SelectInst &I);
   void visitBinaryOperator(Instruction &I);
   void visitCmpInst(CmpInst &I);
-  void visitExtractElementInst(ExtractElementInst &I);
-  void visitInsertElementInst(InsertElementInst &I);
-  void visitShuffleVectorInst(ShuffleVectorInst &I);
   void visitExtractValueInst(ExtractValueInst &EVI);
   void visitInsertValueInst(InsertValueInst &IVI);
   void visitLandingPadInst(LandingPadInst &I) { markAnythingOverdefined(&I); }
   void visitFuncletPadInst(FuncletPadInst &FPI) {
     markAnythingOverdefined(&FPI);
   }
   void visitCatchSwitchInst(CatchSwitchInst &CPI) {
     markAnythingOverdefined(&CPI);
void SCCPSolver::getFeasibleSuccessors(TerminatorInst &TI,
   Succs.resize(TI.getNumSuccessors());
   if (auto *BI = dyn_cast<BranchInst>(&TI)) {
     if (BI->isUnconditional()) {
       Succs[0] = true;
       return;
     }
 
     LatticeVal BCValue = getValueState(BI->getCondition());
+
     ConstantInt *CI = BCValue.getConstantInt();
     if (!CI) {
       // Overdefined condition variables, and branches on unfoldable constant
       // conditions, mean the branch could go either way.
       if (!BCValue.isUnknown())
         Succs[0] = Succs[1] = true;
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way.
     Succs[CI->isZero()] = true;
     return;
   }
 
   // Unwinding instructions successors are always executable.
   if (TI.isExceptional()) {
     Succs.assign(TI.getNumSuccessors(), true);
     return;
   }
 
   if (auto *SI = dyn_cast<SwitchInst>(&TI)) {
     if (!SI->getNumCases()) {
       Succs[0] = true;
       return;
     }
     LatticeVal SCValue = getValueState(SI->getCondition());
+
+    // Handle branch on undef marking the first successor as live.
+    if (SCValue.isConstant()) {
+      Constant *C  = SCValue.getConstant();
+      assert(C && "C should be a constant");
+      if (isa<UndefValue>(C)) {
+        ConstantInt *CI = SI->case_begin().getCaseValue();
+        Succs[SI->findCaseValue(CI).getSuccessorIndex()] = true;
+        return;
+      }
+    }
+
     ConstantInt *CI = SCValue.getConstantInt();
 
     if (!CI) {   // Overdefined or unknown condition?
       // All destinations are executable!
       if (!SCValue.isUnknown())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
void SCCPSolver::visitPHINode(PHINode &PN) {
   // and slow us down a lot.  Just mark them overdefined.
   if (PN.getNumIncomingValues() > 64)
     return markOverdefined(&PN);
 
   // Look at all of the executable operands of the PHI node.  If any of them
   // are overdefined, the PHI becomes overdefined as well.  If they are all
   // constant, and they agree with each other, the PHI becomes the identical
   // constant.  If they are constant and don't agree, the PHI is overdefined.
-  // If there are no executable operands, the PHI remains unknown.
-  //
+  // If all the operands are undefined, the PHI goes to overdefined.
   Constant *OperandVal = nullptr;
   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     LatticeVal IV = getValueState(PN.getIncomingValue(i));
     if (IV.isUnknown()) continue;  // Doesn't influence PHI node.
 
+    // 'undef' doesn't influence a phi.
+    // For example, we have:
+    // %patatino = phi i32* [ undef, %a ], [ null, %b ], [ null, %c ]
+    // We can fold %patatino to null as the other two phi values agree
+    // and 'undef' has no effect here.
+    if (IV.isConstant() && isa<UndefValue>(IV.getConstant()))
+      continue;
+
     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent()))
       continue;
 
     if (IV.isOverdefined())    // PHI node becomes overdefined!
       return markOverdefined(&PN);
 
     if (!OperandVal) {   // Grab the first value.
       OperandVal = IV.getConstant();
       continue;
     }
 
     // There is already a reachable operand.  If we conflict with it,
     // then the PHI node becomes overdefined.  If we agree with it, we
     // can continue on.
 
     // Check to see if there are two different constants merging, if so, the PHI
     // node is overdefined.
     if (IV.getConstant() != OperandVal)
       return markOverdefined(&PN);
   }
 
   // If we exited the loop, this means that the PHI node only has constant
   // arguments that agree with each other(and OperandVal is the constant) or
-  // OperandVal is null because there are no defined incoming arguments.  If
-  // this is the case, the PHI remains unknown.
-  //
+  // OperandVal is null because there are no defined incoming arguments.
+  // In the latter case, we send it to overdefined.
   if (OperandVal)
-    markConstant(&PN, OperandVal);      // Acquire operand value
+    return markConstant(&PN, OperandVal);      // Acquire operand value
+  return markOverdefined(&PN);
 }
 
 void SCCPSolver::visitReturnInst(ReturnInst &I) {
   if (I.getNumOperands() == 0) return;  // ret void
 
   Function *F = I.getParent()->getParent();
   Value *ResultOp = I.getOperand(0);
 
void SCCPSolver::visitTerminatorInst(TerminatorInst &TI) {
   // Mark all feasible successors executable.
   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
     if (SuccFeasible[i])
       markEdgeExecutable(BB, TI.getSuccessor(i));
 }
 
 void SCCPSolver::visitCastInst(CastInst &I) {
   LatticeVal OpSt = getValueState(I.getOperand(0));
-  if (OpSt.isOverdefined())          // Inherit overdefinedness of operand
-    markOverdefined(&I);
-  else if (OpSt.isConstant()) {
-    // Fold the constant as we build.
+  if (OpSt.isOverdefined())
+    return markOverdefined(&I);
+  if (OpSt.isConstant()) {
     Constant *C = ConstantFoldCastOperand(I.getOpcode(), OpSt.getConstant(),
                                           I.getType(), DL);
-    if (isa<UndefValue>(C))
-      return;
-    // Propagate constant value
     markConstant(&I, C);
   }
 }
 
 
 void SCCPSolver::visitExtractValueInst(ExtractValueInst &EVI) {
   // If this returns a struct, mark all elements over defined, we don't track
   // structs in structs.
void SCCPSolver::visitSelectInst(SelectInst &I) {
   }
 
   // Otherwise, the condition is overdefined or a constant we can't evaluate.
   // See if we can produce something better than overdefined based on the T/F
   // value.
   LatticeVal TVal = getValueState(I.getTrueValue());
   LatticeVal FVal = getValueState(I.getFalseValue());
 
+  if (TVal.isConstant() && FVal.isConstant()) {
+    // FIXME: check if there's a way to just call an API instead of
+    // doing the constant folding dance in SCCP.
+    Constant *TC = TVal.getConstant();
+    Constant *FC = FVal.getConstant();
+
     // select ?, C, C -> C.
-  if (TVal.isConstant() && FVal.isConstant() &&
-      TVal.getConstant() == FVal.getConstant())
-    return markConstant(&I, FVal.getConstant());
-
-  if (TVal.isUnknown())   // select ?, undef, X -> X.
-    return mergeInValue(&I, FVal);
-  if (FVal.isUnknown())   // select ?, X, undef -> X.
-    return mergeInValue(&I, TVal);
+    if (TC == FC)
+      return markConstant(&I, TC);
+
+    // select ?, undef, C -> C
+    // select ?, C, undef -> C
+    if (isa<UndefValue>(TC))
+      return markConstant(&I, FC);
+    if (isa<UndefValue>(FC))
+      return markConstant(&I, TC);
+  }
   markOverdefined(&I);
 }
 
 // Handle Binary Operators.
 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 (V1State.isConstant() && V2State.isConstant()) {
     Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(),
                                     V2State.getConstant());
-    // X op Y -> undef.
-    if (isa<UndefValue>(C))
-      return;
     return markConstant(IV, &I, C);
   }
 
-  // If something is undef, wait for it to resolve.
+  // If something is unknown, wait for it to resolve.
   if (!V1State.isOverdefined() && !V2State.isOverdefined())
     return;
 
   // Otherwise, one of our operands is overdefined.  Try to produce something
   // better than overdefined with some tricks.
 
   // If this is an AND or OR with 0 or -1, it doesn't matter that the other
   // operand is overdefined.
   if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul ||
       I.getOpcode() == Instruction::Or) {
     LatticeVal *NonOverdefVal = nullptr;
     if (!V1State.isOverdefined())
       NonOverdefVal = &V1State;
     else if (!V2State.isOverdefined())
       NonOverdefVal = &V2State;
 
     if (NonOverdefVal) {
       if (NonOverdefVal->isUnknown())
         return;
 
       if (I.getOpcode() == Instruction::And ||
           I.getOpcode() == Instruction::Mul) {
         // X and 0 = 0
+        // X and undef = 0
         // X * 0 = 0
-        if (NonOverdefVal->getConstant()->isNullValue())
-          return markConstant(IV, &I, NonOverdefVal->getConstant());
+        Constant *C = NonOverdefVal->getConstant();
+        if (C->isNullValue() || isa<UndefValue>(C))
+          return markConstant(IV, &I, Constant::getNullValue(I.getType()));
       } else {
         // X or -1 = -1
-        if (ConstantInt *CI = NonOverdefVal->getConstantInt())
-          if (CI->isAllOnesValue())
-            return markConstant(IV, &I, NonOverdefVal->getConstant());
+        // X or undef = -1
+        Constant *C = NonOverdefVal->getConstant();
+        Constant *CI = NonOverdefVal->getConstantInt();
+        if ((C && isa<UndefValue>(C)) || (CI && CI->isAllOnesValue()))
+          return markConstant(IV, &I, Constant::getAllOnesValue(I.getType()));
       }
     }
   }
 
 
   markOverdefined(&I);
 }
 
 // Handle ICmpInst instruction.
 void SCCPSolver::visitCmpInst(CmpInst &I) {
   LatticeVal V1State = getValueState(I.getOperand(0));
   LatticeVal V2State = getValueState(I.getOperand(1));
 
   LatticeVal &IV = ValueState[&I];
   if (IV.isOverdefined()) return;
 
   if (V1State.isConstant() && V2State.isConstant()) {
     Constant *C = ConstantExpr::getCompare(
         I.getPredicate(), V1State.getConstant(), V2State.getConstant());
-    if (isa<UndefValue>(C))
-      return;
     return markConstant(IV, &I, C);
   }
 
   // If operands are still unknown, wait for it to resolve.
   if (!V1State.isOverdefined() && !V2State.isOverdefined())
     return;
 
   markOverdefined(&I);
 }
 
-void SCCPSolver::visitExtractElementInst(ExtractElementInst &I) {
-  // TODO : SCCP does not handle vectors properly.
-  return markOverdefined(&I);
-}
-
-void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
-  // TODO : SCCP does not handle vectors properly.
-  return markOverdefined(&I);
-}
-
-void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) {
-  // TODO : SCCP does not handle vectors properly.
-  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) {
     assert(State.isConstant() && "Unknown state!");
     Operands.push_back(State.getConstant());
   }
 
   Constant *Ptr = Operands[0];
   auto Indices = makeArrayRef(Operands.begin() + 1, Operands.end());
   Constant *C =
       ConstantExpr::getGetElementPtr(I.getSourceElementType(), Ptr, Indices);
-  if (isa<UndefValue>(C))
-      return;
   markConstant(&I, C);
 }
 
 void SCCPSolver::visitStoreInst(StoreInst &SI) {
   // If this store is of a struct, ignore it.
   if (SI.getOperand(0)->getType()->isStructTy())
     return;
 
void SCCPSolver::visitLoadInst(LoadInst &I) {
   if (IV.isOverdefined()) return;
 
   if (!PtrVal.isConstant() || I.isVolatile())
     return markOverdefined(IV, &I);
 
   Constant *Ptr = PtrVal.getConstant();
 
   // load null is undefined.
+  // XXXdavide: should we constant fold this one?
   if (isa<ConstantPointerNull>(Ptr) && I.getPointerAddressSpace() == 0)
     return;
 
   // Transform load (constant global) into the value loaded.
   if (auto *GV = dyn_cast<GlobalVariable>(Ptr)) {
     if (!TrackedGlobals.empty()) {
       // If we are tracking this global, merge in the known value for it.
       DenseMap<GlobalVariable*, LatticeVal>::iterator It =
         TrackedGlobals.find(GV);
       if (It != TrackedGlobals.end()) {
         mergeInValue(IV, &I, It->second);
         return;
       }
     }
   }
 
   // Transform load from a constant into a constant if possible.
-  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL)) {
-    if (isa<UndefValue>(C))
-      return;
+  if (Constant *C = ConstantFoldLoadFromConstPtr(Ptr, I.getType(), DL))
     return markConstant(IV, &I, C);
-  }
 
   // Otherwise we cannot say for certain what value this load will produce.
   // Bail out.
   markOverdefined(IV, &I);
 }
 
 void SCCPSolver::visitCallSite(CallSite CS) {
   Function *F = CS.getCalledFunction();
if (F && F->isDeclaration() && !I->getType()->isStructTy() &&
         Operands.push_back(State.getConstant());
       }
 
       if (getValueState(I).isOverdefined())
         return;
 
       // If we can constant fold this, mark the result of the call as a
       // constant.
-      if (Constant *C = ConstantFoldCall(F, Operands, TLI)) {
-        // call -> undef.
-        if (isa<UndefValue>(C))
-          return;
+      if (Constant *C = ConstantFoldCall(F, Operands, TLI))
         return markConstant(I, C);
-      }
-    }
 
     // Otherwise, we don't know anything about this call, mark it overdefined.
     return markAnythingOverdefined(I);
   }
 
   // If this is a local function that doesn't have its address taken, mark its
   // entry block executable and merge in the actual arguments to the call into
   // the formal arguments of the function.
while (!BBWorkList.empty()) {
 
       // Notify all instructions in this basic block that they are newly
       // executable.
       visit(BB);
     }
   }
 }
 
-/// ResolvedUndefsIn - While solving the dataflow for a function, we assume
-/// that branches on undef values cannot reach any of their successors.
-/// However, this is not a safe assumption.  After we solve dataflow, this
-/// method should be use to handle this.  If this returns true, the solver
-/// should be rerun.
-///
-/// This method handles this by finding an unresolved branch and marking it one
-/// of the edges from the block as being feasible, even though the condition
-/// doesn't say it would otherwise be.  This allows SCCP to find the rest of the
-/// CFG and only slightly pessimizes the analysis results (by marking one,
-/// potentially infeasible, edge feasible).  This cannot usefully modify the
-/// constraints on the condition of the branch, as that would impact other users
-/// of the value.
-///
-/// This scan also checks for values that use undefs, whose results are actually
-/// defined.  For example, 'zext i8 undef to i32' should produce all zeros
-/// conservatively, as "(zext i8 X -> i32) & 0xFF00" must always return zero,
-/// even if X isn't defined.
-bool SCCPSolver::ResolvedUndefsIn(Function &F) {
-  for (BasicBlock &BB : F) {
-    if (!BBExecutable.count(&BB))
-      continue;
-
-    for (Instruction &I : BB) {
-      // Look for instructions which produce undef values.
-      if (I.getType()->isVoidTy()) continue;
-
-      if (auto *STy = dyn_cast<StructType>(I.getType())) {
-        // Only a few things that can be structs matter for undef.
-
-        // Tracked calls must never be marked overdefined in ResolvedUndefsIn.
-        if (CallSite CS = CallSite(&I))
-          if (Function *F = CS.getCalledFunction())
-            if (MRVFunctionsTracked.count(F))
-              continue;
-
-        // 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())
-            markOverdefined(LV, &I);
-        }
-        continue;
-      }
-
-      LatticeVal &LV = getValueState(&I);
-      if (!LV.isUnknown()) continue;
-
-      // extractvalue is safe; check here because the argument is a struct.
-      if (isa<ExtractValueInst>(I))
-        continue;
-
-      // Compute the operand LatticeVals, for convenience below.
-      // Anything taking a struct is conservatively assumed to require
-      // overdefined markings.
-      if (I.getOperand(0)->getType()->isStructTy()) {
-        markOverdefined(&I);
-        return true;
-      }
-      LatticeVal Op0LV = getValueState(I.getOperand(0));
-      LatticeVal Op1LV;
-      if (I.getNumOperands() == 2) {
-        if (I.getOperand(1)->getType()->isStructTy()) {
-          markOverdefined(&I);
-          return true;
-        }
-
-        Op1LV = getValueState(I.getOperand(1));
-      }
-      // If this is an instructions whose result is defined even if the input is
-      // not fully defined, propagate the information.
-      Type *ITy = I.getType();
-      switch (I.getOpcode()) {
-      case Instruction::Add:
-      case Instruction::Sub:
-      case Instruction::Trunc:
-      case Instruction::FPTrunc:
-      case Instruction::BitCast:
-        break; // Any undef -> undef
-      case Instruction::FSub:
-      case Instruction::FAdd:
-      case Instruction::FMul:
-      case Instruction::FDiv:
-      case Instruction::FRem:
-        // Floating-point binary operation: be conservative.
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          markForcedConstant(&I, Constant::getNullValue(ITy));
-        else
-          markOverdefined(&I);
-        return true;
-      case Instruction::ZExt:
-      case Instruction::SExt:
-      case Instruction::FPToUI:
-      case Instruction::FPToSI:
-      case Instruction::FPExt:
-      case Instruction::PtrToInt:
-      case Instruction::IntToPtr:
-      case Instruction::SIToFP:
-      case Instruction::UIToFP:
-        // undef -> 0; some outputs are impossible
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::Mul:
-      case Instruction::And:
-        // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          break;
-        // undef * X -> 0.   X could be zero.
-        // undef & X -> 0.   X could be zero.
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-
-      case Instruction::Or:
-        // Both operands undef -> undef
-        if (Op0LV.isUnknown() && Op1LV.isUnknown())
-          break;
-        // undef | X -> -1.   X could be -1.
-        markForcedConstant(&I, Constant::getAllOnesValue(ITy));
-        return true;
-
-      case Instruction::Xor:
-        // undef ^ undef -> 0; strictly speaking, this is not strictly
-        // necessary, but we try to be nice to people who expect this
-        // behavior in simple cases
-        if (Op0LV.isUnknown() && Op1LV.isUnknown()) {
-          markForcedConstant(&I, Constant::getNullValue(ITy));
-          return true;
-        }
-        // undef ^ X -> undef
-        break;
-
-      case Instruction::SDiv:
-      case Instruction::UDiv:
-      case Instruction::SRem:
-      case Instruction::URem:
-        // X / undef -> undef.  No change.
-        // X % undef -> undef.  No change.
-        if (Op1LV.isUnknown()) break;
-
-        // X / 0 -> undef.  No change.
-        // X % 0 -> undef.  No change.
-        if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())
-          break;
-
-        // undef / X -> 0.   X could be maxint.
-        // undef % X -> 0.   X could be 1.
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-
-      case Instruction::AShr:
-        // X >>a undef -> undef.
-        if (Op1LV.isUnknown()) break;
-
-        // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
-
-        // undef >>a X -> 0
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::LShr:
-      case Instruction::Shl:
-        // X << undef -> undef.
-        // X >> undef -> undef.
-        if (Op1LV.isUnknown()) break;
-
-        // Shifting by the bitwidth or more is undefined.
-        if (Op1LV.isConstant()) {
-          if (auto *ShiftAmt = Op1LV.getConstantInt())
-            if (ShiftAmt->getLimitedValue() >=
-                ShiftAmt->getType()->getScalarSizeInBits())
-              break;
-        }
-
-        // undef << X -> 0
-        // undef >> X -> 0
-        markForcedConstant(&I, Constant::getNullValue(ITy));
-        return true;
-      case Instruction::Select:
-        Op1LV = getValueState(I.getOperand(1));
-        // undef ? X : Y  -> X or Y.  There could be commonality between X/Y.
-        if (Op0LV.isUnknown()) {
-          if (!Op1LV.isConstant())  // Pick the constant one if there is any.
-            Op1LV = getValueState(I.getOperand(2));
-        } else if (Op1LV.isUnknown()) {
-          // c ? undef : undef -> undef.  No change.
-          Op1LV = getValueState(I.getOperand(2));
-          if (Op1LV.isUnknown())
-            break;
-          // Otherwise, c ? undef : x -> x.
-        } else {
-          // Leave Op1LV as Operand(1)'s LatticeValue.
-        }
-
-        if (Op1LV.isConstant())
-          markForcedConstant(&I, Op1LV.getConstant());
-        else
-          markOverdefined(&I);
-        return true;
-      case Instruction::Load:
-        // A load here means one of two things: a load of undef from a global,
-        // a load from an unknown pointer.  Either way, having it return undef
-        // is okay.
-        break;
-      case Instruction::ICmp:
-        // X == undef -> undef.  Other comparisons get more complicated.
-        if (cast<ICmpInst>(&I)->isEquality())
-          break;
-        markOverdefined(&I);
-        return true;
-      case Instruction::Call:
-      case Instruction::Invoke: {
-        // 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 (Function *F = CallSite(&I).getCalledFunction())
-          if (TrackedRetVals.count(F))
-            break;
-
-        // If the call is constant-foldable, we mark it overdefined because
-        // we do not know what return values are valid.
-        markOverdefined(&I);
-        return true;
-      }
-      default:
-        // If we don't know what should happen here, conservatively mark it
-        // overdefined.
-        markOverdefined(&I);
-        return true;
-      }
-    }
-
-    // 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.
-    TerminatorInst *TI = BB.getTerminator();
-    if (auto *BI = dyn_cast<BranchInst>(TI)) {
-      if (!BI->isConditional()) continue;
-      if (!getValueState(BI->getCondition()).isUnknown())
-        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;
-      }
-
-      // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Handle this by forcing the input value to the
-      // branch to false.
-      markForcedConstant(BI->getCondition(),
-                         ConstantInt::getFalse(TI->getContext()));
-      return true;
-    }
-
-    if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-      if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
-        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;
-      }
-
-      markForcedConstant(SI->getCondition(), SI->case_begin().getCaseValue());
-      return true;
-    }
-  }
-
-  return false;
-}
-
 static bool tryToReplaceWithConstant(SCCPSolver &Solver, Value *V) {
   Constant *Const = nullptr;
   if (V->getType()->isStructTy()) {
     std::vector<LatticeVal> IVs = Solver.getStructLatticeValueFor(V);
     if (any_of(IVs, [](const LatticeVal &LV) { return LV.isOverdefined(); }))
       return false;
     std::vector<Constant *> ConstVals;
     auto *ST = dyn_cast<StructType>(V->getType());
static bool runSCCP(Function &F, const DataLayout &DL,
 
   // Mark the first block of the function as being executable.
   Solver.MarkBlockExecutable(&F.front());
 
   // Mark all arguments to the function as being overdefined.
   for (Argument &AI : F.args())
     Solver.markAnythingOverdefined(&AI);
 
-  // Solve for constants.
-  bool ResolvedUndefs = true;
-  while (ResolvedUndefs) {
-    Solver.Solve();
-    DEBUG(dbgs() << "RESOLVING UNDEFs\n");
-    ResolvedUndefs = Solver.ResolvedUndefsIn(F);
-  }
-
   bool MadeChanges = false;
 
   // If we decided that there are basic blocks that are dead in this function,
   // delete their contents now.  Note that we cannot actually delete the blocks,
   // as we cannot modify the CFG of the function.
 
   for (BasicBlock &BB : F) {
     if (!Solver.isBlockExecutable(&BB)) {
static bool runIPSCCP(Module &M, const DataLayout &DL,
 
   // Loop over global variables.  We inform the solver about any internal global
   // variables that do not have their 'addresses taken'.  If they don't have
   // their addresses taken, we can propagate constants through them.
   for (GlobalVariable &G : M.globals())
     if (!G.isConstant() && G.hasLocalLinkage() && !AddressIsTaken(&G))
       Solver.TrackValueOfGlobalVariable(&G);
 
-  // Solve for constants.
-  bool ResolvedUndefs = true;
-  while (ResolvedUndefs) {
-    Solver.Solve();
 
-    DEBUG(dbgs() << "RESOLVING UNDEFS\n");
-    ResolvedUndefs = false;
-    for (Function &F : M)
-      ResolvedUndefs |= Solver.ResolvedUndefsIn(F);
-  }
-
   bool MadeChanges = false;
 
   // Iterate over all of the instructions in the module, replacing them with
   // constants if we have found them to be of constant values.
   //
   SmallVector<BasicBlock*, 512> BlocksToErase;
 
   for (Function &F : M) {
for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
 
         if (&*BB != &F.front())
           BlocksToErase.push_back(&*BB);
         continue;
       }
 
       for (BasicBlock::iterator BI = BB->begin(), E = BB->end(); BI != E; ) {
         Instruction *Inst = &*BI++;
+
+        // Fix branches to undef -> branches to false.
+        if (auto *BrInst = dyn_cast<BranchInst>(Inst)) {
+          if (!BrInst->isConditional())
+            continue;
+          auto *C = dyn_cast<Constant>(BrInst->getCondition());
+          if (!C || !isa<UndefValue>(C))
+            continue;
+          BrInst->setCondition(ConstantInt::getFalse(BrInst->getContext()));
+          Solver.MarkBlockExecutable(BrInst->getSuccessor(1));
+        }
+
+        // Fix switches on undef -> switch on the first constant.
+        if (auto *SI = dyn_cast<SwitchInst>(Inst)) {
+          if (!SI->getNumCases())
+            continue;
+          auto *C = dyn_cast<Constant>(SI->getCondition());
+          if (!C || !isa<UndefValue>(C))
+            continue;
+          SI->setCondition(SI->case_begin().getCaseValue());
+          Solver.MarkBlockExecutable(SI->case_begin().getCaseSuccessor());
+        }
+
         if (Inst->getType()->isVoidTy())
           continue;
         if (tryToReplaceWithConstant(Solver, Inst)) {
           if (!isa<CallInst>(Inst) && !isa<TerminatorInst>(Inst))
             Inst->eraseFromParent();
           // Hey, we just changed something!
           MadeChanges = true;
           ++IPNumInstRemoved;
for (unsigned i = 0, e = BlocksToErase.size(); i != e; ++i) {
         // will be deleted. Step past all adjacent uses from the same user.
         auto *I = dyn_cast<Instruction>(*UI);
         do { ++UI; } while (UI != UE && *UI == I);
 
         // Ignore blockaddress users; BasicBlock's dtor will handle them.
         if (!I) continue;
 
         bool Folded = ConstantFoldTerminator(I->getParent());
-        if (!Folded) {
-          // The constant folder may not have been able to fold the terminator
-          // if this is a branch or switch on undef.  Fold it manually as a
-          // branch to the first successor.
-#ifndef NDEBUG
-          if (auto *BI = dyn_cast<BranchInst>(I)) {
-            assert(BI->isConditional() && isa<UndefValue>(BI->getCondition()) &&
-                   "Branch should be foldable!");
-          } else if (auto *SI = dyn_cast<SwitchInst>(I)) {
-            assert(isa<UndefValue>(SI->getCondition()) && "Switch should fold");
-          } else {
-            llvm_unreachable("Didn't fold away reference to block!");
-          }
-#endif
-
-          // Make this an uncond branch to the first successor.
-          TerminatorInst *TI = I->getParent()->getTerminator();
-          BranchInst::Create(TI->getSuccessor(0), TI);
-
-          // Remove entries in successor phi nodes to remove edges.
-          for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
-            TI->getSuccessor(i)->removePredecessor(TI->getParent());
-
-          // Remove the old terminator.
-          TI->eraseFromParent();
-        }
+        assert(Folded && "The terminator should've been folded");
       }
 
       // Finally, delete the basic block.
       F.getBasicBlockList().erase(DeadBB);
     }
     BlocksToErase.clear();
   }
 

test/Transforms/IPConstantProp/PR16052.ll

 ; RUN: opt < %s -S -ipsccp | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i64 @fn2() {
 entry:
   %conv = sext i32 undef to i64
   %div = sdiv i64 8, %conv
   %call2 = call i64 @fn1(i64 %div)
   ret i64 %call2
 }
 
 ; CHECK-DAG: define i64 @fn2(
 ; CHECK: %[[CALL:.*]] = call i64 @fn1(i64 undef)
+; CHECK-NEXT: ret i64 undef
 
 define internal i64 @fn1(i64 %p1) {
 entry:
   %tobool = icmp ne i64 %p1, 0
   %cond = select i1 %tobool, i64 %p1, i64 %p1
   ret i64 %cond
 }
 
 ; CHECK-DAG: define internal i64 @fn1(
-; CHECK: %[[SEL:.*]] = select i1 undef, i64 undef, i64 undef
-; CHECK: ret i64 %[[SEL]]
+; CHECK: ret i64 undef

test/Transforms/IPConstantProp/PR26044.ll

 define internal i32 @fn1(i32 %p1) {
 entry:
   %tobool = icmp ne i32 %p1, 0
   %cond = select i1 %tobool, i32 %p1, i32 %p1
   ret i32 %cond
 }
 
 ; CHECK-LABEL: define void @fn2(
-; CHECK: call i32 @fn1(i32 undef)
+; CHECK: call i32 @fn1(i32 %0)
 
 ; CHECK-LABEL: define internal i32 @fn1(
-; CHECK:%[[COND:.*]] = select i1 undef, i32 undef, i32 undef
+; CHECK:%[[COND:.*]] = select i1 %tobool, i32 %p1, i32 %p1
 ; CHECK: ret i32 %[[COND]]

test/Transforms/SCCP/undef-resolve.ll

 ; icmp eq with undef simplifies to undef
 define i1 @test8() {
   %t = icmp eq i32 undef, -1
   ret i1 %t
 ; CHECK-LABEL: @test8(
 ; CHECK: ret i1 undef
 }
 
-; Make sure we don't conclude that relational comparisons simplify to undef
+; Make sure we constant-fold to false
 define i1 @test9() {
   %t = icmp ugt i32 undef, -1
   ret i1 %t
 ; CHECK-LABEL: @test9(
-; CHECK: icmp ugt
+; CHECK: ret i1 false
 }
 
 ; Make sure we handle extractvalue
 define i64 @test10() { 
 entry:
   %e = extractvalue { i64, i64 } undef, 1
   ret i64 %e
 ; CHECK-LABEL: @test10(