llvm/lib/IR/TypeFinder.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-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 }