1//===- TypeMetadataUtils.cpp - Utilities related to type metadata ---------===//
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 contains functions that make it easier to manipulate type metadata
11// for devirtualization.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/TypeMetadataUtils.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/Intrinsics.h"
18#include "llvm/IR/Module.h"
19
20using namespace llvm;
21
22// Search for virtual calls that call FPtr and add them to DevirtCalls.
23static void
24findCallsAtConstantOffset(SmallVectorImpl<DevirtCallSite> &DevirtCalls,
25                          bool *HasNonCallUses, Value *FPtr, uint64_t Offset) {
26  for (const Use &U : FPtr->uses()) {
27    Value *User = U.getUser();
28    if (isa<BitCastInst>(User)) {
29      findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset);
30    } else if (auto CI = dyn_cast<CallInst>(User)) {
31      DevirtCalls.push_back({Offset, CI});
32    } else if (auto II = dyn_cast<InvokeInst>(User)) {
33      DevirtCalls.push_back({Offset, II});
34    } else if (HasNonCallUses) {
35      *HasNonCallUses = true;
36    }
37  }
38}
39
40// Search for virtual calls that load from VPtr and add them to DevirtCalls.
41static void
42findLoadCallsAtConstantOffset(Module *M,
43                              SmallVectorImpl<DevirtCallSite> &DevirtCalls,
44                              Value *VPtr, int64_t Offset) {
45  for (const Use &U : VPtr->uses()) {
46    Value *User = U.getUser();
47    if (isa<BitCastInst>(User)) {
48      findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset);
49    } else if (isa<LoadInst>(User)) {
50      findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset);
51    } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) {
52      // Take into account the GEP offset.
53      if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) {
54        SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
55        int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
56            GEP->getSourceElementType(), Indices);
57        findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset);
58      }
59    }
60  }
61}
62
63void llvm::findDevirtualizableCallsForTypeTest(
64    SmallVectorImpl<DevirtCallSite> &DevirtCalls,
65    SmallVectorImpl<CallInst *> &Assumes, CallInst *CI) {
66  assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test);
67
68  Module *M = CI->getParent()->getParent()->getParent();
69
70  // Find llvm.assume intrinsics for this llvm.type.test call.
71  for (const Use &CIU : CI->uses()) {
72    auto AssumeCI = dyn_cast<CallInst>(CIU.getUser());
73    if (AssumeCI) {
74      Function *F = AssumeCI->getCalledFunction();
75      if (F && F->getIntrinsicID() == Intrinsic::assume)
76        Assumes.push_back(AssumeCI);
77    }
78  }
79
80  // If we found any, search for virtual calls based on %p and add them to
81  // DevirtCalls.
82  if (!Assumes.empty())
83    findLoadCallsAtConstantOffset(M, DevirtCalls,
84                                  CI->getArgOperand(0)->stripPointerCasts(), 0);
85}
86
87void llvm::findDevirtualizableCallsForTypeCheckedLoad(
88    SmallVectorImpl<DevirtCallSite> &DevirtCalls,
89    SmallVectorImpl<Instruction *> &LoadedPtrs,
90    SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses, CallInst *CI) {
91  assert(CI->getCalledFunction()->getIntrinsicID() ==
92         Intrinsic::type_checked_load);
93
94  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
95  if (!Offset) {
96    HasNonCallUses = true;
97    return;
98  }
99
100  for (Use &U : CI->uses()) {
101    auto CIU = U.getUser();
102    if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
103      if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
104        LoadedPtrs.push_back(EVI);
105        continue;
106      }
107      if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
108        Preds.push_back(EVI);
109        continue;
110      }
111    }
112    HasNonCallUses = true;
113  }
114
115  for (Value *LoadedPtr : LoadedPtrs)
116    findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
117                              Offset->getZExtValue());
118}
119