1ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===- LowerBitSets.h - Bitset lowering pass --------------------*- C++ -*-===// 2ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 3ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// The LLVM Compiler Infrastructure 4ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 5ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// This file is distributed under the University of Illinois Open Source 6ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// License. See LICENSE.TXT for details. 7ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 8ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===----------------------------------------------------------------------===// 9ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 10ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// This file defines parts of the bitset lowering pass implementation that may 11ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// be usefully unit tested. 12ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines// 13ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines//===----------------------------------------------------------------------===// 14ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 15ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H 16ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H 17ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 18ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/ADT/DenseMap.h" 19ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include "llvm/ADT/SmallVector.h" 20ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 21ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <stdint.h> 22ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <limits> 23ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <set> 24ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <vector> 25ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 26ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesnamespace llvm { 27ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 28ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass DataLayout; 29ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass GlobalVariable; 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesclass Value; 31ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 32ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct BitSetInfo { 334c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar // The indices of the set bits in the bitset. 344c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::set<uint64_t> Bits; 35ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 36ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The byte offset into the combined global represented by the bitset. 37ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines uint64_t ByteOffset; 38ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 39ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The size of the bitset in bits. 40ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines uint64_t BitSize; 41ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 42ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Log2 alignment of the bit set relative to the combined global. 43ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // For example, a log2 alignment of 3 means that bits in the bitset 44ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // represent addresses 8 bytes apart. 45ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned AlignLog2; 46ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 47ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isSingleOffset() const { 484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Bits.size() == 1; 49ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 50ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 51ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool isAllOnes() const { 524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar return Bits.size() == BitSize; 53ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 54ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 55ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool containsGlobalOffset(uint64_t Offset) const; 56ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar bool containsValue(const DataLayout &DL, 58ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const DenseMap<GlobalVariable *, uint64_t> &GlobalLayout, 59ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Value *V, uint64_t COffset = 0) const; 60ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 61ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 62ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct BitSetBuilder { 63ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<uint64_t, 16> Offsets; 64ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines uint64_t Min, Max; 65ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 66ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BitSetBuilder() : Min(std::numeric_limits<uint64_t>::max()), Max(0) {} 67ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 68ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void addOffset(uint64_t Offset) { 69ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Min > Offset) 70ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Min = Offset; 71ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Max < Offset) 72ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Max = Offset; 73ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 74ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Offsets.push_back(Offset); 75ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 76ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 77ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BitSetInfo build(); 78ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 79ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 80ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// This class implements a layout algorithm for globals referenced by bit sets 81ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// that tries to keep members of small bit sets together. This can 82ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// significantly reduce bit set sizes in many cases. 83ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 84ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// It works by assembling fragments of layout from sets of referenced globals. 85ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Each set of referenced globals causes the algorithm to create a new 86ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// fragment, which is assembled by appending each referenced global in the set 87ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// into the fragment. If a referenced global has already been referenced by an 88ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// fragment created earlier, we instead delete that fragment and append its 89ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// contents into the fragment we are assembling. 90ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 91ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// By starting with the smallest fragments, we minimize the size of the 92ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// fragments that are copied into larger fragments. This is most intuitively 93ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// thought about when considering the case where the globals are virtual tables 94ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// and the bit sets represent their derived classes: in a single inheritance 95ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// hierarchy, the optimum layout would involve a depth-first search of the 96ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// class hierarchy (and in fact the computed layout ends up looking a lot like 97ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// a DFS), but a naive DFS would not work well in the presence of multiple 98ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// inheritance. This aspect of the algorithm ends up fitting smaller 99ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// hierarchies inside larger ones where that would be beneficial. 100ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 101ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// For example, consider this class hierarchy: 102ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 103ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// A B 104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// \ / | \ 105ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// C D E 106ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 107ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and 108ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our 109ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to 110ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to 111ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows: 112ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 113ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Add bsC, fragments {{C}} 114ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Add bsD, fragments {{C}, {D}} 115ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Add bsE, fragments {{C}, {D}, {E}} 116ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Add bsA, fragments {{A, C}, {D}, {E}} 117ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// Add bsB, fragments {{B, A, C, D, E}} 118ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 119ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 120ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// fewer) objects, at the cost of bsB needing to cover 1 more object. 121ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// 122ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// The bit set lowering pass assigns an object index to each object that needs 123ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// to be laid out, and calls addFragment for each bit set passing the object 124ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// indices of its referenced globals. It then assembles a layout from the 125ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines/// computed layout in the Fragments field. 126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesstruct GlobalLayoutBuilder { 127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// The computed layout. Each element of this vector contains a fragment of 128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// layout (which may be empty) consisting of object indices. 129ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<std::vector<uint64_t>> Fragments; 130ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 131ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Mapping from object index to fragment index. 132ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::vector<uint64_t> FragmentMap; 133ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 134ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines GlobalLayoutBuilder(uint64_t NumObjects) 135ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : Fragments(1), FragmentMap(NumObjects) {} 136ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 137ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Add F to the layout while trying to keep its indices contiguous. 138ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// If a previously seen fragment uses any of F's indices, that 139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// fragment will be laid out inside F. 140ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void addFragment(const std::set<uint64_t> &F); 141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines}; 142ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1434c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// This class is used to build a byte array containing overlapping bit sets. By 1444c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// loading from indexed offsets into the byte array and applying a mask, a 1454c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// program can test bits from the bit set with a relatively short instruction 1464c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// sequence. For example, suppose we have 15 bit sets to lay out: 1474c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1484c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), 1494c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), 1504c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// L (4 bits), M (3 bits), N (2 bits), O (1 bit) 1514c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1524c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// These bits can be laid out in a 16-byte array like this: 1534c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1544c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// Byte Offset 1554c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 0123456789ABCDEF 1564c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// Bit 1574c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 7 HHHHHHHHHIIIIIII 1584c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 6 GGGGGGGGGGJJJJJJ 1594c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 5 FFFFFFFFFFFKKKKK 1604c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 4 EEEEEEEEEEEELLLL 1614c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 3 DDDDDDDDDDDDDMMM 1624c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 2 CCCCCCCCCCCCCCNN 1634c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1 BBBBBBBBBBBBBBBO 1644c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 0 AAAAAAAAAAAAAAAA 1654c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1664c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to 1674c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done 1684c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM. 1694c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// 1704c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array, 1714c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// because for one thing it gives us better packing (the more bins there are, 1724c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// the less evenly they will be filled), and for another, the instruction 1734c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar/// sequences can be slightly shorter, both on x86 and ARM. 1744c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainarstruct ByteArrayBuilder { 1754c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// The byte array built so far. 1764c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::vector<uint8_t> Bytes; 1774c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1784c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar enum { BitsPerByte = 8 }; 1794c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1804c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// The number of bytes allocated so far for each of the bits. 1814c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar uint64_t BitAllocs[BitsPerByte]; 1824c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1834c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar ByteArrayBuilder() { 1844c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar memset(BitAllocs, 0, sizeof(BitAllocs)); 1854c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar } 1864c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 1874c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Allocate BitSize bits in the byte array where Bits contains the bits to 1884c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// set. AllocByteOffset is set to the offset within the byte array and 1894c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest 1904c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// Processing Time) multiprocessor scheduling algorithm to lay out the bits 1914c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar /// efficiently; the pass allocates bit sets in decreasing size order. 1924c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar void allocate(const std::set<uint64_t> &Bits, uint64_t BitSize, 1934c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar uint64_t &AllocByteOffset, uint8_t &AllocMask); 1944c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar}; 1954c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar 196ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines} // namespace llvm 197ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#endif 199