[Bitcode] Support expanding constant expressions into instructions

This implements an autoupgrade from constant expressions to
instructions, which is needed for
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179.

The basic approach is that constant expressions (CST_CODE_CE_*
records) now initially only create a BitcodeConstant value that
holds opcode, flags and operands IDs. Then, when the value actually
gets used, it can be converted either into a constant expression
(if that expression type is still supported) or into a sequence of
instructions. As currently all expressions are still supported,
-expand-constant-exprs is added for testing purposes, to force
expansion.

PHI nodes require special handling, because the constant expression
needs to be evaluated on the incoming edge. We do this by putting
it into a temporary block and then wiring it up appropriately
afterwards (for non-critical edges, we could also move the
instructions into the predecessor).

This also removes the need for the forward referenced constants
machinery, as the BitcodeConstants only hold value IDs. At the
point where the value is actually materialized, no forward
references are needed anymore.

Differential Revision: https://reviews.llvm.org/D127729

1 files changed, 594 insertions, 308 deletions

diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
index 1bf527f..7abe7c0 100644
--- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -94,6 +94,11 @@ static cl::opt<bool> PrintSummaryGUIDs(
     cl::desc(
         "Print the global id for each value when reading the module summary"));
 
+static cl::opt<bool> ExpandConstantExprs(
+    "expand-constant-exprs", cl::Hidden,
+    cl::desc(
+        "Expand constant expressions to instructions for testing purposes"));
+
 namespace {
 
 enum {
@@ -473,6 +478,90 @@ BitcodeReaderBase::readNameFromStrtab(ArrayRef<uint64_t> Record) {
 
 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 non-expressions. This includes constant aggregates
+  // (struct, array, vector) that might need expansion, as well as non-leaf
+  // constants that don't need expansion (no_cfi, dso_local, blockaddress),
+  // but still go through BitcodeConstant to avoid different uselist orders
+  // between the two cases.
+  static constexpr uint8_t ConstantStructOpcode = 255;
+  static constexpr uint8_t ConstantArrayOpcode = 254;
+  static constexpr uint8_t ConstantVectorOpcode = 253;
+  static constexpr uint8_t NoCFIOpcode = 252;
+  static constexpr uint8_t DSOLocalEquivalentOpcode = 251;
+  static constexpr uint8_t BlockAddressOpcode = 250;
+  static constexpr uint8_t FirstSpecialOpcode = BlockAddressOpcode;
+
+  // Separate struct to make passing different number of parameters to
+  // BitcodeConstant::create() more convenient.
+  struct ExtraInfo {
+    uint8_t Opcode;
+    uint8_t Flags;
+    unsigned Extra;
+    Type *SrcElemTy;
+
+    ExtraInfo(uint8_t Opcode, uint8_t Flags = 0, unsigned Extra = 0,
+              Type *SrcElemTy = nullptr)
+        : Opcode(Opcode), Flags(Flags), Extra(Extra), SrcElemTy(SrcElemTy) {}
+  };
+
+  uint8_t Opcode;
+  uint8_t Flags;
+  unsigned NumOperands;
+  unsigned Extra;  // GEP inrange index or blockaddress BB id.
+  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()), Extra(Info.Extra),
+        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 (Extra == (unsigned)-1)
+      return None;
+    return Extra;
+  }
+
+  const char *getOpcodeName() const {
+    return Instruction::getOpcodeName(Opcode);
+  }
+};
+
 class BitcodeReader : public BitcodeReaderBase, public GVMaterializer {
   LLVMContext &Context;
   Module *TheModule = nullptr;
@@ -499,6 +588,10 @@ class BitcodeReader : public BitcodeReaderBase, public GVMaterializer {
   /// 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 +711,14 @@ private:
   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);
+    return ValueList.getValueFwdRef(ID, Ty, TyID, ConstExprInsertBB);
   }
 
   Metadata *getFnMetadataByID(unsigned ID) {
@@ -643,7 +740,8 @@ private:
   /// 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 @@ private:
       // 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 @@ private:
       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 @@ private:
   /// 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 @@ private:
 
   /// 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
@@ -856,7 +959,10 @@ BitcodeReader::BitcodeReader(BitstreamCursor Stream, StringRef Strtab,
                              StringRef ProducerIdentification,
                              LLVMContext &Context)
     : BitcodeReaderBase(std::move(Stream), Strtab), Context(Context),
-      ValueList(Context, this->Stream.SizeInBytes()) {
+      ValueList(this->Stream.SizeInBytes(),
+                [this](unsigned ValID, BasicBlock *InsertBB) {
+                  return materializeValue(ValID, InsertBB);
+                }) {
   this->ProducerIdentification = std::string(ProducerIdentification);
 }
 
@@ -1273,6 +1379,259 @@ unsigned BitcodeReader::getVirtualTypeID(Type *Ty,
   return TypeID;
 }
 
+static bool isConstExprSupported(uint8_t Opcode) {
+  // These are not real constant expressions, always consider them supported.
+  if (Opcode >= BitcodeConstant::FirstSpecialOpcode)
+    return true;
+
+  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;
+    }
+
+    // Iterate in reverse, so values will get popped from the worklist in
+    // expected order.
+    SmallVector<Value *> Ops;
+    for (unsigned OpID : reverse(BC->getOperandIDs())) {
+      auto It = MaterializedValues.find(OpID);
+      if (It != MaterializedValues.end())
+        Ops.push_back(It->second);
+      else
+        Worklist.push_back(OpID);
+    }
+
+    // Some expressions have not been resolved yet, handle them first and then
+    // revisit this one.
+    if (Ops.size() != BC->getOperandIDs().size())
+      continue;
+    std::reverse(Ops.begin(), Ops.end());
+
+    SmallVector<Constant *> ConstOps;
+    for (Value *Op : Ops)
+      if (auto *C = dyn_cast<Constant>(Op))
+        ConstOps.push_back(C);
+
+    // Materialize as constant expression if 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::NoCFIOpcode: {
+          auto *GV = dyn_cast<GlobalValue>(ConstOps[0]);
+          if (!GV)
+            return error("no_cfi operand must be GlobalValue");
+          C = NoCFIValue::get(GV);
+          break;
+        }
+        case BitcodeConstant::DSOLocalEquivalentOpcode: {
+          auto *GV = dyn_cast<GlobalValue>(ConstOps[0]);
+          if (!GV)
+            return error("dso_local operand must be GlobalValue");
+          C = DSOLocalEquivalent::get(GV);
+          break;
+        }
+        case BitcodeConstant::BlockAddressOpcode: {
+          Function *Fn = dyn_cast<Function>(ConstOps[0]);
+          if (!Fn)
+            return error("blockaddress operand must be a function");
+
+          // If the function is already parsed we can insert the block address
+          // right away.
+          BasicBlock *BB;
+          unsigned BBID = BC->Extra;
+          if (!BBID)
+            // Invalid reference to entry block.
+            return error("Invalid ID");
+          if (!Fn->empty()) {
+            Function::iterator BBI = Fn->begin(), BBE = Fn->end();
+            for (size_t I = 0, E = BBID; I != E; ++I) {
+              if (BBI == BBE)
+                return error("Invalid ID");
+              ++BBI;
+            }
+            BB = &*BBI;
+          } else {
+            // Otherwise insert a placeholder and remember it so it can be
+            // inserted when the function is parsed.
+            auto &FwdBBs = BasicBlockFwdRefs[Fn];
+            if (FwdBBs.empty())
+              BasicBlockFwdRefQueue.push_back(Fn);
+            if (FwdBBs.size() < BBID + 1)
+              FwdBBs.resize(BBID + 1);
+            if (!FwdBBs[BBID])
+              FwdBBs[BBID] = BasicBlock::Create(Context);
+            BB = FwdBBs[BBID];
+          }
+          C = BlockAddress::get(Fn, BB);
+          break;
+        }
+        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(Twine("Value referenced by initializer is an unsupported "
+                         "constant expression of type ") +
+                   BC->getOpcodeName());
+
+    // 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 +2745,10 @@ Error BitcodeReader::resolveGlobalAndIndirectSymbolInits() {
       // 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 +2758,10 @@ Error BitcodeReader::resolveGlobalAndIndirectSymbolInits() {
     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 +2785,30 @@ Error BitcodeReader::resolveGlobalAndIndirectSymbolInits() {
     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 +2841,6 @@ Error BitcodeReader::parseConstants() {
   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 +2852,8 @@ Error BitcodeReader::parseConstants() {
     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 +2944,19 @@ Error BitcodeReader::parseConstants() {
         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 +3041,7 @@ Error BitcodeReader::parseConstants() {
       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 +3052,7 @@ Error BitcodeReader::parseConstants() {
       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 +3070,8 @@ Error BitcodeReader::parseConstants() {
               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 +3086,7 @@ Error BitcodeReader::parseConstants() {
         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 +3111,14 @@ Error BitcodeReader::parseConstants() {
       } 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 +3142,21 @@ Error BitcodeReader::parseConstants() {
         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.getValueOr(-1),
+           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 +3167,19 @@ Error BitcodeReader::parseConstants() {
         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 +3187,30 @@ Error BitcodeReader::parseConstants() {
       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 +3218,10 @@ Error BitcodeReader::parseConstants() {
         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 +3230,12 @@ Error BitcodeReader::parseConstants() {
       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,
+          {(uint8_t)(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.
@@ -3107,39 +3364,10 @@ Error BitcodeReader::parseConstants() {
       Type *FnTy = getTypeByID(FnTyID);
       if (!FnTy)
         return error("Invalid blockaddress record");
-      Function *Fn = dyn_cast_or_null<Function>(
-          ValueList.getConstantFwdRef(Record[1], FnTy, FnTyID));
-      if (!Fn)
-        return error("Invalid blockaddress record");
-
-      // If the function is already parsed we can insert the block address right
-      // away.
-      BasicBlock *BB;
-      unsigned BBID = Record[2];
-      if (!BBID)
-        // Invalid reference to entry block.
-        return error("Invalid ID");
-      if (!Fn->empty()) {
-        Function::iterator BBI = Fn->begin(), BBE = Fn->end();
-        for (size_t I = 0, E = BBID; I != E; ++I) {
-          if (BBI == BBE)
-            return error("Invalid ID");
-          ++BBI;
-        }
-        BB = &*BBI;
-      } else {
-        // Otherwise insert a placeholder and remember it so it can be inserted
-        // when the function is parsed.
-        auto &FwdBBs = BasicBlockFwdRefs[Fn];
-        if (FwdBBs.empty())
-          BasicBlockFwdRefQueue.push_back(Fn);
-        if (FwdBBs.size() < BBID + 1)
-          FwdBBs.resize(BBID + 1);
-        if (!FwdBBs[BBID])
-          FwdBBs[BBID] = BasicBlock::Create(Context);
-        BB = FwdBBs[BBID];
-      }
-      V = BlockAddress::get(Fn, BB);
+      V = BitcodeConstant::create(
+          Alloc, CurTy,
+          {BitcodeConstant::BlockAddressOpcode, 0, (unsigned)Record[2]},
+          Record[1]);
       break;
     }
     case bitc::CST_CODE_DSO_LOCAL_EQUIVALENT: {
@@ -3149,12 +3377,8 @@ Error BitcodeReader::parseConstants() {
       Type *GVTy = getTypeByID(GVTyID);
       if (!GVTy)
         return error("Invalid dso_local record");
-      GlobalValue *GV = dyn_cast_or_null<GlobalValue>(
-          ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID));
-      if (!GV)
-        return error("Invalid dso_local record");
-
-      V = DSOLocalEquivalent::get(GV);
+      V = BitcodeConstant::create(
+          Alloc, CurTy, BitcodeConstant::DSOLocalEquivalentOpcode, Record[1]);
       break;
     }
     case bitc::CST_CODE_NO_CFI_VALUE: {
@@ -3164,11 +3388,8 @@ Error BitcodeReader::parseConstants() {
       Type *GVTy = getTypeByID(GVTyID);
       if (!GVTy)
         return error("Invalid no_cfi record");
-      GlobalValue *GV = dyn_cast_or_null<GlobalValue>(
-          ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID));
-      if (!GV)
-        return error("Invalid no_cfi record");
-      V = NoCFIValue::get(GV);
+      V = BitcodeConstant::create(Alloc, CurTy, BitcodeConstant::NoCFIOpcode,
+                                  Record[1]);
       break;
     }
     }
@@ -4248,6 +4469,12 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
   unsigned NextValueNo = ValueList.size();
   BasicBlock *CurBB = nullptr;
   unsigned CurBBNo = 0;
+  // Block into which constant expressions from phi nodes are materialized.
+  BasicBlock *PhiConstExprBB = nullptr;
+  // Edge blocks for phi nodes into which constant expressions have been
+  // expanded.
+  SmallMapVector<std::pair<BasicBlock *, BasicBlock *>, BasicBlock *, 4>
+    ConstExprEdgeBBs;
 
   DebugLoc LastLoc;
   auto getLastInstruction = [&]() -> Instruction * {
@@ -4426,7 +4653,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4676,9 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4716,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4762,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +4781,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4822,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4866,11 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4916,12 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4936,11 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4970,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +4985,14 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5004,14 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5033,9 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5078,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5102,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5116,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5136,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5156,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumHandlers = Record[Idx++];
 
@@ -4964,7 +5197,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumArgOperands = Record[Idx++];
 
@@ -4972,7 +5205,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5233,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5289,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5298,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5314,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5353,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +5376,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5390,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5420,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5449,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +5477,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
           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 +5492,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5541,55 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       }
       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");
+        }
+
+        // Phi nodes may contain the same predecessor multiple times, in which
+        // case the incoming value must be identical. Directly reuse the already
+        // seen value here, to avoid expanding a constant expression multiple
+        // times.
+        auto It = Args.find(BB);
+        if (It != Args.end()) {
+          PN->addIncoming(It->second, BB);
+          continue;
+        }
+
+        // If there already is a block for this edge (from a different phi),
+        // use it.
+        BasicBlock *EdgeBB = ConstExprEdgeBBs.lookup({BB, CurBB});
+        if (!EdgeBB) {
+          // Otherwise, use a temporary block (that we will discard if it
+          // turns out to be unnecessary).
+          if (!PhiConstExprBB)
+            PhiConstExprBB = BasicBlock::Create(Context, "phi.constexpr", F);
+          EdgeBB = PhiConstExprBB;
+        }
+
         // 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, EdgeBB);
         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, EdgeBB);
+        if (!V) {
           PN->deleteValue();
+          PhiConstExprBB->eraseFromParent();
           return error("Invalid phi record");
         }
+
+        if (EdgeBB == PhiConstExprBB && !EdgeBB->empty()) {
+          ConstExprEdgeBBs.insert({{BB, CurBB}, EdgeBB});
+          PhiConstExprBB = nullptr;
+        }
         PN->addIncoming(V, BB);
+        Args.insert({BB, V});
       }
       I = PN;
       ResTypeID = TyID;
@@ -5355,7 +5624,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5644,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +5681,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       }
       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 +5713,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5751,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5795,16 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5831,16 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5874,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5883,12 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5942,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +5950,12 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +6010,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +6021,10 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +6104,8 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
 
       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 +6131,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
           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 +6145,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +6188,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
         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 +6212,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +6225,7 @@ Error BitcodeReader::parseFunctionBody(Function *F) {
       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 +6287,19 @@ OutOfRecordLoop:
   if (MDLoader->hasFwdRefs())
     return error("Invalid function metadata: outgoing forward refs");
 
+  if (PhiConstExprBB)
+    PhiConstExprBB->eraseFromParent();
+
+  for (const auto &Pair : ConstExprEdgeBBs) {
+    BasicBlock *From = Pair.first.first;
+    BasicBlock *To = Pair.first.second;
+    BasicBlock *EdgeBB = Pair.second;
+    BranchInst::Create(To, EdgeBB);
+    From->getTerminator()->replaceSuccessorWith(To, EdgeBB);
+    To->replacePhiUsesWith(From, EdgeBB);
+    EdgeBB->moveBefore(To);
+  }
+
   // Trim the value list down to the size it was before we parsed this function.
   ValueList.shrinkTo(ModuleValueListSize);
   MDLoader->shrinkTo(ModuleMDLoaderSize);