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(GEP->op_begin() + 1, GEP->op_end()); 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 80 const Module *M = CI->getParent()->getParent()->getParent(); 81 82 // Find llvm.assume intrinsics for this llvm.type.test call. 83 for (const Use &CIU : CI->uses()) 84 if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser())) 85 Assumes.push_back(Assume); 86 87 // If we found any, search for virtual calls based on %p and add them to 88 // DevirtCalls. 89 if (!Assumes.empty()) 90 findLoadCallsAtConstantOffset( 91 M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT); 92 } 93 94 void llvm::findDevirtualizableCallsForTypeCheckedLoad( 95 SmallVectorImpl<DevirtCallSite> &DevirtCalls, 96 SmallVectorImpl<Instruction *> &LoadedPtrs, 97 SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses, 98 const CallInst *CI, DominatorTree &DT) { 99 assert(CI->getCalledFunction()->getIntrinsicID() == 100 Intrinsic::type_checked_load); 101 102 auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 103 if (!Offset) { 104 HasNonCallUses = true; 105 return; 106 } 107 108 for (const Use &U : CI->uses()) { 109 auto CIU = U.getUser(); 110 if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) { 111 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) { 112 LoadedPtrs.push_back(EVI); 113 continue; 114 } 115 if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) { 116 Preds.push_back(EVI); 117 continue; 118 } 119 } 120 HasNonCallUses = true; 121 } 122 123 for (Value *LoadedPtr : LoadedPtrs) 124 findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr, 125 Offset->getZExtValue(), CI, DT); 126 } 127 128 Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, 129 Constant *TopLevelGlobal) { 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 TopLevelGlobal); 147 } 148 if (auto *C = dyn_cast<ConstantArray>(I)) { 149 ArrayType *VTableTy = C->getType(); 150 uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType()); 151 152 unsigned Op = Offset / ElemSize; 153 if (Op >= C->getNumOperands()) 154 return nullptr; 155 156 return getPointerAtOffset(cast<Constant>(I->getOperand(Op)), 157 Offset % ElemSize, M, TopLevelGlobal); 158 } 159 160 // (Swift-specific) relative-pointer support starts here. 161 if (auto *CI = dyn_cast<ConstantInt>(I)) { 162 if (Offset == 0 && CI->getZExtValue() == 0) { 163 return I; 164 } 165 } 166 if (auto *C = dyn_cast<ConstantExpr>(I)) { 167 switch (C->getOpcode()) { 168 case Instruction::Trunc: 169 case Instruction::PtrToInt: 170 return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M, 171 TopLevelGlobal); 172 case Instruction::Sub: { 173 auto *Operand0 = cast<Constant>(C->getOperand(0)); 174 auto *Operand1 = cast<Constant>(C->getOperand(1)); 175 176 auto StripGEP = [](Constant *C) { 177 auto *CE = dyn_cast<ConstantExpr>(C); 178 if (!CE) 179 return C; 180 if (CE->getOpcode() != Instruction::GetElementPtr) 181 return C; 182 return CE->getOperand(0); 183 }; 184 auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M)); 185 186 // Check that in the "sub (@a, @b)" expression, @b points back to the top 187 // level global (or a GEP thereof) that we're processing. Otherwise bail. 188 if (Operand1TargetGlobal != TopLevelGlobal) 189 return nullptr; 190 191 return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal); 192 } 193 default: 194 return nullptr; 195 } 196 } 197 return nullptr; 198 } 199 200 void llvm::replaceRelativePointerUsersWithZero(Function *F) { 201 for (auto *U : F->users()) { 202 auto *PtrExpr = dyn_cast<ConstantExpr>(U); 203 if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt) 204 continue; 205 206 for (auto *PtrToIntUser : PtrExpr->users()) { 207 auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser); 208 if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub) 209 continue; 210 211 SubExpr->replaceNonMetadataUsesWith( 212 ConstantInt::get(SubExpr->getType(), 0)); 213 } 214 } 215 } 216