[Bitcode] Support expanding constant expressions into instructions

[nikic]

Summary

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.

[nikic]

Fix one of the uselistorder issues, improve error message.

[nikic]

@dexonsmith I'm really struggling to get the uselistorder support working with this patch. The key change here is that constant expressions are materialized on first use, rather than all at once when parsing the constant block. I think I fixed the case where constant expressions are referenced by instructions correctly, but despite trying different variants for a few hours, I just can't figure out how to handle expressions in global initializers correctly. Do you have any pointers?

[dexonsmith]

This seems challenging indeed. (To clarify, there’s never a need to worry about use-list-order when an upgrade is happening, since use-lists can be dropped when there’s a mismatch, but since all constants have changed materialization order that affects the non-upgrade case too.)

The key is to understand the order that constant expressions will be created, and therefore what the “natural” use-list order would be. What might help to debug this would be to sort use-lists before serialization, and dump them after deserialization, to track the mutations. Once you understand what’s happening it should be easier to add/change the logic to predict the order.

It might be okay to add an extra pass to serialization (only when use-lists are being written), as long as it it’s still relatively cheap. Not sure if that’s helpful or not.

BTW, it’s not easy for me to dig in myself for the next couple of months (don’t have ready access to a development machine) but happy to iterate on ideas / think things through.

[nikic]

Fix uselistorder preservation. In the end, this largely amounted to removing a lot of the special handling around global values we previously had. In orderModule(), we now visit globals in the same order they get initialized (which is reverse order) and also visit the initializers while doing so. Additionally, we now go through BitcodeConstant for all non-leaf constants, even those that wouldn't strictly require it (no_cfi, dso_local and blockaddress). This makes sure that we don't get a different uselistorder for just these special cases, which would get really awkward to handle.

There is still a remaining issue in this patch, because there are some getValueFwdRef() calls from MetadataLoader, which also need to materialize constant expressions.

[dexonsmith]

Nice; glad this was a simplification in the end. I had a quick look and the new logic looks right to me.

I’m curious: is the metadata loader issue related to use-list order, or independent?

[nikic]

I’m curious: is the metadata loader issue related to use-list order, or independent?

Both :) I just fixed the general issue, and am now left with the use-list order issue only. I think we should be ordering MetadataAsValue uses as part of functions now (rather than globally) and also predict use lists for them, but I haven't figured out the details yet.

[nikic]

Okay, the metadata use-list order issue is fixed now as well, so this patch should be ready. The extra subtlety there is that function metadata is decoded in one go before the function instructions, rather than interleaved as it gets used. Additionally it's necessary to explicitly visit these operands in predictValueUseListOrder(), otherwise we might not emit a uselistorder directive at all.

[dexonsmith]

I’ll leave the main review to @aeubanks (SGTM but I don’t have time right now to think through in detail), but I looked at the metadata and use-list order changes and they LGTM. Thanks for working through the issues!

[nhaehnle]

Most of this looks good to me, I just have a few nits and one bigger question about phi handling inline.

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

99

Suggest to make it easier to understand for somebody who lacks context.

520–524

Shouldn't these be private?

1428–1432

Could be an if/else without a break so that all required values are pushed to the worklist immediately, which is slightly more convenient for the common case where the constant expression overall is a tree. But I don't feel strongly about it.

5576–5589

I don't understand what Args is trying to achieve here. Each predecessor basic block should only appear once, so the Args.find(BB) should never be successful -- right?

I *think* perhaps what you're trying to do is optimize the case where multiple phi nodes have the same incoming value for the same basic block? But then the Args map would have to have bigger scope and look slightly different.

Speaking of, shouldn't the PhiConstExprBB be cached somehow so that multiple phi nodes use the same edge basic blocks?

[nikic]

Address review comments, and in particular fix handling of multiple phis in the same block.

[nikic]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

520–524

These are directly used in the materializeValue() code. It didn't seem worthwhile to make these private and add getters for something that is private to the bitcode reader anyway.

1428–1432

Good point, done. A subtlety here is that we now need to iterate in reverse order (and then reverse Ops) to make sure the worklist entries are processed in correct order. Otherwise we'd expand the last operand first.

5576–5589

A predecessor can appear multiple times in a phi block, but must have the same incoming value each time. This most commonly happens with switch terminators (see @test_phi_multiple_identical_predecessors). I've made the comment for this a bit more detailed.

And you're absolutely right, I wasn't handling the case of multiple phis correctly. I've changes this to reuse the same block for all expressions on one edge (@test_phi_multiple_nodes).

[nhaehnle]

Thanks. This looks pretty good to me, but I'm not familiar with the bitcode reader so perhaps somebody else can still take a look.

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

5576–5589

Huh, I didn't realize duplicate predecessors were allowed. Weird, but okay :)

[nikic]

In D127729#3601812, @nhaehnle wrote:

Thanks. This looks pretty good to me, but I'm not familiar with the bitcode reader so perhaps somebody else can still take a look.

Thanks for the review!

Don't think we have a lot of people familiar with the bitcode reader, maybe @aeubanks or @efriedma can take a look?

[dexonsmith]

BitcodeReader LGTM.

[MaskRay]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

98

Omit cl::init(false),

3239

