lib/Bitcode/Writer/ValueEnumerator.cpp

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