LLVM  15.0.0git
WholeProgramDevirt.h
Go to the documentation of this file.
1 //===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
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 defines parts of the whole-program devirtualization pass
10 // implementation that may be usefully unit tested.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
15 #define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
16 
17 #include "llvm/IR/GlobalValue.h"
18 #include "llvm/IR/PassManager.h"
19 #include <cassert>
20 #include <cstdint>
21 #include <map>
22 #include <set>
23 #include <utility>
24 #include <vector>
25 
26 namespace llvm {
27 class Module;
28 
29 template <typename T> class ArrayRef;
30 template <typename T> class MutableArrayRef;
31 class Function;
32 class GlobalVariable;
33 class ModuleSummaryIndex;
34 struct ValueInfo;
35 
36 namespace wholeprogramdevirt {
37 
38 // A bit vector that keeps track of which bits are used. We use this to
39 // pack constant values compactly before and after each virtual table.
41  std::vector<uint8_t> Bytes;
42 
43  // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
44  std::vector<uint8_t> BytesUsed;
45 
46  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
47  if (Bytes.size() < Pos + Size) {
48  Bytes.resize(Pos + Size);
49  BytesUsed.resize(Pos + Size);
50  }
51  return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
52  }
53 
54  // Set little-endian value Val with size Size at bit position Pos,
55  // and mark bytes as used.
56  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
57  assert(Pos % 8 == 0);
58  auto DataUsed = getPtrToData(Pos / 8, Size);
59  for (unsigned I = 0; I != Size; ++I) {
60  DataUsed.first[I] = Val >> (I * 8);
61  assert(!DataUsed.second[I]);
62  DataUsed.second[I] = 0xff;
63  }
64  }
65 
66  // Set big-endian value Val with size Size at bit position Pos,
67  // and mark bytes as used.
68  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
69  assert(Pos % 8 == 0);
70  auto DataUsed = getPtrToData(Pos / 8, Size);
71  for (unsigned I = 0; I != Size; ++I) {
72  DataUsed.first[Size - I - 1] = Val >> (I * 8);
73  assert(!DataUsed.second[Size - I - 1]);
74  DataUsed.second[Size - I - 1] = 0xff;
75  }
76  }
77 
78  // Set bit at bit position Pos to b and mark bit as used.
79  void setBit(uint64_t Pos, bool b) {
80  auto DataUsed = getPtrToData(Pos / 8, 1);
81  if (b)
82  *DataUsed.first |= 1 << (Pos % 8);
83  assert(!(*DataUsed.second & (1 << Pos % 8)));
84  *DataUsed.second |= 1 << (Pos % 8);
85  }
86 };
87 
88 // The bits that will be stored before and after a particular vtable.
89 struct VTableBits {
90  // The vtable global.
92 
93  // Cache of the vtable's size in bytes.
95 
96  // The bit vector that will be laid out before the vtable. Note that these
97  // bytes are stored in reverse order until the globals are rebuilt. This means
98  // that any values in the array must be stored using the opposite endianness
99  // from the target.
101 
102  // The bit vector that will be laid out after the vtable.
104 };
105 
106 // Information about a member of a particular type identifier.
108  // The VTableBits for the vtable.
110 
111  // The offset in bytes from the start of the vtable (i.e. the address point).
113 
114  bool operator<(const TypeMemberInfo &other) const {
115  return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
116  }
117 };
118 
119 // A virtual call target, i.e. an entry in a particular vtable.
122 
123  // For testing only.
125  : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {}
126 
127  // The function stored in the vtable.
129 
130  // A pointer to the type identifier member through which the pointer to Fn is
131  // accessed.
133 
134  // When doing virtual constant propagation, this stores the return value for
135  // the function when passed the currently considered argument list.
137 
138  // Whether the target is big endian.
140 
141  // Whether at least one call site to the target was devirtualized.
142  bool WasDevirt;
143 
144  // The minimum byte offset before the address point. This covers the bytes in
145  // the vtable object before the address point (e.g. RTTI, access-to-top,
146  // vtables for other base classes) and is equal to the offset from the start
147  // of the vtable object to the address point.
148  uint64_t minBeforeBytes() const { return TM->Offset; }
149 
150  // The minimum byte offset after the address point. This covers the bytes in
151  // the vtable object after the address point (e.g. the vtable for the current
152  // class and any later base classes) and is equal to the size of the vtable
153  // object minus the offset from the start of the vtable object to the address
154  // point.
155  uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; }
156 
157  // The number of bytes allocated (for the vtable plus the byte array) before
158  // the address point.
160  return minBeforeBytes() + TM->Bits->Before.Bytes.size();
161  }
162 
163  // The number of bytes allocated (for the vtable plus the byte array) after
164  // the address point.
166  return minAfterBytes() + TM->Bits->After.Bytes.size();
167  }
168 
169  // Set the bit at position Pos before the address point to RetVal.
170  void setBeforeBit(uint64_t Pos) {
171  assert(Pos >= 8 * minBeforeBytes());
172  TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
173  }
174 
175  // Set the bit at position Pos after the address point to RetVal.
176  void setAfterBit(uint64_t Pos) {
177  assert(Pos >= 8 * minAfterBytes());
178  TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
179  }
180 
181  // Set the bytes at position Pos before the address point to RetVal.
182  // Because the bytes in Before are stored in reverse order, we use the
183  // opposite endianness to the target.
184  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
185  assert(Pos >= 8 * minBeforeBytes());
186  if (IsBigEndian)
187  TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
188  else
189  TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
190  }
191 
192  // Set the bytes at position Pos after the address point to RetVal.
193  void setAfterBytes(uint64_t Pos, uint8_t Size) {
194  assert(Pos >= 8 * minAfterBytes());
195  if (IsBigEndian)
196  TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
197  else
198  TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
199  }
200 };
201 
202 // Find the minimum offset that we may store a value of size Size bits at. If
203 // IsAfter is set, look for an offset before the object, otherwise look for an
204 // offset after the object.
206  uint64_t Size);
207 
208 // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
209 // given allocation offset before the vtable address. Stores the computed
210 // byte/bit offset to OffsetByte/OffsetBit.
212  uint64_t AllocBefore, unsigned BitWidth,
213  int64_t &OffsetByte, uint64_t &OffsetBit);
214 
215 // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
216 // given allocation offset after the vtable address. Stores the computed
217 // byte/bit offset to OffsetByte/OffsetBit.
219  uint64_t AllocAfter, unsigned BitWidth,
220  int64_t &OffsetByte, uint64_t &OffsetBit);
221 
222 } // end namespace wholeprogramdevirt
223 
224 struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
227  bool UseCommandLine = false;
229  : ExportSummary(nullptr), ImportSummary(nullptr), UseCommandLine(true) {}
234  }
236 };
237 
241 };
242 
244  Module &M, bool WholeProgramVisibilityEnabledInLTO,
245  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);
247  ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
248  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);
249 
250 /// Perform index-based whole program devirtualization on the \p Summary
251 /// index. Any devirtualized targets used by a type test in another module
252 /// are added to the \p ExportedGUIDs set. For any local devirtualized targets
253 /// only used within the defining module, the information necessary for
254 /// locating the corresponding WPD resolution is recorded for the ValueInfo
255 /// in case it is exported by cross module importing (in which case the
256 /// devirtualized target name will need adjustment).
258  ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
259  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
260 
261 /// Call after cross-module importing to update the recorded single impl
262 /// devirt target names for any locals that were exported.
264  ModuleSummaryIndex &Summary,
265  function_ref<bool(StringRef, ValueInfo)> isExported,
266  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
267 
268 } // end namespace llvm
269 
270 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::wholeprogramdevirt::VirtualCallTarget::TM
const TypeMemberInfo * TM
Definition: WholeProgramDevirt.h:132
llvm::wholeprogramdevirt::setAfterReturnValues
void setAfterReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
Definition: WholeProgramDevirt.cpp:300
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::wholeprogramdevirt::findLowestOffset
uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
Definition: WholeProgramDevirt.cpp:210
llvm::WholeProgramDevirtPass::ImportSummary
const ModuleSummaryIndex * ImportSummary
Definition: WholeProgramDevirt.h:226
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::wholeprogramdevirt::VirtualCallTarget::allocatedBeforeBytes
uint64_t allocatedBeforeBytes() const
Definition: WholeProgramDevirt.h:159
llvm::runWholeProgramDevirtOnIndex
void runWholeProgramDevirtOnIndex(ModuleSummaryIndex &Summary, std::set< GlobalValue::GUID > &ExportedGUIDs, std::map< ValueInfo, std::vector< VTableSlotSummary >> &LocalWPDTargetsMap)
Perform index-based whole program devirtualization on the Summary index.
Definition: WholeProgramDevirt.cpp:898
llvm::wholeprogramdevirt::VirtualCallTarget::Fn
Function * Fn
Definition: WholeProgramDevirt.h:128
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::wholeprogramdevirt::VirtualCallTarget::VirtualCallTarget
VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM)
Definition: WholeProgramDevirt.cpp:317
llvm::VTableSlotSummary
Definition: WholeProgramDevirt.h:238
llvm::wholeprogramdevirt::VirtualCallTarget::VirtualCallTarget
VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
Definition: WholeProgramDevirt.h:124
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::wholeprogramdevirt::VTableBits::ObjectSize
uint64_t ObjectSize
Definition: WholeProgramDevirt.h:94
llvm::MutableArrayRef
class LLVM_NODISCARD MutableArrayRef
Definition: ArrayRef.h:28
llvm::WholeProgramDevirtPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: WholeProgramDevirt.cpp:822
llvm::WholeProgramDevirtPass::WholeProgramDevirtPass
WholeProgramDevirtPass()
Definition: WholeProgramDevirt.h:228
llvm::wholeprogramdevirt::setBeforeReturnValues
void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
Definition: WholeProgramDevirt.cpp:283
llvm::wholeprogramdevirt::TypeMemberInfo::Offset
uint64_t Offset
Definition: WholeProgramDevirt.h:112
GlobalValue.h
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:306
llvm::wholeprogramdevirt::VirtualCallTarget::WasDevirt
bool WasDevirt
Definition: WholeProgramDevirt.h:142
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::wholeprogramdevirt::VirtualCallTarget::minBeforeBytes
uint64_t minBeforeBytes() const
Definition: WholeProgramDevirt.h:148
llvm::wholeprogramdevirt::AccumBitVector::BytesUsed
std::vector< uint8_t > BytesUsed
Definition: WholeProgramDevirt.h:44
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::wholeprogramdevirt::AccumBitVector
Definition: WholeProgramDevirt.h:40
llvm::wholeprogramdevirt::VTableBits::After
AccumBitVector After
Definition: WholeProgramDevirt.h:103
llvm::wholeprogramdevirt::VirtualCallTarget::IsBigEndian
bool IsBigEndian
Definition: WholeProgramDevirt.h:139
llvm::wholeprogramdevirt::AccumBitVector::getPtrToData
std::pair< uint8_t *, uint8_t * > getPtrToData(uint64_t Pos, uint8_t Size)
Definition: WholeProgramDevirt.h:46
llvm::ValueInfo
Struct that holds a reference to a particular GUID in a global value summary.
Definition: ModuleSummaryIndex.h:167
llvm::updateVCallVisibilityInIndex
void updateVCallVisibilityInIndex(ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
Definition: WholeProgramDevirt.cpp:878
llvm::wholeprogramdevirt::AccumBitVector::setBE
void setBE(uint64_t Pos, uint64_t Val, uint8_t Size)
Definition: WholeProgramDevirt.h:68
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::wholeprogramdevirt::VirtualCallTarget::RetVal
uint64_t RetVal
Definition: WholeProgramDevirt.h:136
uint64_t
llvm::WholeProgramDevirtPass
Definition: WholeProgramDevirt.h:224
llvm::wholeprogramdevirt::VirtualCallTarget
Definition: WholeProgramDevirt.h:120
llvm::WholeProgramDevirtPass::ExportSummary
ModuleSummaryIndex * ExportSummary
Definition: WholeProgramDevirt.h:225
llvm::WholeProgramDevirtPass::UseCommandLine
bool UseCommandLine
Definition: WholeProgramDevirt.h:227
llvm::wholeprogramdevirt::VirtualCallTarget::setAfterBit
void setAfterBit(uint64_t Pos)
Definition: WholeProgramDevirt.h:176
llvm::wholeprogramdevirt::VirtualCallTarget::setBeforeBytes
void setBeforeBytes(uint64_t Pos, uint8_t Size)
Definition: WholeProgramDevirt.h:184
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::wholeprogramdevirt::AccumBitVector::setBit
void setBit(uint64_t Pos, bool b)
Definition: WholeProgramDevirt.h:79
llvm::updateIndexWPDForExports
void updateIndexWPDForExports(ModuleSummaryIndex &Summary, function_ref< bool(StringRef, ValueInfo)> isExported, std::map< ValueInfo, std::vector< VTableSlotSummary >> &LocalWPDTargetsMap)
Call after cross-module importing to update the recorded single impl devirt target names for any loca...
Definition: WholeProgramDevirt.cpp:904
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::WholeProgramDevirtPass::WholeProgramDevirtPass
WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary)
Definition: WholeProgramDevirt.h:230
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::updateVCallVisibilityInModule
void updateVCallVisibilityInModule(Module &M, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
Definition: WholeProgramDevirt.cpp:858
llvm::wholeprogramdevirt::VTableBits::GV
GlobalVariable * GV
Definition: WholeProgramDevirt.h:91
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::wholeprogramdevirt::TypeMemberInfo::operator<
bool operator<(const TypeMemberInfo &other) const
Definition: WholeProgramDevirt.h:114
llvm::VTableSlotSummary::ByteOffset
uint64_t ByteOffset
Definition: WholeProgramDevirt.h:240
llvm::VTableSlotSummary::TypeID
StringRef TypeID
Definition: WholeProgramDevirt.h:239
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::wholeprogramdevirt::VTableBits
Definition: WholeProgramDevirt.h:89
PassManager.h
llvm::wholeprogramdevirt::VTableBits::Before
AccumBitVector Before
Definition: WholeProgramDevirt.h:100
llvm::wholeprogramdevirt::VirtualCallTarget::setAfterBytes
void setAfterBytes(uint64_t Pos, uint8_t Size)
Definition: WholeProgramDevirt.h:193
llvm::wholeprogramdevirt::TypeMemberInfo::Bits
VTableBits * Bits
Definition: WholeProgramDevirt.h:109
llvm::wholeprogramdevirt::VirtualCallTarget::allocatedAfterBytes
uint64_t allocatedAfterBytes() const
Definition: WholeProgramDevirt.h:165
llvm::ModuleSummaryIndex
Class to hold module path string table and global value map, and encapsulate methods for operating on...
Definition: ModuleSummaryIndex.h:1087
llvm::wholeprogramdevirt::AccumBitVector::Bytes
std::vector< uint8_t > Bytes
Definition: WholeProgramDevirt.h:41
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::wholeprogramdevirt::TypeMemberInfo
Definition: WholeProgramDevirt.h:107
wholeprogramdevirt
wholeprogramdevirt
Definition: WholeProgramDevirt.cpp:812
llvm::wholeprogramdevirt::VirtualCallTarget::setBeforeBit
void setBeforeBit(uint64_t Pos)
Definition: WholeProgramDevirt.h:170
llvm::wholeprogramdevirt::VirtualCallTarget::minAfterBytes
uint64_t minAfterBytes() const
Definition: WholeProgramDevirt.h:155
llvm::wholeprogramdevirt::AccumBitVector::setLE
void setLE(uint64_t Pos, uint64_t Val, uint8_t Size)
Definition: WholeProgramDevirt.h:56
llvm::codeview::PublicSymFlags::Function
@ Function