Introduce a generic operator to apply complex operations to BitVector

[serge-sans-paille]

Summary

This avoids temporary and memcpy call when computing large expressions.

It's basically some kind of poor man's expression template, but it seems easier
to maintain to have a single generic apply call instead of the whole
expression template machinery here.

[serge-sans-paille]

Fix formatting

[RKSimon]

Are you seeing any changes in performance from this?

[serge-sans-paille]

With the patch, running perf stat ./bin/clang -w -c sqlite3.c -o/dev/null (basically compiling the SQLite amalgametion), I get

5,959,419,554      instructions

without the patch, I get

5,970,690,708      instructions

[RKSimon]

Please can you add more test coverage in BitVectorTest.cpp ?

@zturner Any comments?

[RKSimon]

OK - please would it be possible to get this checked for compile time tracker regressions? Otherwise I have no strong objections to this.

[nikic]

llvm/include/llvm/ADT/BitVector.h

575

Shouldn't this be max_element rather than min_element?

(Or, can we change this class to make operations on differently-sized vectors illegal? This is hard to reason about.)

[RKSimon]

Please add BitVectorTest.cpp test coverage (inc tests covering the min_element/max_element issue) and confirm this doesn't cause compiler time tracking regressions.

[nikic]

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=d11d5d1c5f5a8bafc28be98f43c15a3452abb98b&to=315217e6db0e08f703716fa9f0a07c792d8833b0&stat=instructions I think this is an improvement, but below my noise threshold.

[serge-sans-paille]

As suggested by reviewers, limit usage to arrays with the same size and increase test coverage

[RKSimon]

LGTM - cheers

[serge-sans-paille]

Fix assertion

llvm/include/llvm/ADT/BitVector.h

bool test(const BitVector &RHS) const {
 
     for (; i != ThisWords ; ++i)
       if (Bits[i] != 0)
         return true;
 
     return false;
   }
 
+  template <class F, class... ArgTys>
+  static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
+                          ArgTys const &...Args) {
+    assert(llvm::all_of(
+               std::initializer_list<unsigned>{Args.size()...},
+               [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
+           "consistent sizes");
+    Out.resize(Arg.size());
+    for (size_t i = 0, e = Out.NumBitWords(Arg.size()); i != e; ++i)
+      Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...);
+    Out.clear_unused_bits();
+    return Out;
+  }
+
   BitVector &operator|=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] |= RHS.Bits[i];
     return *this;
   }
 

llvm/lib/CodeGen/CFIInstrInserter.cpp

#endif
 
   MBBInfo.Processed = true;
 
   // Update outgoing CFA info.
   MBBInfo.OutgoingCFAOffset = SetOffset;
   MBBInfo.OutgoingCFARegister = SetRegister;
 
   // Update outgoing CSR info.
