LLVM 20.0.0git
LowerTypeTests.h
Go to the documentation of this file.
1//===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines parts of the type test lowering pass implementation that
10// may be usefully unit tested.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
15#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
16
18#include "llvm/IR/PassManager.h"
19#include <cstdint>
20#include <cstring>
21#include <limits>
22#include <set>
23#include <vector>
24
25namespace llvm {
26
27class Module;
28class ModuleSummaryIndex;
29class raw_ostream;
30
31namespace lowertypetests {
32
33struct 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.
39
40 // The size of the bitset in bits.
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
48 bool isSingleOffset() const {
49 return Bits.size() == 1;
50 }
51
52 bool isAllOnes() const {
53 return Bits.size() == BitSize;
54 }
55
57
58 void print(raw_ostream &OS) const;
59};
60
63 uint64_t Min = std::numeric_limits<uint64_t>::max();
65
66 BitSetBuilder() = default;
67
69 if (Min > Offset)
70 Min = Offset;
71 if (Max < Offset)
72 Max = Offset;
73
75 }
76
78};
79
80/// This class implements a layout algorithm for globals referenced by bit sets
81/// that tries to keep members of small bit sets together. This can
82/// significantly reduce bit set sizes in many cases.
83///
84/// It works by assembling fragments of layout from sets of referenced globals.
85/// Each set of referenced globals causes the algorithm to create a new
86/// fragment, which is assembled by appending each referenced global in the set
87/// into the fragment. If a referenced global has already been referenced by an
88/// fragment created earlier, we instead delete that fragment and append its
89/// contents into the fragment we are assembling.
90///
91/// By starting with the smallest fragments, we minimize the size of the
92/// fragments that are copied into larger fragments. This is most intuitively
93/// thought about when considering the case where the globals are virtual tables
94/// and the bit sets represent their derived classes: in a single inheritance
95/// hierarchy, the optimum layout would involve a depth-first search of the
96/// class hierarchy (and in fact the computed layout ends up looking a lot like
97/// a DFS), but a naive DFS would not work well in the presence of multiple
98/// inheritance. This aspect of the algorithm ends up fitting smaller
99/// hierarchies inside larger ones where that would be beneficial.
100///
101/// For example, consider this class hierarchy:
102///
103/// A B
104/// \ / | \
105/// C D E
106///
107/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and
108/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our
109/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to
110/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to
111/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:
112///
113/// Add bsC, fragments {{C}}
114/// Add bsD, fragments {{C}, {D}}
115/// Add bsE, fragments {{C}, {D}, {E}}
116/// Add bsA, fragments {{A, C}, {D}, {E}}
117/// Add bsB, fragments {{B, A, C, D, E}}
118///
119/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3
120/// fewer) objects, at the cost of bsB needing to cover 1 more object.
121///
122/// The bit set lowering pass assigns an object index to each object that needs
123/// to be laid out, and calls addFragment for each bit set passing the object
124/// indices of its referenced globals. It then assembles a layout from the
125/// computed layout in the Fragments field.
127 /// The computed layout. Each element of this vector contains a fragment of
128 /// layout (which may be empty) consisting of object indices.
129 std::vector<std::vector<uint64_t>> Fragments;
130
131 /// Mapping from object index to fragment index.
132 std::vector<uint64_t> FragmentMap;
133
135 : Fragments(1), FragmentMap(NumObjects) {}
136
137 /// Add F to the layout while trying to keep its indices contiguous.
138 /// If a previously seen fragment uses any of F's indices, that
139 /// fragment will be laid out inside F.
140 void addFragment(const std::set<uint64_t> &F);
141};
142
143/// This class is used to build a byte array containing overlapping bit sets. By
144/// loading from indexed offsets into the byte array and applying a mask, a
145/// program can test bits from the bit set with a relatively short instruction
146/// sequence. For example, suppose we have 15 bit sets to lay out:
147///
148/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits),
149/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits),
150/// L (4 bits), M (3 bits), N (2 bits), O (1 bit)
151///
152/// These bits can be laid out in a 16-byte array like this:
153///
154/// Byte Offset
155/// 0123456789ABCDEF
156/// Bit
157/// 7 HHHHHHHHHIIIIIII
158/// 6 GGGGGGGGGGJJJJJJ
159/// 5 FFFFFFFFFFFKKKKK
160/// 4 EEEEEEEEEEEELLLL
161/// 3 DDDDDDDDDDDDDMMM
162/// 2 CCCCCCCCCCCCCCNN
163/// 1 BBBBBBBBBBBBBBBO
164/// 0 AAAAAAAAAAAAAAAA
165///
166/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to
167/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done
168/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM.
169///
170/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array,
171/// because for one thing it gives us better packing (the more bins there are,
172/// the less evenly they will be filled), and for another, the instruction
173/// sequences can be slightly shorter, both on x86 and ARM.
175 /// The byte array built so far.
176 std::vector<uint8_t> Bytes;
177
178 enum { BitsPerByte = 8 };
179
180 /// The number of bytes allocated so far for each of the bits.
182
184 memset(BitAllocs, 0, sizeof(BitAllocs));
185 }
186
187 /// Allocate BitSize bits in the byte array where Bits contains the bits to
188 /// set. AllocByteOffset is set to the offset within the byte array and
189 /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest
190 /// Processing Time) multiprocessor scheduling algorithm to lay out the bits
191 /// efficiently; the pass allocates bit sets in decreasing size order.
192 void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize,
193 uint64_t &AllocByteOffset, uint8_t &AllocMask);
194};
195
197
198} // end namespace lowertypetests
199
200class LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> {
201 bool UseCommandLine = false;
202
203 ModuleSummaryIndex *ExportSummary = nullptr;
204 const ModuleSummaryIndex *ImportSummary = nullptr;
205 bool DropTypeTests = true;
206
207public:
208 LowerTypeTestsPass() : UseCommandLine(true) {}
210 const ModuleSummaryIndex *ImportSummary,
211 bool DropTypeTests = false)
212 : ExportSummary(ExportSummary), ImportSummary(ImportSummary),
213 DropTypeTests(DropTypeTests) {}
215};
216
217} // end namespace llvm
218
219#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H
basic Basic Alias true
#define F(x, y, z)
Definition: MD5.cpp:55
Machine Check Debug Module
This header defines various interfaces for pass management in LLVM.
raw_pwrite_stream & OS
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
LowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary, bool DropTypeTests=false)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Class to hold module path string table and global value map, and encapsulate methods for operating on...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
bool isJumpTableCanonical(Function *F)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:69
SmallVector< uint64_t, 16 > Offsets
bool containsGlobalOffset(uint64_t Offset) const
void print(raw_ostream &OS) const
This class is used to build a byte array containing overlapping bit sets.
uint64_t BitAllocs[BitsPerByte]
The number of bytes allocated so far for each of the bits.
std::vector< uint8_t > Bytes
The byte array built so far.
void allocate(const std::set< uint64_t > &Bits, uint64_t BitSize, uint64_t &AllocByteOffset, uint8_t &AllocMask)
Allocate BitSize bits in the byte array where Bits contains the bits to set.
This class implements a layout algorithm for globals referenced by bit sets that tries to keep member...
std::vector< std::vector< uint64_t > > Fragments
The computed layout.
void addFragment(const std::set< uint64_t > &F)
Add F to the layout while trying to keep its indices contiguous.
std::vector< uint64_t > FragmentMap
Mapping from object index to fragment index.