1573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling//===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===// 2573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// 3573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// The LLVM Compiler Infrastructure 4573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// 5573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// This file is distributed under the University of Illinois Open Source 6573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// License. See LICENSE.TXT for details. 7573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// 8573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling//===----------------------------------------------------------------------===// 9573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// 10c2c50cdcdc19a1bca993c06d13d8cdca87083ce4Chandler Carruth// This file implements the TypeFinder class for the IR library. 11573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling// 12573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling//===----------------------------------------------------------------------===// 13573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 144068e1af9ff68b6b5fdb3233f1304e53f1bf179aChandler Carruth#include "llvm/IR/TypeFinder.h" 15d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 160b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/BasicBlock.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Metadata.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 21573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingusing namespace llvm; 22573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 23573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::run(const Module &M, bool onlyNamed) { 24573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling OnlyNamed = onlyNamed; 25573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 26573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Get types from global variables. 27573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Module::const_global_iterator I = M.global_begin(), 28573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = M.global_end(); I != E; ++I) { 29573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(I->getType()); 30573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (I->hasInitializer()) 31573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(I->getInitializer()); 32573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 33573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 34573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Get types from aliases. 35573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Module::const_alias_iterator I = M.alias_begin(), 36573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = M.alias_end(); I != E; ++I) { 37573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(I->getType()); 38573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (const Value *Aliasee = I->getAliasee()) 39573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(Aliasee); 40573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 41573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 42573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Get types from functions. 43573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling SmallVector<std::pair<unsigned, MDNode*>, 4> MDForInst; 44573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) { 45573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(FI->getType()); 46573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 47573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // First incorporate the arguments. 48573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Function::const_arg_iterator AI = FI->arg_begin(), 49573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling AE = FI->arg_end(); AI != AE; ++AI) 50573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(AI); 51573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 52573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Function::const_iterator BB = FI->begin(), E = FI->end(); 53573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling BB != E;++BB) 54573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (BasicBlock::const_iterator II = BB->begin(), 55573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = BB->end(); II != E; ++II) { 56573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const Instruction &I = *II; 57573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 58573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate the type of the instruction. 59573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(I.getType()); 60573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 61573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate non-instruction operand types. (We are incorporating all 62573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // instructions with this loop.) 63573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end(); 64573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling OI != OE; ++OI) 65573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!isa<Instruction>(OI)) 66573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(*OI); 67573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 68573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate types hiding in metadata. 69573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling I.getAllMetadataOtherThanDebugLoc(MDForInst); 70573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = MDForInst.size(); i != e; ++i) 71573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateMDNode(MDForInst[i].second); 72573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 73573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling MDForInst.clear(); 74573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 75573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 76573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 77573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), 78573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = M.named_metadata_end(); I != E; ++I) { 79573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const NamedMDNode *NMD = I; 80573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) 81573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateMDNode(NMD->getOperand(i)); 82573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 83573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 84573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 85573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::clear() { 86573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling VisitedConstants.clear(); 87573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling VisitedTypes.clear(); 88573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling StructTypes.clear(); 89573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 90573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 91573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateType - This method adds the type to the list of used structures 92573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// if it's not in there already. 93573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateType(Type *Ty) { 94573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Check to see if we're already visited this type. 95573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedTypes.insert(Ty).second) 96573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 97573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 98573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // If this is a structure or opaque type, add a name for the type. 99573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (StructType *STy = dyn_cast<StructType>(Ty)) 100573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!OnlyNamed || STy->hasName()) 101573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling StructTypes.push_back(STy); 102573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 103573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Recursively walk all contained types. 104573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Type::subtype_iterator I = Ty->subtype_begin(), 105573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = Ty->subtype_end(); I != E; ++I) 106573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(*I); 107573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 108573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 109573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateValue - This method is used to walk operand lists finding types 110573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// hiding in constant expressions and other operands that won't be walked in 111573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// other ways. GlobalValues, basic blocks, instructions, and inst operands are 112573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// all explicitly enumerated. 113573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateValue(const Value *V) { 114573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (const MDNode *M = dyn_cast<MDNode>(V)) 115573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return incorporateMDNode(M); 116573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 117573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 118573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 119573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Already visited? 120573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedConstants.insert(V).second) 121573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 122573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 123573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Check this type. 124573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(V->getType()); 125573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 126573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // If this is an instruction, we incorporate it separately. 127573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (isa<Instruction>(V)) 128573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 129573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 130573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Look in operands for types. 131573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const User *U = cast<User>(V); 132573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Constant::const_op_iterator I = U->op_begin(), 133573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = U->op_end(); I != E;++I) 134573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(*I); 135573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 136573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 137573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateMDNode - This method is used to walk the operands of an MDNode to 138573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// find types hiding within. 139573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateMDNode(const MDNode *V) { 140573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Already visited? 141573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedConstants.insert(V).second) 142573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 143573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 144573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Look in operands for types. 145573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) 146573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (Value *Op = V->getOperand(i)) 147573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(Op); 148573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 149