Simplify representation of forward value references in bitcode.

Simplify instruction records by adding concept of a forward type reference
map that maps ValueID's to types. Used to generate forward reference types
for instruction arguments that need a type because the forward reference
has not yet been generated.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=3507
R=jvoung@chromium.org, mseaborn@chromium.org

Review URL: https://codereview.chromium.org/16963004

5 files changed, 173 insertions, 109 deletions

diff --git a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
index c38df6c9ad..8fe6274a15 100644
--- a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
+++ b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.cpp
@@ -282,7 +282,18 @@ Constant *NaClBitcodeReaderValueList::getConstantFwdRef(unsigned Idx,
   return C;
 }
 
-Value *NaClBitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty) {
+Value *NaClBitcodeReaderValueList::getValueFwdRef(unsigned Idx) {
+  if (Idx >= size())
+    return 0;
+
+  if (Value *V = ValuePtrs[Idx])
+    return V;
+
+  return 0;
+}
+
+Value *NaClBitcodeReaderValueList::getOrCreateValueFwdRef(
+    unsigned Idx, Type *Ty) {
   if (Idx >= size())
     resize(Idx + 1);
 
@@ -795,7 +806,7 @@ bool NaClBitcodeReader::ParseMetadata() {
         if (Ty->isMetadataTy())
           Elts.push_back(MDValueList.getValueFwdRef(Record[i+1]));
         else if (!Ty->isVoidTy())
-          Elts.push_back(ValueList.getValueFwdRef(Record[i+1], Ty));
+          Elts.push_back(ValueList.getOrCreateValueFwdRef(Record[i+1], Ty));
         else
           Elts.push_back(NULL);
       }
@@ -1840,10 +1851,11 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       continue;
     }
 
-    case naclbitc::FUNC_CODE_INST_BINOP: {    // BINOP: [opval, ty, opval, opcode]
+    case naclbitc::FUNC_CODE_INST_BINOP: {
+      // BINOP: [opval, opval, opcode[, flags]]
       unsigned OpNum = 0;
       Value *LHS, *RHS;
-      if (getValueTypePair(Record, OpNum, NextValueNo, LHS) ||
+      if (getValue(Record, OpNum, NextValueNo, LHS) ||
           popValue(Record, OpNum, NextValueNo, LHS->getType(), RHS) ||
           OpNum+1 > Record.size())
         return Error("Invalid BINOP record");
@@ -1886,10 +1898,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       }
       break;
     }
-    case naclbitc::FUNC_CODE_INST_CAST: {    // CAST: [opval, opty, destty, castopc]
+    case naclbitc::FUNC_CODE_INST_CAST: {    // CAST: [opval, destty, castopc]
       unsigned OpNum = 0;
       Value *Op;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
+      if (getValue(Record, OpNum, NextValueNo, Op) ||
           OpNum+2 != Record.size())
         return Error("Invalid CAST record");
 
@@ -1905,13 +1917,13 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
     case naclbitc::FUNC_CODE_INST_GEP: { // GEP: [n x operands]
       unsigned OpNum = 0;
       Value *BasePtr;
-      if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr))
+      if (getValue(Record, OpNum, NextValueNo, BasePtr))
         return Error("Invalid GEP record");
 
       SmallVector<Value*, 16> GEPIdx;
       while (OpNum != Record.size()) {
         Value *Op;
-        if (getValueTypePair(Record, OpNum, NextValueNo, Op))
+        if (getValue(Record, OpNum, NextValueNo, Op))
           return Error("Invalid GEP record");
         GEPIdx.push_back(Op);
       }
@@ -1924,10 +1936,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
     }
 
     case naclbitc::FUNC_CODE_INST_EXTRACTVAL: {
-                                       // EXTRACTVAL: [opty, opval, n x indices]
+                                       // EXTRACTVAL: [opval, n x indices]
       unsigned OpNum = 0;
       Value *Agg;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Agg))
+      if (getValue(Record, OpNum, NextValueNo, Agg))
         return Error("Invalid EXTRACTVAL record");
 
       SmallVector<unsigned, 4> EXTRACTVALIdx;
@@ -1945,13 +1957,13 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
     }
 
     case naclbitc::FUNC_CODE_INST_INSERTVAL: {
-                           // INSERTVAL: [opty, opval, opty, opval, n x indices]
+                           // INSERTVAL: [opval, opval, n x indices]
       unsigned OpNum = 0;
       Value *Agg;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Agg))
+      if (getValue(Record, OpNum, NextValueNo, Agg))
         return Error("Invalid INSERTVAL record");
       Value *Val;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Val))
