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 } 71 } 72 } 73 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 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 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 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