[NFC][regalloc] Make VirtRegAuxInfo part of allocator state

[mtrofin]

Summary

All the state of VRAI is allocator-wide, so we can avoid creating it every time we need it, to simplify readability - the way weights are calculated is decided per algorithm. In addition, the normalization function is allocator-specific. In a next change, we can simplify that design in favor of just having it as a virtual member. This also enables experimenting with alternative weight calculation mechanisms, where the decision on which to use is made in one place (i.e. where the VRAI is instantiated).

[qcolombet]

Hi,

From the perspective of the caller, this patch exposes some implementation details that I am not sure are worth it.

Put differently, what is the expected benefits of moving VRAI life-time to the allocators?

VRAI are relatively light-weight objects and I wouldn't expect saving on the constructor to bring us any gain. So what are we after here?

Cheers,
-Quentin

[mtrofin]

In D88499#2301230, @qcolombet wrote:

Hi,

From the perspective of the caller, this patch exposes some implementation details that I am not sure are worth it.

Put differently, what is the expected benefits of moving VRAI life-time to the allocators?

VRAI are relatively light-weight objects and I wouldn't expect saving on the constructor to bring us any gain. So what are we after here?

Cheers,
-Quentin

Indeed, it's not a performance issue, I see the motivation may read that way. It's helping with readability around weight calculation. The patch clarifies that the way we calculate weights is a per-allocation algorithm concern - including which normalization function we use. When looking at Greedy, for example, it's easier to read that "weight calculation always happens the same way". My next step would be to then make the normalization a virtual, and have a PBQPVirtRegAuxInfo overriding it.

Finally, as another next step, it simplifies exploring other weight calculation strategies: we make weightCalcHelper virtual, and go from there. Same reasoning as above - in Greedy, for instance, we can then just instantiate the desired VirtRegAuxInfo variant in the one place, rather than chasing all instantiation sites.

[qcolombet]

When looking at Greedy, for example, it's easier to read that "weight calculation always happens the same way".

I see. The readability improvement is worth it, I agree.

llvm/include/llvm/CodeGen/CalcSpillWeights.h

public:
     ///               before start will not affect the weight. Relevant for
     ///               weight calculation of future split artifact.
     /// \param end    The expected end of the split artifact. Instructions
     ///               after end will not affect the weight. Relevant for
     ///               weight calculation of future split artifact.
     /// \return The spill weight. Returns negative weight for unspillable li.
     float weightCalcHelper(LiveInterval &li, SlotIndex *start = nullptr,
                            SlotIndex *end = nullptr);
-  };
 
     /// Compute spill weights and allocation hints for all virtual register
     /// live intervals.
-  void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF,
-                                     VirtRegMap *VRM,
-                                     const MachineLoopInfo &MLI,
-                                     const MachineBlockFrequencyInfo &MBFI,
-                                     VirtRegAuxInfo::NormalizingFn norm =
-                                         normalizeSpillWeight);
-
+    void calculateSpillWeightsAndHints();
+  };
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H

llvm/lib/CodeGen/CalcSpillWeights.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 #include <tuple>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "calcspillweights"
 
