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/Intrinsics.h" 20 #include "llvm/IR/Module.h" 21 22 using namespace llvm; 23 24 // Search for virtual calls that call FPtr and add them to DevirtCalls. 25 static void 26 findCallsAtConstantOffset(SmallVectorImpl<DevirtCallSite> &DevirtCalls, 27 bool *HasNonCallUses, Value *FPtr, uint64_t Offset, 28 const CallInst *CI, DominatorTree &DT) { 29 for (const Use &U : FPtr->uses()) { 30 Instruction *User = cast<Instruction>(U.getUser()); 31 // Ignore this instruction if it is not dominated by the type intrinsic 32 // being analyzed. Otherwise we may transform a call sharing the same 33 // vtable pointer incorrectly. Specifically, this situation can arise 34 // after indirect call promotion and inlining, where we may have uses 35 // of the vtable pointer guarded by a function pointer check, and a fallback 36 // indirect call. 37 if (!DT.dominates(CI, User)) 38 continue; 39 if (isa<BitCastInst>(User)) { 40 findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset, CI, 41 DT); 42 } else if (auto *CI = dyn_cast<CallInst>(User)) { 43 DevirtCalls.push_back({Offset, *CI}); 44 } else if (auto *II = dyn_cast<InvokeInst>(User)) { 45 DevirtCalls.push_back({Offset, *II}); 46 } else if (HasNonCallUses) { 47 *HasNonCallUses = true; 48 } 49 } 50 } 51 52 // Search for virtual calls that load from VPtr and add them to DevirtCalls. 53 static void findLoadCallsAtConstantOffset( 54 const Module *M, SmallVectorImpl<DevirtCallSite> &DevirtCalls, Value *VPtr, 55 int64_t Offset, const CallInst *CI, DominatorTree &DT) { 56 for (const Use &U : VPtr->uses()) { 57 Value *User = U.getUser(); 58 if (isa<BitCastInst>(User)) { 59 findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset, CI, DT); 60 } else if (isa<LoadInst>(User)) { 61 findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset, CI, DT); 62 } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) { 63 // Take into account the GEP offset. 64 if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) { 65 SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end()); 66 int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType( 67 GEP->getSourceElementType(), Indices); 68 findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset, 69 CI, DT); 70 } 71 } 72 } 73 } 74 75 void llvm::findDevirtualizableCallsForTypeTest( 76 SmallVectorImpl<DevirtCallSite> &DevirtCalls, 77 SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI, 78 DominatorTree &DT) { 79 assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test); 80 81 const Module *M = CI->getParent()->getParent()->getParent(); 82 83 // Find llvm.assume intrinsics for this llvm.type.test call. 84 for (const Use &CIU : CI->uses()) 85 if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser())) 86 Assumes.push_back(Assume); 87 88 // If we found any, search for virtual calls based on %p and add them to 89 // DevirtCalls. 90 if (!Assumes.empty()) 91 findLoadCallsAtConstantOffset( 92 M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT); 93 } 94 95 void llvm::findDevirtualizableCallsForTypeCheckedLoad( 96 SmallVectorImpl<DevirtCallSite> &DevirtCalls, 97 SmallVectorImpl<Instruction *> &LoadedPtrs, 98 SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses, 99 const CallInst *CI, DominatorTree &DT) { 100 assert(CI->getCalledFunction()->getIntrinsicID() == 101 Intrinsic::type_checked_load); 102 103 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 104 if (!Offset) { 105 HasNonCallUses = true; 106 return; 107 } 108 109 for (const Use &U : CI->uses()) { 110 auto CIU = U.getUser(); 111 if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) { 112 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) { 113 LoadedPtrs.push_back(EVI); 114 continue; 115 } 116 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) { 117 Preds.push_back(EVI); 118 continue; 119 } 120 } 121 HasNonCallUses = true; 122 } 123 124 for (Value *LoadedPtr : LoadedPtrs) 125 findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr, 126 Offset->getZExtValue(), CI, DT); 127 } 128 129 Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M) { 130 if (I->getType()->isPointerTy()) { 131 if (Offset == 0) 132 return I; 133 return nullptr; 134 } 135 136 const DataLayout &DL = M.getDataLayout(); 137 138 if (auto *C = dyn_cast<ConstantStruct>(I)) { 139 const StructLayout *SL = DL.getStructLayout(C->getType()); 140 if (Offset >= SL->getSizeInBytes()) 141 return nullptr; 142 143 unsigned Op = SL->getElementContainingOffset(Offset); 144 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)), 145 Offset - SL->getElementOffset(Op), M); 146 } 147 if (auto *C = dyn_cast<ConstantArray>(I)) { 148 ArrayType *VTableTy = C->getType(); 149 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType()); 150 151 unsigned Op = Offset / ElemSize; 152 if (Op >= C->getNumOperands()) 153 return nullptr; 154 155 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)), 156 Offset % ElemSize, M); 157 } 158 return nullptr; 159 } 160