From da2dbf21a9b3602f7a0f871dec15f03d273bc07b Mon Sep 17 00:00:00 2001 From: Peter Collingbourne Date: Tue, 3 Mar 2015 00:49:28 +0000 Subject: 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 --- llvm/unittests/Transforms/IPO/LowerBitSets.cpp | 90 +++++++++++++++++++++----- 1 file changed, 75 insertions(+), 15 deletions(-) (limited to 'llvm/unittests/Transforms/IPO/LowerBitSets.cpp') diff --git a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp index 26a42528378..613a15fe0d0 100644 --- a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp +++ b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp @@ -15,27 +15,39 @@ using namespace llvm; TEST(LowerBitSets, BitSetBuilder) { struct { std::vector Offsets; - std::vector Bits; + std::set 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 @@ TEST(LowerBitSets, GlobalLayoutBuilder) { EXPECT_EQ(T.WantLayout, ComputedLayout); } } + +TEST(LowerBitSets, ByteArrayBuilder) { + struct BABAlloc { + std::set Bits; + uint64_t BitSize; + uint64_t WantByteOffset; + uint8_t WantMask; + }; + + struct { + std::vector Allocs; + std::vector 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); + } +} -- cgit v1.2.3