LLVM  14.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  Constant *TopLevelGlobal) {
131  if (I->getType()->isPointerTy()) {
132  if (Offset == 0)
133  return I;
134  return nullptr;
135  }
136 
137  const DataLayout &DL = M.getDataLayout();
138 
139  if (auto *C = dyn_cast<ConstantStruct>(I)) {
140  const StructLayout *SL = DL.getStructLayout(C->getType());
141  if (Offset >= SL->getSizeInBytes())
142  return nullptr;
143 
144  unsigned Op = SL->getElementContainingOffset(Offset);
145  return getPointerAtOffset(cast<Constant>(I->getOperand(Op)),
146  Offset - SL->getElementOffset(Op), M,
147  TopLevelGlobal);
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, TopLevelGlobal);
159  }
160 
161  // (Swift-specific) relative-pointer support starts here.
162  if (auto *CI = dyn_cast<ConstantInt>(I)) {
163  if (Offset == 0 && CI->getZExtValue() == 0) {
164  return I;
165  }
166  }
167  if (auto *C = dyn_cast<ConstantExpr>(I)) {
168  switch (C->getOpcode()) {
169  case Instruction::Trunc:
170  case Instruction::PtrToInt:
171  return getPointerAtOffset(cast<Constant>(C->getOperand(0)), Offset, M,
172  TopLevelGlobal);
173  case Instruction::Sub: {
174  auto *Operand0 = cast<Constant>(C->getOperand(0));
175  auto *Operand1 = cast<Constant>(C->getOperand(1));
176 
177  auto StripGEP = [](Constant *C) {
178  auto *CE = dyn_cast<ConstantExpr>(C);
179  if (!CE)
180  return C;
181  if (CE->getOpcode() != Instruction::GetElementPtr)
182  return C;
183  return CE->getOperand(0);
184  };
185  auto *Operand1TargetGlobal = StripGEP(getPointerAtOffset(Operand1, 0, M));
186 
187  // Check that in the "sub (@a, @b)" expression, @b points back to the top
188  // level global (or a GEP thereof) that we're processing. Otherwise bail.
189  if (Operand1TargetGlobal != TopLevelGlobal)
190  return nullptr;
191 
192  return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
193  }
194  default:
195  return nullptr;
196  }
197  }
198  return nullptr;
199 }
llvm
---------------------— PointerInfo ------------------------------------—
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:357
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:1393
TypeMetadataUtils.h
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:377
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:612
uint64_t
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::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:206
llvm::StructLayout::getSizeInBytes
uint64_t getSizeInBytes() const
Definition: DataLayout.h:619
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:687
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:321
llvm::StructLayout::getElementOffset
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:642
Instructions.h
llvm::getPointerAtOffset
Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)
Definition: TypeMetadataUtils.cpp:129
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:1338
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:1475
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
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:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44