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         // 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
 113 void 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 structures
 120 /// if it's not in there already.
 121 void 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 processing
 137     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 types
 144 /// hiding in constant expressions and other operands that won't be walked in
 145 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
 146 /// all explicitly enumerated.
 147 void 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 to
 184 /// find types hiding within.
 185 void 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
 205 void 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 }