LowerBitSets: Use byte arrays instead of bit sets to represent in-memory bit sets.
By loading from indexed offsets into a byte array and applying a mask, a
program can test bits from the bit set with a relatively short instruction
sequence. For example, suppose we have 15 bit sets to lay out:
A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits),
F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits),
L (4 bits), M (3 bits), N (2 bits), O (1 bit)
These bits can be laid out in a 16-byte array like this:
Byte Offset
0123456789ABCDEF
Bit
7 HHHHHHHHHIIIIIII
6 GGGGGGGGGGJJJJJJ
5 FFFFFFFFFFFKKKKK
4 EEEEEEEEEEEELLLL
3 DDDDDDDDDDDDDMMM
2 CCCCCCCCCCCCCCNN
1 BBBBBBBBBBBBBBBO
0 AAAAAAAAAAAAAAAA
For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to
test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done
in 1-2 machine instructions on x86, or 4-6 instructions on ARM.
This uses the LPT multiprocessor scheduling algorithm to lay out the bits
efficiently.
Saves ~450KB of instructions in a recent build of Chromium.
Differential Revision: http://reviews.llvm.org/D7954
llvm-svn: 231043
diff --git a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
index 26a4252..613a15f 100644
--- a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
+++ b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
@@ -15,27 +15,39 @@
TEST(LowerBitSets, BitSetBuilder) {
struct {
std::vector<uint64_t> Offsets;
- std::vector<uint8_t> Bits;
+ std::set<uint64_t> Bits;
uint64_t ByteOffset;
uint64_t BitSize;
unsigned AlignLog2;
bool IsSingleOffset;
bool IsAllOnes;
} BSBTests[] = {
- {{}, {0}, 0, 1, 0, false, false},
- {{0}, {1}, 0, 1, 0, true, true},
- {{4}, {1}, 4, 1, 0, true, true},
- {{37}, {1}, 37, 1, 0, true, true},
- {{0, 1}, {3}, 0, 2, 0, false, true},
- {{0, 4}, {3}, 0, 2, 2, false, true},
- {{0, uint64_t(1) << 33}, {3}, 0, 2, 33, false, true},
- {{3, 7}, {3}, 3, 2, 2, false, true},
- {{0, 1, 7}, {131}, 0, 8, 0, false, false},
- {{0, 2, 14}, {131}, 0, 8, 1, false, false},
- {{0, 1, 8}, {3, 1}, 0, 9, 0, false, false},
- {{0, 2, 16}, {3, 1}, 0, 9, 1, false, false},
- {{0, 1, 2, 3, 4, 5, 6, 7}, {255}, 0, 8, 0, false, true},
- {{0, 1, 2, 3, 4, 5, 6, 7, 8}, {255, 1}, 0, 9, 0, false, true},
+ {{}, {}, 0, 1, 0, false, false},
+ {{0}, {0}, 0, 1, 0, true, true},
+ {{4}, {0}, 4, 1, 0, true, true},
+ {{37}, {0}, 37, 1, 0, true, true},
+ {{0, 1}, {0, 1}, 0, 2, 0, false, true},
+ {{0, 4}, {0, 1}, 0, 2, 2, false, true},
+ {{0, uint64_t(1) << 33}, {0, 1}, 0, 2, 33, false, true},
+ {{3, 7}, {0, 1}, 3, 2, 2, false, true},
+ {{0, 1, 7}, {0, 1, 7}, 0, 8, 0, false, false},
+ {{0, 2, 14}, {0, 1, 7}, 0, 8, 1, false, false},
+ {{0, 1, 8}, {0, 1, 8}, 0, 9, 0, false, false},
+ {{0, 2, 16}, {0, 1, 8}, 0, 9, 1, false, false},
+ {{0, 1, 2, 3, 4, 5, 6, 7},
+ {0, 1, 2, 3, 4, 5, 6, 7},
+ 0,
+ 8,
+ 0,
+ false,
+ true},
+ {{0, 1, 2, 3, 4, 5, 6, 7, 8},
+ {0, 1, 2, 3, 4, 5, 6, 7, 8},
+ 0,
+ 9,
+ 0,
+ false,
+ true},
};
for (auto &&T : BSBTests) {
@@ -93,3 +105,51 @@
EXPECT_EQ(T.WantLayout, ComputedLayout);
}
}
+
+TEST(LowerBitSets, ByteArrayBuilder) {
+ struct BABAlloc {
+ std::set<uint64_t> Bits;
+ uint64_t BitSize;
+ uint64_t WantByteOffset;
+ uint8_t WantMask;
+ };
+
+ struct {
+ std::vector<BABAlloc> Allocs;
+ std::vector<uint8_t> WantBytes;
+ } BABTests[] = {
+ {{{{0}, 1, 0, 1}, {{0}, 1, 0, 2}}, {3}},
+ {{{{0}, 16, 0, 1},
+ {{1}, 15, 0, 2},
+ {{2}, 14, 0, 4},
+ {{3}, 13, 0, 8},
+ {{4}, 12, 0, 0x10},
+ {{5}, 11, 0, 0x20},
+ {{6}, 10, 0, 0x40},
+ {{7}, 9, 0, 0x80},
+ {{0}, 7, 9, 0x80},
+ {{0}, 6, 10, 0x40},
+ {{0}, 5, 11, 0x20},
+ {{0}, 4, 12, 0x10},
+ {{0}, 3, 13, 8},
+ {{0}, 2, 14, 4},
+ {{0}, 1, 15, 2}},
+ {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80, 0, 0x80, 0x40, 0x20, 0x10, 8, 4,
+ 2}},
+ };
+
+ for (auto &&T : BABTests) {
+ ByteArrayBuilder BABuilder;
+
+ for (auto &&A : T.Allocs) {
+ uint64_t GotByteOffset;
+ uint8_t GotMask;
+
+ BABuilder.allocate(A.Bits, A.BitSize, GotByteOffset, GotMask);
+ EXPECT_EQ(A.WantByteOffset, GotByteOffset);
+ EXPECT_EQ(A.WantMask, GotMask);
+ }
+
+ EXPECT_EQ(T.WantBytes, BABuilder.Bytes);
+ }
+}