LLVM API Documentation

ValueEnumerator.cpp
Go to the documentation of this file.
00001 //===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the ValueEnumerator class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "ValueEnumerator.h"
00015 #include "llvm/ADT/STLExtras.h"
00016 #include "llvm/ADT/SmallPtrSet.h"
00017 #include "llvm/IR/Constants.h"
00018 #include "llvm/IR/DerivedTypes.h"
00019 #include "llvm/IR/Instructions.h"
00020 #include "llvm/IR/Module.h"
00021 #include "llvm/IR/UseListOrder.h"
00022 #include "llvm/IR/ValueSymbolTable.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/raw_ostream.h"
00025 #include <algorithm>
00026 using namespace llvm;
00027 
00028 namespace {
00029 typedef DenseMap<const Value *, std::pair<unsigned, bool>> OrderMap;
00030 }
00031 
00032 static void orderValue(const Value *V, OrderMap &OM) {
00033   if (OM.lookup(V).first)
00034     return;
00035 
00036   if (const Constant *C = dyn_cast<Constant>(V))
00037     if (C->getNumOperands() && !isa<GlobalValue>(C))
00038       for (const Value *Op : C->operands())
00039         if (!isa<BasicBlock>(Op))
00040           orderValue(Op, OM);
00041 
00042   // Note: we cannot cache this lookup above, since inserting into the map
00043   // changes the map's size, and thus affects the ID.
00044   OM[V].first = OM.size() + 1;
00045 }
00046 
00047 static OrderMap orderModule(const Module *M) {
00048   // This needs to match the order used by ValueEnumerator::ValueEnumerator()
00049   // and ValueEnumerator::incorporateFunction().
00050   OrderMap OM;
00051 
00052   for (const GlobalVariable &G : M->globals())
00053     orderValue(&G, OM);
00054   for (const Function &F : *M)
00055     orderValue(&F, OM);
00056   for (const GlobalAlias &A : M->aliases())
00057     orderValue(&A, OM);
00058   for (const GlobalVariable &G : M->globals())
00059     if (G.hasInitializer())
00060       orderValue(G.getInitializer(), OM);
00061   for (const GlobalAlias &A : M->aliases())
00062     orderValue(A.getAliasee(), OM);
00063   for (const Function &F : *M)
00064     if (F.hasPrefixData())
00065       orderValue(F.getPrefixData(), OM);
00066 
00067   for (const Function &F : *M) {
00068     if (F.isDeclaration())
00069       continue;
00070     // Here we need to match the union of ValueEnumerator::incorporateFunction()
00071     // and WriteFunction().  Basic blocks are implicitly declared before
00072     // anything else (by declaring their size).
00073     for (const BasicBlock &BB : F)
00074       orderValue(&BB, OM);
00075     for (const Argument &A : F.args())
00076       orderValue(&A, OM);
00077     for (const BasicBlock &BB : F)
00078       for (const Instruction &I : BB)
00079         for (const Value *Op : I.operands())
00080           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
00081               isa<InlineAsm>(*Op))
00082             orderValue(Op, OM);
00083     for (const BasicBlock &BB : F)
00084       for (const Instruction &I : BB)
00085         orderValue(&I, OM);
00086   }
00087   return OM;
00088 }
00089 
00090 static void predictValueUseListOrderImpl(const Value *V, const Function *F,
00091                                          unsigned ID, const OrderMap &OM,
00092                                          UseListOrderStack &Stack) {
00093   // Predict use-list order for this one.
00094   typedef std::pair<const Use *, unsigned> Entry;
00095   SmallVector<Entry, 64> List;
00096   for (const Use &U : V->uses())
00097     // Check if this user will be serialized.
00098     if (OM.lookup(U.getUser()).first)
00099       List.push_back(std::make_pair(&U, List.size()));
00100 
00101   if (List.size() < 2)
00102     // We may have lost some users.
00103     return;
00104 
00105   std::sort(List.begin(), List.end(),
00106             [&OM, ID](const Entry &L, const Entry &R) {
00107     const Use *LU = L.first;
00108     const Use *RU = R.first;
00109     if (LU == RU)
00110       return false;
00111 
00112     auto LID = OM.lookup(LU->getUser()).first;
00113     auto RID = OM.lookup(RU->getUser()).first;
00114     // If ID is 4, then expect: 7 6 5 1 2 3.
00115     if (LID < RID) {
00116       if (RID < ID)
00117         return true;
00118       return false;
00119     }
00120     if (RID < LID) {
00121       if (LID < ID)
00122         return false;
00123       return true;
00124     }
00125     // LID and RID are equal, so we have different operands of the same user.
00126     // Assume operands are added in order for all instructions.
00127     if (LU->getOperandNo() < RU->getOperandNo())
00128       return LID < ID;
00129     return ID < LID;
00130   });
00131 
00132   if (std::is_sorted(
00133           List.begin(), List.end(),
00134           [](const Entry &L, const Entry &R) { return L.second < R.second; }))
00135     // Order is already correct.
00136     return;
00137 
00138   // Store the shuffle.
00139   UseListOrder O(V, F, List.size());
00140   assert(List.size() == O.Shuffle.size() && "Wrong size");
00141   for (size_t I = 0, E = List.size(); I != E; ++I)
00142     O.Shuffle[I] = List[I].second;
00143   Stack.emplace_back(std::move(O));
00144 }
00145 
00146 static void predictValueUseListOrder(const Value *V, const Function *F,
00147                                      OrderMap &OM, UseListOrderStack &Stack) {
00148   auto &IDPair = OM[V];
00149   assert(IDPair.first && "Unmapped value");
00150   if (IDPair.second)
00151     // Already predicted.
00152     return;
00153 
00154   // Do the actual prediction.
00155   IDPair.second = true;
00156   if (!V->use_empty() && std::next(V->use_begin()) != V->use_end())
00157     predictValueUseListOrderImpl(V, F, IDPair.first, OM, Stack);
00158 
00159   // Recursive descent into constants.
00160   if (const Constant *C = dyn_cast<Constant>(V))
00161     if (C->getNumOperands() && !isa<GlobalValue>(C))
00162       for (const Value *Op : C->operands())
00163         if (isa<Constant>(Op) && !isa<GlobalValue>(Op))
00164           predictValueUseListOrder(Op, F, OM, Stack);
00165 }
00166 
00167 static UseListOrderStack predictUseListOrder(const Module *M) {
00168   OrderMap OM = orderModule(M);
00169 
00170   // Use-list orders need to be serialized after all the users have been added
00171   // to a value, or else the shuffles will be incomplete.  Store them per
00172   // function in a stack.
00173   //
00174   // Aside from function order, the order of values doesn't matter much here.
00175   UseListOrderStack Stack;
00176 
00177   // We want to visit the functions backward now so we can list function-local
00178   // constants in the last Function they're used in.  Module-level constants
00179   // have already been visited above.
00180   for (auto I = M->rbegin(), E = M->rend(); I != E; ++I) {
00181     const Function &F = *I;
00182     if (F.isDeclaration())
00183       continue;
00184     for (const BasicBlock &BB : F)
00185       predictValueUseListOrder(&BB, &F, OM, Stack);
00186     for (const Argument &A : F.args())
00187       predictValueUseListOrder(&A, &F, OM, Stack);
00188     for (const BasicBlock &BB : F)
00189       for (const Instruction &I : BB)
00190         for (const Value *Op : I.operands())
00191           if ((isa<Constant>(*Op) && !isa<GlobalValue>(*Op)) ||
00192               isa<InlineAsm>(*Op))
00193             predictValueUseListOrder(Op, &F, OM, Stack);
00194     for (const BasicBlock &BB : F)
00195       for (const Instruction &I : BB)
00196         predictValueUseListOrder(&I, &F, OM, Stack);
00197   }
00198 
00199   // Visit globals last, since the module-level use-list block will be seen
00200   // before the function bodies are processed.
00201   for (const GlobalVariable &G : M->globals())
00202     predictValueUseListOrder(&G, nullptr, OM, Stack);
00203   for (const Function &F : *M)
00204     predictValueUseListOrder(&F, nullptr, OM, Stack);
00205   for (const GlobalAlias &A : M->aliases())
00206     predictValueUseListOrder(&A, nullptr, OM, Stack);
00207   for (const GlobalVariable &G : M->globals())
00208     if (G.hasInitializer())
00209       predictValueUseListOrder(G.getInitializer(), nullptr, OM, Stack);
00210   for (const GlobalAlias &A : M->aliases())
00211     predictValueUseListOrder(A.getAliasee(), nullptr, OM, Stack);
00212   for (const Function &F : *M)
00213     if (F.hasPrefixData())
00214       predictValueUseListOrder(F.getPrefixData(), nullptr, OM, Stack);
00215 
00216   return Stack;
00217 }
00218 
00219 static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
00220   return V.first->getType()->isIntOrIntVectorTy();
00221 }
00222 
00223 /// ValueEnumerator - Enumerate module-level information.
00224 ValueEnumerator::ValueEnumerator(const Module *M) {
00225   if (shouldPreserveBitcodeUseListOrder())
00226     UseListOrders = predictUseListOrder(M);
00227 
00228   // Enumerate the global variables.
00229   for (Module::const_global_iterator I = M->global_begin(),
00230 
00231          E = M->global_end(); I != E; ++I)
00232     EnumerateValue(I);
00233 
00234   // Enumerate the functions.
00235   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
00236     EnumerateValue(I);
00237     EnumerateAttributes(cast<Function>(I)->getAttributes());
00238   }
00239 
00240   // Enumerate the aliases.
00241   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
00242        I != E; ++I)
00243     EnumerateValue(I);
00244 
00245   // Remember what is the cutoff between globalvalue's and other constants.
00246   unsigned FirstConstant = Values.size();
00247 
00248   // Enumerate the global variable initializers.
00249   for (Module::const_global_iterator I = M->global_begin(),
00250          E = M->global_end(); I != E; ++I)
00251     if (I->hasInitializer())
00252       EnumerateValue(I->getInitializer());
00253 
00254   // Enumerate the aliasees.
00255   for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
00256        I != E; ++I)
00257     EnumerateValue(I->getAliasee());
00258 
00259   // Enumerate the prefix data constants.
00260   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
00261     if (I->hasPrefixData())
00262       EnumerateValue(I->getPrefixData());
00263 
00264   // Insert constants and metadata that are named at module level into the slot
00265   // pool so that the module symbol table can refer to them...
00266   EnumerateValueSymbolTable(M->getValueSymbolTable());
00267   EnumerateNamedMetadata(M);
00268 
00269   SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
00270 
00271   // Enumerate types used by function bodies and argument lists.
00272   for (const Function &F : *M) {
00273     for (const Argument &A : F.args())
00274       EnumerateType(A.getType());
00275 
00276     for (const BasicBlock &BB : F)
00277       for (const Instruction &I : BB) {
00278         for (const Use &Op : I.operands()) {
00279           if (MDNode *MD = dyn_cast<MDNode>(&Op))
00280             if (MD->isFunctionLocal() && MD->getFunction())
00281               // These will get enumerated during function-incorporation.
00282               continue;
00283           EnumerateOperandType(Op);
00284         }
00285         EnumerateType(I.getType());
00286         if (const CallInst *CI = dyn_cast<CallInst>(&I))
00287           EnumerateAttributes(CI->getAttributes());
00288         else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I))
00289           EnumerateAttributes(II->getAttributes());
00290 
00291         // Enumerate metadata attached with this instruction.
00292         MDs.clear();
00293         I.getAllMetadataOtherThanDebugLoc(MDs);
00294         for (unsigned i = 0, e = MDs.size(); i != e; ++i)
00295           EnumerateMetadata(MDs[i].second);
00296 
00297         if (!I.getDebugLoc().isUnknown()) {
00298           MDNode *Scope, *IA;
00299           I.getDebugLoc().getScopeAndInlinedAt(Scope, IA, I.getContext());
00300           if (Scope) EnumerateMetadata(Scope);
00301           if (IA) EnumerateMetadata(IA);
00302         }
00303       }
00304   }
00305 
00306   // Optimize constant ordering.
00307   OptimizeConstants(FirstConstant, Values.size());
00308 }
00309 
00310 unsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const {
00311   InstructionMapType::const_iterator I = InstructionMap.find(Inst);
00312   assert(I != InstructionMap.end() && "Instruction is not mapped!");
00313   return I->second;
00314 }
00315 
00316 unsigned ValueEnumerator::getComdatID(const Comdat *C) const {
00317   unsigned ComdatID = Comdats.idFor(C);
00318   assert(ComdatID && "Comdat not found!");
00319   return ComdatID;
00320 }
00321 
00322 void ValueEnumerator::setInstructionID(const Instruction *I) {
00323   InstructionMap[I] = InstructionCount++;
00324 }
00325 
00326 unsigned ValueEnumerator::getValueID(const Value *V) const {
00327   if (isa<MDNode>(V) || isa<MDString>(V)) {
00328     ValueMapType::const_iterator I = MDValueMap.find(V);
00329     assert(I != MDValueMap.end() && "Value not in slotcalculator!");
00330     return I->second-1;
00331   }
00332 
00333   ValueMapType::const_iterator I = ValueMap.find(V);
00334   assert(I != ValueMap.end() && "Value not in slotcalculator!");
00335   return I->second-1;
00336 }
00337 
00338 void ValueEnumerator::dump() const {
00339   print(dbgs(), ValueMap, "Default");
00340   dbgs() << '\n';
00341   print(dbgs(), MDValueMap, "MetaData");
00342   dbgs() << '\n';
00343 }
00344 
00345 void ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
00346                             const char *Name) const {
00347 
00348   OS << "Map Name: " << Name << "\n";
00349   OS << "Size: " << Map.size() << "\n";
00350   for (ValueMapType::const_iterator I = Map.begin(),
00351          E = Map.end(); I != E; ++I) {
00352 
00353     const Value *V = I->first;
00354     if (V->hasName())
00355       OS << "Value: " << V->getName();
00356     else
00357       OS << "Value: [null]\n";
00358     V->dump();
00359 
00360     OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
00361     for (const Use &U : V->uses()) {
00362       if (&U != &*V->use_begin())
00363         OS << ",";
00364       if(U->hasName())
00365         OS << " " << U->getName();
00366       else
00367         OS << " [null]";
00368 
00369     }
00370     OS <<  "\n\n";
00371   }
00372 }
00373 
00374 /// OptimizeConstants - Reorder constant pool for denser encoding.
00375 void ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) {
00376   if (CstStart == CstEnd || CstStart+1 == CstEnd) return;
00377 
00378   if (shouldPreserveBitcodeUseListOrder())
00379     // Optimizing constants makes the use-list order difficult to predict.
00380     // Disable it for now when trying to preserve the order.
00381     return;
00382 
00383   std::stable_sort(Values.begin() + CstStart, Values.begin() + CstEnd,
00384                    [this](const std::pair<const Value *, unsigned> &LHS,
00385                           const std::pair<const Value *, unsigned> &RHS) {
00386     // Sort by plane.
00387     if (LHS.first->getType() != RHS.first->getType())
00388       return getTypeID(LHS.first->getType()) < getTypeID(RHS.first->getType());
00389     // Then by frequency.
00390     return LHS.second > RHS.second;
00391   });
00392 
00393   // Ensure that integer and vector of integer constants are at the start of the
00394   // constant pool.  This is important so that GEP structure indices come before
00395   // gep constant exprs.
00396   std::partition(Values.begin()+CstStart, Values.begin()+CstEnd,
00397                  isIntOrIntVectorValue);
00398 
00399   // Rebuild the modified portion of ValueMap.
00400   for (; CstStart != CstEnd; ++CstStart)
00401     ValueMap[Values[CstStart].first] = CstStart+1;
00402 }
00403 
00404 
00405 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
00406 /// table into the values table.
00407 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
00408   for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
00409        VI != VE; ++VI)
00410     EnumerateValue(VI->getValue());
00411 }
00412 
00413 /// EnumerateNamedMetadata - Insert all of the values referenced by
00414 /// named metadata in the specified module.
00415 void ValueEnumerator::EnumerateNamedMetadata(const Module *M) {
00416   for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
00417        E = M->named_metadata_end(); I != E; ++I)
00418     EnumerateNamedMDNode(I);
00419 }
00420 
00421 void ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) {
00422   for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i)
00423     EnumerateMetadata(MD->getOperand(i));
00424 }
00425 
00426 /// EnumerateMDNodeOperands - Enumerate all non-function-local values
00427 /// and types referenced by the given MDNode.
00428 void ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) {
00429   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00430     if (Value *V = N->getOperand(i)) {
00431       if (isa<MDNode>(V) || isa<MDString>(V))
00432         EnumerateMetadata(V);
00433       else if (!isa<Instruction>(V) && !isa<Argument>(V))
00434         EnumerateValue(V);
00435     } else
00436       EnumerateType(Type::getVoidTy(N->getContext()));
00437   }
00438 }
00439 
00440 void ValueEnumerator::EnumerateMetadata(const Value *MD) {
00441   assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind");
00442 
00443   // Enumerate the type of this value.
00444   EnumerateType(MD->getType());
00445 
00446   const MDNode *N = dyn_cast<MDNode>(MD);
00447 
00448   // In the module-level pass, skip function-local nodes themselves, but
00449   // do walk their operands.
00450   if (N && N->isFunctionLocal() && N->getFunction()) {
00451     EnumerateMDNodeOperands(N);
00452     return;
00453   }
00454 
00455   // Check to see if it's already in!
00456   unsigned &MDValueID = MDValueMap[MD];
00457   if (MDValueID) {
00458     // Increment use count.
00459     MDValues[MDValueID-1].second++;
00460     return;
00461   }
00462   MDValues.push_back(std::make_pair(MD, 1U));
00463   MDValueID = MDValues.size();
00464 
00465   // Enumerate all non-function-local operands.
00466   if (N)
00467     EnumerateMDNodeOperands(N);
00468 }
00469 
00470 /// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata
00471 /// information reachable from the given MDNode.
00472 void ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) {
00473   assert(N->isFunctionLocal() && N->getFunction() &&
00474          "EnumerateFunctionLocalMetadata called on non-function-local mdnode!");
00475 
00476   // Enumerate the type of this value.
00477   EnumerateType(N->getType());
00478 
00479   // Check to see if it's already in!
00480   unsigned &MDValueID = MDValueMap[N];
00481   if (MDValueID) {
00482     // Increment use count.
00483     MDValues[MDValueID-1].second++;
00484     return;
00485   }
00486   MDValues.push_back(std::make_pair(N, 1U));
00487   MDValueID = MDValues.size();
00488 
00489   // To incoroporate function-local information visit all function-local
00490   // MDNodes and all function-local values they reference.
00491   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00492     if (Value *V = N->getOperand(i)) {
00493       if (MDNode *O = dyn_cast<MDNode>(V)) {
00494         if (O->isFunctionLocal() && O->getFunction())
00495           EnumerateFunctionLocalMetadata(O);
00496       } else if (isa<Instruction>(V) || isa<Argument>(V))
00497         EnumerateValue(V);
00498     }
00499 
00500   // Also, collect all function-local MDNodes for easy access.
00501   FunctionLocalMDs.push_back(N);
00502 }
00503 
00504 void ValueEnumerator::EnumerateValue(const Value *V) {
00505   assert(!V->getType()->isVoidTy() && "Can't insert void values!");
00506   assert(!isa<MDNode>(V) && !isa<MDString>(V) &&
00507          "EnumerateValue doesn't handle Metadata!");
00508 
00509   // Check to see if it's already in!
00510   unsigned &ValueID = ValueMap[V];
00511   if (ValueID) {
00512     // Increment use count.
00513     Values[ValueID-1].second++;
00514     return;
00515   }
00516 
00517   if (auto *GO = dyn_cast<GlobalObject>(V))
00518     if (const Comdat *C = GO->getComdat())
00519       Comdats.insert(C);
00520 
00521   // Enumerate the type of this value.
00522   EnumerateType(V->getType());
00523 
00524   if (const Constant *C = dyn_cast<Constant>(V)) {
00525     if (isa<GlobalValue>(C)) {
00526       // Initializers for globals are handled explicitly elsewhere.
00527     } else if (C->getNumOperands()) {
00528       // If a constant has operands, enumerate them.  This makes sure that if a
00529       // constant has uses (for example an array of const ints), that they are
00530       // inserted also.
00531 
00532       // We prefer to enumerate them with values before we enumerate the user
00533       // itself.  This makes it more likely that we can avoid forward references
00534       // in the reader.  We know that there can be no cycles in the constants
00535       // graph that don't go through a global variable.
00536       for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
00537            I != E; ++I)
00538         if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress.
00539           EnumerateValue(*I);
00540 
00541       // Finally, add the value.  Doing this could make the ValueID reference be
00542       // dangling, don't reuse it.
00543       Values.push_back(std::make_pair(V, 1U));
00544       ValueMap[V] = Values.size();
00545       return;
00546     }
00547   }
00548 
00549   // Add the value.
00550   Values.push_back(std::make_pair(V, 1U));
00551   ValueID = Values.size();
00552 }
00553 
00554 
00555 void ValueEnumerator::EnumerateType(Type *Ty) {
00556   unsigned *TypeID = &TypeMap[Ty];
00557 
00558   // We've already seen this type.
00559   if (*TypeID)
00560     return;
00561 
00562   // If it is a non-anonymous struct, mark the type as being visited so that we
00563   // don't recursively visit it.  This is safe because we allow forward
00564   // references of these in the bitcode reader.
00565   if (StructType *STy = dyn_cast<StructType>(Ty))
00566     if (!STy->isLiteral())
00567       *TypeID = ~0U;
00568 
00569   // Enumerate all of the subtypes before we enumerate this type.  This ensures
00570   // that the type will be enumerated in an order that can be directly built.
00571   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00572        I != E; ++I)
00573     EnumerateType(*I);
00574 
00575   // Refresh the TypeID pointer in case the table rehashed.
00576   TypeID = &TypeMap[Ty];
00577 
00578   // Check to see if we got the pointer another way.  This can happen when
00579   // enumerating recursive types that hit the base case deeper than they start.
00580   //
00581   // If this is actually a struct that we are treating as forward ref'able,
00582   // then emit the definition now that all of its contents are available.
00583   if (*TypeID && *TypeID != ~0U)
00584     return;
00585 
00586   // Add this type now that its contents are all happily enumerated.
00587   Types.push_back(Ty);
00588 
00589   *TypeID = Types.size();
00590 }
00591 
00592 // Enumerate the types for the specified value.  If the value is a constant,
00593 // walk through it, enumerating the types of the constant.
00594 void ValueEnumerator::EnumerateOperandType(const Value *V) {
00595   EnumerateType(V->getType());
00596 
00597   if (const Constant *C = dyn_cast<Constant>(V)) {
00598     // If this constant is already enumerated, ignore it, we know its type must
00599     // be enumerated.
00600     if (ValueMap.count(V)) return;
00601 
00602     // This constant may have operands, make sure to enumerate the types in
00603     // them.
00604     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
00605       const Value *Op = C->getOperand(i);
00606 
00607       // Don't enumerate basic blocks here, this happens as operands to
00608       // blockaddress.
00609       if (isa<BasicBlock>(Op)) continue;
00610 
00611       EnumerateOperandType(Op);
00612     }
00613 
00614     if (const MDNode *N = dyn_cast<MDNode>(V)) {
00615       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00616         if (Value *Elem = N->getOperand(i))
00617           EnumerateOperandType(Elem);
00618     }
00619   } else if (isa<MDString>(V) || isa<MDNode>(V))
00620     EnumerateMetadata(V);
00621 }
00622 
00623 void ValueEnumerator::EnumerateAttributes(AttributeSet PAL) {
00624   if (PAL.isEmpty()) return;  // null is always 0.
00625 
00626   // Do a lookup.
00627   unsigned &Entry = AttributeMap[PAL];
00628   if (Entry == 0) {
00629     // Never saw this before, add it.
00630     Attribute.push_back(PAL);
00631     Entry = Attribute.size();
00632   }
00633 
00634   // Do lookups for all attribute groups.
00635   for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) {
00636     AttributeSet AS = PAL.getSlotAttributes(i);
00637     unsigned &Entry = AttributeGroupMap[AS];
00638     if (Entry == 0) {
00639       AttributeGroups.push_back(AS);
00640       Entry = AttributeGroups.size();
00641     }
00642   }
00643 }
00644 
00645 void ValueEnumerator::incorporateFunction(const Function &F) {
00646   InstructionCount = 0;
00647   NumModuleValues = Values.size();
00648   NumModuleMDValues = MDValues.size();
00649 
00650   // Adding function arguments to the value table.
00651   for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end();
00652        I != E; ++I)
00653     EnumerateValue(I);
00654 
00655   FirstFuncConstantID = Values.size();
00656 
00657   // Add all function-level constants to the value table.
00658   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
00659     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
00660       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
00661            OI != E; ++OI) {
00662         if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
00663             isa<InlineAsm>(*OI))
00664           EnumerateValue(*OI);
00665       }
00666     BasicBlocks.push_back(BB);
00667     ValueMap[BB] = BasicBlocks.size();
00668   }
00669 
00670   // Optimize the constant layout.
00671   OptimizeConstants(FirstFuncConstantID, Values.size());
00672 
00673   // Add the function's parameter attributes so they are available for use in
00674   // the function's instruction.
00675   EnumerateAttributes(F.getAttributes());
00676 
00677   FirstInstID = Values.size();
00678 
00679   SmallVector<MDNode *, 8> FnLocalMDVector;
00680   // Add all of the instructions.
00681   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
00682     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
00683       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
00684            OI != E; ++OI) {
00685         if (MDNode *MD = dyn_cast<MDNode>(*OI))
00686           if (MD->isFunctionLocal() && MD->getFunction())
00687             // Enumerate metadata after the instructions they might refer to.
00688             FnLocalMDVector.push_back(MD);
00689       }
00690 
00691       SmallVector<std::pair<unsigned, MDNode*>, 8> MDs;
00692       I->getAllMetadataOtherThanDebugLoc(MDs);
00693       for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
00694         MDNode *N = MDs[i].second;
00695         if (N->isFunctionLocal() && N->getFunction())
00696           FnLocalMDVector.push_back(N);
00697       }
00698 
00699       if (!I->getType()->isVoidTy())
00700         EnumerateValue(I);
00701     }
00702   }
00703 
00704   // Add all of the function-local metadata.
00705   for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i)
00706     EnumerateFunctionLocalMetadata(FnLocalMDVector[i]);
00707 }
00708 
00709 void ValueEnumerator::purgeFunction() {
00710   /// Remove purged values from the ValueMap.
00711   for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i)
00712     ValueMap.erase(Values[i].first);
00713   for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i)
00714     MDValueMap.erase(MDValues[i].first);
00715   for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
00716     ValueMap.erase(BasicBlocks[i]);
00717 
00718   Values.resize(NumModuleValues);
00719   MDValues.resize(NumModuleMDValues);
00720   BasicBlocks.clear();
00721   FunctionLocalMDs.clear();
00722 }
00723 
00724 static void IncorporateFunctionInfoGlobalBBIDs(const Function *F,
00725                                  DenseMap<const BasicBlock*, unsigned> &IDMap) {
00726   unsigned Counter = 0;
00727   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00728     IDMap[BB] = ++Counter;
00729 }
00730 
00731 /// getGlobalBasicBlockID - This returns the function-specific ID for the
00732 /// specified basic block.  This is relatively expensive information, so it
00733 /// should only be used by rare constructs such as address-of-label.
00734 unsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const {
00735   unsigned &Idx = GlobalBasicBlockIDs[BB];
00736   if (Idx != 0)
00737     return Idx-1;
00738 
00739   IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs);
00740   return getGlobalBasicBlockID(BB);
00741 }
00742