1de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===- TypeMetadataUtils.cpp - Utilities related to type metadata ---------===// 2de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 3de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The LLVM Compiler Infrastructure 4de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 5de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This file is distributed under the University of Illinois Open Source 6de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// License. See LICENSE.TXT for details. 7de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 8de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 9de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 10de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This file contains functions that make it easier to manipulate type metadata 11de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// for devirtualization. 12de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 13de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===----------------------------------------------------------------------===// 14de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 15de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/TypeMetadataUtils.h" 16de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Constants.h" 17de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Intrinsics.h" 18de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/IR/Module.h" 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 20de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarusing namespace llvm; 21de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 22de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Search for virtual calls that call FPtr and add them to DevirtCalls. 23de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic void 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarfindCallsAtConstantOffset(SmallVectorImpl<DevirtCallSite> &DevirtCalls, 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool *HasNonCallUses, Value *FPtr, uint64_t Offset) { 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const Use &U : FPtr->uses()) { 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *User = U.getUser(); 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<BitCastInst>(User)) { 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset); 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (auto CI = dyn_cast<CallInst>(User)) { 31de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DevirtCalls.push_back({Offset, CI}); 32de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (auto II = dyn_cast<InvokeInst>(User)) { 33de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DevirtCalls.push_back({Offset, II}); 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (HasNonCallUses) { 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar *HasNonCallUses = true; 36de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 37de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Search for virtual calls that load from VPtr and add them to DevirtCalls. 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic void 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarfindLoadCallsAtConstantOffset(Module *M, 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<DevirtCallSite> &DevirtCalls, 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *VPtr, int64_t Offset) { 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const Use &U : VPtr->uses()) { 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Value *User = U.getUser(); 47de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (isa<BitCastInst>(User)) { 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset); 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (isa<LoadInst>(User)) { 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset); 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) { 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Take into account the GEP offset. 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) { 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end()); 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType( 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar GEP->getSourceElementType(), Indices); 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset); 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 59de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 61de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid llvm::findDevirtualizableCallsForTypeTest( 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<DevirtCallSite> &DevirtCalls, 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<CallInst *> &Assumes, CallInst *CI) { 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test); 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Module *M = CI->getParent()->getParent()->getParent(); 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Find llvm.assume intrinsics for this llvm.type.test call. 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const Use &CIU : CI->uses()) { 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto AssumeCI = dyn_cast<CallInst>(CIU.getUser()); 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (AssumeCI) { 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Function *F = AssumeCI->getCalledFunction(); 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (F && F->getIntrinsicID() == Intrinsic::assume) 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Assumes.push_back(AssumeCI); 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If we found any, search for virtual calls based on %p and add them to 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // DevirtCalls. 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Assumes.empty()) 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findLoadCallsAtConstantOffset(M, DevirtCalls, 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CI->getArgOperand(0)->stripPointerCasts(), 0); 85de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid llvm::findDevirtualizableCallsForTypeCheckedLoad( 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<DevirtCallSite> &DevirtCalls, 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<Instruction *> &LoadedPtrs, 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses, CallInst *CI) { 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(CI->getCalledFunction()->getIntrinsicID() == 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Intrinsic::type_checked_load); 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1)); 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Offset) { 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar HasNonCallUses = true; 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return; 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Use &U : CI->uses()) { 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto CIU = U.getUser(); 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) { 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) { 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LoadedPtrs.push_back(EVI); 105de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) { 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Preds.push_back(EVI); 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar HasNonCallUses = true; 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (Value *LoadedPtr : LoadedPtrs) 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr, 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Offset->getZExtValue()); 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 119