Index: llvm/lib/Bitcode/Reader/BitcodeReader.cpp
===================================================================
--- llvm/lib/Bitcode/Reader/BitcodeReader.cpp
+++ llvm/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -94,6 +94,10 @@
     cl::desc(
         "Print the global id for each value when reading the module summary"));
 
+static cl::opt<bool> ExpandConstantExprs(
+    "expand-constant-exprs", cl::init(false), cl::Hidden,
+    cl::desc("Expand constant expressions for testing purposes"));
+
 namespace {
 
 enum {
@@ -473,6 +477,81 @@
 
 namespace {
 
+/// This represents a constant expression or constant aggregate using a custom
+/// structure internal to the bitcode reader. Later, this structure will be
+/// expanded by materializeValue() either into a constant expression/aggregate,
+/// or into an instruction sequence at the point of use. This allows us to
+/// upgrade bitcode using constant expressions even if this kind of constant
+/// expression is no longer supported.
+class BitcodeConstant final : public Value,
+                              TrailingObjects<BitcodeConstant, unsigned> {
+  friend TrailingObjects;
+
+  // Value subclass ID: Pick largest possible value to avoid any clashes.
+  static constexpr uint8_t SubclassID = 255;
+
+public:
+  // Opcodes used for constant structs, arrays and vector. Pick the largest
+  // possible values for these to avoid clashes with instruction opcodes.
+  static constexpr uint8_t ConstantStructOpcode = 255;
+  static constexpr uint8_t ConstantArrayOpcode = 254;
+  static constexpr uint8_t ConstantVectorOpcode = 253;
+
+  // Separate struct to make passing different number of parameters to
+  // BitcodeConstant::create() more convenient.
+  struct ExtraInfo {
+    uint8_t Opcode;
+    uint8_t Flags;
+    unsigned InRangeIndex;
+    Type *SrcElemTy;
+
+    ExtraInfo(uint8_t Opcode, uint8_t Flags = 0,
+              Optional<unsigned> InRangeIndex = None,
+              Type *SrcElemTy = nullptr)
+        : Opcode(Opcode), Flags(Flags),
+          InRangeIndex(InRangeIndex.getValueOr(-1)), SrcElemTy(SrcElemTy) {}
+  };
+
+  uint8_t Opcode;
+  uint8_t Flags;
+  unsigned NumOperands;
+  unsigned InRangeIndex; // GEP inrange index (or -1 if not inrange)
+  Type *SrcElemTy;       // GEP source element type.
+
+private:
+  BitcodeConstant(Type *Ty, const ExtraInfo &Info, ArrayRef<unsigned> OpIDs)
+      : Value(Ty, SubclassID), Opcode(Info.Opcode), Flags(Info.Flags),
+        NumOperands(OpIDs.size()), InRangeIndex(Info.InRangeIndex),
+        SrcElemTy(Info.SrcElemTy) {
+    std::uninitialized_copy(OpIDs.begin(), OpIDs.end(),
+                            getTrailingObjects<unsigned>());
+  }
+
+  BitcodeConstant &operator=(const BitcodeConstant &) = delete;
+
+public:
+  static BitcodeConstant *create(BumpPtrAllocator &A, Type *Ty,
+                                 const ExtraInfo &Info,
+                                 ArrayRef<unsigned> OpIDs) {
+    void *Mem = A.Allocate(totalSizeToAlloc<unsigned>(OpIDs.size()),
+                           alignof(BitcodeConstant));
+    return new (Mem) BitcodeConstant(Ty, Info, OpIDs);
+  }
+
+  static bool classof(const Value *V) { return V->getValueID() == SubclassID; }
+
+  ArrayRef<unsigned> getOperandIDs() const {
+    return makeArrayRef(getTrailingObjects<unsigned>(), NumOperands);
+  }
+
+  Optional<unsigned> getInRangeIndex() const {
+    assert(Opcode == Instruction::GetElementPtr);
+    if (InRangeIndex == (unsigned)-1)
+      return None;
+    return InRangeIndex;
+  }
+};
+
 class BitcodeReader : public BitcodeReaderBase, public GVMaterializer {
   LLVMContext &Context;
   Module *TheModule = nullptr;
@@ -499,6 +578,10 @@
   /// for the given pair of Type and contained type ID.
   DenseMap<std::pair<Type *, unsigned>, unsigned> VirtualTypeIDs;
   DenseMap<Function *, unsigned> FunctionTypeIDs;
+  /// Allocator for BitcodeConstants. This should come before ValueList,
+  /// because the ValueList might hold ValueHandles to these constants, so
+  /// ValueList must be destroyed before Alloc.
+  BumpPtrAllocator Alloc;
   BitcodeReaderValueList ValueList;
   Optional<MetadataLoader> MDLoader;
   std::vector<Comdat *> ComdatList;
@@ -618,10 +701,24 @@
   unsigned getContainedTypeID(unsigned ID, unsigned Idx = 0);
   unsigned getVirtualTypeID(Type *Ty, ArrayRef<unsigned> ContainedTypeIDs = {});
 
-  Value *getFnValueByID(unsigned ID, Type *Ty, unsigned TyID) {
+  Expected<Value *> materializeValue(unsigned ValID, BasicBlock *InsertBB);
+  Expected<Constant *> getValueForInitializer(unsigned ID);
+
+  Value *getFnValueByID(unsigned ID, Type *Ty, unsigned TyID,
+                        BasicBlock *ConstExprInsertBB) {
     if (Ty && Ty->isMetadataTy())
       return MetadataAsValue::get(Ty->getContext(), getFnMetadataByID(ID));
-    return ValueList.getValueFwdRef(ID, Ty, TyID);
+    Value *V = ValueList.getValueFwdRef(ID, Ty, TyID);
+    if (!V)
+      return nullptr;
+
+    Expected<Value *> MaybeV = materializeValue(ID, ConstExprInsertBB);
+    if (!MaybeV) {
+      // TODO: We might want to propagate the precise error message here.
+      consumeError(MaybeV.takeError());
+      return nullptr;
+    }
+    return MaybeV.get();
   }
 
   Metadata *getFnMetadataByID(unsigned ID) {
@@ -643,7 +740,8 @@
   /// Increment Slot past the number of slots used in the record. Return true on
   /// failure.
   bool getValueTypePair(const SmallVectorImpl<uint64_t> &Record, unsigned &Slot,
-                        unsigned InstNum, Value *&ResVal, unsigned &TypeID) {
+                        unsigned InstNum, Value *&ResVal, unsigned &TypeID,
+                        BasicBlock *ConstExprInsertBB) {
     if (Slot == Record.size()) return true;
     unsigned ValNo = (unsigned)Record[Slot++];
     // Adjust the ValNo, if it was encoded relative to the InstNum.
@@ -653,7 +751,7 @@
       // If this is not a forward reference, just return the value we already
       // have.
       TypeID = ValueList.getTypeID(ValNo);
-      ResVal = getFnValueByID(ValNo, nullptr, TypeID);
+      ResVal = getFnValueByID(ValNo, nullptr, TypeID, ConstExprInsertBB);
       assert((!ResVal || ResVal->getType() == getTypeByID(TypeID)) &&
              "Incorrect type ID stored for value");
       return ResVal == nullptr;
@@ -662,7 +760,8 @@
       return true;
 
     TypeID = (unsigned)Record[Slot++];
-    ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID);
+    ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID,
+                            ConstExprInsertBB);
     return ResVal == nullptr;
   }
 
@@ -670,8 +769,9 @@
   /// past the number of slots used by the value in the record. Return true if
   /// there is an error.
   bool popValue(const SmallVectorImpl<uint64_t> &Record, unsigned &Slot,
-                unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal) {
-    if (getValue(Record, Slot, InstNum, Ty, TyID, ResVal))
+                unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal,
+                BasicBlock *ConstExprInsertBB) {
+    if (getValue(Record, Slot, InstNum, Ty, TyID, ResVal, ConstExprInsertBB))
       return true;
     // All values currently take a single record slot.
     ++Slot;
@@ -680,32 +780,35 @@
 
   /// Like popValue, but does not increment the Slot number.
   bool getValue(const SmallVectorImpl<uint64_t> &Record, unsigned Slot,
-                unsigned InstNum, Type *Ty, unsigned TyID,  Value *&ResVal) {
-    ResVal = getValue(Record, Slot, InstNum, Ty, TyID);
+                unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal,
+                BasicBlock *ConstExprInsertBB) {
+    ResVal = getValue(Record, Slot, InstNum, Ty, TyID, ConstExprInsertBB);
     return ResVal == nullptr;
   }
 
   /// Version of getValue that returns ResVal directly, or 0 if there is an
   /// error.
   Value *getValue(const SmallVectorImpl<uint64_t> &Record, unsigned Slot,
-                  unsigned InstNum, Type *Ty, unsigned TyID) {
+                  unsigned InstNum, Type *Ty, unsigned TyID,
+                  BasicBlock *ConstExprInsertBB) {
     if (Slot == Record.size()) return nullptr;
     unsigned ValNo = (unsigned)Record[Slot];
     // Adjust the ValNo, if it was encoded relative to the InstNum.
     if (UseRelativeIDs)
       ValNo = InstNum - ValNo;
-    return getFnValueByID(ValNo, Ty, TyID);
+    return getFnValueByID(ValNo, Ty, TyID, ConstExprInsertBB);
   }
 
   /// Like getValue, but decodes signed VBRs.
   Value *getValueSigned(const SmallVectorImpl<uint64_t> &Record, unsigned Slot,
-                        unsigned InstNum, Type *Ty, unsigned TyID) {
+                        unsigned InstNum, Type *Ty, unsigned TyID,
+                        BasicBlock *ConstExprInsertBB) {
     if (Slot == Record.size()) return nullptr;
     unsigned ValNo = (unsigned)decodeSignRotatedValue(Record[Slot]);
     // Adjust the ValNo, if it was encoded relative to the InstNum.
     if (UseRelativeIDs)
       ValNo = InstNum - ValNo;
-    return getFnValueByID(ValNo, Ty, TyID);
+    return getFnValueByID(ValNo, Ty, TyID, ConstExprInsertBB);
   }
 
   /// Upgrades old-style typeless byval/sret/inalloca attributes by adding the
@@ -1273,6 +1376,202 @@
   return TypeID;
 }
 
+static bool isConstExprSupported(uint8_t Opcode) {
+  return !ExpandConstantExprs;
+}
+
+Expected<Value *> BitcodeReader::materializeValue(unsigned StartValID,
+                                                  BasicBlock *InsertBB) {
+  // Quickly handle the case where there is no BitcodeConstant to resolve.
+  if (StartValID < ValueList.size() && ValueList[StartValID] &&
+      !isa<BitcodeConstant>(ValueList[StartValID]))
+    return ValueList[StartValID];
+
+  SmallDenseMap<unsigned, Value *> MaterializedValues;
+  SmallVector<unsigned> Worklist;
+  Worklist.push_back(StartValID);
+  while (!Worklist.empty()) {
+    unsigned ValID = Worklist.back();
+    if (MaterializedValues.count(ValID)) {
+      // Duplicate expression that was already handled.
+      Worklist.pop_back();
+      continue;
+    }
+
+    if (ValID >= ValueList.size() || !ValueList[ValID])
+      return error("Invalid value ID");
+
+    Value *V = ValueList[ValID];
+    auto *BC = dyn_cast<BitcodeConstant>(V);
+    if (!BC) {
+      MaterializedValues.insert({ValID, V});
+      Worklist.pop_back();
+      continue;
+    }
+
+    SmallVector<Value *> Ops;
+    for (unsigned OpID : BC->getOperandIDs()) {
+      auto It = MaterializedValues.find(OpID);
+      if (It == MaterializedValues.end()) {
+        Worklist.push_back(OpID);
+        break;
+      }
+      Ops.push_back(It->second);
+    }
+
+    // Some expressions have not been resolved yet, handle them first and then
+    // revisit this one.
+    if (Ops.size() != BC->getOperandIDs().size())
+      continue;
+
+    SmallVector<Constant *> ConstOps;
+    for (Value *Op : Ops)
+      if (auto *C = dyn_cast<Constant>(Op))
+        ConstOps.push_back(C);
+
+    // Materialize as constant expression is possible.
+    if (isConstExprSupported(BC->Opcode) && ConstOps.size() == Ops.size()) {
+      Constant *C;
+      if (Instruction::isCast(BC->Opcode)) {
+        C = ConstantExpr::getCast(BC->Opcode, ConstOps[0], BC->getType());
+      } else if (Instruction::isUnaryOp(BC->Opcode)) {
+        C = ConstantExpr::get(BC->Opcode, ConstOps[0], BC->Flags);
+      } else if (Instruction::isBinaryOp(BC->Opcode)) {
+        C = ConstantExpr::get(BC->Opcode, ConstOps[0], ConstOps[1], BC->Flags);
+      } else {
+        switch (BC->Opcode) {
+        case BitcodeConstant::ConstantStructOpcode:
+          C = ConstantStruct::get(cast<StructType>(BC->getType()), ConstOps);
+          break;
+        case BitcodeConstant::ConstantArrayOpcode:
+          C = ConstantArray::get(cast<ArrayType>(BC->getType()), ConstOps);
+          break;
+        case BitcodeConstant::ConstantVectorOpcode:
+          C = ConstantVector::get(ConstOps);
+          break;
+        case Instruction::ICmp:
+        case Instruction::FCmp:
+          C = ConstantExpr::getCompare(BC->Flags, ConstOps[0], ConstOps[1]);
+          break;
+        case Instruction::GetElementPtr:
+          C = ConstantExpr::getGetElementPtr(
+              BC->SrcElemTy, ConstOps[0], makeArrayRef(ConstOps).drop_front(),
+              BC->Flags, BC->getInRangeIndex());
+          break;
+        case Instruction::Select:
+          C = ConstantExpr::getSelect(ConstOps[0], ConstOps[1], ConstOps[2]);
+          break;
+        case Instruction::ExtractElement:
+          C = ConstantExpr::getExtractElement(ConstOps[0], ConstOps[1]);
+          break;
+        case Instruction::InsertElement:
+          C = ConstantExpr::getInsertElement(ConstOps[0], ConstOps[1],
+                                             ConstOps[2]);
+          break;
+        case Instruction::ShuffleVector: {
+          SmallVector<int, 16> Mask;
+          ShuffleVectorInst::getShuffleMask(ConstOps[2], Mask);
+          C = ConstantExpr::getShuffleVector(ConstOps[0], ConstOps[1], Mask);
+          break;
+        }
+        default:
+          llvm_unreachable("Unhandled bitcode constant");
+        }
+      }
+
+      // Cache resolved constant.
+      ValueList.replaceValueWithoutRAUW(ValID, C);
+      MaterializedValues.insert({ValID, C});
+      Worklist.pop_back();
+      continue;
+    }
+
+    if (!InsertBB)
+      return error("Value referenced by initializer is not a constant");
+
+    // Materialize as instructions if necessary.
+    Instruction *I;
+    if (Instruction::isCast(BC->Opcode)) {
+      I = CastInst::Create((Instruction::CastOps)BC->Opcode, Ops[0],
+                           BC->getType(), "constexpr", InsertBB);
+    } else if (Instruction::isUnaryOp(BC->Opcode)) {
+      I = UnaryOperator::Create((Instruction::UnaryOps)BC->Opcode, Ops[0],
+                                "constexpr", InsertBB);
+    } else if (Instruction::isBinaryOp(BC->Opcode)) {
+      I = BinaryOperator::Create((Instruction::BinaryOps)BC->Opcode, Ops[0],
+                                 Ops[1], "constexpr", InsertBB);
+      if (isa<OverflowingBinaryOperator>(I)) {
+        if (BC->Flags & OverflowingBinaryOperator::NoSignedWrap)
+          I->setHasNoSignedWrap();
+        if (BC->Flags & OverflowingBinaryOperator::NoUnsignedWrap)
+          I->setHasNoUnsignedWrap();
+      }
+      if (isa<PossiblyExactOperator>(I) &&
+          (BC->Flags & PossiblyExactOperator::IsExact))
+        I->setIsExact();
+    } else {
+      switch (BC->Opcode) {
+      case BitcodeConstant::ConstantStructOpcode:
+      case BitcodeConstant::ConstantArrayOpcode:
+      case BitcodeConstant::ConstantVectorOpcode: {
+        Type *IdxTy = Type::getInt32Ty(BC->getContext());
+        Value *V = PoisonValue::get(BC->getType());
+        for (auto Pair : enumerate(Ops)) {
+          Value *Idx = ConstantInt::get(IdxTy, Pair.index());
+          V = InsertElementInst::Create(V, Pair.value(), Idx, "constexpr.ins",
+                                        InsertBB);
+        }
+        I = cast<Instruction>(V);
+        break;
+      }
+      case Instruction::ICmp:
+      case Instruction::FCmp:
+        I = CmpInst::Create((Instruction::OtherOps)BC->Opcode,
+                            (CmpInst::Predicate)BC->Flags, Ops[0], Ops[1],
+                            "constexpr", InsertBB);
+        break;
+      case Instruction::GetElementPtr:
+        I = GetElementPtrInst::Create(BC->SrcElemTy, Ops[0],
+                                      makeArrayRef(Ops).drop_front(),
+                                      "constexpr", InsertBB);
+        if (BC->Flags)
+          cast<GetElementPtrInst>(I)->setIsInBounds();
+        break;
+      case Instruction::Select:
+        I = SelectInst::Create(Ops[0], Ops[1], Ops[2], "constexpr", InsertBB);
+        break;
+      case Instruction::ExtractElement:
+        I = ExtractElementInst::Create(Ops[0], Ops[1], "constexpr", InsertBB);
+        break;
+      case Instruction::InsertElement:
+        I = InsertElementInst::Create(Ops[0], Ops[1], Ops[2], "constexpr",
+                                      InsertBB);
+        break;
+      case Instruction::ShuffleVector:
+        I = new ShuffleVectorInst(Ops[0], Ops[1], Ops[2], "constexpr",
+                                  InsertBB);
+        break;
+      default:
+        llvm_unreachable("Unhandled bitcode constant");
+      }
+    }
+
+    MaterializedValues.insert({ValID, I});
+    Worklist.pop_back();
+  }
+
+  return MaterializedValues[StartValID];
+}
+
+Expected<Constant *> BitcodeReader::getValueForInitializer(unsigned ID) {
+  Expected<Value *> MaybeV = materializeValue(ID, /* InsertBB */ nullptr);
+  if (!MaybeV)
+    return MaybeV.takeError();
+
+  // Result must be Constant if InsertBB is nullptr.
+  return cast<Constant>(MaybeV.get());
+}
+
 StructType *BitcodeReader::createIdentifiedStructType(LLVMContext &Context,
                                                       StringRef Name) {
   auto *Ret = StructType::create(Context, Name);
@@ -2386,10 +2685,10 @@
       // Not ready to resolve this yet, it requires something later in the file.
       GlobalInits.push_back(GlobalInitWorklist.back());
     } else {
-      if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-        GlobalInitWorklist.back().first->setInitializer(C);
-      else
-        return error("Expected a constant");
+      Expected<Constant *> MaybeC = getValueForInitializer(ValID);
+      if (!MaybeC)
+        return MaybeC.takeError();
+      GlobalInitWorklist.back().first->setInitializer(MaybeC.get());
     }
     GlobalInitWorklist.pop_back();
   }
@@ -2399,9 +2698,10 @@
     if (ValID >= ValueList.size()) {
       IndirectSymbolInits.push_back(IndirectSymbolInitWorklist.back());
     } else {
-      Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]);
-      if (!C)
-        return error("Expected a constant");
+      Expected<Constant *> MaybeC = getValueForInitializer(ValID);
+      if (!MaybeC)
+        return MaybeC.takeError();
+      Constant *C = MaybeC.get();
       GlobalValue *GV = IndirectSymbolInitWorklist.back().first;
       if (auto *GA = dyn_cast<GlobalAlias>(GV)) {
         if (C->getType() != GV->getType())
@@ -2425,30 +2725,30 @@
     if (Info.PersonalityFn) {
       unsigned ValID = Info.PersonalityFn - 1;
       if (ValID < ValueList.size()) {
-        if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-          Info.F->setPersonalityFn(C);
-        else
-          return error("Expected a constant");
+        Expected<Constant *> MaybeC = getValueForInitializer(ValID);
+        if (!MaybeC)
+          return MaybeC.takeError();
+        Info.F->setPersonalityFn(MaybeC.get());
         Info.PersonalityFn = 0;
       }
     }
     if (Info.Prefix) {
       unsigned ValID = Info.Prefix - 1;
       if (ValID < ValueList.size()) {
-        if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-          Info.F->setPrefixData(C);
-        else
-          return error("Expected a constant");
+        Expected<Constant *> MaybeC = getValueForInitializer(ValID);
+        if (!MaybeC)
+          return MaybeC.takeError();
+        Info.F->setPrefixData(MaybeC.get());
         Info.Prefix = 0;
       }
     }
     if (Info.Prologue) {
       unsigned ValID = Info.Prologue - 1;
       if (ValID < ValueList.size()) {
-        if (Constant *C = dyn_cast_or_null<Constant>(ValueList[ValID]))
-          Info.F->setPrologueData(C);
-        else
-          return error("Expected a constant");
+        Expected<Constant *> MaybeC = getValueForInitializer(ValID);
+        if (!MaybeC)
+          return MaybeC.takeError();
+        Info.F->setPrologueData(MaybeC.get());
         Info.Prologue = 0;
       }
     }
@@ -2481,26 +2781,6 @@
   Type *CurElemTy = nullptr;
   unsigned NextCstNo = ValueList.size();
 
-  struct DelayedShufTy {
-    VectorType *OpTy;
-    unsigned OpTyID;
-    VectorType *RTy;
-    uint64_t Op0Idx;
-    uint64_t Op1Idx;
-    uint64_t Op2Idx;
-    unsigned CstNo;
-  };
-  std::vector<DelayedShufTy> DelayedShuffles;
-  struct DelayedSelTy {
-    Type *OpTy;
-    unsigned OpTyID;
-    uint64_t Op0Idx;
-    uint64_t Op1Idx;
-    uint64_t Op2Idx;
-    unsigned CstNo;
-  };
-  std::vector<DelayedSelTy> DelayedSelectors;
-
   while (true) {
     Expected<BitstreamEntry> MaybeEntry = Stream.advanceSkippingSubblocks();
     if (!MaybeEntry)
@@ -2512,68 +2792,8 @@
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
-      // Once all the constants have been read, go through and resolve forward
-      // references.
-      //
-      // We have to treat shuffles specially because they don't have three
-      // operands anymore.  We need to convert the shuffle mask into an array,
-      // and we can't convert a forward reference.
-      for (auto &DelayedShuffle : DelayedShuffles) {
-        VectorType *OpTy = DelayedShuffle.OpTy;
-        unsigned OpTyID = DelayedShuffle.OpTyID;
-        VectorType *RTy = DelayedShuffle.RTy;
-        uint64_t Op0Idx = DelayedShuffle.Op0Idx;
-        uint64_t Op1Idx = DelayedShuffle.Op1Idx;
-        uint64_t Op2Idx = DelayedShuffle.Op2Idx;
-        uint64_t CstNo = DelayedShuffle.CstNo;
-        Constant *Op0 = ValueList.getConstantFwdRef(Op0Idx, OpTy, OpTyID);
-        Constant *Op1 = ValueList.getConstantFwdRef(Op1Idx, OpTy, OpTyID);
-        Type *ShufTy =
-            VectorType::get(Type::getInt32Ty(Context), RTy->getElementCount());
-        Constant *Op2 = ValueList.getConstantFwdRef(
-            Op2Idx, ShufTy, getVirtualTypeID(ShufTy, Int32TyID));
-        if (!ShuffleVectorInst::isValidOperands(Op0, Op1, Op2))
-          return error("Invalid shufflevector operands");
-        SmallVector<int, 16> Mask;
-        ShuffleVectorInst::getShuffleMask(Op2, Mask);
-        Value *V = ConstantExpr::getShuffleVector(Op0, Op1, Mask);
-        if (Error Err = ValueList.assignValue(
-                CstNo, V,
-                getVirtualTypeID(V->getType(), getContainedTypeID(OpTyID))))
-          return Err;
-      }
-      for (auto &DelayedSelector : DelayedSelectors) {
-        Type *OpTy = DelayedSelector.OpTy;
-        unsigned OpTyID = DelayedSelector.OpTyID;
-        Type *SelectorTy = Type::getInt1Ty(Context);
-        unsigned SelectorTyID = getVirtualTypeID(SelectorTy);
-        uint64_t Op0Idx = DelayedSelector.Op0Idx;
-        uint64_t Op1Idx = DelayedSelector.Op1Idx;
-        uint64_t Op2Idx = DelayedSelector.Op2Idx;
-        uint64_t CstNo = DelayedSelector.CstNo;
-        Constant *Op1 = ValueList.getConstantFwdRef(Op1Idx, OpTy, OpTyID);
-        Constant *Op2 = ValueList.getConstantFwdRef(Op2Idx, OpTy, OpTyID);
-        // The selector might be an i1 or an <n x i1>
-        // Get the type from the ValueList before getting a forward ref.
-        if (VectorType *VTy = dyn_cast<VectorType>(OpTy)) {
-          Value *V = ValueList[Op0Idx];
-          assert(V);
-          if (SelectorTy != V->getType()) {
-            SelectorTy = VectorType::get(SelectorTy, VTy->getElementCount());
-            SelectorTyID = getVirtualTypeID(SelectorTy, SelectorTyID);
-          }
-        }
-        Constant *Op0 =
-            ValueList.getConstantFwdRef(Op0Idx, SelectorTy, SelectorTyID);
-        Value *V = ConstantExpr::getSelect(Op0, Op1, Op2);
-        if (Error Err = ValueList.assignValue(CstNo, V, OpTyID))
-          return Err;
-      }
-
       if (NextCstNo != ValueList.size())
         return error("Invalid constant reference");
-
-      ValueList.resolveConstantForwardRefs();
       return Error::success();
     case BitstreamEntry::Record:
       // The interesting case.
@@ -2664,28 +2884,19 @@
         return error("Invalid aggregate record");
 
       unsigned Size = Record.size();
-      SmallVector<Constant*, 16> Elts;
-
-      if (StructType *STy = dyn_cast<StructType>(CurTy)) {
-        for (unsigned i = 0; i != Size; ++i)
-          Elts.push_back(ValueList.getConstantFwdRef(
-              Record[i], STy->getElementType(i),
-              getContainedTypeID(CurTyID, i)));
-        V = ConstantStruct::get(STy, Elts);
-      } else if (ArrayType *ATy = dyn_cast<ArrayType>(CurTy)) {
-        Type *EltTy = ATy->getElementType();
-        unsigned EltTyID = getContainedTypeID(CurTyID);
-        for (unsigned i = 0; i != Size; ++i)
-          Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy,
-                                                     EltTyID));
-        V = ConstantArray::get(ATy, Elts);
-      } else if (VectorType *VTy = dyn_cast<VectorType>(CurTy)) {
-        Type *EltTy = VTy->getElementType();
-        unsigned EltTyID = getContainedTypeID(CurTyID);
-        for (unsigned i = 0; i != Size; ++i)
-          Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy,
-                                                     EltTyID));
-        V = ConstantVector::get(Elts);
+      SmallVector<unsigned, 16> Elts;
+      for (unsigned i = 0; i != Size; ++i)
+        Elts.push_back(Record[i]);
+
+      if (isa<StructType>(CurTy)) {
+        V = BitcodeConstant::create(
+            Alloc, CurTy, BitcodeConstant::ConstantStructOpcode, Elts);
+      } else if (isa<ArrayType>(CurTy)) {
+        V = BitcodeConstant::create(Alloc, CurTy,
+                                    BitcodeConstant::ConstantArrayOpcode, Elts);
+      } else if (isa<VectorType>(CurTy)) {
+        V = BitcodeConstant::create(
+            Alloc, CurTy, BitcodeConstant::ConstantVectorOpcode, Elts);
       } else {
         V = UndefValue::get(CurTy);
       }
@@ -2770,9 +2981,7 @@
       if (Opc < 0) {
         V = UndefValue::get(CurTy);  // Unknown unop.
       } else {
-        Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy, CurTyID);
-        unsigned Flags = 0;
-        V = ConstantExpr::get(Opc, LHS, Flags);
+        V = BitcodeConstant::create(Alloc, CurTy, Opc, (unsigned)Record[1]);
       }
       break;
     }
