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, ArgTys const&... Args) {
+    static_assert(sizeof...(ArgTys) > 0, "at least one argument");
+    std::initializer_list<size_t> Sizes = { Args.size()...};
+    size_t CommonSize = *std::min_element(Sizes.begin(), Sizes.end());
+    if (Out.size() < CommonSize)
+      Out.resize(CommonSize);
+    for (size_t i = 0, e = Out.NumBitWords(CommonSize); i != e; ++i)
+      Out.Bits[i] = f(Args.Bits[i]...);
+    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));