/home/maskray/llvm/llvm/lib/Bitcode/Reader/BitcodeReader.cpp:3235:12: error: non-constant-expression cannot be narrowed from type 'llvm::Instruction::OtherOps' to 'uint8_t' (aka 'unsigned char') in initializer list [-Wc++11-narrowing]
          {OpTy->isFPOrFPVectorTy() ? Instruction::FCmp : Instruction::ICmp,
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Add a uint8_t cast

[MaskRay]

llvm/lib/Bitcode/Reader/ValueList.h

33

Unused now? warning: private field 'Context' is not used [-Wunused-private-field]

[nikic]

Drop cl::init, fix warnings.

[bkramer]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2822

I found a 2013 vintage CUDA bitcode file that relies on this upgrader. It does

@unrollpragma = private addrspace(1) constant [17 x i8] c"#pragma unroll 1\00"
bitcast @unrollpragma to i8*

Bitcasting away addrspace has been disallowed since the advent of addrspacecast. Was this backwards compat dropped accidentally or is it time to drop this upgrader?

If we want the latter we can also remove it from AutoUpgrade.cpp.

[nikic]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2822

This wasn't intentional. Can you please check whether https://gist.github.com/nikic/a4daeb24294f1f16ed45a531bcfaa146 works with your bitcode file?

[bkramer]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2822

That fixes the assert failure I was seeeing. Thanks.

[nikic]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2822

Thanks for the quick confirmation, I've landed this as https://github.com/llvm/llvm-project/commit/1271b8f57ab95b601b75b69cd957b9ee9f0c186c.

You might want to add your file as a bitcode test, if that makes sense from a license / size perspective. That would make sure it doesn't break in the future :)

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

 
 using namespace llvm;
 
 static cl::opt<bool> PrintSummaryGUIDs(
     "print-summary-global-ids", cl::init(false), cl::Hidden,
     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 {
   SWITCH_INST_MAGIC = 0x4B5 // May 2012 => 1205 => Hex
 };
 
 } // end anonymous namespace
 
BitcodeReaderBase::readNameFromStrtab(ArrayRef<uint64_t> Record) {
   // Invalid reference. Let the caller complain about the record being empty.
   if (Record[0] + Record[1] > Strtab.size())
     return {"", {}};
   return {StringRef(Strtab.data() + Record[0], Record[1]), Record.slice(2)};
 }
 
 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;
   // Next offset to start scanning for lazy parsing of function bodies.
   uint64_t NextUnreadBit = 0;
   // Last function offset found in the VST.
   uint64_t LastFunctionBlockBit = 0;
   bool SeenValueSymbolTable = false;
class BitcodeReader : public BitcodeReaderBase, public GVMaterializer {
   /// In some cases, we need to create a type ID for a type that was not
   /// explicitly encoded in the bitcode, or we don't know about at the current
   /// point. For example, a global may explicitly encode the value type ID, but
   /// not have a type ID for the pointer to value type, for which we create a
   /// virtual type ID instead. This map stores the new type ID that was created
   /// 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;
   DenseSet<GlobalObject *> ImplicitComdatObjects;
   SmallVector<Instruction *, 64> InstructionList;
 
   std::vector<std::pair<GlobalVariable *, unsigned>> GlobalInits;
   std::vector<std::pair<GlobalValue *, unsigned>> IndirectSymbolInits;
private:
 
   static constexpr unsigned InvalidTypeID = ~0u;
 
   Type *getTypeByID(unsigned ID);
   Type *getPtrElementTypeByID(unsigned ID);
   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) {
     return MDLoader->getMetadataFwdRefOrLoad(ID);
   }
 
   BasicBlock *getBasicBlock(unsigned ID) const {
     if (ID >= FunctionBBs.size()) return nullptr; // Invalid ID
     return FunctionBBs[ID];
   }
 
   AttributeList getAttributes(unsigned i) const {
     if (i-1 < MAttributes.size())
       return MAttributes[i-1];
     return AttributeList();
   }
 
   /// Read a value/type pair out of the specified record from slot 'Slot'.
   /// 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.
     if (UseRelativeIDs)
       ValNo = InstNum - ValNo;
     if (ValNo < InstNum) {
       // 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;
     }
     if (Slot == Record.size())
       return true;
 
     TypeID = (unsigned)Record[Slot++];
-    ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID);
+    ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID,
+                            ConstExprInsertBB);
     return ResVal == nullptr;
   }
 
   /// Read a value out of the specified record from slot 'Slot'. Increment Slot
   /// 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;
     return false;
   }
 
   /// 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
   /// corresponding argument's pointee type. Also upgrades intrinsics that now
   /// require an elementtype attribute.
   Error propagateAttributeTypes(CallBase *CB, ArrayRef<unsigned> ArgsTys);
 
   /// Converts alignment exponent (i.e. power of two (or zero)) to the
#endif
   unsigned TypeID = TypeList.size();
   TypeList.push_back(Ty);
   if (!ChildTypeIDs.empty())
     append_range(ContainedTypeIDs[TypeID], ChildTypeIDs);
   VirtualTypeIDs.insert({CacheKey, TypeID});
   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;
+    }
+
+    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 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);
   IdentifiedStructTypes.push_back(Ret);
   return Ret;
 }
 
 StructType *BitcodeReader::createIdentifiedStructType(LLVMContext &Context) {
Error BitcodeReader::resolveGlobalAndIndirectSymbolInits() {
   FunctionOperandWorklist.swap(FunctionOperands);
 
   while (!GlobalInitWorklist.empty()) {
     unsigned ValID = GlobalInitWorklist.back().second;
     if (ValID >= ValueList.size()) {
       // 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();
   }
 
   while (!IndirectSymbolInitWorklist.empty()) {
     unsigned ValID = IndirectSymbolInitWorklist.back().second;
     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())
           return error("Alias and aliasee types don't match");
         GA->setAliasee(C);
       } else if (auto *GI = dyn_cast<GlobalIFunc>(GV)) {
         Type *ResolverFTy =
             GlobalIFunc::getResolverFunctionType(GI->getValueType());
         // Transparently fix up the type for compatiblity with older bitcode
         GI->setResolver(
             ConstantExpr::getBitCast(C, ResolverFTy->getPointerTo()));
       } else {
         return error("Expected an alias or an ifunc");
       }
     }
     IndirectSymbolInitWorklist.pop_back();
   }
 
   while (!FunctionOperandWorklist.empty()) {
     FunctionOperandInfo &Info = FunctionOperandWorklist.back();
     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;
       }
     }
     if (Info.PersonalityFn || Info.Prefix || Info.Prologue)
       FunctionOperands.push_back(Info);
     FunctionOperandWorklist.pop_back();
   }
 
Error BitcodeReader::parseConstants() {
 
   // Read all the records for this value table.
   Type *CurTy = Type::getInt32Ty(Context);
   unsigned Int32TyID = getVirtualTypeID(CurTy);
   unsigned CurTyID = Int32TyID;
   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)
       return MaybeEntry.takeError();
     BitstreamEntry Entry = MaybeEntry.get();
 
     switch (Entry.Kind) {
     case BitstreamEntry::SubBlock: // Handled for us already.
     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.
       break;
     }
 
     // Read a record.
     Record.clear();
