aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/libs/llvm14/include/llvm/Transforms/IPO/WholeProgramDevirt.h
blob: 10b3d88d35d41f7df61002a7f719d91f0640e6b2 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines parts of the whole-program devirtualization pass
// implementation that may be usefully unit tested.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Transforms/IPO/FunctionImport.h"
#include <cassert>
#include <cstdint>
#include <set>
#include <utility>
#include <vector>

namespace llvm {

template <typename T> class ArrayRef;
template <typename T> class MutableArrayRef;
class Function;
class GlobalVariable;
class ModuleSummaryIndex;
struct ValueInfo;

namespace wholeprogramdevirt {

// A bit vector that keeps track of which bits are used. We use this to
// pack constant values compactly before and after each virtual table.
struct AccumBitVector {
  std::vector<uint8_t> Bytes;

  // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
  std::vector<uint8_t> BytesUsed;

  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
    if (Bytes.size() < Pos + Size) {
      Bytes.resize(Pos + Size);
      BytesUsed.resize(Pos + Size);
    }
    return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
  }

  // Set little-endian value Val with size Size at bit position Pos,
  // and mark bytes as used.
  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
    assert(Pos % 8 == 0);
    auto DataUsed = getPtrToData(Pos / 8, Size);
    for (unsigned I = 0; I != Size; ++I) {
      DataUsed.first[I] = Val >> (I * 8);
      assert(!DataUsed.second[I]);
      DataUsed.second[I] = 0xff;
    }
  }

  // Set big-endian value Val with size Size at bit position Pos,
  // and mark bytes as used.
  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
    assert(Pos % 8 == 0);
    auto DataUsed = getPtrToData(Pos / 8, Size);
    for (unsigned I = 0; I != Size; ++I) {
      DataUsed.first[Size - I - 1] = Val >> (I * 8);
      assert(!DataUsed.second[Size - I - 1]);
      DataUsed.second[Size - I - 1] = 0xff;
    }
  }

  // Set bit at bit position Pos to b and mark bit as used.
  void setBit(uint64_t Pos, bool b) {
    auto DataUsed = getPtrToData(Pos / 8, 1);
    if (b)
      *DataUsed.first |= 1 << (Pos % 8);
    assert(!(*DataUsed.second & (1 << Pos % 8)));
    *DataUsed.second |= 1 << (Pos % 8);
  }
};

// The bits that will be stored before and after a particular vtable.
struct VTableBits {
  // The vtable global.
  GlobalVariable *GV;

  // Cache of the vtable's size in bytes.
  uint64_t ObjectSize = 0;

  // The bit vector that will be laid out before the vtable. Note that these
  // bytes are stored in reverse order until the globals are rebuilt. This means
  // that any values in the array must be stored using the opposite endianness
  // from the target.
  AccumBitVector Before;

  // The bit vector that will be laid out after the vtable.
  AccumBitVector After;
};

// Information about a member of a particular type identifier.
struct TypeMemberInfo {
  // The VTableBits for the vtable.
  VTableBits *Bits;

  // The offset in bytes from the start of the vtable (i.e. the address point).
  uint64_t Offset;

  bool operator<(const TypeMemberInfo &other) const {
    return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
  }
};

