CbC/CbC_llvm: lib/Bitcode/Writer/ValueEnumerator.cpp comparison

comparison lib/Bitcode/Writer/ValueEnumerator.cpp @ 120:1172e4bd9c6f

update 4.0.0

author	mir3636
date	Fri, 25 Nov 2016 19:14:25 +0900
parents	7d135dc70f03
children	803732b1fca8

comparison

equal deleted inserted replaced

-:34baf5011add
+:1172e4bd9c6f
 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 GlobalIFunc &I : M.ifuncs())
+if (!isa<GlobalValue>(I.getResolver()))
+orderValue(I.getResolver(), OM);
 for (const Function &F : M) {
 for (const Use &U : F.operands())
 if (!isa<GlobalValue>(U.get()))
 orderValue(U.get(), OM);
 }
 // uses in their initializers.
 for (const Function &F : M)
 orderValue(&F, OM);
 for (const GlobalAlias &A : M.aliases())
 orderValue(&A, OM);
+for (const GlobalIFunc &I : M.ifuncs())
+orderValue(&I, OM);
 for (const GlobalVariable &G : M.globals())
 orderValue(&G, OM);
 OM.LastGlobalValueID = OM.size();
 for (const Function &F : M) {
 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 GlobalIFunc &I : M.ifuncs())
+predictValueUseListOrder(&I, 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 GlobalIFunc &I : M.ifuncs())
+predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
 for (const Function &F : M) {
 for (const Use &U : F.operands())
 predictValueUseListOrder(U.get(), nullptr, OM, Stack);
 }
 return V.first->getType()->isIntOrIntVectorTy();
 }
 ValueEnumerator::ValueEnumerator(const Module &M,
 bool ShouldPreserveUseListOrder)
-: HasMDString(false), HasDILocation(false), HasGenericDINode(false),
+: ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
-ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
 if (ShouldPreserveUseListOrder)
 UseListOrders = predictUseListOrder(M);
 // Enumerate the global variables.
 for (const GlobalVariable &GV : M.globals())
 // Enumerate the aliases.
 for (const GlobalAlias &GA : M.aliases())
 EnumerateValue(&GA);
+// Enumerate the ifuncs.
+for (const GlobalIFunc &GIF : M.ifuncs())
+EnumerateValue(&GIF);
 // Remember what is the cutoff between globalvalue's and other constants.
 unsigned FirstConstant = Values.size();
 // Enumerate the global variable initializers.
 for (const GlobalVariable &GV : M.globals())
 EnumerateValue(GV.getInitializer());
 // Enumerate the aliasees.
 for (const GlobalAlias &GA : M.aliases())
 EnumerateValue(GA.getAliasee());
+// Enumerate the ifunc resolvers.
+for (const GlobalIFunc &GIF : M.ifuncs())
+EnumerateValue(GIF.getResolver());
 // Enumerate any optional Function data.
 for (const Function &F : M)
 for (const Use &U : F.operands())
 EnumerateValue(U.get());
 // pool so that the module symbol table can refer to them...
 EnumerateValueSymbolTable(M.getValueSymbolTable());
 EnumerateNamedMetadata(M);
 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
+for (const GlobalVariable &GV : M.globals()) {
+MDs.clear();
+GV.getAllMetadata(MDs);
+for (const auto &I : MDs)
+// FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
+// to write metadata to the global variable's own metadata block
+// (PR28134).
+EnumerateMetadata(nullptr, I.second);
+}
 // Enumerate types used by function bodies and argument lists.
 for (const Function &F : M) {
 for (const Argument &A : F.args())
 EnumerateType(A.getType());
 // Enumerate metadata attached to this function.
+MDs.clear();
 F.getAllMetadata(MDs);
 for (const auto &I : MDs)
-EnumerateMetadata(I.second);
+EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
 for (const BasicBlock &BB : F)
 for (const Instruction &I : BB) {
 for (const Use &Op : I.operands()) {
 auto *MD = dyn_cast<MetadataAsValue>(&Op);
 // Local metadata is enumerated during function-incorporation.
 if (isa<LocalAsMetadata>(MD->getMetadata()))
 continue;
-EnumerateMetadata(MD->getMetadata());
+EnumerateMetadata(&F, MD->getMetadata());
 }
 EnumerateType(I.getType());
 if (const CallInst *CI = dyn_cast<CallInst>(&I))
 EnumerateAttributes(CI->getAttributes());
 else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
 // Enumerate metadata attached with this instruction.
 MDs.clear();
 I.getAllMetadataOtherThanDebugLoc(MDs);
 for (unsigned i = 0, e = MDs.size(); i != e; ++i)
-EnumerateMetadata(MDs[i].second);
+EnumerateMetadata(&F, MDs[i].second);
 // Don't enumerate the location directly -- it has a special record
 // type -- but enumerate its operands.
 if (DILocation *L = I.getDebugLoc())
-EnumerateMDNodeOperands(L);
+for (const Metadata *Op : L->operands())
+EnumerateMetadata(&F, Op);
 }
 }
 // Optimize constant ordering.
 OptimizeConstants(FirstConstant, Values.size());
