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