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