@@ -2783,9 +2992,7 @@
       if (Opc < 0) {
         V = UndefValue::get(CurTy);  // Unknown binop.
       } else {
-        Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy, CurTyID);
-        Constant *RHS = ValueList.getConstantFwdRef(Record[2], CurTy, CurTyID);
-        unsigned Flags = 0;
+        uint8_t Flags = 0;
         if (Record.size() >= 4) {
           if (Opc == Instruction::Add ||
               Opc == Instruction::Sub ||
@@ -2803,7 +3010,8 @@
               Flags |= SDivOperator::IsExact;
           }
         }
-        V = ConstantExpr::get(Opc, LHS, RHS, Flags);
+        V = BitcodeConstant::create(Alloc, CurTy, {(uint8_t)Opc, Flags},
+                                    {(unsigned)Record[1], (unsigned)Record[2]});
       }
       break;
     }
@@ -2818,9 +3026,7 @@
         Type *OpTy = getTypeByID(OpTyID);
         if (!OpTy)
           return error("Invalid cast constexpr record");
-        Constant *Op = ValueList.getConstantFwdRef(Record[2], OpTy, OpTyID);
-        V = UpgradeBitCastExpr(Opc, Op, CurTy);
-        if (!V) V = ConstantExpr::getCast(Opc, Op, CurTy);
+        V = BitcodeConstant::create(Alloc, CurTy, Opc, (unsigned)Record[2]);
       }
       break;
     }