// A virtual call target, i.e. an entry in a particular vtable.
struct VirtualCallTarget {
  VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM);

  // For testing only.
  VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
      : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {}

  // The function stored in the vtable.
  Function *Fn;

  // A pointer to the type identifier member through which the pointer to Fn is
  // accessed.
  const TypeMemberInfo *TM;

  // When doing virtual constant propagation, this stores the return value for
  // the function when passed the currently considered argument list.
  uint64_t RetVal;

  // Whether the target is big endian.
  bool IsBigEndian;

  // Whether at least one call site to the target was devirtualized.
  bool WasDevirt;

  // The minimum byte offset before the address point. This covers the bytes in
  // the vtable object before the address point (e.g. RTTI, access-to-top,
  // vtables for other base classes) and is equal to the offset from the start
  // of the vtable object to the address point.
  uint64_t minBeforeBytes() const { return TM->Offset; }

  // The minimum byte offset after the address point. This covers the bytes in
  // the vtable object after the address point (e.g. the vtable for the current
  // class and any later base classes) and is equal to the size of the vtable
  // object minus the offset from the start of the vtable object to the address
  // point.
  uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; }

  // The number of bytes allocated (for the vtable plus the byte array) before
  // the address point.
  uint64_t allocatedBeforeBytes() const {
    return minBeforeBytes() + TM->Bits->Before.Bytes.size();
  }

  // The number of bytes allocated (for the vtable plus the byte array) after
  // the address point.
  uint64_t allocatedAfterBytes() const {
    return minAfterBytes() + TM->Bits->After.Bytes.size();
  }

  // Set the bit at position Pos before the address point to RetVal.
  void setBeforeBit(uint64_t Pos) {
    assert(Pos >= 8 * minBeforeBytes());
    TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
  }

  // Set the bit at position Pos after the address point to RetVal.
  void setAfterBit(uint64_t Pos) {
    assert(Pos >= 8 * minAfterBytes());
    TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
  }

  // Set the bytes at position Pos before the address point to RetVal.
  // Because the bytes in Before are stored in reverse order, we use the
  // opposite endianness to the target.
  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
    assert(Pos >= 8 * minBeforeBytes());
    if (IsBigEndian)
      TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
    else
      TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
  }

  // Set the bytes at position Pos after the address point to RetVal.
  void setAfterBytes(uint64_t Pos, uint8_t Size) {
    assert(Pos >= 8 * minAfterBytes());
    if (IsBigEndian)
      TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
    else
      TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
  }
};

// Find the minimum offset that we may store a value of size Size bits at. If
// IsAfter is set, look for an offset before the object, otherwise look for an
// offset after the object.
uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter,
                          uint64_t Size);

// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
// given allocation offset before the vtable address. Stores the computed
// byte/bit offset to OffsetByte/OffsetBit.
void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
                           uint64_t AllocBefore, unsigned BitWidth,
                           int64_t &OffsetByte, uint64_t &OffsetBit);

// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
// given allocation offset after the vtable address. Stores the computed
// byte/bit offset to OffsetByte/OffsetBit.
void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
                          uint64_t AllocAfter, unsigned BitWidth,
                          int64_t &OffsetByte, uint64_t &OffsetBit);

} // end namespace wholeprogramdevirt

struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
  ModuleSummaryIndex *ExportSummary;
  const ModuleSummaryIndex *ImportSummary;
  bool UseCommandLine = false;
  WholeProgramDevirtPass()
      : ExportSummary(nullptr), ImportSummary(nullptr), UseCommandLine(true) {}
  WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
                         const ModuleSummaryIndex *ImportSummary)
      : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
    assert(!(ExportSummary && ImportSummary));
  }
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
};

struct VTableSlotSummary {
  StringRef TypeID;
  uint64_t ByteOffset;
};

void updateVCallVisibilityInModule(
    Module &M, bool WholeProgramVisibilityEnabledInLTO,
    const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);
void updateVCallVisibilityInIndex(
    ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO,
    const DenseSet<GlobalValue::GUID> &DynamicExportSymbols);

/// Perform index-based whole program devirtualization on the \p Summary
/// index. Any devirtualized targets used by a type test in another module
/// are added to the \p ExportedGUIDs set. For any local devirtualized targets
/// only used within the defining module, the information necessary for
/// locating the corresponding WPD resolution is recorded for the ValueInfo
/// in case it is exported by cross module importing (in which case the
/// devirtualized target name will need adjustment).
void runWholeProgramDevirtOnIndex(
    ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);

/// Call after cross-module importing to update the recorded single impl
/// devirt target names for any locals that were exported.
void updateIndexWPDForExports(
    ModuleSummaryIndex &Summary,
    function_ref<bool(StringRef, ValueInfo)> isExported,
    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);

} // end namespace llvm

#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif