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