-void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS,
-                           MachineFunction &MF,
-                           VirtRegMap *VRM,
-                           const MachineLoopInfo &MLI,
-                           const MachineBlockFrequencyInfo &MBFI,
-                           VirtRegAuxInfo::NormalizingFn norm) {
+void VirtRegAuxInfo::calculateSpillWeightsAndHints() {
   LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
                     << "********** Function: " << MF.getName() << '\n');
 
   MachineRegisterInfo &MRI = MF.getRegInfo();
-  VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
-  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
-    unsigned Reg = Register::index2VirtReg(i);
+  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
+    unsigned Reg = Register::index2VirtReg(I);
     if (MRI.reg_nodbg_empty(Reg))
       continue;
-    VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg));
+    calculateSpillWeightAndHint(LIS.getInterval(Reg));
   }
 }
 
 // Return the preferred allocation register for reg, given a COPY instruction.
 static Register copyHint(const MachineInstr *mi, unsigned reg,
                          const TargetRegisterInfo &tri,
                          const MachineRegisterInfo &mri) {
   unsigned sub, hsub;

llvm/lib/CodeGen/RegAllocBasic.cpp

 bool RABasic::runOnMachineFunction(MachineFunction &mf) {
   LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
                     << "********** Function: " << mf.getName() << '\n');
 
   MF = &mf;
   RegAllocBase::init(getAnalysis<VirtRegMap>(),
                      getAnalysis<LiveIntervals>(),
                      getAnalysis<LiveRegMatrix>());
-
-  calculateSpillWeightsAndHints(*LIS, *MF, VRM,
-                                getAnalysis<MachineLoopInfo>(),
-                                getAnalysis<MachineBlockFrequencyInfo>());
+  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(),
+  VRAI.calculateSpillWeightsAndHints();
 
   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
 
   allocatePhysRegs();
   postOptimization();
 
   // Diagnostic output before rewriting
   LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");

llvm/lib/CodeGen/RegAllocGreedy.cpp

class RAGreedy : public MachineFunctionPass,
   SpillPlacement *SpillPlacer;
   LiveDebugVariables *DebugVars;
   AliasAnalysis *AA;
 
   // state
   std::unique_ptr<Spiller> SpillerInstance;
   PQueue Queue;
   unsigned NextCascade;
+  std::unique_ptr<VirtRegAuxInfo> VRAI;
 
   // Live ranges pass through a number of stages as we try to allocate them.
   // Some of the stages may also create new live ranges:
   //
   // - Region splitting.
   // - Per-block splitting.
   // - Local splitting.
   // - Spilling.
if (!LIS->hasInterval(Evictor))
     return false;
   LiveInterval &EvictorLI = LIS->getInterval(Evictor);
   if (EvictorLI.FindSegmentContaining(Cand.Intf.first()) == EvictorLI.end())
     return false;
 
   // Now, check to see if the local interval we will create is going to be
   // expensive enough to evict somebody If so, this may cause a bad eviction
   // chain.
-  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
   float splitArtifactWeight =
-      VRAI.futureWeight(LIS->getInterval(Evictee),
+      VRAI->futureWeight(LIS->getInterval(Evictee),
                          Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
   if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
     return false;
 
   return true;
 }
 
 /// Check if splitting VirtRegToSplit will create a local split interval
 /// in basic block number BBNumber that may cause a spill.
bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit,
   // Check if the local interval will evict a cheaper interval.
   float CheapestEvictWeight = 0;
   unsigned FutureEvictedPhysReg = getCheapestEvicteeWeight(
       Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
       Cand.Intf.last(), &CheapestEvictWeight);
 
   // Have we found an interval that can be evicted?
   if (FutureEvictedPhysReg) {
-    VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
     float splitArtifactWeight =
-        VRAI.futureWeight(LIS->getInterval(VirtRegToSplit),
+        VRAI->futureWeight(LIS->getInterval(VirtRegToSplit),
                            Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
     // Will the weight of the local interval be higher than the cheapest evictee
     // weight? If so it will evict it and will not cause a spill.
     if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
       return false;
   }
 
   // The local interval is not able to find non interferencing assignment and
   // not able to evict a less worthy interval, therfore, it can cause a spill.
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   Loops = &getAnalysis<MachineLoopInfo>();
   Bundles = &getAnalysis<EdgeBundles>();
   SpillPlacer = &getAnalysis<SpillPlacement>();
   DebugVars = &getAnalysis<LiveDebugVariables>();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   initializeCSRCost();
 
-  calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
+  VRAI = std::make_unique<VirtRegAuxInfo>(*MF, *LIS, VRM, *Loops, *MBFI);
+
+  VRAI->calculateSpillWeightsAndHints();
 
   LLVM_DEBUG(LIS->dump());
 
   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
   SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
   ExtraRegInfo.clear();
   ExtraRegInfo.resize(MRI->getNumVirtRegs());
   NextCascade = 1;

llvm/lib/CodeGen/RegAllocPBQP.cpp

 
 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
   LiveIntervals &LIS = getAnalysis<LiveIntervals>();
   MachineBlockFrequencyInfo &MBFI =
     getAnalysis<MachineBlockFrequencyInfo>();
 
   VirtRegMap &VRM = getAnalysis<VirtRegMap>();
 
-  calculateSpillWeightsAndHints(LIS, MF, &VRM, getAnalysis<MachineLoopInfo>(),
-                                MBFI, normalizePBQPSpillWeight);
+  VirtRegAuxInfo VRAI(MF, LIS, &VRM, getAnalysis<MachineLoopInfo>(), MBFI,
+                      normalizePBQPSpillWeight);
+  VRAI.calculateSpillWeightsAndHints();
 
   std::unique_ptr<Spiller> VRegSpiller(createInlineSpiller(*this, MF, VRM));
 
   MF.getRegInfo().freezeReservedRegs(MF);
 
   LLVM_DEBUG(dbgs() << "PBQP Register Allocating for " << MF.getName() << "\n");
 
   // Allocator main loop: