From 29b789befab99ac4e8e62b6bc813dc181174cf33 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 19 Nov 2003 17:27:18 +0000 Subject: [PATCH] * Finegrainify namespacification * Strength reduce several data structures which were left over from the "bad old days" * Minor efficiency improvements * Major efficiency improvement: In BytecodeParser::insertValue, do not allocate a new ValueTab entry just because some value exists with a large type. This dramatically reduces the number of allocations/deallocations performed by the bytecode reader, and speeds up parsing of Kimwitu++ from 34s to 17s. This is to help address PR127 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10085 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Bytecode/Reader/Reader.cpp | 93 ++++++++++----------------- lib/Bytecode/Reader/ReaderInternals.h | 27 ++++---- 2 files changed, 47 insertions(+), 73 deletions(-) diff --git a/lib/Bytecode/Reader/Reader.cpp b/lib/Bytecode/Reader/Reader.cpp index 4c2ec041418..ed8f9e804c9 100644 --- a/lib/Bytecode/Reader/Reader.cpp +++ b/lib/Bytecode/Reader/Reader.cpp @@ -12,7 +12,6 @@ // Note that this library should be as fast as possible, reentrant, and // threadsafe!! // -// TODO: Return error messages to caller instead of printing them out directly. // TODO: Allow passing in an option to ignore the symbol table // //===----------------------------------------------------------------------===// @@ -31,8 +30,7 @@ #include "Config/sys/types.h" #include #include - -namespace llvm { +using namespace llvm; static inline void ALIGN32(const unsigned char *&begin, const unsigned char *end) { @@ -83,24 +81,20 @@ const Type *BytecodeParser::getType(unsigned ID) { throw std::string("Illegal type reference!"); } -unsigned BytecodeParser::insertValue(Value *Val, ValueTable &ValueTab) { - return insertValue(Val, getTypeSlot(Val->getType()), ValueTab); -} - unsigned BytecodeParser::insertValue(Value *Val, unsigned type, ValueTable &ValueTab) { assert((!isa(Val) || Val->getType()->isPrimitiveType() || !cast(Val)->isNullValue()) && "Cannot read null values from bytecode!"); assert(type != Type::TypeTyID && "Types should never be insertValue'd!"); - + if (ValueTab.size() <= type) { unsigned OldSize = ValueTab.size(); ValueTab.resize(type+1); - while (OldSize != type+1) - ValueTab[OldSize++] = new ValueList(); } + if (!ValueTab[type]) ValueTab[type] = new ValueList(); + //cerr << "insertValue Values[" << type << "][" << ValueTab[type].size() // << "] = " << Val << "\n"; ValueTab[type]->push_back(Val); @@ -110,10 +104,6 @@ unsigned BytecodeParser::insertValue(Value *Val, unsigned type, } -Value *BytecodeParser::getValue(const Type *Ty, unsigned oNum, bool Create) { - return getValue(getTypeSlot(Ty), oNum, Create); -} - Value *BytecodeParser::getValue(unsigned type, unsigned oNum, bool Create) { assert(type != Type::TypeTyID && "getValue() cannot get types!"); assert(type != Type::LabelTyID && "getValue() cannot get blocks!"); @@ -125,13 +115,13 @@ Value *BytecodeParser::getValue(unsigned type, unsigned oNum, bool Create) { --Num; } - if (type < ModuleValues.size()) { + if (type < ModuleValues.size() && ModuleValues[type]) { if (Num < ModuleValues[type]->size()) return ModuleValues[type]->getOperand(Num); Num -= ModuleValues[type]->size(); } - if (Values.size() > type && Values[type]->size() > Num) + if (Values.size() > type && Values[type] && Num < Values[type]->size()) return Values[type]->getOperand(Num); if (!Create) return 0; // Do not create a placeholder? @@ -181,11 +171,11 @@ Constant *BytecodeParser::getConstantValue(unsigned TypeSlot, unsigned Slot) { const Type *Ty = getType(TypeSlot); std::pair Key(Ty, Slot); - GlobalRefsType::iterator I = GlobalRefs.lower_bound(Key); + ConstantRefsType::iterator I = ConstantFwdRefs.lower_bound(Key); - if (I != GlobalRefs.end() && I->first == Key) { + if (I != ConstantFwdRefs.end() && I->first == Key) { BCR_TRACE(5, "Previous forward ref found!\n"); - return cast(I->second); + return I->second; } else { // Create a placeholder for the constant reference and // keep track of the fact that we have a forward ref to recycle it @@ -193,7 +183,7 @@ Constant *BytecodeParser::getConstantValue(unsigned TypeSlot, unsigned Slot) { Constant *C = new ConstPHolder(Ty, Slot); // Keep track of the fact that we have a forward ref to recycle it - GlobalRefs.insert(I, std::make_pair(Key, C)); + ConstantFwdRefs.insert(I, std::make_pair(Key, C)); return C; } } @@ -265,22 +255,16 @@ void BytecodeParser::ParseSymbolTable(const unsigned char *&Buf, if (Buf > EndBuf) throw std::string("Tried to read past end of buffer."); } -void BytecodeParser::ResolveReferencesToValue(Value *NewV, unsigned Slot) { - GlobalRefsType::iterator I = GlobalRefs.find(std::make_pair(NewV->getType(), - Slot)); - if (I == GlobalRefs.end()) return; // Never forward referenced? +void BytecodeParser::ResolveReferencesToConstant(Constant *NewV, unsigned Slot){ + ConstantRefsType::iterator I = + ConstantFwdRefs.find(std::make_pair(NewV->getType(), Slot)); + if (I == ConstantFwdRefs.end()) return; // Never forward referenced? BCR_TRACE(3, "Mutating forward refs!\n"); - Value *VPH = I->second; // Get the placeholder... - VPH->replaceAllUsesWith(NewV); - - // If this is a global variable being resolved, remove the placeholder from - // the module... - if (GlobalValue* GVal = dyn_cast(NewV)) - GVal->getParent()->getGlobalList().remove(cast(VPH)); - - delete VPH; // Delete the old placeholder - GlobalRefs.erase(I); // Remove the map entry for it + Value *PH = I->second; // Get the placeholder... + PH->replaceAllUsesWith(NewV); + delete PH; // Delete the old placeholder + ConstantFwdRefs.erase(I); // Remove the map entry for it } void BytecodeParser::ParseFunction(const unsigned char *&Buf, @@ -288,30 +272,24 @@ void BytecodeParser::ParseFunction(const unsigned char *&Buf, if (FunctionSignatureList.empty()) throw std::string("FunctionSignatureList empty!"); - Function *F = FunctionSignatureList.back().first; - unsigned FunctionSlot = FunctionSignatureList.back().second; + Function *F = FunctionSignatureList.back(); FunctionSignatureList.pop_back(); // Save the information for future reading of the function - LazyFunctionInfo *LFI = new LazyFunctionInfo(); - LFI->Buf = Buf; LFI->EndBuf = EndBuf; LFI->FunctionSlot = FunctionSlot; - LazyFunctionLoadMap[F] = LFI; + LazyFunctionLoadMap[F] = LazyFunctionInfo(Buf, EndBuf); // Pretend we've `parsed' this function Buf = EndBuf; } void BytecodeParser::materializeFunction(Function* F) { // Find {start, end} pointers and slot in the map. If not there, we're done. - std::map::iterator Fi = + std::map::iterator Fi = LazyFunctionLoadMap.find(F); if (Fi == LazyFunctionLoadMap.end()) return; - - LazyFunctionInfo *LFI = Fi->second; - const unsigned char *Buf = LFI->Buf; - const unsigned char *EndBuf = LFI->EndBuf; - unsigned FunctionSlot = LFI->FunctionSlot; + + const unsigned char *Buf = Fi->second.Buf; + const unsigned char *EndBuf = Fi->second.EndBuf; LazyFunctionLoadMap.erase(Fi); - delete LFI; GlobalValue::LinkageTypes Linkage = GlobalValue::ExternalLinkage; @@ -344,7 +322,7 @@ void BytecodeParser::materializeFunction(Function* F) { Function::aiterator AI = F->abegin(); for (FunctionType::ParamTypes::const_iterator It = Params.begin(); It != Params.end(); ++It, ++AI) - insertValue(AI, Values); + insertValue(AI, getTypeSlot(AI->getType()), Values); // Keep track of how many basic blocks we have read in... unsigned BlockNum = 0; @@ -355,11 +333,10 @@ void BytecodeParser::materializeFunction(Function* F) { readBlock(Buf, EndBuf, Type, Size); switch (Type) { - case BytecodeFormat::ConstantPool: { + case BytecodeFormat::ConstantPool: BCR_TRACE(2, "BLOCK BytecodeFormat::ConstantPool: {\n"); ParseConstantPool(Buf, Buf+Size, Values, FunctionTypeValues); break; - } case BytecodeFormat::BasicBlock: { BCR_TRACE(2, "BLOCK BytecodeFormat::BasicBlock: {\n"); @@ -368,11 +345,10 @@ void BytecodeParser::materializeFunction(Function* F) { break; } - case BytecodeFormat::SymbolTable: { + case BytecodeFormat::SymbolTable: BCR_TRACE(2, "BLOCK BytecodeFormat::SymbolTable: {\n"); ParseSymbolTable(Buf, Buf+Size, &F->getSymbolTable(), F); break; - } default: BCR_TRACE(2, "BLOCK :ignored! {\n"); @@ -392,6 +368,7 @@ void BytecodeParser::materializeFunction(Function* F) { throw std::string("Illegal basic block operand reference"); ParsedBasicBlocks.clear(); + // Resolve forward references. Replace any uses of a forward reference value // with the real value. @@ -483,7 +460,7 @@ void BytecodeParser::ParseModuleGlobalInfo(const unsigned char *&Buf, GlobalVariable *GV = new GlobalVariable(ElTy, VarType & 1, Linkage, 0, "", TheModule); BCR_TRACE(2, "Global Variable of type: " << *Ty << "\n"); - ResolveReferencesToValue(GV, insertValue(GV, SlotNo, ModuleValues)); + insertValue(GV, SlotNo, ModuleValues); if (VarType & 2) { // Does it have an initializer? unsigned InitSlot; @@ -514,13 +491,12 @@ void BytecodeParser::ParseModuleGlobalInfo(const unsigned char *&Buf, // Insert the placeholder... Function *Func = new Function(cast(Ty), GlobalValue::InternalLinkage, "", TheModule); - unsigned DestSlot = insertValue(Func, FnSignature, ModuleValues); - ResolveReferencesToValue(Func, DestSlot); + insertValue(Func, FnSignature, ModuleValues); // Keep track of this information in a list that is emptied as functions are // loaded... // - FunctionSignatureList.push_back(std::make_pair(Func, DestSlot)); + FunctionSignatureList.push_back(Func); if (read_vbr(Buf, End, FnSignature)) throw Error_readvbr; BCR_TRACE(2, "Function of type: " << Ty << "\n"); @@ -642,7 +618,6 @@ void BytecodeParser::ParseModule(const unsigned char *Buf, BCR_TRACE(1, "BLOCK BytecodeFormat::SymbolTable: {\n"); ParseSymbolTable(Buf, Buf+Size, &TheModule->getSymbolTable(), 0); break; - default: Buf += Size; if (OldBuf > Buf) throw std::string("Expected Module Block!"); @@ -660,7 +635,9 @@ void BytecodeParser::ParseModule(const unsigned char *Buf, GlobalInits.pop_back(); // Look up the initializer value... - if (Value *V = getValue(GV->getType()->getElementType(), Slot, false)) { + // FIXME: Preserve this type ID! + unsigned TypeSlot = getTypeSlot(GV->getType()->getElementType()); + if (Value *V = getValue(TypeSlot, Slot, false)) { if (GV->hasInitializer()) throw std::string("Global *already* has an initializer?!"); GV->setInitializer(cast(V)); @@ -696,5 +673,3 @@ void BytecodeParser::ParseBytecode(const unsigned char *Buf, unsigned Length, throw; } } - -} // End llvm namespace diff --git a/lib/Bytecode/Reader/ReaderInternals.h b/lib/Bytecode/Reader/ReaderInternals.h index 8522aee4c29..aea45c2bed7 100644 --- a/lib/Bytecode/Reader/ReaderInternals.h +++ b/lib/Bytecode/Reader/ReaderInternals.h @@ -37,7 +37,8 @@ namespace llvm { struct LazyFunctionInfo { const unsigned char *Buf, *EndBuf; - unsigned FunctionSlot; + LazyFunctionInfo(const unsigned char *B = 0, const unsigned char *EB = 0) + : Buf(B), EndBuf(EB) {} }; class BytecodeParser : public ModuleProvider { @@ -104,13 +105,13 @@ private: std::vector ParsedBasicBlocks; - // GlobalRefs - This maintains a mapping between 's and forward - // references to global values or constants. Such values may be referenced - // before they are defined, and if so, the temporary object that they - // represent is held here. + // ConstantFwdRefs - This maintains a mapping between 's and + // forward references to constants. Such values may be referenced before they + // are defined, and if so, the temporary object that they represent is held + // here. // - typedef std::map, Value*> GlobalRefsType; - GlobalRefsType GlobalRefs; + typedef std::map, Constant*> ConstantRefsType; + ConstantRefsType ConstantFwdRefs; // TypesLoaded - This vector mirrors the Values[TypeTyID] plane. It is used // to deal with forward references to types. @@ -123,7 +124,7 @@ private: // each function in the module. When the function is loaded, this function is // filled in. // - std::vector > FunctionSignatureList; + std::vector FunctionSignatureList; // Constant values are read in after global variables. Because of this, we // must defer setting the initializers on global variables until after module @@ -136,7 +137,7 @@ private: // information about each function: its begin and end pointer in the buffer // and its FunctionSlot. // - std::map LazyFunctionLoadMap; + std::map LazyFunctionLoadMap; private: void freeTable(ValueTable &Tab) { @@ -169,14 +170,13 @@ private: ValueTable &Tab, TypeValuesListTy &TypeTab); Constant *parseConstantValue(const unsigned char *&Buf, const unsigned char *End, - const Type *Ty); + unsigned TypeID); void parseTypeConstants(const unsigned char *&Buf, const unsigned char *EndBuf, TypeValuesListTy &Tab, unsigned NumEntries); const Type *parseTypeConstant(const unsigned char *&Buf, const unsigned char *EndBuf); - Value *getValue(const Type *Ty, unsigned num, bool Create = true); Value *getValue(unsigned TypeID, unsigned num, bool Create = true); const Type *getType(unsigned ID); BasicBlock *getBasicBlock(unsigned ID); @@ -185,13 +185,12 @@ private: return getConstantValue(getTypeSlot(Ty), num); } - unsigned insertValue(Value *V, ValueTable &Table); unsigned insertValue(Value *V, unsigned Type, ValueTable &Table); unsigned getTypeSlot(const Type *Ty); - // resolve all references to the placeholder (if any) for the given value - void ResolveReferencesToValue(Value *Val, unsigned Slot); + // resolve all references to the placeholder (if any) for the given constant + void ResolveReferencesToConstant(Constant *C, unsigned Slot); }; template -- 2.34.1