LLVM  10.0.0svn
TypeMetadataUtils.cpp
Go to the documentation of this file.
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 
15 #include "llvm/IR/Constants.h"
16 #include "llvm/IR/Dominators.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
25  bool *HasNonCallUses, Value *FPtr, uint64_t Offset,
26  const CallInst *CI, DominatorTree &DT) {
27  for (const Use &U : FPtr->uses()) {
28  Instruction *User = cast<Instruction>(U.getUser());
29  // Ignore this instruction if it is not dominated by the type intrinsic
30  // being analyzed. Otherwise we may transform a call sharing the same
31  // vtable pointer incorrectly. Specifically, this situation can arise
32  // after indirect call promotion and inlining, where we may have uses
33  // of the vtable pointer guarded by a function pointer check, and a fallback
34  // indirect call.
35  if (!DT.dominates(CI, User))
36  continue;
37  if (isa<BitCastInst>(User)) {
38  findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset, CI,
39  DT);
40  } else if (auto CI = dyn_cast<CallInst>(User)) {
41  DevirtCalls.push_back({Offset, CI});
42  } else if (auto II = dyn_cast<InvokeInst>(User)) {
43  DevirtCalls.push_back({Offset, II});
44  } else if (HasNonCallUses) {
45  *HasNonCallUses = true;
46  }
47  }
48 }
49 
50 // Search for virtual calls that load from VPtr and add them to DevirtCalls.
52  const Module *M, SmallVectorImpl<DevirtCallSite> &DevirtCalls, Value *VPtr,
53  int64_t Offset, const CallInst *CI, DominatorTree &DT) {
54  for (const Use &U : VPtr->uses()) {
55  Value *User = U.getUser();
56  if (isa<BitCastInst>(User)) {
57  findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset, CI, DT);
58  } else if (isa<LoadInst>(User)) {
59  findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset, CI, DT);
60  } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) {
61  // Take into account the GEP offset.
62  if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) {
63  SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
64  int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
65  GEP->getSourceElementType(), Indices);
66  findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset,
67  CI, DT);
68  }
69  }
70  }
71 }
72 
75  SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
76  DominatorTree &DT) {
77  assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test);
78 
79  const Module *M = CI->getParent()->getParent()->getParent();
80 
81  // Find llvm.assume intrinsics for this llvm.type.test call.
82  for (const Use &CIU : CI->uses()) {
83  if (auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser())) {
84  Function *F = AssumeCI->getCalledFunction();
85  if (F && F->getIntrinsicID() == Intrinsic::assume)
86  Assumes.push_back(AssumeCI);
87  }
88  }
89 
90  // If we found any, search for virtual calls based on %p and add them to
91  // DevirtCalls.
92  if (!Assumes.empty())
94  M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT);
95 }
96 
100  SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
101  const CallInst *CI, DominatorTree &DT) {
103  Intrinsic::type_checked_load);
104 
105  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
106  if (!Offset) {
107  HasNonCallUses = true;
108  return;
109  }
110 
111  for (const Use &U : CI->uses()) {
112  auto CIU = U.getUser();
113  if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
114  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
115  LoadedPtrs.push_back(EVI);
116  continue;
117  }
118  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
119  Preds.push_back(EVI);
120  continue;
121  }
122  }
123  HasNonCallUses = true;
124  }
125 
126  for (Value *LoadedPtr : LoadedPtrs)
127  findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
128  Offset->getZExtValue(), CI, DT);
129 }
130 
132  if (I->getType()->isPointerTy()) {
133  if (Offset == 0)
134  return I;
135  return nullptr;
136  }
137 
138  const DataLayout &DL = M.getDataLayout();
139 
140  if (auto *C = dyn_cast<ConstantStruct>(I)) {
141  const StructLayout *SL = DL.getStructLayout(C->getType());
142  if (Offset >= SL->getSizeInBytes())
143  return nullptr;
144 
145  unsigned Op = SL->getElementContainingOffset(Offset);
146  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
147  Offset - SL->getElementOffset(Op), M);
148  }
149  if (auto *C = dyn_cast<ConstantArray>(I)) {
150  ArrayType *VTableTy = C->getType();
151  uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
152 
153  unsigned Op = Offset / ElemSize;
154  if (Op >= C->getNumOperands())
155  return nullptr;
156 
157  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
158  Offset % ElemSize, M);
159  }
160  return nullptr;
161 }
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
iterator_range< use_iterator > uses()
Definition: Value.h:375
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
void findDevirtualizableCallsForTypeTest(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< CallInst *> &Assumes, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.test, find all devirtualizable call sites based on the call ...
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:613
This class represents a function call, abstracting a target machine&#39;s calling convention.
static void findLoadCallsAtConstantOffset(const Module *M, SmallVectorImpl< DevirtCallSite > &DevirtCalls, Value *VPtr, int64_t Offset, const CallInst *CI, DominatorTree &DT)
F(f)
Hexagon Common GEP
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it...
Definition: DataLayout.cpp:80
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
void findDevirtualizableCallsForTypeCheckedLoad(SmallVectorImpl< DevirtCallSite > &DevirtCalls, SmallVectorImpl< Instruction *> &LoadedPtrs, SmallVectorImpl< Instruction *> &Preds, bool &HasNonCallUses, const CallInst *CI, DominatorTree &DT)
Given a call to the intrinsic @llvm.type.checked.load, find all devirtualizable call sites based on t...
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:585
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
Class to represent array types.
Definition: DerivedTypes.h:408
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:486
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:529
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
uint64_t getSizeInBytes() const
Definition: DataLayout.h:593
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
static void findCallsAtConstantOffset(SmallVectorImpl< DevirtCallSite > &DevirtCalls, bool *HasNonCallUses, Value *FPtr, uint64_t Offset, const CallInst *CI, DominatorTree &DT)
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:607
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1287
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
LLVM Value Representation.
Definition: Value.h:74
Type * getElementType() const
Definition: DerivedTypes.h:399
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M)
int64_t getIndexedOffsetInType(Type *ElemTy, ArrayRef< Value *> Indices) const
Returns the offset from the beginning of the type for the specified indices.
Definition: DataLayout.cpp:806
const BasicBlock * getParent() const
Definition: Instruction.h:66