diff options
Diffstat (limited to 'lib/Bitcode/Writer')
-rw-r--r-- | lib/Bitcode/Writer/BitWriter.cpp | 14 | ||||
-rw-r--r-- | lib/Bitcode/Writer/BitcodeWriter.cpp | 174 | ||||
-rw-r--r-- | lib/Bitcode/Writer/ValueEnumerator.cpp | 333 | ||||
-rw-r--r-- | lib/Bitcode/Writer/ValueEnumerator.h | 16 |
4 files changed, 373 insertions, 164 deletions
diff --git a/lib/Bitcode/Writer/BitWriter.cpp b/lib/Bitcode/Writer/BitWriter.cpp index 3747122..7218ea0 100644 --- a/lib/Bitcode/Writer/BitWriter.cpp +++ b/lib/Bitcode/Writer/BitWriter.cpp @@ -18,10 +18,10 @@ using namespace llvm; /*===-- Operations on modules ---------------------------------------------===*/ int LLVMWriteBitcodeToFile(LLVMModuleRef M, const char *Path) { - std::string ErrorInfo; - raw_fd_ostream OS(Path, ErrorInfo, sys::fs::F_None); + std::error_code EC; + raw_fd_ostream OS(Path, EC, sys::fs::F_None); - if (!ErrorInfo.empty()) + if (EC) return -1; WriteBitcodeToFile(unwrap(M), OS); @@ -39,3 +39,11 @@ int LLVMWriteBitcodeToFD(LLVMModuleRef M, int FD, int ShouldClose, int LLVMWriteBitcodeToFileHandle(LLVMModuleRef M, int FileHandle) { return LLVMWriteBitcodeToFD(M, FileHandle, true, false); } + +LLVMMemoryBufferRef LLVMWriteBitcodeToMemoryBuffer(LLVMModuleRef M) { + std::string Data; + raw_string_ostream OS(Data); + + WriteBitcodeToFile(unwrap(M), OS); + return wrap(MemoryBuffer::getMemBufferCopy(OS.str()).release()); +} diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp index dd9282a..6cfc357 100644 --- a/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -22,6 +22,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/UseListOrder.h" #include "llvm/IR/ValueSymbolTable.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/ErrorHandling.h" @@ -32,12 +33,6 @@ #include <map> using namespace llvm; -static cl::opt<bool> -EnablePreserveUseListOrdering("enable-bc-uselist-preserve", - cl::desc("Turn on experimental support for " - "use-list order preservation."), - cl::init(false), cl::Hidden); - /// These are manifest constants used by the bitcode writer. They do not need to /// be kept in sync with the reader, but need to be consistent within this file. enum { @@ -201,6 +196,8 @@ static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) { return bitc::ATTR_KIND_NON_LAZY_BIND; case Attribute::NonNull: return bitc::ATTR_KIND_NON_NULL; + case Attribute::Dereferenceable: + return bitc::ATTR_KIND_DEREFERENCEABLE; case Attribute::NoRedZone: return bitc::ATTR_KIND_NO_RED_ZONE; case Attribute::NoReturn: @@ -272,7 +269,7 @@ static void WriteAttributeGroupTable(const ValueEnumerator &VE, if (Attr.isEnumAttribute()) { Record.push_back(0); Record.push_back(getAttrKindEncoding(Attr.getKindAsEnum())); - } else if (Attr.isAlignAttribute()) { + } else if (Attr.isIntAttribute()) { Record.push_back(1); Record.push_back(getAttrKindEncoding(Attr.getKindAsEnum())); Record.push_back(Attr.getValueAsInt()); @@ -713,18 +710,15 @@ static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE, static uint64_t GetOptimizationFlags(const Value *V) { uint64_t Flags = 0; - if (const OverflowingBinaryOperator *OBO = - dyn_cast<OverflowingBinaryOperator>(V)) { + if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(V)) { if (OBO->hasNoSignedWrap()) Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP; if (OBO->hasNoUnsignedWrap()) Flags |= 1 << bitc::OBO_NO_UNSIGNED_WRAP; - } else if (const PossiblyExactOperator *PEO = - dyn_cast<PossiblyExactOperator>(V)) { + } else if (const auto *PEO = dyn_cast<PossiblyExactOperator>(V)) { if (PEO->isExact()) Flags |= 1 << bitc::PEO_EXACT; - } else if (const FPMathOperator *FPMO = - dyn_cast<const FPMathOperator>(V)) { + } else if (const auto *FPMO = dyn_cast<FPMathOperator>(V)) { if (FPMO->hasUnsafeAlgebra()) Flags |= FastMathFlags::UnsafeAlgebra; if (FPMO->hasNoNaNs()) @@ -762,13 +756,13 @@ static void WriteMDNode(const MDNode *N, static void WriteModuleMetadata(const Module *M, const ValueEnumerator &VE, BitstreamWriter &Stream) { - const ValueEnumerator::ValueList &Vals = VE.getMDValues(); + const auto &Vals = VE.getMDValues(); bool StartedMetadataBlock = false; unsigned MDSAbbrev = 0; SmallVector<uint64_t, 64> Record; for (unsigned i = 0, e = Vals.size(); i != e; ++i) { - if (const MDNode *N = dyn_cast<MDNode>(Vals[i].first)) { + if (const MDNode *N = dyn_cast<MDNode>(Vals[i])) { if (!N->isFunctionLocal() || !N->getFunction()) { if (!StartedMetadataBlock) { Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3); @@ -776,7 +770,7 @@ static void WriteModuleMetadata(const Module *M, } WriteMDNode(N, VE, Stream, Record); } - } else if (const MDString *MDS = dyn_cast<MDString>(Vals[i].first)) { + } else if (const MDString *MDS = dyn_cast<MDString>(Vals[i])) { if (!StartedMetadataBlock) { Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3); @@ -854,7 +848,7 @@ static void WriteMetadataAttachment(const Function &F, // Write metadata attachments // METADATA_ATTACHMENT - [m x [value, [n x [id, mdnode]]] - SmallVector<std::pair<unsigned, MDNode*>, 4> MDs; + SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); @@ -1431,13 +1425,20 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, break; } - case Instruction::Alloca: + case Instruction::Alloca: { Code = bitc::FUNC_CODE_INST_ALLOCA; Vals.push_back(VE.getTypeID(I.getType())); Vals.push_back(VE.getTypeID(I.getOperand(0)->getType())); Vals.push_back(VE.getValueID(I.getOperand(0))); // size. - Vals.push_back(Log2_32(cast<AllocaInst>(I).getAlignment())+1); + const AllocaInst &AI = cast<AllocaInst>(I); + unsigned AlignRecord = Log2_32(AI.getAlignment()) + 1; + assert(Log2_32(Value::MaximumAlignment) + 1 < 1 << 5 && + "not enough bits for maximum alignment"); + assert(AlignRecord < 1 << 5 && "alignment greater than 1 << 64"); + AlignRecord |= AI.isUsedWithInAlloca() << 5; + Vals.push_back(AlignRecord); break; + } case Instruction::Load: if (cast<LoadInst>(I).isAtomic()) { @@ -1598,6 +1599,39 @@ static void WriteValueSymbolTable(const ValueSymbolTable &VST, Stream.ExitBlock(); } +static void WriteUseList(ValueEnumerator &VE, UseListOrder &&Order, + BitstreamWriter &Stream) { + assert(Order.Shuffle.size() >= 2 && "Shuffle too small"); + unsigned Code; + if (isa<BasicBlock>(Order.V)) + Code = bitc::USELIST_CODE_BB; + else + Code = bitc::USELIST_CODE_DEFAULT; + + SmallVector<uint64_t, 64> Record; + for (unsigned I : Order.Shuffle) + Record.push_back(I); + Record.push_back(VE.getValueID(Order.V)); + Stream.EmitRecord(Code, Record); +} + +static void WriteUseListBlock(const Function *F, ValueEnumerator &VE, + BitstreamWriter &Stream) { + auto hasMore = [&]() { + return !VE.UseListOrders.empty() && VE.UseListOrders.back().F == F; + }; + if (!hasMore()) + // Nothing to do. + return; + + Stream.EnterSubblock(bitc::USELIST_BLOCK_ID, 3); + while (hasMore()) { + WriteUseList(VE, std::move(VE.UseListOrders.back()), Stream); + VE.UseListOrders.pop_back(); + } + Stream.ExitBlock(); +} + /// WriteFunction - Emit a function body to the module stream. static void WriteFunction(const Function &F, ValueEnumerator &VE, BitstreamWriter &Stream) { @@ -1666,6 +1700,8 @@ static void WriteFunction(const Function &F, ValueEnumerator &VE, if (NeedsMetadataAttachment) WriteMetadataAttachment(F, VE, Stream); + if (shouldPreserveBitcodeUseListOrder()) + WriteUseListBlock(&F, VE, Stream); VE.purgeFunction(); Stream.ExitBlock(); } @@ -1831,98 +1867,6 @@ static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) { Stream.ExitBlock(); } -// Sort the Users based on the order in which the reader parses the bitcode -// file. -static bool bitcodereader_order(const User *lhs, const User *rhs) { - // TODO: Implement. - return true; -} - -static void WriteUseList(const Value *V, const ValueEnumerator &VE, - BitstreamWriter &Stream) { - - // One or zero uses can't get out of order. - if (V->use_empty() || V->hasNUses(1)) - return; - - // Make a copy of the in-memory use-list for sorting. - SmallVector<const User*, 8> UserList(V->user_begin(), V->user_end()); - - // Sort the copy based on the order read by the BitcodeReader. - std::sort(UserList.begin(), UserList.end(), bitcodereader_order); - - // TODO: Generate a diff between the BitcodeWriter in-memory use-list and the - // sorted list (i.e., the expected BitcodeReader in-memory use-list). - - // TODO: Emit the USELIST_CODE_ENTRYs. -} - -static void WriteFunctionUseList(const Function *F, ValueEnumerator &VE, - BitstreamWriter &Stream) { - VE.incorporateFunction(*F); - - for (Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end(); - AI != AE; ++AI) - WriteUseList(AI, VE, Stream); - for (Function::const_iterator BB = F->begin(), FE = F->end(); BB != FE; - ++BB) { - WriteUseList(BB, VE, Stream); - for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); II != IE; - ++II) { - WriteUseList(II, VE, Stream); - for (User::const_op_iterator OI = II->op_begin(), E = II->op_end(); - OI != E; ++OI) { - if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || - isa<InlineAsm>(*OI)) - WriteUseList(*OI, VE, Stream); - } - } - } - VE.purgeFunction(); -} - -// Emit use-lists. -static void WriteModuleUseLists(const Module *M, ValueEnumerator &VE, - BitstreamWriter &Stream) { - Stream.EnterSubblock(bitc::USELIST_BLOCK_ID, 3); - - // XXX: this modifies the module, but in a way that should never change the - // behavior of any pass or codegen in LLVM. The problem is that GVs may - // contain entries in the use_list that do not exist in the Module and are - // not stored in the .bc file. - for (Module::const_global_iterator I = M->global_begin(), E = M->global_end(); - I != E; ++I) - I->removeDeadConstantUsers(); - - // Write the global variables. - for (Module::const_global_iterator GI = M->global_begin(), - GE = M->global_end(); GI != GE; ++GI) { - WriteUseList(GI, VE, Stream); - - // Write the global variable initializers. - if (GI->hasInitializer()) - WriteUseList(GI->getInitializer(), VE, Stream); - } - - // Write the functions. - for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI) { - WriteUseList(FI, VE, Stream); - if (!FI->isDeclaration()) - WriteFunctionUseList(FI, VE, Stream); - if (FI->hasPrefixData()) - WriteUseList(FI->getPrefixData(), VE, Stream); - } - - // Write the aliases. - for (Module::const_alias_iterator AI = M->alias_begin(), AE = M->alias_end(); - AI != AE; ++AI) { - WriteUseList(AI, VE, Stream); - WriteUseList(AI->getAliasee(), VE, Stream); - } - - Stream.ExitBlock(); -} - /// WriteModule - Emit the specified module to the bitstream. static void WriteModule(const Module *M, BitstreamWriter &Stream) { Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3); @@ -1933,7 +1877,7 @@ static void WriteModule(const Module *M, BitstreamWriter &Stream) { Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals); // Analyze the module, enumerating globals, functions, etc. - ValueEnumerator VE(M); + ValueEnumerator VE(*M); // Emit blockinfo, which defines the standard abbreviations etc. WriteBlockInfo(VE, Stream); @@ -1965,9 +1909,9 @@ static void WriteModule(const Module *M, BitstreamWriter &Stream) { // Emit names for globals/functions etc. WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream); - // Emit use-lists. - if (EnablePreserveUseListOrdering) - WriteModuleUseLists(M, VE, Stream); + // Emit module-level use-lists. + if (shouldPreserveBitcodeUseListOrder()) + WriteUseListBlock(nullptr, VE, Stream); // Emit function bodies. for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) diff --git a/lib/Bitcode/Writer/ValueEnumerator.cpp b/lib/Bitcode/Writer/ValueEnumerator.cpp index 15f8034..f065c83 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.cpp +++ b/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -18,31 +18,280 @@ #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Module.h" +#include "llvm/IR/UseListOrder.h" #include "llvm/IR/ValueSymbolTable.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> using namespace llvm; +namespace { +struct OrderMap { + DenseMap<const Value *, std::pair<unsigned, bool>> IDs; + unsigned LastGlobalConstantID; + unsigned LastGlobalValueID; + + OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {} + + bool isGlobalConstant(unsigned ID) const { + return ID <= LastGlobalConstantID; + } + bool isGlobalValue(unsigned ID) const { + return ID <= LastGlobalValueID && !isGlobalConstant(ID); + } + + 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; + } +}; +} + +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)) + for (const Value *Op : C->operands()) + if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op)) + orderValue(Op, 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 Function &F : M) + if (F.hasPrefixData()) + if (!isa<GlobalValue>(F.getPrefixData())) + orderValue(F.getPrefixData(), OM); + 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 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); + 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. + typedef std::pair<const Use *, unsigned> Entry; + SmallVector<Entry, 64> List; + for (const Use &U : V->uses()) + // Check if this user will be serialized. + if (OM.lookup(U.getUser()).first) + List.push_back(std::make_pair(&U, List.size())); + + if (List.size() < 2) + // We may have lost some users. + return; + + bool IsGlobalValue = OM.isGlobalValue(ID); + std::sort(List.begin(), List.end(), [&](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)) + 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) { + if (LID <= ID) + if (!IsGlobalValue) // GlobalValue uses don't get reversed. + return false; + return true; + } + + // LID and RID are equal, so we have different operands of the same user. + // Assume operands are added in order for all instructions. + if (LID <= ID) + if (!IsGlobalValue) // GlobalValue uses don't get reversed. + return LU->getOperandNo() < RU->getOperandNo(); + return LU->getOperandNo() > RU->getOperandNo(); + }); + + if (std::is_sorted( + List.begin(), List.end(), + [](const Entry &L, const Entry &R) { return L.second < R.second; })) + // Order is already correct. + return; + + // Store the shuffle. + Stack.emplace_back(V, F, List.size()); + assert(List.size() == Stack.back().Shuffle.size() && "Wrong size"); + for (size_t I = 0, E = List.size(); I != E; ++I) + Stack.back().Shuffle[I] = List[I].second; +} + +static void predictValueUseListOrder(const Value *V, const Function *F, + OrderMap &OM, UseListOrderStack &Stack) { + auto &IDPair = OM[V]; + assert(IDPair.first && "Unmapped value"); + if (IDPair.second) + // Already predicted. + return; + + // Do the actual prediction. + IDPair.second = true; + if (!V->use_empty() && std::next(V->use_begin()) != V->use_end()) + predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack); + + // Recursive descent into constants. + if (const Constant *C = dyn_cast<Constant>(V)) + if (C->getNumOperands()) // Visit GlobalValues. + for (const Value *Op : C->operands()) + if (isa<Constant>(Op)) // Visit GlobalValues. + predictValueUseListOrder(Op, F, OM, Stack); +} + +static UseListOrderStack predictUseListOrder(const Module &M) { + OrderMap OM = orderModule(M); + + // Use-list orders need to be serialized after all the users have been added + // to a value, or else the shuffles will be incomplete. Store them per + // function in a stack. + // + // Aside from function order, the order of values doesn't matter much here. + UseListOrderStack Stack; + + // We want to visit the functions backward now so we can list function-local + // constants in the last Function they're used in. Module-level constants + // have already been visited above. + for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) { + const Function &F = *I; + if (F.isDeclaration()) + continue; + for (const BasicBlock &BB : F) + predictValueUseListOrder(&BB, &F, OM, Stack); + for (const Argument &A : F.args()) + predictValueUseListOrder(&A, &F, OM, Stack); + 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); + 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()) + predictValueUseListOrder(&A, nullptr, OM, Stack); + for (const GlobalVariable &G : M.globals()) + if (G.hasInitializer()) + predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack); + for (const GlobalAlias &A : M.aliases()) + predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack); + for (const Function &F : M) + if (F.hasPrefixData()) + predictValueUseListOrder(F.getPrefixData(), nullptr, OM, Stack); + + return Stack; +} + static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { return V.first->getType()->isIntOrIntVectorTy(); } -/// ValueEnumerator - Enumerate module-level information. -ValueEnumerator::ValueEnumerator(const Module *M) { +ValueEnumerator::ValueEnumerator(const Module &M) { + if (shouldPreserveBitcodeUseListOrder()) + UseListOrders = predictUseListOrder(M); + // Enumerate the global variables. - for (Module::const_global_iterator I = M->global_begin(), - E = M->global_end(); I != E; ++I) + for (Module::const_global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) EnumerateValue(I); // Enumerate the functions. - for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { + for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) { EnumerateValue(I); EnumerateAttributes(cast<Function>(I)->getAttributes()); } // Enumerate the aliases. - for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); + for (Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; ++I) EnumerateValue(I); @@ -50,30 +299,30 @@ ValueEnumerator::ValueEnumerator(const Module *M) { unsigned FirstConstant = Values.size(); // Enumerate the global variable initializers. - for (Module::const_global_iterator I = M->global_begin(), - E = M->global_end(); I != E; ++I) + for (Module::const_global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) if (I->hasInitializer()) EnumerateValue(I->getInitializer()); // Enumerate the aliasees. - for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); + for (Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; ++I) EnumerateValue(I->getAliasee()); // Enumerate the prefix data constants. - for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) + for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) if (I->hasPrefixData()) EnumerateValue(I->getPrefixData()); // Insert constants and metadata that are named at module level into the slot // pool so that the module symbol table can refer to them... - EnumerateValueSymbolTable(M->getValueSymbolTable()); + EnumerateValueSymbolTable(M.getValueSymbolTable()); EnumerateNamedMetadata(M); - SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; + SmallVector<std::pair<unsigned, MDNode *>, 8> MDs; // Enumerate types used by function bodies and argument lists. - for (const Function &F : *M) { + for (const Function &F : M) { for (const Argument &A : F.args()) EnumerateType(A.getType()); @@ -179,6 +428,11 @@ void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { if (CstStart == CstEnd || CstStart+1 == CstEnd) return; + if (shouldPreserveBitcodeUseListOrder()) + // Optimizing constants makes the use-list order difficult to predict. + // Disable it for now when trying to preserve the order. + return; + std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd, [this](const std::pair<const Value *, unsigned> &LHS, const std::pair<const Value *, unsigned> &RHS) { @@ -209,11 +463,12 @@ void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { EnumerateValue(VI->getValue()); } -/// EnumerateNamedMetadata - Insert all of the values referenced by -/// named metadata in the specified module. -void ValueEnumerator::EnumerateNamedMetadata(const Module *M) { - for (Module::const_named_metadata_iterator I = M->named_metadata_begin(), - E = M->named_metadata_end(); I != E; ++I) +/// Insert all of the values referenced by named metadata in the specified +/// module. +void ValueEnumerator::EnumerateNamedMetadata(const Module &M) { + for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), + E = M.named_metadata_end(); + I != E; ++I) EnumerateNamedMDNode(I); } @@ -239,31 +494,31 @@ void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { void ValueEnumerator::EnumerateMetadata(const Value *MD) { assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind"); - // Enumerate the type of this value. - EnumerateType(MD->getType()); - + // Skip function-local nodes themselves, but walk their operands. const MDNode *N = dyn_cast<MDNode>(MD); - - // In the module-level pass, skip function-local nodes themselves, but - // do walk their operands. if (N && N->isFunctionLocal() && N->getFunction()) { EnumerateMDNodeOperands(N); return; } - // Check to see if it's already in! - unsigned &MDValueID = MDValueMap[MD]; - if (MDValueID) { - // Increment use count. - MDValues[MDValueID-1].second++; + // Insert a dummy ID to block the co-recursive call to + // EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph. + // + // Return early if there's already an ID. + if (!MDValueMap.insert(std::make_pair(MD, 0)).second) return; - } - MDValues.push_back(std::make_pair(MD, 1U)); - MDValueID = MDValues.size(); - // Enumerate all non-function-local operands. + // Enumerate the type of this value. + EnumerateType(MD->getType()); + + // Visit operands first to minimize RAUW. if (N) EnumerateMDNodeOperands(N); + + // Replace the dummy ID inserted above with the correct one. MDValueMap may + // have changed by inserting operands, so we need a fresh lookup here. + MDValues.push_back(MD); + MDValueMap[MD] = MDValues.size(); } /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata @@ -277,12 +532,10 @@ void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) { // Check to see if it's already in! unsigned &MDValueID = MDValueMap[N]; - if (MDValueID) { - // Increment use count. - MDValues[MDValueID-1].second++; + if (MDValueID) return; - } - MDValues.push_back(std::make_pair(N, 1U)); + + MDValues.push_back(N); MDValueID = MDValues.size(); // To incoroporate function-local information visit all function-local @@ -487,7 +740,7 @@ void ValueEnumerator::incorporateFunction(const Function &F) { FnLocalMDVector.push_back(MD); } - SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; + SmallVector<std::pair<unsigned, MDNode *>, 8> MDs; I->getAllMetadataOtherThanDebugLoc(MDs); for (unsigned i = 0, e = MDs.size(); i != e; ++i) { MDNode *N = MDs[i].second; @@ -510,7 +763,7 @@ void ValueEnumerator::purgeFunction() { for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) ValueMap.erase(Values[i].first); for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i) - MDValueMap.erase(MDValues[i].first); + MDValueMap.erase(MDValues[i]); for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) ValueMap.erase(BasicBlocks[i]); diff --git a/lib/Bitcode/Writer/ValueEnumerator.h b/lib/Bitcode/Writer/ValueEnumerator.h index 1c9f38e..563c214 100644 --- a/lib/Bitcode/Writer/ValueEnumerator.h +++ b/lib/Bitcode/Writer/ValueEnumerator.h @@ -11,13 +11,14 @@ // //===----------------------------------------------------------------------===// -#ifndef VALUE_ENUMERATOR_H -#define VALUE_ENUMERATOR_H +#ifndef LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H +#define LLVM_LIB_BITCODE_WRITER_VALUEENUMERATOR_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/UniqueVector.h" #include "llvm/IR/Attributes.h" +#include "llvm/IR/UseListOrder.h" #include <vector> namespace llvm { @@ -42,6 +43,9 @@ public: // For each value, we remember its Value* and occurrence frequency. typedef std::vector<std::pair<const Value*, unsigned> > ValueList; + + UseListOrderStack UseListOrders; + private: typedef DenseMap<Type*, unsigned> TypeMapType; TypeMapType TypeMap; @@ -54,7 +58,7 @@ private: typedef UniqueVector<const Comdat *> ComdatSetType; ComdatSetType Comdats; - ValueList MDValues; + std::vector<const Value *> MDValues; SmallVector<const MDNode *, 8> FunctionLocalMDs; ValueMapType MDValueMap; @@ -92,7 +96,7 @@ private: ValueEnumerator(const ValueEnumerator &) LLVM_DELETED_FUNCTION; void operator=(const ValueEnumerator &) LLVM_DELETED_FUNCTION; public: - ValueEnumerator(const Module *M); + ValueEnumerator(const Module &M); void dump() const; void print(raw_ostream &OS, const ValueMapType &Map, const char *Name) const; @@ -130,7 +134,7 @@ public: } const ValueList &getValues() const { return Values; } - const ValueList &getMDValues() const { return MDValues; } + const std::vector<const Value *> &getMDValues() const { return MDValues; } const SmallVectorImpl<const MDNode *> &getFunctionLocalMDValues() const { return FunctionLocalMDs; } @@ -172,7 +176,7 @@ private: void EnumerateAttributes(AttributeSet PAL); void EnumerateValueSymbolTable(const ValueSymbolTable &ST); - void EnumerateNamedMetadata(const Module *M); + void EnumerateNamedMetadata(const Module &M); }; } // End llvm namespace |