[LiveVariables] Switch Kill/Defs sets to be `DenseSet`

[davide]

Summary

The testcase in https://bugs.llvm.org/show_bug.cgi?id=32984 went from 3 minutes to 10 minutes after a change that made the LoopUnroll pass more aggressive (increasing the threshold).

-time-passes reveals large part of the time is spent in PHI Elimination (in the backend).
My profiling shows all the time of PHI elimination goes to llvm::LiveVariables::addNewBlock. This is because we keep Defs/Kills registers in a SmallSet, and lvm/ADT/SmallSet.h -> VIterator vfind(const T &V); is O(N).

Switching to a DenseSet reduces the time spent in the pass from 297 seconds to 97 seconds. Profiling still shows a lot of time is spent iterating the data structure, so I guess there's room for improvement.

I tried a SparseBitVector and it's slightly slower than the DenseMap solution. I wanted to try a BitVector but I'm not sure I have an upper bound on the number of elements.

[davide]

+ @mzolotukhin/ @Gerolf (who showed interest in compile time regressions)

[MatzeB]

Not much to say about the patch itself which looks fine.

I wanted to try a BitVector but I'm not sure I have an upper bound on the number of elements.

An upper bound for virtual register numbers would be MachineRegisterInfo::getNumVirtRegs() (and TargetRegisterInfo::getNumReg() for physical registers though I think this set is only about vregs).

[MatzeB]

If this turns out to be more common and we would want to address this on a more fundamental level, this is what we could do:

• Finally finish the TwoAddressInstructionPass rewrite; LiveVariables has been deprecated for a long time, we just cannot throw it out because of this one last pass.
• Easier fix: The critical edge splitting appears to be a part of PHIElimination that happens before anything else. If we would pull that out into a separate pass and perform it before computing LiveVariables, then we wouldn't need to go through the trouble of updating LiveVariables.

[MatzeB]

And I should mark this green. LGTM

[MatzeB]

In D33088#752373, @MatzeB wrote:

• Easier fix: The critical edge splitting appears to be a part of PHIElimination that happens before anything else. If we would pull that out into a separate pass and perform it before computing LiveVariables, then we wouldn't need to go through the trouble of updating LiveVariables.

Reading the code a bit more it seems that the critical edge splitting logic is already depending on liveness information so it's not that easy to fix.

[MatzeB]

And also slightly related: For the sort of queries that LiveVariables supports "Fast liveness checking for ssa-form programs" / https://doi.org/10.1145/1356058.1356064 would be a perfect fit. However given that the long term goal would be to replace all of this with LiveIntervalAnalysis, it's probably not worth pursuing that here.

[davide]

In D33088#752378, @MatzeB wrote:

And also slightly related: For the sort of queries that LiveVariables supports "Fast liveness checking for ssa-form programs" / https://doi.org/10.1145/1356058.1356064 would be a perfect fit. However given that the long term goal would be to replace all of this with LiveIntervalAnalysis, it's probably not worth pursuing that here.

Coincidence, I was right now reading the same paper https://hal.inria.fr/inria-00192219/document (Google helped me finding it).
If this still turns out to be a problem for my org (the original bugreport is reduced from a case we hit in the wild) I'll take a look at it, but it's nowhere near the top of my list, unfortunately.

[sanjoy]

How big does the set get? Did you try using SmallDenseSet instead?

[davide]

In D33088#752754, @sanjoy wrote:

How big does the set get? Did you try using SmallDenseSet instead?

I don't have numbers off-hand, but I'll run my experiments and follow up here.

[davide]

In D33088#752754, @sanjoy wrote:

How big does the set get? Did you try using SmallDenseSet instead?

Hi Sanjoy, I tried to switch to SmallDenseSet and that slows down things a little
2min38sec -> 2min55sec`

My set doesn't grow too much, it's < 100 elements, roughly.

Feel free to follow-up if you have any questions, and thanks for your comment!

Davide

[davide]

In particular, the time spent in EliminatePHI goes from

92.7229 ( 59.4%)   0.0100 (  1.1%)  92.7329 ( 59.0%)  92.7333 ( 59.0%)  Eliminate PHI nodes for register allocation

to

107.5286 ( 62.0%)   0.0090 (  1.1%)  107.5375 ( 61.7%)  107.5381 ( 61.7%)  Eliminate PHI nodes for register allocation

llvm/trunk/lib/CodeGen/LiveVariables.cpp

 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
 /// variables that are live out of DomBB will be marked as passing live through
 /// BB.
 void LiveVariables::addNewBlock(MachineBasicBlock *BB,
                                 MachineBasicBlock *DomBB,
                                 MachineBasicBlock *SuccBB) {
   const unsigned NumNew = BB->getNumber();
 
-  SmallSet<unsigned, 16> Defs, Kills;
+  DenseSet<unsigned> Defs, Kills;
 
   MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
   for (; BBI != BBE && BBI->isPHI(); ++BBI) {
     // Record the def of the PHI node.
     Defs.insert(BBI->getOperand(0).getReg());
 
     // All registers used by PHI nodes in SuccBB must be live through BB.
     for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2)