llvm/lib/Analysis/TypeMetadataUtils.cpp

   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     } else if (auto *Call = dyn_cast<CallInst>(User)) {
  71       if (Call->getIntrinsicID() == llvm::Intrinsic::load_relative) {
  72         if (auto *LoadOffset = dyn_cast<ConstantInt>(Call->getOperand(1))) {
  73           findCallsAtConstantOffset(DevirtCalls, nullptr, User,
  74                                     Offset + LoadOffset->getSExtValue(), CI,
  75                                     DT);
  76         }
  77       }
  78     }
  79   }
  80 }
  81
  82 void llvm::findDevirtualizableCallsForTypeTest(
  83     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
  84     SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
  85     DominatorTree &DT) {
  86   assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test ||
  87          CI->getCalledFunction()->getIntrinsicID() ==
  88              Intrinsic::public_type_test);
  89
  90   const Module *M = CI->getParent()->getParent()->getParent();
  91
  92   // Find llvm.assume intrinsics for this llvm.type.test call.
  93   for (const Use &CIU : CI->uses())
  94     if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
  95       Assumes.push_back(Assume);
  96
  97   // If we found any, search for virtual calls based on %p and add them to
  98   // DevirtCalls.
  99   if (!Assumes.empty())
 100     findLoadCallsAtConstantOffset(
 101         M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT);
 102 }
 103
 104 void llvm::findDevirtualizableCallsForTypeCheckedLoad(
 105     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
 106     SmallVectorImpl<Instruction *> &LoadedPtrs,
 107     SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
 108     const CallInst *CI, DominatorTree &DT) {
 109   assert(CI->getCalledFunction()->getIntrinsicID() ==
 110              Intrinsic::type_checked_load ||
 111          CI->getCalledFunction()->getIntrinsicID() ==
 112              Intrinsic::type_checked_load_relative);
 113
 114   auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
 115   if (!Offset) {
 116     HasNonCallUses = true;
 117     return;
 118   }
 119
 120   for (const Use &U : CI->uses()) {
 121     auto CIU = U.getUser();
 122     if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
 123       if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
 124         LoadedPtrs.push_back(EVI);
 125         continue;
 126       }
 127       if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
 128         Preds.push_back(EVI);
 129         continue;
 130       }
 131     }
 132     HasNonCallUses = true;
 133   }
 134
 135   for (Value *LoadedPtr : LoadedPtrs)
 136     findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
 137                               Offset->getZExtValue(), CI, DT);
 138 }
 139
 140 Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
 141                                    Constant *TopLevelGlobal) {
 142   // TODO: Ideally it would be the caller who knows if it's appropriate to strip
 143   // the DSOLocalEquicalent. More generally, it would feel more appropriate to
 144   // have two functions that handle absolute and relative pointers separately.
 145   if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(I))
 146     I = Equiv->getGlobalValue();
 147
 148   if (I->getType()->isPointerTy()) {
 149     if (Offset == 0)
 150       return I;
 151     return nullptr;
 152   }
 153
 154   const DataLayout &DL = M.getDataLayout();
 155
 156   if (auto *C = dyn_cast<ConstantStruct>(I)) {
 157     const StructLayout *SL = DL.getStructLayout(C->getType());
 158     if (Offset >= SL->getSizeInBytes())
 159       return nullptr;
 160
 161     unsigned Op = SL->getElementContainingOffset(Offset);
 162     return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
 163                               Offset - SL->getElementOffset(Op), M,
 164                               TopLevelGlobal);
 165   }
 166   if (auto *C = dyn_cast<ConstantArray>(I)) {
 167     ArrayType *VTableTy = C->getType();
 168     uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
 169
 170     unsigned Op = Offset / ElemSize;
 171     if (Op >= C->getNumOperands())
 172       return nullptr;
 173
 174     return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
 175                               Offset % ElemSize, M, TopLevelGlobal);
 176   }
 177
 178   // Relative-pointer support starts here.
 179   if (auto *CI = dyn_cast<ConstantInt>(I)) {
 180     if (Offset == 0 && CI->isZero()) {
 181       return I;
 182     }
 183   }
 184   if (auto *C = dyn_cast<ConstantExpr>(I)) {
 185     switch (C->getOpcode()) {
 186     case Instruction::Trunc:
 187     case Instruction::PtrToInt:
 188       return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M,
 189                                 TopLevelGlobal);
 190     case Instruction::Sub: {
 191       auto *Operand0 = cast<Constant>(C->getOperand(0));
 192       auto *Operand1 = cast<Constant>(C->getOperand(1));
 193
 194       auto StripGEP = [](Constant *C) {
 195         auto *CE = dyn_cast<ConstantExpr>(C);
 196         if (!CE)
 197           return C;
 198         if (CE->getOpcode() != Instruction::GetElementPtr)
 199           return C;
 200         return CE->getOperand(0);
 201       };
 202       auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M));
 203
 204       // Check that in the "sub (@a, @b)" expression, @b points back to the top
 205       // level global (or a GEP thereof) that we're processing. Otherwise bail.
 206       if (Operand1TargetGlobal != TopLevelGlobal)
 207         return nullptr;
 208
 209       return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
 210     }
 211     default:
 212       return nullptr;
 213     }
 214   }
 215   return nullptr;
 216 }
 217
 218 std::pair<Function *, Constant *>
 219 llvm::getFunctionAtVTableOffset(GlobalVariable *GV, uint64_t Offset,
 220                                 Module &M) {
 221   Constant *Ptr = getPointerAtOffset(GV->getInitializer(), Offset, M, GV);
 222   if (!Ptr)
 223     return std::pair<Function *, Constant *>(nullptr, nullptr);
 224
 225   auto C = Ptr->stripPointerCasts();
 226   // Make sure this is a function or alias to a function.
 227   auto Fn = dyn_cast<Function>(C);
 228   auto A = dyn_cast<GlobalAlias>(C);
 229   if (!Fn && A)
 230     Fn = dyn_cast<Function>(A->getAliasee());
 231
 232   if (!Fn)
 233     return std::pair<Function *, Constant *>(nullptr, nullptr);
 234
 235   return std::pair<Function *, Constant *>(Fn, C);
 236 }
 237
 238 static void replaceRelativePointerUserWithZero(User *U) {
 239   auto *PtrExpr = dyn_cast<ConstantExpr>(U);
 240   if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
 241     return;
 242
 243   for (auto *PtrToIntUser : PtrExpr->users()) {
 244     auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser);
 245     if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
 246       return;
 247
 248     SubExpr->replaceNonMetadataUsesWith(
 249         ConstantInt::get(SubExpr->getType(), 0));
 250   }
 251 }
 252
 253 void llvm::replaceRelativePointerUsersWithZero(Constant *C) {
 254   for (auto *U : C->users()) {
 255     if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(U))
 256       replaceRelativePointerUsersWithZero(Equiv);
 257     else
 258       replaceRelativePointerUserWithZero(U);
 259   }
 260 }