@@ -2845,15 +3051,14 @@
       } else if (BitCode == bitc::CST_CODE_CE_INBOUNDS_GEP)
         InBounds = true;
 
-      SmallVector<Constant*, 16> Elts;
+      SmallVector<unsigned, 16> Elts;
       unsigned BaseTypeID = Record[OpNum];
       while (OpNum != Record.size()) {
         unsigned ElTyID = Record[OpNum++];
         Type *ElTy = getTypeByID(ElTyID);
         if (!ElTy)
           return error("Invalid getelementptr constexpr record");
-        Elts.push_back(ValueList.getConstantFwdRef(Record[OpNum++], ElTy,
-                                                   ElTyID));
+        Elts.push_back(Record[OpNum++]);
       }
 
       if (Elts.size() < 1)
@@ -2877,20 +3082,20 @@
         return error("Explicit gep operator type does not match pointee type "
                      "of pointer operand");
 
-      ArrayRef<Constant *> Indices(Elts.begin() + 1, Elts.end());
-      V = ConstantExpr::getGetElementPtr(PointeeType, Elts[0], Indices,
-                                         InBounds, InRangeIndex);
+      V = BitcodeConstant::create(
+          Alloc, CurTy,
+          {Instruction::GetElementPtr, InBounds, InRangeIndex, PointeeType},
+          Elts);
       break;
     }
     case bitc::CST_CODE_CE_SELECT: {  // CE_SELECT: [opval#, opval#, opval#]
       if (Record.size() < 3)
         return error("Invalid select constexpr record");
 
-      DelayedSelectors.push_back(
-          {CurTy, CurTyID, Record[0], Record[1], Record[2], NextCstNo});
-      (void)ValueList.getConstantFwdRef(NextCstNo, CurTy, CurTyID);
-      ++NextCstNo;
-      continue;
+      V = BitcodeConstant::create(
+          Alloc, CurTy, Instruction::Select,
+          {(unsigned)Record[0], (unsigned)Record[1], (unsigned)Record[2]});
+      break;
     }
     case bitc::CST_CODE_CE_EXTRACTELT
         : { // CE_EXTRACTELT: [opty, opval, opty, opval]
@@ -2901,22 +3106,19 @@
         dyn_cast_or_null<VectorType>(getTypeByID(OpTyID));
       if (!OpTy)
         return error("Invalid extractelement constexpr record");
-      Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy, OpTyID);
-      Constant *Op1 = nullptr;
+      unsigned IdxRecord;
       if (Record.size() == 4) {
         unsigned IdxTyID = Record[2];
         Type *IdxTy = getTypeByID(IdxTyID);
         if (!IdxTy)
           return error("Invalid extractelement constexpr record");
-        Op1 = ValueList.getConstantFwdRef(Record[3], IdxTy, IdxTyID);
+        IdxRecord = Record[3];
       } else {
         // Deprecated, but still needed to read old bitcode files.
-        Op1 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context),
-                                          Int32TyID);
+        IdxRecord = Record[2];
       }
