TypeFinder.cpp revision 263508
1231200Smm//===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===// 2231200Smm// 3231200Smm// The LLVM Compiler Infrastructure 4231200Smm// 5231200Smm// This file is distributed under the University of Illinois Open Source 6231200Smm// License. See LICENSE.TXT for details. 7231200Smm// 8231200Smm//===----------------------------------------------------------------------===// 9231200Smm// 10231200Smm// This file implements the TypeFinder class for the IR library. 11231200Smm// 12231200Smm//===----------------------------------------------------------------------===// 13231200Smm 14231200Smm#include "llvm/IR/TypeFinder.h" 15231200Smm#include "llvm/ADT/SmallVector.h" 16231200Smm#include "llvm/IR/BasicBlock.h" 17231200Smm#include "llvm/IR/DerivedTypes.h" 18231200Smm#include "llvm/IR/Function.h" 19231200Smm#include "llvm/IR/Metadata.h" 20231200Smm#include "llvm/IR/Module.h" 21231200Smmusing namespace llvm; 22231200Smm 23231200Smmvoid TypeFinder::run(const Module &M, bool onlyNamed) { 24231200Smm OnlyNamed = onlyNamed; 25238856Smm 26231200Smm // Get types from global variables. 27358090Smm for (Module::const_global_iterator I = M.global_begin(), 28231200Smm E = M.global_end(); I != E; ++I) { 29231200Smm incorporateType(I->getType()); 30231200Smm if (I->hasInitializer()) 31231200Smm incorporateValue(I->getInitializer()); 32231200Smm } 33231200Smm 34231200Smm // Get types from aliases. 35302295Smm for (Module::const_alias_iterator I = M.alias_begin(), 36238856Smm E = M.alias_end(); I != E; ++I) { 37238856Smm incorporateType(I->getType()); 38231200Smm if (const Value *Aliasee = I->getAliasee()) 39231200Smm incorporateValue(Aliasee); 40231200Smm } 41231200Smm 42231200Smm // Get types from functions. 43231200Smm SmallVector<std::pair<unsigned, MDNode*>, 4> MDForInst; 44231200Smm for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) { 45231200Smm incorporateType(FI->getType()); 46231200Smm 47231200Smm if (FI->hasPrefixData()) 48231200Smm incorporateValue(FI->getPrefixData()); 49231200Smm 50231200Smm // First incorporate the arguments. 51231200Smm for (Function::const_arg_iterator AI = FI->arg_begin(), 52231200Smm AE = FI->arg_end(); AI != AE; ++AI) 53231200Smm incorporateValue(AI); 54231200Smm 55231200Smm for (Function::const_iterator BB = FI->begin(), E = FI->end(); 56231200Smm BB != E;++BB) 57231200Smm for (BasicBlock::const_iterator II = BB->begin(), 58231200Smm E = BB->end(); II != E; ++II) { 59231200Smm const Instruction &I = *II; 60231200Smm 61231200Smm // Incorporate the type of the instruction. 62231200Smm incorporateType(I.getType()); 63231200Smm 64231200Smm // Incorporate non-instruction operand types. (We are incorporating all 65231200Smm // instructions with this loop.) 66231200Smm for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end(); 67231200Smm OI != OE; ++OI) 68231200Smm if (!isa<Instruction>(OI)) 69231200Smm incorporateValue(*OI); 70231200Smm 71231200Smm // Incorporate types hiding in metadata. 72231200Smm I.getAllMetadataOtherThanDebugLoc(MDForInst); 73353377Smm for (unsigned i = 0, e = MDForInst.size(); i != e; ++i) 74231200Smm incorporateMDNode(MDForInst[i].second); 75231200Smm 76231200Smm MDForInst.clear(); 77231200Smm } 78231200Smm } 79231200Smm 80231200Smm for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), 81231200Smm E = M.named_metadata_end(); I != E; ++I) { 82231200Smm const NamedMDNode *NMD = I; 83231200Smm for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) 84231200Smm incorporateMDNode(NMD->getOperand(i)); 85231200Smm } 86231200Smm} 87231200Smm 88231200Smmvoid TypeFinder::clear() { 89231200Smm VisitedConstants.clear(); 90231200Smm VisitedTypes.clear(); 91231200Smm StructTypes.clear(); 92231200Smm} 93231200Smm 94231200Smm/// incorporateType - This method adds the type to the list of used structures 95231200Smm/// if it's not in there already. 96231200Smmvoid TypeFinder::incorporateType(Type *Ty) { 97231200Smm // Check to see if we've already visited this type. 98231200Smm if (!VisitedTypes.insert(Ty).second) 99231200Smm return; 100231200Smm 101231200Smm SmallVector<Type *, 4> TypeWorklist; 102231200Smm TypeWorklist.push_back(Ty); 103231200Smm do { 104302001Smm Ty = TypeWorklist.pop_back_val(); 105302001Smm 106302001Smm // If this is a structure or opaque type, add a name for the type. 107302001Smm if (StructType *STy = dyn_cast<StructType>(Ty)) 108302001Smm if (!OnlyNamed || STy->hasName()) 109302001Smm StructTypes.push_back(STy); 110231200Smm 111231200Smm // Add all unvisited subtypes to worklist for processing 112231200Smm for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 113231200Smm E = Ty->subtype_rend(); 114231200Smm I != E; ++I) 115231200Smm if (VisitedTypes.insert(*I).second) 116231200Smm TypeWorklist.push_back(*I); 117231200Smm } while (!TypeWorklist.empty()); 118231200Smm} 119231200Smm 120231200Smm/// incorporateValue - This method is used to walk operand lists finding types 121231200Smm/// hiding in constant expressions and other operands that won't be walked in 122231200Smm/// other ways. GlobalValues, basic blocks, instructions, and inst operands are 123231200Smm/// all explicitly enumerated. 124231200Smmvoid TypeFinder::incorporateValue(const Value *V) { 125231200Smm if (const MDNode *M = dyn_cast<MDNode>(V)) 126231200Smm return incorporateMDNode(M); 127231200Smm 128231200Smm if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 129231200Smm 130231200Smm // Already visited? 131302001Smm if (!VisitedConstants.insert(V).second) 132231200Smm return; 133231200Smm 134231200Smm // Check this type. 135231200Smm incorporateType(V->getType()); 136231200Smm 137231200Smm // If this is an instruction, we incorporate it separately. 138231200Smm if (isa<Instruction>(V)) 139231200Smm return; 140231200Smm 141353377Smm // Look in operands for types. 142231200Smm const User *U = cast<User>(V); 143302001Smm for (Constant::const_op_iterator I = U->op_begin(), 144231200Smm E = U->op_end(); I != E;++I) 145231200Smm incorporateValue(*I); 146231200Smm} 147231200Smm 148231200Smm/// incorporateMDNode - This method is used to walk the operands of an MDNode to 149231200Smm/// find types hiding within. 150231200Smmvoid TypeFinder::incorporateMDNode(const MDNode *V) { 151231200Smm // Already visited? 152231200Smm if (!VisitedConstants.insert(V).second) 153231200Smm return; 154231200Smm 155231200Smm // Look in operands for types. 156231200Smm for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) 157231200Smm if (Value *Op = V->getOperand(i)) 158231200Smm incorporateValue(Op); 159231200Smm} 160231200Smm