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