contrib/llvm/include/llvm/Transforms/IPO/LowerTypeTests.h

   1 //===- LowerTypeTests.h - type metadata lowering 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 type test lowering pass implementation that
  11 // may be usefully unit tested.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
  16 #define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/IR/Module.h"
  21 #include "llvm/IR/PassManager.h"
  22
  23 #include <cstdint>
  24 #include <cstring>
  25 #include <limits>
  26 #include <set>
  27 #include <vector>
  28
  29 namespace llvm {
  30
  31 class DataLayout;
  32 class GlobalObject;
  33 class Value;
  34 class raw_ostream;
  35
  36 namespace lowertypetests {
  37
  38 struct BitSetInfo {
  39   // The indices of the set bits in the bitset.
  40   std::set<uint64_t> Bits;
  41
  42   // The byte offset into the combined global represented by the bitset.
  43   uint64_t ByteOffset;
  44
  45   // The size of the bitset in bits.
  46   uint64_t BitSize;
  47
  48   // Log2 alignment of the bit set relative to the combined global.
  49   // For example, a log2 alignment of 3 means that bits in the bitset
  50   // represent addresses 8 bytes apart.
  51   unsigned AlignLog2;
  52
  53   bool isSingleOffset() const {
  54     return Bits.size() == 1;
  55   }
  56
  57   bool isAllOnes() const {
  58     return Bits.size() == BitSize;
  59   }
  60
  61   bool containsGlobalOffset(uint64_t Offset) const;
  62
  63   bool containsValue(const DataLayout &DL,
  64                      const DenseMap<GlobalObject *, uint64_t> &GlobalLayout,
  65                      Value *V, uint64_t COffset = 0) const;
  66
  67   void print(raw_ostream &OS) const;
  68 };
  69
  70 struct BitSetBuilder {
  71   SmallVector<uint64_t, 16> Offsets;
  72   uint64_t Min, Max;
  73
  74   BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {}
  75
  76   void addOffset(uint64_t Offset) {
  77     if (Min > Offset)
  78       Min = Offset;
  79     if (Max < Offset)
  80       Max = Offset;
  81
  82     Offsets.push_back(Offset);
  83   }
  84
  85   BitSetInfo build();
  86 };
  87
  88 /// This class implements a layout algorithm for globals referenced by bit sets
  89 /// that tries to keep members of small bit sets together. This can
  90 /// significantly reduce bit set sizes in many cases.
  91 ///
  92 /// It works by assembling fragments of layout from sets of referenced globals.
  93 /// Each set of referenced globals causes the algorithm to create a new
  94 /// fragment, which is assembled by appending each referenced global in the set
  95 /// into the fragment. If a referenced global has already been referenced by an
  96 /// fragment created earlier, we instead delete that fragment and append its
  97 /// contents into the fragment we are assembling.
  98 ///
  99 /// By starting with the smallest fragments, we minimize the size of the
 100 /// fragments that are copied into larger fragments. This is most intuitively
 101 /// thought about when considering the case where the globals are virtual tables
 102 /// and the bit sets represent their derived classes: in a single inheritance
 103 /// hierarchy, the optimum layout would involve a depth-first search of the
 104 /// class hierarchy (and in fact the computed layout ends up looking a lot like
 105 /// a DFS), but a naive DFS would not work well in the presence of multiple
 106 /// inheritance. This aspect of the algorithm ends up fitting smaller
 107 /// hierarchies inside larger ones where that would be beneficial.
 108 ///
 109 /// For example, consider this class hierarchy:
 110 ///
 111 /// A       B
 112 ///   \   / | \
 113 ///     C   D   E
 114 ///
 115 /// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and
 116 /// bsE (E). If we laid out our objects by DFS traversing B followed by A, our
 117 /// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to
 118 /// cover the only 4 objects in its hierarchy, but not for bsA as it needs to
 119 /// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:
 120 ///
 121 /// Add bsC, fragments {{C}}
 122 /// Add bsD, fragments {{C}, {D}}
 123 /// Add bsE, fragments {{C}, {D}, {E}}
 124 /// Add bsA, fragments {{A, C}, {D}, {E}}
 125 /// Add bsB, fragments {{B, A, C, D, E}}
 126 ///
 127 /// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3
 128 /// fewer) objects, at the cost of bsB needing to cover 1 more object.
 129 ///
 130 /// The bit set lowering pass assigns an object index to each object that needs
 131 /// to be laid out, and calls addFragment for each bit set passing the object
 132 /// indices of its referenced globals. It then assembles a layout from the
 133 /// computed layout in the Fragments field.
 134 struct GlobalLayoutBuilder {
 135   /// The computed layout. Each element of this vector contains a fragment of
 136   /// layout (which may be empty) consisting of object indices.
 137   std::vector<std::vector<uint64_t>> Fragments;
 138
 139   /// Mapping from object index to fragment index.
 140   std::vector<uint64_t> FragmentMap;
 141
 142   GlobalLayoutBuilder(uint64_t NumObjects)
 143       : Fragments(1), FragmentMap(NumObjects) {}
 144
 145   /// Add F to the layout while trying to keep its indices contiguous.
 146   /// If a previously seen fragment uses any of F's indices, that
 147   /// fragment will be laid out inside F.
 148   void addFragment(const std::set<uint64_t> &F);
 149 };
 150
 151 /// This class is used to build a byte array containing overlapping bit sets. By
 152 /// loading from indexed offsets into the byte array and applying a mask, a
 153 /// program can test bits from the bit set with a relatively short instruction
 154 /// sequence. For example, suppose we have 15 bit sets to lay out:
 155 ///
 156 /// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits),
 157 /// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits),
 158 /// L (4 bits), M (3 bits), N (2 bits), O (1 bit)
 159 ///
 160 /// These bits can be laid out in a 16-byte array like this:
 161 ///
 162 ///       Byte Offset
 163 ///     0123456789ABCDEF
 164 /// Bit
 165 ///   7 HHHHHHHHHIIIIIII
 166 ///   6 GGGGGGGGGGJJJJJJ
 167 ///   5 FFFFFFFFFFFKKKKK
 168 ///   4 EEEEEEEEEEEELLLL
 169 ///   3 DDDDDDDDDDDDDMMM
 170 ///   2 CCCCCCCCCCCCCCNN
 171 ///   1 BBBBBBBBBBBBBBBO
 172 ///   0 AAAAAAAAAAAAAAAA
 173 ///
 174 /// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to
 175 /// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done
 176 /// in 1-2 machine instructions on x86, or 4-6 instructions on ARM.
 177 ///
 178 /// This is a byte array, rather than (say) a 2-byte array or a 4-byte array,
 179 /// because for one thing it gives us better packing (the more bins there are,
 180 /// the less evenly they will be filled), and for another, the instruction
 181 /// sequences can be slightly shorter, both on x86 and ARM.
 182 struct ByteArrayBuilder {
 183   /// The byte array built so far.
 184   std::vector<uint8_t> Bytes;
 185
 186   enum { BitsPerByte = 8 };
 187
 188   /// The number of bytes allocated so far for each of the bits.
 189   uint64_t BitAllocs[BitsPerByte];
 190
 191   ByteArrayBuilder() {
 192     memset(BitAllocs, 0, sizeof(BitAllocs));
 193   }
 194
 195   /// Allocate BitSize bits in the byte array where Bits contains the bits to
 196   /// set. AllocByteOffset is set to the offset within the byte array and
 197   /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest
 198   /// Processing Time) multiprocessor scheduling algorithm to lay out the bits
 199   /// efficiently; the pass allocates bit sets in decreasing size order.
 200   void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize,
 201                 uint64_t &AllocByteOffset, uint8_t &AllocMask);
 202 };
 203
 204 } // end namespace lowertypetests
 205
 206 class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> {
 207 public:
 208   PreservedAnalyses run(Module &M, AnalysisManager<Module> &AM);
 209 };
 210
 211 } // end namespace llvm
 212
 213 #endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H