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
21 using namespace llvm;
22
23 // Search for virtual calls that call FPtr and add them to DevirtCalls.
24 static void
findCallsAtConstantOffset(SmallVectorImpl<DevirtCallSite> & DevirtCalls,bool * HasNonCallUses,Value * FPtr,uint64_t Offset,const CallInst * CI,DominatorTree & DT)25 findCallsAtConstantOffset(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>(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(CI, User))
37 continue;
38 if (isa<BitCastInst>(User)) {
39 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset, CI,
40 DT);
41 } else if (auto *CI = dyn_cast<CallInst>(User)) {
42 DevirtCalls.push_back({Offset, *CI});
43 } else if (auto *II = dyn_cast<InvokeInst>(User)) {
44 DevirtCalls.push_back({Offset, *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.
findLoadCallsAtConstantOffset(const Module * M,SmallVectorImpl<DevirtCallSite> & DevirtCalls,Value * VPtr,int64_t Offset,const CallInst * CI,DominatorTree & DT)52 static 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>(User)) {
58 findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset, CI, DT);
59 } else if (isa<LoadInst>(User)) {
60 findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset, CI, DT);
61 } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) {
62 // Take into account the GEP offset.
63 if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) {
64 SmallVector<Value *, 8> Indices(drop_begin(GEP->operands()));
65 int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
66 GEP->getSourceElementType(), Indices);
67 findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset,
68 CI, DT);
69 }
70 }
71 }
72 }
73
findDevirtualizableCallsForTypeTest(SmallVectorImpl<DevirtCallSite> & DevirtCalls,SmallVectorImpl<CallInst * > & Assumes,const CallInst * CI,DominatorTree & DT)74 void llvm::findDevirtualizableCallsForTypeTest(
75 SmallVectorImpl<DevirtCallSite> &DevirtCalls,
76 SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
77 DominatorTree &DT) {
78 assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test ||
79 CI->getCalledFunction()->getIntrinsicID() ==
80 Intrinsic::public_type_test);
81
82 const Module *M = CI->getParent()->getParent()->getParent();
83
84 // Find llvm.assume intrinsics for this llvm.type.test call.
85 for (const Use &CIU : CI->uses())
86 if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
87 Assumes.push_back(Assume);
88
89 // If we found any, search for virtual calls based on %p and add them to
90 // DevirtCalls.
91 if (!Assumes.empty())
92 findLoadCallsAtConstantOffset(
93 M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT);
94 }
95
findDevirtualizableCallsForTypeCheckedLoad(SmallVectorImpl<DevirtCallSite> & DevirtCalls,SmallVectorImpl<Instruction * > & LoadedPtrs,SmallVectorImpl<Instruction * > & Preds,bool & HasNonCallUses,const CallInst * CI,DominatorTree & DT)96 void llvm::findDevirtualizableCallsForTypeCheckedLoad(
97 SmallVectorImpl<DevirtCallSite> &DevirtCalls,
98 SmallVectorImpl<Instruction *> &LoadedPtrs,
99 SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
100 const CallInst *CI, DominatorTree &DT) {
101 assert(CI->getCalledFunction()->getIntrinsicID() ==
102 Intrinsic::type_checked_load);
103
104 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
105 if (!Offset) {
106 HasNonCallUses = true;
107 return;
108 }
109
110 for (const Use &U : CI->uses()) {
111 auto CIU = U.getUser();
112 if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
113 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
114 LoadedPtrs.push_back(EVI);
115 continue;
116 }
117 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
118 Preds.push_back(EVI);
119 continue;
120 }
121 }
122 HasNonCallUses = true;
123 }
124
125 for (Value *LoadedPtr : LoadedPtrs)
126 findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
127 Offset->getZExtValue(), CI, DT);
128 }
129
getPointerAtOffset(Constant * I,uint64_t Offset,Module & M,Constant * TopLevelGlobal)130 Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
131 Constant *TopLevelGlobal) {
132 if (I->getType()->isPointerTy()) {
133 if (Offset == 0)
134 return I;
135 return nullptr;
136 }
137
138 const DataLayout &DL = M.getDataLayout();
139
140 if (auto *C = dyn_cast<ConstantStruct>(I)) {
141 const StructLayout *SL = DL.getStructLayout(C->getType());
142 if (Offset >= SL->getSizeInBytes())
143 return nullptr;
144
145 unsigned Op = SL->getElementContainingOffset(Offset);
146 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
147 Offset - SL->getElementOffset(Op), M,
148 TopLevelGlobal);
149 }
150 if (auto *C = dyn_cast<ConstantArray>(I)) {
151 ArrayType *VTableTy = C->getType();
152 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
153
154 unsigned Op = Offset / ElemSize;
155 if (Op >= C->getNumOperands())
156 return nullptr;
157
158 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
159 Offset % ElemSize, M, TopLevelGlobal);
160 }
161
162 // (Swift-specific) relative-pointer support starts here.
163 if (auto *CI = dyn_cast<ConstantInt>(I)) {
164 if (Offset == 0 && CI->getZExtValue() == 0) {
165 return I;
166 }
167 }
168 if (auto *C = dyn_cast<ConstantExpr>(I)) {
169 switch (C->getOpcode()) {
170 case Instruction::Trunc:
171 case Instruction::PtrToInt:
172 return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M,
173 TopLevelGlobal);
174 case Instruction::Sub: {
175 auto *Operand0 = cast<Constant>(C->getOperand(0));
176 auto *Operand1 = cast<Constant>(C->getOperand(1));
177
178 auto StripGEP = [](Constant *C) {
179 auto *CE = dyn_cast<ConstantExpr>(C);
180 if (!CE)
181 return C;
182 if (CE->getOpcode() != Instruction::GetElementPtr)
183 return C;
184 return CE->getOperand(0);
185 };
186 auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M));
187
188 // Check that in the "sub (@a, @b)" expression, @b points back to the top
189 // level global (or a GEP thereof) that we're processing. Otherwise bail.
190 if (Operand1TargetGlobal != TopLevelGlobal)
191 return nullptr;
192
193 return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
194 }
195 default:
196 return nullptr;
197 }
198 }
199 return nullptr;
200 }
201
replaceRelativePointerUsersWithZero(Function * F)202 void llvm::replaceRelativePointerUsersWithZero(Function *F) {
203 for (auto *U : F->users()) {
204 auto *PtrExpr = dyn_cast<ConstantExpr>(U);
205 if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
206 continue;
207
208 for (auto *PtrToIntUser : PtrExpr->users()) {
209 auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser);
210 if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
211 continue;
212
213 SubExpr->replaceNonMetadataUsesWith(
214 ConstantInt::get(SubExpr->getType(), 0));
215 }
216 }
217 }
218