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