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 471e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne if (FI->hasPrefixData()) 481e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne incorporateValue(FI->getPrefixData()); 491e3037f0be430ef2339838bbdede11f45658bd82Peter Collingbourne 50573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // First incorporate the arguments. 51573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Function::const_arg_iterator AI = FI->arg_begin(), 52573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling AE = FI->arg_end(); AI != AE; ++AI) 53573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(AI); 54573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 55573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Function::const_iterator BB = FI->begin(), E = FI->end(); 56573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling BB != E;++BB) 57573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (BasicBlock::const_iterator II = BB->begin(), 58573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = BB->end(); II != E; ++II) { 59573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const Instruction &I = *II; 60573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 61573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate the type of the instruction. 62573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(I.getType()); 63573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 64573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate non-instruction operand types. (We are incorporating all 65573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // instructions with this loop.) 66573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end(); 67573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling OI != OE; ++OI) 68573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!isa<Instruction>(OI)) 69573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(*OI); 70573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 71573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Incorporate types hiding in metadata. 72573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling I.getAllMetadataOtherThanDebugLoc(MDForInst); 73573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = MDForInst.size(); i != e; ++i) 74573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateMDNode(MDForInst[i].second); 75573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 76573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling MDForInst.clear(); 77573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 78573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 79573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 80573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), 81573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = M.named_metadata_end(); I != E; ++I) { 82573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const NamedMDNode *NMD = I; 83573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) 84573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateMDNode(NMD->getOperand(i)); 85573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling } 86573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 87573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 88573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::clear() { 89573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling VisitedConstants.clear(); 90573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling VisitedTypes.clear(); 91573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling StructTypes.clear(); 92573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 93573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 94573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateType - This method adds the type to the list of used structures 95573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// if it's not in there already. 96573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateType(Type *Ty) { 971e6810005f426798ce2541c26f0cdc7a08670846Will Dietz // Check to see if we've already visited this type. 98573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedTypes.insert(Ty).second) 99573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 100573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 1011e6810005f426798ce2541c26f0cdc7a08670846Will Dietz SmallVector<Type *, 4> TypeWorklist; 1021e6810005f426798ce2541c26f0cdc7a08670846Will Dietz TypeWorklist.push_back(Ty); 1031e6810005f426798ce2541c26f0cdc7a08670846Will Dietz do { 1041e6810005f426798ce2541c26f0cdc7a08670846Will Dietz Ty = TypeWorklist.pop_back_val(); 1051e6810005f426798ce2541c26f0cdc7a08670846Will Dietz 1061e6810005f426798ce2541c26f0cdc7a08670846Will Dietz // If this is a structure or opaque type, add a name for the type. 1071e6810005f426798ce2541c26f0cdc7a08670846Will Dietz if (StructType *STy = dyn_cast<StructType>(Ty)) 1081e6810005f426798ce2541c26f0cdc7a08670846Will Dietz if (!OnlyNamed || STy->hasName()) 1091e6810005f426798ce2541c26f0cdc7a08670846Will Dietz StructTypes.push_back(STy); 1101e6810005f426798ce2541c26f0cdc7a08670846Will Dietz 1111e6810005f426798ce2541c26f0cdc7a08670846Will Dietz // Add all unvisited subtypes to worklist for processing 1121e6810005f426798ce2541c26f0cdc7a08670846Will Dietz for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 1131e6810005f426798ce2541c26f0cdc7a08670846Will Dietz E = Ty->subtype_rend(); 1141e6810005f426798ce2541c26f0cdc7a08670846Will Dietz I != E; ++I) 1151e6810005f426798ce2541c26f0cdc7a08670846Will Dietz if (VisitedTypes.insert(*I).second) 1161e6810005f426798ce2541c26f0cdc7a08670846Will Dietz TypeWorklist.push_back(*I); 1171e6810005f426798ce2541c26f0cdc7a08670846Will Dietz } while (!TypeWorklist.empty()); 118573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 119573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 120573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateValue - This method is used to walk operand lists finding types 121573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// hiding in constant expressions and other operands that won't be walked in 122573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// other ways. GlobalValues, basic blocks, instructions, and inst operands are 123573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// all explicitly enumerated. 124573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateValue(const Value *V) { 125573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (const MDNode *M = dyn_cast<MDNode>(V)) 126573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return incorporateMDNode(M); 127573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 128573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 129573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 130573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Already visited? 131573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedConstants.insert(V).second) 132573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 133573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 134573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Check this type. 135573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateType(V->getType()); 136573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 137573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // If this is an instruction, we incorporate it separately. 138573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (isa<Instruction>(V)) 139573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 140573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 141573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Look in operands for types. 142573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling const User *U = cast<User>(V); 143573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (Constant::const_op_iterator I = U->op_begin(), 144573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling E = U->op_end(); I != E;++I) 145573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(*I); 146573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 147573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 148573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// incorporateMDNode - This method is used to walk the operands of an MDNode to 149573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling/// find types hiding within. 150573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendlingvoid TypeFinder::incorporateMDNode(const MDNode *V) { 151573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Already visited? 152573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (!VisitedConstants.insert(V).second) 153573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling return; 154573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling 155573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling // Look in operands for types. 156573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) 157573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling if (Value *Op = V->getOperand(i)) 158573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling incorporateValue(Op); 159573e97326766359d3a9747eed7b7d47b6c33fa0fBill Wendling} 160