-      if (!Op1)
-        return error("Invalid extractelement constexpr record");
-      V = ConstantExpr::getExtractElement(Op0, Op1);
+      V = BitcodeConstant::create(Alloc, CurTy, Instruction::ExtractElement,
+                                  {(unsigned)Record[1], IdxRecord});
       break;
     }
     case bitc::CST_CODE_CE_INSERTELT
@@ -2924,35 +3126,30 @@
       VectorType *OpTy = dyn_cast<VectorType>(CurTy);
       if (Record.size() < 3 || !OpTy)
         return error("Invalid insertelement constexpr record");
-      Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy, CurTyID);
-      Constant *Op1 = ValueList.getConstantFwdRef(Record[1],
-                                                  OpTy->getElementType(),
-                                                  getContainedTypeID(CurTyID));
-      Constant *Op2 = nullptr;
+      unsigned IdxRecord;
       if (Record.size() == 4) {
         unsigned IdxTyID = Record[2];
         Type *IdxTy = getTypeByID(IdxTyID);
         if (!IdxTy)
           return error("Invalid insertelement constexpr record");
-        Op2 = ValueList.getConstantFwdRef(Record[3], IdxTy, IdxTyID);
+        IdxRecord = Record[3];
       } else {
         // Deprecated, but still needed to read old bitcode files.
-        Op2 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context),
-                                          Int32TyID);
+        IdxRecord = Record[2];
       }
-      if (!Op2)
-        return error("Invalid insertelement constexpr record");
-      V = ConstantExpr::getInsertElement(Op0, Op1, Op2);
+      V = BitcodeConstant::create(
+          Alloc, CurTy, Instruction::InsertElement,
+          {(unsigned)Record[0], (unsigned)Record[1], IdxRecord});
       break;
     }
     case bitc::CST_CODE_CE_SHUFFLEVEC: { // CE_SHUFFLEVEC: [opval, opval, opval]
       VectorType *OpTy = dyn_cast<VectorType>(CurTy);
       if (Record.size() < 3 || !OpTy)
         return error("Invalid shufflevector constexpr record");
-      DelayedShuffles.push_back(
-          {OpTy, CurTyID, OpTy, Record[0], Record[1], Record[2], NextCstNo});
-      ++NextCstNo;
-      continue;
+      V = BitcodeConstant::create(
+          Alloc, CurTy, Instruction::ShuffleVector,
+          {(unsigned)Record[0], (unsigned)Record[1], (unsigned)Record[2]});
+      break;
     }
     case bitc::CST_CODE_CE_SHUFVEC_EX: { // [opty, opval, opval, opval]
       VectorType *RTy = dyn_cast<VectorType>(CurTy);
@@ -2960,10 +3157,10 @@
         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
       if (Record.size() < 4 || !RTy || !OpTy)
         return error("Invalid shufflevector constexpr record");
-      DelayedShuffles.push_back(
-          {OpTy, CurTyID, RTy, Record[1], Record[2], Record[3], NextCstNo});
-      ++NextCstNo;
-      continue;
+      V = BitcodeConstant::create(
+          Alloc, CurTy, Instruction::ShuffleVector,
+          {(unsigned)Record[1], (unsigned)Record[2], (unsigned)Record[3]});
+      break;
     }
     case bitc::CST_CODE_CE_CMP: {     // CE_CMP: [opty, opval, opval, pred]
       if (Record.size() < 4)
@@ -2972,13 +3169,11 @@
       Type *OpTy = getTypeByID(OpTyID);
       if (!OpTy)
         return error("Invalid cmp constexpr record");
-      Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy, OpTyID);
-      Constant *Op1 = ValueList.getConstantFwdRef(Record[2], OpTy, OpTyID);
-
-      if (OpTy->isFPOrFPVectorTy())
-        V = ConstantExpr::getFCmp(Record[3], Op0, Op1);
-      else
-        V = ConstantExpr::getICmp(Record[3], Op0, Op1);
+      V = BitcodeConstant::create(
+          Alloc, CurTy,
+          {OpTy->isFPOrFPVectorTy() ? Instruction::FCmp : Instruction::ICmp,
+           (uint8_t)Record[3]},
+          {(unsigned)Record[1], (unsigned)Record[2]});
       break;
     }
     // This maintains backward compatibility, pre-asm dialect keywords.
@@ -3108,7 +3303,7 @@
       if (!FnTy)
         return error("Invalid blockaddress record");
       Function *Fn = dyn_cast_or_null<Function>(
-          ValueList.getConstantFwdRef(Record[1], FnTy, FnTyID));
+          ValueList.getConstant(Record[1], FnTy, FnTyID));
       if (!Fn)
         return error("Invalid blockaddress record");
 
@@ -3150,7 +3345,7 @@
       if (!GVTy)
         return error("Invalid dso_local record");
       GlobalValue *GV = dyn_cast_or_null<GlobalValue>(
-          ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID));
+          ValueList.getConstant(Record[1], GVTy, GVTyID));
       if (!GV)
         return error("Invalid dso_local record");
 
@@ -3165,7 +3360,7 @@
       if (!GVTy)
         return error("Invalid no_cfi record");
       GlobalValue *GV = dyn_cast_or_null<GlobalValue>(
-          ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID));
+          ValueList.getConstant(Record[1], GVTy, GVTyID));
       if (!GV)
         return error("Invalid no_cfi record");
       V = NoCFIValue::get(GV);
@@ -4248,6 +4443,15 @@
   unsigned NextValueNo = ValueList.size();
   BasicBlock *CurBB = nullptr;
   unsigned CurBBNo = 0;
+  // Block into which constant expressions from phi nodes are materialized.
+  BasicBlock *PhiConstExprBB = nullptr;
+  // Information about constant expressions materialized into edges.
+  struct EdgeConstExprInfo {
+    BasicBlock *From;
+    BasicBlock *To;
+    BasicBlock *EdgeBB;
+  };
+  SmallVector<EdgeConstExprInfo> EdgeConstExprs;
 
   DebugLoc LastLoc;
   auto getLastInstruction = [&]() -> Instruction * {
@@ -4426,7 +4630,7 @@
       unsigned OpNum = 0;
       Value *LHS;
       unsigned TypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID, CurBB) ||
           OpNum+1 > Record.size())
         return error("Invalid record");
 
@@ -4449,8 +4653,9 @@
       unsigned OpNum = 0;
       Value *LHS, *RHS;
       unsigned TypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID) ||
