LowerTypeTests.h revision 321369
11553Srgrimes//===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===// 21553Srgrimes// 31553Srgrimes// The LLVM Compiler Infrastructure 41553Srgrimes// 51553Srgrimes// This file is distributed under the University of Illinois Open Source 61553Srgrimes// License. See LICENSE.TXT for details. 71553Srgrimes// 81553Srgrimes//===----------------------------------------------------------------------===// 91553Srgrimes// 101553Srgrimes// This file defines parts of the type test lowering pass implementation that 111553Srgrimes// may be usefully unit tested. 121553Srgrimes// 131553Srgrimes//===----------------------------------------------------------------------===// 141553Srgrimes 151553Srgrimes#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H 161553Srgrimes#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H 171553Srgrimes 181553Srgrimes#include "llvm/ADT/SmallVector.h" 191553Srgrimes#include "llvm/IR/Module.h" 201553Srgrimes#include "llvm/IR/PassManager.h" 211553Srgrimes#include <cstdint> 221553Srgrimes#include <cstring> 231553Srgrimes#include <limits> 241553Srgrimes#include <set> 251553Srgrimes#include <vector> 261553Srgrimes 271553Srgrimesnamespace llvm { 281553Srgrimes 291553Srgrimesclass raw_ostream; 301553Srgrimes 311553Srgrimesnamespace lowertypetests { 321553Srgrimes 331553Srgrimesstruct BitSetInfo { 341553Srgrimes // The indices of the set bits in the bitset. 351553Srgrimes std::set<uint64_t> Bits; 3629780Scharnier 371553Srgrimes // The byte offset into the combined global represented by the bitset. 381553Srgrimes uint64_t ByteOffset; 391553Srgrimes 401553Srgrimes // The size of the bitset in bits. 411553Srgrimes uint64_t BitSize; 4229780Scharnier 4315648Sjoerg // Log2 alignment of the bit set relative to the combined global. 4429780Scharnier // For example, a log2 alignment of 3 means that bits in the bitset 4529780Scharnier // represent addresses 8 bytes apart. 4650479Speter unsigned AlignLog2; 471553Srgrimes 481553Srgrimes bool isSingleOffset() const { 491553Srgrimes return Bits.size() == 1; 501553Srgrimes } 511553Srgrimes 521553Srgrimes bool isAllOnes() const { 531553Srgrimes return Bits.size() == BitSize; 541553Srgrimes } 551553Srgrimes 561553Srgrimes bool containsGlobalOffset(uint64_t Offset) const; 571553Srgrimes 581553Srgrimes void print(raw_ostream &OS) const; 591553Srgrimes}; 601553Srgrimes 611553Srgrimesstruct BitSetBuilder { 621553Srgrimes SmallVector<uint64_t, 16> Offsets; 631553Srgrimes uint64_t Min = std::numeric_limits<uint64_t>::max(); 641553Srgrimes uint64_t Max = 0; 651553Srgrimes 661553Srgrimes BitSetBuilder() = default; 671553Srgrimes 681553Srgrimes void addOffset(uint64_t Offset) { 691553Srgrimes if (Min > Offset) 701553Srgrimes Min = Offset; 711553Srgrimes if (Max < Offset) 7227748Simp Max = Offset; 731553Srgrimes 741553Srgrimes Offsets.push_back(Offset); 7527748Simp } 761553Srgrimes 771553Srgrimes BitSetInfo build(); 781553Srgrimes}; 791553Srgrimes 801553Srgrimes/// This class implements a layout algorithm for globals referenced by bit sets 811553Srgrimes/// that tries to keep members of small bit sets together. This can 8268380Sgad/// significantly reduce bit set sizes in many cases. 8331492Swollman/// 841553Srgrimes/// It works by assembling fragments of layout from sets of referenced globals. 851553Srgrimes/// Each set of referenced globals causes the algorithm to create a new 861553Srgrimes/// fragment, which is assembled by appending each referenced global in the set 8731492Swollman/// into the fragment. If a referenced global has already been referenced by an 8831492Swollman/// fragment created earlier, we instead delete that fragment and append its 891553Srgrimes/// contents into the fragment we are assembling. 901553Srgrimes/// 911553Srgrimes/// By starting with the smallest fragments, we minimize the size of the 9231492Swollman/// fragments that are copied into larger fragments. This is most intuitively 931553Srgrimes/// thought about when considering the case where the globals are virtual tables 941553Srgrimes/// and the bit sets represent their derived classes: in a single inheritance 951553Srgrimes/// hierarchy, the optimum layout would involve a depth-first search of the 961553Srgrimes/// class hierarchy (and in fact the computed layout ends up looking a lot like 9732654Swollman/// a DFS), but a naive DFS would not work well in the presence of multiple 9831492Swollman/// inheritance. This aspect of the algorithm ends up fitting smaller 9931492Swollman/// hierarchies inside larger ones where that would be beneficial. 10031492Swollman/// 1011553Srgrimes/// For example, consider this class hierarchy: 10231492Swollman/// 10331492Swollman/// A B 1041553Srgrimes/// \ / | \ 10531492Swollman/// C D E 10631492Swollman/// 10731492Swollman/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and 10831492Swollman/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our 10931492Swollman/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to 11031492Swollman/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to 11127748Simp/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows: 1121553Srgrimes/// 11331492Swollman/// Add bsC, fragments {{C}} 11431492Swollman/// Add bsD, fragments {{C}, {D}} 1151553Srgrimes/// Add bsE, fragments {{C}, {D}, {E}} 1161553Srgrimes/// Add bsA, fragments {{A, C}, {D}, {E}} 1171553Srgrimes/// Add bsB, fragments {{B, A, C, D, E}} 11831492Swollman/// 11931492Swollman/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 12031492Swollman/// fewer) objects, at the cost of bsB needing to cover 1 more object. 1211553Srgrimes/// 1221553Srgrimes/// The bit set lowering pass assigns an object index to each object that needs 1231553Srgrimes/// to be laid out, and calls addFragment for each bit set passing the object 1241553Srgrimes/// indices of its referenced globals. It then assembles a layout from the 1251553Srgrimes/// computed layout in the Fragments field. 12631492Swollmanstruct GlobalLayoutBuilder { 12731492Swollman /// The computed layout. Each element of this vector contains a fragment of 1281553Srgrimes /// layout (which may be empty) consisting of object indices. 1291553Srgrimes std::vector<std::vector<uint64_t>> Fragments; 1301553Srgrimes 1311553Srgrimes /// Mapping from object index to fragment index. 13231492Swollman std::vector<uint64_t> FragmentMap; 13331492Swollman 1341553Srgrimes GlobalLayoutBuilder(uint64_t NumObjects) 1351553Srgrimes : Fragments(1), FragmentMap(NumObjects) {} 1361553Srgrimes 1371553Srgrimes /// Add F to the layout while trying to keep its indices contiguous. 1381553Srgrimes /// If a previously seen fragment uses any of F's indices, that 1391553Srgrimes /// fragment will be laid out inside F. 1401553Srgrimes void addFragment(const std::set<uint64_t> &F); 14131492Swollman}; 14231492Swollman 1431553Srgrimes/// This class is used to build a byte array containing overlapping bit sets. By 14468253Sgad/// loading from indexed offsets into the byte array and applying a mask, a 1451553Srgrimes/// program can test bits from the bit set with a relatively short instruction 14668735Sgad/// sequence. For example, suppose we have 15 bit sets to lay out: 14768735Sgad/// 1481553Srgrimes/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), 1491553Srgrimes/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), 15068253Sgad/// L (4 bits), M (3 bits), N (2 bits), O (1 bit) 15168253Sgad/// 1521553Srgrimes/// These bits can be laid out in a 16-byte array like this: 1531553Srgrimes/// 1541553Srgrimes/// Byte Offset 1551553Srgrimes/// 0123456789ABCDEF 1561553Srgrimes/// Bit 1571553Srgrimes/// 7 HHHHHHHHHIIIIIII 1581553Srgrimes/// 6 GGGGGGGGGGJJJJJJ 15968380Sgad/// 5 FFFFFFFFFFFKKKKK 16029780Scharnier/// 4 EEEEEEEEEEEELLLL 16131492Swollman/// 3 DDDDDDDDDDDDDMMM 16268380Sgad/// 2 CCCCCCCCCCCCCCNN 16368380Sgad/// 1 BBBBBBBBBBBBBBBO 16468253Sgad/// 0 AAAAAAAAAAAAAAAA 1651553Srgrimes/// 16627748Simp/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to 16768380Sgad/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done 16868380Sgad/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM. 16968380Sgad/// 17068380Sgad/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array, 1711553Srgrimes/// because for one thing it gives us better packing (the more bins there are, 1721553Srgrimes/// the less evenly they will be filled), and for another, the instruction 1731553Srgrimes/// sequences can be slightly shorter, both on x86 and ARM. 1741553Srgrimesstruct ByteArrayBuilder { 1751553Srgrimes /// The byte array built so far. 1761553Srgrimes std::vector<uint8_t> Bytes; 1771553Srgrimes 1781553Srgrimes enum { BitsPerByte = 8 }; 1791553Srgrimes 18068253Sgad /// The number of bytes allocated so far for each of the bits. 1811553Srgrimes uint64_t BitAllocs[BitsPerByte]; 1821553Srgrimes 1831553Srgrimes ByteArrayBuilder() { 1841553Srgrimes memset(BitAllocs, 0, sizeof(BitAllocs)); 1851553Srgrimes } 1861553Srgrimes 1871553Srgrimes /// Allocate BitSize bits in the byte array where Bits contains the bits to 1881553Srgrimes /// set. AllocByteOffset is set to the offset within the byte array and 1891553Srgrimes /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest 1901553Srgrimes /// Processing Time) multiprocessor scheduling algorithm to lay out the bits 19127748Simp /// efficiently; the pass allocates bit sets in decreasing size order. 19227748Simp void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize, 19327748Simp uint64_t &AllocByteOffset, uint8_t &AllocMask); 19427748Simp}; 1951553Srgrimes 19627748Simp} // end namespace lowertypetests 19727748Simp 19827748Simpclass LowerTypeTestsPass : public PassInfoMixin<LowerTypeTestsPass> { 1991553Srgrimespublic: 2001553Srgrimes PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 2011553Srgrimes}; 2021553Srgrimes 20368380Sgad} // end namespace llvm 2041553Srgrimes 2051553Srgrimes#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H 2061553Srgrimes