case bitc::CST_CODE_FLOAT: {    // FLOAT: [fpval]
       break;
     }
 
     case bitc::CST_CODE_AGGREGATE: {// AGGREGATE: [n x value number]
       if (Record.empty())
         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;
+        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);
       }
       break;
     }
     case bitc::CST_CODE_STRING:    // STRING: [values]
     case bitc::CST_CODE_CSTRING: { // CSTRING: [values]
       if (Record.empty())
while (true) {
     }
     case bitc::CST_CODE_CE_UNOP: {  // CE_UNOP: [opcode, opval]
       if (Record.size() < 2)
         return error("Invalid unary op constexpr record");
       int Opc = getDecodedUnaryOpcode(Record[0], CurTy);
       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;
     }
     case bitc::CST_CODE_CE_BINOP: {  // CE_BINOP: [opcode, opval, opval]
       if (Record.size() < 3)
         return error("Invalid binary op constexpr record");
       int Opc = getDecodedBinaryOpcode(Record[0], CurTy);
       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 ||
               Opc == Instruction::Mul ||
               Opc == Instruction::Shl) {
             if (Record[3] & (1 << bitc::OBO_NO_SIGNED_WRAP))
               Flags |= OverflowingBinaryOperator::NoSignedWrap;
             if (Record[3] & (1 << bitc::OBO_NO_UNSIGNED_WRAP))
               Flags |= OverflowingBinaryOperator::NoUnsignedWrap;
           } else if (Opc == Instruction::SDiv ||
                      Opc == Instruction::UDiv ||
                      Opc == Instruction::LShr ||
                      Opc == Instruction::AShr) {
             if (Record[3] & (1 << bitc::PEO_EXACT))
               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;
     }
     case bitc::CST_CODE_CE_CAST: {  // CE_CAST: [opcode, opty, opval]
       if (Record.size() < 3)
         return error("Invalid cast constexpr record");
       int Opc = getDecodedCastOpcode(Record[0]);
       if (Opc < 0) {
         V = UndefValue::get(CurTy);  // Unknown cast.
       } else {
         unsigned OpTyID = Record[1];
         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;
     }
     case bitc::CST_CODE_CE_INBOUNDS_GEP: // [ty, n x operands]
     case bitc::CST_CODE_CE_GEP: // [ty, n x operands]
     case bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX: { // [ty, flags, n x
                                                      // operands]
       if (Record.size() < 2)
         return error("Constant GEP record must have at least two elements");
       unsigned OpNum = 0;
       Type *PointeeType = nullptr;
       if (BitCode == bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX ||
           Record.size() % 2)
         PointeeType = getTypeByID(Record[OpNum++]);
 
       bool InBounds = false;
       Optional<unsigned> InRangeIndex;
       if (BitCode == bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX) {
         uint64_t Op = Record[OpNum++];
         InBounds = Op & 1;
         InRangeIndex = Op >> 1;
       } 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)
         return error("Invalid gep with no operands");
 
       Type *BaseType = getTypeByID(BaseTypeID);
       if (isa<VectorType>(BaseType)) {
         BaseTypeID = getContainedTypeID(BaseTypeID, 0);
         BaseType = getTypeByID(BaseTypeID);
       }
 
       PointerType *OrigPtrTy = dyn_cast_or_null<PointerType>(BaseType);
       if (!OrigPtrTy)
         return error("GEP base operand must be pointer or vector of pointer");
 
       if (!PointeeType) {
         PointeeType = getPtrElementTypeByID(BaseTypeID);
         if (!PointeeType)
           return error("Missing element type for old-style constant GEP");
       } else if (!OrigPtrTy->isOpaqueOrPointeeTypeMatches(PointeeType))
         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]
       if (Record.size() < 3)
         return error("Invalid extractelement constexpr record");
       unsigned OpTyID = Record[0];
       VectorType *OpTy =
         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
         : { // CE_INSERTELT: [opval, opval, opty, opval]
       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);
       VectorType *OpTy =
         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)
         return error("Invalid cmp constexpt record");
       unsigned OpTyID = Record[0];
       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.
     // Deprecated, but still needed to read old bitcode files.
     case bitc::CST_CODE_INLINEASM_OLD: {
       if (Record.size() < 2)
         return error("Invalid inlineasm record");
       std::string AsmStr, ConstrStr;
while (true) {
     }
     case bitc::CST_CODE_BLOCKADDRESS:{
       if (Record.size() < 3)
         return error("Invalid blockaddress record");
       unsigned FnTyID = Record[0];
       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: {
       if (Record.size() < 2)
         return error("Invalid dso_local record");
       unsigned GVTyID = Record[0];
       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: {
       if (Record.size() < 2)
         return error("Invalid no_cfi record");
       unsigned GVTyID = Record[0];
       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;
     }
     }
 
     assert(V->getType() == getTypeByID(CurTyID) && "Incorrect result type ID");
     if (Error Err = ValueList.assignValue(NextCstNo, V, CurTyID))
       return Err;
     ++NextCstNo;
for (Argument &I : F->args()) {
     assert(I.getType() == getTypeByID(ArgTyID) &&
            "Incorrect fully specified type for Function Argument");
     ValueList.push_back(&I, ArgTyID);
     ++ArgNo;
   }
   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 * {
     if (CurBB && !CurBB->empty())
       return &CurBB->back();
     else if (CurBBNo && FunctionBBs[CurBBNo - 1] &&
              !FunctionBBs[CurBBNo - 1]->empty())
       return &FunctionBBs[CurBBNo - 1]->back();
case bitc::FUNC_CODE_DEBUG_LOC: {      // DEBUG_LOC: [line, col, scope, ia]
       I->setDebugLoc(LastLoc);
       I = nullptr;
       continue;
     }
     case bitc::FUNC_CODE_INST_UNOP: {    // UNOP: [opval, ty, opcode]
       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");
 
       int Opc = getDecodedUnaryOpcode(Record[OpNum++], LHS->getType());
       if (Opc == -1)
         return error("Invalid record");
       I = UnaryOperator::Create((Instruction::UnaryOps)Opc, LHS);
       ResTypeID = TypeID;
       InstructionList.push_back(I);
       if (OpNum < Record.size()) {
         if (isa<FPMathOperator>(I)) {
           FastMathFlags FMF = getDecodedFastMathFlags(Record[OpNum]);
           if (FMF.any())
             I->setFastMathFlags(FMF);
         }
       }
       break;
     }
     case bitc::FUNC_CODE_INST_BINOP: {    // BINOP: [opval, ty, opval, opcode]
       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");
 
       int Opc = getDecodedBinaryOpcode(Record[OpNum++], LHS->getType());
       if (Opc == -1)
         return error("Invalid record");
       I = BinaryOperator::Create((Instruction::BinaryOps)Opc, LHS, RHS);
       ResTypeID = TypeID;
case bitc::FUNC_CODE_INST_BINOP: {    // BINOP: [opval, ty, opval, opcode]
 
       }
       break;
     }
     case bitc::FUNC_CODE_INST_CAST: {    // CAST: [opval, opty, destty, castopc]
       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");
 
       ResTypeID = Record[OpNum];
       Type *ResTy = getTypeByID(ResTypeID);
       int Opc = getDecodedCastOpcode(Record[OpNum + 1]);
       if (Opc == -1 || !ResTy)
         return error("Invalid record");
case bitc::FUNC_CODE_INST_GEP: { // GEP: type, [n x operands]
       } else {
         InBounds = BitCode == bitc::FUNC_CODE_INST_INBOUNDS_GEP_OLD;
         TyID = InvalidTypeID;
         Ty = nullptr;
       }
 
       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) {
         TyID = getContainedTypeID(BasePtrTypeID);
         if (BasePtr->getType()->isVectorTy())
           TyID = getContainedTypeID(TyID);
         Ty = getTypeByID(TyID);
       } else if (!cast<PointerType>(BasePtr->getType()->getScalarType())
                       ->isOpaqueOrPointeeTypeMatches(Ty)) {
         return error(
             "Explicit gep type does not match pointee type of pointer operand");
       }
 
       SmallVector<Value*, 16> GEPIdx;
       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);
       }
 
       I = GetElementPtrInst::Create(Ty, BasePtr, GEPIdx);
 
       ResTypeID = TyID;
       if (cast<GEPOperator>(I)->getNumIndices() != 0) {
case bitc::FUNC_CODE_INST_GEP: { // GEP: type, [n x operands]
       break;
     }
 
     case bitc::FUNC_CODE_INST_EXTRACTVAL: {
                                        // EXTRACTVAL: [opty, opval, n x indices]
       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();
 
       unsigned RecSize = Record.size();
       if (OpNum == RecSize)
         return error("EXTRACTVAL: Invalid instruction with 0 indices");
 
       SmallVector<unsigned, 4> EXTRACTVALIdx;
case bitc::FUNC_CODE_INST_EXTRACTVAL: {
       break;
     }
 
     case bitc::FUNC_CODE_INST_INSERTVAL: {
                            // INSERTVAL: [opty, opval, opty, opval, n x indices]
       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();
       if (OpNum == RecSize)
         return error("INSERTVAL: Invalid instruction with 0 indices");
 
       SmallVector<unsigned, 4> INSERTVALIdx;
       Type *CurTy = Agg->getType();
while (true) {
 
     case bitc::FUNC_CODE_INST_SELECT: { // SELECT: [opval, ty, opval, opval]
       // obsolete form of select
       // handles select i1 ... in old bitcode
       unsigned OpNum = 0;
       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);
       ResTypeID = TypeID;
       InstructionList.push_back(I);
       break;
     }
 
     case bitc::FUNC_CODE_INST_VSELECT: {// VSELECT: [ty,opval,opval,predty,pred]
       // new form of select
       // handles select i1 or select [N x i1]
       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]
       if (VectorType* vector_type =
           dyn_cast<VectorType>(Cond->getType())) {
         // expect <n x i1>
         if (vector_type->getElementType() != Type::getInt1Ty(Context))
           return error("Invalid type for value");
case bitc::FUNC_CODE_INST_VSELECT: {// VSELECT: [ty,opval,opval,predty,pred]
       }
       break;
     }
 
     case bitc::FUNC_CODE_INST_EXTRACTELT: { // EXTRACTELT: [opty, opval, opval]
       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");
       I = ExtractElementInst::Create(Vec, Idx);
       ResTypeID = getContainedTypeID(VecTypeID);
       InstructionList.push_back(I);
       break;
     }
 
     case bitc::FUNC_CODE_INST_INSERTELT: { // INSERTELT: [ty, opval,opval,opval]
       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;
       InstructionList.push_back(I);
       break;
     }
 
     case bitc::FUNC_CODE_INST_SHUFFLEVEC: {// SHUFFLEVEC: [opval,ty,opval,opval]
       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");
 
       I = new ShuffleVectorInst(Vec1, Vec2, Mask);
       ResTypeID =
           getVirtualTypeID(I->getType(), getContainedTypeID(Vec1TypeID));
       InstructionList.push_back(I);
       break;
     }
 
     case bitc::FUNC_CODE_INST_CMP:   // CMP: [opty, opval, opval, pred]
       // Old form of ICmp/FCmp returning bool
       // Existed to differentiate between icmp/fcmp and vicmp/vfcmp which were
       // both legal on vectors but had different behaviour.
     case bitc::FUNC_CODE_INST_CMP2: { // CMP2: [opty, opval, opval, pred]
       // FCmp/ICmp returning bool or vector of bool
 
       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())
         return error(
             "Invalid record: operand number exceeded available operands");
 
       unsigned PredVal = Record[OpNum];
       bool IsFP = LHS->getType()->isFPOrFPVectorTy();
case bitc::FUNC_CODE_INST_RET: // RET: [opty,opval<optional>]
           I = ReturnInst::Create(Context);
           InstructionList.push_back(I);
           break;
         }
 
         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");
 
         I = ReturnInst::Create(Context, Op);
         InstructionList.push_back(I);
         break;
       }
     case bitc::FUNC_CODE_INST_BR: { // BR: [bb#, bb#, opval] or [bb#]
       if (Record.size() != 1 && Record.size() != 3)
         return error("Invalid record");
       BasicBlock *TrueDest = getBasicBlock(Record[0]);
       if (!TrueDest)
         return error("Invalid record");
 
       if (Record.size() == 1) {
         I = BranchInst::Create(TrueDest);
         InstructionList.push_back(I);
       }
       else {
         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);
         InstructionList.push_back(I);
       }
       break;
     }
     case bitc::FUNC_CODE_INST_CLEANUPRET: { // CLEANUPRET: [val] or [val,bb#]
       if (Record.size() != 1 && Record.size() != 2)
         return error("Invalid record");
       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;
       if (Record.size() == 2) {
         UnwindDest = getBasicBlock(Record[Idx++]);
         if (!UnwindDest)
           return error("Invalid record");
       }
 
       I = CleanupReturnInst::Create(CleanupPad, UnwindDest);
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_CATCHRET: { // CATCHRET: [val,bb#]
       if (Record.size() != 2)
         return error("Invalid record");
       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++]);
       if (!BB)
         return error("Invalid record");
 
       I = CatchReturnInst::Create(CatchPad, BB);
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_CATCHSWITCH: { // CATCHSWITCH: [tok,num,(bb)*,bb?]
       // We must have, at minimum, the outer scope and the number of arguments.
       if (Record.size() < 2)
         return error("Invalid record");
 
       unsigned Idx = 0;
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumHandlers = Record[Idx++];
 
       SmallVector<BasicBlock *, 2> Handlers;
       for (unsigned Op = 0; Op != NumHandlers; ++Op) {
         BasicBlock *BB = getBasicBlock(Record[Idx++]);
         if (!BB)
           return error("Invalid record");
case bitc::FUNC_CODE_INST_CLEANUPPAD: { // [tok,num,(ty,val)*]
       // We must have, at minimum, the outer scope and the number of arguments.
       if (Record.size() < 2)
         return error("Invalid record");
 
       unsigned Idx = 0;
 
       Type *TokenTy = Type::getTokenTy(Context);
       Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy,
-                                  getVirtualTypeID(TokenTy));
+                                  getVirtualTypeID(TokenTy), CurBB);
 
       unsigned NumArgOperands = Record[Idx++];
 
       SmallVector<Value *, 2> Args;
       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);
       }
 
       if (Record.size() != Idx)
         return error("Invalid record");
 
       if (BitCode == bitc::FUNC_CODE_INST_CLEANUPPAD)
