Line data Source code
1 : //===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines parts of the whole-program devirtualization pass
11 : // implementation that may be usefully unit tested.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
16 : #define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
17 :
18 : #include "llvm/IR/Module.h"
19 : #include "llvm/IR/PassManager.h"
20 : #include <cassert>
21 : #include <cstdint>
22 : #include <utility>
23 : #include <vector>
24 :
25 : namespace llvm {
26 :
27 : template <typename T> class ArrayRef;
28 : template <typename T> class MutableArrayRef;
29 : class Function;
30 : class GlobalVariable;
31 : class ModuleSummaryIndex;
32 :
33 : namespace wholeprogramdevirt {
34 :
35 : // A bit vector that keeps track of which bits are used. We use this to
36 : // pack constant values compactly before and after each virtual table.
37 : struct AccumBitVector {
38 : std::vector<uint8_t> Bytes;
39 :
40 : // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
41 : std::vector<uint8_t> BytesUsed;
42 :
43 80 : std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
44 160 : if (Bytes.size() < Pos + Size) {
45 56 : Bytes.resize(Pos + Size);
46 56 : BytesUsed.resize(Pos + Size);
47 : }
48 80 : return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
49 : }
50 :
51 : // Set little-endian value Val with size Size at bit position Pos,
52 : // and mark bytes as used.
53 8 : void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
54 : assert(Pos % 8 == 0);
55 8 : auto DataUsed = getPtrToData(Pos / 8, Size);
56 30 : for (unsigned I = 0; I != Size; ++I) {
57 22 : DataUsed.first[I] = Val >> (I * 8);
58 : assert(!DataUsed.second[I]);
59 22 : DataUsed.second[I] = 0xff;
60 : }
61 8 : }
62 :
63 : // Set big-endian value Val with size Size at bit position Pos,
64 : // and mark bytes as used.
65 16 : void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
66 : assert(Pos % 8 == 0);
67 16 : auto DataUsed = getPtrToData(Pos / 8, Size);
68 70 : for (unsigned I = 0; I != Size; ++I) {
69 54 : DataUsed.first[Size - I - 1] = Val >> (I * 8);
70 : assert(!DataUsed.second[Size - I - 1]);
71 54 : DataUsed.second[Size - I - 1] = 0xff;
72 : }
73 16 : }
74 :
75 : // Set bit at bit position Pos to b and mark bit as used.
76 56 : void setBit(uint64_t Pos, bool b) {
77 56 : auto DataUsed = getPtrToData(Pos / 8, 1);
78 56 : if (b)
79 28 : *DataUsed.first |= 1 << (Pos % 8);
80 : assert(!(*DataUsed.second & (1 << Pos % 8)));
81 56 : *DataUsed.second |= 1 << (Pos % 8);
82 56 : }
83 : };
84 :
85 : // The bits that will be stored before and after a particular vtable.
86 239 : struct VTableBits {
87 : // The vtable global.
88 : GlobalVariable *GV;
89 :
90 : // Cache of the vtable's size in bytes.
91 : uint64_t ObjectSize = 0;
92 :
93 : // The bit vector that will be laid out before the vtable. Note that these
94 : // bytes are stored in reverse order until the globals are rebuilt. This means
95 : // that any values in the array must be stored using the opposite endianness
96 : // from the target.
97 : AccumBitVector Before;
98 :
99 : // The bit vector that will be laid out after the vtable.
100 : AccumBitVector After;
101 : };
102 :
103 : // Information about a member of a particular type identifier.
104 : struct TypeMemberInfo {
105 : // The VTableBits for the vtable.
106 : VTableBits *Bits;
107 :
108 : // The offset in bytes from the start of the vtable (i.e. the address point).
109 : uint64_t Offset;
110 :
111 0 : bool operator<(const TypeMemberInfo &other) const {
112 623 : return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
113 : }
114 : };
115 :
116 : // A virtual call target, i.e. an entry in a particular vtable.
117 : struct VirtualCallTarget {
118 : VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM);
119 :
120 : // For testing only.
121 : VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
122 2 : : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {}
123 :
124 : // The function stored in the vtable.
125 : Function *Fn;
126 :
127 : // A pointer to the type identifier member through which the pointer to Fn is
128 : // accessed.
129 : const TypeMemberInfo *TM;
130 :
131 : // When doing virtual constant propagation, this stores the return value for
132 : // the function when passed the currently considered argument list.
133 : uint64_t RetVal;
134 :
135 : // Whether the target is big endian.
136 : bool IsBigEndian;
137 :
138 : // Whether at least one call site to the target was devirtualized.
139 : bool WasDevirt;
140 :
141 : // The minimum byte offset before the address point. This covers the bytes in
142 : // the vtable object before the address point (e.g. RTTI, access-to-top,
143 : // vtables for other base classes) and is equal to the offset from the start
144 : // of the vtable object to the address point.
145 152 : uint64_t minBeforeBytes() const { return TM->Offset; }
146 :
147 : // The minimum byte offset after the address point. This covers the bytes in
148 : // the vtable object after the address point (e.g. the vtable for the current
149 : // class and any later base classes) and is equal to the size of the vtable
150 : // object minus the offset from the start of the vtable object to the address
151 : // point.
152 160 : uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; }
153 :
154 : // The number of bytes allocated (for the vtable plus the byte array) before
155 : // the address point.
156 : uint64_t allocatedBeforeBytes() const {
157 128 : return minBeforeBytes() + TM->Bits->Before.Bytes.size();
158 : }
159 :
160 : // The number of bytes allocated (for the vtable plus the byte array) after
161 : // the address point.
162 : uint64_t allocatedAfterBytes() const {
163 128 : return minAfterBytes() + TM->Bits->After.Bytes.size();
164 : }
165 :
166 : // Set the bit at position Pos before the address point to RetVal.
167 0 : void setBeforeBit(uint64_t Pos) {
168 : assert(Pos >= 8 * minBeforeBytes());
169 44 : TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
170 0 : }
171 :
172 : // Set the bit at position Pos after the address point to RetVal.
173 0 : void setAfterBit(uint64_t Pos) {
174 : assert(Pos >= 8 * minAfterBytes());
175 12 : TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
176 0 : }
177 :
178 : // Set the bytes at position Pos before the address point to RetVal.
179 : // Because the bytes in Before are stored in reverse order, we use the
180 : // opposite endianness to the target.
181 16 : void setBeforeBytes(uint64_t Pos, uint8_t Size) {
182 : assert(Pos >= 8 * minBeforeBytes());
183 16 : if (IsBigEndian)
184 0 : TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
185 : else
186 16 : TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
187 16 : }
188 :
189 : // Set the bytes at position Pos after the address point to RetVal.
190 8 : void setAfterBytes(uint64_t Pos, uint8_t Size) {
191 : assert(Pos >= 8 * minAfterBytes());
192 8 : if (IsBigEndian)
193 0 : TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
194 : else
195 8 : TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
196 8 : }
197 : };
198 :
199 : // Find the minimum offset that we may store a value of size Size bits at. If
200 : // IsAfter is set, look for an offset before the object, otherwise look for an
201 : // offset after the object.
202 : uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter,
203 : uint64_t Size);
204 :
205 : // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
206 : // given allocation offset before the vtable address. Stores the computed
207 : // byte/bit offset to OffsetByte/OffsetBit.
208 : void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
209 : uint64_t AllocBefore, unsigned BitWidth,
210 : int64_t &OffsetByte, uint64_t &OffsetBit);
211 :
212 : // Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
213 : // given allocation offset after the vtable address. Stores the computed
214 : // byte/bit offset to OffsetByte/OffsetBit.
215 : void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
216 : uint64_t AllocAfter, unsigned BitWidth,
217 : int64_t &OffsetByte, uint64_t &OffsetBit);
218 :
219 : } // end namespace wholeprogramdevirt
220 :
221 : struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
222 : ModuleSummaryIndex *ExportSummary;
223 : const ModuleSummaryIndex *ImportSummary;
224 : WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
225 : const ModuleSummaryIndex *ImportSummary)
226 31 : : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
227 : assert(!(ExportSummary && ImportSummary));
228 : }
229 : PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
230 : };
231 :
232 : } // end namespace llvm
233 :
234 : #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
|
