LLVM 20.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/ADT/DenseSet.h"
18#include "llvm/IR/GlobalValue.h"
19#include "llvm/IR/PassManager.h"
20#include <cassert>
21#include <cstdint>
22#include <map>
23#include <set>
24#include <utility>
25#include <vector>
26
27namespace llvm {
28class Module;
29
30template <typename T> class ArrayRef;
31template <typename T> class MutableArrayRef;
32class GlobalVariable;
33class ModuleSummaryIndex;
34struct ValueInfo;
35
36namespace 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.
89struct 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 (or an alias to a 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.
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.
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.
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.
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
224struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
227 bool UseCommandLine = false;
229 : ExportSummary(nullptr), ImportSummary(nullptr), UseCommandLine(true) {}
234 }
236};
237
241};
242bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO);
244 bool WholeProgramVisibilityEnabledInLTO);
246 Module &M, bool WholeProgramVisibilityEnabledInLTO,
247 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,
248 bool ValidateAllVtablesHaveTypeInfos,
249 function_ref<bool(StringRef)> IsVisibleToRegularObj);
251 ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
252 const DenseSet<GlobalValue::GUID> &DynamicExportSymbols,
253 const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols);
254
257 DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols,
258 function_ref<bool(StringRef)> IsVisibleToRegularObj);
259
260/// Perform index-based whole program devirtualization on the \p Summary
261/// index. Any devirtualized targets used by a type test in another module
262/// are added to the \p ExportedGUIDs set. For any local devirtualized targets
263/// only used within the defining module, the information necessary for
264/// locating the corresponding WPD resolution is recorded for the ValueInfo
265/// in case it is exported by cross module importing (in which case the
266/// devirtualized target name will need adjustment).
268 ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
269 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
270
271/// Call after cross-module importing to update the recorded single impl
272/// devirt target names for any locals that were exported.
274 ModuleSummaryIndex &Summary,
275 function_ref<bool(StringRef, ValueInfo)> isExported,
276 std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
277
278} // end namespace llvm
279
280#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
basic Basic Alias true
This file defines the DenseSet and SmallDenseSet classes.
uint64_t Size
#define I(x, y, z)
Definition: MD5.cpp:58
Machine Check Debug Module
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Class to hold module path string table and global value map, and encapsulate methods for operating on...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
An efficient, type-erasing, non-owning reference to a callable.
uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
void setAfterReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO)
void updatePublicTypeTestCalls(Module &M, bool WholeProgramVisibilityEnabledInLTO)
void getVisibleToRegularObjVtableGUIDs(ModuleSummaryIndex &Index, DenseSet< GlobalValue::GUID > &VisibleToRegularObjSymbols, function_ref< bool(StringRef)> IsVisibleToRegularObj)
Based on typeID string, get all associated vtable GUIDS that are visible to regular objects.
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...
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
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.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
void updateVCallVisibilityInModule(Module &M, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols, bool ValidateAllVtablesHaveTypeInfos, function_ref< bool(StringRef)> IsVisibleToRegularObj)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
void updateVCallVisibilityInIndex(ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, const DenseSet< GlobalValue::GUID > &DynamicExportSymbols, const DenseSet< GlobalValue::GUID > &VisibleToRegularObjSymbols)
If whole program visibility asserted, then upgrade all public vcall visibility metadata on vtable def...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
Struct that holds a reference to a particular GUID in a global value summary.
WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary)
const ModuleSummaryIndex * ImportSummary
ModuleSummaryIndex * ExportSummary
PreservedAnalyses run(Module &M, ModuleAnalysisManager &)
void setBE(uint64_t Pos, uint64_t Val, uint8_t Size)
void setLE(uint64_t Pos, uint64_t Val, uint8_t Size)
std::pair< uint8_t *, uint8_t * > getPtrToData(uint64_t Pos, uint8_t Size)
bool operator<(const TypeMemberInfo &other) const
VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
void setBeforeBytes(uint64_t Pos, uint8_t Size)
void setAfterBytes(uint64_t Pos, uint8_t Size)