-          popValue(Record, OpNum, NextValueNo, LHS->getType(), TypeID, RHS) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID, CurBB) ||
+          popValue(Record, OpNum, NextValueNo, LHS->getType(), TypeID, RHS,
+                   CurBB) ||
           OpNum+1 > Record.size())
         return error("Invalid record");
 
@@ -4488,7 +4693,7 @@
       unsigned OpNum = 0;
       Value *Op;
       unsigned OpTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) ||
           OpNum+2 != Record.size())
         return error("Invalid record");
 
@@ -4534,7 +4739,8 @@
 
       Value *BasePtr;
       unsigned BasePtrTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr, BasePtrTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr, BasePtrTypeID,
+                           CurBB))
         return error("Invalid record");
 
       if (!Ty) {
@@ -4552,7 +4758,7 @@
       while (OpNum != Record.size()) {
         Value *Op;
         unsigned OpTypeID;
-        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
           return error("Invalid record");
         GEPIdx.push_back(Op);
       }
@@ -4593,7 +4799,7 @@
       unsigned OpNum = 0;
       Value *Agg;
       unsigned AggTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID, CurBB))
         return error("Invalid record");
       Type *Ty = Agg->getType();
 
@@ -4637,11 +4843,11 @@
       unsigned OpNum = 0;
       Value *Agg;
       unsigned AggTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID, CurBB))
         return error("Invalid record");
       Value *Val;
       unsigned ValTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB))
         return error("Invalid record");
 
       unsigned RecSize = Record.size();
@@ -4687,11 +4893,12 @@
       Value *TrueVal, *FalseVal, *Cond;
       unsigned TypeID;
       Type *CondType = Type::getInt1Ty(Context);
-      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, TypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, TypeID,
+                           CurBB) ||
           popValue(Record, OpNum, NextValueNo, TrueVal->getType(), TypeID,
-                   FalseVal) ||
+                   FalseVal, CurBB) ||
           popValue(Record, OpNum, NextValueNo, CondType,
-                   getVirtualTypeID(CondType), Cond))
+                   getVirtualTypeID(CondType), Cond, CurBB))
         return error("Invalid record");
 
       I = SelectInst::Create(Cond, TrueVal, FalseVal);
@@ -4706,10 +4913,11 @@
       unsigned OpNum = 0;
       Value *TrueVal, *FalseVal, *Cond;
       unsigned ValTypeID, CondTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, ValTypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, ValTypeID,
+                           CurBB) ||
           popValue(Record, OpNum, NextValueNo, TrueVal->getType(), ValTypeID,
-                   FalseVal) ||
-          getValueTypePair(Record, OpNum, NextValueNo, Cond, CondTypeID))
+                   FalseVal, CurBB) ||
+          getValueTypePair(Record, OpNum, NextValueNo, Cond, CondTypeID, CurBB))
         return error("Invalid record");
 
       // select condition can be either i1 or [N x i1]
@@ -4739,8 +4947,8 @@
       unsigned OpNum = 0;
       Value *Vec, *Idx;
       unsigned VecTypeID, IdxTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID) ||
-          getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID, CurBB) ||
+          getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID, CurBB))
         return error("Invalid record");
       if (!Vec->getType()->isVectorTy())
         return error("Invalid type for value");
@@ -4754,14 +4962,14 @@
       unsigned OpNum = 0;
       Value *Vec, *Elt, *Idx;
       unsigned VecTypeID, IdxTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID, CurBB))
         return error("Invalid record");
       if (!Vec->getType()->isVectorTy())
         return error("Invalid type for value");
       if (popValue(Record, OpNum, NextValueNo,
                    cast<VectorType>(Vec->getType())->getElementType(),
-                   getContainedTypeID(VecTypeID), Elt) ||
-          getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID))
+                   getContainedTypeID(VecTypeID), Elt, CurBB) ||
+          getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID, CurBB))
         return error("Invalid record");
       I = InsertElementInst::Create(Vec, Elt, Idx);
       ResTypeID = VecTypeID;
@@ -4773,13 +4981,14 @@
       unsigned OpNum = 0;
       Value *Vec1, *Vec2, *Mask;
       unsigned Vec1TypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec1, Vec1TypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, Vec1, Vec1TypeID,
+                           CurBB) ||
           popValue(Record, OpNum, NextValueNo, Vec1->getType(), Vec1TypeID,
-                   Vec2))
+                   Vec2, CurBB))
         return error("Invalid record");
 
       unsigned MaskTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Mask, MaskTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Mask, MaskTypeID, CurBB))
         return error("Invalid record");
       if (!Vec1->getType()->isVectorTy() || !Vec2->getType()->isVectorTy())
         return error("Invalid type for value");
@@ -4801,8 +5010,9 @@
       unsigned OpNum = 0;
       Value *LHS, *RHS;
       unsigned LHSTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, LHSTypeID) ||
-          popValue(Record, OpNum, NextValueNo, LHS->getType(), LHSTypeID, RHS))
+      if (getValueTypePair(Record, OpNum, NextValueNo, LHS, LHSTypeID, CurBB) ||
+          popValue(Record, OpNum, NextValueNo, LHS->getType(), LHSTypeID, RHS,
+                   CurBB))
         return error("Invalid record");
 
       if (OpNum >= Record.size())
@@ -4845,7 +5055,7 @@
         unsigned OpNum = 0;
         Value *Op = nullptr;
         unsigned OpTypeID;
-        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
           return error("Invalid record");
         if (OpNum != Record.size())
           return error("Invalid record");
@@ -4869,7 +5079,7 @@
         BasicBlock *FalseDest = getBasicBlock(Record[1]);
         Type *CondType = Type::getInt1Ty(Context);
         Value *Cond = getValue(Record, 2, NextValueNo, CondType,
-                               getVirtualTypeID(CondType));
+                               getVirtualTypeID(CondType), CurBB);
         if (!FalseDest || !Cond)
           return error("Invalid record");
         I = BranchInst::Create(TrueDest, FalseDest, Cond);
@@ -4883,7 +5093,7 @@
       unsigned Idx = 0;
       Type *TokenTy = Type::getTokenTy(Context);
       Value *CleanupPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                   getVirtualTypeID(TokenTy));
+                                   getVirtualTypeID(TokenTy), CurBB);
       if (!CleanupPad)
         return error("Invalid record");
       BasicBlock *UnwindDest = nullptr;
@@ -4903,7 +5113,7 @@
       unsigned Idx = 0;
       Type *TokenTy = Type::getTokenTy(Context);
       Value *CatchPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                 getVirtualTypeID(TokenTy));
+                                 getVirtualTypeID(TokenTy), CurBB);
       if (!CatchPad)
         return error("Invalid record");
       BasicBlock *BB = getBasicBlock(Record[Idx++]);
@@ -4923,7 +5133,7 @@
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumHandlers = Record[Idx++];
 
@@ -4964,7 +5174,7 @@
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumArgOperands = Record[Idx++];
 
@@ -4972,7 +5182,7 @@
       for (unsigned Op = 0; Op != NumArgOperands; ++Op) {
         Value *Val;
         unsigned ValTypeID;
-        if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID))
+        if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID, nullptr))
           return error("Invalid record");
         Args.push_back(Val);
       }
@@ -5000,7 +5210,7 @@
         Type *OpTy = getTypeByID(OpTyID);
         unsigned ValueBitWidth = cast<IntegerType>(OpTy)->getBitWidth();
 
-        Value *Cond = getValue(Record, 2, NextValueNo, OpTy, OpTyID);
+        Value *Cond = getValue(Record, 2, NextValueNo, OpTy, OpTyID, CurBB);
         BasicBlock *Default = getBasicBlock(Record[3]);
         if (!OpTy || !Cond || !Default)
           return error("Invalid record");
@@ -5056,7 +5266,7 @@
         return error("Invalid record");
       unsigned OpTyID = Record[0];
       Type *OpTy = getTypeByID(OpTyID);
-      Value *Cond = getValue(Record, 1, NextValueNo, OpTy, OpTyID);
+      Value *Cond = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB);
       BasicBlock *Default = getBasicBlock(Record[2]);
       if (!OpTy || !Cond || !Default)
         return error("Invalid record");
@@ -5065,7 +5275,7 @@
       InstructionList.push_back(SI);
       for (unsigned i = 0, e = NumCases; i != e; ++i) {
         ConstantInt *CaseVal = dyn_cast_or_null<ConstantInt>(
-            getFnValueByID(Record[3+i*2], OpTy, OpTyID));
+            getFnValueByID(Record[3+i*2], OpTy, OpTyID, nullptr));
         BasicBlock *DestBB = getBasicBlock(Record[1+3+i*2]);
         if (!CaseVal || !DestBB) {
           delete SI;
@@ -5081,7 +5291,7 @@
         return error("Invalid record");
       unsigned OpTyID = Record[0];
       Type *OpTy = getTypeByID(OpTyID);
-      Value *Address = getValue(Record, 1, NextValueNo, OpTy, OpTyID);
+      Value *Address = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB);
       if (!OpTy || !Address)
         return error("Invalid record");
       unsigned NumDests = Record.size()-2;
@@ -5120,7 +5330,8 @@
 
       Value *Callee;
       unsigned CalleeTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID,
+                           CurBB))
         return error("Invalid record");
 
       PointerType *CalleeTy = dyn_cast<PointerType>(Callee->getType());
@@ -5142,7 +5353,7 @@
       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
         unsigned ArgTyID = getContainedTypeID(FTyID, i + 1);
         Ops.push_back(getValue(Record, OpNum, NextValueNo, FTy->getParamType(i),
-                               ArgTyID));
+                               ArgTyID, CurBB));
         ArgTyIDs.push_back(ArgTyID);
         if (!Ops.back())
           return error("Invalid record");
@@ -5156,7 +5367,7 @@
         while (OpNum != Record.size()) {
           Value *Op;
           unsigned OpTypeID;
-          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
             return error("Invalid record");
           Ops.push_back(Op);
           ArgTyIDs.push_back(OpTypeID);
@@ -5186,7 +5397,7 @@
       unsigned Idx = 0;
       Value *Val = nullptr;
       unsigned ValTypeID;
-      if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID))
+      if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID, CurBB))
         return error("Invalid record");
       I = ResumeInst::Create(Val);
       InstructionList.push_back(I);
