include/llvm/Transforms/IPO/WholeProgramDevirt.h

   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   std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
  43     if (Bytes.size() < Pos + Size) {
  44       Bytes.resize(Pos + Size);
  45       BytesUsed.resize(Pos + Size);
  46     }
  47     return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
  48   }
  49
  50   // Set little-endian value Val with size Size at bit position Pos,
  51   // and mark bytes as used.
  52   void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
  53     assert(Pos % 8 == 0);
  54     auto DataUsed = getPtrToData(Pos / 8, Size);
  55     for (unsigned I = 0; I != Size; ++I) {
  56       DataUsed.first[I] = Val >> (I * 8);
  57       assert(!DataUsed.second[I]);
  58       DataUsed.second[I] = 0xff;
  59     }
  60   }
  61
  62   // Set big-endian value Val with size Size at bit position Pos,
  63   // and mark bytes as used.
  64   void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
  65     assert(Pos % 8 == 0);
  66     auto DataUsed = getPtrToData(Pos / 8, Size);
  67     for (unsigned I = 0; I != Size; ++I) {
  68       DataUsed.first[Size - I - 1] = Val >> (I * 8);
  69       assert(!DataUsed.second[Size - I - 1]);
  70       DataUsed.second[Size - I - 1] = 0xff;
  71     }
  72   }
  73
  74   // Set bit at bit position Pos to b and mark bit as used.
  75   void setBit(uint64_t Pos, bool b) {
  76     auto DataUsed = getPtrToData(Pos / 8, 1);
  77     if (b)
  78       *DataUsed.first |= 1 << (Pos % 8);
  79     assert(!(*DataUsed.second & (1 << Pos % 8)));
  80     *DataUsed.second |= 1 << (Pos % 8);
  81   }
  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   bool operator<(const TypeMemberInfo &other) const {
 111     return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
 112   }
 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   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   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   uint64_t allocatedBeforeBytes() const {
 156     return minBeforeBytes() + TM->Bits->Before.Bytes.size();
 157   }
 158
 159   // The number of bytes allocated (for the vtable plus the byte array) after
 160   // the address point.
 161   uint64_t allocatedAfterBytes() const {
 162     return minAfterBytes() + TM->Bits->After.Bytes.size();
 163   }
 164
 165   // Set the bit at position Pos before the address point to RetVal.
 166   void setBeforeBit(uint64_t Pos) {
 167     assert(Pos >= 8 * minBeforeBytes());
 168     TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
 169   }
 170
 171   // Set the bit at position Pos after the address point to RetVal.
 172   void setAfterBit(uint64_t Pos) {
 173     assert(Pos >= 8 * minAfterBytes());
 174     TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
 175   }
 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   void setBeforeBytes(uint64_t Pos, uint8_t Size) {
 181     assert(Pos >= 8 * minBeforeBytes());
 182     if (IsBigEndian)
 183       TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
 184     else
 185       TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
 186   }
 187
 188   // Set the bytes at position Pos after the address point to RetVal.
 189   void setAfterBytes(uint64_t Pos, uint8_t Size) {
 190     assert(Pos >= 8 * minAfterBytes());
 191     if (IsBigEndian)
 192       TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
 193     else
 194       TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
 195   }
 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       : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
 226     assert(!(ExportSummary && ImportSummary));
 227   }
 228   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 229 };
 230
 231 } // end namespace llvm
 232
 233 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H