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