1//===- TypeFinder.cpp - Implement the TypeFinder class --------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the TypeFinder class for the IR library.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/IR/TypeFinder.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/IR/BasicBlock.h"
16#include "llvm/IR/Constant.h"
17#include "llvm/IR/DerivedTypes.h"
18#include "llvm/IR/Function.h"
19#include "llvm/IR/Instruction.h"
20#include "llvm/IR/Metadata.h"
21#include "llvm/IR/Module.h"
22#include "llvm/IR/Type.h"
23#include "llvm/IR/Use.h"
24#include "llvm/IR/User.h"
25#include "llvm/IR/Value.h"
26#include "llvm/Support/Casting.h"
27#include <utility>
28
29using namespace llvm;
30
31void TypeFinder::run(const Module &M, bool onlyNamed) {
32  OnlyNamed = onlyNamed;
33
34  // Get types from global variables.
35  for (const auto &G : M.globals()) {
36    incorporateType(G.getType());
37    if (G.hasInitializer())
38      incorporateValue(G.getInitializer());
39  }
40
41  // Get types from aliases.
42  for (const auto &A : M.aliases()) {
43    incorporateType(A.getType());
44    if (const Value *Aliasee = A.getAliasee())
45      incorporateValue(Aliasee);
46  }
47
48  // Get types from functions.
49  SmallVector<std::pair<unsigned, MDNode *>, 4> MDForInst;
50  for (const Function &FI : M) {
51    incorporateType(FI.getType());
52
53    for (const Use &U : FI.operands())
54      incorporateValue(U.get());
55
56    // First incorporate the arguments.
57    for (const auto &A : FI.args())
58      incorporateValue(&A);
59
60    for (const BasicBlock &BB : FI)
61      for (const Instruction &I : BB) {
62        // Incorporate the type of the instruction.
63        incorporateType(I.getType());
64
65        // Incorporate non-instruction operand types. (We are incorporating all
66        // instructions with this loop.)
67        for (const auto &O : I.operands())
68          if (&*O && !isa<Instruction>(&*O))
69            incorporateValue(&*O);
70
71        // Incorporate types hiding in metadata.
72        I.getAllMetadataOtherThanDebugLoc(MDForInst);
73        for (const auto &MD : MDForInst)
74          incorporateMDNode(MD.second);
75        MDForInst.clear();
76      }
77  }
78
79  for (const auto &NMD : M.named_metadata())
80    for (const auto *MDOp : NMD.operands())
81      incorporateMDNode(MDOp);
82}
83
84void 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.
92void 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.
120void 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 (const auto &I : U->operands())
145    incorporateValue(&*I);
146}
147
148/// incorporateMDNode - This method is used to walk the operands of an MDNode to
149/// find types hiding within.
150void TypeFinder::incorporateMDNode(const MDNode *V) {
151  // Already visited?
152  if (!VisitedMetadata.insert(V).second)
153    return;
154
155  // Look in operands for types.
156  for (Metadata *Op : V->operands()) {
157    if (!Op)
158      continue;
159    if (auto *N = dyn_cast<MDNode>(Op)) {
160      incorporateMDNode(N);
161      continue;
162    }
163    if (auto *C = dyn_cast<ConstantAsMetadata>(Op)) {
164      incorporateValue(C->getValue());
165      continue;
166    }
167  }
168}
169