lib/IR/TypeFinder.cpp

   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
  29 using namespace llvm;
  30
  31 void 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
  84 void 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.
  92 void 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.
 120 void 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.
 150 void 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 }