stop encoding type/value pairs when the type is implied by the value.

This shrinks the function block of kc++ from 1055K to 906K


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36816 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 145 insertions, 110 deletions

diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index 79ddcf7..128f43e 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -1168,23 +1168,20 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case bitc::FUNC_CODE_INST_GEP: { // GEP: [n x operands]
-      if (Record.size() < 2 || (Record.size() & 1))
-        return Error("Invalid GEP record");
-      const Type *OpTy = getTypeByID(Record[0]);
-      Value *Op = getFnValueByID(Record[1], OpTy);
-      if (OpTy == 0 || Op == 0)
+      unsigned OpNum = 0;
+      Value *BasePtr;
+      if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr))
         return Error("Invalid GEP record");
 
       SmallVector<Value*, 16> GEPIdx;
-      for (unsigned i = 1, e = Record.size()/2; i != e; ++i) {
-        const Type *IdxTy = getTypeByID(Record[i*2]);
-        Value *Idx = getFnValueByID(Record[i*2+1], IdxTy);
-        if (IdxTy == 0 || Idx == 0)
+      while (OpNum != Record.size()) {
+        Value *Op;
+        if (getValueTypePair(Record, OpNum, NextValueNo, Op))
           return Error("Invalid GEP record");
-        GEPIdx.push_back(Idx);
+        GEPIdx.push_back(Op);
       }
 
-      I = new GetElementPtrInst(Op, &GEPIdx[0], GEPIdx.size());
+      I = new GetElementPtrInst(BasePtr, &GEPIdx[0], GEPIdx.size());
       break;
     }
       
@@ -1242,16 +1239,17 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
     }
       
     case bitc::FUNC_CODE_INST_CMP: { // CMP: [opty, opval, opval, pred]
-      if (Record.size() < 4) return Error("Invalid CMP record");
-      const Type *OpTy = getTypeByID(Record[0]);
-      Value *LHS = getFnValueByID(Record[1], OpTy);
-      Value *RHS = getFnValueByID(Record[2], OpTy);
-      if (OpTy == 0 || LHS == 0 || RHS == 0)
+      unsigned OpNum = 0;
+      Value *LHS, *RHS;
+      if (getValueTypePair(Record, OpNum, NextValueNo, LHS) ||
+          getValue(Record, OpNum, LHS->getType(), RHS) ||
+          OpNum+1 != Record.size())
         return Error("Invalid CMP record");
-      if (OpTy->isFPOrFPVector())
-        I = new FCmpInst((FCmpInst::Predicate)Record[3], LHS, RHS);
+      
+      if (LHS->getType()->isFPOrFPVector())
+        I = new FCmpInst((FCmpInst::Predicate)Record[OpNum], LHS, RHS);
       else
-        I = new ICmpInst((ICmpInst::Predicate)Record[3], LHS, RHS);
+        I = new ICmpInst((ICmpInst::Predicate)Record[OpNum], LHS, RHS);
       break;
     }
     
@@ -1259,16 +1257,15 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
       if (Record.size() == 0) {
         I = new ReturnInst();
         break;
-      }
-      if (Record.size() == 2) {
-        const Type *OpTy = getTypeByID(Record[0]);
-        Value *Op = getFnValueByID(Record[1], OpTy);
-        if (!OpTy || !Op)
+      } else {
+        unsigned OpNum = 0;
+        Value *Op;
+        if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
+            OpNum != Record.size())
           return Error("Invalid RET record");
         I = new ReturnInst(Op);
         break;
       }
