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