LowerTypeTests.h

Go to the documentation of this file.

//===- LowerTypeTests.h - type metadata lowering 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 type test lowering pass implementation that
// may be usefully unit tested.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
 
#include "llvm/ADT/FunctionExtras.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/Compiler.h"
#include <cstdint>
#include <cstring>
#include <limits>
#include <set>
#include <vector>
 
namespace llvm {
 
class Module;
class ModuleSummaryIndex;
class raw_ostream;
 
namespace lowertypetests {
 
struct BitSetInfo {
  // The indices of the set bits in the bitset.
  std::set<uint64_t> Bits;
 
  // The byte offset into the combined global represented by the bitset.
  uint64_t ByteOffset;
 
  // The size of the bitset in bits.
  uint64_t BitSize;
 
  // Log2 alignment of the bit set relative to the combined global.
  // For example, a log2 alignment of 3 means that bits in the bitset
  // represent addresses 8 bytes apart.
  unsigned AlignLog2;
 
  bool isSingleOffset() const {
    return Bits.size() == 1;
  }
 
  bool isAllOnes() const {
    return Bits.size() == BitSize;
  }
 
  LLVM_ABI bool containsGlobalOffset(uint64_t Offset) const;
 
  LLVM_ABI void print(raw_ostream &OS) const;
};
 
struct BitSetBuilder {
  SmallVector<uint64_t, 16> Offsets;
  uint64_t Min = std::numeric_limits<uint64_t>::max();
  uint64_t Max = 0;
 
  explicit BitSetBuilder(ArrayRef<uint64_t> Offsets) : Offsets(Offsets) {
    if (!Offsets.empty()) {
      auto [MinIt, MaxIt] = std::minmax_element(Offsets.begin(), Offsets.end());
      Min = *MinIt;
      Max = *MaxIt;
    }
  }
 
  LLVM_ABI BitSetInfo build();
};
 
/// This class implements a layout algorithm for globals referenced by bit sets
/// that tries to keep members of small bit sets together. This can
/// significantly reduce bit set sizes in many cases.
///
/// It works by assembling fragments of layout from sets of referenced globals.
/// Each set of referenced globals causes the algorithm to create a new
/// fragment, which is assembled by appending each referenced global in the set
/// into the fragment. If a referenced global has already been referenced by an
/// fragment created earlier, we instead delete that fragment and append its
/// contents into the fragment we are assembling.
///
/// By starting with the smallest fragments, we minimize the size of the
/// fragments that are copied into larger fragments. This is most intuitively
/// thought about when considering the case where the globals are virtual tables
/// and the bit sets represent their derived classes: in a single inheritance
/// hierarchy, the optimum layout would involve a depth-first search of the
/// class hierarchy (and in fact the computed layout ends up looking a lot like
/// a DFS), but a naive DFS would not work well in the presence of multiple
/// inheritance. This aspect of the algorithm ends up fitting smaller
/// hierarchies inside larger ones where that would be beneficial.
///
/// For example, consider this class hierarchy:
///
/// A       B
///   \   / | \
///     C   D   E
///
/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and
/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our
/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to
/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to
/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:
///
/// Add bsC, fragments {{C}}
/// Add bsD, fragments {{C}, {D}}
/// Add bsE, fragments {{C}, {D}, {E}}
/// Add bsA, fragments {{A, C}, {D}, {E}}
/// Add bsB, fragments {{B, A, C, D, E}}
///
/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3
/// fewer) objects, at the cost of bsB needing to cover 1 more object.
///
/// The bit set lowering pass assigns an object index to each object that needs
/// to be laid out, and calls addFragment for each bit set passing the object
/// indices of its referenced globals. It then assembles a layout by calling
/// build().
class GlobalLayoutBuilder {
  /// The computed layout. Each element of this vector contains a fragment of
  /// layout (which may be empty) consisting of object indices.
  std::vector<std::vector<uint64_t>> Fragments;
 
  /// Mapping from object index to fragment index.
  std::vector<uint64_t> FragmentMap;
 
