LCOV - code coverage report
Current view: top level - lib/Bitcode/Writer - ValueEnumerator.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 476 507 93.9 %
Date: 2017-09-14 15:23:50 Functions: 37 39 94.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ValueEnumerator.cpp - Number values and types for bitcode writer ---===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the ValueEnumerator class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "ValueEnumerator.h"
      15             : #include "llvm/ADT/DenseMap.h"
      16             : #include "llvm/ADT/SmallVector.h"
      17             : #include "llvm/IR/Argument.h"
      18             : #include "llvm/IR/Attributes.h"
      19             : #include "llvm/IR/BasicBlock.h"
      20             : #include "llvm/IR/Constant.h"
      21             : #include "llvm/IR/DebugInfoMetadata.h"
      22             : #include "llvm/IR/DerivedTypes.h"
      23             : #include "llvm/IR/Function.h"
      24             : #include "llvm/IR/GlobalAlias.h"
      25             : #include "llvm/IR/GlobalIFunc.h"
      26             : #include "llvm/IR/GlobalObject.h"
      27             : #include "llvm/IR/GlobalValue.h"
      28             : #include "llvm/IR/GlobalVariable.h"
      29             : #include "llvm/IR/Instruction.h"
      30             : #include "llvm/IR/Instructions.h"
      31             : #include "llvm/IR/Metadata.h"
      32             : #include "llvm/IR/Module.h"
      33             : #include "llvm/IR/Type.h"
      34             : #include "llvm/IR/Use.h"
      35             : #include "llvm/IR/UseListOrder.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 <cassert>
      46             : #include <cstddef>
      47             : #include <iterator>
      48             : #include <tuple>
      49             : #include <utility>
      50             : #include <vector>
      51             : 
      52             : using namespace llvm;
      53             : 
      54             : namespace {
      55             : 
      56        5128 : struct OrderMap {
      57             :   DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
      58             :   unsigned LastGlobalConstantID = 0;
      59             :   unsigned LastGlobalValueID = 0;
      60             : 
      61        5128 :   OrderMap() = default;
      62             : 
      63             :   bool isGlobalConstant(unsigned ID) const {
      64             :     return ID <= LastGlobalConstantID;
      65             :   }
      66             : 
      67             :   bool isGlobalValue(unsigned ID) const {
      68      217467 :     return ID <= LastGlobalValueID && !isGlobalConstant(ID);
      69             :   }
      70             : 
      71       10256 :   unsigned size() const { return IDs.size(); }
      72      147498 :   std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
      73             : 
      74             :   std::pair<unsigned, bool> lookup(const Value *V) const {
      75      509030 :     return IDs.lookup(V);
      76             :   }
      77             : 
      78             :   void index(const Value *V) {
      79             :     // Explicitly sequence get-size and insert-value operations to avoid UB.
      80      114856 :     unsigned ID = IDs.size() + 1;
      81      114856 :     IDs[V].first = ID;
      82             :   }
      83             : };
      84             : 
      85             : } // end anonymous namespace
      86             : 
      87       64108 : static void orderValue(const Value *V, OrderMap &OM) {
      88       64108 :   if (OM.lookup(V).first)
      89             :     return;
      90             : 
      91       18676 :   if (const Constant *C = dyn_cast<Constant>(V))
      92       37352 :     if (C->getNumOperands() && !isa<GlobalValue>(C))
      93        5550 :       for (const Value *Op : C->operands())
      94        5808 :         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
      95        2029 :           orderValue(Op, OM);
      96             : 
      97             :   // Note: we cannot cache this lookup above, since inserting into the map
      98             :   // changes the map's size, and thus affects the other IDs.
      99             :   OM.index(V);
     100             : }
     101             : 
     102        2564 : static OrderMap orderModule(const Module &M) {
     103             :   // This needs to match the order used by ValueEnumerator::ValueEnumerator()
     104             :   // and ValueEnumerator::incorporateFunction().
     105        2564 :   OrderMap OM;
     106             : 
     107             :   // In the reader, initializers of GlobalValues are set *after* all the
     108             :   // globals have been read.  Rather than awkwardly modeling this behaviour
     109             :   // directly in predictValueUseListOrderImpl(), just assign IDs to
     110             :   // initializers of GlobalValues before GlobalValues themselves to model this
     111             :   // implicitly.
     112        4804 :   for (const GlobalVariable &G : M.globals())
     113        2240 :     if (G.hasInitializer())
     114        1828 :       if (!isa<GlobalValue>(G.getInitializer()))
     115        1625 :         orderValue(G.getInitializer(), OM);
     116        3110 :   for (const GlobalAlias &A : M.aliases())
     117         546 :     if (!isa<GlobalValue>(A.getAliasee()))
     118         269 :       orderValue(A.getAliasee(), OM);
     119        2592 :   for (const GlobalIFunc &I : M.ifuncs())
     120          28 :     if (!isa<GlobalValue>(I.getResolver()))
     121           0 :       orderValue(I.getResolver(), OM);
     122       13816 :   for (const Function &F : M) {
     123       12572 :     for (const Use &U : F.operands())
     124         324 :       if (!isa<GlobalValue>(U.get()))
     125         277 :         orderValue(U.get(), OM);
     126             :   }
     127        2564 :   OM.LastGlobalConstantID = OM.size();
     128             : 
     129             :   // Initializers of GlobalValues are processed in
     130             :   // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
     131             :   // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
     132             :   // by giving IDs in reverse order.
     133             :   //
     134             :   // Since GlobalValues never reference each other directly (just through
     135             :   // initializers), their relative IDs only matter for determining order of
     136             :   // uses in their initializers.
     137       13816 :   for (const Function &F : M)
     138        6124 :     orderValue(&F, OM);
     139        3110 :   for (const GlobalAlias &A : M.aliases())
     140         546 :     orderValue(&A, OM);
     141        2564 :   for (const GlobalIFunc &I : M.ifuncs())
     142          28 :     orderValue(&I, OM);
     143        4804 :   for (const GlobalVariable &G : M.globals())
     144        2240 :     orderValue(&G, OM);
     145        2564 :   OM.LastGlobalValueID = OM.size();
     146             : 
     147       13816 :   for (const Function &F : M) {
     148        6124 :     if (F.isDeclaration())
     149        1715 :       continue;
     150             :     // Here we need to match the union of ValueEnumerator::incorporateFunction()
     151             :     // and WriteFunction().  Basic blocks are implicitly declared before
     152             :     // anything else (by declaring their size).
     153       21363 :     for (const BasicBlock &BB : F)
     154        8136 :       orderValue(&BB, OM);
     155        7459 :     for (const Argument &A : F.args())
     156        3050 :       orderValue(&A, OM);
     157       21363 :     for (const BasicBlock &BB : F)
     158       51930 :       for (const Instruction &I : BB)
     159      100161 :         for (const Value *Op : I.operands())
     160       50646 :           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
     161       32910 :               isa<InlineAsm>(*Op))
     162       12262 :             orderValue(Op, OM);
     163       21363 :     for (const BasicBlock &BB : F)
     164       51930 :       for (const Instruction &I : BB)
     165       27522 :         orderValue(&I, OM);
     166             :   }
     167        2564 :   return OM;
     168             : }
     169             : 
     170        6792 : static void predictValueUseListOrderImpl(const Value *V, const Function *F,
     171             :                                          unsigned ID, const OrderMap &OM,
     172             :                                          UseListOrderStack &Stack) {
     173             :   // Predict use-list order for this one.
     174             :   using Entry = std::pair<const Use *, unsigned>;
     175        8328 :   SmallVector<Entry, 64> List;
     176       48638 :   for (const Use &U : V->uses())
     177             :     // Check if this user will be serialized.
     178       56524 :     if (OM.lookup(U.getUser()).first)
     179       83634 :       List.push_back(std::make_pair(&U, List.size()));
     180             : 
     181        6792 :   if (List.size() < 2)
     182             :     // We may have lost some users.
     183        5256 :     return;
     184             : 
     185       13032 :   bool IsGlobalValue = OM.isGlobalValue(ID);
     186      221362 :   std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
     187      208330 :     const Use *LU = L.first;
     188      208330 :     const Use *RU = R.first;
     189      208330 :     if (LU == RU)
     190             :       return false;
     191             : 
     192      627611 :     auto LID = OM.lookup(LU->getUser()).first;
     193      416660 :     auto RID = OM.lookup(RU->getUser()).first;
     194             : 
     195             :     // Global values are processed in reverse order.
     196             :     //
     197             :     // Moreover, initializers of GlobalValues are set *after* all the globals
     198             :     // have been read (despite having earlier IDs).  Rather than awkwardly
     199             :     // modeling this behaviour here, orderModule() has assigned IDs to
     200             :     // initializers of GlobalValues before GlobalValues themselves.
     201        4988 :     if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
     202        2367 :       return LID < RID;
     203             : 
     204             :     // If ID is 4, then expect: 7 6 5 1 2 3.
     205      205963 :     if (LID < RID) {
     206      205963 :       if (RID <= ID)
     207         629 :         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
     208             :           return true;
     209             :       return false;
     210             :     }
     211      150867 :     if (RID < LID) {
     212      149083 :       if (LID <= ID)
     213         310 :         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
     214             :           return false;
     215             :       return true;
     216             :     }
     217             : 
     218             :     // LID and RID are equal, so we have different operands of the same user.
     219             :     // Assume operands are added in order for all instructions.
     220        1784 :     if (LID <= ID)
     221          78 :       if (!IsGlobalValue) // GlobalValue uses don't get reversed.
     222          25 :         return LU->getOperandNo() < RU->getOperandNo();
     223        1759 :     return LU->getOperandNo() > RU->getOperandNo();
     224             :   });
     225             : 
     226       19548 :   if (std::is_sorted(
     227             :           List.begin(), List.end(),
     228             :           [](const Entry &L, const Entry &R) { return L.second < R.second; }))
     229             :     // Order is already correct.
     230             :     return;
     231             : 
     232             :   // Store the shuffle.
     233        1536 :   Stack.emplace_back(V, F, List.size());
     234             :   assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
     235       12863 :   for (size_t I = 0, E = List.size(); I != E; ++I)
     236       29373 :     Stack.back().Shuffle[I] = List[I].second;
     237             : }
     238             : 
     239       73749 : static void predictValueUseListOrder(const Value *V, const Function *F,
     240             :                                      OrderMap &OM, UseListOrderStack &Stack) {
     241       73749 :   auto &IDPair = OM[V];
     242             :   assert(IDPair.first && "Unmapped value");
     243       73749 :   if (IDPair.second)
     244             :     // Already predicted.
     245             :     return;
     246             : 
     247             :   // Do the actual prediction.
     248       57428 :   IDPair.second = true;
     249      173420 :   if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
     250        6792 :     predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
     251             : 
     252             :   // Recursive descent into constants.
     253       18676 :   if (const Constant *C = dyn_cast<Constant>(V))
     254       37352 :     if (C->getNumOperands()) // Visit GlobalValues.
     255       13296 :       for (const Value *Op : C->operands())
     256        5630 :         if (isa<Constant>(Op)) // Visit GlobalValues.
     257        5586 :           predictValueUseListOrder(Op, F, OM, Stack);
     258             : }
     259             : 
     260        2564 : static UseListOrderStack predictUseListOrder(const Module &M) {
     261        5128 :   OrderMap OM = orderModule(M);
     262             : 
     263             :   // Use-list orders need to be serialized after all the users have been added
     264             :   // to a value, or else the shuffles will be incomplete.  Store them per
     265             :   // function in a stack.
     266             :   //
     267             :   // Aside from function order, the order of values doesn't matter much here.
     268        2564 :   UseListOrderStack Stack;
     269             : 
     270             :   // We want to visit the functions backward now so we can list function-local
     271             :   // constants in the last Function they're used in.  Module-level constants
     272             :   // have already been visited above.
     273        5128 :   for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
     274        6124 :     const Function &F = *I;
     275        6124 :     if (F.isDeclaration())
     276        1715 :       continue;
     277       21363 :     for (const BasicBlock &BB : F)
     278        8136 :       predictValueUseListOrder(&BB, &F, OM, Stack);
     279        7459 :     for (const Argument &A : F.args())
     280        3050 :       predictValueUseListOrder(&A, &F, OM, Stack);
     281       21363 :     for (const BasicBlock &BB : F)
     282       51930 :       for (const Instruction &I : BB)
     283      100161 :         for (const Value *Op : I.operands())
     284       27381 :           if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
     285       17791 :             predictValueUseListOrder(Op, &F, OM, Stack);
     286       21363 :     for (const BasicBlock &BB : F)
     287       51930 :       for (const Instruction &I : BB)
     288       27522 :         predictValueUseListOrder(&I, &F, OM, Stack);
     289             :   }
     290             : 
     291             :   // Visit globals last, since the module-level use-list block will be seen
     292             :   // before the function bodies are processed.
     293        4804 :   for (const GlobalVariable &G : M.globals())
     294        2240 :     predictValueUseListOrder(&G, nullptr, OM, Stack);
     295       13816 :   for (const Function &F : M)
     296        6124 :     predictValueUseListOrder(&F, nullptr, OM, Stack);
     297        3110 :   for (const GlobalAlias &A : M.aliases())
     298         546 :     predictValueUseListOrder(&A, nullptr, OM, Stack);
     299        2592 :   for (const GlobalIFunc &I : M.ifuncs())
     300          28 :     predictValueUseListOrder(&I, nullptr, OM, Stack);
     301        4804 :   for (const GlobalVariable &G : M.globals())
     302        2240 :     if (G.hasInitializer())
     303        1828 :       predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
     304        3110 :   for (const GlobalAlias &A : M.aliases())
     305         546 :     predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
     306        2592 :   for (const GlobalIFunc &I : M.ifuncs())
     307          28 :     predictValueUseListOrder(I.getResolver(), nullptr, OM, Stack);
     308       13816 :   for (const Function &F : M) {
     309       12572 :     for (const Use &U : F.operands())
     310         324 :       predictValueUseListOrder(U.get(), nullptr, OM, Stack);
     311             :   }
     312             : 
     313        2564 :   return Stack;
     314             : }
     315             : 
     316        5840 : static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
     317       11680 :   return V.first->getType()->isIntOrIntVectorTy();
     318             : }
     319             : 
     320        3637 : ValueEnumerator::ValueEnumerator(const Module &M,
     321        3637 :                                  bool ShouldPreserveUseListOrder)
     322       65466 :     : ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
     323        3637 :   if (ShouldPreserveUseListOrder)
     324        5128 :     UseListOrders = predictUseListOrder(M);
     325             : 
     326             :   // Enumerate the global variables.
     327        8540 :   for (const GlobalVariable &GV : M.globals())
     328        4903 :     EnumerateValue(&GV);
     329             : 
     330             :   // Enumerate the functions.
     331       20547 :   for (const Function & F : M) {
     332        9636 :     EnumerateValue(&F);
     333        9636 :     EnumerateAttributes(F.getAttributes());
     334             :   }
     335             : 
     336             :   // Enumerate the aliases.
     337        4336 :   for (const GlobalAlias &GA : M.aliases())
     338         699 :     EnumerateValue(&GA);
     339             : 
     340             :   // Enumerate the ifuncs.
     341        3665 :   for (const GlobalIFunc &GIF : M.ifuncs())
     342          28 :     EnumerateValue(&GIF);
     343             : 
     344             :   // Remember what is the cutoff between globalvalue's and other constants.
     345        7274 :   unsigned FirstConstant = Values.size();
     346             : 
     347             :   // Enumerate the global variable initializers and attributes.
     348        8540 :   for (const GlobalVariable &GV : M.globals()) {
     349        4903 :     if (GV.hasInitializer())
     350        4005 :       EnumerateValue(GV.getInitializer());
     351        4903 :     if (GV.hasAttributes())
     352          12 :       EnumerateAttributes(GV.getAttributesAsList(AttributeList::FunctionIndex));
     353             :   }
     354             : 
     355             :   // Enumerate the aliasees.
     356        4336 :   for (const GlobalAlias &GA : M.aliases())
     357         699 :     EnumerateValue(GA.getAliasee());
     358             : 
     359             :   // Enumerate the ifunc resolvers.
     360        3665 :   for (const GlobalIFunc &GIF : M.ifuncs())
     361          28 :     EnumerateValue(GIF.getResolver());
     362             : 
     363             :   // Enumerate any optional Function data.
     364       20547 :   for (const Function &F : M)
     365       19701 :     for (const Use &U : F.operands())
     366         429 :       EnumerateValue(U.get());
     367             : 
     368             :   // Enumerate the metadata type.
     369             :   //
     370             :   // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
     371             :   // only encodes the metadata type when it's used as a value.
     372        3637 :   EnumerateType(Type::getMetadataTy(M.getContext()));
     373             : 
     374             :   // Insert constants and metadata that are named at module level into the slot
     375             :   // pool so that the module symbol table can refer to them...
     376        3637 :   EnumerateValueSymbolTable(M.getValueSymbolTable());
     377        3637 :   EnumerateNamedMetadata(M);
     378             : 
     379        7274 :   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
     380        8540 :   for (const GlobalVariable &GV : M.globals()) {
     381        4903 :     MDs.clear();
     382        4903 :     GV.getAllMetadata(MDs);
     383       14798 :     for (const auto &I : MDs)
     384             :       // FIXME: Pass GV to EnumerateMetadata and arrange for the bitcode writer
     385             :       // to write metadata to the global variable's own metadata block
     386             :       // (PR28134).
     387          89 :       EnumerateMetadata(nullptr, I.second);
     388             :   }
     389             : 
     390             :   // Enumerate types used by function bodies and argument lists.
     391       20547 :   for (const Function &F : M) {
     392       17561 :     for (const Argument &A : F.args())
     393        7925 :       EnumerateType(A.getType());
     394             : 
     395             :     // Enumerate metadata attached to this function.
     396        9636 :     MDs.clear();
     397        9636 :     F.getAllMetadata(MDs);
     398       29268 :     for (const auto &I : MDs)
     399         360 :       EnumerateMetadata(F.isDeclaration() ? nullptr : &F, I.second);
     400             : 
     401       40917 :     for (const BasicBlock &BB : F)
     402       91219 :       for (const Instruction &I : BB) {
     403      200680 :         for (const Use &Op : I.operands()) {
     404         820 :           auto *MD = dyn_cast<MetadataAsValue>(&Op);
     405       89476 :           if (!MD) {
     406       89476 :             EnumerateOperandType(Op);
     407       89476 :             continue;
     408             :           }
     409             : 
     410             :           // Local metadata is enumerated during function-incorporation.
     411        1640 :           if (isa<LocalAsMetadata>(MD->getMetadata()))
     412         250 :             continue;
     413             : 
     414         570 :           EnumerateMetadata(&F, MD->getMetadata());
     415             :         }
     416       55192 :         EnumerateType(I.getType());
     417        7570 :         if (const CallInst *CI = dyn_cast<CallInst>(&I))
     418        7570 :           EnumerateAttributes(CI->getAttributes());
     419         144 :         else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
     420         144 :           EnumerateAttributes(II->getAttributes());
     421             : 
     422             :         // Enumerate metadata attached with this instruction.
     423       55192 :         MDs.clear();
     424       55192 :         I.getAllMetadataOtherThanDebugLoc(MDs);
     425      111347 :         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
     426        1926 :           EnumerateMetadata(&F, MDs[i].second);
     427             : 
     428             :         // Don't enumerate the location directly -- it has a special record
     429             :         // type -- but enumerate its operands.
     430      110384 :         if (DILocation *L = I.getDebugLoc())
     431        7976 :           for (const Metadata *Op : L->operands())
     432        2005 :             EnumerateMetadata(&F, Op);
     433             :       }
     434             :   }
     435             : 
     436             :   // Optimize constant ordering.
     437        7274 :   OptimizeConstants(FirstConstant, Values.size());
     438             : 
     439             :   // Organize metadata ordering.
     440        3637 :   organizeMetadata();
     441        3637 : }
     442             : 
     443         873 : unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
     444         873 :   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
     445             :   assert(I != InstructionMap.end() && "Instruction is not mapped!");
     446         873 :   return I->second;
     447             : }
     448             : 
     449         739 : unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
     450        1478 :   unsigned ComdatID = Comdats.idFor(C);
     451             :   assert(ComdatID && "Comdat not found!");
     452         739 :   return ComdatID;
     453             : }
     454             : 
     455       55178 : void ValueEnumerator::setInstructionID(const Instruction *I) {
     456      110356 :   InstructionMap[I] = InstructionCount++;
     457       55178 : }
     458             : 
     459      160057 : unsigned ValueEnumerator::getValueID(const Value *V) const {
     460         820 :   if (auto *MD = dyn_cast<MetadataAsValue>(V))
     461        1640 :     return getMetadataID(MD->getMetadata());
     462             : 
     463      159237 :   ValueMapType::const_iterator I = ValueMap.find(V);
     464             :   assert(I != ValueMap.end() && "Value not in slotcalculator!");
     465      159237 :   return I->second-1;
     466             : }
     467             : 
     468             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     469             : LLVM_DUMP_METHOD void ValueEnumerator::dump() const {
     470             :   print(dbgs(), ValueMap, "Default");
     471             :   dbgs() << '\n';
     472             :   print(dbgs(), MetadataMap, "MetaData");
     473             :   dbgs() << '\n';
     474             : }
     475             : #endif
     476             : 
     477           0 : void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
     478             :                             const char *Name) const {
     479           0 :   OS << "Map Name: " << Name << "\n";
     480           0 :   OS << "Size: " << Map.size() << "\n";
     481           0 :   for (ValueMapType::const_iterator I = Map.begin(),
     482           0 :          E = Map.end(); I != E; ++I) {
     483           0 :     const Value *V = I->first;
     484           0 :     if (V->hasName())
     485           0 :       OS << "Value: " << V->getName();
     486             :     else
     487           0 :       OS << "Value: [null]\n";
     488           0 :     V->print(errs());
     489           0 :     errs() << '\n';
     490             : 
     491           0 :     OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
     492           0 :     for (const Use &U : V->uses()) {
     493           0 :       if (&U != &*V->use_begin())
     494           0 :         OS << ",";
     495           0 :       if(U->hasName())
     496           0 :         OS << " " << U->getName();
     497             :       else
     498           0 :         OS << " [null]";
     499             : 
     500             :     }
     501           0 :     OS <<  "\n\n";
     502             :   }
     503           0 : }
     504             : 
     505           0 : void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
     506             :                             const char *Name) const {
     507           0 :   OS << "Map Name: " << Name << "\n";
     508           0 :   OS << "Size: " << Map.size() << "\n";
     509           0 :   for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
     510           0 :     const Metadata *MD = I->first;
     511           0 :     OS << "Metadata: slot = " << I->second.ID << "\n";
     512           0 :     OS << "Metadata: function = " << I->second.F << "\n";
     513           0 :     MD->print(OS);
     514           0 :     OS << "\n";
     515             :   }
     516           0 : }
     517             : 
     518             : /// OptimizeConstants - Reorder constant pool for denser encoding.
     519       10688 : void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
     520       10688 :   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
     521             : 
     522        2486 :   if (ShouldPreserveUseListOrder)
     523             :     // Optimizing constants makes the use-list order difficult to predict.
     524             :     // Disable it for now when trying to preserve the order.
     525             :     return;
     526             : 
     527        4608 :   std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
     528             :                    [this](const std::pair<const Value *, unsigned> &LHS,
     529       42888 :                           const std::pair<const Value *, unsigned> &RHS) {
     530             :     // Sort by plane.
     531       18252 :     if (LHS.first->getType() != RHS.first->getType())
     532       49272 :       return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
     533             :     // Then by frequency.
     534        5934 :     return LHS.second > RHS.second;
     535             :   });
     536             : 
     537             :   // Ensure that integer and vector of integer constants are at the start of the
     538             :   // constant pool.  This is important so that GEP structure indices come before
     539             :   // gep constant exprs.
     540        3840 :   std::stable_partition(Values.begin() + CstStart, Values.begin() + CstEnd,
     541        1536 :                         isIntOrIntVectorValue);
     542             : 
     543             :   // Rebuild the modified portion of ValueMap.
     544       12448 :   for (; CstStart != CstEnd; ++CstStart)
     545       17520 :     ValueMap[Values[CstStart].first] = CstStart+1;
     546             : }
     547             : 
     548             : /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
     549             : /// table into the values table.
     550        3637 : void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
     551        7274 :   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
     552       18617 :        VI != VE; ++VI)
     553       14980 :     EnumerateValue(VI->getValue());
     554        3637 : }
     555             : 
     556             : /// Insert all of the values referenced by named metadata in the specified
     557             : /// module.
     558        3637 : void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
     559        5258 :   for (const auto &I : M.named_metadata())
     560        1621 :     EnumerateNamedMDNode(&I);
     561        3637 : }
     562             : 
     563        1621 : void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
     564        5319 :   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
     565        3698 :     EnumerateMetadata(nullptr, MD->getOperand(i));
     566        1621 : }
     567             : 
     568        7935 : unsigned ValueEnumerator::getMetadataFunctionID(const Function *F) const {
     569        7935 :   return F ? getValueID(F) + 1 : 0;
     570             : }
     571             : 
     572        7685 : void ValueEnumerator::EnumerateMetadata(const Function *F, const Metadata *MD) {
     573        7685 :   EnumerateMetadata(getMetadataFunctionID(F), MD);
     574        7685 : }
     575             : 
     576         250 : void ValueEnumerator::EnumerateFunctionLocalMetadata(
     577             :     const Function &F, const LocalAsMetadata *Local) {
     578         250 :   EnumerateFunctionLocalMetadata(getMetadataFunctionID(&F), Local);
     579         250 : }
     580             : 
     581         151 : void ValueEnumerator::dropFunctionFromMetadata(
     582             :     MetadataMapType::value_type &FirstMD) {
     583         302 :   SmallVector<const MDNode *, 64> Worklist;
     584         546 :   auto push = [&Worklist](MetadataMapType::value_type &MD) {
     585         399 :     auto &Entry = MD.second;
     586             : 
     587             :     // Nothing to do if this metadata isn't tagged.
     588         399 :     if (!Entry.F)
     589             :       return;
     590             : 
     591             :     // Drop the function tag.
     592         292 :     Entry.F = 0;
     593             : 
     594             :     // If this is has an ID and is an MDNode, then its operands have entries as
     595             :     // well.  We need to drop the function from them too.
     596         292 :     if (Entry.ID)
     597         584 :       if (auto *N = dyn_cast<MDNode>(MD.first))
     598         147 :         Worklist.push_back(N);
     599         151 :   };
     600         151 :   push(FirstMD);
     601         298 :   while (!Worklist.empty())
     602        1186 :     for (const Metadata *Op : Worklist.pop_back_val()->operands()) {
     603         446 :       if (!Op)
     604         198 :         continue;
     605         248 :       auto MD = MetadataMap.find(Op);
     606         744 :       if (MD != MetadataMap.end())
     607         248 :         push(*MD);
     608             :     }
     609         151 : }
     610             : 
     611        7685 : void ValueEnumerator::EnumerateMetadata(unsigned F, const Metadata *MD) {
     612             :   // It's vital for reader efficiency that uniqued subgraphs are done in
     613             :   // post-order; it's expensive when their operands have forward references.
     614             :   // If a distinct node is referenced from a uniqued node, it'll be delayed
     615             :   // until the uniqued subgraph has been completely traversed.
     616       15370 :   SmallVector<const MDNode *, 32> DelayedDistinctNodes;
     617             : 
     618             :   // Start by enumerating MD, and then work through its transitive operands in
     619             :   // post-order.  This requires a depth-first search.
     620       15370 :   SmallVector<std::pair<const MDNode *, MDNode::op_iterator>, 32> Worklist;
     621        7685 :   if (const MDNode *N = enumerateMetadataImpl(F, MD))
     622       13920 :     Worklist.push_back(std::make_pair(N, N->op_begin()));
     623             : 
     624       18817 :   while (!Worklist.empty()) {
     625       22264 :     const MDNode *N = Worklist.back().first;
     626             : 
     627             :     // Enumerate operands until we hit a new node.  We need to traverse these
     628             :     // nodes' operands before visiting the rest of N's operands.
     629       33396 :     MDNode::op_iterator I = std::find_if(
     630       11132 :         Worklist.back().second, N->op_end(),
     631       40484 :         [&](const Metadata *MD) { return enumerateMetadataImpl(F, MD); });
     632       11132 :     if (I != N->op_end()) {
     633        3246 :       auto *Op = cast<MDNode>(*I);
     634        6492 :       Worklist.back().second = ++I;
     635             : 
     636             :       // Delay traversing Op if it's a distinct node and N is uniqued.
     637        3246 :       if (Op->isDistinct() && !N->isDistinct())
     638         165 :         DelayedDistinctNodes.push_back(Op);
     639             :       else
     640       12324 :         Worklist.push_back(std::make_pair(Op, Op->op_begin()));
     641        3246 :       continue;
     642             :     }
     643             : 
     644             :     // All the operands have been visited.  Now assign an ID.
     645        7886 :     Worklist.pop_back();
     646       15772 :     MDs.push_back(N);
     647       23658 :     MetadataMap[N].ID = MDs.size();
     648             : 
     649             :     // Flush out any delayed distinct nodes; these are all the distinct nodes
     650             :     // that are leaves in last uniqued subgraph.
     651       11074 :     if (Worklist.empty() || Worklist.back().first->isDistinct()) {
     652       17559 :       for (const MDNode *N : DelayedDistinctNodes)
     653         495 :         Worklist.push_back(std::make_pair(N, N->op_begin()));
     654             :       DelayedDistinctNodes.clear();
     655             :     }
     656             :   }
     657        7685 : }
     658             : 
     659       37037 : const MDNode *ValueEnumerator::enumerateMetadataImpl(unsigned F, const Metadata *MD) {
     660       37037 :   if (!MD)
     661             :     return nullptr;
     662             : 
     663             :   assert(
     664             :       (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
     665             :       "Invalid metadata kind");
     666             : 
     667       82353 :   auto Insertion = MetadataMap.insert(std::make_pair(MD, MDIndex(F)));
     668       27451 :   MDIndex &Entry = Insertion.first->second;
     669       27451 :   if (!Insertion.second) {
     670             :     // Already mapped.  If F doesn't match the function tag, drop it.
     671       11041 :     if (Entry.hasDifferentFunction(F))
     672         151 :       dropFunctionFromMetadata(*Insertion.first);
     673             :     return nullptr;
     674             :   }
     675             : 
     676             :   // Don't assign IDs to metadata nodes.
     677       16561 :   if (auto *N = dyn_cast<MDNode>(MD))
     678             :     return N;
     679             : 
     680             :   // Save the metadata.
     681        8675 :   MDs.push_back(MD);
     682       17350 :   Entry.ID = MDs.size();
     683             : 
     684             :   // Enumerate the constant, if any.
     685       12349 :   if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
     686        3674 :     EnumerateValue(C->getValue());
     687             : 
     688             :   return nullptr;
     689             : }
     690             : 
     691             : /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
     692             : /// information reachable from the metadata.
     693         250 : void ValueEnumerator::EnumerateFunctionLocalMetadata(
     694             :     unsigned F, const LocalAsMetadata *Local) {
     695             :   assert(F && "Expected a function");
     696             : 
     697             :   // Check to see if it's already in!
     698         500 :   MDIndex &Index = MetadataMap[Local];
     699         250 :   if (Index.ID) {
     700             :     assert(Index.F == F && "Expected the same function");
     701             :     return;
     702             :   }
     703             : 
     704         494 :   MDs.push_back(Local);
     705         247 :   Index.F = F;
     706         494 :   Index.ID = MDs.size();
     707             : 
     708         247 :   EnumerateValue(Local->getValue());
     709             : }
     710             : 
     711             : static unsigned getMetadataTypeOrder(const Metadata *MD) {
     712             :   // Strings are emitted in bulk and must come first.
     713      346112 :   if (isa<MDString>(MD))
     714             :     return 0;
     715             : 
     716             :   // ConstantAsMetadata doesn't reference anything.  We may as well shuffle it
     717             :   // to the front since we can detect it.
     718      197920 :   auto *N = dyn_cast<MDNode>(MD);
     719             :   if (!N)
     720             :     return 1;
     721             : 
     722             :   // The reader is fast forward references for distinct node operands, but slow
     723             :   // when uniqued operands are unresolved.
     724       77743 :   return N->isDistinct() ? 2 : 3;
     725             : }
     726             : 
     727        3637 : void ValueEnumerator::organizeMetadata() {
     728             :   assert(MetadataMap.size() == MDs.size() &&
     729             :          "Metadata map and vector out of sync");
     730             : 
     731        7274 :   if (MDs.empty())
     732        3272 :     return;
     733             : 
     734             :   // Copy out the index information from MetadataMap in order to choose a new
     735             :   // order.
     736        1273 :   SmallVector<MDIndex, 64> Order;
     737        1816 :   Order.reserve(MetadataMap.size());
     738       20193 :   for (const Metadata *MD : MDs)
     739       16561 :     Order.push_back(MetadataMap.lookup(MD));
     740             : 
     741             :   // Partition:
     742             :   //   - by function, then
     743             :   //   - by isa<MDString>
     744             :   // and then sort by the original/current ID.  Since the IDs are guaranteed to
     745             :   // be unique, the result of std::sort will be deterministic.  There's no need
     746             :   // for std::stable_sort.
     747       90160 :   std::sort(Order.begin(), Order.end(), [this](MDIndex LHS, MDIndex RHS) {
     748      432640 :     return std::make_tuple(LHS.F, getMetadataTypeOrder(LHS.get(MDs)), LHS.ID) <
     749      432640 :            std::make_tuple(RHS.F, getMetadataTypeOrder(RHS.get(MDs)), RHS.ID);
     750       86528 :   });
     751             : 
     752             :   // Rebuild MDs, index the metadata ranges for each function in FunctionMDs,
     753             :   // and fix up MetadataMap.
     754        2181 :   std::vector<const Metadata *> OldMDs = std::move(MDs);
     755        1816 :   MDs.reserve(OldMDs.size());
     756       27963 :   for (unsigned I = 0, E = Order.size(); I != E && !Order[I].F; ++I) {
     757       51564 :     auto *MD = Order[I].get(OldMDs);
     758       12891 :     MDs.push_back(MD);
     759       25782 :     MetadataMap[MD].ID = I + 1;
     760       25782 :     if (isa<MDString>(MD))
     761        3783 :       ++NumMDStrings;
     762             :   }
     763             : 
     764             :   // Return early if there's nothing for the functions.
     765        2724 :   if (MDs.size() == Order.size())
     766         543 :     return;
     767             : 
     768             :   // Build the function metadata ranges.
     769         365 :   MDRange R;
     770         365 :   FunctionMDs.reserve(OldMDs.size());
     771         365 :   unsigned PrevF = 0;
     772        4765 :   for (unsigned I = MDs.size(), E = Order.size(), ID = MDs.size(); I != E;
     773             :        ++I) {
     774        7340 :     unsigned F = Order[I].F;
     775        3670 :     if (!PrevF) {
     776         365 :       PrevF = F;
     777        3305 :     } else if (PrevF != F) {
     778         184 :       R.Last = FunctionMDs.size();
     779         276 :       std::swap(R, FunctionMDInfo[PrevF]);
     780         184 :       R.First = FunctionMDs.size();
     781             : 
     782         184 :       ID = MDs.size();
     783          92 :       PrevF = F;
     784             :     }
     785             : 
     786       14680 :     auto *MD = Order[I].get(OldMDs);
     787        3670 :     FunctionMDs.push_back(MD);
     788        7340 :     MetadataMap[MD].ID = ++ID;
     789        7340 :     if (isa<MDString>(MD))
     790        1218 :       ++R.NumStrings;
     791             :   }
     792         730 :   R.Last = FunctionMDs.size();
     793         730 :   FunctionMDInfo[PrevF] = R;
     794             : }
     795             : 
     796        7051 : void ValueEnumerator::incorporateFunctionMetadata(const Function &F) {
     797       14102 :   NumModuleMDs = MDs.size();
     798             : 
     799        7051 :   auto R = FunctionMDInfo.lookup(getValueID(&F) + 1);
     800        7051 :   NumMDStrings = R.NumStrings;
     801       35255 :   MDs.insert(MDs.end(), FunctionMDs.begin() + R.First,
     802       42306 :              FunctionMDs.begin() + R.Last);
     803        7051 : }
     804             : 
     805      110067 : void ValueEnumerator::EnumerateValue(const Value *V) {
     806             :   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
     807             :   assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
     808             : 
     809             :   // Check to see if it's already in!
     810      220134 :   unsigned &ValueID = ValueMap[V];
     811      110067 :   if (ValueID) {
     812             :     // Increment use count.
     813       80970 :     Values[ValueID-1].second++;
     814       40485 :     return;
     815             :   }
     816             : 
     817       84121 :   if (auto *GO = dyn_cast<GlobalObject>(V))
     818       14539 :     if (const Comdat *C = GO->getComdat())
     819         739 :       Comdats.insert(C);
     820             : 
     821             :   // Enumerate the type of this value.
     822       69582 :   EnumerateType(V->getType());
     823             : 
     824      104083 :   if (const Constant *C = dyn_cast<Constant>(V)) {
     825       34501 :     if (isa<GlobalValue>(C)) {
     826             :       // Initializers for globals are handled explicitly elsewhere.
     827       38470 :     } else if (C->getNumOperands()) {
     828             :       // If a constant has operands, enumerate them.  This makes sure that if a
     829             :       // constant has uses (for example an array of const ints), that they are
     830             :       // inserted also.
     831             : 
     832             :       // We prefer to enumerate them with values before we enumerate the user
     833             :       // itself.  This makes it more likely that we can avoid forward references
     834             :       // in the reader.  We know that there can be no cycles in the constants
     835             :       // graph that don't go through a global variable.
     836       21640 :       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
     837       13654 :            I != E; ++I)
     838        9661 :         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
     839        9584 :           EnumerateValue(*I);
     840             : 
     841             :       // Finally, add the value.  Doing this could make the ValueID reference be
     842             :       // dangling, don't reuse it.
     843       11979 :       Values.push_back(std::make_pair(V, 1U));
     844       11979 :       ValueMap[V] = Values.size();
     845        3993 :       return;
     846             :     }
     847             :   }
     848             : 
     849             :   // Add the value.
     850      196767 :   Values.push_back(std::make_pair(V, 1U));
     851      131178 :   ValueID = Values.size();
     852             : }
     853             : 
     854             : 
     855      267223 : void ValueEnumerator::EnumerateType(Type *Ty) {
     856      534446 :   unsigned *TypeID = &TypeMap[Ty];
     857             : 
     858             :   // We've already seen this type.
     859      267223 :   if (*TypeID)
     860             :     return;
     861             : 
     862             :   // If it is a non-anonymous struct, mark the type as being visited so that we
     863             :   // don't recursively visit it.  This is safe because we allow forward
     864             :   // references of these in the bitcode reader.
     865       37850 :   if (StructType *STy = dyn_cast<StructType>(Ty))
     866        2054 :     if (!STy->isLiteral())
     867        1589 :       *TypeID = ~0U;
     868             : 
     869             :   // Enumerate all of the subtypes before we enumerate this type.  This ensures
     870             :   // that the type will be enumerated in an order that can be directly built.
     871      109282 :   for (Type *SubTy : Ty->subtypes())
     872       37690 :     EnumerateType(SubTy);
     873             : 
     874             :   // Refresh the TypeID pointer in case the table rehashed.
     875       71592 :   TypeID = &TypeMap[Ty];
     876             : 
     877             :   // Check to see if we got the pointer another way.  This can happen when
     878             :   // enumerating recursive types that hit the base case deeper than they start.
     879             :   //
     880             :   // If this is actually a struct that we are treating as forward ref'able,
     881             :   // then emit the definition now that all of its contents are available.
     882       35796 :   if (*TypeID && *TypeID != ~0U)
     883             :     return;
     884             : 
     885             :   // Add this type now that its contents are all happily enumerated.
     886       35606 :   Types.push_back(Ty);
     887             : 
     888       71212 :   *TypeID = Types.size();
     889             : }
     890             : 
     891             : // Enumerate the types for the specified value.  If the value is a constant,
     892             : // walk through it, enumerating the types of the constant.
     893       93197 : void ValueEnumerator::EnumerateOperandType(const Value *V) {
     894       93197 :   EnumerateType(V->getType());
     895             : 
     896             :   assert(!isa<MetadataAsValue>(V) && "Unexpected metadata operand");
     897             : 
     898       39484 :   const Constant *C = dyn_cast<Constant>(V);
     899             :   if (!C)
     900             :     return;
     901             : 
     902             :   // If this constant is already enumerated, ignore it, we know its type must
     903             :   // be enumerated.
     904       78968 :   if (ValueMap.count(C))
     905             :     return;
     906             : 
     907             :   // This constant may have operands, make sure to enumerate the types in
     908             :   // them.
     909       34945 :   for (const Value *Op : C->operands()) {
     910             :     // Don't enumerate basic blocks here, this happens as operands to
     911             :     // blockaddress.
     912        7550 :     if (isa<BasicBlock>(Op))
     913          54 :       continue;
     914             : 
     915        3721 :     EnumerateOperandType(Op);
     916             :   }
     917             : }
     918             : 
     919       24413 : void ValueEnumerator::EnumerateAttributes(AttributeList PAL) {
     920       24413 :   if (PAL.isEmpty()) return;  // null is always 0.
     921             : 
     922             :   // Do a lookup.
     923       13778 :   unsigned &Entry = AttributeListMap[PAL];
     924        6889 :   if (Entry == 0) {
     925             :     // Never saw this before, add it.
     926        2147 :     AttributeLists.push_back(PAL);
     927        4294 :     Entry = AttributeLists.size();
     928             :   }
     929             : 
     930             :   // Do lookups for all attribute groups.
     931       25285 :   for (unsigned i = PAL.index_begin(), e = PAL.index_end(); i != e; ++i) {
     932       11507 :     AttributeSet AS = PAL.getAttributes(i);
     933       11507 :     if (!AS.hasAttributes())
     934        2445 :       continue;
     935        9062 :     IndexAndAttrSet Pair = {i, AS};
     936       18124 :     unsigned &Entry = AttributeGroupMap[Pair];
     937        9062 :     if (Entry == 0) {
     938        2456 :       AttributeGroups.push_back(Pair);
     939        4912 :       Entry = AttributeGroups.size();
     940             :     }
     941             :   }
     942             : }
     943             : 
     944        7051 : void ValueEnumerator::incorporateFunction(const Function &F) {
     945        7051 :   InstructionCount = 0;
     946       14102 :   NumModuleValues = Values.size();
     947             : 
     948             :   // Add global metadata to the function block.  This doesn't include
     949             :   // LocalAsMetadata.
     950        7051 :   incorporateFunctionMetadata(F);
     951             : 
     952             :   // Adding function arguments to the value table.
     953       12295 :   for (const auto &I : F.args())
     954        5244 :     EnumerateValue(&I);
     955             : 
     956       14102 :   FirstFuncConstantID = Values.size();
     957             : 
     958             :   // Add all function-level constants to the value table.
     959       33154 :   for (const BasicBlock &BB : F) {
     960       91181 :     for (const Instruction &I : BB)
     961      200640 :       for (const Use &OI : I.operands()) {
     962       99972 :         if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
     963       26129 :           EnumerateValue(OI);
     964             :       }
     965       24002 :     BasicBlocks.push_back(&BB);
     966       36003 :     ValueMap[&BB] = BasicBlocks.size();
     967             :   }
     968             : 
     969             :   // Optimize the constant layout.
     970       14102 :   OptimizeConstants(FirstFuncConstantID, Values.size());
     971             : 
     972             :   // Add the function's parameter attributes so they are available for use in
     973             :   // the function's instruction.
     974        7051 :   EnumerateAttributes(F.getAttributes());
     975             : 
     976       14102 :   FirstInstID = Values.size();
     977             : 
     978       14102 :   SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
     979             :   // Add all of the instructions.
     980       33154 :   for (const BasicBlock &BB : F) {
     981       91181 :     for (const Instruction &I : BB) {
     982      200640 :       for (const Use &OI : I.operands()) {
     983         820 :         if (auto *MD = dyn_cast<MetadataAsValue>(&OI))
     984        1640 :           if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
     985             :             // Enumerate metadata after the instructions they might refer to.
     986         250 :             FnLocalMDVector.push_back(Local);
     987             :       }
     988             : 
     989      110356 :       if (!I.getType()->isVoidTy())
     990       29782 :         EnumerateValue(&I);
     991             :     }
     992             :   }
     993             : 
     994             :   // Add all of the function-local metadata.
     995       14352 :   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) {
     996             :     // At this point, every local values have been incorporated, we shouldn't
     997             :     // have a metadata operand that references a value that hasn't been seen.
     998             :     assert(ValueMap.count(FnLocalMDVector[i]->getValue()) &&
     999             :            "Missing value for metadata operand");
    1000         500 :     EnumerateFunctionLocalMetadata(F, FnLocalMDVector[i]);
    1001             :   }
    1002        7051 : }
    1003             : 
    1004        7051 : void ValueEnumerator::purgeFunction() {
    1005             :   /// Remove purged values from the ValueMap.
    1006       60032 :   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
    1007       91860 :     ValueMap.erase(Values[i].first);
    1008       18003 :   for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
    1009        7802 :     MetadataMap.erase(MDs[i]);
    1010       26103 :   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
    1011       24002 :     ValueMap.erase(BasicBlocks[i]);
    1012             : 
    1013        7051 :   Values.resize(NumModuleValues);
    1014        7051 :   MDs.resize(NumModuleMDs);
    1015       14102 :   BasicBlocks.clear();
    1016        7051 :   NumMDStrings = 0;
    1017        7051 : }
    1018             : 
    1019          51 : static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
    1020             :                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
    1021          51 :   unsigned Counter = 0;
    1022         341 :   for (const BasicBlock &BB : *F)
    1023         376 :     IDMap[&BB] = ++Counter;
    1024          51 : }
    1025             : 
    1026             : /// getGlobalBasicBlockID - This returns the function-specific ID for the
    1027             : /// specified basic block.  This is relatively expensive information, so it
    1028             : /// should only be used by rare constructs such as address-of-label.
    1029         128 : unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
    1030         256 :   unsigned &Idx = GlobalBasicBlockIDs[BB];
    1031         128 :   if (Idx != 0)
    1032          77 :     return Idx-1;
    1033             : 
    1034          51 :   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
    1035          51 :   return getGlobalBasicBlockID(BB);
    1036             : }
    1037             : 
    1038       18145 : uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const {
    1039       54435 :   return Log2_32_Ceil(getTypes().size() + 1);
    1040             : }

Generated by: LCOV version 1.13