case bitc::FUNC_CODE_INST_SWITCH: { // SWITCH: [opty, op0, op1, ...]
         // format were reverted but we still recognize bitcode that uses it.
         // Hopefully someday we will have support for case ranges and can use
         // this format again.
 
         unsigned OpTyID = Record[1];
         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");
 
         unsigned NumCases = Record[4];
 
         SwitchInst *SI = SwitchInst::Create(Cond, Default, NumCases);
         InstructionList.push_back(SI);
case bitc::FUNC_CODE_INST_SWITCH: { // SWITCH: [opty, op0, op1, ...]
       }
 
       // Old SwitchInst format without case ranges.
 
       if (Record.size() < 3 || (Record.size() & 1) == 0)
         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");
       unsigned NumCases = (Record.size()-3)/2;
       SwitchInst *SI = SwitchInst::Create(Cond, Default, NumCases);
       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;
           return error("Invalid record");
         }
         SI->addCase(CaseVal, DestBB);
       }
       I = SI;
       break;
     }
     case bitc::FUNC_CODE_INST_INDIRECTBR: { // INDIRECTBR: [opty, op0, op1, ...]
       if (Record.size() < 2)
         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;
       IndirectBrInst *IBI = IndirectBrInst::Create(Address, NumDests);
       InstructionList.push_back(IBI);
       for (unsigned i = 0, e = NumDests; i != e; ++i) {
         if (BasicBlock *DestBB = getBasicBlock(Record[2+i])) {
           IBI->addDestination(DestBB);
case bitc::FUNC_CODE_INST_INVOKE: {
         FTyID = Record[OpNum++];
         FTy = dyn_cast<FunctionType>(getTypeByID(FTyID));
         if (!FTy)
           return error("Explicit invoke type is not a function type");
       }
 
       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());
       if (!CalleeTy)
         return error("Callee is not a pointer");
       if (!FTy) {
         FTyID = getContainedTypeID(CalleeTypeID);
         FTy = dyn_cast_or_null<FunctionType>(getTypeByID(FTyID));
         if (!FTy)
           return error("Callee is not of pointer to function type");
       } else if (!CalleeTy->isOpaqueOrPointeeTypeMatches(FTy))
         return error("Explicit invoke type does not match pointee type of "
                      "callee operand");
       if (Record.size() < FTy->getNumParams() + OpNum)
         return error("Insufficient operands to call");
 
       SmallVector<Value*, 16> Ops;
       SmallVector<unsigned, 16> ArgTyIDs;
       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");
       }
 
       if (!FTy->isVarArg()) {
         if (Record.size() != OpNum)
           return error("Invalid record");
       } else {
         // Read type/value pairs for varargs params.
         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);
         }
       }
 
       // Upgrade the bundles if needed.
       if (!OperandBundles.empty())