  /// Optional comparator for object hotness/ordering.
  unique_function<bool(uint64_t, uint64_t)> Less;
 
public:
  /// Construct a layout builder for \p NumObjects objects.
  /// If \p Less is provided, it is used to sort sub-fragments and root
  /// fragments by maximum element.
  GlobalLayoutBuilder(uint64_t NumObjects,
                      unique_function<bool(uint64_t, uint64_t)> Less = nullptr)
      : Fragments(1), FragmentMap(NumObjects), Less(std::move(Less)) {}
 
  /// Add F to the layout while trying to keep its indices contiguous.
  /// If a previously seen fragment uses any of F's indices, that
  /// fragment will be laid out inside F.
  LLVM_ABI void addFragment(const std::set<uint64_t> &F);
 
  /// Flatten fragments into a single layout and return it.
  LLVM_ABI const std::vector<uint64_t> &build();
};
 
/// This class is used to build a byte array containing overlapping bit sets. By
/// loading from indexed offsets into the byte array and applying a mask, a
/// program can test bits from the bit set with a relatively short instruction
/// sequence. For example, suppose we have 15 bit sets to lay out:
///
/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits),
/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits),
/// L (4 bits), M (3 bits), N (2 bits), O (1 bit)
///
/// These bits can be laid out in a 16-byte array like this:
///
///       Byte Offset
///     0123456789ABCDEF
/// Bit
///   7 HHHHHHHHHIIIIIII
///   6 GGGGGGGGGGJJJJJJ
///   5 FFFFFFFFFFFKKKKK
///   4 EEEEEEEEEEEELLLL
///   3 DDDDDDDDDDDDDMMM
///   2 CCCCCCCCCCCCCCNN
///   1 BBBBBBBBBBBBBBBO
///   0 AAAAAAAAAAAAAAAA
///
/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to
/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done
/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM.
///
/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array,
/// because for one thing it gives us better packing (the more bins there are,
/// the less evenly they will be filled), and for another, the instruction
/// sequences can be slightly shorter, both on x86 and ARM.
struct ByteArrayBuilder {
  /// The byte array built so far.
  std::vector<uint8_t> Bytes;
 
  enum { BitsPerByte = 8 };
 
  /// The number of bytes allocated so far for each of the bits.
  uint64_t BitAllocs[BitsPerByte];
 
  ByteArrayBuilder() {
    memset(BitAllocs, 0, sizeof(BitAllocs));
  }
 
  /// Allocate BitSize bits in the byte array where Bits contains the bits to
  /// set. AllocByteOffset is set to the offset within the byte array and
  /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest
  /// Processing Time) multiprocessor scheduling algorithm to lay out the bits
  /// efficiently; the pass allocates bit sets in decreasing size order.
  LLVM_ABI void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize,
                         uint64_t &AllocByteOffset, uint8_t &AllocMask);
};
 
LLVM_ABI bool isJumpTableCanonical(Function *F);
 
/// Specifies how to drop type tests.
enum class DropTestKind {
  Assume, /// Drop only llvm.assumes using type test value.
  All,    /// Drop the type test and all uses.
};
 
} // end namespace lowertypetests
 
class LowerTypeTestsPass : public RequiredPassInfoMixin<LowerTypeTestsPass> {
  bool UseCommandLine = false;
 
  ModuleSummaryIndex *ExportSummary = nullptr;
  const ModuleSummaryIndex *ImportSummary = nullptr;
 
public:
  LowerTypeTestsPass() : UseCommandLine(true) {}
  LowerTypeTestsPass(ModuleSummaryIndex *ExportSummary,
                     const ModuleSummaryIndex *ImportSummary)
      : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {}
 
  LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
};
 
class DropTypeTestsPass : public RequiredPassInfoMixin<DropTypeTestsPass> {
  lowertypetests::DropTestKind Kind = lowertypetests::DropTestKind::Assume;
 
public:
  explicit DropTypeTestsPass(
      lowertypetests::DropTestKind Kind = lowertypetests::DropTestKind::Assume)
      : Kind(Kind) {}
  LLVM_ABI void
  printPipeline(raw_ostream &OS,
                function_ref<StringRef(StringRef)> MapClassName2PassName);
  LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
};
 
class SimplifyTypeTestsPass
    : public OptionalPassInfoMixin<SimplifyTypeTestsPass> {
public:
  LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
};
 
} // end namespace llvm
 
#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H