-      return Error("Invalid RET record");
     case bitc::FUNC_CODE_INST_BR: { // BR: [bb#, bb#, opval] or [bb#]
       if (Record.size() != 1 && Record.size() != 3)
         return Error("Invalid BR record");
@@ -1312,46 +1309,42 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
     }
       
     case bitc::FUNC_CODE_INST_INVOKE: { // INVOKE: [cc,fnty, op0,op1,op2, ...]
-      if (Record.size() < 5)
-        return Error("Invalid INVOKE record");
+      if (Record.size() < 3) return Error("Invalid INVOKE record");
       unsigned CCInfo = Record[0];
-      const PointerType *CalleeTy =
-        dyn_cast_or_null<PointerType>(getTypeByID(Record[1]));
-      Value *Callee = getFnValueByID(Record[2], CalleeTy);
-      BasicBlock *NormalBB = getBasicBlock(Record[3]);
-      BasicBlock *UnwindBB = getBasicBlock(Record[4]);
-      if (CalleeTy == 0 || Callee == 0 || NormalBB == 0 || UnwindBB == 0)
+      BasicBlock *NormalBB = getBasicBlock(Record[1]);
+      BasicBlock *UnwindBB = getBasicBlock(Record[2]);
+      
+      unsigned OpNum = 3;
+      Value *Callee;
+      if (getValueTypePair(Record, OpNum, NextValueNo, Callee))
         return Error("Invalid INVOKE record");
       
-      const FunctionType *FTy =
+      const PointerType *CalleeTy = dyn_cast<PointerType>(Callee->getType());
+      const FunctionType *FTy = !CalleeTy ? 0 :
         dyn_cast<FunctionType>(CalleeTy->getElementType());
 
       // Check that the right number of fixed parameters are here.
-      if (FTy == 0 || Record.size() < 5+FTy->getNumParams())
+      if (FTy == 0 || NormalBB == 0 || UnwindBB == 0 ||
+          Record.size() < OpNum+FTy->getNumParams())
         return Error("Invalid INVOKE record");
-
+      
       SmallVector<Value*, 16> Ops;
-      for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
-        Ops.push_back(getFnValueByID(Record[5+i], FTy->getParamType(i)));
-        if (Ops.back() == 0)
-          return Error("Invalid INVOKE record");
+      for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
+        Ops.push_back(getFnValueByID(Record[OpNum], FTy->getParamType(i)));
+        if (Ops.back() == 0) return Error("Invalid INVOKE record");
       }
       
-      unsigned FirstVarargParam = 5+FTy->getNumParams();
-      if (FTy->isVarArg()) {
-        // Read type/value pairs for varargs params.
-        if ((Record.size()-FirstVarargParam) & 1)
+      if (!FTy->isVarArg()) {
+        if (Record.size() != OpNum)
           return Error("Invalid INVOKE record");
-        
-        for (unsigned i = FirstVarargParam, e = Record.size(); i != e; i += 2) {
-          const Type *ArgTy = getTypeByID(Record[i]);
-          Ops.push_back(getFnValueByID(Record[i+1], ArgTy));
-          if (Ops.back() == 0 || ArgTy == 0)
+      } else {
+        // Read type/value pairs for varargs params.
+        while (OpNum != Record.size()) {
+          Value *Op;
+          if (getValueTypePair(Record, OpNum, NextValueNo, Op))
             return Error("Invalid INVOKE record");
+          Ops.push_back(Op);
         }
-      } else {
-        if (Record.size() != FirstVarargParam)
-          return Error("Invalid INVOKE record");
       }
       
       I = new InvokeInst(Callee, NormalBB, UnwindBB, &Ops[0], Ops.size());
@@ -1416,13 +1409,13 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case bitc::FUNC_CODE_INST_LOAD: { // LOAD: [opty, op, align, vol]
-      if (Record.size() < 4)
-        return Error("Invalid LOAD record");
-      const Type *OpTy = getTypeByID(Record[0]);
-      Value *Op = getFnValueByID(Record[1], OpTy);
-      if (!OpTy || !Op)
-        return Error("Invalid LOAD record");
-      I = new LoadInst(Op, "", Record[3], (1 << Record[2]) >> 1);
+      unsigned OpNum = 0;
+      Value *Op;
+      if (getValueTypePair(Record, OpNum, NextValueNo, Op) ||
+          OpNum+2 != Record.size())
+        return Error("Invalid RET record");
+      
+      I = new LoadInst(Op, "", Record[OpNum+1], (1 << Record[OpNum]) >> 1);
       break;
     }
     case bitc::FUNC_CODE_INST_STORE: { // STORE:[ptrty,val,ptr, align, vol]
@@ -1438,37 +1431,38 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
       break;
     }
     case bitc::FUNC_CODE_INST_CALL: { // CALL: [cc, fnty, fnid, arg0, arg1...]
-      if (Record.size() < 3)
+      if (Record.size() < 1)
         return Error("Invalid CALL record");
       unsigned CCInfo = Record[0];
-      const PointerType *OpTy = 
-        dyn_cast_or_null<PointerType>(getTypeByID(Record[1]));
+      
+      unsigned OpNum = 1;
+      Value *Callee;
+      if (getValueTypePair(Record, OpNum, NextValueNo, Callee))
+        return Error("Invalid CALL record");
+      
+      const PointerType *OpTy = dyn_cast<PointerType>(Callee->getType());
       const FunctionType *FTy = 0;
       if (OpTy) FTy = dyn_cast<FunctionType>(OpTy->getElementType());
-      Value *Callee = getFnValueByID(Record[2], OpTy);
-      if (!FTy || !Callee || Record.size() < FTy->getNumParams()+3)
+      if (!FTy || Record.size() < FTy->getNumParams()+OpNum)
         return Error("Invalid CALL record");
       
       SmallVector<Value*, 16> Args;
       // Read the fixed params.
-      for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
-        Args.push_back(getFnValueByID(Record[i+3], FTy->getParamType(i)));
+      for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
+        Args.push_back(getFnValueByID(Record[OpNum], FTy->getParamType(i)));
         if (Args.back() == 0) return Error("Invalid CALL record");
       }
       
-      
       // Read type/value pairs for varargs params.
-      unsigned NextArg = FTy->getNumParams()+3;
       if (!FTy->isVarArg()) {
-        if (NextArg != Record.size())
+        if (OpNum != Record.size())
           return Error("Invalid CALL record");
       } else {
-        if ((Record.size()-NextArg) & 1)
-          return Error("Invalid CALL record");
-        for (unsigned e = Record.size(); NextArg != e; NextArg += 2) {
-          Args.push_back(getFnValueByID(Record[NextArg+1], 
-                                        getTypeByID(Record[NextArg])));
-          if (Args.back() == 0) return Error("Invalid CALL record");
+        while (OpNum != Record.size()) {
+          Value *Op;
+          if (getValueTypePair(Record, OpNum, NextValueNo, Op))
+            return Error("Invalid CALL record");
+          Args.push_back(Op);
         }
       }
       
diff --git a/lib/Bitcode/Reader/BitcodeReader.h b/lib/Bitcode/Reader/BitcodeReader.h
index 44d69a6..2dcce0b 100644
--- a/lib/Bitcode/Reader/BitcodeReader.h
+++ b/lib/Bitcode/Reader/BitcodeReader.h
@@ -147,6 +147,34 @@ private:
       return ParamAttrs[i-1];
     return 0;
   }
+  
+  /// 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) {
+    if (Slot == Record.size()) return true;
+    unsigned ValNo = Record[Slot++];
+    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 = Record[Slot++];
+    ResVal = getFnValueByID(ValNo, getTypeByID(TypeNo));
+    return ResVal == 0;
+  }
+  bool getValue(SmallVector<uint64_t, 64> &Record, unsigned &Slot,
+                const Type *Ty, Value *&ResVal) {
+    if (Slot == Record.size()) return true;
+    unsigned ValNo = Record[Slot++];
+    ResVal = getFnValueByID(ValNo, Ty);
+    return ResVal == 0;
+  }
 
   
   bool ParseModule(const std::string &ModuleID);
diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp
index 23e7011..1797729 100644
--- a/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -572,9 +572,29 @@ static void WriteModuleConstants(const ValueEnumerator &VE,
   }
 }
 