+// Organize metadata ordering.
+organizeMetadata();
 }
 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
 InstructionMapType::const_iterator I = InstructionMap.find(Inst);
 assert(I != InstructionMap.end() && "Instruction is not mapped!");
 ValueMapType::const_iterator I = ValueMap.find(V);
 assert(I != ValueMap.end() && "Value not in slotcalculator!");
 return I->second-1;
 }
-void ValueEnumerator::dump() const {
+LLVM_DUMP_METHOD void ValueEnumerator::dump() const {
 print(dbgs(), ValueMap, "Default");
 dbgs() << '\n';
 print(dbgs(), MetadataMap, "MetaData");
 dbgs() << '\n';
 }
 OS << "Map Name: " << Name << "\n";
 OS << "Size: " << Map.size() << "\n";
 for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
 const Metadata *MD = I->first;
-OS << "Metadata: slot = " << I->second << "\n";
+OS << "Metadata: slot = " << I->second.ID << "\n";
+OS << "Metadata: function = " << I->second.F << "\n";
 MD->print(OS);
+OS << "\n";
 }
 }
 /// OptimizeConstants - Reorder constant pool for denser encoding.
 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
 });
 // Ensure that integer and vector of integer constants are at the start of the
 // constant pool.  This is important so that GEP structure indices come before
 // gep constant exprs.
-std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
+std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
 isIntOrIntVectorValue);
 // Rebuild the modified portion of ValueMap.
 for (; CstStart != CstEnd; ++CstStart)
 ValueMap[Values[CstStart].first] = CstStart+1;
 }
 EnumerateNamedMDNode(&I);
 }
 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
 for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
-EnumerateMetadata(MD->getOperand(i));
+EnumerateMetadata(nullptr, MD->getOperand(i));
 }
