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
21using namespace llvm;
22
23// Search for virtual calls that call FPtr and add them to DevirtCalls.
24static void
25findCallsAtConstantOffset(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.
52static 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
74void 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
96void 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         CI->getCalledFunction()->getIntrinsicID() ==
104             Intrinsic::type_checked_load_relative);
105
106  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
107  if (!Offset) {
108    HasNonCallUses = true;
109    return;
110  }
111
112  for (const Use &U : CI->uses()) {
113    auto CIU = U.getUser();
114    if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
115      if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
116        LoadedPtrs.push_back(EVI);
117        continue;
118      }
119      if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
120        Preds.push_back(EVI);
121        continue;
122      }
123    }
124    HasNonCallUses = true;
125  }
126
127  for (Value *LoadedPtr : LoadedPtrs)
128    findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
129                              Offset->getZExtValue(), CI, DT);
130}
131
132Constant *llvm::getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
133                                   Constant *TopLevelGlobal) {
134  if (I->getType()->isPointerTy()) {
135    if (Offset == 0)
136      return I;
137    return nullptr;
138  }
139
140  const DataLayout &DL = M.getDataLayout();
141
142  if (auto *C = dyn_cast<ConstantStruct>(I)) {
143    const StructLayout *SL = DL.getStructLayout(C->getType());
144    if (Offset >= SL->getSizeInBytes())
145      return nullptr;
146
147    unsigned Op = SL->getElementContainingOffset(Offset);
148    return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
149                              Offset - SL->getElementOffset(Op), M,
150                              TopLevelGlobal);
151  }
152  if (auto *C = dyn_cast<ConstantArray>(I)) {
153    ArrayType *VTableTy = C->getType();
154    uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
155
156    unsigned Op = Offset / ElemSize;
157    if (Op >= C->getNumOperands())
158      return nullptr;
159
160    return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
161                              Offset % ElemSize, M, TopLevelGlobal);
162  }
163
164  // (Swift-specific) relative-pointer support starts here.
165  if (auto *CI = dyn_cast<ConstantInt>(I)) {
166    if (Offset == 0 && CI->isZero()) {
167      return I;
168    }
169  }
170  if (auto *C = dyn_cast<ConstantExpr>(I)) {
171    switch (C->getOpcode()) {
172    case Instruction::Trunc:
173    case Instruction::PtrToInt:
174      return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M,
175                                TopLevelGlobal);
176    case Instruction::Sub: {
177      auto *Operand0 = cast<Constant>(C->getOperand(0));
178      auto *Operand1 = cast<Constant>(C->getOperand(1));
179
180      auto StripGEP = [](Constant *C) {
181        auto *CE = dyn_cast<ConstantExpr>(C);
182        if (!CE)
183          return C;
184        if (CE->getOpcode() != Instruction::GetElementPtr)
185          return C;
186        return CE->getOperand(0);
187      };
188      auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M));
189
190      // Check that in the "sub (@a, @b)" expression, @b points back to the top
191      // level global (or a GEP thereof) that we're processing. Otherwise bail.
192      if (Operand1TargetGlobal != TopLevelGlobal)
193        return nullptr;
194
195      return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
196    }
197    default:
198      return nullptr;
199    }
200  }
201  return nullptr;
202}
203
204void llvm::replaceRelativePointerUsersWithZero(Function *F) {
205  for (auto *U : F->users()) {
206    auto *PtrExpr = dyn_cast<ConstantExpr>(U);
207    if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
208      continue;
209
210    for (auto *PtrToIntUser : PtrExpr->users()) {
211      auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser);
212      if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
213        continue;
214
215      SubExpr->replaceNonMetadataUsesWith(
216          ConstantInt::get(SubExpr->getType(), 0));
217    }
218  }
219}
220