compile time improvement for MachineSink

[• hulx2000]

Summary

Currently whenever we sink any instruction, we do clearKillFlags for every use of every use operand for that instruction, apparently there are a lot of duplication, therefore compile time penalties.

This patch collect all the interested registers first, do clearKillFlags for it all together at once at the end, so we only need to do clearKillFlags once for one register, duplication is avoided.

The speedup for one of our testcase is 10x

Suggestions are welcome.

[• dberlin]

lib/CodeGen/MachineSink.cpp

300

for (auto Reg : RegsToClearKillFlags)
  MRI->clearKillFlags(Reg);

RegsToClearKillFlags.clear()

[hiraditya]

lib/CodeGen/MachineSink.cpp

175

In line: 154, we check that SrcReg has only one non-debug-use. So I'm wondering why we need to clear kill flags in the entire function when there will be only one use of SrcReg i.e., in MI which is erased anyway.

772–773

Typo: `registers'

[hiraditya]

LGTM

[• hulx2000]

fix the typo I forgot earlier.

[• hulx2000]

rebase the latest tip now just in case.

[• hulx2000]

recover last change by last patch, now this is the final version

[MatzeB]

LGTM with the following nitpick adressed:

lib/CodeGen/MachineSink.cpp

773–774

No need to state the fact that the flags may be incorrect a second time. I think it is enough to use something simple as:

if(MO.isReg() && MO.isUse())

RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags later.

[MatzeB]

Do you have commit access or should I commit this for you?

[• hulx2000]

Yes, please commit it for me, since you are on it, could you please fix the comment for me too.

Thanks a lot.

lib/CodeGen/MachineSink.cpp

175

I will remove that, this is not the timing consuming part anyway.

300

will do that, thanks.

lib/CodeGen/MachineSink.cpp

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"

     // will be split.
     SetVector<std::pair<MachineBasicBlock*,MachineBasicBlock*> > ToSplit;
 
+    SparseBitVector<> RegsToClearKillFlags;
+
   public:
     static char ID; // Pass identification
     MachineSinking() : MachineFunctionPass(ID) {

   MRI->replaceRegWith(DstReg, SrcReg);
   MI->eraseFromParent();
 
-  // Conservatively, clear any kill flags, since it's possible that they are no
-  // longer correct.
-  MRI->clearKillFlags(SrcReg);
+  // Conservatively, record registers to clear any kill flags later,
+  // since it's possible that they are no longer correct.
+  RegsToClearKillFlags.set(SrcReg);
 
   ++NumCoalesces;
   return true;

     if (!MadeChange) break;
     EverMadeChange = true;
   }
+
+  // Conservatively, clear any kill flags for recorded registers,
+  if (EverMadeChange) {
+    for (SparseBitVector<>::iterator I = RegsToClearKillFlags.begin(),
+         E = RegsToClearKillFlags.end();
+         I != E;
+         ++I) {
+      MRI->clearKillFlags(*I);
+    }
+    RegsToClearKillFlags.clear();
+  }
+
   return EverMadeChange;
 }
 

                          ++MachineBasicBlock::iterator(DbgMI));
   }
 
-  // Conservatively, clear any kill flags, since it's possible that they are no
-  // longer correct.
-  // Note that we have to clear the kill flags for any register this instruction
-  // uses as we may sink over another instruction which currently kills the
-  // used registers.
+  // Conservatively, record regsters to clear any kill flags later,
+  // since it's possible that they are no longer correct.
   for (MachineOperand &MO : MI->operands()) {
     if (MO.isReg() && MO.isUse())
-      MRI->clearKillFlags(MO.getReg());
+      RegsToClearKillFlags.set(MO.getReg());
   }
 
   return true;