Home | History | Annotate | Download | only in Writer
      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/STLExtras.h"
     16 #include "llvm/ADT/SmallPtrSet.h"
     17 #include "llvm/IR/Constants.h"
     18 #include "llvm/IR/DebugInfoMetadata.h"
     19 #include "llvm/IR/DerivedTypes.h"
     20 #include "llvm/IR/Instructions.h"
     21 #include "llvm/IR/Module.h"
     22 #include "llvm/IR/UseListOrder.h"
     23 #include "llvm/IR/ValueSymbolTable.h"
     24 #include "llvm/Support/Debug.h"
     25 #include "llvm/Support/raw_ostream.h"
     26 #include <algorithm>
     27 using namespace llvm;
     28 
     29 namespace {
     30 struct OrderMap {
     31   DenseMap<const Value *, std::pair<unsigned, bool>> IDs;
     32   unsigned LastGlobalConstantID;
     33   unsigned LastGlobalValueID;
     34 
     35   OrderMap() : LastGlobalConstantID(0), LastGlobalValueID(0) {}
     36 
     37   bool isGlobalConstant(unsigned ID) const {
     38     return ID <= LastGlobalConstantID;
     39   }
     40   bool isGlobalValue(unsigned ID) const {
     41     return ID <= LastGlobalValueID && !isGlobalConstant(ID);
     42   }
     43 
     44   unsigned size() const { return IDs.size(); }
     45   std::pair<unsigned, bool> &operator[](const Value *V) { return IDs[V]; }
     46   std::pair<unsigned, bool> lookup(const Value *V) const {
     47     return IDs.lookup(V);
     48   }
     49   void index(const Value *V) {
     50     // Explicitly sequence get-size and insert-value operations to avoid UB.
     51     unsigned ID = IDs.size() + 1;
     52     IDs[V].first = ID;
     53   }
     54 };
     55 }
     56 
     57 static void orderValue(const Value *V, OrderMap &OM) {
     58   if (OM.lookup(V).first)
     59     return;
     60 
     61   if (const Constant *C = dyn_cast<Constant>(V))
     62     if (C->getNumOperands() && !isa<GlobalValue>(C))
     63       for (const Value *Op : C->operands())
     64         if (!isa<BasicBlock>(Op) && !isa<GlobalValue>(Op))
     65           orderValue(Op, OM);
     66 
     67   // Note: we cannot cache this lookup above, since inserting into the map
     68   // changes the map's size, and thus affects the other IDs.
     69   OM.index(V);
     70 }
     71 
     72 static OrderMap orderModule(const Module &M) {
     73   // This needs to match the order used by ValueEnumerator::ValueEnumerator()
     74   // and ValueEnumerator::incorporateFunction().
     75   OrderMap OM;
     76 
     77   // In the reader, initializers of GlobalValues are set *after* all the
     78   // globals have been read.  Rather than awkwardly modeling this behaviour
     79   // directly in predictValueUseListOrderImpl(), just assign IDs to
     80   // initializers of GlobalValues before GlobalValues themselves to model this
     81   // implicitly.
     82   for (const GlobalVariable &G : M.globals())
     83     if (G.hasInitializer())
     84       if (!isa<GlobalValue>(G.getInitializer()))
     85         orderValue(G.getInitializer(), OM);
     86   for (const GlobalAlias &A : M.aliases())
     87     if (!isa<GlobalValue>(A.getAliasee()))
     88       orderValue(A.getAliasee(), OM);
     89   for (const Function &F : M) {
     90     for (const Use &U : F.operands())
     91       if (!isa<GlobalValue>(U.get()))
     92         orderValue(U.get(), OM);
     93   }
     94   OM.LastGlobalConstantID = OM.size();
     95 
     96   // Initializers of GlobalValues are processed in
     97   // BitcodeReader::ResolveGlobalAndAliasInits().  Match the order there rather
     98   // than ValueEnumerator, and match the code in predictValueUseListOrderImpl()
     99   // by giving IDs in reverse order.
    100   //
    101   // Since GlobalValues never reference each other directly (just through
    102   // initializers), their relative IDs only matter for determining order of
    103   // uses in their initializers.
    104   for (const Function &F : M)
    105     orderValue(&F, OM);
    106   for (const GlobalAlias &A : M.aliases())
    107     orderValue(&A, OM);
    108   for (const GlobalVariable &G : M.globals())
    109     orderValue(&G, OM);
    110   OM.LastGlobalValueID = OM.size();
    111 
    112   for (const Function &F : M) {
    113     if (F.isDeclaration())
    114       continue;
    115     // Here we need to match the union of ValueEnumerator::incorporateFunction()
    116     // and WriteFunction().  Basic blocks are implicitly declared before
    117     // anything else (by declaring their size).
    118     for (const BasicBlock &BB : F)
    119       orderValue(&BB, OM);
    120     for (const Argument &A : F.args())
    121       orderValue(&A, OM);
    122     for (const BasicBlock &BB : F)
    123       for (const Instruction &I : BB)
    124         for (const Value *Op : I.operands())
    125           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
    126               isa<InlineAsm>(*Op))
    127             orderValue(Op, OM);
    128     for (const BasicBlock &BB : F)
    129       for (const Instruction &I : BB)
    130         orderValue(&I, OM);
    131   }
    132   return OM;
    133 }
    134 
    135 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
    136                                          unsigned ID, const OrderMap &OM,
    137                                          UseListOrderStack &Stack) {
    138   // Predict use-list order for this one.
    139   typedef std::pair<const Use *, unsigned> Entry;
    140   SmallVector<Entry, 64> List;
    141   for (const Use &U : V->uses())
    142     // Check if this user will be serialized.
    143     if (OM.lookup(U.getUser()).first)
    144       List.push_back(std::make_pair(&U, List.size()));
    145 
    146   if (List.size() < 2)
    147     // We may have lost some users.
    148     return;
    149 
    150   bool IsGlobalValue = OM.isGlobalValue(ID);
    151   std::sort(List.begin(), List.end(), [&](const Entry &L, const Entry &R) {
    152     const Use *LU = L.first;
    153     const Use *RU = R.first;
    154     if (LU == RU)
    155       return false;
    156 
    157     auto LID = OM.lookup(LU->getUser()).first;
    158     auto RID = OM.lookup(RU->getUser()).first;
    159 
    160     // Global values are processed in reverse order.
    161     //
    162     // Moreover, initializers of GlobalValues are set *after* all the globals
    163     // have been read (despite having earlier IDs).  Rather than awkwardly
    164     // modeling this behaviour here, orderModule() has assigned IDs to
    165     // initializers of GlobalValues before GlobalValues themselves.
    166     if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID))
    167       return LID < RID;
    168 
    169     // If ID is 4, then expect: 7 6 5 1 2 3.
    170     if (LID < RID) {
    171       if (RID <= ID)
    172         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
    173           return true;
    174       return false;
    175     }
    176     if (RID < LID) {
    177       if (LID <= ID)
    178         if (!IsGlobalValue) // GlobalValue uses don't get reversed.
    179           return false;
    180       return true;
    181     }
    182 
    183     // LID and RID are equal, so we have different operands of the same user.
    184     // Assume operands are added in order for all instructions.
    185     if (LID <= ID)
    186       if (!IsGlobalValue) // GlobalValue uses don't get reversed.
    187         return LU->getOperandNo() < RU->getOperandNo();
    188     return LU->getOperandNo() > RU->getOperandNo();
    189   });
    190 
    191   if (std::is_sorted(
    192           List.begin(), List.end(),
    193           [](const Entry &L, const Entry &R) { return L.second < R.second; }))
    194     // Order is already correct.
    195     return;
    196 
    197   // Store the shuffle.
    198   Stack.emplace_back(V, F, List.size());
    199   assert(List.size() == Stack.back().Shuffle.size() && "Wrong size");
    200   for (size_t I = 0, E = List.size(); I != E; ++I)
    201     Stack.back().Shuffle[I] = List[I].second;
    202 }
    203 
    204 static void predictValueUseListOrder(const Value *V, const Function *F,
    205                                      OrderMap &OM, UseListOrderStack &Stack) {
    206   auto &IDPair = OM[V];
    207   assert(IDPair.first && "Unmapped value");
    208   if (IDPair.second)
    209     // Already predicted.
    210     return;
    211 
    212   // Do the actual prediction.
    213   IDPair.second = true;
    214   if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
    215     predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
    216 
    217   // Recursive descent into constants.
    218   if (const Constant *C = dyn_cast<Constant>(V))
    219     if (C->getNumOperands()) // Visit GlobalValues.
    220       for (const Value *Op : C->operands())
    221         if (isa<Constant>(Op)) // Visit GlobalValues.
    222           predictValueUseListOrder(Op, F, OM, Stack);
    223 }
    224 
    225 static UseListOrderStack predictUseListOrder(const Module &M) {
    226   OrderMap OM = orderModule(M);
    227 
    228   // Use-list orders need to be serialized after all the users have been added
    229   // to a value, or else the shuffles will be incomplete.  Store them per
    230   // function in a stack.
    231   //
    232   // Aside from function order, the order of values doesn't matter much here.
    233   UseListOrderStack Stack;
    234 
    235   // We want to visit the functions backward now so we can list function-local
    236   // constants in the last Function they're used in.  Module-level constants
    237   // have already been visited above.
    238   for (auto I = M.rbegin(), E = M.rend(); I != E; ++I) {
    239     const Function &F = *I;
    240     if (F.isDeclaration())
    241       continue;
    242     for (const BasicBlock &BB : F)
    243       predictValueUseListOrder(&BB, &F, OM, Stack);
    244     for (const Argument &A : F.args())
    245       predictValueUseListOrder(&A, &F, OM, Stack);
    246     for (const BasicBlock &BB : F)
    247       for (const Instruction &I : BB)
    248         for (const Value *Op : I.operands())
    249           if (isa<Constant>(*Op) || isa<InlineAsm>(*Op)) // Visit GlobalValues.
    250             predictValueUseListOrder(Op, &F, OM, Stack);
    251     for (const BasicBlock &BB : F)
    252       for (const Instruction &I : BB)
    253         predictValueUseListOrder(&I, &F, OM, Stack);
    254   }
    255 
    256   // Visit globals last, since the module-level use-list block will be seen
    257   // before the function bodies are processed.
    258   for (const GlobalVariable &G : M.globals())
    259     predictValueUseListOrder(&G, nullptr, OM, Stack);
    260   for (const Function &F : M)
    261     predictValueUseListOrder(&F, nullptr, OM, Stack);
    262   for (const GlobalAlias &A : M.aliases())
    263     predictValueUseListOrder(&A, nullptr, OM, Stack);
    264   for (const GlobalVariable &G : M.globals())
    265     if (G.hasInitializer())
    266       predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
    267   for (const GlobalAlias &A : M.aliases())
    268     predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
    269   for (const Function &F : M) {
    270     for (const Use &U : F.operands())
    271       predictValueUseListOrder(U.get(), nullptr, OM, Stack);
    272   }
    273 
    274   return Stack;
    275 }
    276 
    277 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
    278   return V.first->getType()->isIntOrIntVectorTy();
    279 }
    280 
    281 ValueEnumerator::ValueEnumerator(const Module &M,
    282                                  bool ShouldPreserveUseListOrder)
    283     : HasMDString(false), HasDILocation(false), HasGenericDINode(false),
    284       ShouldPreserveUseListOrder(ShouldPreserveUseListOrder) {
    285   if (ShouldPreserveUseListOrder)
    286     UseListOrders = predictUseListOrder(M);
    287 
    288   // Enumerate the global variables.
    289   for (const GlobalVariable &GV : M.globals())
    290     EnumerateValue(&GV);
    291 
    292   // Enumerate the functions.
    293   for (const Function & F : M) {
    294     EnumerateValue(&F);
    295     EnumerateAttributes(F.getAttributes());
    296   }
    297 
    298   // Enumerate the aliases.
    299   for (const GlobalAlias &GA : M.aliases())
    300     EnumerateValue(&GA);
    301 
    302   // Remember what is the cutoff between globalvalue's and other constants.
    303   unsigned FirstConstant = Values.size();
    304 
    305   // Enumerate the global variable initializers.
    306   for (const GlobalVariable &GV : M.globals())
    307     if (GV.hasInitializer())
    308       EnumerateValue(GV.getInitializer());
    309 
    310   // Enumerate the aliasees.
    311   for (const GlobalAlias &GA : M.aliases())
    312     EnumerateValue(GA.getAliasee());
    313 
    314   // Enumerate any optional Function data.
    315   for (const Function &F : M)
    316     for (const Use &U : F.operands())
    317       EnumerateValue(U.get());
    318 
    319   // Enumerate the metadata type.
    320   //
    321   // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode
    322   // only encodes the metadata type when it's used as a value.
    323   EnumerateType(Type::getMetadataTy(M.getContext()));
    324 
    325   // Insert constants and metadata that are named at module level into the slot
    326   // pool so that the module symbol table can refer to them...
    327   EnumerateValueSymbolTable(M.getValueSymbolTable());
    328   EnumerateNamedMetadata(M);
    329 
    330   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
    331 
    332   // Enumerate types used by function bodies and argument lists.
    333   for (const Function &F : M) {
    334     for (const Argument &A : F.args())
    335       EnumerateType(A.getType());
    336 
    337     // Enumerate metadata attached to this function.
    338     F.getAllMetadata(MDs);
    339     for (const auto &I : MDs)
    340       EnumerateMetadata(I.second);
    341 
    342     for (const BasicBlock &BB : F)
    343       for (const Instruction &I : BB) {
    344         for (const Use &Op : I.operands()) {
    345           auto *MD = dyn_cast<MetadataAsValue>(&Op);
    346           if (!MD) {
    347             EnumerateOperandType(Op);
    348             continue;
    349           }
    350 
    351           // Local metadata is enumerated during function-incorporation.
    352           if (isa<LocalAsMetadata>(MD->getMetadata()))
    353             continue;
    354 
    355           EnumerateMetadata(MD->getMetadata());
    356         }
    357         EnumerateType(I.getType());
    358         if (const CallInst *CI = dyn_cast<CallInst>(&I))
    359           EnumerateAttributes(CI->getAttributes());
    360         else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
    361           EnumerateAttributes(II->getAttributes());
    362 
    363         // Enumerate metadata attached with this instruction.
    364         MDs.clear();
    365         I.getAllMetadataOtherThanDebugLoc(MDs);
    366         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
    367           EnumerateMetadata(MDs[i].second);
    368 
    369         // Don't enumerate the location directly -- it has a special record
    370         // type -- but enumerate its operands.
    371         if (DILocation *L = I.getDebugLoc())
    372           EnumerateMDNodeOperands(L);
    373       }
    374   }
    375 
    376   // Optimize constant ordering.
    377   OptimizeConstants(FirstConstant, Values.size());
    378 }
    379 
    380 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
    381   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
    382   assert(I != InstructionMap.end() && "Instruction is not mapped!");
    383   return I->second;
    384 }
    385 
    386 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
    387   unsigned ComdatID = Comdats.idFor(C);
    388   assert(ComdatID && "Comdat not found!");
    389   return ComdatID;
    390 }
    391 
    392 void ValueEnumerator::setInstructionID(const Instruction *I) {
    393   InstructionMap[I] = InstructionCount++;
    394 }
    395 
    396 unsigned ValueEnumerator::getValueID(const Value *V) const {
    397   if (auto *MD = dyn_cast<MetadataAsValue>(V))
    398     return getMetadataID(MD->getMetadata());
    399 
    400   ValueMapType::const_iterator I = ValueMap.find(V);
    401   assert(I != ValueMap.end() && "Value not in slotcalculator!");
    402   return I->second-1;
    403 }
    404 
    405 void ValueEnumerator::dump() const {
    406   print(dbgs(), ValueMap, "Default");
    407   dbgs() << '\n';
    408   print(dbgs(), MDValueMap, "MetaData");
    409   dbgs() << '\n';
    410 }
    411 
    412 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
    413                             const char *Name) const {
    414 
    415   OS << "Map Name: " << Name << "\n";
    416   OS << "Size: " << Map.size() << "\n";
    417   for (ValueMapType::const_iterator I = Map.begin(),
    418          E = Map.end(); I != E; ++I) {
    419 
    420     const Value *V = I->first;
    421     if (V->hasName())
    422       OS << "Value: " << V->getName();
    423     else
    424       OS << "Value: [null]\n";
    425     V->dump();
    426 
    427     OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
    428     for (const Use &U : V->uses()) {
    429       if (&U != &*V->use_begin())
    430         OS << ",";
    431       if(U->hasName())
    432         OS << " " << U->getName();
    433       else
    434         OS << " [null]";
    435 
    436     }
    437     OS <<  "\n\n";
    438   }
    439 }
    440 
    441 void ValueEnumerator::print(raw_ostream &OS, const MetadataMapType &Map,
    442                             const char *Name) const {
    443 
    444   OS << "Map Name: " << Name << "\n";
    445   OS << "Size: " << Map.size() << "\n";
    446   for (auto I = Map.begin(), E = Map.end(); I != E; ++I) {
    447     const Metadata *MD = I->first;
    448     OS << "Metadata: slot = " << I->second << "\n";
    449     MD->print(OS);
    450   }
    451 }
    452 
    453 /// OptimizeConstants - Reorder constant pool for denser encoding.
    454 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
    455   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
    456 
    457   if (ShouldPreserveUseListOrder)
    458     // Optimizing constants makes the use-list order difficult to predict.
    459     // Disable it for now when trying to preserve the order.
    460     return;
    461 
    462   std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
    463                    [this](const std::pair<const Value *, unsigned> &LHS,
    464                           const std::pair<const Value *, unsigned> &RHS) {
    465     // Sort by plane.
    466     if (LHS.first->getType() != RHS.first->getType())
    467       return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
    468     // Then by frequency.
    469     return LHS.second > RHS.second;
    470   });
    471 
    472   // Ensure that integer and vector of integer constants are at the start of the
    473   // constant pool.  This is important so that GEP structure indices come before
    474   // gep constant exprs.
    475   std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
    476                  isIntOrIntVectorValue);
    477 
    478   // Rebuild the modified portion of ValueMap.
    479   for (; CstStart != CstEnd; ++CstStart)
    480     ValueMap[Values[CstStart].first] = CstStart+1;
    481 }
    482 
    483 
    484 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
    485 /// table into the values table.
    486 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
    487   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
    488        VI != VE; ++VI)
    489     EnumerateValue(VI->getValue());
    490 }
    491 
    492 /// Insert all of the values referenced by named metadata in the specified
    493 /// module.
    494 void ValueEnumerator::EnumerateNamedMetadata(const Module &M) {
    495   for (const auto &I : M.named_metadata())
    496     EnumerateNamedMDNode(&I);
    497 }
    498 
    499 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
    500   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
    501     EnumerateMetadata(MD->getOperand(i));
    502 }
    503 
    504 /// EnumerateMDNodeOperands - Enumerate all non-function-local values
    505 /// and types referenced by the given MDNode.
    506 void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
    507   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
    508     Metadata *MD = N->getOperand(i);
    509     if (!MD)
    510       continue;
    511     assert(!isa<LocalAsMetadata>(MD) && "MDNodes cannot be function-local");
    512     EnumerateMetadata(MD);
    513   }
    514 }
    515 
    516 void ValueEnumerator::EnumerateMetadata(const Metadata *MD) {
    517   assert(
    518       (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) &&
    519       "Invalid metadata kind");
    520 
    521   // Insert a dummy ID to block the co-recursive call to
    522   // EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph.
    523   //
    524   // Return early if there's already an ID.
    525   if (!MDValueMap.insert(std::make_pair(MD, 0)).second)
    526     return;
    527 
    528   // Visit operands first to minimize RAUW.
    529   if (auto *N = dyn_cast<MDNode>(MD))
    530     EnumerateMDNodeOperands(N);
    531   else if (auto *C = dyn_cast<ConstantAsMetadata>(MD))
    532     EnumerateValue(C->getValue());
    533 
    534   HasMDString |= isa<MDString>(MD);
    535   HasDILocation |= isa<DILocation>(MD);
    536   HasGenericDINode |= isa<GenericDINode>(MD);
    537 
    538   // Replace the dummy ID inserted above with the correct one.  MDValueMap may
    539   // have changed by inserting operands, so we need a fresh lookup here.
    540   MDs.push_back(MD);
    541   MDValueMap[MD] = MDs.size();
    542 }
    543 
    544 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
    545 /// information reachable from the metadata.
    546 void ValueEnumerator::EnumerateFunctionLocalMetadata(
    547     const LocalAsMetadata *Local) {
    548   // Check to see if it's already in!
    549   unsigned &MDValueID = MDValueMap[Local];
    550   if (MDValueID)
    551     return;
    552 
    553   MDs.push_back(Local);
    554   MDValueID = MDs.size();
    555 
    556   EnumerateValue(Local->getValue());
    557 
    558   // Also, collect all function-local metadata for easy access.
    559   FunctionLocalMDs.push_back(Local);
    560 }
    561 
    562 void ValueEnumerator::EnumerateValue(const Value *V) {
    563   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
    564   assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!");
    565 
    566   // Check to see if it's already in!
    567   unsigned &ValueID = ValueMap[V];
    568   if (ValueID) {
    569     // Increment use count.
    570     Values[ValueID-1].second++;
    571     return;
    572   }
    573 
    574   if (auto *GO = dyn_cast<GlobalObject>(V))
    575     if (const Comdat *C = GO->getComdat())
    576       Comdats.insert(C);
    577 
    578   // Enumerate the type of this value.
    579   EnumerateType(V->getType());
    580 
    581   if (const Constant *C = dyn_cast<Constant>(V)) {
    582     if (isa<GlobalValue>(C)) {
    583       // Initializers for globals are handled explicitly elsewhere.
    584     } else if (C->getNumOperands()) {
    585       // If a constant has operands, enumerate them.  This makes sure that if a
    586       // constant has uses (for example an array of const ints), that they are
    587       // inserted also.
    588 
    589       // We prefer to enumerate them with values before we enumerate the user
    590       // itself.  This makes it more likely that we can avoid forward references
    591       // in the reader.  We know that there can be no cycles in the constants
    592       // graph that don't go through a global variable.
    593       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
    594            I != E; ++I)
    595         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
    596           EnumerateValue(*I);
    597 
    598       // Finally, add the value.  Doing this could make the ValueID reference be
    599       // dangling, don't reuse it.
    600       Values.push_back(std::make_pair(V, 1U));
    601       ValueMap[V] = Values.size();
    602       return;
    603     }
    604   }
    605 
    606   // Add the value.
    607   Values.push_back(std::make_pair(V, 1U));
    608   ValueID = Values.size();
    609 }
    610 
    611 
    612 void ValueEnumerator::EnumerateType(Type *Ty) {
    613   unsigned *TypeID = &TypeMap[Ty];
    614 
    615   // We've already seen this type.
    616   if (*TypeID)
    617     return;
    618 
    619   // If it is a non-anonymous struct, mark the type as being visited so that we
    620   // don't recursively visit it.  This is safe because we allow forward
    621   // references of these in the bitcode reader.
    622   if (StructType *STy = dyn_cast<StructType>(Ty))
    623     if (!STy->isLiteral())
    624       *TypeID = ~0U;
    625 
    626   // Enumerate all of the subtypes before we enumerate this type.  This ensures
    627   // that the type will be enumerated in an order that can be directly built.
    628   for (Type *SubTy : Ty->subtypes())
    629     EnumerateType(SubTy);
    630 
    631   // Refresh the TypeID pointer in case the table rehashed.
    632   TypeID = &TypeMap[Ty];
    633 
    634   // Check to see if we got the pointer another way.  This can happen when
    635   // enumerating recursive types that hit the base case deeper than they start.
    636   //
    637   // If this is actually a struct that we are treating as forward ref'able,
    638   // then emit the definition now that all of its contents are available.
    639   if (*TypeID && *TypeID != ~0U)
    640     return;
    641 
    642   // Add this type now that its contents are all happily enumerated.
    643   Types.push_back(Ty);
    644 
    645   *TypeID = Types.size();
    646 }
    647 
    648 // Enumerate the types for the specified value.  If the value is a constant,
    649 // walk through it, enumerating the types of the constant.
    650 void ValueEnumerator::EnumerateOperandType(const Value *V) {
    651   EnumerateType(V->getType());
    652 
    653   if (auto *MD = dyn_cast<MetadataAsValue>(V)) {
    654     assert(!isa<LocalAsMetadata>(MD->getMetadata()) &&
    655            "Function-local metadata should be left for later");
    656 
    657     EnumerateMetadata(MD->getMetadata());
    658     return;
    659   }
    660 
    661   const Constant *C = dyn_cast<Constant>(V);
    662   if (!C)
    663     return;
    664 
    665   // If this constant is already enumerated, ignore it, we know its type must
    666   // be enumerated.
    667   if (ValueMap.count(C))
    668     return;
    669 
    670   // This constant may have operands, make sure to enumerate the types in
    671   // them.
    672   for (const Value *Op : C->operands()) {
    673     // Don't enumerate basic blocks here, this happens as operands to
    674     // blockaddress.
    675     if (isa<BasicBlock>(Op))
    676       continue;
    677 
    678     EnumerateOperandType(Op);
    679   }
    680 }
    681 
    682 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
    683   if (PAL.isEmpty()) return;  // null is always 0.
    684 
    685   // Do a lookup.
    686   unsigned &Entry = AttributeMap[PAL];
    687   if (Entry == 0) {
    688     // Never saw this before, add it.
    689     Attribute.push_back(PAL);
    690     Entry = Attribute.size();
    691   }
    692 
    693   // Do lookups for all attribute groups.
    694   for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
    695     AttributeSet AS = PAL.getSlotAttributes(i);
    696     unsigned &Entry = AttributeGroupMap[AS];
    697     if (Entry == 0) {
    698       AttributeGroups.push_back(AS);
    699       Entry = AttributeGroups.size();
    700     }
    701   }
    702 }
    703 
    704 void ValueEnumerator::incorporateFunction(const Function &F) {
    705   InstructionCount = 0;
    706   NumModuleValues = Values.size();
    707   NumModuleMDs = MDs.size();
    708 
    709   // Adding function arguments to the value table.
    710   for (const auto &I : F.args())
    711     EnumerateValue(&I);
    712 
    713   FirstFuncConstantID = Values.size();
    714 
    715   // Add all function-level constants to the value table.
    716   for (const BasicBlock &BB : F) {
    717     for (const Instruction &I : BB)
    718       for (const Use &OI : I.operands()) {
    719         if ((isa<Constant>(OI) && !isa<GlobalValue>(OI)) || isa<InlineAsm>(OI))
    720           EnumerateValue(OI);
    721       }
    722     BasicBlocks.push_back(&BB);
    723     ValueMap[&BB] = BasicBlocks.size();
    724   }
    725 
    726   // Optimize the constant layout.
    727   OptimizeConstants(FirstFuncConstantID, Values.size());
    728 
    729   // Add the function's parameter attributes so they are available for use in
    730   // the function's instruction.
    731   EnumerateAttributes(F.getAttributes());
    732 
    733   FirstInstID = Values.size();
    734 
    735   SmallVector<LocalAsMetadata *, 8> FnLocalMDVector;
    736   // Add all of the instructions.
    737   for (const BasicBlock &BB : F) {
    738     for (const Instruction &I : BB) {
    739       for (const Use &OI : I.operands()) {
    740         if (auto *MD = dyn_cast<MetadataAsValue>(&OI))
    741           if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata()))
    742             // Enumerate metadata after the instructions they might refer to.
    743             FnLocalMDVector.push_back(Local);
    744       }
    745 
    746       if (!I.getType()->isVoidTy())
    747         EnumerateValue(&I);
    748     }
    749   }
    750 
    751   // Add all of the function-local metadata.
    752   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
    753     EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
    754 }
    755 
    756 void ValueEnumerator::purgeFunction() {
    757   /// Remove purged values from the ValueMap.
    758   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
    759     ValueMap.erase(Values[i].first);
    760   for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i)
    761     MDValueMap.erase(MDs[i]);
    762   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
    763     ValueMap.erase(BasicBlocks[i]);
    764 
    765   Values.resize(NumModuleValues);
    766   MDs.resize(NumModuleMDs);
    767   BasicBlocks.clear();
    768   FunctionLocalMDs.clear();
    769 }
    770 
    771 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
    772                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
    773   unsigned Counter = 0;
    774   for (const BasicBlock &BB : *F)
    775     IDMap[&BB] = ++Counter;
    776 }
    777 
    778 /// getGlobalBasicBlockID - This returns the function-specific ID for the
    779 /// specified basic block.  This is relatively expensive information, so it
    780 /// should only be used by rare constructs such as address-of-label.
    781 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
    782   unsigned &Idx = GlobalBasicBlockIDs[BB];
    783   if (Idx != 0)
    784     return Idx-1;
    785 
    786   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
    787   return getGlobalBasicBlockID(BB);
    788 }
    789 
    790 uint64_t ValueEnumerator::computeBitsRequiredForTypeIndicies() const {
    791   return Log2_32_Ceil(getTypes().size() + 1);
    792 }
    793