Coverage Report

Created: 2019-07-24 05:18

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