LCOV - code coverage report
Current view: top level - include/llvm/Transforms/IPO - WholeProgramDevirt.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 41 48 85.4 %
Date: 2018-10-17 09:37:48 Functions: 6 11 54.5 %
Legend: Lines: hit not hit

          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

Generated by: LCOV version 1.13