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 
20 using namespace llvm;
21 
22 // Search for virtual calls that call FPtr and add them to DevirtCalls.
23 static void
24 findCallsAtConstantOffset(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.
41 static void
42 findLoadCallsAtConstantOffset(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 
63 void 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     if (auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser())) {
73       Function *F = AssumeCI->getCalledFunction();
74       if (F && F->getIntrinsicID() == Intrinsic::assume)
75         Assumes.push_back(AssumeCI);
76     }
77   }
78 
79   // If we found any, search for virtual calls based on %p and add them to
80   // DevirtCalls.
81   if (!Assumes.empty())
82     findLoadCallsAtConstantOffset(M, DevirtCalls,
83                                   CI->getArgOperand(0)->stripPointerCasts(), 0);
84 }
85 
86 void llvm::findDevirtualizableCallsForTypeCheckedLoad(
87     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
88     SmallVectorImpl<Instruction *> &LoadedPtrs,
89     SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses, CallInst *CI) {
90   assert(CI->getCalledFunction()->getIntrinsicID() ==
91          Intrinsic::type_checked_load);
92 
93   auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
94   if (!Offset) {
95     HasNonCallUses = true;
96     return;
97   }
98 
99   for (Use &U : CI->uses()) {
100     auto CIU = U.getUser();
101     if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
102       if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
103         LoadedPtrs.push_back(EVI);
104         continue;
105       }
106       if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
107         Preds.push_back(EVI);
108         continue;
109       }
110     }
111     HasNonCallUses = true;
112   }
113 
114   for (Value *LoadedPtr : LoadedPtrs)
115     findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
116                               Offset->getZExtValue());
117 }
118