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