LLVM  mainline
TypeFinder.cpp
Go to the documentation of this file.
00001 //===-- TypeFinder.cpp - Implement the TypeFinder class -------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the TypeFinder class for the IR library.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/IR/TypeFinder.h"
00015 #include "llvm/ADT/SmallVector.h"
00016 #include "llvm/IR/BasicBlock.h"
00017 #include "llvm/IR/DerivedTypes.h"
00018 #include "llvm/IR/Function.h"
00019 #include "llvm/IR/Metadata.h"
00020 #include "llvm/IR/Module.h"
00021 using namespace llvm;
00022 
00023 void TypeFinder::run(const Module &M, bool onlyNamed) {
00024   OnlyNamed = onlyNamed;
00025 
00026   // Get types from global variables.
00027   for (Module::const_global_iterator I = M.global_begin(),
00028          E = M.global_end(); I != E; ++I) {
00029     incorporateType(I->getType());
00030     if (I->hasInitializer())
00031       incorporateValue(I->getInitializer());
00032   }
00033 
00034   // Get types from aliases.
00035   for (Module::const_alias_iterator I = M.alias_begin(),
00036          E = M.alias_end(); I != E; ++I) {
00037     incorporateType(I->getType());
00038     if (const Value *Aliasee = I->getAliasee())
00039       incorporateValue(Aliasee);
00040   }
00041 
00042   // Get types from functions.
00043   SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
00044   for (Module::const_iterator FI = M.begin(), E = M.end(); FI != E; ++FI) {
00045     incorporateType(FI->getType());
00046 
00047     if (FI->hasPrefixData())
00048       incorporateValue(FI->getPrefixData());
00049 
00050     if (FI->hasPrologueData())
00051       incorporateValue(FI->getPrologueData());
00052 
00053     if (FI->hasPersonalityFn())
00054       incorporateValue(FI->getPersonalityFn());
00055 
00056     // First incorporate the arguments.
00057     for (Function::const_arg_iterator AI = FI->arg_begin(),
00058            AE = FI->arg_end(); AI != AE; ++AI)
00059       incorporateValue(AI);
00060 
00061     for (Function::const_iterator BB = FI->begin(), E = FI->end();
00062          BB != E;++BB)
00063       for (BasicBlock::const_iterator II = BB->begin(),
00064              E = BB->end(); II != E; ++II) {
00065         const Instruction &I = *II;
00066 
00067         // Incorporate the type of the instruction.
00068         incorporateType(I.getType());
00069 
00070         // Incorporate non-instruction operand types. (We are incorporating all
00071         // instructions with this loop.)
00072         for (User::const_op_iterator OI = I.op_begin(), OE = I.op_end();
00073              OI != OE; ++OI)
00074           if (*OI && !isa<Instruction>(OI))
00075             incorporateValue(*OI);
00076 
00077         // Incorporate types hiding in metadata.
00078         I.getAllMetadataOtherThanDebugLoc(MDForInst);
00079         for (unsigned i = 0, e = MDForInst.size(); i != e; ++i)
00080           incorporateMDNode(MDForInst[i].second);
00081 
00082         MDForInst.clear();
00083       }
00084   }
00085 
00086   for (Module::const_named_metadata_iterator I = M.named_metadata_begin(),
00087          E = M.named_metadata_end(); I != E; ++I) {
00088     const NamedMDNode *NMD = I;
00089     for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
00090       incorporateMDNode(NMD->getOperand(i));
00091   }
00092 }
00093 
00094 void TypeFinder::clear() {
00095   VisitedConstants.clear();
00096   VisitedTypes.clear();
00097   StructTypes.clear();
00098 }
00099 
00100 /// incorporateType - This method adds the type to the list of used structures
00101 /// if it's not in there already.
00102 void TypeFinder::incorporateType(Type *Ty) {
00103   // Check to see if we've already visited this type.
00104   if (!VisitedTypes.insert(Ty).second)
00105     return;
00106 
00107   SmallVector<Type *, 4> TypeWorklist;
00108   TypeWorklist.push_back(Ty);
00109   do {
00110     Ty = TypeWorklist.pop_back_val();
00111 
00112     // If this is a structure or opaque type, add a name for the type.
00113     if (StructType *STy = dyn_cast<StructType>(Ty))
00114       if (!OnlyNamed || STy->hasName())
00115         StructTypes.push_back(STy);
00116 
00117     // Add all unvisited subtypes to worklist for processing
00118     for (Type::subtype_reverse_iterator I = Ty->subtype_rbegin(),
00119                                         E = Ty->subtype_rend();
00120          I != E; ++I)
00121       if (VisitedTypes.insert(*I).second)
00122         TypeWorklist.push_back(*I);
00123   } while (!TypeWorklist.empty());
00124 }
00125 
00126 /// incorporateValue - This method is used to walk operand lists finding types
00127 /// hiding in constant expressions and other operands that won't be walked in
00128 /// other ways.  GlobalValues, basic blocks, instructions, and inst operands are
00129 /// all explicitly enumerated.
00130 void TypeFinder::incorporateValue(const Value *V) {
00131   if (const auto *M = dyn_cast<MetadataAsValue>(V)) {
00132     if (const auto *N = dyn_cast<MDNode>(M->getMetadata()))
00133       return incorporateMDNode(N);
00134     if (const auto *MDV = dyn_cast<ValueAsMetadata>(M->getMetadata()))
00135       return incorporateValue(MDV->getValue());
00136     return;
00137   }
00138 
00139   if (!isa<Constant>(V) || isa<GlobalValue>(V)) return;
00140 
00141   // Already visited?
00142   if (!VisitedConstants.insert(V).second)
00143     return;
00144 
00145   // Check this type.
00146   incorporateType(V->getType());
00147 
00148   // If this is an instruction, we incorporate it separately.
00149   if (isa<Instruction>(V))
00150     return;
00151 
00152   // Look in operands for types.
00153   const User *U = cast<User>(V);
00154   for (Constant::const_op_iterator I = U->op_begin(),
00155          E = U->op_end(); I != E;++I)
00156     incorporateValue(*I);
00157 }
00158 
00159 /// incorporateMDNode - This method is used to walk the operands of an MDNode to
00160 /// find types hiding within.
00161 void TypeFinder::incorporateMDNode(const MDNode *V) {
00162   // Already visited?
00163   if (!VisitedMetadata.insert(V).second)
00164     return;
00165 
00166   // Look in operands for types.
00167   for (unsigned i = 0, e = V->getNumOperands(); i != e; ++i) {
00168     Metadata *Op = V->getOperand(i);
00169     if (!Op)
00170       continue;
00171     if (auto *N = dyn_cast<MDNode>(Op)) {
00172       incorporateMDNode(N);
00173       continue;
00174     }
00175     if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
00176       incorporateValue(C->getValue());
00177       continue;
00178     }
00179   }
00180 }