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