LowerBitSets: Introduce global layout builder.

The builder is based on a layout algorithm that tries to keep members of
small bit sets together. The new layout compresses Chromium's bit sets to
around 15% of their original size.

Differential Revision: http://reviews.llvm.org/D7796

llvm-svn: 230394

1 files changed, 27 insertions, 0 deletions

diff --git a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
index 796d90f29e9..2f27c0762ff 100644
--- a/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
+++ b/llvm/unittests/Transforms/IPO/LowerBitSets.cpp
@@ -62,3 +62,30 @@ TEST(LowerBitSets, BitSetBuilder) {
     }
   }
 }
+
+TEST(LowerBitSets, GlobalLayoutBuilder) {
+  struct {
+    uint64_t NumObjects;
+    std::vector<std::set<uint64_t>> Fragments;
+    std::vector<uint64_t> WantLayout;
+  } GLBTests[] = {
+    {0, {}, {}},
+    {4, {{0, 1}, {2, 3}}, {0, 1, 2, 3}},
+    {3, {{0, 1}, {1, 2}}, {0, 1, 2}},
+    {4, {{0, 1}, {1, 2}, {2, 3}}, {0, 1, 2, 3}},
+    {4, {{0, 1}, {2, 3}, {1, 2}}, {0, 1, 2, 3}},
+    {6, {{2, 5}, {0, 1, 2, 3, 4, 5}}, {0, 1, 2, 5, 3, 4}},
+  };
+
+  for (auto &&T : GLBTests) {
+    GlobalLayoutBuilder GLB(T.NumObjects);
+    for (auto &&F : T.Fragments)
+      GLB.addFragment(F);
+
+    std::vector<uint64_t> ComputedLayout;
+    for (auto &&F : GLB.Fragments)
+      ComputedLayout.insert(ComputedLayout.end(), F.begin(), F.end());
+
+    EXPECT_EQ(T.WantLayout, ComputedLayout);
+  }
+}