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