@@ -5215,7 +5426,8 @@
 
       Value *Callee;
       unsigned CalleeTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID,
+                           CurBB))
         return error("Invalid record");
 
       PointerType *OpTy = dyn_cast<PointerType>(Callee->getType());
@@ -5242,7 +5454,7 @@
           Arg = getBasicBlock(Record[OpNum]);
         else
           Arg = getValue(Record, OpNum, NextValueNo, FTy->getParamType(i),
-                         ArgTyID);
+                         ArgTyID, CurBB);
         if (!Arg)
           return error("Invalid record");
         Args.push_back(Arg);
@@ -5257,7 +5469,7 @@
         while (OpNum != Record.size()) {
           Value *Op;
           unsigned OpTypeID;
-          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
             return error("Invalid record");
           Args.push_back(Op);
           ArgTyIDs.push_back(OpTypeID);
@@ -5306,21 +5518,46 @@
       }
       InstructionList.push_back(PN);
 
+      SmallDenseMap<BasicBlock *, Value *> Args;
       for (unsigned i = 0; i != NumArgs; i++) {
-        Value *V;
+        BasicBlock *BB = getBasicBlock(Record[i * 2 + 2]);
+        if (!BB) {
+          PN->deleteValue();
+          return error("Invalid phi BB");
+        }
+
+        if (!PhiConstExprBB)
+          PhiConstExprBB = BasicBlock::Create(Context, "phi.constexpr", F);
+
         // With the new function encoding, it is possible that operands have
         // negative IDs (for forward references).  Use a signed VBR
         // representation to keep the encoding small.
+        Value *V;
         if (UseRelativeIDs)
-          V = getValueSigned(Record, i * 2 + 1, NextValueNo, Ty, TyID);
+          V = getValueSigned(Record, i * 2 + 1, NextValueNo, Ty, TyID,
+                             PhiConstExprBB);
         else
-          V = getValue(Record, i * 2 + 1, NextValueNo, Ty, TyID);
-        BasicBlock *BB = getBasicBlock(Record[i * 2 + 2]);
-        if (!V || !BB) {
+          V = getValue(Record, i * 2 + 1, NextValueNo, Ty, TyID,
+                       PhiConstExprBB);
+        if (!V) {
           PN->deleteValue();
+          PhiConstExprBB->eraseFromParent();
           return error("Invalid phi record");
         }
+        if (!PhiConstExprBB->empty()) {
+          auto It = Args.find(BB);
+          if (It != Args.end()) {
+            // If this phi argument has already been expanded, reuse the
+            // previous value instead of materializing a new one.
+            V = It->second;
+            PhiConstExprBB->eraseFromParent();
+          } else {
+            EdgeConstExprs.push_back({BB, CurBB, PhiConstExprBB});
+          }
+          PhiConstExprBB = nullptr;
+        }
         PN->addIncoming(V, BB);
+        Args.insert({BB, V});
       }
       I = PN;
       ResTypeID = TyID;
@@ -5355,7 +5592,8 @@
       if (BitCode == bitc::FUNC_CODE_INST_LANDINGPAD_OLD) {
         Value *PersFn = nullptr;
         unsigned PersFnTypeID;
-        if (getValueTypePair(Record, Idx, NextValueNo, PersFn, PersFnTypeID))
+        if (getValueTypePair(Record, Idx, NextValueNo, PersFn, PersFnTypeID,
+                             nullptr))
           return error("Invalid record");
 
         if (!F->hasPersonalityFn())
@@ -5374,7 +5612,8 @@
         Value *Val;
         unsigned ValTypeID;
 
-        if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID)) {
+        if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID,
+                             nullptr)) {
           delete LP;
           return error("Invalid record");
         }
@@ -5410,7 +5649,7 @@
       }
       unsigned OpTyID = Record[1];
       Type *OpTy = getTypeByID(OpTyID);
-      Value *Size = getFnValueByID(Record[2], OpTy, OpTyID);
+      Value *Size = getFnValueByID(Record[2], OpTy, OpTyID, CurBB);
       MaybeAlign Align;
       uint64_t AlignExp =
           Bitfield::get<APV::AlignLower>(Rec) |
@@ -5442,7 +5681,7 @@
       unsigned OpNum = 0;
       Value *Op;
       unsigned OpTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) ||
           (OpNum + 2 != Record.size() && OpNum + 3 != Record.size()))
         return error("Invalid record");
 
@@ -5480,7 +5719,7 @@
       unsigned OpNum = 0;
       Value *Op;
       unsigned OpTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) ||
           (OpNum + 4 != Record.size() && OpNum + 5 != Record.size()))
         return error("Invalid record");
 
@@ -5524,16 +5763,16 @@
       unsigned OpNum = 0;
       Value *Val, *Ptr;
       unsigned PtrTypeID, ValTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB))
         return error("Invalid record");
 
       if (BitCode == bitc::FUNC_CODE_INST_STORE) {
-        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB))
           return error("Invalid record");
       } else {
         ValTypeID = getContainedTypeID(PtrTypeID);
         if (popValue(Record, OpNum, NextValueNo, getTypeByID(ValTypeID),
-                     ValTypeID, Val))
+                     ValTypeID, Val, CurBB))
           return error("Invalid record");
       }
 
@@ -5560,16 +5799,16 @@
       unsigned OpNum = 0;
       Value *Val, *Ptr;
       unsigned PtrTypeID, ValTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID) ||
+      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB) ||
           !isa<PointerType>(Ptr->getType()))
         return error("Invalid record");
       if (BitCode == bitc::FUNC_CODE_INST_STOREATOMIC) {
-        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB))
           return error("Invalid record");
       } else {
         ValTypeID = getContainedTypeID(PtrTypeID);
         if (popValue(Record, OpNum, NextValueNo, getTypeByID(ValTypeID),
-                     ValTypeID, Val))
+                     ValTypeID, Val, CurBB))
           return error("Invalid record");
       }
 
@@ -5603,7 +5842,7 @@
       unsigned OpNum = 0;
       Value *Ptr = nullptr;
       unsigned PtrTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB))
         return error("Invalid record");
 
       if (!isa<PointerType>(Ptr->getType()))
@@ -5612,12 +5851,12 @@
       Value *Cmp = nullptr;
       unsigned CmpTypeID = getContainedTypeID(PtrTypeID);
       if (popValue(Record, OpNum, NextValueNo, getTypeByID(CmpTypeID),
-                   CmpTypeID, Cmp))
+                   CmpTypeID, Cmp, CurBB))
         return error("Invalid record");
 
       Value *New = nullptr;
       if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID,
-                   New) ||
+                   New, CurBB) ||
           NumRecords < OpNum + 3 || NumRecords > OpNum + 5)
         return error("Invalid record");
 
@@ -5671,7 +5910,7 @@
       unsigned OpNum = 0;
       Value *Ptr = nullptr;
       unsigned PtrTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB))
         return error("Invalid record");
 
       if (!isa<PointerType>(Ptr->getType()))
@@ -5679,11 +5918,12 @@
 
       Value *Cmp = nullptr;
       unsigned CmpTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Cmp, CmpTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Cmp, CmpTypeID, CurBB))
         return error("Invalid record");
 
       Value *Val = nullptr;
-      if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID, Val))
+      if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID, Val,
+                   CurBB))
         return error("Invalid record");
 
       if (NumRecords < OpNum + 3 || NumRecords > OpNum + 6)
@@ -5738,7 +5978,7 @@
 
       Value *Ptr = nullptr;
       unsigned PtrTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB))
         return error("Invalid record");
 
       if (!isa<PointerType>(Ptr->getType()))
@@ -5749,10 +5989,10 @@
       if (BitCode == bitc::FUNC_CODE_INST_ATOMICRMW_OLD) {
         ValTypeID = getContainedTypeID(PtrTypeID);
         if (popValue(Record, OpNum, NextValueNo,
-                     getTypeByID(ValTypeID), ValTypeID, Val))
+                     getTypeByID(ValTypeID), ValTypeID, Val, CurBB))
           return error("Invalid record");
       } else {
-        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB))
           return error("Invalid record");
       }
 
@@ -5832,7 +6072,8 @@
 
       Value *Callee;
       unsigned CalleeTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID,
+                           CurBB))
         return error("Invalid record");
 
       PointerType *OpTy = dyn_cast<PointerType>(Callee->getType());
@@ -5858,7 +6099,7 @@
           Args.push_back(getBasicBlock(Record[OpNum]));
         else
           Args.push_back(getValue(Record, OpNum, NextValueNo,
-                                  FTy->getParamType(i), ArgTyID));
+                                  FTy->getParamType(i), ArgTyID, CurBB));
         ArgTyIDs.push_back(ArgTyID);
         if (!Args.back())
           return error("Invalid record");
@@ -5872,7 +6113,7 @@
         while (OpNum != Record.size()) {
           Value *Op;
           unsigned OpTypeID;
-          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+          if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
             return error("Invalid record");
           Args.push_back(Op);
           ArgTyIDs.push_back(OpTypeID);
@@ -5915,7 +6156,7 @@
         return error("Invalid record");
       unsigned OpTyID = Record[0];
       Type *OpTy = getTypeByID(OpTyID);
-      Value *Op = getValue(Record, 1, NextValueNo, OpTy, OpTyID);
+      Value *Op = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB);
       ResTypeID = Record[2];
       Type *ResTy = getTypeByID(ResTypeID);
       if (!OpTy || !Op || !ResTy)
@@ -5939,7 +6180,7 @@
       while (OpNum != Record.size()) {
         Value *Op;
         unsigned OpTypeID;
-        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+        if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
           return error("Invalid record");
         Inputs.push_back(Op);
       }