case bitc::FUNC_CODE_INST_INVOKE: {
       }
 
       break;
     }
     case bitc::FUNC_CODE_INST_RESUME: { // RESUME: [opval]
       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);
       break;
     }
     case bitc::FUNC_CODE_INST_CALLBR: {
       // CALLBR: [attr, cc, norm, transfs, fty, fnid, args]
       unsigned OpNum = 0;
case bitc::FUNC_CODE_INST_CALLBR: {
         FTyID = Record[OpNum++];
         FTy = dyn_cast_or_null<FunctionType>(getTypeByID(FTyID));
         if (!FTy)
           return error("Explicit call type is not a function type");
       }
 
       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());
       if (!OpTy)
         return error("Callee is not a pointer type");
       if (!FTy) {
         FTyID = getContainedTypeID(CalleeTypeID);
         FTy = dyn_cast_or_null<FunctionType>(getTypeByID(FTyID));
case bitc::FUNC_CODE_INST_CALLBR: {
       // Read the fixed params.
       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
         Value *Arg;
         unsigned ArgTyID = getContainedTypeID(FTyID, i + 1);
         if (FTy->getParamType(i)->isLabelTy())
           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);
         ArgTyIDs.push_back(ArgTyID);
       }
 
       // Read type/value pairs for varargs params.
       if (!FTy->isVarArg()) {
         if (OpNum != Record.size())
           return error("Invalid record");
       } else {
         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);
         }
       }
 
       // Upgrade the bundles if needed.
       if (!OperandBundles.empty())