-/// EnumerateMDNodeOperands - Enumerate all non-function-local values
+unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
-/// and types referenced by the given MDNode.
+return F ? getValueID(F) + 1 : 0;
-void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
+}
-for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
-Metadata *MD = N->getOperand(i);
+void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
-if (!MD)
+EnumerateMetadata(getMetadataFunctionID(F), MD);
+}
+void ValueEnumerator::EnumerateFunctionLocalMetadata(
+const Function &F, const LocalAsMetadata *Local) {
+EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
+}
+void ValueEnumerator::dropFunctionFromMetadata(
+MetadataMapType::value_type &FirstMD) {
+SmallVector<const MDNode *, 64> Worklist;
+auto push = [this, &Worklist](MetadataMapType::value_type &MD) {
+auto &Entry = MD.second;
+// Nothing to do if this metadata isn't tagged.
+if (!Entry.F)
+return;
+// Drop the function tag.
+Entry.F = 0;
+// If this is has an ID and is an MDNode, then its operands have entries as
+// well.  We need to drop the function from them too.
+if (Entry.ID)
+if (auto *N = dyn_cast<MDNode>(MD.first))
+Worklist.push_back(N);
+};
+push(FirstMD);
+while (!Worklist.empty())
+for (const Metadata *Op : Worklist.pop_back_val()->operands()) {
+if (!Op)
+continue;
+auto MD = MetadataMap.find(Op);
+if (MD != MetadataMap.end())
+push(*MD);
+}
+}
+void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
+// It's vital for reader efficiency that uniqued subgraphs are done in
+// post-order; it's expensive when their operands have forward references.
+// If a distinct node is referenced from a uniqued node, it'll be delayed
+// until the uniqued subgraph has been completely traversed.
+SmallVector<const MDNode *, 32> DelayedDistinctNodes;
+// Start by enumerating MD, and then work through its transitive operands in
+// post-order.  This requires a depth-first search.
+SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist;
+if (const MDNode *N = enumerateMetadataImpl(F, MD))
+Worklist.push_back(std::make_pair(N, N->op_begin()));
+while (!Worklist.empty()) {
+const MDNode *N = Worklist.back().first;
+// Enumerate operands until we hit a new node.  We need to traverse these
+// nodes' operands before visiting the rest of N's operands.
+MDNode::op_iterator I = std::find_if(
+Worklist.back().second, N->op_end(),
+[&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
+if (I != N->op_end()) {
+auto *Op = cast<MDNode>(*I);
+Worklist.back().second = ++I;
+// Delay traversing Op if it's a distinct node and N is uniqued.
+if (Op->isDistinct() && !N->isDistinct())
+DelayedDistinctNodes.push_back(Op);
+else
+Worklist.push_back(std::make_pair(Op, Op->op_begin()));
 continue;
-assert(!isa<LocalAsMetadata>(MD) && "MDNodes cannot be function-local");
+}
-EnumerateMetadata(MD);
-}
+// All the operands have been visited.  Now assign an ID.
-}
+Worklist.pop_back();
+MDs.push_back(N);
-void ValueEnumerator::EnumerateMetadata(const Metadata *MD) {
+MetadataMap[N].ID = MDs.size();
+// Flush out any delayed distinct nodes; these are all the distinct nodes
+// that are leaves in last uniqued subgraph.
+if (Worklist.empty() || Worklist.back().first->isDistinct()) {
+for (const MDNode *N : DelayedDistinctNodes)
+Worklist.push_back(std::make_pair(N, N->op_begin()));
+DelayedDistinctNodes.clear();
+}
+}
+}
+const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) {
+if (!MD)
+return nullptr;
 assert(
 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
 "Invalid metadata kind");
-// Insert a dummy ID to block the co-recursive call to
+auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));
-// EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph.
+MDIndex &Entry = Insertion.first->second;
-//
+if (!Insertion.second) {
-// Return early if there's already an ID.
+// Already mapped.  If F doesn't match the function tag, drop it.
-if (!MetadataMap.insert(std::make_pair(MD, 0)).second)
+if (Entry.hasDifferentFunction(F))
-return;
+dropFunctionFromMetadata(*Insertion.first);
+return nullptr;
-// Visit operands first to minimize RAUW.
+}
+// Don't assign IDs to metadata nodes.
 if (auto *N = dyn_cast<MDNode>(MD))
-EnumerateMDNodeOperands(N);
+return N;
-else if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
+// Save the metadata.
+MDs.push_back(MD);
+Entry.ID = MDs.size();
+// Enumerate the constant, if any.
+if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
 EnumerateValue(C->getValue());
