1 //===- LowerBitSets.h - Bitset 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 bitset lowering pass implementation that may
11 // be usefully unit tested.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
16 #define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallVector.h"
34 std::vector<uint8_t> Bits;
36 // The byte offset into the combined global represented by the bitset.
39 // The size of the bitset in bits.
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.
47 bool isSingleOffset() const {
48 return Bits.size() == 1 && Bits[0] == 1;
51 bool isAllOnes() const {
52 for (unsigned I = 0; I != Bits.size() - 1; ++I)
57 return Bits[Bits.size() - 1] == 0xFF;
59 return Bits[Bits.size() - 1] == (1 << (BitSize % 8)) - 1;
62 bool containsGlobalOffset(uint64_t Offset) const;
64 bool containsValue(const DataLayout *DL,
65 const DenseMap<GlobalVariable *, uint64_t> &GlobalLayout,
66 Value *V, uint64_t COffset = 0) const;
70 struct BitSetBuilder {
71 SmallVector<uint64_t, 16> Offsets;
74 BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {}
76 void addOffset(uint64_t Offset) {
82 Offsets.push_back(Offset);
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.
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.
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.
109 /// For example, consider this class hierarchy:
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:
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}}
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.
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;
139 /// Mapping from object index to fragment index.
140 std::vector<uint64_t> FragmentMap;
142 GlobalLayoutBuilder(uint64_t NumObjects)
143 : Fragments(1), FragmentMap(NumObjects) {}
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);