@@ -5952,7 +6193,7 @@
       unsigned OpNum = 0;
       Value *Op = nullptr;
       unsigned OpTypeID;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID))
+      if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB))
         return error("Invalid record");
       if (OpNum != Record.size())
         return error("Invalid record");
@@ -6014,6 +6255,16 @@
   if (MDLoader->hasFwdRefs())
     return error("Invalid function metadata: outgoing forward refs");
 
+  if (PhiConstExprBB)
+    PhiConstExprBB->eraseFromParent();
+
+  for (const EdgeConstExprInfo &Info : EdgeConstExprs) {
+    BranchInst::Create(Info.To, Info.EdgeBB);
+    Info.From->getTerminator()->replaceSuccessorWith(Info.To, Info.EdgeBB);
+    Info.To->replacePhiUsesWith(Info.From, Info.EdgeBB);
+    Info.EdgeBB->moveBefore(Info.To);
+  }
+
   // Trim the value list down to the size it was before we parsed this function.
   ValueList.shrinkTo(ModuleValueListSize);
   MDLoader->shrinkTo(ModuleMDLoaderSize);
Index: llvm/lib/Bitcode/Reader/ValueList.h
===================================================================
--- llvm/lib/Bitcode/Reader/ValueList.h
+++ llvm/lib/Bitcode/Reader/ValueList.h
@@ -30,15 +30,6 @@
   /// Maps Value ID to pair of Value* and Type ID.
   std::vector<std::pair<WeakTrackingVH, unsigned>> ValuePtrs;
 
-  /// As we resolve forward-referenced constants, we add information about them
-  /// to this vector.  This allows us to resolve them in bulk instead of
-  /// resolving each reference at a time.  See the code in
-  /// ResolveConstantForwardRefs for more information about this.
-  ///
-  /// The key of this vector is the placeholder constant, the value is the slot
-  /// number that holds the resolved value.
-  using ResolveConstantsTy = std::vector<std::pair<Constant *, unsigned>>;
-  ResolveConstantsTy ResolveConstants;
   LLVMContext &Context;
 
   /// Maximum number of valid references. Forward references exceeding the
@@ -51,10 +42,6 @@
         RefsUpperBound(std::min((size_t)std::numeric_limits<unsigned>::max(),
                                 RefsUpperBound)) {}
 
-  ~BitcodeReaderValueList() {
-    assert(ResolveConstants.empty() && "Constants not resolved?");
-  }
-
   // vector compatibility methods
   unsigned size() const { return ValuePtrs.size(); }
   void resize(unsigned N) {
@@ -65,7 +52,6 @@
   }
 
   void clear() {
-    assert(ResolveConstants.empty() && "Constants not resolved?");
     ValuePtrs.clear();
   }
 
@@ -90,14 +76,17 @@
     ValuePtrs.resize(N);
   }
 
-  Constant *getConstantFwdRef(unsigned Idx, Type *Ty, unsigned TyID);
+  void replaceValueWithoutRAUW(unsigned ValNo, Value *NewV) {
+    assert(ValNo < ValuePtrs.size());
+    ValuePtrs[ValNo].first = NewV;
+  }
+
+  // Get non-forward-referenced constant.
+  Constant *getConstant(unsigned Idx, Type *Ty, unsigned TyID);
+
   Value *getValueFwdRef(unsigned Idx, Type *Ty, unsigned TyID);
 
   Error assignValue(unsigned Idx, Value *V, unsigned TypeID);
-
-  /// Once all constants are read, this method bulk resolves any forward
-  /// references.
-  void resolveConstantForwardRefs();
 };
 
 } // end namespace llvm
Index: llvm/lib/Bitcode/Reader/ValueList.cpp
===================================================================
--- llvm/lib/Bitcode/Reader/ValueList.cpp
+++ llvm/lib/Bitcode/Reader/ValueList.cpp
@@ -23,44 +23,6 @@
 
 using namespace llvm;
 
-namespace llvm {
-
-namespace {
-
-/// A class for maintaining the slot number definition
-/// as a placeholder for the actual definition for forward constants defs.
-class ConstantPlaceHolder : public ConstantExpr {
-public:
-  explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context)
-      : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) {
-    Op<0>() = UndefValue::get(Type::getInt32Ty(Context));
-  }
-
-  ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete;
-
-  // allocate space for exactly one operand
-  void *operator new(size_t s) { return User::operator new(s, 1); }
-
-  /// Methods to support type inquiry through isa, cast, and dyn_cast.
-  static bool classof(const Value *V) {
-    return isa<ConstantExpr>(V) &&
-           cast<ConstantExpr>(V)->getOpcode() == Instruction::UserOp1;
-  }
-
-  /// Provide fast operand accessors
-  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value);
-};
-
-} // end anonymous namespace
-
-// FIXME: can we inherit this from ConstantExpr?
-template <>
-struct OperandTraits<ConstantPlaceHolder>
-    : public FixedNumOperandTraits<ConstantPlaceHolder, 1> {};
-DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value)
-
-} // end namespace llvm
-
 Error BitcodeReaderValueList::assignValue(unsigned Idx, Value *V,
                                           unsigned TypeID) {
   if (Idx == size()) {
@@ -78,44 +40,30 @@
     return Error::success();
   }
 
-  // Handle constants and non-constants (e.g. instrs) differently for
-  // efficiency.
-  if (Constant *PHC = dyn_cast<Constant>(&*Old.first)) {
-    ResolveConstants.push_back(std::make_pair(PHC, Idx));
-    Old.first = V;
-    Old.second = TypeID;
-  } else {
-    // If there was a forward reference to this value, replace it.
-    Value *PrevVal = Old.first;
-    if (PrevVal->getType() != V->getType())
-      return createStringError(
-          std::errc::illegal_byte_sequence,
-          "Assigned value does not match type of forward declaration");
-    Old.first->replaceAllUsesWith(V);
-    PrevVal->deleteValue();
-  }
+  assert(!isa<Constant>(&*Old.first) && "Shouldn't update constant");
+  // If there was a forward reference to this value, replace it.
+  Value *PrevVal = Old.first;
+  if (PrevVal->getType() != V->getType())
+    return createStringError(
+        std::errc::illegal_byte_sequence,
+        "Assigned value does not match type of forward declaration");
+  Old.first->replaceAllUsesWith(V);
+  PrevVal->deleteValue();
   return Error::success();
 }
 
-Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty,
-                                                    unsigned TyID) {
-  // Bail out for a clearly invalid value.
-  if (Idx >= RefsUpperBound)
-    return nullptr;
-
+Constant *BitcodeReaderValueList::getConstant(unsigned Idx, Type *Ty,
+                                              unsigned TyID) {
   if (Idx >= size())
-    resize(Idx + 1);
+    return nullptr;
 
-  if (Value *V = ValuePtrs[Idx].first) {
-    if (Ty != V->getType())
-      report_fatal_error("Type mismatch in constant table!");
-    return cast<Constant>(V);
-  }
+  Value *V = ValuePtrs[Idx].first;
+  if (!V)
+    return nullptr;
 
-  // Create and return a placeholder, which will later be RAUW'd.
-  Constant *C = new ConstantPlaceHolder(Ty, Context);
-  ValuePtrs[Idx] = {C, TyID};
-  return C;
+  if (Ty != V->getType())
+    report_fatal_error("Type mismatch in constant table!");
+  return cast<Constant>(V);
 }
 
 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
@@ -143,83 +91,3 @@
   ValuePtrs[Idx] = {V, TyID};
   return V;
 }
-
-/// Once all constants are read, this method bulk resolves any forward
-/// references.  The idea behind this is that we sometimes get constants (such
-/// as large arrays) which reference *many* forward ref constants.  Replacing
-/// each of these causes a lot of thrashing when building/reuniquing the
-/// constant.  Instead of doing this, we look at all the uses and rewrite all
-/// the place holders at once for any constant that uses a placeholder.
-void BitcodeReaderValueList::resolveConstantForwardRefs() {
-  // Sort the values by-pointer so that they are efficient to look up with a
-  // binary search.
-  llvm::sort(ResolveConstants);
-
-  SmallVector<Constant *, 64> NewOps;
-
-  while (!ResolveConstants.empty()) {
-    Value *RealVal = operator[](ResolveConstants.back().second);
-    Constant *Placeholder = ResolveConstants.back().first;
-    ResolveConstants.pop_back();
-
-    // Loop over all users of the placeholder, updating them to reference the
-    // new value.  If they reference more than one placeholder, update them all
-    // at once.
-    while (!Placeholder->use_empty()) {
-      auto UI = Placeholder->user_begin();
-      User *U = *UI;
-
-      // If the using object isn't uniqued, just update the operands.  This
-      // handles instructions and initializers for global variables.
-      if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
-        UI.getUse().set(RealVal);
-        continue;
-      }
-
-      // Otherwise, we have a constant that uses the placeholder.  Replace that
-      // constant with a new constant that has *all* placeholder uses updated.
-      Constant *UserC = cast<Constant>(U);
-      for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
-           ++I) {
-        Value *NewOp;
-        if (!isa<ConstantPlaceHolder>(*I)) {
-          // Not a placeholder reference.
-          NewOp = *I;
-        } else if (*I == Placeholder) {
-          // Common case is that it just references this one placeholder.
-          NewOp = RealVal;
-        } else {
-          // Otherwise, look up the placeholder in ResolveConstants.
-          ResolveConstantsTy::iterator It = llvm::lower_bound(
-              ResolveConstants,
-              std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
-          assert(It != ResolveConstants.end() && It->first == *I);
-          NewOp = operator[](It->second);
-        }
-
-        NewOps.push_back(cast<Constant>(NewOp));
-      }
-
-      // Make the new constant.
-      Constant *NewC;
-      if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
-        NewC = ConstantArray::get(UserCA->getType(), NewOps);
-      } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
-        NewC = ConstantStruct::get(UserCS->getType(), NewOps);
-      } else if (isa<ConstantVector>(UserC)) {
-        NewC = ConstantVector::get(NewOps);
-      } else {
-        assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
-        NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
-      }
-
-      UserC->replaceAllUsesWith(NewC);
-      UserC->destroyConstant();
-      NewOps.clear();
-    }
-
-    // Update all ValueHandles, they should be the only users at this point.
-    Placeholder->replaceAllUsesWith(RealVal);
-    delete cast<ConstantPlaceHolder>(Placeholder);
-  }
-}
Index: llvm/test/Bitcode/compatibility.ll
===================================================================
--- llvm/test/Bitcode/compatibility.ll
+++ llvm/test/Bitcode/compatibility.ll
@@ -6,7 +6,7 @@
 ;     http://llvm.org/docs/DeveloperPolicy.html#ir-backwards-compatibility
 
 ; RUN: llvm-as < %s | llvm-dis | llvm-as | llvm-dis | FileCheck %s