-  MBBInfo.OutgoingCSRSaved = MBBInfo.IncomingCSRSaved;
-  MBBInfo.OutgoingCSRSaved |= CSRSaved;
-  MBBInfo.OutgoingCSRSaved.reset(CSRRestored);
+  BitVector::apply([](auto x, auto y, auto z) { return (x | y) & ~z; },
+                   MBBInfo.OutgoingCSRSaved, MBBInfo.IncomingCSRSaved, CSRSaved,
+                   CSRRestored);
 }
 
 void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
   SmallVector<MachineBasicBlock *, 4> Stack;
   Stack.push_back(MBBInfo.MBB);
 
   do {
     MachineBasicBlock *Current = Stack.pop_back_val();
void CFIInstrInserter::updateSuccCFAInfo(MBBCFAInfo &MBBInfo) {
   } while (!Stack.empty());
 }
 
 bool CFIInstrInserter::insertCFIInstrs(MachineFunction &MF) {
   const MBBCFAInfo *PrevMBBInfo = &MBBVector[MF.front().getNumber()];
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   bool InsertedCFIInstr = false;
 
+  BitVector SetDifference;
   for (MachineBasicBlock &MBB : MF) {
     // Skip the first MBB in a function
     if (MBB.getNumber() == MF.front().getNumber()) continue;
 
     const MBBCFAInfo &MBBInfo = MBBVector[MBB.getNumber()];
     auto MBBI = MBBInfo.MBB->begin();
     DebugLoc DL = MBBInfo.MBB->findDebugLoc(MBBI);
 
for (MachineBasicBlock &MBB : MF) {
     if (ForceFullCFA) {
       MF.getSubtarget().getFrameLowering()->emitCalleeSavedFrameMoves(
           *MBBInfo.MBB, MBBI);
       InsertedCFIInstr = true;
       PrevMBBInfo = &MBBInfo;
       continue;
     }
 
-    BitVector SetDifference = PrevMBBInfo->OutgoingCSRSaved;
-    SetDifference.reset(MBBInfo.IncomingCSRSaved);
+    BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
+                     PrevMBBInfo->OutgoingCSRSaved, MBBInfo.IncomingCSRSaved);
     for (int Reg : SetDifference.set_bits()) {
       unsigned CFIIndex =
           MF.addFrameInst(MCCFIInstruction::createRestore(nullptr, Reg));
       BuildMI(*MBBInfo.MBB, MBBI, DL, TII->get(TargetOpcode::CFI_INSTRUCTION))
           .addCFIIndex(CFIIndex);
       InsertedCFIInstr = true;
     }
 
-    SetDifference = MBBInfo.IncomingCSRSaved;
-    SetDifference.reset(PrevMBBInfo->OutgoingCSRSaved);
+    BitVector::apply([](auto x, auto y) { return x & ~y; }, SetDifference,
+                     MBBInfo.IncomingCSRSaved, PrevMBBInfo->OutgoingCSRSaved);
     for (int Reg : SetDifference.set_bits()) {
       auto it = CSRLocMap.find(Reg);
       assert(it != CSRLocMap.end() && "Reg should have an entry in CSRLocMap");
       unsigned CFIIndex;
       CSRSavedLocation RO = it->second;
       if (!RO.Reg && RO.Offset) {
         CFIIndex = MF.addFrameInst(
             MCCFIInstruction::createOffset(nullptr, Reg, *RO.Offset));

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, ProxyIndex) {
   TypeParam Vec(3);
   EXPECT_TRUE(Vec.none());
   Vec[0] = Vec[1] = Vec[2] = true;
   EXPECT_EQ(Vec.size(), Vec.count());
   Vec[2] = Vec[1] = Vec[0] = false;
   EXPECT_TRUE(Vec.none());
 }
 
+
 TYPED_TEST(BitVectorTest, PortableBitMask) {
   TypeParam A;
   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
 
   A.resize(10);
   A.setBitsInMask(Mask1, 1);
   EXPECT_EQ(10u, A.size());
   EXPECT_FALSE(A.test(0));
using DMI = DenseMapInfo<TypeParam>;
     B.resize(20);
     B.set(10);
     B.reserve(1000);
 
     EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B));
   }
 }
 
+TEST(BitVectoryTest, Apply) {
+  for (int i = 0; i < 2; ++i) {
+    int j = i * 100 + 3;
+
+    const BitVector x =
+        createBitVector<BitVector>(j + 5, {{i, i + 1}, {j - 1, j}});
+    const BitVector y = createBitVector<BitVector>(j + 5, {{i, j}});
+    const BitVector z =
+        createBitVector<BitVector>(j + 5, {{i + 1, i + 2}, {j, j + 1}});
+
+    auto op0 = [](auto x) { return ~x; };
+    BitVector expected0 = x;
+    expected0.flip();
+    BitVector out0(j - 2);
+    BitVector::apply(op0, out0, x);
+    EXPECT_EQ(out0, expected0);
+
+    auto op1 = [](auto x, auto y) { return x & ~y; };
+    BitVector expected1 = x;
+    expected1.reset(y);
+    BitVector out1;
+    BitVector::apply(op1, out1, x, y);
+    EXPECT_EQ(out1, expected1);
+
+    auto op2 = [](auto x, auto y, auto z) { return (x ^ ~y) | z; };
+    BitVector expected2 = y;
+    expected2.flip();
+    expected2 ^= x;
+    expected2 |= z;
+    BitVector out2(j + 5);
+    BitVector::apply(op2, out2, x, y, z);
+    EXPECT_EQ(out2, expected2);
+  }
+}
+
+
 } // namespace