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. 43280031Sdim 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 47296417Sdim for (const Use &U : FI->operands()) 48296417Sdim incorporateValue(U.get()); 49261991Sdim 50249259Sdim // First incorporate the arguments. 51249259Sdim for (Function::const_arg_iterator AI = FI->arg_begin(), 52249259Sdim AE = FI->arg_end(); AI != AE; ++AI) 53296417Sdim 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) 68288943Sdim if (*OI && !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) { 82296417Sdim 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) { 97261991Sdim // Check to see if we've already visited this type. 98249259Sdim if (!VisitedTypes.insert(Ty).second) 99249259Sdim return; 100249259Sdim 101261991Sdim SmallVector<Type *, 4> TypeWorklist; 102261991Sdim TypeWorklist.push_back(Ty); 103261991Sdim do { 104261991Sdim Ty = TypeWorklist.pop_back_val(); 105249259Sdim 106261991Sdim // If this is a structure or opaque type, add a name for the type. 107261991Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) 108261991Sdim if (!OnlyNamed || STy->hasName()) 109261991Sdim StructTypes.push_back(STy); 110261991Sdim 111261991Sdim // Add all unvisited subtypes to worklist for processing 112261991Sdim for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 113261991Sdim E = Ty->subtype_rend(); 114261991Sdim I != E; ++I) 115261991Sdim if (VisitedTypes.insert(*I).second) 116261991Sdim TypeWorklist.push_back(*I); 117261991Sdim } 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) { 125280031Sdim if (const auto *M = dyn_cast<MetadataAsValue>(V)) { 126280031Sdim if (const auto *N = dyn_cast<MDNode>(M->getMetadata())) 127280031Sdim return incorporateMDNode(N); 128280031Sdim if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata())) 129280031Sdim return incorporateValue(MDV->getValue()); 130280031Sdim return; 131280031Sdim } 132249259Sdim 133249259Sdim if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 134249259Sdim 135249259Sdim // Already visited? 136249259Sdim if (!VisitedConstants.insert(V).second) 137249259Sdim return; 138249259Sdim 139249259Sdim // Check this type. 140249259Sdim incorporateType(V->getType()); 141249259Sdim 142249259Sdim // If this is an instruction, we incorporate it separately. 143249259Sdim if (isa<Instruction>(V)) 144249259Sdim return; 145249259Sdim 146249259Sdim // Look in operands for types. 147249259Sdim const User *U = cast<User>(V); 148249259Sdim for (Constant::const_op_iterator I = U->op_begin(), 149249259Sdim E = U->op_end(); I != E;++I) 150249259Sdim incorporateValue(*I); 151249259Sdim} 152249259Sdim 153249259Sdim/// incorporateMDNode - This method is used to walk the operands of an MDNode to 154249259Sdim/// find types hiding within. 155249259Sdimvoid TypeFinder::incorporateMDNode(const MDNode *V) { 156249259Sdim // Already visited? 157280031Sdim if (!VisitedMetadata.insert(V).second) 158249259Sdim return; 159249259Sdim 160249259Sdim // Look in operands for types. 161280031Sdim for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) { 162280031Sdim Metadata *Op = V->getOperand(i); 163280031Sdim if (!Op) 164280031Sdim continue; 165280031Sdim if (auto *N = dyn_cast<MDNode>(Op)) { 166280031Sdim incorporateMDNode(N); 167280031Sdim continue; 168280031Sdim } 169280031Sdim if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) { 170280031Sdim incorporateValue(C->getValue()); 171280031Sdim continue; 172280031Sdim } 173280031Sdim } 174249259Sdim} 175