-HasMDString |= isa<MDString>(MD);
+return nullptr;
-HasDILocation |= isa<DILocation>(MD);
-HasGenericDINode |= isa<GenericDINode>(MD);
-// Replace the dummy ID inserted above with the correct one.  MetadataMap may
-// have changed by inserting operands, so we need a fresh lookup here.
-MDs.push_back(MD);
-MetadataMap[MD] = MDs.size();
 }
 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
 /// information reachable from the metadata.
 void ValueEnumerator::EnumerateFunctionLocalMetadata(
-const LocalAsMetadata *Local) {
+unsigned F, const LocalAsMetadata *Local) {
+assert(F && "Expected a function");
 // Check to see if it's already in!
-unsigned &MetadataID = MetadataMap[Local];
+MDIndex &Index = MetadataMap[Local];
-if (MetadataID)
+if (Index.ID) {
-return;
+assert(Index.F == F && "Expected the same function");
+return;
+}
 MDs.push_back(Local);
-MetadataID = MDs.size();
+Index.F = F;
+Index.ID = MDs.size();
 EnumerateValue(Local->getValue());
+}
-// Also, collect all function-local metadata for easy access.
-FunctionLocalMDs.push_back(Local);
+static unsigned getMetadataTypeOrder(const Metadata *MD) {
+// Strings are emitted in bulk and must come first.
+if (isa<MDString>(MD))
+return 0;
+// ConstantAsMetadata doesn't reference anything.  We may as well shuffle it
+// to the front since we can detect it.
+auto *N = dyn_cast<MDNode>(MD);
+if (!N)
+return 1;
+// The reader is fast forward references for distinct node operands, but slow
+// when uniqued operands are unresolved.
+return N->isDistinct() ? 2 : 3;
+}
+void ValueEnumerator::organizeMetadata() {
+assert(MetadataMap.size() == MDs.size() &&
+"Metadata map and vector out of sync");
+if (MDs.empty())
+return;
+// Copy out the index information from MetadataMap in order to choose a new
+// order.
+SmallVector<MDIndex, 64> Order;
+Order.reserve(MetadataMap.size());
+for (const Metadata *MD : MDs)
+Order.push_back(MetadataMap.lookup(MD));
+// Partition:
+//   - by function, then
+//   - by isa<MDString>
+// and then sort by the original/current ID.  Since the IDs are guaranteed to
+// be unique, the result of std::sort will be deterministic.  There's no need
+// for std::stable_sort.
+std::sort(Order.begin(), Order.end(), [this](MDIndex LHS, MDIndex RHS) {
+return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <
+std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);
+});
+// Rebuild MDs, index the metadata ranges for each function in FunctionMDs,
+// and fix up MetadataMap.
+std::vector<const Metadata *> OldMDs = std::move(MDs);
+MDs.reserve(OldMDs.size());
+for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {
+auto *MD = Order[I].get(OldMDs);
+MDs.push_back(MD);
+MetadataMap[MD].ID = I + 1;
+if (isa<MDString>(MD))
+++NumMDStrings;
+}
+// Return early if there's nothing for the functions.
+if (MDs.size() == Order.size())
+return;
+// Build the function metadata ranges.
+MDRange R;
+FunctionMDs.reserve(OldMDs.size());
+unsigned PrevF = 0;
+for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;
+++I) {
+unsigned F = Order[I].F;
+if (!PrevF) {
+PrevF = F;
+} else if (PrevF != F) {
+R.Last = FunctionMDs.size();
+std::swap(R, FunctionMDInfo[PrevF]);
+R.First = FunctionMDs.size();
+ID = MDs.size();
+PrevF = F;
+}
+auto *MD = Order[I].get(OldMDs);
+FunctionMDs.push_back(MD);
+MetadataMap[MD].ID = ++ID;
+if (isa<MDString>(MD))
+++R.NumStrings;
+}
+R.Last = FunctionMDs.size();
+FunctionMDInfo[PrevF] = R;
+}
+void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {
+NumModuleMDs = MDs.size();
+auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);
+NumMDStrings = R.NumStrings;
+MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,
+FunctionMDs.begin() + R.Last);
 }
 void ValueEnumerator::EnumerateValue(const Value *V) {
 assert(!V->getType()->isVoidTy() && "Can't insert void values!");
 assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
 // Enumerate the types for the specified value.  If the value is a constant,
 // walk through it, enumerating the types of the constant.
 void ValueEnumerator::EnumerateOperandType(const Value *V) {
 EnumerateType(V->getType());
-if (auto *MD = dyn_cast<MetadataAsValue>(V)) {
+assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
-assert(!isa<LocalAsMetadata>(MD->getMetadata()) &&
-"Function-local metadata should be left for later");
-EnumerateMetadata(MD->getMetadata());
-return;
-}
 const Constant *C = dyn_cast<Constant>(V);
 if (!C)
 return;
 }
 void ValueEnumerator::incorporateFunction(const Function &F) {
 InstructionCount = 0;
 NumModuleValues = Values.size();
-NumModuleMDs = MDs.size();
+// Add global metadata to the function block.  This doesn't include
+// LocalAsMetadata.
+incorporateFunctionMetadata(F);
 // Adding function arguments to the value table.
 for (const auto &I : F.args())
 EnumerateValue(&I);
 EnumerateValue(&I);
 }
 }
 // Add all of the function-local metadata.
-for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
+for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
-EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
+// At this point, every local values have been incorporated, we shouldn't
+// have a metadata operand that references a value that hasn't been seen.
+assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
+"Missing value for metadata operand");
+EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
+}
 }
 void ValueEnumerator::purgeFunction() {
 /// Remove purged values from the ValueMap.
 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
 ValueMap.erase(BasicBlocks[i]);
 Values.resize(NumModuleValues);
 MDs.resize(NumModuleMDs);
 BasicBlocks.clear();
-FunctionLocalMDs.clear();
+NumMDStrings = 0;
 }
 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
 DenseMap<const BasicBlock*, unsigned> &IDMap) {
 unsigned Counter = 0;

Mercurial > hg > CbC > CbC_llvm

comparison lib/Bitcode/Writer/ValueEnumerator.cpp @ 120:1172e4bd9c6f