1146 lines · cpp
1//===- ValueEnumerator.cpp - Number values and types for bitcode writer ---===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the ValueEnumerator class.10// Forked from lib/Bitcode/Writer11//12//===----------------------------------------------------------------------===//13 14#include "DXILValueEnumerator.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/Config/llvm-config.h"17#include "llvm/IR/Argument.h"18#include "llvm/IR/BasicBlock.h"19#include "llvm/IR/Constant.h"20#include "llvm/IR/DebugInfoMetadata.h"21#include "llvm/IR/DerivedTypes.h"22#include "llvm/IR/Function.h"23#include "llvm/IR/GlobalAlias.h"24#include "llvm/IR/GlobalIFunc.h"25#include "llvm/IR/GlobalObject.h"26#include "llvm/IR/GlobalValue.h"27#include "llvm/IR/GlobalVariable.h"28#include "llvm/IR/Instruction.h"29#include "llvm/IR/Instructions.h"30#include "llvm/IR/Metadata.h"31#include "llvm/IR/Module.h"32#include "llvm/IR/Operator.h"33#include "llvm/IR/Type.h"34#include "llvm/IR/TypedPointerType.h"35#include "llvm/IR/Use.h"36#include "llvm/IR/User.h"37#include "llvm/IR/Value.h"38#include "llvm/IR/ValueSymbolTable.h"39#include "llvm/Support/Casting.h"40#include "llvm/Support/Compiler.h"41#include "llvm/Support/Debug.h"42#include "llvm/Support/MathExtras.h"43#include "llvm/Support/raw_ostream.h"44#include <algorithm>45#include <cstddef>46#include <iterator>47#include <tuple>48 49using namespace llvm;50using namespace llvm::dxil;51 52namespace {53 54struct OrderMap {55 DenseMap<const Value *, std::pair<unsigned, bool>> IDs;56 unsigned LastGlobalConstantID = 0;57 unsigned LastGlobalValueID = 0;58 59 OrderMap() = default;60 61 bool isGlobalConstant(unsigned ID) const {62 return ID <= LastGlobalConstantID;63 }64 65 bool isGlobalValue(unsigned ID) const {66 return ID <= LastGlobalValueID && !isGlobalConstant(ID);67 }68 69 unsigned size() const { return IDs.size(); }70 std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }71 72 std::pair<unsigned, bool> lookup(const Value *V) const {73 return IDs.lookup(V);74 }75 76 void index(const Value *V) {77 // Explicitly sequence get-size and insert-value operations to avoid UB.78 unsigned ID = IDs.size() + 1;79 IDs[V].first = ID;80 }81};82 83} // end anonymous namespace84 85static void orderValue(const Value *V, OrderMap &OM) {86 if (OM.lookup(V).first)87 return;88 89 if (const Constant *C = dyn_cast<Constant>(V)) {90 if (C->getNumOperands() && !isa<GlobalValue>(C)) {91 for (const Value *Op : C->operands())92 if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))93 orderValue(Op, OM);94 if (auto *CE = dyn_cast<ConstantExpr>(C))95 if (CE->getOpcode() == Instruction::ShuffleVector)96 orderValue(CE->getShuffleMaskForBitcode(), OM);97 }98 }99 100 // Note: we cannot cache this lookup above, since inserting into the map101 // changes the map's size, and thus affects the other IDs.102 OM.index(V);103}104 105static OrderMap orderModule(const Module &M) {106 // This needs to match the order used by ValueEnumerator::ValueEnumerator()107 // and ValueEnumerator::incorporateFunction().108 OrderMap OM;109 110 // In the reader, initializers of GlobalValues are set *after* all the111 // globals have been read. Rather than awkwardly modeling this behaviour112 // directly in predictValueUseListOrderImpl(), just assign IDs to113 // initializers of GlobalValues before GlobalValues themselves to model this114 // implicitly.115 for (const GlobalVariable &G : M.globals())116 if (G.hasInitializer())117 if (!isa<GlobalValue>(G.getInitializer()))118 orderValue(G.getInitializer(), OM);119 for (const GlobalAlias &A : M.aliases())120 if (!isa<GlobalValue>(A.getAliasee()))121 orderValue(A.getAliasee(), OM);122 for (const GlobalIFunc &I : M.ifuncs())123 if (!isa<GlobalValue>(I.getResolver()))124 orderValue(I.getResolver(), OM);125 for (const Function &F : M) {126 for (const Use &U : F.operands())127 if (!isa<GlobalValue>(U.get()))128 orderValue(U.get(), OM);129 }130 131 // As constants used in metadata operands are emitted as module-level132 // constants, we must order them before other operands. Also, we must order133 // these before global values, as these will be read before setting the134 // global values' initializers. The latter matters for constants which have135 // uses towards other constants that are used as initializers.136 auto orderConstantValue = [&OM](const Value *V) {137 if ((isa<Constant>(V) && !isa<GlobalValue>(V)) || isa<InlineAsm>(V))138 orderValue(V, OM);139 };140 for (const Function &F : M) {141 if (F.isDeclaration())142 continue;143 for (const BasicBlock &BB : F)144 for (const Instruction &I : BB)145 for (const Value *V : I.operands()) {146 if (const auto *MAV = dyn_cast<MetadataAsValue>(V)) {147 if (const auto *VAM =148 dyn_cast<ValueAsMetadata>(MAV->getMetadata())) {149 orderConstantValue(VAM->getValue());150 } else if (const auto *AL =151 dyn_cast<DIArgList>(MAV->getMetadata())) {152 for (const auto *VAM : AL->getArgs())153 orderConstantValue(VAM->getValue());154 }155 }156 }157 }158 OM.LastGlobalConstantID = OM.size();159 160 // Initializers of GlobalValues are processed in161 // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather162 // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()163 // by giving IDs in reverse order.164 //165 // Since GlobalValues never reference each other directly (just through166 // initializers), their relative IDs only matter for determining order of167 // uses in their initializers.168 for (const Function &F : M)169 orderValue(&F, OM);170 for (const GlobalAlias &A : M.aliases())171 orderValue(&A, OM);172 for (const GlobalIFunc &I : M.ifuncs())173 orderValue(&I, OM);174 for (const GlobalVariable &G : M.globals())175 orderValue(&G, OM);176 OM.LastGlobalValueID = OM.size();177 178 for (const Function &F : M) {179 if (F.isDeclaration())180 continue;181 // Here we need to match the union of ValueEnumerator::incorporateFunction()182 // and WriteFunction(). Basic blocks are implicitly declared before183 // anything else (by declaring their size).184 for (const BasicBlock &BB : F)185 orderValue(&BB, OM);186 for (const Argument &A : F.args())187 orderValue(&A, OM);188 for (const BasicBlock &BB : F)189 for (const Instruction &I : BB) {190 for (const Value *Op : I.operands())191 if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||192 isa<InlineAsm>(*Op))193 orderValue(Op, OM);194 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))195 orderValue(SVI->getShuffleMaskForBitcode(), OM);196 }197 for (const BasicBlock &BB : F)198 for (const Instruction &I : BB)199 orderValue(&I, OM);200 }201 return OM;202}203 204static void predictValueUseListOrderImpl(const Value *V, const Function *F,205 unsigned ID, const OrderMap &OM,206 UseListOrderStack &Stack) {207 // Predict use-list order for this one.208 using Entry = std::pair<const Use *, unsigned>;209 SmallVector<Entry, 64> List;210 for (const Use &U : V->uses())211 // Check if this user will be serialized.212 if (OM.lookup(U.getUser()).first)213 List.push_back(std::make_pair(&U, List.size()));214 215 if (List.size() < 2)216 // We may have lost some users.217 return;218 219 bool IsGlobalValue = OM.isGlobalValue(ID);220 llvm::sort(List, [&](const Entry &L, const Entry &R) {221 const Use *LU = L.first;222 const Use *RU = R.first;223 if (LU == RU)224 return false;225 226 auto LID = OM.lookup(LU->getUser()).first;227 auto RID = OM.lookup(RU->getUser()).first;228 229 // Global values are processed in reverse order.230 //231 // Moreover, initializers of GlobalValues are set *after* all the globals232 // have been read (despite having earlier IDs). Rather than awkwardly233 // modeling this behaviour here, orderModule() has assigned IDs to234 // initializers of GlobalValues before GlobalValues themselves.235 if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) {236 if (LID == RID)237 return LU->getOperandNo() > RU->getOperandNo();238 return LID < RID;239 }240 241 // If ID is 4, then expect: 7 6 5 1 2 3.242 if (LID < RID) {243 if (RID <= ID)244 if (!IsGlobalValue) // GlobalValue uses don't get reversed.245 return true;246 return false;247 }248 if (RID < LID) {249 if (LID <= ID)250 if (!IsGlobalValue) // GlobalValue uses don't get reversed.251 return false;252 return true;253 }254 255 // LID and RID are equal, so we have different operands of the same user.256 // Assume operands are added in order for all instructions.257 if (LID <= ID)258 if (!IsGlobalValue) // GlobalValue uses don't get reversed.259 return LU->getOperandNo() < RU->getOperandNo();260 return LU->getOperandNo() > RU->getOperandNo();261 });262 263 if (llvm::is_sorted(List, llvm::less_second()))264 // Order is already correct.265 return;266 267 // Store the shuffle.268 Stack.emplace_back(V, F, List.size());269 assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");270 for (size_t I = 0, E = List.size(); I != E; ++I)271 Stack.back().Shuffle[I] = List[I].second;272}273 274static void predictValueUseListOrder(const Value *V, const Function *F,275 OrderMap &OM, UseListOrderStack &Stack) {276 auto &IDPair = OM[V];277 assert(IDPair.first && "Unmapped value");278 if (IDPair.second)279 // Already predicted.280 return;281 282 // Do the actual prediction.283 IDPair.second = true;284 if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())285 predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);286 287 // Recursive descent into constants.288 if (const Constant *C = dyn_cast<Constant>(V)) {289 if (C->getNumOperands()) { // Visit GlobalValues.290 for (const Value *Op : C->operands())291 if (isa<Constant>(Op)) // Visit GlobalValues.292 predictValueUseListOrder(Op, F, OM, Stack);293 if (auto *CE = dyn_cast<ConstantExpr>(C))294 if (CE->getOpcode() == Instruction::ShuffleVector)295 predictValueUseListOrder(CE->getShuffleMaskForBitcode(), F, OM,296 Stack);297 }298 }299}300 301static UseListOrderStack predictUseListOrder(const Module &M) {302 OrderMap OM = orderModule(M);303 304 // Use-list orders need to be serialized after all the users have been added305 // to a value, or else the shuffles will be incomplete. Store them per306 // function in a stack.307 //308 // Aside from function order, the order of values doesn't matter much here.309 UseListOrderStack Stack;310 311 // We want to visit the functions backward now so we can list function-local312 // constants in the last Function they're used in. Module-level constants313 // have already been visited above.314 for (const Function &F : llvm::reverse(M)) {315 if (F.isDeclaration())316 continue;317 for (const BasicBlock &BB : F)318 predictValueUseListOrder(&BB, &F, OM, Stack);319 for (const Argument &A : F.args())320 predictValueUseListOrder(&A, &F, OM, Stack);321 for (const BasicBlock &BB : F)322 for (const Instruction &I : BB) {323 for (const Value *Op : I.operands())324 if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.325 predictValueUseListOrder(Op, &F, OM, Stack);326 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))327 predictValueUseListOrder(SVI->getShuffleMaskForBitcode(), &F, OM,328 Stack);329 }330 for (const BasicBlock &BB : F)331 for (const Instruction &I : BB)332 predictValueUseListOrder(&I, &F, OM, Stack);333 }334 335 // Visit globals last, since the module-level use-list block will be seen336 // before the function bodies are processed.337 for (const GlobalVariable &G : M.globals())338 predictValueUseListOrder(&G, nullptr, OM, Stack);339 for (const Function &F : M)340 predictValueUseListOrder(&F, nullptr, OM, Stack);341 for (const GlobalAlias &A : M.aliases())342 predictValueUseListOrder(&A, nullptr, OM, Stack);343 for (const GlobalIFunc &I : M.ifuncs())344 predictValueUseListOrder(&I, nullptr, OM, Stack);345 for (const GlobalVariable &G : M.globals())346 if (G.hasInitializer())347 predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);348 for (const GlobalAlias &A : M.aliases())349 predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);350 for (const GlobalIFunc &I : M.ifuncs())351 predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);352 for (const Function &F : M) {353 for (const Use &U : F.operands())354 predictValueUseListOrder(U.get(), nullptr, OM, Stack);355 }356 357 return Stack;358}359 360ValueEnumerator::ValueEnumerator(const Module &M, Type *PrefixType) {361 EnumerateType(PrefixType);362 363 UseListOrders = predictUseListOrder(M);364 365 // Enumerate the global variables.366 for (const GlobalVariable &GV : M.globals()) {367 EnumerateValue(&GV);368 EnumerateType(GV.getValueType());369 }370 371 // Enumerate the functions.372 for (const Function &F : M) {373 EnumerateValue(&F);374 EnumerateType(F.getValueType());375 EnumerateType(376 TypedPointerType::get(F.getFunctionType(), F.getAddressSpace()));377 EnumerateAttributes(F.getAttributes());378 }379 380 // Enumerate the aliases.381 for (const GlobalAlias &GA : M.aliases()) {382 EnumerateValue(&GA);383 EnumerateType(GA.getValueType());384 }385 386 // Enumerate the ifuncs.387 for (const GlobalIFunc &GIF : M.ifuncs()) {388 EnumerateValue(&GIF);389 EnumerateType(GIF.getValueType());390 }391 392 // Enumerate the global variable initializers and attributes.393 for (const GlobalVariable &GV : M.globals()) {394 if (GV.hasInitializer())395 EnumerateValue(GV.getInitializer());396 EnumerateType(397 TypedPointerType::get(GV.getValueType(), GV.getAddressSpace()));398 if (GV.hasAttributes())399 EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex));400 }401 402 // Enumerate the aliasees.403 for (const GlobalAlias &GA : M.aliases())404 EnumerateValue(GA.getAliasee());405 406 // Enumerate the ifunc resolvers.407 for (const GlobalIFunc &GIF : M.ifuncs())408 EnumerateValue(GIF.getResolver());409 410 // Enumerate any optional Function data.411 for (const Function &F : M)412 for (const Use &U : F.operands())413 EnumerateValue(U.get());414 415 // Enumerate the metadata type.416 //417 // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode418 // only encodes the metadata type when it's used as a value.419 EnumerateType(Type::getMetadataTy(M.getContext()));420 421 // Insert constants and metadata that are named at module level into the slot422 // pool so that the module symbol table can refer to them...423 EnumerateValueSymbolTable(M.getValueSymbolTable());424 EnumerateNamedMetadata(M);425 426 SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;427 for (const GlobalVariable &GV : M.globals()) {428 MDs.clear();429 GV.getAllMetadata(MDs);430 for (const auto &I : MDs)431 // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer432 // to write metadata to the global variable's own metadata block433 // (PR28134).434 EnumerateMetadata(nullptr, I.second);435 }436 437 // Enumerate types used by function bodies and argument lists.438 for (const Function &F : M) {439 for (const Argument &A : F.args())440 EnumerateType(A.getType());441 442 // Enumerate metadata attached to this function.443 MDs.clear();444 F.getAllMetadata(MDs);445 for (const auto &I : MDs)446 EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);447 448 for (const BasicBlock &BB : F)449 for (const Instruction &I : BB) {450 for (const Use &Op : I.operands()) {451 auto *MD = dyn_cast<MetadataAsValue>(&Op);452 if (!MD) {453 EnumerateOperandType(Op);454 continue;455 }456 457 // Local metadata is enumerated during function-incorporation, but458 // any ConstantAsMetadata arguments in a DIArgList should be examined459 // now.460 if (isa<LocalAsMetadata>(MD->getMetadata()))461 continue;462 if (auto *AL = dyn_cast<DIArgList>(MD->getMetadata())) {463 for (auto *VAM : AL->getArgs())464 if (isa<ConstantAsMetadata>(VAM))465 EnumerateMetadata(&F, VAM);466 continue;467 }468 469 EnumerateMetadata(&F, MD->getMetadata());470 }471 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))472 EnumerateType(SVI->getShuffleMaskForBitcode()->getType());473 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I))474 EnumerateType(GEP->getSourceElementType());475 if (auto *AI = dyn_cast<AllocaInst>(&I))476 EnumerateType(AI->getAllocatedType());477 EnumerateType(I.getType());478 if (const auto *Call = dyn_cast<CallBase>(&I)) {479 EnumerateAttributes(Call->getAttributes());480 EnumerateType(Call->getFunctionType());481 }482 483 // Enumerate metadata attached with this instruction.484 MDs.clear();485 I.getAllMetadataOtherThanDebugLoc(MDs);486 for (unsigned i = 0, e = MDs.size(); i != e; ++i)487 EnumerateMetadata(&F, MDs[i].second);488 489 // Don't enumerate the location directly -- it has a special record490 // type -- but enumerate its operands.491 if (DILocation *L = I.getDebugLoc())492 for (const Metadata *Op : L->operands())493 EnumerateMetadata(&F, Op);494 }495 }496 497 // Organize metadata ordering.498 organizeMetadata();499}500 501unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {502 InstructionMapType::const_iterator I = InstructionMap.find(Inst);503 assert(I != InstructionMap.end() && "Instruction is not mapped!");504 return I->second;505}506 507unsigned ValueEnumerator::getComdatID(const Comdat *C) const {508 unsigned ComdatID = Comdats.idFor(C);509 assert(ComdatID && "Comdat not found!");510 return ComdatID;511}512 513void ValueEnumerator::setInstructionID(const Instruction *I) {514 InstructionMap[I] = InstructionCount++;515}516 517unsigned ValueEnumerator::getValueID(const Value *V) const {518 if (auto *MD = dyn_cast<MetadataAsValue>(V))519 return getMetadataID(MD->getMetadata());520 521 ValueMapType::const_iterator I = ValueMap.find(V);522 assert(I != ValueMap.end() && "Value not in slotcalculator!");523 return I->second - 1;524}525 526#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)527LLVM_DUMP_METHOD void ValueEnumerator::dump() const {528 print(dbgs(), ValueMap, "Default");529 dbgs() << '\n';530 print(dbgs(), MetadataMap, "MetaData");531 dbgs() << '\n';532}533#endif534 535void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,536 const char *Name) const {537 OS << "Map Name: " << Name << "\n";538 OS << "Size: " << Map.size() << "\n";539 for (const auto &I : Map) {540 const Value *V = I.first;541 if (V->hasName())542 OS << "Value: " << V->getName();543 else544 OS << "Value: [null]\n";545 V->print(errs());546 errs() << '\n';547 548 OS << " Uses(" << V->getNumUses() << "):";549 for (const Use &U : V->uses()) {550 if (&U != &*V->use_begin())551 OS << ",";552 if (U->hasName())553 OS << " " << U->getName();554 else555 OS << " [null]";556 }557 OS << "\n\n";558 }559}560 561void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,562 const char *Name) const {563 OS << "Map Name: " << Name << "\n";564 OS << "Size: " << Map.size() << "\n";565 for (const auto &I : Map) {566 const Metadata *MD = I.first;567 OS << "Metadata: slot = " << I.second.ID << "\n";568 OS << "Metadata: function = " << I.second.F << "\n";569 MD->print(OS);570 OS << "\n";571 }572}573 574/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol575/// table into the values table.576void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {577 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();578 VI != VE; ++VI)579 EnumerateValue(VI->getValue());580}581 582/// Insert all of the values referenced by named metadata in the specified583/// module.584void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {585 for (const auto &I : M.named_metadata())586 EnumerateNamedMDNode(&I);587}588 589void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {590 for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)591 EnumerateMetadata(nullptr, MD->getOperand(i));592}593 594unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {595 return F ? getValueID(F) + 1 : 0;596}597 598void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {599 EnumerateMetadata(getMetadataFunctionID(F), MD);600}601 602void ValueEnumerator::EnumerateFunctionLocalMetadata(603 const Function &F, const LocalAsMetadata *Local) {604 EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);605}606 607void ValueEnumerator::EnumerateFunctionLocalListMetadata(608 const Function &F, const DIArgList *ArgList) {609 EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&F), ArgList);610}611 612void ValueEnumerator::dropFunctionFromMetadata(613 MetadataMapType::value_type &FirstMD) {614 SmallVector<const MDNode *, 64> Worklist;615 auto push = [&Worklist](MetadataMapType::value_type &MD) {616 auto &Entry = MD.second;617 618 // Nothing to do if this metadata isn't tagged.619 if (!Entry.F)620 return;621 622 // Drop the function tag.623 Entry.F = 0;624 625 // If this is has an ID and is an MDNode, then its operands have entries as626 // well. We need to drop the function from them too.627 if (Entry.ID)628 if (auto *N = dyn_cast<MDNode>(MD.first))629 Worklist.push_back(N);630 };631 push(FirstMD);632 while (!Worklist.empty())633 for (const Metadata *Op : Worklist.pop_back_val()->operands()) {634 if (!Op)635 continue;636 auto MD = MetadataMap.find(Op);637 if (MD != MetadataMap.end())638 push(*MD);639 }640}641 642void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {643 // It's vital for reader efficiency that uniqued subgraphs are done in644 // post-order; it's expensive when their operands have forward references.645 // If a distinct node is referenced from a uniqued node, it'll be delayed646 // until the uniqued subgraph has been completely traversed.647 SmallVector<const MDNode *, 32> DelayedDistinctNodes;648 649 // Start by enumerating MD, and then work through its transitive operands in650 // post-order. This requires a depth-first search.651 SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist;652 if (const MDNode *N = enumerateMetadataImpl(F, MD))653 Worklist.push_back(std::make_pair(N, N->op_begin()));654 655 while (!Worklist.empty()) {656 const MDNode *N = Worklist.back().first;657 658 // Enumerate operands until we hit a new node. We need to traverse these659 // nodes' operands before visiting the rest of N's operands.660 MDNode::op_iterator I = std::find_if(661 Worklist.back().second, N->op_end(),662 [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });663 if (I != N->op_end()) {664 auto *Op = cast<MDNode>(*I);665 Worklist.back().second = ++I;666 667 // Delay traversing Op if it's a distinct node and N is uniqued.668 if (Op->isDistinct() && !N->isDistinct())669 DelayedDistinctNodes.push_back(Op);670 else671 Worklist.push_back(std::make_pair(Op, Op->op_begin()));672 continue;673 }674 675 // All the operands have been visited. Now assign an ID.676 Worklist.pop_back();677 MDs.push_back(N);678 MetadataMap[N].ID = MDs.size();679 680 // Flush out any delayed distinct nodes; these are all the distinct nodes681 // that are leaves in last uniqued subgraph.682 if (Worklist.empty() || Worklist.back().first->isDistinct()) {683 for (const MDNode *N : DelayedDistinctNodes)684 Worklist.push_back(std::make_pair(N, N->op_begin()));685 DelayedDistinctNodes.clear();686 }687 }688}689 690const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F,691 const Metadata *MD) {692 if (!MD)693 return nullptr;694 695 assert(696 (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&697 "Invalid metadata kind");698 699 auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));700 MDIndex &Entry = Insertion.first->second;701 if (!Insertion.second) {702 // Already mapped. If F doesn't match the function tag, drop it.703 if (Entry.hasDifferentFunction(F))704 dropFunctionFromMetadata(*Insertion.first);705 return nullptr;706 }707 708 // Don't assign IDs to metadata nodes.709 if (auto *N = dyn_cast<MDNode>(MD))710 return N;711 712 // Save the metadata.713 MDs.push_back(MD);714 Entry.ID = MDs.size();715 716 // Enumerate the constant, if any.717 if (auto *C = dyn_cast<ConstantAsMetadata>(MD))718 EnumerateValue(C->getValue());719 720 return nullptr;721}722 723/// EnumerateFunctionLocalMetadata - Incorporate function-local metadata724/// information reachable from the metadata.725void ValueEnumerator::EnumerateFunctionLocalMetadata(726 unsigned F, const LocalAsMetadata *Local) {727 assert(F && "Expected a function");728 729 // Check to see if it's already in!730 MDIndex &Index = MetadataMap[Local];731 if (Index.ID) {732 assert(Index.F == F && "Expected the same function");733 return;734 }735 736 MDs.push_back(Local);737 Index.F = F;738 Index.ID = MDs.size();739 740 EnumerateValue(Local->getValue());741}742 743/// EnumerateFunctionLocalListMetadata - Incorporate function-local metadata744/// information reachable from the metadata.745void ValueEnumerator::EnumerateFunctionLocalListMetadata(746 unsigned F, const DIArgList *ArgList) {747 assert(F && "Expected a function");748 749 // Check to see if it's already in!750 MDIndex &Index = MetadataMap[ArgList];751 if (Index.ID) {752 assert(Index.F == F && "Expected the same function");753 return;754 }755 756 for (ValueAsMetadata *VAM : ArgList->getArgs()) {757 if (isa<LocalAsMetadata>(VAM)) {758 assert(MetadataMap.count(VAM) &&759 "LocalAsMetadata should be enumerated before DIArgList");760 assert(MetadataMap[VAM].F == F &&761 "Expected LocalAsMetadata in the same function");762 } else {763 assert(isa<ConstantAsMetadata>(VAM) &&764 "Expected LocalAsMetadata or ConstantAsMetadata");765 assert(ValueMap.count(VAM->getValue()) &&766 "Constant should be enumerated beforeDIArgList");767 EnumerateMetadata(F, VAM);768 }769 }770 771 MDs.push_back(ArgList);772 Index.F = F;773 Index.ID = MDs.size();774}775 776static unsigned getMetadataTypeOrder(const Metadata *MD) {777 // Strings are emitted in bulk and must come first.778 if (isa<MDString>(MD))779 return 0;780 781 // ConstantAsMetadata doesn't reference anything. We may as well shuffle it782 // to the front since we can detect it.783 auto *N = dyn_cast<MDNode>(MD);784 if (!N)785 return 1;786 787 // The reader is fast forward references for distinct node operands, but slow788 // when uniqued operands are unresolved.789 return N->isDistinct() ? 2 : 3;790}791 792void ValueEnumerator::organizeMetadata() {793 assert(MetadataMap.size() == MDs.size() &&794 "Metadata map and vector out of sync");795 796 if (MDs.empty())797 return;798 799 // Copy out the index information from MetadataMap in order to choose a new800 // order.801 SmallVector<MDIndex, 64> Order;802 Order.reserve(MetadataMap.size());803 for (const Metadata *MD : MDs)804 Order.push_back(MetadataMap.lookup(MD));805 806 // Partition:807 // - by function, then808 // - by isa<MDString>809 // and then sort by the original/current ID. Since the IDs are guaranteed to810 // be unique, the result of llvm::sort will be deterministic. There's no need811 // for std::stable_sort.812 llvm::sort(Order, [this](MDIndex LHS, MDIndex RHS) {813 return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <814 std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);815 });816 817 // Rebuild MDs, index the metadata ranges for each function in FunctionMDs,818 // and fix up MetadataMap.819 std::vector<const Metadata *> OldMDs;820 MDs.swap(OldMDs);821 MDs.reserve(OldMDs.size());822 for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {823 auto *MD = Order[I].get(OldMDs);824 MDs.push_back(MD);825 MetadataMap[MD].ID = I + 1;826 if (isa<MDString>(MD))827 ++NumMDStrings;828 }829 830 // Return early if there's nothing for the functions.831 if (MDs.size() == Order.size())832 return;833 834 // Build the function metadata ranges.835 MDRange R;836 FunctionMDs.reserve(OldMDs.size());837 unsigned PrevF = 0;838 for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;839 ++I) {840 unsigned F = Order[I].F;841 if (!PrevF) {842 PrevF = F;843 } else if (PrevF != F) {844 R.Last = FunctionMDs.size();845 std::swap(R, FunctionMDInfo[PrevF]);846 R.First = FunctionMDs.size();847 848 ID = MDs.size();849 PrevF = F;850 }851 852 auto *MD = Order[I].get(OldMDs);853 FunctionMDs.push_back(MD);854 MetadataMap[MD].ID = ++ID;855 if (isa<MDString>(MD))856 ++R.NumStrings;857 }858 R.Last = FunctionMDs.size();859 FunctionMDInfo[PrevF] = R;860}861 862void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {863 NumModuleMDs = MDs.size();864 865 auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);866 NumMDStrings = R.NumStrings;867 MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,868 FunctionMDs.begin() + R.Last);869}870 871void ValueEnumerator::EnumerateValue(const Value *V) {872 assert(!V->getType()->isVoidTy() && "Can't insert void values!");873 assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");874 875 // Check to see if it's already in!876 unsigned &ValueID = ValueMap[V];877 if (ValueID) {878 // Increment use count.879 Values[ValueID - 1].second++;880 return;881 }882 883 if (auto *GO = dyn_cast<GlobalObject>(V))884 if (const Comdat *C = GO->getComdat())885 Comdats.insert(C);886 887 // Enumerate the type of this value.888 EnumerateType(V->getType());889 890 if (const Constant *C = dyn_cast<Constant>(V)) {891 if (isa<GlobalValue>(C)) {892 // Initializers for globals are handled explicitly elsewhere.893 } else if (C->getNumOperands()) {894 // If a constant has operands, enumerate them. This makes sure that if a895 // constant has uses (for example an array of const ints), that they are896 // inserted also.897 898 // We prefer to enumerate them with values before we enumerate the user899 // itself. This makes it more likely that we can avoid forward references900 // in the reader. We know that there can be no cycles in the constants901 // graph that don't go through a global variable.902 for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); I != E;903 ++I)904 if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.905 EnumerateValue(*I);906 if (auto *CE = dyn_cast<ConstantExpr>(C)) {907 if (CE->getOpcode() == Instruction::ShuffleVector)908 EnumerateValue(CE->getShuffleMaskForBitcode());909 if (auto *GEP = dyn_cast<GEPOperator>(CE))910 EnumerateType(GEP->getSourceElementType());911 }912 913 // Finally, add the value. Doing this could make the ValueID reference be914 // dangling, don't reuse it.915 Values.push_back(std::make_pair(V, 1U));916 ValueMap[V] = Values.size();917 return;918 }919 }920 921 // Add the value.922 Values.push_back(std::make_pair(V, 1U));923 ValueID = Values.size();924}925 926void ValueEnumerator::EnumerateType(Type *Ty) {927 unsigned *TypeID = &TypeMap[Ty];928 929 // We've already seen this type.930 if (*TypeID)931 return;932 933 // If it is a non-anonymous struct, mark the type as being visited so that we934 // don't recursively visit it. This is safe because we allow forward935 // references of these in the bitcode reader.936 if (StructType *STy = dyn_cast<StructType>(Ty))937 if (!STy->isLiteral())938 *TypeID = ~0U;939 940 // Enumerate all of the subtypes before we enumerate this type. This ensures941 // that the type will be enumerated in an order that can be directly built.942 for (Type *SubTy : Ty->subtypes())943 EnumerateType(SubTy);944 945 // Refresh the TypeID pointer in case the table rehashed.946 TypeID = &TypeMap[Ty];947 948 // Check to see if we got the pointer another way. This can happen when949 // enumerating recursive types that hit the base case deeper than they start.950 //951 // If this is actually a struct that we are treating as forward ref'able,952 // then emit the definition now that all of its contents are available.953 if (*TypeID && *TypeID != ~0U)954 return;955 956 // Add this type now that its contents are all happily enumerated.957 Types.push_back(Ty);958 959 *TypeID = Types.size();960}961 962// Enumerate the types for the specified value. If the value is a constant,963// walk through it, enumerating the types of the constant.964void ValueEnumerator::EnumerateOperandType(const Value *V) {965 EnumerateType(V->getType());966 967 assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");968 969 const Constant *C = dyn_cast<Constant>(V);970 if (!C)971 return;972 973 // If this constant is already enumerated, ignore it, we know its type must974 // be enumerated.975 if (ValueMap.count(C))976 return;977 978 // This constant may have operands, make sure to enumerate the types in979 // them.980 for (const Value *Op : C->operands()) {981 // Don't enumerate basic blocks here, this happens as operands to982 // blockaddress.983 if (isa<BasicBlock>(Op))984 continue;985 986 EnumerateOperandType(Op);987 }988 if (auto *CE = dyn_cast<ConstantExpr>(C)) {989 if (CE->getOpcode() == Instruction::ShuffleVector)990 EnumerateOperandType(CE->getShuffleMaskForBitcode());991 if (CE->getOpcode() == Instruction::GetElementPtr)992 EnumerateType(cast<GEPOperator>(CE)->getSourceElementType());993 }994}995 996void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {997 if (PAL.isEmpty())998 return; // null is always 0.999 1000 // Do a lookup.1001 unsigned &Entry = AttributeListMap[PAL];1002 if (Entry == 0) {1003 // Never saw this before, add it.1004 AttributeLists.push_back(PAL);1005 Entry = AttributeLists.size();1006 }1007 1008 // Do lookups for all attribute groups.1009 for (unsigned i : PAL.indexes()) {1010 AttributeSet AS = PAL.getAttributes(i);1011 if (!AS.hasAttributes())1012 continue;1013 IndexAndAttrSet Pair = {i, AS};1014 unsigned &Entry = AttributeGroupMap[Pair];1015 if (Entry == 0) {1016 AttributeGroups.push_back(Pair);1017 Entry = AttributeGroups.size();1018 1019 for (Attribute Attr : AS) {1020 if (Attr.isTypeAttribute())1021 EnumerateType(Attr.getValueAsType());1022 }1023 }1024 }1025}1026 1027void ValueEnumerator::incorporateFunction(const Function &F) {1028 InstructionCount = 0;1029 NumModuleValues = Values.size();1030 1031 // Add global metadata to the function block. This doesn't include1032 // LocalAsMetadata.1033 incorporateFunctionMetadata(F);1034 1035 // Adding function arguments to the value table.1036 for (const auto &I : F.args()) {1037 EnumerateValue(&I);1038 if (I.hasAttribute(Attribute::ByVal))1039 EnumerateType(I.getParamByValType());1040 else if (I.hasAttribute(Attribute::StructRet))1041 EnumerateType(I.getParamStructRetType());1042 else if (I.hasAttribute(Attribute::ByRef))1043 EnumerateType(I.getParamByRefType());1044 }1045 FirstFuncConstantID = Values.size();1046 1047 // Add all function-level constants to the value table.1048 for (const BasicBlock &BB : F) {1049 for (const Instruction &I : BB) {1050 for (const Use &OI : I.operands()) {1051 if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))1052 EnumerateValue(OI);1053 }1054 if (auto *SVI = dyn_cast<ShuffleVectorInst>(&I))1055 EnumerateValue(SVI->getShuffleMaskForBitcode());1056 }1057 BasicBlocks.push_back(&BB);1058 ValueMap[&BB] = BasicBlocks.size();1059 }1060 1061 // Add the function's parameter attributes so they are available for use in1062 // the function's instruction.1063 EnumerateAttributes(F.getAttributes());1064 1065 FirstInstID = Values.size();1066 1067 SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;1068 SmallVector<DIArgList *, 8> ArgListMDVector;1069 // Add all of the instructions.1070 for (const BasicBlock &BB : F) {1071 for (const Instruction &I : BB) {1072 for (const Use &OI : I.operands()) {1073 if (auto *MD = dyn_cast<MetadataAsValue>(&OI)) {1074 if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) {1075 // Enumerate metadata after the instructions they might refer to.1076 FnLocalMDVector.push_back(Local);1077 } else if (auto *ArgList = dyn_cast<DIArgList>(MD->getMetadata())) {1078 ArgListMDVector.push_back(ArgList);1079 for (ValueAsMetadata *VMD : ArgList->getArgs()) {1080 if (auto *Local = dyn_cast<LocalAsMetadata>(VMD)) {1081 // Enumerate metadata after the instructions they might refer1082 // to.1083 FnLocalMDVector.push_back(Local);1084 }1085 }1086 }1087 }1088 }1089 1090 if (!I.getType()->isVoidTy())1091 EnumerateValue(&I);1092 }1093 }1094 1095 // Add all of the function-local metadata.1096 for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {1097 // At this point, every local values have been incorporated, we shouldn't1098 // have a metadata operand that references a value that hasn't been seen.1099 assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&1100 "Missing value for metadata operand");1101 EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);1102 }1103 // DIArgList entries must come after function-local metadata, as it is not1104 // possible to forward-reference them.1105 for (const DIArgList *ArgList : ArgListMDVector)1106 EnumerateFunctionLocalListMetadata(F, ArgList);1107}1108 1109void ValueEnumerator::purgeFunction() {1110 /// Remove purged values from the ValueMap.1111 for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)1112 ValueMap.erase(Values[i].first);1113 for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)1114 MetadataMap.erase(MDs[i]);1115 for (const BasicBlock *BB : BasicBlocks)1116 ValueMap.erase(BB);1117 1118 Values.resize(NumModuleValues);1119 MDs.resize(NumModuleMDs);1120 BasicBlocks.clear();1121 NumMDStrings = 0;1122}1123 1124static void IncorporateFunctionInfoGlobalBBIDs(1125 const Function *F, DenseMap<const BasicBlock *, unsigned> &IDMap) {1126 unsigned Counter = 0;1127 for (const BasicBlock &BB : *F)1128 IDMap[&BB] = ++Counter;1129}1130 1131/// getGlobalBasicBlockID - This returns the function-specific ID for the1132/// specified basic block. This is relatively expensive information, so it1133/// should only be used by rare constructs such as address-of-label.1134unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {1135 unsigned &Idx = GlobalBasicBlockIDs[BB];1136 if (Idx != 0)1137 return Idx - 1;1138 1139 IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);1140 return getGlobalBasicBlockID(BB);1141}1142 1143uint64_t ValueEnumerator::computeBitsRequiredForTypeIndices() const {1144 return Log2_32_Ceil(getTypes().size() + 1);1145}1146