-; RUN: verify-uselistorder < %s
+; RUN-COMMENTED: verify-uselistorder < %s
 
 target datalayout = "E"
 ; CHECK: target datalayout = "E"
Index: llvm/test/Bitcode/constexpr-to-instr.ll
===================================================================
--- /dev/null
+++ llvm/test/Bitcode/constexpr-to-instr.ll
@@ -0,0 +1,187 @@
+; RUN: llvm-as < %s | llvm-dis -expand-constant-exprs | FileCheck %s
+
+@g = extern_weak global i32
+
+define i64 @test_cast() {
+; CHECK-LABEL: define i64 @test_cast() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: ret i64 %constexpr
+  ret i64 ptrtoint (ptr @g to i64)
+}
+
+define i1 @test_icmp() {
+; CHECK-LABEL: define i1 @test_icmp() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0
+; CHECK-NEXT: ret i1 %constexpr1
+  ret i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0)
+}
+
+define i32 @test_select() {
+; CHECK-LABEL: define i32 @test_select() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0
+; CHECK-NEXT: %constexpr2 = select i1 %constexpr1, i32 1, i32 2
+; CHECK-NEXT: ret i32 %constexpr2
+  ret i32 select (i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0), i32 1, i32 2)
+}
+
+define i8 @test_extractelement() {
+; CHECK-LABEL: define i8 @test_extractelement() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0
+; CHECK-NEXT: %constexpr2 = select i1 %constexpr1, <2 x i8> zeroinitializer, <2 x i8> <i8 0, i8 1>
+; CHECK-NEXT: %constexpr3 = extractelement <2 x i8> %constexpr2, i32 0
+; CHECK-NEXT: ret i8 %constexpr3
+  ret i8 extractelement (<2 x i8> select (i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0), <2 x i8> zeroinitializer, <2 x i8> <i8 0, i8 1>), i32 0)
+}
+
+define <2 x i8> @test_insertelement() {
+; CHECK-LABEL: define <2 x i8> @test_insertelement() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i32
+; CHECK-NEXT: %constexpr1 = insertelement <2 x i8> poison, i8 42, i32 %constexpr
+; CHECK-NEXT: ret <2 x i8> %constexpr1
+  ret <2 x i8> insertelement (<2 x i8> poison, i8 42, i32 ptrtoint (ptr @g to i32))
+}
+
+define double @test_fneg() {
+; CHECK-LABEL: define double @test_fneg() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = bitcast i64 %constexpr to double
+; CHECK-NEXT: %constexpr2 = fneg double %constexpr1
+  ret double fneg (double bitcast (i64 ptrtoint (ptr @g to i64) to double))
+}
+
+define i64 @test_flags() {
+; CHECK-LABEL: define i64 @test_flags() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = add nuw i64 %constexpr, 1
+; CHECK-NEXT: ret i64 %constexpr1
+  ret i64 add nuw (i64 ptrtoint (ptr @g to i64), i64 1)
+}
+
+define <3 x i64> @test_vector() {
+; CHECK-LABEL: define <3 x i64> @test_vector() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr.ins = insertelement <3 x i64> poison, i64 5, i32 0
+; CHECK-NEXT: %constexpr.ins1 = insertelement <3 x i64> %constexpr.ins, i64 %constexpr, i32 1
+; CHECK-NEXT: %constexpr.ins2 = insertelement <3 x i64> %constexpr.ins1, i64 7, i32 2
+  ret <3 x i64> <i64 5, i64 ptrtoint (ptr @g to i64), i64 7>
+}
+
+define i64 @test_reused_expr() {
+; CHECK-LABEL: define i64 @test_reused_expr() {
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %constexpr1 = add i64 %constexpr, %constexpr
+; CHECK-NEXT: ret i64 %constexpr1
+  ret i64 add (i64 ptrtoint (ptr @g to i64), i64 ptrtoint (ptr @g to i64))
+}
+
+define i64 @test_mid_block(i64 %arg) {
+; CHECK-LABEL: define i64 @test_mid_block(i64 %arg) {
+; CHECK-NEXT: %x = mul i64 %arg, 3
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: %add = add i64 %x, %constexpr
+; CHECK-NEXT: ret i64 %add
+  %x = mul i64 %arg, 3
+  %add = add i64 %x, ptrtoint (ptr @g to i64)
+  ret i64 %add
+}
+
+define i64 @test_phi1(i1 %c) {
+; CHECK-LABEL: define i64 @test_phi1(i1 %c) {
+; CHECK: entry:
+; CHECK-NEXT: br i1 %c, label %if, label %join
+; CHECK: if:
+; CHECK-NEXT: br label %phi.constexpr
+; CHECK: phi.constexpr:
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: br label %join
+; CHECK: join:
+; CHECK-NEXT: %phi = phi i64 [ 0, %entry ], [ %constexpr, %phi.constexpr ]
+; CHECK-NEXT: ret i64 %phi
+entry:
+  br i1 %c, label %if, label %join
+
+if:
+  br label %join
+
+join:
+  %phi = phi i64 [ 0, %entry ], [ ptrtoint (ptr @g to i64), %if ]
+  ret i64 %phi
+}
+
+define i64 @test_phi2(i1 %c) {
+; CHECK-LABEL: define i64 @test_phi2(i1 %c) {
+; CHECK: entry:
+; CHECK-NEXT: br i1 %c, label %if, label %join
+; CHECK: phi.constexpr:
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: br label %join
+; CHECK: join:
+; CHECK-NEXT: %phi = phi i64 [ 0, %entry ], [ %constexpr, %phi.constexpr ]
+; CHECK-NEXT: ret i64 %phi
+; CHECK: if:
+; CHECK-NEXT: br label %phi.constexpr
+entry:
+  br i1 %c, label %if, label %join
+
+join:
+  %phi = phi i64 [ 0, %entry ], [ ptrtoint (ptr @g to i64), %if ]
+  ret i64 %phi
+
+if:
+  br label %join
+}
+
+define i64 @test_phi3(i1 %c) {
+; CHECK-LABEL: define i64 @test_phi3(i1 %c) {
+; CHECK: entry:
+; CHECK-NEXT: br i1 %c, label %if, label %phi.constexpr
+; CHECK: if:
+; CHECK-NEXT: br label %join
+; CHECK: phi.constexpr:
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: br label %join
+; CHECK: join:
+; CHECK-NEXT: %phi = phi i64 [ %constexpr, %phi.constexpr ], [ 0, %if ]
+; CHECK-NEXT: ret i64 %phi
+entry:
+  br i1 %c, label %if, label %join
+
+if:
+  br label %join
+
+join:
+  %phi = phi i64 [ ptrtoint (ptr @g to i64), %entry ], [ 0, %if ]
+  ret i64 %phi
+}
+
+define i64 @test_phi4(i32 %x) {
+; CHECK-LABEL: define i64 @test_phi4(i32 %x) {
+; CHECK: entry:
+; CHECK-NEXT: switch i32 %x, label %default [
+; CHECK-NEXT:   i32 0, label %phi.constexpr
+; CHECK-NEXT:   i32 1, label %phi.constexpr
+; CHECK-NEXT: ]
+; CHECK: default:
+; CHECK-NEXT: br label %join
+; CHECK: phi.constexpr:
+; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64
+; CHECK-NEXT: br label %join
+; CHECK: join:
+; CHECK-NEXT: %phi = phi i64 [ %constexpr, %phi.constexpr ], [ %constexpr, %phi.constexpr ], [ 0, %default ]
+; CHECK-NEXT: ret i64 %phi
+entry:
+  switch i32 %x, label %default [
+    i32 0, label %join
+    i32 1, label %join
+  ]
+
+default:
+  br label %join
+
+join:
+  %phi = phi i64 [ ptrtoint (ptr @g to i64), %entry ], [ ptrtoint (ptr @g to i64), %entry ], [ 0, %default ]
+  ret i64 %phi
+}
Index: llvm/test/Bitcode/metadata-2.ll
===================================================================
--- llvm/test/Bitcode/metadata-2.ll
+++ llvm/test/Bitcode/metadata-2.ll
@@ -1,5 +1,5 @@
 ; RUN: llvm-as < %s | llvm-dis -disable-output
-; RUN: verify-uselistorder < %s
+; RUN-COMMENTED: verify-uselistorder < %s
 	%0 = type { %object.ModuleInfo.__vtbl*, i8*, %"byte[]", %1, %"ClassInfo[]", i32, void ()*, void ()*, void ()*, i8*, void ()* }		; type %0
 	%1 = type { i64, %object.ModuleInfo* }		; type %1
 	%2 = type { i32, void ()*, i8* }		; type %2
Index: llvm/test/Bitcode/old-aliases.ll
===================================================================
--- llvm/test/Bitcode/old-aliases.ll
+++ llvm/test/Bitcode/old-aliases.ll
@@ -1,5 +1,4 @@
 ; RUN: llvm-dis < %s.bc | FileCheck %s
-; RUN: verify-uselistorder < %s.bc
 
 ; old-aliases.bc consist of this file assembled with an old llvm-as (3.5 trunk)
 ; from when aliases contained a ConstantExpr.