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" 18c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines#include "llvm/IR/DebugInfoMetadata.h" 1923c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/DerivedTypes.h" 2023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/Instructions.h" 2123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/Module.h" 2223c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines#include "llvm/IR/ValueSymbolTable.h" 23d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "llvm/Support/Debug.h" 24d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include "llvm/Support/raw_ostream.h" 25d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines#include <algorithm> 26d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesusing namespace llvm; 27d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 28d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesnamespace llvm_3_2 { 29d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 300da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hinesstatic bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) { 310da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines return V.first->getType()->isIntOrIntVectorTy(); 32d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 33d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 34d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// ValueEnumerator - Enumerate module-level information. 35c706907a8041faaa882f9bd87f1d1c1669023a62Stephen HinesValueEnumerator::ValueEnumerator(const llvm::Module &M) 361906a00dce8e32fe3bb8a957e333ebbbee0888e3Pirama Arumuga Nainar : HasMDString(false), HasDILocation(false) { 37d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the global variables. 38c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_global_iterator I = M.global_begin(), E = M.global_end(); 39c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines I != E; ++I) 4098cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateValue(&*I); 41d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 42d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the functions. 43c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I) { 4498cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateValue(&*I); 45d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(cast<Function>(I)->getAttributes()); 46d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 47d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 48d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the aliases. 49c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); 50d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 5198cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateValue(&*I); 52d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 53d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Remember what is the cutoff between globalvalue's and other constants. 54d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned FirstConstant = Values.size(); 55d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 56d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the global variable initializers. 57c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_global_iterator I = M.global_begin(), E = M.global_end(); 58c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines I != E; ++I) 59d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (I->hasInitializer()) 60d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I->getInitializer()); 61d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 62d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the aliasees. 63c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_alias_iterator I = M.alias_begin(), E = M.alias_end(); 64d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 65d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(I->getAliasee()); 66d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 67c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Enumerate the metadata type. 68c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // 69c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // TODO: Move this to ValueEnumerator::EnumerateOperandType() once bitcode 70c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // only encodes the metadata type when it's used as a value. 71c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateType(Type::getMetadataTy(M.getContext())); 72c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 73c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Insert constants and metadata that are named at module level into the slot 74d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // pool so that the module symbol table can refer to them... 75c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateValueSymbolTable(M.getValueSymbolTable()); 76d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateNamedMetadata(M); 77d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 78c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines SmallVector<std::pair<unsigned, MDNode *>, 8> MDs; 79d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 80d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate types used by function bodies and argument lists. 81c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const Function &F : M) { 82c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const Argument &A : F.args()) 83c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateType(A.getType()); 84c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 85c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const BasicBlock &BB : F) 86c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const Instruction &I : BB) { 87c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const Use &Op : I.operands()) { 88c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines auto *MD = dyn_cast<MetadataAsValue>(&Op); 89c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (!MD) { 90c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateOperandType(Op); 91c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines continue; 92c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines } 93c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 94c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Local metadata is enumerated during function-incorporation. 95c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (isa<LocalAsMetadata>(MD->getMetadata())) 96c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines continue; 97c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 98c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateMetadata(MD->getMetadata()); 99d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 100c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateType(I.getType()); 101c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (const CallInst *CI = dyn_cast<CallInst>(&I)) 102d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(CI->getAttributes()); 103c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) 104d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(II->getAttributes()); 105d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 106d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate metadata attached with this instruction. 107d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines MDs.clear(); 108c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines I.getAllMetadataOtherThanDebugLoc(MDs); 109d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = MDs.size(); i != e; ++i) 110d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(MDs[i].second); 11123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 11221cc01860b95cad7ae60c686e511e8f4ae034e39Pirama Arumuga Nainar // Don't enumerate the location directly -- it has a special record 11321cc01860b95cad7ae60c686e511e8f4ae034e39Pirama Arumuga Nainar // type -- but enumerate its operands. 1141906a00dce8e32fe3bb8a957e333ebbbee0888e3Pirama Arumuga Nainar if (DILocation *L = I.getDebugLoc()) 11521cc01860b95cad7ae60c686e511e8f4ae034e39Pirama Arumuga Nainar EnumerateMDNodeOperands(L); 116d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 117d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 118d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 119d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Optimize constant ordering. 120d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OptimizeConstants(FirstConstant, Values.size()); 121d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 122d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 123d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getInstructionID(const Instruction *Inst) const { 124d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionMapType::const_iterator I = InstructionMap.find(Inst); 125d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(I != InstructionMap.end() && "Instruction is not mapped!"); 126d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return I->second; 127d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 128d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 129d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::setInstructionID(const Instruction *I) { 130d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionMap[I] = InstructionCount++; 131d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 132d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 133d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getValueID(const Value *V) const { 134c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (auto *MD = dyn_cast<MetadataAsValue>(V)) 135c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines return getMetadataID(MD->getMetadata()); 136d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 137d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMapType::const_iterator I = ValueMap.find(V); 138d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(I != ValueMap.end() && "Value not in slotcalculator!"); 139d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return I->second-1; 140d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 141d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 142d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::dump() const { 143d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines print(dbgs(), ValueMap, "Default"); 144d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines dbgs() << '\n'; 145d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines print(dbgs(), MDValueMap, "MetaData"); 146d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines dbgs() << '\n'; 147d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 148d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 149d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map, 150d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const char *Name) const { 151d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 152d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Map Name: " << Name << "\n"; 153d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Size: " << Map.size() << "\n"; 154d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (ValueMapType::const_iterator I = Map.begin(), 155d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines E = Map.end(); I != E; ++I) { 156d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 157d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const Value *V = I->first; 158d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (V->hasName()) 159d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Value: " << V->getName(); 160d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else 161d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "Value: [null]\n"; 162d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines V->dump(); 163d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 164d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):"; 165c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (const Use &U : V->uses()) { 166c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (&U != &*V->use_begin()) 167d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << ","; 168c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if(U->hasName()) 169c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines OS << " " << U->getName(); 170d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines else 171d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << " [null]"; 172d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 173d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 174d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OS << "\n\n"; 175d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 176d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 177d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 178c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hinesvoid ValueEnumerator::print(llvm::raw_ostream &OS, const MetadataMapType &Map, 179c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines const char *Name) const { 180c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 181c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines OS << "Map Name: " << Name << "\n"; 182c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines OS << "Size: " << Map.size() << "\n"; 183c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (auto I = Map.begin(), E = Map.end(); I != E; ++I) { 184c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines const llvm::Metadata *MD = I->first; 185c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines OS << "Metadata: slot = " << I->second << "\n"; 186c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MD->print(OS); 187c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines } 188c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines} 189c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 190c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 191d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// Optimize constant ordering. 192d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesnamespace { 193d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines struct CstSortPredicate { 194d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueEnumerator &VE; 195d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines explicit CstSortPredicate(ValueEnumerator &ve) : VE(ve) {} 196d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines bool operator()(const std::pair<const Value*, unsigned> &LHS, 197d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines const std::pair<const Value*, unsigned> &RHS) { 198d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Sort by plane. 199d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (LHS.first->getType() != RHS.first->getType()) 200d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return VE.getTypeID(LHS.first->getType()) < 201d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines VE.getTypeID(RHS.first->getType()); 202d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Then by frequency. 203d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return LHS.second > RHS.second; 204d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 205d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines }; 206d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 207d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 208d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// OptimizeConstants - Reorder constant pool for denser encoding. 209d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::OptimizeConstants(unsigned CstStart, unsigned CstEnd) { 210d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (CstStart == CstEnd || CstStart+1 == CstEnd) return; 211d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 212d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines CstSortPredicate P(*this); 213d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines std::stable_sort(Values.begin()+CstStart, Values.begin()+CstEnd, P); 214d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 2150da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // Ensure that integer and vector of integer constants are at the start of the 2160da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // constant pool. This is important so that GEP structure indices come before 2170da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // gep constant exprs. 218d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines std::partition(Values.begin()+CstStart, Values.begin()+CstEnd, 2190da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines isIntOrIntVectorValue); 220d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 221d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Rebuild the modified portion of ValueMap. 222d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (; CstStart != CstEnd; ++CstStart) 223d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap[Values[CstStart].first] = CstStart+1; 224d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 225d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 226d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 227d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateValueSymbolTable - Insert all of the values in the specified symbol 228d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// table into the values table. 229d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) { 230d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end(); 231d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines VI != VE; ++VI) 232d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(VI->getValue()); 233d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 234d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 235d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateNamedMetadata - Insert all of the values referenced by 236d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// named metadata in the specified module. 237c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hinesvoid ValueEnumerator::EnumerateNamedMetadata(const llvm::Module &M) { 238c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (llvm::Module::const_named_metadata_iterator I = M.named_metadata_begin(), 239c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines E = M.named_metadata_end(); 240c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines I != E; ++I) 24198cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateNamedMDNode(&*I); 242d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 243d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 244d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateNamedMDNode(const NamedMDNode *MD) { 245d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) 246d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMetadata(MD->getOperand(i)); 247d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 248d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 249d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateMDNodeOperands - Enumerate all non-function-local values 250d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// and types referenced by the given MDNode. 251d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateMDNodeOperands(const MDNode *N) { 252d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 253c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines Metadata *MD = N->getOperand(i); 254c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (!MD) 255c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines continue; 256c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines assert(!isa<LocalAsMetadata>(MD) && "MDNodes cannot be function-local"); 257c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateMetadata(MD); 258d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 259d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 260d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 261c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hinesvoid ValueEnumerator::EnumerateMetadata(const llvm::Metadata *MD) { 262c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines assert( 263c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines (isa<MDNode>(MD) || isa<MDString>(MD) || isa<ConstantAsMetadata>(MD)) && 264c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines "Invalid metadata kind"); 265d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 266c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Insert a dummy ID to block the co-recursive call to 267c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // EnumerateMDNodeOperands() from re-visiting MD in a cyclic graph. 268c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // 269c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Return early if there's already an ID. 270c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (!MDValueMap.insert(std::make_pair(MD, 0)).second) 271c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines return; 272d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 273c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Visit operands first to minimize RAUW. 274c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (auto *N = dyn_cast<MDNode>(MD)) 275d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateMDNodeOperands(N); 276c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines else if (auto *C = dyn_cast<ConstantAsMetadata>(MD)) 277c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateValue(C->getValue()); 278d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 279c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines HasMDString |= isa<MDString>(MD); 2801906a00dce8e32fe3bb8a957e333ebbbee0888e3Pirama Arumuga Nainar HasDILocation |= isa<DILocation>(MD); 281d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 282c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Replace the dummy ID inserted above with the correct one. MDValueMap may 283c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // have changed by inserting operands, so we need a fresh lookup here. 284c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDs.push_back(MD); 285c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDValueMap[MD] = MDs.size(); 286d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 287d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 288d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// EnumerateFunctionLocalMetadataa - Incorporate function-local metadata 289c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines/// information reachable from the metadata. 290c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hinesvoid ValueEnumerator::EnumerateFunctionLocalMetadata( 291c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines const llvm::LocalAsMetadata *Local) { 292d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if it's already in! 293c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines unsigned &MDValueID = MDValueMap[Local]; 294c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (MDValueID) 295d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 296d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 297c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDs.push_back(Local); 298c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDValueID = MDs.size(); 299c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 300c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateValue(Local->getValue()); 301c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 302c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Also, collect all function-local metadata for easy access. 303c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines FunctionLocalMDs.push_back(Local); 304d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 305d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 306d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateValue(const Value *V) { 307d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines assert(!V->getType()->isVoidTy() && "Can't insert void values!"); 308c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines assert(!isa<MetadataAsValue>(V) && "EnumerateValue doesn't handle Metadata!"); 309d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 310d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if it's already in! 311d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &ValueID = ValueMap[V]; 312d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (ValueID) { 313d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Increment use count. 314d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values[ValueID-1].second++; 315d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 316d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 317d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 318d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate the type of this value. 319d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(V->getType()); 320d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 321d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (const Constant *C = dyn_cast<Constant>(V)) { 322d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (isa<GlobalValue>(C)) { 323d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Initializers for globals are handled explicitly elsewhere. 324d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } else if (C->getNumOperands()) { 325d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If a constant has operands, enumerate them. This makes sure that if a 326d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // constant has uses (for example an array of const ints), that they are 327d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // inserted also. 328d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 329d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // We prefer to enumerate them with values before we enumerate the user 330d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // itself. This makes it more likely that we can avoid forward references 331d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // in the reader. We know that there can be no cycles in the constants 332d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // graph that don't go through a global variable. 333d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator I = C->op_begin(), E = C->op_end(); 334d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 335d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!isa<BasicBlock>(*I)) // Don't enumerate BB operand to BlockAddress. 336d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(*I); 337d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 338d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Finally, add the value. Doing this could make the ValueID reference be 339d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // dangling, don't reuse it. 340d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.push_back(std::make_pair(V, 1U)); 341d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap[V] = Values.size(); 342d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 34399d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines } else if (const ConstantDataSequential *CDS = 34499d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines dyn_cast<ConstantDataSequential>(C)) { 34599d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // For our legacy handling of the new ConstantDataSequential type, we 34699d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // need to enumerate the individual elements, as well as mark the 34799d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines // outer constant as used. 34899d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) 34999d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines EnumerateValue(CDS->getElementAsConstant(i)); 35099d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines Values.push_back(std::make_pair(V, 1U)); 35199d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines ValueMap[V] = Values.size(); 35299d429070eb7c4c39fb7d74555031d518a4e0a79Stephen Hines return; 353d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 354d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 355d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 356d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add the value. 357d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.push_back(std::make_pair(V, 1U)); 358d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueID = Values.size(); 359d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 360d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 361d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 362d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateType(Type *Ty) { 363d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned *TypeID = &TypeMap[Ty]; 364d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 365d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // We've already seen this type. 366d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (*TypeID) 367d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 368d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 369d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If it is a non-anonymous struct, mark the type as being visited so that we 370d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // don't recursively visit it. This is safe because we allow forward 371d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // references of these in the bitcode reader. 372d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (StructType *STy = dyn_cast<StructType>(Ty)) 373d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!STy->isLiteral()) 374d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines *TypeID = ~0U; 37523c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 376d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate all of the subtypes before we enumerate this type. This ensures 377d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // that the type will be enumerated in an order that can be directly built. 378c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (Type *SubTy : Ty->subtypes()) 379c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateType(SubTy); 38023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 381d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Refresh the TypeID pointer in case the table rehashed. 382d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines TypeID = &TypeMap[Ty]; 38323c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 384d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Check to see if we got the pointer another way. This can happen when 385d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // enumerating recursive types that hit the base case deeper than they start. 386d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // 387d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // If this is actually a struct that we are treating as forward ref'able, 388d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // then emit the definition now that all of its contents are available. 389d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (*TypeID && *TypeID != ~0U) 390d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return; 39123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 392d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add this type now that its contents are all happily enumerated. 393d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Types.push_back(Ty); 39423c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 395d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines *TypeID = Types.size(); 396d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 397d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 398d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// Enumerate the types for the specified value. If the value is a constant, 399d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines// walk through it, enumerating the types of the constant. 400d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::EnumerateOperandType(const Value *V) { 401d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateType(V->getType()); 40223c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 403c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (auto *MD = dyn_cast<MetadataAsValue>(V)) { 404c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines assert(!isa<LocalAsMetadata>(MD->getMetadata()) && 405c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines "Function-local metadata should be left for later"); 406d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 407c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateMetadata(MD->getMetadata()); 408c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines return; 409c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines } 41023c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 411c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines const Constant *C = dyn_cast<Constant>(V); 412c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (!C) 413c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines return; 41423c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 415c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // If this constant is already enumerated, ignore it, we know its type must 416c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // be enumerated. 417c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (ValueMap.count(C)) 418c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines return; 419d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 420c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // This constant may have operands, make sure to enumerate the types in 421c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // them. 422c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { 423c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines const Value *Op = C->getOperand(i); 424c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 425c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // Don't enumerate basic blocks here, this happens as operands to 426c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines // blockaddress. 427c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (isa<BasicBlock>(Op)) 428c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines continue; 429c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines 430c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines EnumerateOperandType(Op); 431c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines } 432d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 433d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 4340da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hinesvoid ValueEnumerator::EnumerateAttributes(AttributeSet PAL) { 435d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (PAL.isEmpty()) return; // null is always 0. 4360da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines 437d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Do a lookup. 4380da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines unsigned &Entry = AttributeMap[PAL]; 439d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Entry == 0) { 440d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Never saw this before, add it. 44123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines Attribute.push_back(PAL); 44223c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines Entry = Attribute.size(); 443d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 4440da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines 4450da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines // Do lookups for all attribute groups. 4460da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines for (unsigned i = 0, e = PAL.getNumSlots(); i != e; ++i) { 4470da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines AttributeSet AS = PAL.getSlotAttributes(i); 4480da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines unsigned &Entry = AttributeGroupMap[AS]; 4490da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines if (Entry == 0) { 4500da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines AttributeGroups.push_back(AS); 4510da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines Entry = AttributeGroups.size(); 4520da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines } 4530da7f6c8201b27938d3b9f048d71fd784cd1df9aStephen Hines } 454d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 455d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 456d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::incorporateFunction(const Function &F) { 457d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines InstructionCount = 0; 458d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines NumModuleValues = Values.size(); 459c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines NumModuleMDs = MDs.size(); 460d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 461d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Adding function arguments to the value table. 462d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); 463d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines I != E; ++I) 46498cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateValue(&*I); 465d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 466d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FirstFuncConstantID = Values.size(); 467d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 468d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all function-level constants to the value table. 469d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 470d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) 471d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 472d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OI != E; ++OI) { 473d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) || 474d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines isa<InlineAsm>(*OI)) 475d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateValue(*OI); 476d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 47798cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar BasicBlocks.push_back(&*BB); 47898cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar ValueMap[&*BB] = BasicBlocks.size(); 479d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 480d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 481d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Optimize the constant layout. 482d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OptimizeConstants(FirstFuncConstantID, Values.size()); 483d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 484d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add the function's parameter attributes so they are available for use in 485d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // the function's instruction. 486d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateAttributes(F.getAttributes()); 487d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 488d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FirstInstID = Values.size(); 489d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 490c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines SmallVector<llvm::LocalAsMetadata *, 8> FnLocalMDVector; 491d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all of the instructions. 492d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 493d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) { 494d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 495d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines OI != E; ++OI) { 496c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (auto *MD = dyn_cast<llvm::MetadataAsValue>(&*OI)) 497c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines if (auto *Local = dyn_cast<LocalAsMetadata>(MD->getMetadata())) 498d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Enumerate metadata after the instructions they might refer to. 499c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines FnLocalMDVector.push_back(Local); 500d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 50123c4358f12bd9d0ba7166eceebd683db95a41b3fStephen Hines 502d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (!I->getType()->isVoidTy()) 50398cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar EnumerateValue(&*I); 504d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 505d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines } 506d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 507d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines // Add all of the function-local metadata. 508d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = FnLocalMDVector.size(); i != e; ++i) 509d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines EnumerateFunctionLocalMetadata(FnLocalMDVector[i]); 510d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 511d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 512d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesvoid ValueEnumerator::purgeFunction() { 513d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines /// Remove purged values from the ValueMap. 514d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = NumModuleValues, e = Values.size(); i != e; ++i) 515d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap.erase(Values[i].first); 516c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines for (unsigned i = NumModuleMDs, e = MDs.size(); i != e; ++i) 517c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDValueMap.erase(MDs[i]); 518d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i) 519d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines ValueMap.erase(BasicBlocks[i]); 520d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 521d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines Values.resize(NumModuleValues); 522c706907a8041faaa882f9bd87f1d1c1669023a62Stephen Hines MDs.resize(NumModuleMDs); 523d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines BasicBlocks.clear(); 524d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines FunctionLocalMDs.clear(); 525d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 526d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 527d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesstatic void IncorporateFunctionInfoGlobalBBIDs(const Function *F, 528d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines DenseMap<const BasicBlock*, unsigned> &IDMap) { 529d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned Counter = 0; 530d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 53198cfae456bb1831336bce2b21979a04e2e31fed4Pirama Arumuga Nainar IDMap[&*BB] = ++Counter; 532d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 533d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 534d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// getGlobalBasicBlockID - This returns the function-specific ID for the 535d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// specified basic block. This is relatively expensive information, so it 536d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines/// should only be used by rare constructs such as address-of-label. 537d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hinesunsigned ValueEnumerator::getGlobalBasicBlockID(const BasicBlock *BB) const { 538d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines unsigned &Idx = GlobalBasicBlockIDs[BB]; 539d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines if (Idx != 0) 540d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return Idx-1; 541d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 542d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines IncorporateFunctionInfoGlobalBBIDs(BB->getParent(), GlobalBasicBlockIDs); 543d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines return getGlobalBasicBlockID(BB); 544d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} 545d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines 546d711dec946b6408791ca59eb98e363ef04bbd4aaStephen Hines} // end llvm_3_2 namespace 547