1 //===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the TypeFinder class for the IR library. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/IR/TypeFinder.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/IR/BasicBlock.h" 17 #include "llvm/IR/DerivedTypes.h" 18 #include "llvm/IR/Function.h" 19 #include "llvm/IR/Metadata.h" 20 #include "llvm/IR/Module.h" 21 using namespace llvm; 22 23 void TypeFinder::run(const Module &M, bool onlyNamed) { 24 OnlyNamed = onlyNamed; 25 26 // Get types from global variables. 27 for (Module::const_global_iterator I = M.global_begin(), 28 E = M.global_end(); I != E; ++I) { 29 incorporateType(I->getType()); 30 if (I->hasInitializer()) 31 incorporateValue(I->getInitializer()); 32 } 33 34 // Get types from aliases. 35 for (Module::const_alias_iterator I = M.alias_begin(), 36 E = M.alias_end(); I != E; ++I) { 37 incorporateType(I->getType()); 38 if (const Value *Aliasee = I->getAliasee()) 39 incorporateValue(Aliasee); 40 } 41 42 // Get types from functions. 43 SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst; 44 for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) { 45 incorporateType(FI->getType()); 46 47 if (FI->hasPrefixData()) 48 incorporateValue(FI->getPrefixData()); 49 50 if (FI->hasPrologueData()) 51 incorporateValue(FI->getPrologueData()); 52 53 // First incorporate the arguments. 54 for (Function::const_arg_iterator AI = FI->arg_begin(), 55 AE = FI->arg_end(); AI != AE; ++AI) 56 incorporateValue(AI); 57 58 for (Function::const_iterator BB = FI->begin(), E = FI->end(); 59 BB != E;++BB) 60 for (BasicBlock::const_iterator II = BB->begin(), 61 E = BB->end(); II != E; ++II) { 62 const Instruction &I = *II; 63 64 // Incorporate the type of the instruction. 65 incorporateType(I.getType()); 66 67 // Incorporate non-instruction operand types. (We are incorporating all 68 // instructions with this loop.) 69 for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end(); 70 OI != OE; ++OI) 71 if (*OI && !isa<Instruction>(OI)) 72 incorporateValue(*OI); 73 74 // Incorporate types hiding in metadata. 75 I.getAllMetadataOtherThanDebugLoc(MDForInst); 76 for (unsigned i = 0, e = MDForInst.size(); i != e; ++i) 77 incorporateMDNode(MDForInst[i].second); 78 79 MDForInst.clear(); 80 } 81 } 82 83 for (Module::const_named_metadata_iterator I = M.named_metadata_begin(), 84 E = M.named_metadata_end(); I != E; ++I) { 85 const NamedMDNode *NMD = I; 86 for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i) 87 incorporateMDNode(NMD->getOperand(i)); 88 } 89 } 90 91 void TypeFinder::clear() { 92 VisitedConstants.clear(); 93 VisitedTypes.clear(); 94 StructTypes.clear(); 95 } 96 97 /// incorporateType - This method adds the type to the list of used structures 98 /// if it's not in there already. 99 void TypeFinder::incorporateType(Type *Ty) { 100 // Check to see if we've already visited this type. 101 if (!VisitedTypes.insert(Ty).second) 102 return; 103 104 SmallVector<Type *, 4> TypeWorklist; 105 TypeWorklist.push_back(Ty); 106 do { 107 Ty = TypeWorklist.pop_back_val(); 108 109 // If this is a structure or opaque type, add a name for the type. 110 if (StructType *STy = dyn_cast<StructType>(Ty)) 111 if (!OnlyNamed || STy->hasName()) 112 StructTypes.push_back(STy); 113 114 // Add all unvisited subtypes to worklist for processing 115 for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 116 E = Ty->subtype_rend(); 117 I != E; ++I) 118 if (VisitedTypes.insert(*I).second) 119 TypeWorklist.push_back(*I); 120 } while (!TypeWorklist.empty()); 121 } 122 123 /// incorporateValue - This method is used to walk operand lists finding types 124 /// hiding in constant expressions and other operands that won't be walked in 125 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are 126 /// all explicitly enumerated. 127 void TypeFinder::incorporateValue(const Value *V) { 128 if (const auto *M = dyn_cast<MetadataAsValue>(V)) { 129 if (const auto *N = dyn_cast<MDNode>(M->getMetadata())) 130 return incorporateMDNode(N); 131 if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata())) 132 return incorporateValue(MDV->getValue()); 133 return; 134 } 135 136 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 137 138 // Already visited? 139 if (!VisitedConstants.insert(V).second) 140 return; 141 142 // Check this type. 143 incorporateType(V->getType()); 144 145 // If this is an instruction, we incorporate it separately. 146 if (isa<Instruction>(V)) 147 return; 148 149 // Look in operands for types. 150 const User *U = cast<User>(V); 151 for (Constant::const_op_iterator I = U->op_begin(), 152 E = U->op_end(); I != E;++I) 153 incorporateValue(*I); 154 } 155 156 /// incorporateMDNode - This method is used to walk the operands of an MDNode to 157 /// find types hiding within. 158 void TypeFinder::incorporateMDNode(const MDNode *V) { 159 // Already visited? 160 if (!VisitedMetadata.insert(V).second) 161 return; 162 163 // Look in operands for types. 164 for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) { 165 Metadata *Op = V->getOperand(i); 166 if (!Op) 167 continue; 168 if (auto *N = dyn_cast<MDNode>(Op)) { 169 incorporateMDNode(N); 170 continue; 171 } 172 if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) { 173 incorporateValue(C->getValue()); 174 continue; 175 } 176 } 177 } 178
