LLVM  15.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/Module.h"
20 
21 using namespace llvm;
22 
23 // Search for virtual calls that call FPtr and add them to DevirtCalls.
24 static void
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.
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(GEP->op_begin() + 1, GEP->op_end());
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 
76  SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
77  DominatorTree &DT) {
78  assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test);
79 
80  const Module *M = CI->getParent()->getParent()->getParent();
81 
82  // Find llvm.assume intrinsics for this llvm.type.test call.
83  for (const Use &CIU : CI->uses())
84  if (auto *Assume = dyn_cast<AssumeInst>(CIU.getUser()))
85  Assumes.push_back(Assume);
86 
87  // If we found any, search for virtual calls based on %p and add them to
88  // DevirtCalls.
89  if (!Assumes.empty())
91  M, DevirtCalls, CI->getArgOperand(0)->stripPointerCasts(), 0, CI, DT);
92 }
93 
97  SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
98  const CallInst *CI, DominatorTree &DT) {
100  Intrinsic::type_checked_load);
101 
102  auto *Offset = dyn_cast<ConstantInt>(CI->getArgOperand(1));
103  if (!Offset) {
104  HasNonCallUses = true;
105  return;
106  }
107 
108  for (const Use &U : CI->uses()) {
109  auto CIU = U.getUser();
110  if (auto EVI = dyn_cast<ExtractValueInst>(CIU)) {
111  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 0) {
112  LoadedPtrs.push_back(EVI);
113  continue;
114  }
115  if (EVI->getNumIndices() == 1 && EVI->getIndices()[0] == 1) {
116  Preds.push_back(EVI);
117  continue;
118  }
119  }
120  HasNonCallUses = true;
121  }
122 
123  for (Value *LoadedPtr : LoadedPtrs)
124  findCallsAtConstantOffset(DevirtCalls, &HasNonCallUses, LoadedPtr,
125  Offset->getZExtValue(), CI, DT);
126 }
127 
129  Constant *TopLevelGlobal) {
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  TopLevelGlobal);
147  }
148  if (auto *C = dyn_cast<ConstantArray>(I)) {
149  ArrayType *VTableTy = C->getType();
150  uint64_t ElemSize = DL.getTypeAllocSize(VTableTy->getElementType());
151 
152  unsigned Op = Offset / ElemSize;
153  if (Op >= C->getNumOperands())
154  return nullptr;
155 
156  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
157  Offset % ElemSize, M, TopLevelGlobal);
158  }
159 
160  // (Swift-specific) relative-pointer support starts here.
161  if (auto *CI = dyn_cast<ConstantInt>(I)) {
162  if (Offset == 0 && CI->getZExtValue() == 0) {
163  return I;
164  }
165  }
166  if (auto *C = dyn_cast<ConstantExpr>(I)) {
167  switch (C->getOpcode()) {
168  case Instruction::Trunc:
169  case Instruction::PtrToInt:
170  return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M,
171  TopLevelGlobal);
172  case Instruction::Sub: {
173  auto *Operand0 = cast<Constant>(C->getOperand(0));
174  auto *Operand1 = cast<Constant>(C->getOperand(1));
175 
176  auto StripGEP = [](Constant *C) {
177  auto *CE = dyn_cast<ConstantExpr>(C);
178  if (!CE)
179  return C;
180  if (CE->getOpcode() != Instruction::GetElementPtr)
181  return C;
182  return CE->getOperand(0);
183  };
184  auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M));
185 
186  // Check that in the "sub (@a, @b)" expression, @b points back to the top
187  // level global (or a GEP thereof) that we're processing. Otherwise bail.
188  if (Operand1TargetGlobal != TopLevelGlobal)
189  return nullptr;
190 
191  return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
192  }
193  default:
194  return nullptr;
195  }
196  }
197  return nullptr;
198 }
199 
201  for (auto *U : F->users()) {
202  auto *PtrExpr = dyn_cast<ConstantExpr>(U);
203  if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
204  continue;
205 
206  for (auto *PtrToIntUser : PtrExpr->users()) {
207  auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser);
208  if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
209  continue;
210 
211  SubExpr->replaceNonMetadataUsesWith(
212  ConstantInt::get(SubExpr->getType(), 0));
213  }
214  }
215 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:113
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::Function
Definition: Function.h:60
llvm::SmallVector< Value *, 8 >
llvm::replaceRelativePointerUsersWithZero
void replaceRelativePointerUsersWithZero(Function *F)
Finds the same "relative pointer" pattern as described above, where the target is F,...
Definition: TypeMetadataUtils.cpp:200
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Module.h
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
F
#define F(x, y, z)
Definition: MD5.cpp:55
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:122
Constants.h
llvm::User
Definition: User.h:44
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 or the function signa...
Definition: InstrTypes.h:1396
TypeMetadataUtils.h
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:376
llvm::Instruction
Definition: Instruction.h:42
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:928
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:25
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:622
uint64_t
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:620
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:83
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:65
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:629
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:682
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:94
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:652
Instructions.h
llvm::getPointerAtOffset
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)
Processes a Constant recursively looking into elements of arrays, structs and expressions to find a t...
Definition: TypeMetadataUtils.cpp:128
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:52
llvm::CallBase::getArgOperand
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1341
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::ArrayType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:370
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:74
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43