1//===- TypeMetadataUtils.cpp - Utilities related to type metadata ---------===//
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 contains functions that make it easier to manipulate type metadata
10// for devirtualization.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/TypeMetadataUtils.h"
15#include "llvm/IR/Constants.h"
16#include "llvm/IR/Dominators.h"
17#include "llvm/IR/Instructions.h"
18#include "llvm/IR/IntrinsicInst.h"
19#include "llvm/IR/Module.h"
20
21using namespace llvm;
22
23// Search for virtual calls that call FPtr and add them to DevirtCalls.
24static void
25findCallsAtConstantOffset(SmallVectorImpl<DevirtCallSite> &DevirtCalls,
26 bool *HasNonCallUses, Value *FPtr, uint64_t Offset,
27 const CallInst *CI, DominatorTree &DT) {
28 for (const Use &U : FPtr->uses()) {
29 Instruction *User = cast<Instruction>(Val: U.getUser());
30 // Ignore this instruction if it is not dominated by the type intrinsic
31 // being analyzed. Otherwise we may transform a call sharing the same
32 // vtable pointer incorrectly. Specifically, this situation can arise
33 // after indirect call promotion and inlining, where we may have uses
34 // of the vtable pointer guarded by a function pointer check, and a fallback
35 // indirect call.
36 if (!DT.dominates(Def: CI, User))
37 continue;
38 if (isa<BitCastInst>(Val: User)) {
39 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, FPtr: User, Offset, CI,
40 DT);
41 } else if (auto *CI = dyn_cast<CallInst>(Val: User)) {
42 DevirtCalls.push_back(Elt: {.Offset: Offset, .CB: *CI});
43 } else if (auto *II = dyn_cast<InvokeInst>(Val: User)) {
44 DevirtCalls.push_back(Elt: {.Offset: Offset, .CB: *II});
45 } else if (HasNonCallUses) {
46 *HasNonCallUses = true;
47 }
48 }
49}
50
51// Search for virtual calls that load from VPtr and add them to DevirtCalls.
52static void findLoadCallsAtConstantOffset(
53 const Module *M, SmallVectorImpl<DevirtCallSite> &DevirtCalls, Value *VPtr,
54 int64_t Offset, const CallInst *CI, DominatorTree &DT) {
55 for (const Use &U : VPtr->uses()) {
56 Value *User = U.getUser();
57 if (isa<BitCastInst>(Val: User)) {
58 findLoadCallsAtConstantOffset(M, DevirtCalls, VPtr: User, Offset, CI, DT);
59 } else if (isa<LoadInst>(Val: User)) {
60 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses: nullptr, FPtr: User, Offset, CI, DT);
61 } else if (auto GEP = dyn_cast<GetElementPtrInst>(Val: User)) {
62 // Take into account the GEP offset.
63 if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) {
64 SmallVector<Value *, 8> Indices(drop_begin(RangeOrContainer: GEP->operands()));
65 int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
66 ElemTy: GEP->getSourceElementType(), Indices);
67 findLoadCallsAtConstantOffset(M, DevirtCalls, VPtr: User, Offset: Offset + GEPOffset,
68 CI, DT);
69 }
70 } else if (auto *Call = dyn_cast<CallInst>(Val: User)) {
71 if (Call->getIntrinsicID() == llvm::Intrinsic::load_relative) {
72 if (auto *LoadOffset = dyn_cast<ConstantInt>(Val: Call->getOperand(i_nocapture: 1))) {
73 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses: nullptr, FPtr: User,
74 Offset: Offset + LoadOffset->getSExtValue(), CI,
75 DT);
76 }
77 }
78 }
79 }
80}
81
82void llvm::findDevirtualizableCallsForTypeTest(
83 SmallVectorImpl<DevirtCallSite> &DevirtCalls,
84 SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
85 DominatorTree &DT) {
86 assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test ||
87 CI->getCalledFunction()->getIntrinsicID() ==
88 Intrinsic::public_type_test);
89
90 const Module *M = CI->getParent()->getParent()->getParent();
91
92 // Find llvm.assume intrinsics for this llvm.type.test call.
93 for (const Use &CIU : CI->uses())
94 if (auto *Assume = dyn_cast<AssumeInst>(Val: CIU.getUser()))
95 Assumes.push_back(Elt: Assume);
96
97 // If we found any, search for virtual calls based on %p and add them to
98 // DevirtCalls.
99 if (!Assumes.empty())
100 findLoadCallsAtConstantOffset(
101 M, DevirtCalls, VPtr: CI->getArgOperand(i: 0)->stripPointerCasts(), Offset: 0, CI, DT);
102}
103
104void llvm::findDevirtualizableCallsForTypeCheckedLoad(
105 SmallVectorImpl<DevirtCallSite> &DevirtCalls,
106 SmallVectorImpl<Instruction *> &LoadedPtrs,
107 SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
108 const CallInst *CI, DominatorTree &DT) {
109 assert(CI->getCalledFunction()->getIntrinsicID() ==
110 Intrinsic::type_checked_load ||
111 CI->getCalledFunction()->getIntrinsicID() ==
112 Intrinsic::type_checked_load_relative);
113
114 auto *Offset = dyn_cast<ConstantInt>(Val: CI->getArgOperand(i: 1));
115 if (!Offset) {
116 HasNonCallUses = true;
117 return;
118 }
119
120 for (const Use &U : CI->uses()) {
121 auto CIU = U.getUser();
122 if (auto EVI = dyn_cast<ExtractValueInst>(Val: CIU)) {
123 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
124 LoadedPtrs.push_back(Elt: EVI);
125 continue;
126 }
127 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
128 Preds.push_back(Elt: EVI);
129 continue;
130 }
131 }
132 HasNonCallUses = true;
133 }
134
135 for (Value *LoadedPtr : LoadedPtrs)
136 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses: &HasNonCallUses, FPtr: LoadedPtr,
137 Offset: Offset->getZExtValue(), CI, DT);
138}
139
140Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
141 Constant *TopLevelGlobal) {
142 // TODO: Ideally it would be the caller who knows if it's appropriate to strip
143 // the DSOLocalEquicalent. More generally, it would feel more appropriate to
144 // have two functions that handle absolute and relative pointers separately.
145 if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(Val: I))
146 I = Equiv->getGlobalValue();
147
148 if (I->getType()->isPointerTy()) {
149 if (Offset == 0)
150 return I;
151 return nullptr;
152 }
153
154 const DataLayout &DL = M.getDataLayout();
155
156 if (auto *C = dyn_cast<ConstantStruct>(Val: I)) {
157 const StructLayout *SL = DL.getStructLayout(Ty: C->getType());
158 if (Offset >= SL->getSizeInBytes())
159 return nullptr;
160
161 unsigned Op = SL->getElementContainingOffset(FixedOffset: Offset);
162 return getPointerAtOffset(I: cast<Constant>(Val: I->getOperand(i: Op)),
163 Offset: Offset - SL->getElementOffset(Idx: Op), M,
164 TopLevelGlobal);
165 }
166 if (auto *C = dyn_cast<ConstantArray>(Val: I)) {
167 ArrayType *VTableTy = C->getType();
168 uint64_t ElemSize = DL.getTypeAllocSize(Ty: VTableTy->getElementType());
169
170 unsigned Op = Offset / ElemSize;
171 if (Op >= C->getNumOperands())
172 return nullptr;
173
174 return getPointerAtOffset(I: cast<Constant>(Val: I->getOperand(i: Op)),
175 Offset: Offset % ElemSize, M, TopLevelGlobal);
176 }
177
178 // Relative-pointer support starts here.
179 if (auto *CI = dyn_cast<ConstantInt>(Val: I)) {
180 if (Offset == 0 && CI->isZero()) {
181 return I;
182 }
183 }
184 if (auto *C = dyn_cast<ConstantExpr>(Val: I)) {
185 switch (C->getOpcode()) {
186 case Instruction::Trunc:
187 case Instruction::PtrToInt:
188 return getPointerAtOffset(I: cast<Constant>(Val: C->getOperand(i_nocapture: 0)), Offset, M,
189 TopLevelGlobal);
190 case Instruction::Sub: {
191 auto *Operand0 = cast<Constant>(Val: C->getOperand(i_nocapture: 0));
192 auto *Operand1 = cast<Constant>(Val: C->getOperand(i_nocapture: 1));
193
194 auto StripGEP = [](Constant *C) {
195 auto *CE = dyn_cast<ConstantExpr>(Val: C);
196 if (!CE)
197 return C;
198 if (CE->getOpcode() != Instruction::GetElementPtr)
199 return C;
200 return CE->getOperand(i_nocapture: 0);
201 };
202 auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(I: Operand1, Offset: 0, M));
203
204 // Check that in the "sub (@a, @b)" expression, @b points back to the top
205 // level global (or a GEP thereof) that we're processing. Otherwise bail.
206 if (Operand1TargetGlobal != TopLevelGlobal)
207 return nullptr;
208
209 return getPointerAtOffset(I: Operand0, Offset, M, TopLevelGlobal);
210 }
211 default:
212 return nullptr;
213 }
214 }
215 return nullptr;
216}
217
218std::pair<Function *, Constant *>
219llvm::getFunctionAtVTableOffset(GlobalVariable *GV, uint64_t Offset,
220 Module &M) {
221 Constant *Ptr = getPointerAtOffset(I: GV->getInitializer(), Offset, M, TopLevelGlobal: GV);
222 if (!Ptr)
223 return std::pair<Function *, Constant *>(nullptr, nullptr);
224
225 auto C = Ptr->stripPointerCasts();
226 // Make sure this is a function or alias to a function.
227 auto Fn = dyn_cast<Function>(Val: C);
228 auto A = dyn_cast<GlobalAlias>(Val: C);
229 if (!Fn && A)
230 Fn = dyn_cast<Function>(Val: A->getAliasee());
231
232 if (!Fn)
233 return std::pair<Function *, Constant *>(nullptr, nullptr);
234
235 return std::pair<Function *, Constant *>(Fn, C);
236}
237
238static void replaceRelativePointerUserWithZero(User *U) {
239 auto *PtrExpr = dyn_cast<ConstantExpr>(Val: U);
240 if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
241 return;
242
243 for (auto *PtrToIntUser : PtrExpr->users()) {
244 auto *SubExpr = dyn_cast<ConstantExpr>(Val: PtrToIntUser);
245 if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
246 return;
247
248 SubExpr->replaceNonMetadataUsesWith(
249 V: ConstantInt::get(Ty: SubExpr->getType(), V: 0));
250 }
251}
252
253void llvm::replaceRelativePointerUsersWithZero(Constant *C) {
254 for (auto *U : C->users()) {
255 if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(Val: U))
256 replaceRelativePointerUsersWithZero(C: Equiv);
257 else
258 replaceRelativePointerUserWithZero(U);
259 }
260}
261