[MachineSink] Compile time improvement for large testcases which has many kill flags

[yubing]

Summary

We did a experiment and observed dramatic decrease on compilation time which spent on clearing kill flags.
Before:
Number of BasicBlocks:33357
Number of Instructions:162067
Number of Cleared Kill Flags:32869
Time of handling kill flags(ms):1.607509e+05

After:
Number of BasicBlocks:33357
Number of Instructions:162067
Number of Cleared Kill Flags:32869
Time of handling kill flags:3.987371e+03

[yubing]

use DenseSet<unsigned> instead, please ignore previous patch

[pengfei]

How do you calculate the kill flags handling time?

[yubing]

In D111688#3060446, @pengfei wrote:

How do you calculate the kill flags handling time?

I am using std::chrono::high_resolution_clock::now()

std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
std::chrono::duration<double, std::milli> duration = std::chrono::high_resolution_clock::now() - start;

[pengfei]

In D111688#3060447, @yubing wrote:

In D111688#3060446, @pengfei wrote:

How do you calculate the kill flags handling time?

I am using std::chrono::high_resolution_clock::now()

std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
std::chrono::duration<double, std::milli> duration = std::chrono::high_resolution_clock::now() - start;

Do you also calculate the time of all the access to RegsToClearKillFlags?

[yubing]

In D111688#3060458, @pengfei wrote:

In D111688#3060447, @yubing wrote:

In D111688#3060446, @pengfei wrote:

How do you calculate the kill flags handling time?

I am using std::chrono::high_resolution_clock::now()

std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
std::chrono::duration<double, std::milli> duration = std::chrono::high_resolution_clock::now() - start;

Do you also calculate the time of all the access to RegsToClearKillFlags?

The rest code of maintaining RegsToClearKillFlags contributes minority of the compilation time.

[MatzeB]

huh... I guess the problem here was that we interpreted the register numbers as plain unsigned... And virtual registers always have bit 31 set, so I guess the bitset could indeed grow to unreasonable sizes.

• Please try if DenseSet<Register> works too.
• If you can please find a shorter more succinct title.

Then we should be good to land this.

llvm/lib/CodeGen/MachineSink.cpp

134

Does DenseSet<Register> work too? (if it does not then I'm fine with this).

[yubing]

llvm/lib/CodeGen/MachineSink.cpp

134

Thanks for suggestions, DenseSet<Register> works for me.

[yubing]

Replace DenseSet<unsigned> with DenseSet<Register>

[MatzeB]

Please shorten the title of this change!

LGTM

[craig.topper]

In D111688#3062166, @MatzeB wrote:

huh... I guess the problem here was that we interpreted the register numbers as plain unsigned... And virtual registers always have bit 31 set, so I guess the bitset could indeed grow to unreasonable sizes.

• Please try if DenseSet<Register> works too.
• If you can please find a shorter more succinct title.

Then we should be good to land this.

SparseBitVector shouldn't be effected by bit 31 being set. It stores 128 bit chunks of bits in a linked list. Insertion does a linear scan forward or backward from the most recently accessed chunk to trying to find the chunk to insert in. Were we accessing it in some pathologically bad way that caused long linear scans?

If the issue is with the inserting function, then the title of this patch is misleading. The number of kill flags in is irrelevant. The place where the insert happens doesn't know how many kill flags exist. Only the later call to MRI->clearKillFlags(I) would know that.

[yubing]

In D111688#3074036, @craig.topper wrote:

In D111688#3062166, @MatzeB wrote:

huh... I guess the problem here was that we interpreted the register numbers as plain unsigned... And virtual registers always have bit 31 set, so I guess the bitset could indeed grow to unreasonable sizes.

• Please try if DenseSet<Register> works too.
• If you can please find a shorter more succinct title.

Then we should be good to land this.

SparseBitVector shouldn't be effected by bit 31 being set. It stores 128 bit chunks of bits in a linked list. Insertion does a linear scan forward or backward from the most recently accessed chunk to trying to find the chunk to insert in. Were we accessing it in some pathologically bad way that caused long linear scans?

If the issue is with the inserting function, then the title of this patch is misleading. The number of kill flags in is irrelevant. The place where the insert happens doesn't know how many kill flags exist. Only the later call to MRI->clearKillFlags(I) would know that.

Hi, Craig.
Yeah, title is misleading. There are many regs whose kill flags need to be cleared, and machinesink visit these regs such randomly that SparseBitVector is not fit for storing info of these regs.
So I guess a better title is "[MachineSink] Compile time improvement for large testcases which has many regs whose kill flags need to be cleared"?

llvm/lib/CodeGen/MachineSink.cpp

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;
+    DenseSet<Register> RegsToClearKillFlags;
 
     using AllSuccsCache =
         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
 
     /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
     /// post-dominated by another DBG_VALUE of the same variable location.
     /// This is necessary to detect sequences such as:
     ///     %0 = someinst
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())
-      RegsToClearKillFlags.set(MO.getReg()); // Remember to clear kill flags.
+      RegsToClearKillFlags.insert(MO.getReg()); // Remember to clear kill flags.
   }
 
   return true;
 }
 
 void MachineSinking::SalvageUnsunkDebugUsersOfCopy(
     MachineInstr &MI, MachineBasicBlock *TargetBlock) {
   assert(MI.isCopy());