+/// 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
+/// field is not needed.
+///
+/// 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.
+static bool PushValueAndType(Value *V, unsigned InstID,
+                             SmallVector<unsigned, 64> &Vals, 
+                             ValueEnumerator &VE) {
+  unsigned ValID = VE.getValueID(V);
+  Vals.push_back(ValID);
+  if (ValID >= InstID) {
+    Vals.push_back(VE.getTypeID(V->getType()));
+    return true;
+  }
+  return false;
+}
+
 /// WriteInstruction - Emit an instruction to the specified stream.
-static void WriteInstruction(const Instruction &I, ValueEnumerator &VE, 
-                             BitstreamWriter &Stream,
+static void WriteInstruction(const Instruction &I, unsigned InstID,
+                             ValueEnumerator &VE, BitstreamWriter &Stream,
                              SmallVector<unsigned, 64> &Vals) {
   unsigned Code = 0;
   unsigned AbbrevToUse = 0;
@@ -598,10 +618,8 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
 
   case Instruction::GetElementPtr:
     Code = bitc::FUNC_CODE_INST_GEP;
-    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
-      Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
-      Vals.push_back(VE.getValueID(I.getOperand(i)));
-    }
+    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
+      PushValueAndType(I.getOperand(i), InstID, Vals, VE);
     break;
   case Instruction::Select:
     Code = bitc::FUNC_CODE_INST_SELECT;
@@ -633,18 +651,15 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
   case Instruction::ICmp:
   case Instruction::FCmp:
     Code = bitc::FUNC_CODE_INST_CMP;
-    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
-    Vals.push_back(VE.getValueID(I.getOperand(0)));
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
     Vals.push_back(VE.getValueID(I.getOperand(1)));
     Vals.push_back(cast<CmpInst>(I).getPredicate());
     break;
 
   case Instruction::Ret:
     Code = bitc::FUNC_CODE_INST_RET;
-    if (I.getNumOperands()) {
-      Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
-      Vals.push_back(VE.getValueID(I.getOperand(0)));
-    }
+    if (I.getNumOperands())
+      PushValueAndType(I.getOperand(0), InstID, Vals, VE);
     break;
   case Instruction::Br:
     Code = bitc::FUNC_CODE_INST_BR;
@@ -663,10 +678,9 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
   case Instruction::Invoke: {
     Code = bitc::FUNC_CODE_INST_INVOKE;
     Vals.push_back(cast<InvokeInst>(I).getCallingConv());
-    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
-    Vals.push_back(VE.getValueID(I.getOperand(0)));  // callee
-    Vals.push_back(VE.getValueID(I.getOperand(1)));  // normal
-    Vals.push_back(VE.getValueID(I.getOperand(2)));  // unwind
+    Vals.push_back(VE.getValueID(I.getOperand(1)));      // normal dest
+    Vals.push_back(VE.getValueID(I.getOperand(2)));      // unwind dest
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE); // callee
     
     // Emit value #'s for the fixed parameters.
     const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
@@ -676,12 +690,9 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
 
     // Emit type/value pairs for varargs params.
     if (FTy->isVarArg()) {
-      unsigned NumVarargs = I.getNumOperands()-3-FTy->getNumParams();
-      for (unsigned i = I.getNumOperands()-NumVarargs, e = I.getNumOperands();
-           i != e; ++i) {
-        Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
-        Vals.push_back(VE.getValueID(I.getOperand(i)));
-      }
+      for (unsigned i = 3+FTy->getNumParams(), e = I.getNumOperands();
+           i != e; ++i)
+        PushValueAndType(I.getOperand(i), InstID, Vals, VE); // vararg
     }
     break;
   }
