lib/IR/TypeFinder.cpp

   1 //===- TypeFinder.cpp - Implement the TypeFinder class --------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the TypeFinder class for the IR library.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/IR/TypeFinder.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/IR/BasicBlock.h"
  17 #include "llvm/IR/Constant.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   // Look in operands for types.
 157   for (Metadata *Op : V->operands()) {
 158     if (!Op)
 159       continue;
 160     if (auto *N = dyn_cast<MDNode>(Op)) {
 161       incorporateMDNode(N);
 162       continue;
 163     }
 164     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
 165       incorporateValue(C->getValue());
 166       continue;
 167     }
 168   }
 169 }