llvm/lib/Target/DirectX/DXILWriter/DXILValueEnumerator.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the ValueEnumerator class.
  10 // Forked from lib/Bitcode/Writer
  11 //
  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
  49 using namespace llvm;
  50 using namespace llvm::dxil;
  51
  52 namespace {
  53
  54 struct 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 namespace
  84
  85 static 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 map
 101   // changes the map's size, and thus affects the other IDs.
 102   OM.index(V);
 103 }
 104
 105 static 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 the
 111   // globals have been read.  Rather than awkwardly modeling this behaviour
 112   // directly in predictValueUseListOrderImpl(), just assign IDs to
 113   // initializers of GlobalValues before GlobalValues themselves to model this
 114   // 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-level
 132   // constants, we must order them before other operands. Also, we must order
 133   // these before global values, as these will be read before setting the
 134   // global values' initializers. The latter matters for constants which have
 135   // 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 in
 161   // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
 162   // 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 through
 166   // initializers), their relative IDs only matter for determining order of
 167   // 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 before
 183     // 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
 204 static 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 globals
 232     // have been read (despite having earlier IDs).  Rather than awkwardly
 233     // modeling this behaviour here, orderModule() has assigned IDs to
 234     // 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
 274 static 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
 301 static 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 added
 305   // to a value, or else the shuffles will be incomplete.  Store them per
 306   // 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-local
 312   // constants in the last Function they're used in.  Module-level constants
 313   // 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 seen
 336   // 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
 360 ValueEnumerator::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 bitcode
 418   // 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 slot
 422   // 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 writer
 432       // to write metadata to the global variable's own metadata block
 433       // (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, but
 458           // any ConstantAsMetadata arguments in a DIArgList should be examined
 459           // 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 record
 490         // 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
 501 unsigned 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
 507 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
 508   unsigned ComdatID = Comdats.idFor(C);
 509   assert(ComdatID && "Comdat not found!");
 510   return ComdatID;
 511 }
 512
 513 void ValueEnumerator::setInstructionID(const Instruction *I) {
 514   InstructionMap[I] = InstructionCount++;
 515 }
 516
 517 unsigned 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)
 527 LLVM_DUMP_METHOD void ValueEnumerator::dump() const {
 528   print(dbgs(), ValueMap, "Default");
 529   dbgs() << '\n';
 530   print(dbgs(), MetadataMap, "MetaData");
 531   dbgs() << '\n';
 532 }
 533 #endif
 534
 535 void 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     else
 544       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       else
 555         OS << " [null]";
 556     }
 557     OS << "\n\n";
 558   }
 559 }
 560
 561 void 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 symbol
 575 /// table into the values table.
 576 void 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 specified
 583 /// module.
 584 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
 585   for (const auto &I : M.named_metadata())
 586     EnumerateNamedMDNode(&I);
 587 }
 588
 589 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
 590   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
 591     EnumerateMetadata(nullptr, MD->getOperand(i));
 592 }
 593
 594 unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
 595   return F ? getValueID(F) + 1 : 0;
 596 }
 597
 598 void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
 599   EnumerateMetadata(getMetadataFunctionID(F), MD);
 600 }
 601
 602 void ValueEnumerator::EnumerateFunctionLocalMetadata(
 603     const Function &F, const LocalAsMetadata *Local) {
 604   EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
 605 }
 606
 607 void ValueEnumerator::EnumerateFunctionLocalListMetadata(
 608     const Function &F, const DIArgList *ArgList) {
 609   EnumerateFunctionLocalListMetadata(getMetadataFunctionID(&F), ArgList);
 610 }
 611
 612 void 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 as
 626     // 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
 642 void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
 643   // It's vital for reader efficiency that uniqued subgraphs are done in
 644   // 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 delayed
 646   // 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 in
 650   // 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 these
 659     // 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       else
 671         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 nodes
 681     // 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
 690 const 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 metadata
 724 /// information reachable from the metadata.
 725 void 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 metadata
 744 /// information reachable from the metadata.
 745 void 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
 776 static 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 it
 782   // 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 slow
 788   // when uniqued operands are unresolved.
 789   return N->isDistinct() ? 2 : 3;
 790 }
 791
 792 void 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 new
 800   // 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, then
 808   //   - by isa<MDString>
 809   // and then sort by the original/current ID.  Since the IDs are guaranteed to
 810   // be unique, the result of llvm::sort will be deterministic.  There's no need
 811   // 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
 862 void 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
 871 void 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 a
 895       // constant has uses (for example an array of const ints), that they are
 896       // inserted also.
 897
 898       // We prefer to enumerate them with values before we enumerate the user
 899       // itself.  This makes it more likely that we can avoid forward references
 900       // in the reader.  We know that there can be no cycles in the constants
 901       // 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 be
 914       // 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
 926 void 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 we
 934   // don't recursively visit it.  This is safe because we allow forward
 935   // 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 ensures
 941   // 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 when
 949   // 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.
 964 void 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 must
 974   // be enumerated.
 975   if (ValueMap.count(C))
 976     return;
 977
 978   // This constant may have operands, make sure to enumerate the types in
 979   // them.
 980   for (const Value *Op : C->operands()) {
 981     // Don't enumerate basic blocks here, this happens as operands to
 982     // 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
 996 void 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
1027 void ValueEnumerator::incorporateFunction(const Function &F) {
1028   InstructionCount = 0;
1029   NumModuleValues = Values.size();
1030
1031   // Add global metadata to the function block.  This doesn't include
1032   // 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 in
1062   // 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 refer
1082                 // 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't
1098     // 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 not
1104   // possible to forward-reference them.
1105   for (const DIArgList *ArgList : ArgListMDVector)
1106     EnumerateFunctionLocalListMetadata(F, ArgList);
1107 }
1108
1109 void 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
1124 static 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 the
1132 /// specified basic block.  This is relatively expensive information, so it
1133 /// should only be used by rare constructs such as address-of-label.
1134 unsigned 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
1143 uint64_t ValueEnumerator::computeBitsRequiredForTypeIndices() const {
1144   return Log2_32_Ceil(getTypes().size() + 1);
1145 }