1d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines//===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===// 2d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// 3d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// The LLVM Compiler Infrastructure 4d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// 5d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// This file is distributed under the University of Illinois Open Source 6d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// License. See LICENSE.TXT for details. 7d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// 8d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines//===----------------------------------------------------------------------===// 9d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// 10d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// This file implements the ValueEnumerator class. 11d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// 12d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines//===----------------------------------------------------------------------===// 13d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 14d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "ValueEnumerator.h" 15d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "llvm/ADT/STLExtras.h" 1623c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/ADT/SmallPtrSet.h" 1723c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/Constants.h" 1823c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/DerivedTypes.h" 1923c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/Instructions.h" 2023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/Module.h" 2123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/ValueSymbolTable.h" 22d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "llvm/Support/Debug.h" 23d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "llvm/Support/raw_ostream.h" 24d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include <algorithm> 25d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesusing namespace llvm; 26d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 27d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesnamespace llvm_3_2 { 28d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 290da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hinesstatic bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { 300da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines return V.first->getType()->isIntOrIntVectorTy(); 31d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 32d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 33d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// ValueEnumerator - Enumerate module-level information. 34d711dec946b6408791ca59eb98e363ef04bbd4aaStephen HinesValueEnumerator::ValueEnumerator(const Module *M) { 35d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the global variables. 36d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_global_iterator I = M->global_begin(), 37d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines E = M->global_end(); I != E; ++I) 38d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I); 39d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 40d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the functions. 41d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) { 42d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I); 43d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(cast<Function>(I)->getAttributes()); 44d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 45d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 46d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the aliases. 47d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 48d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 49d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I); 50d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 51d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Remember what is the cutoff between globalvalue's and other constants. 52d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned FirstConstant = Values.size(); 53d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 54d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the global variable initializers. 55d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_global_iterator I = M->global_begin(), 56d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines E = M->global_end(); I != E; ++I) 57d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (I->hasInitializer()) 58d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I->getInitializer()); 59d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 60d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the aliasees. 61d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end(); 62d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 63d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I->getAliasee()); 64d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 65d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Insert constants and metadata that are named at module level into the slot 66d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // pool so that the module symbol table can refer to them... 67d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValueSymbolTable(M->getValueSymbolTable()); 68d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateNamedMetadata(M); 69d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 70d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; 71d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 72d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate types used by function bodies and argument lists. 73d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) { 74d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 75d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); 76d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 77d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(I->getType()); 78d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 79d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 80d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){ 81d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 82d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OI != E; ++OI) { 83d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MDNode *MD = dyn_cast<MDNode>(*OI)) 84d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MD->isFunctionLocal() && MD->getFunction()) 85d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // These will get enumerated during function-incorporation. 86d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines continue; 87d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateOperandType(*OI); 88d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 89d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(I->getType()); 90d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (const CallInst *CI = dyn_cast<CallInst>(I)) 91d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(CI->getAttributes()); 92d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else if (const InvokeInst *II = dyn_cast<InvokeInst>(I)) 93d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(II->getAttributes()); 94d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 95d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate metadata attached with this instruction. 96d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDs.clear(); 97d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I->getAllMetadataOtherThanDebugLoc(MDs); 98d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = MDs.size(); i != e; ++i) 99d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(MDs[i].second); 10023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 101d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!I->getDebugLoc().isUnknown()) { 102d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDNode *Scope, *IA; 103d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I->getDebugLoc().getScopeAndInlinedAt(Scope, IA, I->getContext()); 104d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Scope) EnumerateMetadata(Scope); 105d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (IA) EnumerateMetadata(IA); 106d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 107d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 108d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 109d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 110d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Optimize constant ordering. 111d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OptimizeConstants(FirstConstant, Values.size()); 112d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 113d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 114d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { 115d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionMapType::const_iterator I = InstructionMap.find(Inst); 116d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(I != InstructionMap.end() && "Instruction is not mapped!"); 117d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return I->second; 118d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 119d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 120d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::setInstructionID(const Instruction *I) { 121d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionMap[I] = InstructionCount++; 122d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 123d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 124d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getValueID(const Value *V) const { 125d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (isa<MDNode>(V) || isa<MDString>(V)) { 126d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMapType::const_iterator I = MDValueMap.find(V); 127d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(I != MDValueMap.end() && "Value not in slotcalculator!"); 128d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return I->second-1; 129d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 130d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 131d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMapType::const_iterator I = ValueMap.find(V); 132d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(I != ValueMap.end() && "Value not in slotcalculator!"); 133d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return I->second-1; 134d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 135d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 136d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::dump() const { 137d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines print(dbgs(), ValueMap, "Default"); 138d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines dbgs() << '\n'; 139d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines print(dbgs(), MDValueMap, "MetaData"); 140d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines dbgs() << '\n'; 141d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 142d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 143d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, 144d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const char *Name) const { 145d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 146d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Map Name: " << Name << "\n"; 147d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Size: " << Map.size() << "\n"; 148d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (ValueMapType::const_iterator I = Map.begin(), 149d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines E = Map.end(); I != E; ++I) { 150d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 151d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const Value *V = I->first; 152d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (V->hasName()) 153d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Value: " << V->getName(); 154d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else 155d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Value: [null]\n"; 156d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines V->dump(); 157d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 158d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):"; 159d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end(); 160d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines UI != UE; ++UI) { 161d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (UI != V->use_begin()) 162d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << ","; 163d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if((*UI)->hasName()) 164d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << " " << (*UI)->getName(); 165d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else 166d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << " [null]"; 167d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 168d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 169d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "\n\n"; 170d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 171d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 172d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 173d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// Optimize constant ordering. 174d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesnamespace { 175d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines struct CstSortPredicate { 176d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueEnumerator &VE; 177d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} 178d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines bool operator()(const std::pair<const Value*, unsigned> &LHS, 179d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const std::pair<const Value*, unsigned> &RHS) { 180d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Sort by plane. 181d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (LHS.first->getType() != RHS.first->getType()) 182d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return VE.getTypeID(LHS.first->getType()) < 183d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines VE.getTypeID(RHS.first->getType()); 184d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Then by frequency. 185d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return LHS.second > RHS.second; 186d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 187d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines }; 188d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 189d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 190d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// OptimizeConstants - Reorder constant pool for denser encoding. 191d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 192d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 193d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 194d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines CstSortPredicate P(*this); 195d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); 196d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 1970da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // Ensure that integer and vector of integer constants are at the start of the 1980da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // constant pool. This is important so that GEP structure indices come before 1990da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // gep constant exprs. 200d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, 2010da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines isIntOrIntVectorValue); 202d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 203d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Rebuild the modified portion of ValueMap. 204d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (; CstStart != CstEnd; ++CstStart) 205d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap[Values[CstStart].first] = CstStart+1; 206d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 207d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 208d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 209d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 210d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// table into the values table. 211d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 212d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 213d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines VI != VE; ++VI) 214d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(VI->getValue()); 215d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 216d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 217d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateNamedMetadata - Insert all of the values referenced by 218d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// named metadata in the specified module. 219d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateNamedMetadata(const Module *M) { 220d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Module::const_named_metadata_iterator I = M->named_metadata_begin(), 221d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines E = M->named_metadata_end(); I != E; ++I) 222d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateNamedMDNode(I); 223d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 224d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 225d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { 226d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) 227d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(MD->getOperand(i)); 228d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 229d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 230d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateMDNodeOperands - Enumerate all non-function-local values 231d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// and types referenced by the given MDNode. 232d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { 233d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 234d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Value *V = N->getOperand(i)) { 235d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (isa<MDNode>(V) || isa<MDString>(V)) 236d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(V); 237d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else if (!isa<Instruction>(V) && !isa<Argument>(V)) 238d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(V); 239d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } else 240d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(Type::getVoidTy(N->getContext())); 241d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 242d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 243d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 244d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateMetadata(const Value *MD) { 245d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert((isa<MDNode>(MD) || isa<MDString>(MD)) && "Invalid metadata kind"); 246d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 247d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the type of this value. 248d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(MD->getType()); 249d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 250d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const MDNode *N = dyn_cast<MDNode>(MD); 251d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 252d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // In the module-level pass, skip function-local nodes themselves, but 253d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // do walk their operands. 254d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (N && N->isFunctionLocal() && N->getFunction()) { 255d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMDNodeOperands(N); 256d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 257d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 258d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 259d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if it's already in! 260d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &MDValueID = MDValueMap[MD]; 261d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MDValueID) { 262d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Increment use count. 263d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValues[MDValueID-1].second++; 264d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 265d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 266d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValues.push_back(std::make_pair(MD, 1U)); 267d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValueID = MDValues.size(); 268d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 269d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate all non-function-local operands. 270d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (N) 271d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMDNodeOperands(N); 272d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 273d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 274d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata 275d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// information reachable from the given MDNode. 276d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateFunctionLocalMetadata(const MDNode *N) { 277d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(N->isFunctionLocal() && N->getFunction() && 278d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines "EnumerateFunctionLocalMetadata called on non-function-local mdnode!"); 279d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 280d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the type of this value. 281d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(N->getType()); 282d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 283d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if it's already in! 284d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &MDValueID = MDValueMap[N]; 285d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MDValueID) { 286d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Increment use count. 287d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValues[MDValueID-1].second++; 288d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 289d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 290d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValues.push_back(std::make_pair(N, 1U)); 291d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValueID = MDValues.size(); 292d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 293d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // To incoroporate function-local information visit all function-local 294d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // MDNodes and all function-local values they reference. 295d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 296d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Value *V = N->getOperand(i)) { 297d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MDNode *O = dyn_cast<MDNode>(V)) { 298d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (O->isFunctionLocal() && O->getFunction()) 299d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateFunctionLocalMetadata(O); 300d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } else if (isa<Instruction>(V) || isa<Argument>(V)) 301d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(V); 302d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 303d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 304d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Also, collect all function-local MDNodes for easy access. 305d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FunctionLocalMDs.push_back(N); 306d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 307d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 308d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateValue(const Value *V) { 309d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(!V->getType()->isVoidTy() && "Can't insert void values!"); 310d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(!isa<MDNode>(V) && !isa<MDString>(V) && 311d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines "EnumerateValue doesn't handle Metadata!"); 312d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 313d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if it's already in! 314d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &ValueID = ValueMap[V]; 315d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (ValueID) { 316d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Increment use count. 317d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values[ValueID-1].second++; 318d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 319d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 320d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 321d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the type of this value. 322d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(V->getType()); 323d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 324d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (const Constant *C = dyn_cast<Constant>(V)) { 325d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (isa<GlobalValue>(C)) { 326d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Initializers for globals are handled explicitly elsewhere. 327d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } else if (C->getNumOperands()) { 328d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If a constant has operands, enumerate them. This makes sure that if a 329d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // constant has uses (for example an array of const ints), that they are 330d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // inserted also. 331d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 332d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // We prefer to enumerate them with values before we enumerate the user 333d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // itself. This makes it more likely that we can avoid forward references 334d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // in the reader. We know that there can be no cycles in the constants 335d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // graph that don't go through a global variable. 336d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 337d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 338d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. 339d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(*I); 340d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 341d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Finally, add the value. Doing this could make the ValueID reference be 342d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // dangling, don't reuse it. 343d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.push_back(std::make_pair(V, 1U)); 344d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap[V] = Values.size(); 345d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 34699d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines } else if (const ConstantDataSequential *CDS = 34799d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines dyn_cast<ConstantDataSequential>(C)) { 34899d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // For our legacy handling of the new ConstantDataSequential type, we 34999d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // need to enumerate the individual elements, as well as mark the 35099d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // outer constant as used. 35199d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) 35299d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines EnumerateValue(CDS->getElementAsConstant(i)); 35399d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines Values.push_back(std::make_pair(V, 1U)); 35499d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines ValueMap[V] = Values.size(); 35599d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines return; 356d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 357d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 358d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 359d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add the value. 360d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.push_back(std::make_pair(V, 1U)); 361d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueID = Values.size(); 362d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 363d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 364d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 365d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateType(Type *Ty) { 366d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned *TypeID = &TypeMap[Ty]; 367d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 368d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // We've already seen this type. 369d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (*TypeID) 370d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 371d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 372d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If it is a non-anonymous struct, mark the type as being visited so that we 373d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // don't recursively visit it. This is safe because we allow forward 374d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // references of these in the bitcode reader. 375d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (StructType *STy = dyn_cast<StructType>(Ty)) 376d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!STy->isLiteral()) 377d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines *TypeID = ~0U; 37823c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 379d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate all of the subtypes before we enumerate this type. This ensures 380d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // that the type will be enumerated in an order that can be directly built. 381d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 382d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 383d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(*I); 38423c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 385d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Refresh the TypeID pointer in case the table rehashed. 386d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines TypeID = &TypeMap[Ty]; 38723c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 388d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if we got the pointer another way. This can happen when 389d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // enumerating recursive types that hit the base case deeper than they start. 390d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // 391d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If this is actually a struct that we are treating as forward ref'able, 392d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // then emit the definition now that all of its contents are available. 393d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (*TypeID && *TypeID != ~0U) 394d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 39523c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 396d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add this type now that its contents are all happily enumerated. 397d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Types.push_back(Ty); 39823c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 399d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines *TypeID = Types.size(); 400d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 401d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 402d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// Enumerate the types for the specified value. If the value is a constant, 403d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// walk through it, enumerating the types of the constant. 404d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateOperandType(const Value *V) { 405d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(V->getType()); 40623c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 407d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (const Constant *C = dyn_cast<Constant>(V)) { 408d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If this constant is already enumerated, ignore it, we know its type must 409d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // be enumerated. 410d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (ValueMap.count(V)) return; 411d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 412d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // This constant may have operands, make sure to enumerate the types in 413d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // them. 414d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 415d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const Value *Op = C->getOperand(i); 41623c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 417d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Don't enumerate basic blocks here, this happens as operands to 418d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // blockaddress. 419d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (isa<BasicBlock>(Op)) continue; 42023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 421d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateOperandType(Op); 422d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 423d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 424d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (const MDNode *N = dyn_cast<MDNode>(V)) { 425d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 426d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Value *Elem = N->getOperand(i)) 427d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateOperandType(Elem); 428d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 429d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } else if (isa<MDString>(V) || isa<MDNode>(V)) 430d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(V); 431d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 432d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 4330da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hinesvoid ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { 434d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (PAL.isEmpty()) return; // null is always 0. 4350da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines 436d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Do a lookup. 4370da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines unsigned &Entry = AttributeMap[PAL]; 438d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Entry == 0) { 439d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Never saw this before, add it. 44023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines Attribute.push_back(PAL); 44123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines Entry = Attribute.size(); 442d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 4430da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines 4440da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // Do lookups for all attribute groups. 4450da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) { 4460da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines AttributeSet AS = PAL.getSlotAttributes(i); 4470da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines unsigned &Entry = AttributeGroupMap[AS]; 4480da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines if (Entry == 0) { 4490da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines AttributeGroups.push_back(AS); 4500da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines Entry = AttributeGroups.size(); 4510da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines } 4520da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines } 453d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 454d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 455d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::incorporateFunction(const Function &F) { 456d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionCount = 0; 457d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines NumModuleValues = Values.size(); 458d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines NumModuleMDValues = MDValues.size(); 459d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 460d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Adding function arguments to the value table. 461d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 462d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 463d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I); 464d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 465d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FirstFuncConstantID = Values.size(); 466d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 467d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all function-level constants to the value table. 468d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 469d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 470d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 471d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OI != E; ++OI) { 472d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 473d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines isa<InlineAsm>(*OI)) 474d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(*OI); 475d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 476d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines BasicBlocks.push_back(BB); 477d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap[BB] = BasicBlocks.size(); 478d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 479d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 480d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Optimize the constant layout. 481d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OptimizeConstants(FirstFuncConstantID, Values.size()); 482d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 483d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add the function's parameter attributes so they are available for use in 484d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // the function's instruction. 485d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(F.getAttributes()); 486d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 487d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FirstInstID = Values.size(); 488d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 489d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines SmallVector<MDNode *, 8> FnLocalMDVector; 490d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all of the instructions. 491d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 492d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 493d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 494d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OI != E; ++OI) { 495d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MDNode *MD = dyn_cast<MDNode>(*OI)) 496d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (MD->isFunctionLocal() && MD->getFunction()) 497d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate metadata after the instructions they might refer to. 498d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FnLocalMDVector.push_back(MD); 499d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 500d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 501d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines SmallVector<std::pair<unsigned, MDNode*>, 8> MDs; 502d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I->getAllMetadataOtherThanDebugLoc(MDs); 503d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = MDs.size(); i != e; ++i) { 504d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDNode *N = MDs[i].second; 505d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (N->isFunctionLocal() && N->getFunction()) 506d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FnLocalMDVector.push_back(N); 507d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 50823c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 509d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!I->getType()->isVoidTy()) 510d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I); 511d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 512d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 513d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 514d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all of the function-local metadata. 515d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) 516d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateFunctionLocalMetadata(FnLocalMDVector[i]); 517d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 518d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 519d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::purgeFunction() { 520d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines /// Remove purged values from the ValueMap. 521d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 522d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap.erase(Values[i].first); 523d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = NumModuleMDValues, e = MDValues.size(); i != e; ++i) 524d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValueMap.erase(MDValues[i].first); 525d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 526d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap.erase(BasicBlocks[i]); 527d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 528d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.resize(NumModuleValues); 529d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDValues.resize(NumModuleMDValues); 530d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines BasicBlocks.clear(); 531d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FunctionLocalMDs.clear(); 532d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 533d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 534d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesstatic void IncorporateFunctionInfoGlobalBBIDs(const Function *F, 535d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines DenseMap<const BasicBlock*, unsigned> &IDMap) { 536d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned Counter = 0; 537d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 538d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines IDMap[BB] = ++Counter; 539d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 540d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 541d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// getGlobalBasicBlockID - This returns the function-specific ID for the 542d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// specified basic block. This is relatively expensive information, so it 543d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// should only be used by rare constructs such as address-of-label. 544d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { 545d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &Idx = GlobalBasicBlockIDs[BB]; 546d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Idx != 0) 547d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return Idx-1; 548d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 549d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); 550d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return getGlobalBasicBlockID(BB); 551d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 552d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 553d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} // end llvm_3_2 namespace 554