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