214 lines · cpp
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-exception6//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 32using namespace llvm;33 34void 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 all74 // 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 // Incorporate types hiding in variable-location information.93 for (const auto &Dbg : I.getDbgRecordRange()) {94 // Pick out records that have Values.95 if (const DbgVariableRecord *DVI =96 dyn_cast<DbgVariableRecord>(&Dbg)) {97 for (Value *V : DVI->location_ops())98 incorporateValue(V);99 if (DVI->isDbgAssign()) {100 if (Value *Addr = DVI->getAddress())101 incorporateValue(Addr);102 }103 }104 }105 }106 }107 108 for (const auto &NMD : M.named_metadata())109 for (const auto *MDOp : NMD.operands())110 incorporateMDNode(MDOp);111}112 113void TypeFinder::clear() {114 VisitedConstants.clear();115 VisitedTypes.clear();116 StructTypes.clear();117}118 119/// incorporateType - This method adds the type to the list of used structures120/// if it's not in there already.121void TypeFinder::incorporateType(Type *Ty) {122 // Check to see if we've already visited this type.123 if (!VisitedTypes.insert(Ty).second)124 return;125 126 SmallVector<Type *, 4> TypeWorklist;127 TypeWorklist.push_back(Ty);128 do {129 Ty = TypeWorklist.pop_back_val();130 131 // If this is a structure or opaque type, add a name for the type.132 if (StructType *STy = dyn_cast<StructType>(Ty))133 if (!OnlyNamed || STy->hasName())134 StructTypes.push_back(STy);135 136 // Add all unvisited subtypes to worklist for processing137 for (Type *SubTy : llvm::reverse(Ty->subtypes()))138 if (VisitedTypes.insert(SubTy).second)139 TypeWorklist.push_back(SubTy);140 } while (!TypeWorklist.empty());141}142 143/// incorporateValue - This method is used to walk operand lists finding types144/// hiding in constant expressions and other operands that won't be walked in145/// other ways. GlobalValues, basic blocks, instructions, and inst operands are146/// all explicitly enumerated.147void TypeFinder::incorporateValue(const Value *V) {148 if (const auto *M = dyn_cast<MetadataAsValue>(V)) {149 if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))150 return incorporateMDNode(N);151 if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))152 return incorporateValue(MDV->getValue());153 if (const auto *AL = dyn_cast<DIArgList>(M->getMetadata())) {154 for (auto *Arg : AL->getArgs())155 incorporateValue(Arg->getValue());156 return;157 }158 return;159 }160 161 if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;162 163 // Already visited?164 if (!VisitedConstants.insert(V).second)165 return;166 167 // Check this type.168 incorporateType(V->getType());169 170 // If this is an instruction, we incorporate it separately.171 if (isa<Instruction>(V))172 return;173 174 if (auto *GEP = dyn_cast<GEPOperator>(V))175 incorporateType(GEP->getSourceElementType());176 177 // Look in operands for types.178 const User *U = cast<User>(V);179 for (const auto &I : U->operands())180 incorporateValue(&*I);181}182 183/// incorporateMDNode - This method is used to walk the operands of an MDNode to184/// find types hiding within.185void TypeFinder::incorporateMDNode(const MDNode *V) {186 // Already visited?187 if (!VisitedMetadata.insert(V).second)188 return;189 190 // Look in operands for types.191 for (Metadata *Op : V->operands()) {192 if (!Op)193 continue;194 if (auto *N = dyn_cast<MDNode>(Op)) {195 incorporateMDNode(N);196 continue;197 }198 if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {199 incorporateValue(C->getValue());200 continue;201 }202 }203}204 205void TypeFinder::incorporateAttributes(AttributeList AL) {206 if (!VisitedAttributes.insert(AL).second)207 return;208 209 for (AttributeSet AS : AL)210 for (Attribute A : AS)211 if (A.isTypeAttribute())212 incorporateType(A.getValueAsType());213}214