case bitc::FUNC_CODE_INST_PHI: { // PHI: [ty, val0,bb0, ...]
       size_t NumArgs = (Record.size() - 1) / 2;
       PHINode *PN = PHINode::Create(Ty, NumArgs);
       if ((Record.size() - 1) % 2 == 1 && !isa<FPMathOperator>(PN)) {
         PN->deleteValue();
         return error("Invalid phi record");
       }
       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;
 
       // If there are an even number of records, the final record must be FMF.
       if (Record.size() % 2 == 0) {
         assert(isa<FPMathOperator>(I) && "Unexpected phi type");
         FastMathFlags FMF = getDecodedFastMathFlags(Record[Record.size() - 1]);
case bitc::FUNC_CODE_INST_LANDINGPAD_OLD: {
       }
       ResTypeID = Record[Idx++];
       Type *Ty = getTypeByID(ResTypeID);
       if (!Ty)
         return error("Invalid record");
       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())
           F->setPersonalityFn(cast<Constant>(PersFn));
         else if (F->getPersonalityFn() != cast<Constant>(PersFn))
           return error("Personality function mismatch");
       }
 
       bool IsCleanup = !!Record[Idx++];
       unsigned NumClauses = Record[Idx++];
       LandingPadInst *LP = LandingPadInst::Create(Ty, NumClauses);
       LP->setCleanup(IsCleanup);
       for (unsigned J = 0; J != NumClauses; ++J) {
         LandingPadInst::ClauseType CT =
           LandingPadInst::ClauseType(Record[Idx++]); (void)CT;
         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");
         }
 
         assert((CT != LandingPadInst::Catch ||
                 !isa<ArrayType>(Val->getType())) &&
                "Catch clause has a invalid type!");
         assert((CT != LandingPadInst::Filter ||
case bitc::FUNC_CODE_INST_ALLOCA: { // ALLOCA: [instty, opty, op, align]
       if (!Bitfield::get<APV::ExplicitType>(Rec)) {
         TyID = getContainedTypeID(TyID);
         Ty = getTypeByID(TyID);
         if (!Ty)
           return error("Missing element type for old-style alloca");
       }
       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) |
           (Bitfield::get<APV::AlignUpper>(Rec) << APV::AlignLower::Bits);
       if (Error Err = parseAlignmentValue(AlignExp, Align)) {
         return Err;
       }
       if (!Ty || !Size)
case bitc::FUNC_CODE_INST_ALLOCA: { // ALLOCA: [instty, opty, op, align]
       ResTypeID = getVirtualTypeID(AI->getType(), TyID);
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_LOAD: { // LOAD: [opty, op, align, vol]
       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");
 
       if (!isa<PointerType>(Op->getType()))
         return error("Load operand is not a pointer type");
 
       Type *Ty = nullptr;
       if (OpNum + 3 == Record.size()) {
case bitc::FUNC_CODE_INST_LOAD: { // LOAD: [opty, op, align, vol]
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_LOADATOMIC: {
        // LOADATOMIC: [opty, op, align, vol, ordering, ssid]
       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");
 
       if (!isa<PointerType>(Op->getType()))
         return error("Load operand is not a pointer type");
 
       Type *Ty = nullptr;
       if (OpNum + 5 == Record.size()) {
case bitc::FUNC_CODE_INST_LOADATOMIC: {
       InstructionList.push_back(I);
       break;
     }
     case bitc::FUNC_CODE_INST_STORE:
     case bitc::FUNC_CODE_INST_STORE_OLD: { // STORE2:[ptrty, ptr, val, align, vol]
       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");
       }
 
       if (OpNum + 2 != Record.size())
         return error("Invalid record");
 
       if (Error Err = typeCheckLoadStoreInst(Val->getType(), Ptr->getType()))
         return Err;
case bitc::FUNC_CODE_INST_STORE_OLD: { // STORE2:[ptrty, ptr, val, align, vol]
       break;
     }
     case bitc::FUNC_CODE_INST_STOREATOMIC:
     case bitc::FUNC_CODE_INST_STOREATOMIC_OLD: {
       // STOREATOMIC: [ptrty, ptr, val, align, vol, ordering, ssid]
       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");
       }
 
       if (OpNum + 4 != Record.size())
         return error("Invalid record");
 
       if (Error Err = typeCheckLoadStoreInst(Val->getType(), Ptr->getType()))
         return Err;

     }
     case bitc::FUNC_CODE_INST_CMPXCHG_OLD: {
       // CMPXCHG_OLD: [ptrty, ptr, cmp, val, vol, ordering, synchscope,
       // failure_ordering?, weak?]
       const size_t NumRecords = Record.size();
       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()))
         return error("Cmpxchg operand is not a pointer type");
 
       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");
 
       const AtomicOrdering SuccessOrdering =
           getDecodedOrdering(Record[OpNum + 1]);
       if (SuccessOrdering == AtomicOrdering::NotAtomic ||
           SuccessOrdering == AtomicOrdering::Unordered)
         return error("Invalid record");

     }
     case bitc::FUNC_CODE_INST_CMPXCHG: {
       // CMPXCHG: [ptrty, ptr, cmp, val, vol, success_ordering, synchscope,
       // failure_ordering, weak, align?]
       const size_t NumRecords = Record.size();
       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()))
         return error("Cmpxchg operand is not a pointer type");
 
       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)
         return error("Invalid record");
 
       const bool IsVol = Record[OpNum];
 
       const AtomicOrdering SuccessOrdering =

     case bitc::FUNC_CODE_INST_ATOMICRMW: {
       // ATOMICRMW_OLD: [ptrty, ptr, val, op, vol, ordering, ssid, align?]
       // ATOMICRMW: [ptrty, ptr, valty, val, op, vol, ordering, ssid, align?]
       const size_t NumRecords = Record.size();
       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()))
         return error("Invalid record");
 
       Value *Val = nullptr;
       unsigned ValTypeID = InvalidTypeID;
       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");
       }
 
       if (!(NumRecords == (OpNum + 4) || NumRecords == (OpNum + 5)))
         return error("Invalid record");
 
       const AtomicRMWInst::BinOp Operation =
           getDecodedRMWOperation(Record[OpNum]);
case bitc::FUNC_CODE_INST_CALL: {
         FTyID = Record[OpNum++];
         FTy = dyn_cast_or_null<FunctionType>(getTypeByID(FTyID));
         if (!FTy)
           return error("Explicit call type is not a function type");
       }
 
       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());
       if (!OpTy)
         return error("Callee is not a pointer type");
       if (!FTy) {
         FTyID = getContainedTypeID(CalleeTypeID);
         FTy = dyn_cast_or_null<FunctionType>(getTypeByID(FTyID));
case bitc::FUNC_CODE_INST_CALL: {
       SmallVector<unsigned, 16> ArgTyIDs;
       // Read the fixed params.
       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
         unsigned ArgTyID = getContainedTypeID(FTyID, i + 1);
         if (FTy->getParamType(i)->isLabelTy())
           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");
       }
 
       // Read type/value pairs for varargs params.
       if (!FTy->isVarArg()) {
         if (OpNum != Record.size())
           return error("Invalid record");
       } else {
         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);
         }
       }
 
       // Upgrade the bundles if needed.
       if (!OperandBundles.empty())
