1 //===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines parts of the type test lowering pass implementation that
11 // may be usefully unit tested.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
16 #define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/IR/Module.h"
21 #include "llvm/IR/PassManager.h"
36 namespace lowertypetests {
39 // The indices of the set bits in the bitset.
40 std::set<uint64_t> Bits;
42 // The byte offset into the combined global represented by the bitset.
45 // The size of the bitset in bits.
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.
53 bool isSingleOffset() const {
54 return Bits.size() == 1;
57 bool isAllOnes() const {
58 return Bits.size() == BitSize;
61 bool containsGlobalOffset(uint64_t Offset) const;
63 void print(raw_ostream &OS) const;
66 struct BitSetBuilder {
67 SmallVector<uint64_t, 16> Offsets;
70 BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {}
72 void addOffset(uint64_t Offset) {
78 Offsets.push_back(Offset);
84 /// This class implements a layout algorithm for globals referenced by bit sets
85 /// that tries to keep members of small bit sets together. This can
86 /// significantly reduce bit set sizes in many cases.
88 /// It works by assembling fragments of layout from sets of referenced globals.
89 /// Each set of referenced globals causes the algorithm to create a new
90 /// fragment, which is assembled by appending each referenced global in the set
91 /// into the fragment. If a referenced global has already been referenced by an
92 /// fragment created earlier, we instead delete that fragment and append its
93 /// contents into the fragment we are assembling.
95 /// By starting with the smallest fragments, we minimize the size of the
96 /// fragments that are copied into larger fragments. This is most intuitively
97 /// thought about when considering the case where the globals are virtual tables
98 /// and the bit sets represent their derived classes: in a single inheritance
99 /// hierarchy, the optimum layout would involve a depth-first search of the
100 /// class hierarchy (and in fact the computed layout ends up looking a lot like
101 /// a DFS), but a naive DFS would not work well in the presence of multiple
102 /// inheritance. This aspect of the algorithm ends up fitting smaller
103 /// hierarchies inside larger ones where that would be beneficial.
105 /// For example, consider this class hierarchy:
111 /// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and
112 /// bsE (E). If we laid out our objects by DFS traversing B followed by A, our
113 /// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to
114 /// cover the only 4 objects in its hierarchy, but not for bsA as it needs to
115 /// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:
117 /// Add bsC, fragments {{C}}
118 /// Add bsD, fragments {{C}, {D}}
119 /// Add bsE, fragments {{C}, {D}, {E}}
120 /// Add bsA, fragments {{A, C}, {D}, {E}}
121 /// Add bsB, fragments {{B, A, C, D, E}}
123 /// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3
124 /// fewer) objects, at the cost of bsB needing to cover 1 more object.
126 /// The bit set lowering pass assigns an object index to each object that needs
127 /// to be laid out, and calls addFragment for each bit set passing the object
128 /// indices of its referenced globals. It then assembles a layout from the
129 /// computed layout in the Fragments field.
130 struct GlobalLayoutBuilder {
131 /// The computed layout. Each element of this vector contains a fragment of
132 /// layout (which may be empty) consisting of object indices.
133 std::vector<std::vector<uint64_t>> Fragments;
135 /// Mapping from object index to fragment index.
136 std::vector<uint64_t> FragmentMap;
138 GlobalLayoutBuilder(uint64_t NumObjects)
139 : Fragments(1), FragmentMap(NumObjects) {}
141 /// Add F to the layout while trying to keep its indices contiguous.
142 /// If a previously seen fragment uses any of F's indices, that
143 /// fragment will be laid out inside F.
144 void addFragment(const std::set<uint64_t> &F);
147 /// This class is used to build a byte array containing overlapping bit sets. By
148 /// loading from indexed offsets into the byte array and applying a mask, a
149 /// program can test bits from the bit set with a relatively short instruction
150 /// sequence. For example, suppose we have 15 bit sets to lay out:
152 /// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits),
153 /// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits),
154 /// L (4 bits), M (3 bits), N (2 bits), O (1 bit)
156 /// These bits can be laid out in a 16-byte array like this:
161 /// 7 HHHHHHHHHIIIIIII
162 /// 6 GGGGGGGGGGJJJJJJ
163 /// 5 FFFFFFFFFFFKKKKK
164 /// 4 EEEEEEEEEEEELLLL
165 /// 3 DDDDDDDDDDDDDMMM
166 /// 2 CCCCCCCCCCCCCCNN
167 /// 1 BBBBBBBBBBBBBBBO
168 /// 0 AAAAAAAAAAAAAAAA
170 /// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to
171 /// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done
172 /// in 1-2 machine instructions on x86, or 4-6 instructions on ARM.
174 /// This is a byte array, rather than (say) a 2-byte array or a 4-byte array,
175 /// because for one thing it gives us better packing (the more bins there are,
176 /// the less evenly they will be filled), and for another, the instruction
177 /// sequences can be slightly shorter, both on x86 and ARM.
178 struct ByteArrayBuilder {
179 /// The byte array built so far.
180 std::vector<uint8_t> Bytes;
182 enum { BitsPerByte = 8 };
184 /// The number of bytes allocated so far for each of the bits.
185 uint64_t BitAllocs[BitsPerByte];
188 memset(BitAllocs, 0, sizeof(BitAllocs));
191 /// Allocate BitSize bits in the byte array where Bits contains the bits to
192 /// set. AllocByteOffset is set to the offset within the byte array and
193 /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest
194 /// Processing Time) multiprocessor scheduling algorithm to lay out the bits
195 /// efficiently; the pass allocates bit sets in decreasing size order.
196 void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize,
197 uint64_t &AllocByteOffset, uint8_t &AllocMask);
200 } // end namespace lowertypetests
202 class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> {
204 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
207 } // end namespace llvm
209 #endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H