1249259Sdim//===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file implements the TypeFinder class for the IR library. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#include "llvm/IR/TypeFinder.h" 15249259Sdim#include "llvm/ADT/SmallVector.h" 16249259Sdim#include "llvm/IR/BasicBlock.h" 17249259Sdim#include "llvm/IR/DerivedTypes.h" 18249259Sdim#include "llvm/IR/Function.h" 19249259Sdim#include "llvm/IR/Metadata.h" 20249259Sdim#include "llvm/IR/Module.h" 21249259Sdimusing namespace llvm; 22249259Sdim 23249259Sdimvoid TypeFinder::run(const Module &M, bool onlyNamed) { 24249259Sdim OnlyNamed = onlyNamed; 25249259Sdim 26249259Sdim // Get types from global variables. 27249259Sdim for (Module::const_global_iterator I = M.global_begin(), 28249259Sdim E = M.global_end(); I != E; ++I) { 29249259Sdim incorporateType(I->getType()); 30249259Sdim if (I->hasInitializer()) 31249259Sdim incorporateValue(I->getInitializer()); 32249259Sdim } 33249259Sdim 34249259Sdim // Get types from aliases. 35249259Sdim for (Module::const_alias_iterator I = M.alias_begin(), 36249259Sdim E = M.alias_end(); I != E; ++I) { 37249259Sdim incorporateType(I->getType()); 38249259Sdim if (const Value *Aliasee = I->getAliasee()) 39249259Sdim incorporateValue(Aliasee); 40249259Sdim } 41249259Sdim 42249259Sdim // Get types from functions. 43249259Sdim SmallVector<std::pair<unsigned, MDNode*>, 4> MDForInst; 44249259Sdim for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) { 45249259Sdim incorporateType(FI->getType()); 46249259Sdim 47263508Sdim if (FI->hasPrefixData()) 48263508Sdim incorporateValue(FI->getPrefixData()); 49263508Sdim 50249259Sdim // First incorporate the arguments. 51249259Sdim for (Function::const_arg_iterator AI = FI->arg_begin(), 52249259Sdim AE = FI->arg_end(); AI != AE; ++AI) 53249259Sdim incorporateValue(AI); 54249259Sdim 55249259Sdim for (Function::const_iterator BB = FI->begin(), E = FI->end(); 56249259Sdim BB != E;++BB) 57249259Sdim for (BasicBlock::const_iterator II = BB->begin(), 58249259Sdim E = BB->end(); II != E; ++II) { 59249259Sdim const Instruction &I = *II; 60249259Sdim 61249259Sdim // Incorporate the type of the instruction. 62249259Sdim incorporateType(I.getType()); 63249259Sdim 64249259Sdim // Incorporate non-instruction operand types. (We are incorporating all 65249259Sdim // instructions with this loop.) 66249259Sdim for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end(); 67249259Sdim OI != OE; ++OI) 68249259Sdim if (!isa<Instruction>(OI)) 69249259Sdim incorporateValue(*OI); 70249259Sdim 71249259Sdim // Incorporate types hiding in metadata. 72249259Sdim I.getAllMetadataOtherThanDebugLoc(MDForInst); 73249259Sdim for (unsigned i = 0, e = MDForInst.size(); i != e; ++i) 74249259Sdim incorporateMDNode(MDForInst[i].second); 75249259Sdim 76249259Sdim MDForInst.clear(); 77249259Sdim } 78249259Sdim } 79249259Sdim 80249259Sdim for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), 81249259Sdim E = M.named_metadata_end(); I != E; ++I) { 82249259Sdim const NamedMDNode *NMD = I; 83249259Sdim for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) 84249259Sdim incorporateMDNode(NMD->getOperand(i)); 85249259Sdim } 86249259Sdim} 87249259Sdim 88249259Sdimvoid TypeFinder::clear() { 89249259Sdim VisitedConstants.clear(); 90249259Sdim VisitedTypes.clear(); 91249259Sdim StructTypes.clear(); 92249259Sdim} 93249259Sdim 94249259Sdim/// incorporateType - This method adds the type to the list of used structures 95249259Sdim/// if it's not in there already. 96249259Sdimvoid TypeFinder::incorporateType(Type *Ty) { 97263508Sdim // Check to see if we've already visited this type. 98249259Sdim if (!VisitedTypes.insert(Ty).second) 99249259Sdim return; 100249259Sdim 101263508Sdim SmallVector<Type *, 4> TypeWorklist; 102263508Sdim TypeWorklist.push_back(Ty); 103263508Sdim do { 104263508Sdim Ty = TypeWorklist.pop_back_val(); 105249259Sdim 106263508Sdim // If this is a structure or opaque type, add a name for the type. 107263508Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) 108263508Sdim if (!OnlyNamed || STy->hasName()) 109263508Sdim StructTypes.push_back(STy); 110263508Sdim 111263508Sdim // Add all unvisited subtypes to worklist for processing 112263508Sdim for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 113263508Sdim E = Ty->subtype_rend(); 114263508Sdim I != E; ++I) 115263508Sdim if (VisitedTypes.insert(*I).second) 116263508Sdim TypeWorklist.push_back(*I); 117263508Sdim } while (!TypeWorklist.empty()); 118249259Sdim} 119249259Sdim 120249259Sdim/// incorporateValue - This method is used to walk operand lists finding types 121249259Sdim/// hiding in constant expressions and other operands that won't be walked in 122249259Sdim/// other ways. GlobalValues, basic blocks, instructions, and inst operands are 123249259Sdim/// all explicitly enumerated. 124249259Sdimvoid TypeFinder::incorporateValue(const Value *V) { 125249259Sdim if (const MDNode *M = dyn_cast<MDNode>(V)) 126249259Sdim return incorporateMDNode(M); 127249259Sdim 128249259Sdim if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 129249259Sdim 130249259Sdim // Already visited? 131249259Sdim if (!VisitedConstants.insert(V).second) 132249259Sdim return; 133249259Sdim 134249259Sdim // Check this type. 135249259Sdim incorporateType(V->getType()); 136249259Sdim 137249259Sdim // If this is an instruction, we incorporate it separately. 138249259Sdim if (isa<Instruction>(V)) 139249259Sdim return; 140249259Sdim 141249259Sdim // Look in operands for types. 142249259Sdim const User *U = cast<User>(V); 143249259Sdim for (Constant::const_op_iterator I = U->op_begin(), 144249259Sdim E = U->op_end(); I != E;++I) 145249259Sdim incorporateValue(*I); 146249259Sdim} 147249259Sdim 148249259Sdim/// incorporateMDNode - This method is used to walk the operands of an MDNode to 149249259Sdim/// find types hiding within. 150249259Sdimvoid TypeFinder::incorporateMDNode(const MDNode *V) { 151249259Sdim // Already visited? 152249259Sdim if (!VisitedConstants.insert(V).second) 153249259Sdim return; 154249259Sdim 155249259Sdim // Look in operands for types. 156249259Sdim for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) 157249259Sdim if (Value *Op = V->getOperand(i)) 158249259Sdim incorporateValue(Op); 159249259Sdim} 160