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