LLVM  13.0.0git
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/Instructions.h"
18 #include "llvm/IR/IntrinsicInst.h"
19 #include "llvm/IR/Intrinsics.h"
20 #include "llvm/IR/Module.h"
21 
22 using namespace llvm;
23 
24 // Search for virtual calls that call FPtr and add them to DevirtCalls.
25 static void
27  bool *HasNonCallUses, Value *FPtr, uint64_t Offset,
28  const CallInst *CI, DominatorTree &DT) {
29  for (const Use &U : FPtr->uses()) {
30  Instruction *User = cast<Instruction>(U.getUser());
31  // Ignore this instruction if it is not dominated by the type intrinsic
32  // being analyzed. Otherwise we may transform a call sharing the same
33  // vtable pointer incorrectly. Specifically, this situation can arise
34  // after indirect call promotion and inlining, where we may have uses
35  // of the vtable pointer guarded by a function pointer check, and a fallback
36  // indirect call.
37  if (!DT.dominates(CI, User))
38  continue;
39  if (isa<BitCastInst>(User)) {
40  findCallsAtConstantOffset(DevirtCalls, HasNonCallUses, User, Offset, CI,
41  DT);
42  } else if (auto *CI = dyn_cast<CallInst>(User)) {
43  DevirtCalls.push_back({Offset, *CI});
44  } else if (auto *II = dyn_cast<InvokeInst>(User)) {
45  DevirtCalls.push_back({Offset, *II});
46  } else if (HasNonCallUses) {
47  *HasNonCallUses = true;
48  }
49  }
50 }
51 
52 // Search for virtual calls that load from VPtr and add them to DevirtCalls.
54  const Module *M, SmallVectorImpl<DevirtCallSite> &DevirtCalls, Value *VPtr,
55  int64_t Offset, const CallInst *CI, DominatorTree &DT) {
56  for (const Use &U : VPtr->uses()) {
57  Value *User = U.getUser();
58  if (isa<BitCastInst>(User)) {
59  findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset, CI, DT);
60  } else if (isa<LoadInst>(User)) {
61  findCallsAtConstantOffset(DevirtCalls, nullptr, User, Offset, CI, DT);
62  } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) {
63  // Take into account the GEP offset.
64  if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) {
65  SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
66  int64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
67  GEP->getSourceElementType(), Indices);
68  findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset,
69  CI, DT);
70  }
71  }
72  }
73 }
74 
77  SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
78  DominatorTree &DT) {
79  assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test);
80 
81  const Module *M = CI->getParent()->getParent()->getParent();
82 
83  // Find llvm.assume intrinsics for this llvm.type.test call.
84  for (const Use &CIU : CI->uses())
85  if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
86  Assumes.push_back(Assume);
87 
88  // If we found any, search for virtual calls based on %p and add them to
89  // DevirtCalls.
90  if (!Assumes.empty())
92  M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT);
93 }
94 
98  SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
99  const CallInst *CI, DominatorTree &DT) {
101  Intrinsic::type_checked_load);
102 
103  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
104  if (!Offset) {
105  HasNonCallUses = true;
106  return;
107  }
108 
109  for (const Use &U : CI->uses()) {
110  auto CIU = U.getUser();
111  if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
112  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
113  LoadedPtrs.push_back(EVI);
114  continue;
115  }
116  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
117  Preds.push_back(EVI);
118  continue;
119  }
120  }
121  HasNonCallUses = true;
122  }
123 
124  for (Value *LoadedPtr : LoadedPtrs)
125  findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
126  Offset->getZExtValue(), CI, DT);
127 }
128 
130  if (I->getType()->isPointerTy()) {
131  if (Offset == 0)
132  return I;
133  return nullptr;
134  }
135 
136  const DataLayout &DL = M.getDataLayout();
137 
138  if (auto *C = dyn_cast<ConstantStruct>(I)) {
139  const StructLayout *SL = DL.getStructLayout(C->getType());
140  if (Offset >= SL->getSizeInBytes())
141  return nullptr;
142 
143  unsigned Op = SL->getElementContainingOffset(Offset);
144  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
145  Offset - SL->getElementOffset(Op), M);
146  }
147  if (auto *C = dyn_cast<ConstantArray>(I)) {
148  ArrayType *VTableTy = C->getType();
149  uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
150 
151  unsigned Op = Offset / ElemSize;
152  if (Op >= C->getNumOperands())
153  return nullptr;
154 
155  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
156  Offset % ElemSize, M);
157  }
158  return nullptr;
159 }
llvm
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::SmallVector< Value *, 8 >
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
Module.h
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:359
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
Constants.h
llvm::User
Definition: User.h:44
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1396
TypeMetadataUtils.h
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
llvm::Instruction
Definition: Instruction.h:45
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
findCallsAtConstantOffset
static void findCallsAtConstantOffset(SmallVectorImpl< DevirtCallSite > &DevirtCalls, bool *HasNonCallUses, Value *FPtr, uint64_t Offset, const CallInst *CI, DominatorTree &DT)
Definition: TypeMetadataUtils.cpp:26
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:604
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:572
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::StructLayout::getElementContainingOffset
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it.
Definition: DataLayout.cpp:82
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::getPointerAtOffset
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M)
Definition: TypeMetadataUtils.cpp:129
llvm::Function::getIntrinsicID
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:205
llvm::StructLayout::getSizeInBytes
uint64_t getSizeInBytes() const
Definition: DataLayout.h:611
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::Value::stripPointerCasts
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:649
llvm::findDevirtualizableCallsForTypeCheckedLoad
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...
Definition: TypeMetadataUtils.cpp:95
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:634
Instructions.h
Dominators.h
findLoadCallsAtConstantOffset
static void findLoadCallsAtConstantOffset(const Module *M, SmallVectorImpl< DevirtCallSite > &DevirtCalls, Value *VPtr, int64_t Offset, const CallInst *CI, DominatorTree &DT)
Definition: TypeMetadataUtils.cpp:53
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::ArrayType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:372
llvm::findDevirtualizableCallsForTypeTest
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 ...
Definition: TypeMetadataUtils.cpp:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44