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 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. 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 } else if (auto *Call = dyn_cast<CallInst>(User)) { 71 if (Call->getIntrinsicID() == llvm::Intrinsic::load_relative) { 72 if (auto *LoadOffset = dyn_cast<ConstantInt>(Call->getOperand(1))) { 73 findCallsAtConstantOffset(DevirtCalls, nullptr, User, 74 Offset + LoadOffset->getSExtValue(), CI, 75 DT); 76 } 77 } 78 } 79 } 80 } 81 82 void 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>(CIU.getUser())) 95 Assumes.push_back(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, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT); 102 } 103 104 void 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>(CI->getArgOperand(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>(CIU)) { 123 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) { 124 LoadedPtrs.push_back(EVI); 125 continue; 126 } 127 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) { 128 Preds.push_back(EVI); 129 continue; 130 } 131 } 132 HasNonCallUses = true; 133 } 134 135 for (Value *LoadedPtr : LoadedPtrs) 136 findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr, 137 Offset->getZExtValue(), CI, DT); 138 } 139 140 Constant *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>(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>(I)) { 157 const StructLayout *SL = DL.getStructLayout(C->getType()); 158 if (Offset >= SL->getSizeInBytes()) 159 return nullptr; 160 161 unsigned Op = SL->getElementContainingOffset(Offset); 162 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)), 163 Offset - SL->getElementOffset(Op), M, 164 TopLevelGlobal); 165 } 166 if (auto *C = dyn_cast<ConstantArray>(I)) { 167 ArrayType *VTableTy = C->getType(); 168 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType()); 169 170 unsigned Op = Offset / ElemSize; 171 if (Op >= C->getNumOperands()) 172 return nullptr; 173 174 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)), 175 Offset % ElemSize, M, TopLevelGlobal); 176 } 177 178 // Relative-pointer support starts here. 179 if (auto *CI = dyn_cast<ConstantInt>(I)) { 180 if (Offset == 0 && CI->isZero()) { 181 return I; 182 } 183 } 184 if (auto *C = dyn_cast<ConstantExpr>(I)) { 185 switch (C->getOpcode()) { 186 case Instruction::Trunc: 187 case Instruction::PtrToInt: 188 return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M, 189 TopLevelGlobal); 190 case Instruction::Sub: { 191 auto *Operand0 = cast<Constant>(C->getOperand(0)); 192 auto *Operand1 = cast<Constant>(C->getOperand(1)); 193 194 auto StripGEP = [](Constant *C) { 195 auto *CE = dyn_cast<ConstantExpr>(C); 196 if (!CE) 197 return C; 198 if (CE->getOpcode() != Instruction::GetElementPtr) 199 return C; 200 return CE->getOperand(0); 201 }; 202 auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 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(Operand0, Offset, M, TopLevelGlobal); 210 } 211 default: 212 return nullptr; 213 } 214 } 215 return nullptr; 216 } 217 218 std::pair<Function *, Constant *> 219 llvm::getFunctionAtVTableOffset(GlobalVariable *GV, uint64_t Offset, 220 Module &M) { 221 Constant *Ptr = getPointerAtOffset(GV->getInitializer(), Offset, M, 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>(C); 228 auto A = dyn_cast<GlobalAlias>(C); 229 if (!Fn && A) 230 Fn = dyn_cast<Function>(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 238 static void replaceRelativePointerUserWithZero(User *U) { 239 auto *PtrExpr = dyn_cast<ConstantExpr>(U); 240 if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt) 241 return; 242 243 for (auto *PtrToIntUser : PtrExpr->users()) { 244 auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser); 245 if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub) 246 return; 247 248 SubExpr->replaceNonMetadataUsesWith( 249 ConstantInt::get(SubExpr->getType(), 0)); 250 } 251 } 252 253 void llvm::replaceRelativePointerUsersWithZero(Constant *C) { 254 for (auto *U : C->users()) { 255 if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(U)) 256 replaceRelativePointerUsersWithZero(Equiv); 257 else 258 replaceRelativePointerUserWithZero(U); 259 } 260 } 261