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 ↗

(On Diff #25748)

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

RegsToClearKillFlags.clear()

[hiraditya]

lib/CodeGen/MachineSink.cpp

175 ↗

(On Diff #25748)

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.

769 ↗

(On Diff #25748)

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 ↗

(On Diff #25898)

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 ↗

(On Diff #25748)

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

300 ↗

(On Diff #25748)

will do that, thanks.

llvm/trunk/lib/CodeGen/MachineSink.cpp

 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
 // constructs that are not exposed before lowering and instruction selection.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
class MachineSinking : public MachineFunctionPass {
     // Remember which edges have been considered for breaking.
     SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8>
     CEBCandidates;
     // Remember which edges we are about to split.
     // This is different from CEBCandidates since those edges
     // will be split.
     SetVector<std::pair<MachineBasicBlock*,MachineBasicBlock*> > ToSplit;
 
+    SparseBitVector<> RegsToClearKillFlags;
+
   public:
     static char ID; // Pass identification
     MachineSinking() : MachineFunctionPass(ID) {
       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
for (auto &Pair : ToSplit) {
         ++NumSplit;
       } else
         DEBUG(dbgs() << " *** Not legal to break critical edge\n");
     }
     // If this iteration over the code changed anything, keep iterating.
     if (!MadeChange) break;
     EverMadeChange = true;
   }
+
+  // Now clear any kill flags for recorded registers.
+  for (auto I : RegsToClearKillFlags)
+    MRI->clearKillFlags(I);
+  RegsToClearKillFlags.clear();
+
   return EverMadeChange;
 }
 
 bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {
   // Can't sink anything out of a block that has less than two successors.
   if (MBB.succ_size() <= 1 || MBB.empty()) return false;
 
   // Don't bother sinking code out of unreachable blocks. In addition to being
bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) {
 
   // 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.
   for (MachineOperand &MO : MI->operands()) {
     if (MO.isReg() && MO.isUse())
-      MRI->clearKillFlags(MO.getReg());
+      RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
   }
 
   return true;
 }