+      if (getValue(Record, OpNum, NextValueNo, Val))
         return Error("Invalid INSERTVAL record");
 
       SmallVector<unsigned, 4> INSERTVALIdx;
@@ -1968,12 +1980,12 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_SELECT: { // SELECT: [opval, ty, opval, opval]
+    case naclbitc::FUNC_CODE_INST_SELECT: { // SELECT: [opval, opval, opval]
       // obsolete form of select
       // handles select i1 ... in old bitcode
       unsigned OpNum = 0;
       Value *TrueVal, *FalseVal, *Cond;
-      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal) ||
+      if (getValue(Record, OpNum, NextValueNo, TrueVal) ||
           popValue(Record, OpNum, NextValueNo, TrueVal->getType(), FalseVal) ||
           popValue(Record, OpNum, NextValueNo, Type::getInt1Ty(Context), Cond))
         return Error("Invalid SELECT record");
@@ -1983,14 +1995,14 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_VSELECT: {// VSELECT: [ty,opval,opval,predty,pred]
+    case naclbitc::FUNC_CODE_INST_VSELECT: {// VSELECT: [opval, opval, pred]
       // new form of select
       // handles select i1 or select [N x i1]
       unsigned OpNum = 0;
       Value *TrueVal, *FalseVal, *Cond;
-      if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal) ||
+      if (getValue(Record, OpNum, NextValueNo, TrueVal) ||
           popValue(Record, OpNum, NextValueNo, TrueVal->getType(), FalseVal) ||
-          getValueTypePair(Record, OpNum, NextValueNo, Cond))
+          getValue(Record, OpNum, NextValueNo, Cond))
         return Error("Invalid SELECT record");
 
       // select condition can be either i1 or [N x i1]
@@ -2010,10 +2022,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_EXTRACTELT: { // EXTRACTELT: [opty, opval, opval]
+    case naclbitc::FUNC_CODE_INST_EXTRACTELT: { // EXTRACTELT: [opval, opval]
       unsigned OpNum = 0;
       Value *Vec, *Idx;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec) ||
+      if (getValue(Record, OpNum, NextValueNo, Vec) ||
           popValue(Record, OpNum, NextValueNo, Type::getInt32Ty(Context), Idx))
         return Error("Invalid EXTRACTELT record");
       I = ExtractElementInst::Create(Vec, Idx);
@@ -2021,10 +2033,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_INSERTELT: { // INSERTELT: [ty, opval,opval,opval]
+    case naclbitc::FUNC_CODE_INST_INSERTELT: { // INSERTELT: [opval, opval, opval]
       unsigned OpNum = 0;
       Value *Vec, *Elt, *Idx;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec) ||
+      if (getValue(Record, OpNum, NextValueNo, Vec) ||
           popValue(Record, OpNum, NextValueNo,
                    cast<VectorType>(Vec->getType())->getElementType(), Elt) ||
           popValue(Record, OpNum, NextValueNo, Type::getInt32Ty(Context), Idx))
@@ -2034,30 +2046,30 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_SHUFFLEVEC: {// SHUFFLEVEC: [opval,ty,opval,opval]
+    case naclbitc::FUNC_CODE_INST_SHUFFLEVEC: {// SHUFFLEVEC: [opval, opval, opval]
       unsigned OpNum = 0;
       Value *Vec1, *Vec2, *Mask;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Vec1) ||
+      if (getValue(Record, OpNum, NextValueNo, Vec1) ||
           popValue(Record, OpNum, NextValueNo, Vec1->getType(), Vec2))
         return Error("Invalid SHUFFLEVEC record");
 
-      if (getValueTypePair(Record, OpNum, NextValueNo, Mask))
+      if (getValue(Record, OpNum, NextValueNo, Mask))
         return Error("Invalid SHUFFLEVEC record");
       I = new ShuffleVectorInst(Vec1, Vec2, Mask);
       InstructionList.push_back(I);
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_CMP:   // CMP: [opty, opval, opval, pred]
+    case naclbitc::FUNC_CODE_INST_CMP:   // CMP: [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 naclbitc::FUNC_CODE_INST_CMP2: { // CMP2: [opty, opval, opval, pred]
+    case naclbitc::FUNC_CODE_INST_CMP2: { // CMP2: [opval, opval, pred]
       // FCmp/ICmp returning bool or vector of bool
 
       unsigned OpNum = 0;
       Value *LHS, *RHS;
-      if (getValueTypePair(Record, OpNum, NextValueNo, LHS) ||
+      if (getValue(Record, OpNum, NextValueNo, LHS) ||
           popValue(Record, OpNum, NextValueNo, LHS->getType(), RHS) ||
           OpNum+1 != Record.size())
         return Error("Invalid CMP record");
@@ -2070,7 +2082,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
 
-    case naclbitc::FUNC_CODE_INST_RET: // RET: [opty,opval<optional>]
+    case naclbitc::FUNC_CODE_INST_RET: // RET: [opval<optional>]
       {
         unsigned Size = Record.size();
         if (Size == 0) {
@@ -2081,7 +2093,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
 
         unsigned OpNum = 0;
         Value *Op = NULL;
-        if (getValueTypePair(Record, OpNum, NextValueNo, Op))
+        if (getValue(Record, OpNum, NextValueNo, Op))
           return Error("Invalid RET record");
         if (OpNum != Record.size())
           return Error("Invalid RET record");
@@ -2184,7 +2196,8 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       InstructionList.push_back(SI);
       for (unsigned i = 0, e = NumCases; i != e; ++i) {
         ConstantInt *CaseVal =
-          dyn_cast_or_null<ConstantInt>(getFnValueByID(Record[3+i*2], OpTy));
+          dyn_cast_or_null<ConstantInt>(
+              getOrCreateFnValueByID(Record[3+i*2], OpTy));
         BasicBlock *DestBB = getBasicBlock(Record[1+3+i*2]);
         if (CaseVal == 0 || DestBB == 0) {
           delete SI;
@@ -2223,7 +2236,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
     case naclbitc::FUNC_CODE_INST_RESUME: { // RESUME: [opval]
       unsigned Idx = 0;
       Value *Val = 0;
-      if (getValueTypePair(Record, Idx, NextValueNo, Val))
+      if (getValue(Record, Idx, NextValueNo, Val))
         return Error("Invalid RESUME record");
       I = ResumeInst::Create(Val);
       InstructionList.push_back(I);
@@ -2267,7 +2280,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       Type *Ty = getTypeByID(Record[Idx++]);
       if (!Ty) return Error("Invalid LANDINGPAD record");
       Value *PersFn = 0;
-      if (getValueTypePair(Record, Idx, NextValueNo, PersFn))
+      if (getValue(Record, Idx, NextValueNo, PersFn))
         return Error("Invalid LANDINGPAD record");
 
       bool IsCleanup = !!Record[Idx++];
@@ -2279,7 +2292,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
           LandingPadInst::ClauseType(Record[Idx++]); (void)CT;
         Value *Val;
 
-        if (getValueTypePair(Record, Idx, NextValueNo, Val)) {
+        if (getValue(Record, Idx, NextValueNo, Val)) {
           delete LP;
           return Error("Invalid LANDINGPAD record");
         }
@@ -2304,17 +2317,17 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       PointerType *Ty =
         dyn_cast_or_null<PointerType>(getTypeByID(Record[0]));
       Type *OpTy = getTypeByID(Record[1]);
-      Value *Size = getFnValueByID(Record[2], OpTy);
+      Value *Size = getOrCreateFnValueByID(Record[2], OpTy);
       unsigned Align = Record[3];
       if (!Ty || !Size) return Error("Invalid ALLOCA record");
       I = new AllocaInst(Ty->getElementType(), Size, (1 << Align) >> 1);
       InstructionList.push_back(I);
       break;
     }
-    case naclbitc::FUNC_CODE_INST_LOAD: { // LOAD: [opty, op, align, vol]
+    case naclbitc::FUNC_CODE_INST_LOAD: { // LOAD: [op, align, vol]
       unsigned OpNum = 0;
       Value *Op;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
+      if (getValue(Record, OpNum, NextValueNo, Op) ||
           OpNum+2 != Record.size())
         return Error("Invalid LOAD record");
 
@@ -2323,10 +2336,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case naclbitc::FUNC_CODE_INST_LOADATOMIC: {
-       // LOADATOMIC: [opty, op, align, vol, ordering, synchscope]
+       // LOADATOMIC: [op, align, vol, ordering, synchscope]
       unsigned OpNum = 0;
       Value *Op;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
+      if (getValue(Record, OpNum, NextValueNo, Op) ||
           OpNum+4 != Record.size())
         return Error("Invalid LOADATOMIC record");
 
@@ -2344,10 +2357,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       InstructionList.push_back(I);
       break;
     }
-    case naclbitc::FUNC_CODE_INST_STORE: { // STORE2:[ptrty, ptr, val, align, vol]
+    case naclbitc::FUNC_CODE_INST_STORE: { // STORE2:[ptr, val, align, vol]
       unsigned OpNum = 0;
       Value *Val, *Ptr;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) ||
+      if (getValue(Record, OpNum, NextValueNo, Ptr) ||
           popValue(Record, OpNum, NextValueNo,
                     cast<PointerType>(Ptr->getType())->getElementType(), Val) ||
           OpNum+2 != Record.size())
@@ -2358,10 +2371,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case naclbitc::FUNC_CODE_INST_STOREATOMIC: {
-      // STOREATOMIC: [ptrty, ptr, val, align, vol, ordering, synchscope]
+      // STOREATOMIC: [ptr, val, align, vol, ordering, synchscope]
       unsigned OpNum = 0;
       Value *Val, *Ptr;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) ||
+      if (getValue(Record, OpNum, NextValueNo, Ptr) ||
           popValue(Record, OpNum, NextValueNo,
                     cast<PointerType>(Ptr->getType())->getElementType(), Val) ||
           OpNum+4 != Record.size())
@@ -2381,10 +2394,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case naclbitc::FUNC_CODE_INST_CMPXCHG: {
-      // CMPXCHG:[ptrty, ptr, cmp, new, vol, ordering, synchscope]
+      // CMPXCHG:[ptr, cmp, new, vol, ordering, synchscope]
       unsigned OpNum = 0;
       Value *Ptr, *Cmp, *New;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) ||
+      if (getValue(Record, OpNum, NextValueNo, Ptr) ||
           popValue(Record, OpNum, NextValueNo,
                     cast<PointerType>(Ptr->getType())->getElementType(), Cmp) ||
           popValue(Record, OpNum, NextValueNo,
@@ -2401,10 +2414,10 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case naclbitc::FUNC_CODE_INST_ATOMICRMW: {
-      // ATOMICRMW:[ptrty, ptr, val, op, vol, ordering, synchscope]
+      // ATOMICRMW:[ptr, val, op, vol, ordering, synchscope]
       unsigned OpNum = 0;
       Value *Ptr, *Val;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) ||
+      if (getValue(Record, OpNum, NextValueNo, Ptr) ||
           popValue(Record, OpNum, NextValueNo,
                     cast<PointerType>(Ptr->getType())->getElementType(), Val) ||
           OpNum+4 != Record.size())
@@ -2435,7 +2448,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case naclbitc::FUNC_CODE_INST_CALL: {
-      // CALL: [cc, fnty, fnid, arg0, arg1...]
+      // CALL: [cc, fnid, arg0, arg1...]
       if (Record.size() < 2)
         return Error("Invalid CALL record");
 
@@ -2443,7 +2456,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
 
       unsigned OpNum = 1;
       Value *Callee;
-      if (getValueTypePair(Record, OpNum, NextValueNo, Callee))
+      if (getValue(Record, OpNum, NextValueNo, Callee))
         return Error("Invalid CALL record");
 
       PointerType *OpTy = dyn_cast<PointerType>(Callee->getType());
@@ -2470,7 +2483,7 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       } else {
         while (OpNum != Record.size()) {
           Value *Op;
-          if (getValueTypePair(Record, OpNum, NextValueNo, Op))
+          if (getValue(Record, OpNum, NextValueNo, Op))
             return Error("Invalid CALL record");
           Args.push_back(Op);
         }
@@ -2494,6 +2507,12 @@ bool NaClBitcodeReader::ParseFunctionBody(Function *F) {
       InstructionList.push_back(I);
       break;
     }
+    case naclbitc::FUNC_CODE_INST_FORWARDTYPEREF:
+      // Build corresponding forward reference.
+      if (Record.size() != 2)
+        return Error("Invald FORWARDTYPEREF record");
+      getOrCreateFnValueByID(Record[0], getTypeByID(Record[1]));
+      continue;
     }
 
     // Add instruction to end of current BB.  If there is no current BB, reject
diff --git a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
index a426c22f1d..57757e7ded 100644
--- a/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
+++ b/lib/Bitcode/NaCl/Reader/NaClBitcodeReader.h
@@ -77,8 +77,13 @@ public:
     ValuePtrs.resize(N);
   }
 
+  // Gets or creates the forward reference value for Idx with the given type.
+  Value *getOrCreateValueFwdRef(unsigned Idx, Type *Ty);
+
   Constant *getConstantFwdRef(unsigned Idx, Type *Ty);
-  Value *getValueFwdRef(unsigned Idx, Type *Ty);
+
+  // Gets the forward reference value for Idx.
+  Value *getValueFwdRef(unsigned Idx);
 
   void AssignValue(Value *V, unsigned Idx);
 
@@ -240,37 +245,34 @@ private:
              (!AcceptSupportedBitcodeOnly && Header.IsReadable()));
   }
   Type *getTypeByID(unsigned ID);
-  Value *getFnValueByID(unsigned ID, Type *Ty) {
+  // Gets or creates the (function-level) forward referenced value for
+  // ID with the given type.
+  Value *getOrCreateFnValueByID(unsigned ID, Type *Ty) {
     if (Ty && Ty->isMetadataTy())
       return MDValueList.getValueFwdRef(ID);
-    return ValueList.getValueFwdRef(ID, Ty);
+    return ValueList.getOrCreateValueFwdRef(ID, Ty);
+  }
+  // Returns the value associated with ID. The value must already exist,
+  // or a forward referenced value created by getOrCreateFnVaueByID.
+  Value *getFnValueByID(unsigned ID) {
+    return ValueList.getValueFwdRef(ID);
   }
   BasicBlock *getBasicBlock(unsigned ID) const {
     if (ID >= FunctionBBs.size()) return 0; // Invalid ID
     return FunctionBBs[ID];
   }
 
-  /// getValueTypePair - 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(SmallVector<uint64_t, 64> &Record, unsigned &Slot,
-                        unsigned InstNum, Value *&ResVal) {
+  /// \brief 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 getValue(SmallVector<uint64_t, 64> &Record, unsigned &Slot,
+                unsigned InstNum, Value *&ResVal) {
     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.
-      ResVal = getFnValueByID(ValNo, 0);
-      return ResVal == 0;
-    } else if (Slot == Record.size()) {
-      return true;
-    }
-
-    unsigned TypeNo = (unsigned)Record[Slot++];
-    ResVal = getFnValueByID(ValNo, getTypeByID(TypeNo));
+    ResVal = getFnValueByID(ValNo);
     return ResVal == 0;
   }
 
@@ -302,7 +304,7 @@ private:
     // Adjust the ValNo, if it was encoded relative to the InstNum.
     if (UseRelativeIDs)
       ValNo = InstNum - ValNo;
-    return getFnValueByID(ValNo, Ty);
+    return getOrCreateFnValueByID(ValNo, Ty);
   }
 
   /// getValueSigned -- Like getValue, but decodes signed VBRs.
@@ -313,7 +315,7 @@ private:
     // Adjust the ValNo, if it was encoded relative to the InstNum.
     if (UseRelativeIDs)
       ValNo = InstNum - ValNo;
-    return getFnValueByID(ValNo, Ty);
+    return getOrCreateFnValueByID(ValNo, Ty);
   }
 
   bool ParseModule(bool Resume);
diff --git a/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp b/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
index 82d6198fa6..bf1faa463d 100644
--- a/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
+++ b/lib/Bitcode/NaCl/Writer/NaClBitcodeWriter.cpp
@@ -77,7 +77,8 @@ enum {
   FUNCTION_INST_RET_VOID_ABBREV,
   FUNCTION_INST_RET_VAL_ABBREV,
   FUNCTION_INST_UNREACHABLE_ABBREV,
-  FUNCTION_INST_MAX_ABBREV = FUNCTION_INST_UNREACHABLE_ABBREV,
+  FUNCTION_INST_FORWARDTYPEREF_ABBREV,
+  FUNCTION_INST_MAX_ABBREV = FUNCTION_INST_FORWARDTYPEREF_ABBREV,
 
   // TYPE_BLOCK_ID_NEW abbrev id's.
   TYPE_POINTER_ABBREV = naclbitc::FIRST_APPLICATION_ABBREV,
@@ -1070,6 +1071,24 @@ static void WriteModuleConstants(const NaClValueEnumerator &VE,
   }
 }
 
+/// \brief Emits a type for the forward value reference. That is, if
+/// the ID for the given value is larger than or equal to the BaseID,
+/// the corresponding forward reference is generated.
+static void EmitFnForwardTypeRef(const Value *V,
+                                 unsigned BaseID,
+                                 NaClValueEnumerator &VE,
+                                 NaClBitstreamWriter &Stream) {
+  unsigned ValID = VE.getValueID(V);
+  if (ValID >= BaseID &&
+      VE.InsertFnForwardTypeRef(ValID)) {
+    SmallVector<unsigned, 2> Vals;
+    Vals.push_back(ValID);
+    Vals.push_back(VE.getTypeID(V->getType()));
+    Stream.EmitRecord(naclbitc::FUNC_CODE_INST_FORWARDTYPEREF, Vals,
+                      FUNCTION_INST_FORWARDTYPEREF_ABBREV);
+  }
+}
+
 /// PushValueAndType - The file has to encode both the value and type id for
 /// many values, because we need to know what type to create for forward
 /// references.  However, most operands are not forward references, so this type
@@ -1078,17 +1097,14 @@ static void WriteModuleConstants(const NaClValueEnumerator &VE,
 /// This function adds V's value ID to Vals.  If the value ID is higher than the
 /// instruction ID, then it is a forward reference, and it also includes the
 /// type ID.  The value ID that is written is encoded relative to the InstID.
-static bool PushValueAndType(const Value *V, unsigned InstID,
+static void PushValueAndType(const Value *V, unsigned InstID,
                              SmallVector<unsigned, 64> &Vals,
-                             NaClValueEnumerator &VE) {
+                             NaClValueEnumerator &VE,
+                             NaClBitstreamWriter &Stream) {
+  EmitFnForwardTypeRef(V, InstID, VE, Stream);
   unsigned ValID = VE.getValueID(V);
   // Make encoding relative to the InstID.
   Vals.push_back(InstID - ValID);
-  if (ValID >= InstID) {
-    Vals.push_back(VE.getTypeID(V->getType()));
-    return true;
-  }
-  return false;
 }
 
 /// pushValue - Like PushValueAndType, but where the type of the value is
@@ -1126,22 +1142,23 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
   switch (I.getOpcode()) {
   default:
     if (Instruction::isCast(I.getOpcode())) {
+      // CAST:       [opval, destty, castopc]
       Code = naclbitc::FUNC_CODE_INST_CAST;
-      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
-        AbbrevToUse = FUNCTION_INST_CAST_ABBREV;
+      AbbrevToUse = FUNCTION_INST_CAST_ABBREV;
+      PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
       Vals.push_back(VE.getTypeID(I.getType()));
       Vals.push_back(GetEncodedCastOpcode(I.getOpcode()));
     } else {
+      // BINOP:      [opval, opval, opcode[, flags]]
       assert(isa<BinaryOperator>(I) && "Unknown instruction!");
       Code = naclbitc::FUNC_CODE_INST_BINOP;
-      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
-        AbbrevToUse = FUNCTION_INST_BINOP_ABBREV;
+      AbbrevToUse = FUNCTION_INST_BINOP_ABBREV;
+      PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
       pushValue(I.getOperand(1), InstID, Vals, VE);
       Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode()));
       uint64_t Flags = GetOptimizationFlags(&I);
       if (Flags != 0) {
-        if (AbbrevToUse == FUNCTION_INST_BINOP_ABBREV)
-          AbbrevToUse = FUNCTION_INST_BINOP_FLAGS_ABBREV;
+        AbbrevToUse = FUNCTION_INST_BINOP_FLAGS_ABBREV;
         Vals.push_back(Flags);
       }
     }
@@ -1152,11 +1169,11 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     if (cast<GEPOperator>(&I)->isInBounds())
       Code = naclbitc::FUNC_CODE_INST_INBOUNDS_GEP;
     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
-      PushValueAndType(I.getOperand(i), InstID, Vals, VE);
+      PushValueAndType(I.getOperand(i), InstID, Vals, VE, Stream);
     break;
   case Instruction::ExtractValue: {
     Code = naclbitc::FUNC_CODE_INST_EXTRACTVAL;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     const ExtractValueInst *EVI = cast<ExtractValueInst>(&I);
     for (const unsigned *i = EVI->idx_begin(), *e = EVI->idx_end(); i != e; ++i)
       Vals.push_back(*i);
@@ -1164,8 +1181,8 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
   }
   case Instruction::InsertValue: {
     Code = naclbitc::FUNC_CODE_INST_INSERTVAL;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
-    PushValueAndType(I.getOperand(1), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
+    PushValueAndType(I.getOperand(1), InstID, Vals, VE, Stream);
     const InsertValueInst *IVI = cast<InsertValueInst>(&I);
     for (const unsigned *i = IVI->idx_begin(), *e = IVI->idx_end(); i != e; ++i)
       Vals.push_back(*i);
@@ -1173,24 +1190,24 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
   }
   case Instruction::Select:
     Code = naclbitc::FUNC_CODE_INST_VSELECT;
-    PushValueAndType(I.getOperand(1), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(1), InstID, Vals, VE, Stream);
     pushValue(I.getOperand(2), InstID, Vals, VE);
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     break;
   case Instruction::ExtractElement:
     Code = naclbitc::FUNC_CODE_INST_EXTRACTELT;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     pushValue(I.getOperand(1), InstID, Vals, VE);
     break;
   case Instruction::InsertElement:
     Code = naclbitc::FUNC_CODE_INST_INSERTELT;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     pushValue(I.getOperand(1), InstID, Vals, VE);
     pushValue(I.getOperand(2), InstID, Vals, VE);
     break;
   case Instruction::ShuffleVector:
     Code = naclbitc::FUNC_CODE_INST_SHUFFLEVEC;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     pushValue(I.getOperand(1), InstID, Vals, VE);
     pushValue(I.getOperand(2), InstID, Vals, VE);
     break;
@@ -1198,7 +1215,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
   case Instruction::FCmp:
     // compare returning Int1Ty or vector of Int1Ty
     Code = naclbitc::FUNC_CODE_INST_CMP2;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     pushValue(I.getOperand(1), InstID, Vals, VE);
     Vals.push_back(cast<CmpInst>(I).getPredicate());
     break;
@@ -1210,11 +1227,11 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
       if (NumOperands == 0)
         AbbrevToUse = FUNCTION_INST_RET_VOID_ABBREV;
       else if (NumOperands == 1) {
-        if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
-          AbbrevToUse = FUNCTION_INST_RET_VAL_ABBREV;
+        PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
+        AbbrevToUse = FUNCTION_INST_RET_VAL_ABBREV;
       } else {
         for (unsigned i = 0, e = NumOperands; i != e; ++i)
-          PushValueAndType(I.getOperand(i), InstID, Vals, VE);
+          PushValueAndType(I.getOperand(i), InstID, Vals, VE, Stream);
       }
     }
     break;
@@ -1304,7 +1321,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     break;
   case Instruction::Resume:
     Code = naclbitc::FUNC_CODE_INST_RESUME;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     break;
   case Instruction::Unreachable:
     Code = naclbitc::FUNC_CODE_INST_UNREACHABLE;
@@ -1333,7 +1350,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     const LandingPadInst &LP = cast<LandingPadInst>(I);
     Code = naclbitc::FUNC_CODE_INST_LANDINGPAD;
     Vals.push_back(VE.getTypeID(LP.getType()));
-    PushValueAndType(LP.getPersonalityFn(), InstID, Vals, VE);
+    PushValueAndType(LP.getPersonalityFn(), InstID, Vals, VE, Stream);
     Vals.push_back(LP.isCleanup());
     Vals.push_back(LP.getNumClauses());
     for (unsigned I = 0, E = LP.getNumClauses(); I != E; ++I) {
@@ -1341,7 +1358,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
         Vals.push_back(LandingPadInst::Catch);
       else
         Vals.push_back(LandingPadInst::Filter);
-      PushValueAndType(LP.getClause(I), InstID, Vals, VE);
+      PushValueAndType(LP.getClause(I), InstID, Vals, VE, Stream);
     }
     break;
   }
@@ -1357,11 +1374,11 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
   case Instruction::Load:
     if (cast<LoadInst>(I).isAtomic()) {
       Code = naclbitc::FUNC_CODE_INST_LOADATOMIC;
-      PushValueAndType(I.getOperand(0), InstID, Vals, VE);
+      PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);
     } else {
       Code = naclbitc::FUNC_CODE_INST_LOAD;
-      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))  // ptr
-        AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
+      PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);  // ptr
+      AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
     }
     Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
     Vals.push_back(cast<LoadInst>(I).isVolatile());
@@ -1375,7 +1392,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
       Code = naclbitc::FUNC_CODE_INST_STOREATOMIC;
     else
       Code = naclbitc::FUNC_CODE_INST_STORE;
-    PushValueAndType(I.getOperand(1), InstID, Vals, VE);  // ptrty + ptr
+    PushValueAndType(I.getOperand(1), InstID, Vals, VE, Stream);  // ptrty + ptr
     pushValue(I.getOperand(0), InstID, Vals, VE);         // val.
     Vals.push_back(Log2_32(cast<StoreInst>(I).getAlignment())+1);
     Vals.push_back(cast<StoreInst>(I).isVolatile());
@@ -1386,7 +1403,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     break;
   case Instruction::AtomicCmpXchg:
     Code = naclbitc::FUNC_CODE_INST_CMPXCHG;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);  // ptrty + ptr
     pushValue(I.getOperand(1), InstID, Vals, VE);         // cmp.
     pushValue(I.getOperand(2), InstID, Vals, VE);         // newval.
     Vals.push_back(cast<AtomicCmpXchgInst>(I).isVolatile());
@@ -1397,7 +1414,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     break;
   case Instruction::AtomicRMW:
     Code = naclbitc::FUNC_CODE_INST_ATOMICRMW;
-    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE, Stream);  // ptrty + ptr
     pushValue(I.getOperand(1), InstID, Vals, VE);         // val.
     Vals.push_back(GetEncodedRMWOperation(
                      cast<AtomicRMWInst>(I).getOperation()));
@@ -1420,7 +1437,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
 
     Vals.push_back((GetEncodedCallingConv(CI.getCallingConv()) << 1)
                    | unsigned(CI.isTailCall()));
-    PushValueAndType(CI.getCalledValue(), InstID, Vals, VE);  // Callee
+    PushValueAndType(CI.getCalledValue(), InstID, Vals, VE, Stream);  // Callee
 
     // Emit value #'s for the fixed parameters.
     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
@@ -1435,7 +1452,8 @@ static void WriteInstruction(const Instruction &I, unsigned InstID,
     if (FTy->isVarArg()) {
       for (unsigned i = FTy->getNumParams(), e = CI.getNumArgOperands();
            i != e; ++i)
-        PushValueAndType(CI.getArgOperand(i), InstID, Vals, VE);  // varargs
+        // varargs
+        PushValueAndType(CI.getArgOperand(i), InstID, Vals, VE, Stream);
     }
     break;
   }
@@ -1743,6 +1761,15 @@ static void WriteBlockInfo(const NaClValueEnumerator &VE,
                                    Abbv) != FUNCTION_INST_UNREACHABLE_ABBREV)
       llvm_unreachable("Unexpected abbrev ordering!");
   }
+  { // INST_FORWARDTYPEREF abbrev for FUNCTION_BLOCK.
+    NaClBitCodeAbbrev *Abbv = new NaClBitCodeAbbrev();
+    Abbv->Add(NaClBitCodeAbbrevOp(naclbitc::FUNC_CODE_INST_FORWARDTYPEREF));
+    Abbv->Add(NaClBitCodeAbbrevOp(NaClBitCodeAbbrevOp::VBR, 6));
+    Abbv->Add(NaClBitCodeAbbrevOp(NaClBitCodeAbbrevOp::VBR, 6));
+    if (Stream.EmitBlockInfoAbbrev(naclbitc::FUNCTION_BLOCK_ID,
+                                   Abbv) != FUNCTION_INST_FORWARDTYPEREF_ABBREV)
+      llvm_unreachable("Unexpected abbrev ordering!");
+  }
 
   { // Abbrev for METADATA_STRING.
     NaClBitCodeAbbrev *Abbv = new NaClBitCodeAbbrev();
diff --git a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
index 845a608255..4ff9b47bcc 100644
--- a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
+++ b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp
@@ -497,6 +497,9 @@ void NaClValueEnumerator::incorporateFunction(const Function &F) {
   NumModuleValues = Values.size();
   NumModuleMDValues = MDValues.size();
 
+  // Make sure no insertions outside of a function.
+  assert(FnForwardTypeRefs.empty());
+
   // Adding function arguments to the value table.
   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
        I != E; ++I)
@@ -565,6 +568,7 @@ void NaClValueEnumerator::purgeFunction() {
   MDValues.resize(NumModuleMDValues);
   BasicBlocks.clear();
   FunctionLocalMDs.clear();
+  FnForwardTypeRefs.clear();
 }
 
 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
diff --git a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.h b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.h
index 86c0385cde..49c8cd84d3 100644
--- a/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.h
+++ b/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.h
@@ -16,6 +16,7 @@
 #define NACL_VALUE_ENUMERATOR_H
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include <vector>
 
@@ -83,6 +84,11 @@ private:
   unsigned FirstFuncConstantID;
   unsigned FirstInstID;
 
+  /// Holds values that have been forward referenced within a function.
+  /// Used to make sure we don't generate more forward reference declarations
+  /// than necessary.
+  SmallSet<unsigned, 32> FnForwardTypeRefs;
+
   NaClValueEnumerator(const NaClValueEnumerator &) LLVM_DELETED_FUNCTION;
   void operator=(const NaClValueEnumerator &) LLVM_DELETED_FUNCTION;
 public:
@@ -109,6 +115,12 @@ public:
     End = FirstInstID;
   }
 
+  /// \brief Inserts the give value into the set of known function forward
+  /// value type refs. Returns true if the value id is added to the set.
+  bool InsertFnForwardTypeRef(unsigned ValID) {
+    return FnForwardTypeRefs.insert(ValID);
+  }
+
   const ValueList &getValues() const { return Values; }
   const ValueList &getMDValues() const { return MDValues; }
   const SmallVector<const MDNode *, 8> &getFunctionLocalMDValues() const {