include/llvm/Transforms/IPO/LowerBitSets.h

   1 //===- LowerBitSets.h - Bitset 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 bitset lowering pass implementation that may
  11 // be usefully unit tested.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
  16 #define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallVector.h"
  20
  21 #include <stdint.h>
  22 #include <limits>
  23 #include <set>
  24 #include <vector>
  25
  26 namespace llvm {
  27
  28 class DataLayout;
  29 class GlobalVariable;
  30 class Value;
  31
  32 struct BitSetInfo {
  33   // The actual bitset.
  34   std::vector<uint8_t> Bits;
  35
  36   // The byte offset into the combined global represented by the bitset.
  37   uint64_t ByteOffset;
  38
  39   // The size of the bitset in bits.
  40   uint64_t BitSize;
  41
  42   // Log2 alignment of the bit set relative to the combined global.
  43   // For example, a log2 alignment of 3 means that bits in the bitset
  44   // represent addresses 8 bytes apart.
  45   unsigned AlignLog2;
  46
  47   bool isSingleOffset() const {
  48     return Bits.size() == 1 && Bits[0] == 1;
  49   }
  50
  51   bool containsGlobalOffset(uint64_t Offset) const;
  52
  53   bool containsValue(const DataLayout *DL,
  54                      const DenseMap<GlobalVariable *, uint64_t> &GlobalLayout,
  55                      Value *V, uint64_t COffset = 0) const;
  56
  57 };
  58
  59 struct BitSetBuilder {
  60   SmallVector<uint64_t, 16> Offsets;
  61   uint64_t Min, Max;
  62
  63   BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {}
  64
  65   void addOffset(uint64_t Offset) {
  66     if (Min > Offset)
  67       Min = Offset;
  68     if (Max < Offset)
  69       Max = Offset;
  70
  71     Offsets.push_back(Offset);
  72   }
  73
  74   BitSetInfo build();
  75 };
  76
  77 /// This class implements a layout algorithm for globals referenced by bit sets
  78 /// that tries to keep members of small bit sets together. This can
  79 /// significantly reduce bit set sizes in many cases.
  80 ///
  81 /// It works by assembling fragments of layout from sets of referenced globals.
  82 /// Each set of referenced globals causes the algorithm to create a new
  83 /// fragment, which is assembled by appending each referenced global in the set
  84 /// into the fragment. If a referenced global has already been referenced by an
  85 /// fragment created earlier, we instead delete that fragment and append its
  86 /// contents into the fragment we are assembling.
  87 ///
  88 /// By starting with the smallest fragments, we minimize the size of the
  89 /// fragments that are copied into larger fragments. This is most intuitively
  90 /// thought about when considering the case where the globals are virtual tables
  91 /// and the bit sets represent their derived classes: in a single inheritance
  92 /// hierarchy, the optimum layout would involve a depth-first search of the
  93 /// class hierarchy (and in fact the computed layout ends up looking a lot like
  94 /// a DFS), but a naive DFS would not work well in the presence of multiple
  95 /// inheritance. This aspect of the algorithm ends up fitting smaller
  96 /// hierarchies inside larger ones where that would be beneficial.
  97 ///
  98 /// For example, consider this class hierarchy:
  99 ///
 100 /// A       B
 101 ///   \   / | \
 102 ///     C   D   E
 103 ///
 104 /// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and
 105 /// bsE (E). If we laid out our objects by DFS traversing B followed by A, our
 106 /// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to
 107 /// cover the only 4 objects in its hierarchy, but not for bsA as it needs to
 108 /// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:
 109 ///
 110 /// Add bsC, fragments {{C}}
 111 /// Add bsD, fragments {{C}, {D}}
 112 /// Add bsE, fragments {{C}, {D}, {E}}
 113 /// Add bsA, fragments {{A, C}, {D}, {E}}
 114 /// Add bsB, fragments {{B, A, C, D, E}}
 115 ///
 116 /// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3
 117 /// fewer) objects, at the cost of bsB needing to cover 1 more object.
 118 ///
 119 /// The bit set lowering pass assigns an object index to each object that needs
 120 /// to be laid out, and calls addFragment for each bit set passing the object
 121 /// indices of its referenced globals. It then assembles a layout from the
 122 /// computed layout in the Fragments field.
 123 struct GlobalLayoutBuilder {
 124   /// The computed layout. Each element of this vector contains a fragment of
 125   /// layout (which may be empty) consisting of object indices.
 126   std::vector<std::vector<uint64_t>> Fragments;
 127
 128   /// Mapping from object index to fragment index.
 129   std::vector<uint64_t> FragmentMap;
 130
 131   GlobalLayoutBuilder(uint64_t NumObjects)
 132       : Fragments(1), FragmentMap(NumObjects) {}
 133
 134   /// Add F to the layout while trying to keep its indices contiguous.
 135   /// If a previously seen fragment uses any of F's indices, that
 136   /// fragment will be laid out inside F.
 137   void addFragment(const std::set<uint64_t> &F);
 138 };
 139
 140 } // namespace llvm
 141
 142 #endif