From 7337ab9e929a4a787f90d37ee0ed8f4cc27170ab Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 6 May 2007 00:00:00 +0000 Subject: 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 --- lib/Bitcode/Reader/BitcodeReader.cpp | 144 +++++++++++++++++------------------ lib/Bitcode/Reader/BitcodeReader.h | 28 +++++++ lib/Bitcode/Writer/BitcodeWriter.cpp | 83 +++++++++++--------- 3 files changed, 145 insertions(+), 110 deletions(-) (limited to 'lib/Bitcode') 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 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(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(Callee->getType()); + const FunctionType *FTy = !CalleeTy ? 0 : dyn_cast(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 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(getTypeByID(Record[1])); + + unsigned OpNum = 1; + Value *Callee; + if (getValueTypePair(Record, OpNum, NextValueNo, Callee)) + return Error("Invalid CALL record"); + + const PointerType *OpTy = dyn_cast(Callee->getType()); const FunctionType *FTy = 0; if (OpTy) FTy = dyn_cast(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 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 &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 &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 &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 &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(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(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(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(I).getAlignment())+1); Vals.push_back(cast(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(I).getCallingConv() << 1) | cast(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(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 -- cgit v1.1