llvm.org GIT mirror llvm / master include / llvm / Transforms / IPO / WholeProgramDevirt.h
master

Tree @master (Download .tar.gz)

WholeProgramDevirt.h @master

40cd497
 
6b54768
 
 
40cd497
 
 
 
 
 
 
 
 
 
 
7c79872
 
edc7e37
d0a33c4
 
edc7e37
40cd497
 
 
 
 
f6071e1
 
40cd497
 
2a478d4
edc7e37
40cd497
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
dba9146
 
40cd497
 
 
 
 
 
dba9146
40cd497
 
 
 
 
 
dba9146
40cd497
 
dba9146
88add6b
40cd497
 
 
 
dba9146
 
 
40cd497
 
 
 
 
 
 
 
dcedd3b
 
 
40cd497
 
 
 
dba9146
40cd497
 
 
 
 
 
dba9146
40cd497
 
 
 
dba9146
40cd497
 
 
 
 
dba9146
40cd497
 
 
 
 
dba9146
40cd497
 
 
 
 
dba9146
40cd497
 
 
 
 
 
 
 
dba9146
40cd497
dba9146
40cd497
 
 
 
 
 
dba9146
40cd497
dba9146
40cd497
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
d0a33c4
7c79872
 
2a478d4
 
 
 
 
 
 
04d0fe9
7c79872
 
edc7e37
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
d0a33c4
40cd497
d0a33c4
//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines parts of the whole-program devirtualization pass
// implementation that may be usefully unit tested.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Transforms/IPO/FunctionImport.h"
#include <cassert>
#include <cstdint>
#include <set>
#include <utility>
#include <vector>

namespace llvm {

template <typename T> class ArrayRef;
template <typename T> class MutableArrayRef;
class Function;
class GlobalVariable;
class ModuleSummaryIndex;
struct ValueInfo;

namespace wholeprogramdevirt {

// A bit vector that keeps track of which bits are used. We use this to
// pack constant values compactly before and after each virtual table.
struct AccumBitVector {
  std::vector<uint8_t> Bytes;

  // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
  std::vector<uint8_t> BytesUsed;

  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
    if (Bytes.size() < Pos + Size) {
      Bytes.resize(Pos + Size);
      BytesUsed.resize(Pos + Size);
    }
    return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
  }

  // Set little-endian value Val with size Size at bit position Pos,
  // and mark bytes as used.
  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
    assert(Pos % 8 == 0);
    auto DataUsed = getPtrToData(Pos / 8, Size);
    for (unsigned I = 0; I != Size; ++I) {
      DataUsed.first[I] = Val >> (I * 8);
      assert(!DataUsed.second[I]);
      DataUsed.second[I] = 0xff;
    }
  }

  // Set big-endian value Val with size Size at bit position Pos,
  // and mark bytes as used.
  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
    assert(Pos % 8 == 0);
    auto DataUsed = getPtrToData(Pos / 8, Size);
    for (unsigned I = 0; I != Size; ++I) {
      DataUsed.first[Size - I - 1] = Val >> (I * 8);
      assert(!DataUsed.second[Size - I - 1]);
      DataUsed.second[Size - I - 1] = 0xff;
    }
  }

  // Set bit at bit position Pos to b and mark bit as used.
  void setBit(uint64_t Pos, bool b) {
    auto DataUsed = getPtrToData(Pos / 8, 1);
    if (b)
      *DataUsed.first |= 1 << (Pos % 8);
    assert(!(*DataUsed.second & (1 << Pos % 8)));
    *DataUsed.second |= 1 << (Pos % 8);
  }
};

// The bits that will be stored before and after a particular vtable.
struct VTableBits {
  // The vtable global.
  GlobalVariable *GV;

  // Cache of the vtable's size in bytes.
  uint64_t ObjectSize = 0;

  // The bit vector that will be laid out before the vtable. Note that these
  // bytes are stored in reverse order until the globals are rebuilt. This means
  // that any values in the array must be stored using the opposite endianness
  // from the target.
  AccumBitVector Before;

  // The bit vector that will be laid out after the vtable.
  AccumBitVector After;
};

// Information about a member of a particular type identifier.
struct TypeMemberInfo {
  // The VTableBits for the vtable.
  VTableBits *Bits;

  // The offset in bytes from the start of the vtable (i.e. the address point).
  uint64_t Offset;