case bitc::FUNC_CODE_INST_CALL: {
       }
       break;
     }
     case bitc::FUNC_CODE_INST_VAARG: { // VAARG: [valistty, valist, instty]
       if (Record.size() < 3)
         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)
         return error("Invalid record");
       I = new VAArgInst(Op, ResTy);
       InstructionList.push_back(I);
       break;
     }
 
     case bitc::FUNC_CODE_OPERAND_BUNDLE: {
       // A call or an invoke can be optionally prefixed with some variable
       // number of operand bundle blocks.  These blocks are read into
       // OperandBundles and consumed at the next call or invoke instruction.
 
       if (Record.empty() || Record[0] >= BundleTags.size())
         return error("Invalid record");
 
       std::vector<Value *> Inputs;
 
       unsigned OpNum = 1;
       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);
       }
 
       OperandBundles.emplace_back(BundleTags[Record[0]], std::move(Inputs));
       continue;
     }
 
     case bitc::FUNC_CODE_INST_FREEZE: { // FREEZE: [opty,opval]
       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");
 
       I = new FreezeInst(Op);
       ResTypeID = OpTypeID;
       InstructionList.push_back(I);
       break;
if (!A->getParent()) {
       return error("Never resolved value found in function");
     }
   }
 
   // Unexpected unresolved metadata about to be dropped.
   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);
   std::vector<BasicBlock*>().swap(FunctionBBs);
   return Error::success();
 }
 
 /// Find the function body in the bitcode stream

llvm/lib/Bitcode/Reader/ValueList.h

 class LLVMContext;
 class Type;
 class Value;
 
 class BitcodeReaderValueList {
   /// 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
   /// maximum must be invalid.
   unsigned RefsUpperBound;
 
 public:
   BitcodeReaderValueList(LLVMContext &C, size_t RefsUpperBound)
       : Context(C),
         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) {
     ValuePtrs.resize(N);
   }
   void push_back(Value *V, unsigned TypeID) {
     ValuePtrs.emplace_back(V, TypeID);
   }
 
   void clear() {
-    assert(ResolveConstants.empty() && "Constants not resolved?");
     ValuePtrs.clear();
   }
 
   Value *operator[](unsigned i) const {
     assert(i < ValuePtrs.size());
     return ValuePtrs[i].first;
   }
 
   unsigned getTypeID(unsigned ValNo) const {
     assert(ValNo < ValuePtrs.size());
     return ValuePtrs[ValNo].second;
   }
 
   Value *back() const { return ValuePtrs.back().first; }
   void pop_back() {
     ValuePtrs.pop_back();
   }
   bool empty() const { return ValuePtrs.empty(); }
 
   void shrinkTo(unsigned N) {
     assert(N <= size() && "Invalid shrinkTo request!");
     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;
+  }
+
   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
 
 #endif // LLVM_LIB_BITCODE_READER_VALUELIST_H

llvm/lib/Bitcode/Reader/ValueList.cpp

 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cstddef>
 
 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()) {
     push_back(V, TypeID);
     return Error::success();
   }
 
   if (Idx >= size())
     resize(Idx + 1);
 
   auto &Old = ValuePtrs[Idx];
   if (!Old.first) {
     Old.first = V;
     Old.second = TypeID;
     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");
   return Error::success();
 }
 
-Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty,
-                                                    unsigned TyID) {
-  // Bail out for a clearly invalid value.
-  if (Idx >= RefsUpperBound)
-    return nullptr;
-
-  if (Idx >= size())
-    resize(Idx + 1);
-
-  if (Value *V = ValuePtrs[Idx].first) {
-    if (Ty != V->getType())
-      report_fatal_error("Type mismatch in constant table!");
-    return cast<Constant>(V);
-  }
-
-  // Create and return a placeholder, which will later be RAUW'd.
-  Constant *C = new ConstantPlaceHolder(Ty, Context);
-  ValuePtrs[Idx] = {C, TyID};
-  return C;
-}
-
 Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
                                               unsigned TyID) {
   // Bail out for a clearly invalid value.
   if (Idx >= RefsUpperBound)
     return nullptr;
 
   if (Idx >= size())
     resize(Idx + 1);
Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty,
   if (!Ty)
     return nullptr;
 
   // Create and return a placeholder, which will later be RAUW'd.
   Value *V = new Argument(Ty);
   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);
-  }
-}

