LLVM  8.0.1
WholeProgramDevirt.h
Go to the documentation of this file.
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.
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  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
44  if (Bytes.size() < Pos + Size) {
45  Bytes.resize(Pos + Size);
46  BytesUsed.resize(Pos + Size);
47  }
48  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  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
54  assert(Pos % 8 == 0);
55  auto DataUsed = getPtrToData(Pos / 8, Size);
56  for (unsigned I = 0; I != Size; ++I) {
57  DataUsed.first[I] = Val >> (I * 8);
58  assert(!DataUsed.second[I]);
59  DataUsed.second[I] = 0xff;
60  }
61  }
62 
63  // Set big-endian value Val with size Size at bit position Pos,
64  // and mark bytes as used.
65  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
66  assert(Pos % 8 == 0);
67  auto DataUsed = getPtrToData(Pos / 8, Size);
68  for (unsigned I = 0; I != Size; ++I) {
69  DataUsed.first[Size - I - 1] = Val >> (I * 8);
70  assert(!DataUsed.second[Size - I - 1]);
71  DataUsed.second[Size - I - 1] = 0xff;
72  }
73  }
74 
75  // Set bit at bit position Pos to b and mark bit as used.
76  void setBit(uint64_t Pos, bool b) {
77  auto DataUsed = getPtrToData(Pos / 8, 1);
78  if (b)
79  *DataUsed.first |= 1 << (Pos % 8);
80  assert(!(*DataUsed.second & (1 << Pos % 8)));
81  *DataUsed.second |= 1 << (Pos % 8);
82  }
83 };
84 
85 // The bits that will be stored before and after a particular vtable.
86 struct VTableBits {
87  // The vtable global.
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.
98 
99  // The bit vector that will be laid out after the vtable.
101 };
102 
103 // Information about a member of a particular type identifier.
105  // The VTableBits for the vtable.
107 
108  // The offset in bytes from the start of the vtable (i.e. the address point).
109  uint64_t Offset;
110 
111  bool operator<(const TypeMemberInfo &other) const {
112  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.
119 
120  // For testing only.
121  VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
122  : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {}
123 
124  // The function stored in the vtable.
126 
127  // A pointer to the type identifier member through which the pointer to Fn is
128  // accessed.
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.
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  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  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  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  return minAfterBytes() + TM->Bits->After.Bytes.size();
164  }
165 
166  // Set the bit at position Pos before the address point to RetVal.
167  void setBeforeBit(uint64_t Pos) {
168  assert(Pos >= 8 * minBeforeBytes());
169  TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
170  }
171 
172  // Set the bit at position Pos after the address point to RetVal.
173  void setAfterBit(uint64_t Pos) {
174  assert(Pos >= 8 * minAfterBytes());
175  TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
176  }
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  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
182  assert(Pos >= 8 * minBeforeBytes());
183  if (IsBigEndian)
184  TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
185  else
186  TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
187  }
188 
189  // Set the bytes at position Pos after the address point to RetVal.
190  void setAfterBytes(uint64_t Pos, uint8_t Size) {
191  assert(Pos >= 8 * minAfterBytes());
192  if (IsBigEndian)
193  TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
194  else
195  TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
196  }
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.
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.
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> {
225  const ModuleSummaryIndex *ImportSummary)
226  : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
227  assert(!(ExportSummary && ImportSummary));
228  }
230 };
231 
232 } // end namespace llvm
233 
234 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
const ModuleSummaryIndex * ImportSummary
This class represents lattice values for constants.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
void setAfterReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary)
void setBeforeReturnValues(MutableArrayRef< VirtualCallTarget > Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:366
void setAfterBytes(uint64_t Pos, uint8_t Size)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Class to hold module path string table and global value map, and encapsulate methods for operating on...
VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
void setBeforeBytes(uint64_t Pos, uint8_t Size)
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
Module.h This file contains the declarations for the Module class.
wholeprogramdevirt
void setBE(uint64_t Pos, uint64_t Val, uint8_t Size)
ModuleSummaryIndex * ExportSummary
uint64_t findLowestOffset(ArrayRef< VirtualCallTarget > Targets, bool IsAfter, uint64_t Size)
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:47
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::pair< uint8_t *, uint8_t * > getPtrToData(uint64_t Pos, uint8_t Size)
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
bool operator<(const TypeMemberInfo &other) const
void setLE(uint64_t Pos, uint64_t Val, uint8_t Size)