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/Metadata.h" 22 #include "llvm/IR/Module.h" 23 #include "llvm/IR/Type.h" 24 #include "llvm/IR/Use.h" 25 #include "llvm/IR/User.h" 26 #include "llvm/IR/Value.h" 27 #include "llvm/Support/Casting.h" 28 #include <utility> 29 30 using namespace llvm; 31 32 void TypeFinder::run(const Module &M, bool onlyNamed) { 33 OnlyNamed = onlyNamed; 34 35 // Get types from global variables. 36 for (const auto &G : M.globals()) { 37 incorporateType(G.getType()); 38 if (G.hasInitializer()) 39 incorporateValue(G.getInitializer()); 40 } 41 42 // Get types from aliases. 43 for (const auto &A : M.aliases()) { 44 incorporateType(A.getType()); 45 if (const Value *Aliasee = A.getAliasee()) 46 incorporateValue(Aliasee); 47 } 48 49 // Get types from functions. 50 SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst; 51 for (const Function &FI : M) { 52 incorporateType(FI.getType()); 53 54 for (const Use &U : FI.operands()) 55 incorporateValue(U.get()); 56 57 // First incorporate the arguments. 58 for (const auto &A : FI.args()) 59 incorporateValue(&A); 60 61 for (const BasicBlock &BB : FI) 62 for (const Instruction &I : BB) { 63 // Incorporate the type of the instruction. 64 incorporateType(I.getType()); 65 66 // Incorporate non-instruction operand types. (We are incorporating all 67 // instructions with this loop.) 68 for (const auto &O : I.operands()) 69 if (&*O && !isa<Instruction>(&*O)) 70 incorporateValue(&*O); 71 72 // Incorporate types hiding in metadata. 73 I.getAllMetadataOtherThanDebugLoc(MDForInst); 74 for (const auto &MD : MDForInst) 75 incorporateMDNode(MD.second); 76 MDForInst.clear(); 77 } 78 } 79 80 for (const auto &NMD : M.named_metadata()) 81 for (const auto *MDOp : NMD.operands()) 82 incorporateMDNode(MDOp); 83 } 84 85 void TypeFinder::clear() { 86 VisitedConstants.clear(); 87 VisitedTypes.clear(); 88 StructTypes.clear(); 89 } 90 91 /// incorporateType - This method adds the type to the list of used structures 92 /// if it's not in there already. 93 void TypeFinder::incorporateType(Type *Ty) { 94 // Check to see if we've already visited this type. 95 if (!VisitedTypes.insert(Ty).second) 96 return; 97 98 SmallVector<Type *, 4> TypeWorklist; 99 TypeWorklist.push_back(Ty); 100 do { 101 Ty = TypeWorklist.pop_back_val(); 102 103 // If this is a structure or opaque type, add a name for the type. 104 if (StructType *STy = dyn_cast<StructType>(Ty)) 105 if (!OnlyNamed || STy->hasName()) 106 StructTypes.push_back(STy); 107 108 // Add all unvisited subtypes to worklist for processing 109 for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(), 110 E = Ty->subtype_rend(); 111 I != E; ++I) 112 if (VisitedTypes.insert(*I).second) 113 TypeWorklist.push_back(*I); 114 } while (!TypeWorklist.empty()); 115 } 116 117 /// incorporateValue - This method is used to walk operand lists finding types 118 /// hiding in constant expressions and other operands that won't be walked in 119 /// other ways. GlobalValues, basic blocks, instructions, and inst operands are 120 /// all explicitly enumerated. 121 void TypeFinder::incorporateValue(const Value *V) { 122 if (const auto *M = dyn_cast<MetadataAsValue>(V)) { 123 if (const auto *N = dyn_cast<MDNode>(M->getMetadata())) 124 return incorporateMDNode(N); 125 if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata())) 126 return incorporateValue(MDV->getValue()); 127 return; 128 } 129 130 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return; 131 132 // Already visited? 133 if (!VisitedConstants.insert(V).second) 134 return; 135 136 // Check this type. 137 incorporateType(V->getType()); 138 139 // If this is an instruction, we incorporate it separately. 140 if (isa<Instruction>(V)) 141 return; 142 143 // Look in operands for types. 144 const User *U = cast<User>(V); 145 for (const auto &I : U->operands()) 146 incorporateValue(&*I); 147 } 148 149 /// incorporateMDNode - This method is used to walk the operands of an MDNode to 150 /// find types hiding within. 151 void TypeFinder::incorporateMDNode(const MDNode *V) { 152 // Already visited? 153 if (!VisitedMetadata.insert(V).second) 154 return; 155 156 // The arguments in DIArgList are not exposed as operands, so handle such 157 // nodes specifically here. 158 if (const auto *AL = dyn_cast<DIArgList>(V)) { 159 for (auto *Arg : AL->getArgs()) 160 incorporateValue(Arg->getValue()); 161 return; 162 } 163 164 // Look in operands for types. 165 for (Metadata *Op : V->operands()) { 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