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 43 95.3 %
Date: 2017-09-14 15:23:50 Functions: 7 8 87.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             : 
      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        1260 : 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         160 :     if (Bytes.size() < Pos + Size) {
      44          56 :       Bytes.resize(Pos + Size);
      45          56 :       BytesUsed.resize(Pos + Size);
      46             :     }
      47         320 :     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           8 :   void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
      53             :     assert(Pos % 8 == 0);
      54           8 :     auto DataUsed = getPtrToData(Pos / 8, Size);
      55          30 :     for (unsigned I = 0; I != Size; ++I) {
      56          22 :       DataUsed.first[I] = Val >> (I * 8);
      57             :       assert(!DataUsed.second[I]);
      58          22 :       DataUsed.second[I] = 0xff;
      59             :     }
      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             :     assert(Pos % 8 == 0);
      66          16 :     auto DataUsed = getPtrToData(Pos / 8, Size);
      67          70 :     for (unsigned I = 0; I != Size; ++I) {
      68          54 :       DataUsed.first[Size - I - 1] = Val >> (I * 8);
      69             :       assert(!DataUsed.second[Size - I - 1]);
      70          54 :       DataUsed.second[Size - I - 1] = 0xff;
      71             :     }
      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             :     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         420 : 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         181 :     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           4 :       : 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             :   uint64_t allocatedBeforeBytes() const {
     156         192 :     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         192 :     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          88 :     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          24 :     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          16 :   void setBeforeBytes(uint64_t Pos, uint8_t Size) {
     181             :     assert(Pos >= 8 * minBeforeBytes());
     182          16 :     if (IsBigEndian)
     183           0 :       TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
     184             :     else
     185          32 :       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             :     assert(Pos >= 8 * minAfterBytes());
     191           8 :     if (IsBigEndian)
     192           0 :       TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
     193             :     else
     194          16 :       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             :   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
     222             : };
     223             : 
     224             : } // end namespace llvm
     225             : 
     226             : #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

Generated by: LCOV version 1.13