LLVM  16.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 bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO);
244  bool WholeProgramVisibilityEnabledInLTO);
246  Module &M, bool WholeProgramVisibilityEnabledInLTO,
247  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);
249  ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
250  const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);
251 
252 /// Perform index-based whole program devirtualization on the \p Summary
253 /// index. Any devirtualized targets used by a type test in another module
254 /// are added to the \p ExportedGUIDs set. For any local devirtualized targets
255 /// only used within the defining module, the information necessary for
256 /// locating the corresponding WPD resolution is recorded for the ValueInfo
257 /// in case it is exported by cross module importing (in which case the
258 /// devirtualized target name will need adjustment).
260  ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
261  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
262 
263 /// Call after cross-module importing to update the recorded single impl
264 /// devirt target names for any locals that were exported.
266  ModuleSummaryIndex &Summary,
267  function_ref<bool(StringRef, ValueInfo)> isExported,
268  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
269 
270 } // end namespace llvm
271 
272 #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:18
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:855
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:1793
llvm::wholeprogramdevirt::VTableBits::ObjectSize
uint64_t ObjectSize
Definition: WholeProgramDevirt.h:94
llvm::WholeProgramDevirtPass::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
Definition: WholeProgramDevirt.cpp:752
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:28
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:169
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:835
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:861
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:787
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:50
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::updatePublicTypeTestCalls
void updatePublicTypeTestCalls(Module &M, bool WholeProgramVisibilityEnabledInLTO)
Definition: WholeProgramDevirt.cpp:805
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:1199
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
llvm::hasWholeProgramVisibility
bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO)
Definition: WholeProgramDevirt.cpp:779
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