llvm/lib/Bitcode/Writer/ValueEnumerator.cpp

 #include <tuple>
 
 using namespace llvm;
 
 namespace {
 
 struct OrderMap {
   DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
-  unsigned LastGlobalConstantID = 0;
   unsigned LastGlobalValueID = 0;
 
   OrderMap() = default;
 
-  bool isGlobalConstant(unsigned ID) const {
-    return ID <= LastGlobalConstantID;
-  }
-
   bool isGlobalValue(unsigned ID) const {
-    return ID <= LastGlobalValueID && !isGlobalConstant(ID);
+    return ID <= LastGlobalValueID;
   }
 
   unsigned size() const { return IDs.size(); }
   std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
 
   std::pair<unsigned, bool> lookup(const Value *V) const {
     return IDs.lookup(V);
   }
 
   void index(const Value *V) {
     // Explicitly sequence get-size and insert-value operations to avoid UB.
     unsigned ID = IDs.size() + 1;
     IDs[V].first = ID;
   }
 };
 
 } // end anonymous namespace
 
 static void orderValue(const Value *V, OrderMap &OM) {
   if (OM.lookup(V).first)
     return;
 
   if (const Constant *C = dyn_cast<Constant>(V)) {
-    if (C->getNumOperands() && !isa<GlobalValue>(C)) {
+    if (C->getNumOperands()) {
       for (const Value *Op : C->operands())
         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
           orderValue(Op, OM);
       if (auto *CE = dyn_cast<ConstantExpr>(C))
         if (CE->getOpcode() == Instruction::ShuffleVector)
           orderValue(CE->getShuffleMaskForBitcode(), OM);
     }
   }
 
   // Note: we cannot cache this lookup above, since inserting into the map
   // changes the map's size, and thus affects the other IDs.
   OM.index(V);
 }
 
 static OrderMap orderModule(const Module &M) {
   // This needs to match the order used by ValueEnumerator::ValueEnumerator()
   // and ValueEnumerator::incorporateFunction().
   OrderMap OM;
 
-  // In the reader, initializers of GlobalValues are set *after* all the
-  // globals have been read.  Rather than awkwardly modeling this behaviour
-  // directly in predictValueUseListOrderImpl(), just assign IDs to
-  // initializers of GlobalValues before GlobalValues themselves to model this
-  // implicitly.
-  for (const GlobalVariable &G : M.globals())
-    if (G.hasInitializer())
-      if (!isa<GlobalValue>(G.getInitializer()))
-        orderValue(G.getInitializer(), OM);
-  for (const GlobalAlias &A : M.aliases())
-    if (!isa<GlobalValue>(A.getAliasee()))
-      orderValue(A.getAliasee(), OM);
-  for (const GlobalIFunc &I : M.ifuncs())
-    if (!isa<GlobalValue>(I.getResolver()))
-      orderValue(I.getResolver(), OM);
-  for (const Function &F : M) {
-    for (const Use &U : F.operands())
-      if (!isa<GlobalValue>(U.get()))
-        orderValue(U.get(), OM);
-  }
+  // Initializers of GlobalValues are processed in
+  // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
+  // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
+  // by giving IDs in reverse order.
+  //
+  // Since GlobalValues never reference each other directly (just through
+  // initializers), their relative IDs only matter for determining order of
+  // uses in their initializers.
+  for (const GlobalVariable &G : reverse(M.globals()))
+    orderValue(&G, OM);
+  for (const GlobalAlias &A : reverse(M.aliases()))
+    orderValue(&A, OM);
+  for (const GlobalIFunc &I : reverse(M.ifuncs()))
+    orderValue(&I, OM);
+  for (const Function &F : reverse(M))
+    orderValue(&F, OM);
+  OM.LastGlobalValueID = OM.size();
 
   // As constants used in metadata operands are emitted as module-level
   // constants, we must order them before other operands. Also, we must order
   // these before global values, as these will be read before setting the
   // global values' initializers. The latter matters for constants which have
   // uses towards other constants that are used as initializers.
   auto orderConstantValue = [&OM](const Value *V) {
     if ((isa<Constant>(V) && !isa<GlobalValue>(V)) || isa<InlineAsm>(V))
for (const BasicBlock &BB : F)
             } else if (const auto *AL =
                            dyn_cast<DIArgList>(MAV->getMetadata())) {
               for (const auto *VAM : AL->getArgs())
                 orderConstantValue(VAM->getValue());
             }
           }
         }
   }
-  OM.LastGlobalConstantID = OM.size();
-
-  // Initializers of GlobalValues are processed in
-  // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
-  // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
-  // by giving IDs in reverse order.
-  //
-  // Since GlobalValues never reference each other directly (just through
-  // initializers), their relative IDs only matter for determining order of
-  // uses in their initializers.
-  for (const Function &F : M)
-    orderValue(&F, OM);
-  for (const GlobalAlias &A : M.aliases())
-    orderValue(&A, OM);
-  for (const GlobalIFunc &I : M.ifuncs())
-    orderValue(&I, OM);
-  for (const GlobalVariable &G : M.globals())
-    orderValue(&G, OM);
-  OM.LastGlobalValueID = OM.size();
 
   for (const Function &F : M) {
     if (F.isDeclaration())
       continue;
     // Here we need to match the union of ValueEnumerator::incorporateFunction()
     // and WriteFunction().  Basic blocks are implicitly declared before
     // anything else (by declaring their size).
     for (const BasicBlock &BB : F)
       orderValue(&BB, OM);
     for (const Argument &A : F.args())
       orderValue(&A, OM);
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB) {
         for (const Value *Op : I.operands())
           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
               isa<InlineAsm>(*Op))
             orderValue(Op, OM);
         if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
           orderValue(SVI->getShuffleMaskForBitcode(), OM);
-      }
-    for (const BasicBlock &BB : F)
-      for (const Instruction &I : BB)
         orderValue(&I, OM);
       }
+  }
   return OM;
 }
 
 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
                                          unsigned ID, const OrderMap &OM,
                                          UseListOrderStack &Stack) {
   // Predict use-list order for this one.
   using Entry = std::pair<const Use *, unsigned>;
llvm::sort(List, [&](const Entry &L, const Entry &R) {
     const Use *LU = L.first;
     const Use *RU = R.first;
     if (LU == RU)
       return false;
 
     auto LID = OM.lookup(LU->getUser()).first;
     auto RID = OM.lookup(RU->getUser()).first;
 
-    // Global values are processed in reverse order.
-    //
-    // Moreover, initializers of GlobalValues are set *after* all the globals
-    // have been read (despite having earlier IDs).  Rather than awkwardly
-    // modeling this behaviour here, orderModule() has assigned IDs to
-    // initializers of GlobalValues before GlobalValues themselves.
-    if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) {
-      if (LID == RID)
-        return LU->getOperandNo() > RU->getOperandNo();
-      return LID < RID;
-    }
-
     // If ID is 4, then expect: 7 6 5 1 2 3.
     if (LID < RID) {
       if (RID <= ID)
         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
           return true;
       return false;
     }
     if (RID < LID) {
for (const Function &F : llvm::reverse(M)) {
     for (const BasicBlock &BB : F)
       for (const Instruction &I : BB) {
         for (const Value *Op : I.operands())
           if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
             predictValueUseListOrder(Op, &F, OM, Stack);
         if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))
           predictValueUseListOrder(SVI->getShuffleMaskForBitcode(), &F, OM,
                                    Stack);
-      }
-    for (const BasicBlock &BB : F)
-      for (const Instruction &I : BB)
         predictValueUseListOrder(&I, &F, OM, Stack);
       }
+  }
 
   // Visit globals last, since the module-level use-list block will be seen
   // before the function bodies are processed.
   for (const GlobalVariable &G : M.globals())
     predictValueUseListOrder(&G, nullptr, OM, Stack);
   for (const Function &F : M)
     predictValueUseListOrder(&F, nullptr, OM, Stack);
   for (const GlobalAlias &A : M.aliases())

llvm/test/Bitcode/constexpr-to-instr.ll

+; 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
+}