@@ -721,11 +732,11 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
     
   case Instruction::Load:
     Code = bitc::FUNC_CODE_INST_LOAD;
-    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
-    Vals.push_back(VE.getValueID(I.getOperand(0))); // ptr.
+    if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))  // ptr
+      AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
+      
     Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
     Vals.push_back(cast<LoadInst>(I).isVolatile());
-    AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
     break;
   case Instruction::Store:
     Code = bitc::FUNC_CODE_INST_STORE;
@@ -739,8 +750,7 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
     Code = bitc::FUNC_CODE_INST_CALL;
     Vals.push_back((cast<CallInst>(I).getCallingConv() << 1) |
                    cast<CallInst>(I).isTailCall());
-    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
-    Vals.push_back(VE.getValueID(I.getOperand(0)));  // callee
+    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // Callee
     
     // Emit value #'s for the fixed parameters.
     const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
@@ -752,10 +762,8 @@ static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
     if (FTy->isVarArg()) {
       unsigned NumVarargs = I.getNumOperands()-1-FTy->getNumParams();
       for (unsigned i = I.getNumOperands()-NumVarargs, e = I.getNumOperands();
-           i != e; ++i) {
-        Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
-        Vals.push_back(VE.getValueID(I.getOperand(i)));
-      }
+           i != e; ++i)
+        PushValueAndType(I.getOperand(i), InstID, Vals, VE);  // varargs
     }
     break;
   }
@@ -850,10 +858,17 @@ static void WriteFunction(const Function &F, ValueEnumerator &VE,
   VE.getFunctionConstantRange(CstStart, CstEnd);
   WriteConstants(CstStart, CstEnd, VE, Stream, false);
   
+  // Keep a running idea of what the instruction ID is. 
+  unsigned InstID = CstEnd;
+  
   // Finally, emit all the instructions, in order.
   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
-    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
-      WriteInstruction(*I, VE, Stream, Vals);
+    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
+         I != E; ++I) {
+      WriteInstruction(*I, InstID, VE, Stream, Vals);
+      if (I->getType() != Type::VoidTy)
+        ++InstID;
+    }
   
   // Emit names for all the instructions etc.
   WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);
@@ -997,8 +1012,6 @@ static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) {
   { // INST_LOAD abbrev for FUNCTION_BLOCK.
     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_LOAD));
-    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // typeid
-                              Log2_32_Ceil(VE.getTypes().size()+1)));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Ptr
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // Align
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // volatile