  bool operator<(const TypeMemberInfo &other) const {
    return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
  }
};

// A virtual call target, i.e. an entry in a particular vtable.
struct VirtualCallTarget {
  VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM);

  // For testing only.
  VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian)
      : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian), WasDevirt(false) {}

  // The function stored in the vtable.
  Function *Fn;

  // A pointer to the type identifier member through which the pointer to Fn is
  // accessed.
  const TypeMemberInfo *TM;

  // When doing virtual constant propagation, this stores the return value for
  // the function when passed the currently considered argument list.
  uint64_t RetVal;

  // Whether the target is big endian.
  bool IsBigEndian;

  // Whether at least one call site to the target was devirtualized.
  bool WasDevirt;

  // The minimum byte offset before the address point. This covers the bytes in
  // the vtable object before the address point (e.g. RTTI, access-to-top,
  // vtables for other base classes) and is equal to the offset from the start
  // of the vtable object to the address point.
  uint64_t minBeforeBytes() const { return TM->Offset; }

  // The minimum byte offset after the address point. This covers the bytes in
  // the vtable object after the address point (e.g. the vtable for the current
  // class and any later base classes) and is equal to the size of the vtable
  // object minus the offset from the start of the vtable object to the address
  // point.
  uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; }

  // The number of bytes allocated (for the vtable plus the byte array) before
  // the address point.
  uint64_t allocatedBeforeBytes() const {
    return minBeforeBytes() + TM->Bits->Before.Bytes.size();
  }

  // The number of bytes allocated (for the vtable plus the byte array) after
  // the address point.
  uint64_t allocatedAfterBytes() const {
    return minAfterBytes() + TM->Bits->After.Bytes.size();
  }

  // Set the bit at position Pos before the address point to RetVal.
  void setBeforeBit(uint64_t Pos) {
    assert(Pos >= 8 * minBeforeBytes());
    TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
  }

  // Set the bit at position Pos after the address point to RetVal.
  void setAfterBit(uint64_t Pos) {
    assert(Pos >= 8 * minAfterBytes());
    TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
  }

  // Set the bytes at position Pos before the address point to RetVal.
  // Because the bytes in Before are stored in reverse order, we use the
  // opposite endianness to the target.
  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
    assert(Pos >= 8 * minBeforeBytes());
    if (IsBigEndian)
      TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
    else
      TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
  }

  // Set the bytes at position Pos after the address point to RetVal.
  void setAfterBytes(uint64_t Pos, uint8_t Size) {
    assert(Pos >= 8 * minAfterBytes());
    if (IsBigEndian)
      TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
    else
      TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
  }
};

// Find the minimum offset that we may store a value of size Size bits at. If
// IsAfter is set, look for an offset before the object, otherwise look for an
// offset after the object.
uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter,
                          uint64_t Size);

// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
// given allocation offset before the vtable address. Stores the computed
// byte/bit offset to OffsetByte/OffsetBit.
void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
                           uint64_t AllocBefore, unsigned BitWidth,
                           int64_t &OffsetByte, uint64_t &OffsetBit);

// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
// given allocation offset after the vtable address. Stores the computed
// byte/bit offset to OffsetByte/OffsetBit.
void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
                          uint64_t AllocAfter, unsigned BitWidth,
                          int64_t &OffsetByte, uint64_t &OffsetBit);

} // end namespace wholeprogramdevirt

struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
  ModuleSummaryIndex *ExportSummary;
  const ModuleSummaryIndex *ImportSummary;
  WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
                         const ModuleSummaryIndex *ImportSummary)
      : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
    assert(!(ExportSummary && ImportSummary));
  }
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
};

struct VTableSlotSummary {
  StringRef TypeID;
  uint64_t ByteOffset;
};

/// Perform index-based whole program devirtualization on the \p Summary
/// index. Any devirtualized targets used by a type test in another module
/// are added to the \p ExportedGUIDs set. For any local devirtualized targets
/// only used within the defining module, the information necessary for
/// locating the corresponding WPD resolution is recorded for the ValueInfo
/// in case it is exported by cross module importing (in which case the
/// devirtualized target name will need adjustment).
void runWholeProgramDevirtOnIndex(
    ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);

/// Call after cross-module importing to update the recorded single impl
/// devirt target names for any locals that were exported.
void updateIndexWPDForExports(
    ModuleSummaryIndex &Summary,
    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);

} // end namespace llvm

#endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H