contrib/llvm/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 (Module::const_global_iterator I = M.global_begin(),
  37          E = M.global_end(); I != E; ++I) {
  38     incorporateType(I->getType());
  39     if (I->hasInitializer())
  40       incorporateValue(I->getInitializer());
  41   }
  42
  43   // Get types from aliases.
  44   for (Module::const_alias_iterator I = M.alias_begin(),
  45          E = M.alias_end(); I != E; ++I) {
  46     incorporateType(I->getType());
  47     if (const Value *Aliasee = I->getAliasee())
  48       incorporateValue(Aliasee);
  49   }
  50
  51   // Get types from functions.
  52   SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
  53   for (const Function &FI : M) {
  54     incorporateType(FI.getType());
  55
  56     for (const Use &U : FI.operands())
  57       incorporateValue(U.get());
  58
  59     // First incorporate the arguments.
  60     for (Function::const_arg_iterator AI = FI.arg_begin(), AE = FI.arg_end();
  61          AI != AE; ++AI)
  62       incorporateValue(&*AI);
  63
  64     for (const BasicBlock &BB : FI)
  65       for (const Instruction &I : BB) {
  66         // Incorporate the type of the instruction.
  67         incorporateType(I.getType());
  68
  69         // Incorporate non-instruction operand types. (We are incorporating all
  70         // instructions with this loop.)
  71         for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
  72              OI != OE; ++OI)
  73           if (*OI && !isa<Instruction>(OI))
  74             incorporateValue(*OI);
  75
  76         // Incorporate types hiding in metadata.
  77         I.getAllMetadataOtherThanDebugLoc(MDForInst);
  78         for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
  79           incorporateMDNode(MDForInst[i].second);
  80
  81         MDForInst.clear();
  82       }
  83   }
  84
  85   for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
  86          E = M.named_metadata_end(); I != E; ++I) {
  87     const NamedMDNode *NMD = &*I;
  88     for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
  89       incorporateMDNode(NMD->getOperand(i));
  90   }
  91 }
  92
  93 void TypeFinder::clear() {
  94   VisitedConstants.clear();
  95   VisitedTypes.clear();
  96   StructTypes.clear();
  97 }
  98
  99 /// incorporateType - This method adds the type to the list of used structures
 100 /// if it's not in there already.
 101 void TypeFinder::incorporateType(Type *Ty) {
 102   // Check to see if we've already visited this type.
 103   if (!VisitedTypes.insert(Ty).second)
 104     return;
 105
 106   SmallVector<Type *, 4> TypeWorklist;
 107   TypeWorklist.push_back(Ty);
 108   do {
 109     Ty = TypeWorklist.pop_back_val();
 110
 111     // If this is a structure or opaque type, add a name for the type.
 112     if (StructType *STy = dyn_cast<StructType>(Ty))
 113       if (!OnlyNamed || STy->hasName())
 114         StructTypes.push_back(STy);
 115
 116     // Add all unvisited subtypes to worklist for processing
 117     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
 118                                         E = Ty->subtype_rend();
 119          I != E; ++I)
 120       if (VisitedTypes.insert(*I).second)
 121         TypeWorklist.push_back(*I);
 122   } while (!TypeWorklist.empty());
 123 }
 124
 125 /// incorporateValue - This method is used to walk operand lists finding types
 126 /// hiding in constant expressions and other operands that won't be walked in
 127 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
 128 /// all explicitly enumerated.
 129 void TypeFinder::incorporateValue(const Value *V) {
 130   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
 131     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
 132       return incorporateMDNode(N);
 133     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
 134       return incorporateValue(MDV->getValue());
 135     return;
 136   }
 137
 138   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
 139
 140   // Already visited?
 141   if (!VisitedConstants.insert(V).second)
 142     return;
 143
 144   // Check this type.
 145   incorporateType(V->getType());
 146
 147   // If this is an instruction, we incorporate it separately.
 148   if (isa<Instruction>(V))
 149     return;
 150
 151   // Look in operands for types.
 152   const User *U = cast<User>(V);
 153   for (Constant::const_op_iterator I = U->op_begin(),
 154          E = U->op_end(); I != E;++I)
 155     incorporateValue(*I);
 156 }
 157
 158 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
 159 /// find types hiding within.
 160 void TypeFinder::incorporateMDNode(const MDNode *V) {
 161   // Already visited?
 162   if (!VisitedMetadata.insert(V).second)
 163     return;
 164
 165   // Look in operands for types.
 166   for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) {
 167     Metadata *Op = V->getOperand(i);
 168     if (!Op)
 169       continue;
 170     if (auto *N = dyn_cast<MDNode>(Op)) {
 171       incorporateMDNode(N);
 172       continue;
 173     }
 174     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
 175       incorporateValue(C->getValue());
 176       continue;
 177     }
 178   }
 179 }