1 //===- TypeFinder.cpp - Implement the TypeFinder class --------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the TypeFinder class for the IR library. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/IR/TypeFinder.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/IR/BasicBlock.h" 16 #include "llvm/IR/Constant.h" 17 #include "llvm/IR/DebugInfoMetadata.h" 18 #include "llvm/IR/DerivedTypes.h" 19 #include "llvm/IR/Function.h" 20 #include "llvm/IR/Instruction.h" 21 #include "llvm/IR/Instructions.h" 22 #include "llvm/IR/Metadata.h" 23 #include "llvm/IR/Module.h" 24 #include "llvm/IR/Operator.h" 25 #include "llvm/IR/Type.h" 26 #include "llvm/IR/Use.h" 27 #include "llvm/IR/User.h" 28 #include "llvm/IR/Value.h" 29 #include "llvm/Support/Casting.h" 30 #include <utility> 31 32 using namespace llvm; 33 34 void TypeFinder::run(const Module &M, bool onlyNamed) { 35 OnlyNamed = onlyNamed; 36 37 // Get types from global variables. 38 for (const auto &G : M.globals()) { 39 incorporateType(G.getValueType()); 40 if (G.hasInitializer()) 41 incorporateValue(G.getInitializer()); 42 } 43 44 // Get types from aliases. 45 for (const auto &A : M.aliases()) { 46 incorporateType(A.getValueType()); 47 if (const Value *Aliasee = A.getAliasee()) 48 incorporateValue(Aliasee); 49 } 50 51 // Get types from ifuncs. 52 for (const auto &GI : M.ifuncs()) 53 incorporateType(GI.getValueType()); 54 55 // Get types from functions. 56 SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst; 57 for (const Function &FI : M) { 58 incorporateType(FI.getFunctionType()); 59 incorporateAttributes(FI.getAttributes()); 60 61 for (const Use &U : FI.operands()) 62 incorporateValue(U.get()); 63 64 // First incorporate the arguments. 65 for (const auto &A : FI.args()) 66 incorporateValue(&A); 67 68 for (const BasicBlock &BB : FI) 69 for (const Instruction &I : BB) { 70 // Incorporate the type of the instruction. 71 incorporateType(I.getType()); 72 73 // Incorporate non-instruction operand types. (We are incorporating all 74 // instructions with this loop.) 75 for (const auto &O : I.operands()) 76 if (&*O && !isa<Instruction>(&*O)) 77 incorporateValue(&*O); 78 79 if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) 80 incorporateType(GEP->getSourceElementType()); 81 if (auto *AI = dyn_cast<AllocaInst>(&I)) 82 incorporateType(AI->getAllocatedType()); 83 if (const auto *CB = dyn_cast<CallBase>(&I)) 84 incorporateAttributes(CB->getAttributes()); 85 86 // Incorporate types hiding in metadata. 87 I.getAllMetadataOtherThanDebugLoc(MDForInst); 88 for (const auto &MD : MDForInst) 89 incorporateMDNode(MD.second); 90 MDForInst.clear(); 91 } 92 } 93 94 for (const auto &NMD : M.named_metadata()) 95 for (const auto *MDOp : NMD.operands()) 96 incorporateMDNode(MDOp); 97 } 98 99 void TypeFinder::clear() { 100 VisitedConstants.clear(); 101 VisitedTypes.clear(); 102 StructTypes.clear(); 103 } 104 105 /// incorporateType - This method adds the type to the list of used structures 106 /// if it's not in there already. 107 void TypeFinder::incorporateType(Type *Ty) { 108 // Check to see if we've already visited this type. 109 if (!VisitedTypes.insert(Ty).second) 110 return; 111 112 SmallVector<Type *, 4> TypeWorklist; 113 TypeWorklist.push_back(Ty); 114 do { 115 Ty = TypeWorklist.pop_back_val(); 116 117 // If this is a structure or opaque type, add a name for the type. 118 if (StructType *STy = dyn_cast<StructType>(Ty)) 119 if (!OnlyNamed || STy->hasName()) 120 StructTypes.push_back(STy); 121 122 // Add all unvisited subtypes to worklist for processing 123 for (Type *SubTy : llvm::reverse(Ty->subtypes())) 124 if (VisitedTypes.insert(SubTy).second) 125 TypeWorklist.push_back(SubTy); 126 } while (!TypeWorklist.empty()); 127 } 128 129 /// incorporateValue - This method is used to walk operand lists finding types 130 /// hiding in constant expressions and other operands that won't be walked in 131 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are 132 /// all explicitly enumerated. 133 void TypeFinder::incorporateValue(const Value *V) { 134 if (const auto *M = dyn_cast<MetadataAsValue>(V)) { 135 if (const auto *N = dyn_cast<MDNode>(M->getMetadata())) 136 return incorporateMDNode(N); 137 if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata())) 138 return incorporateValue(MDV->getValue()); 139 return; 140 } 141 142 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 143 144 // Already visited? 145 if (!VisitedConstants.insert(V).second) 146 return; 147 148 // Check this type. 149 incorporateType(V->getType()); 150 151 // If this is an instruction, we incorporate it separately. 152 if (isa<Instruction>(V)) 153 return; 154 155 if (auto *GEP = dyn_cast<GEPOperator>(V)) 156 incorporateType(GEP->getSourceElementType()); 157 158 // Look in operands for types. 159 const User *U = cast<User>(V); 160 for (const auto &I : U->operands()) 161 incorporateValue(&*I); 162 } 163 164 /// incorporateMDNode - This method is used to walk the operands of an MDNode to 165 /// find types hiding within. 166 void TypeFinder::incorporateMDNode(const MDNode *V) { 167 // Already visited? 168 if (!VisitedMetadata.insert(V).second) 169 return; 170 171 // The arguments in DIArgList are not exposed as operands, so handle such 172 // nodes specifically here. 173 if (const auto *AL = dyn_cast<DIArgList>(V)) { 174 for (auto *Arg : AL->getArgs()) 175 incorporateValue(Arg->getValue()); 176 return; 177 } 178 179 // Look in operands for types. 180 for (Metadata *Op : V->operands()) { 181 if (!Op) 182 continue; 183 if (auto *N = dyn_cast<MDNode>(Op)) { 184 incorporateMDNode(N); 185 continue; 186 } 187 if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) { 188 incorporateValue(C->getValue()); 189 continue; 190 } 191 } 192 } 193 194 void TypeFinder::incorporateAttributes(AttributeList AL) { 195 if (!VisitedAttributes.insert(AL).second) 196 return; 197 198 for (AttributeSet AS : AL) 199 for (Attribute A : AS) 200 if (A.isTypeAttribute()) 201 incorporateType(A.getValueAsType()); 202 } 203