LiveRegUnits: Add accumulateBackward() function

[MatzeB]

Summary

This function can be used to accumulate the set of all read and modified
register in a sequence of instructions.

Use this code in RegisterScavenging.cpp:findSurvivorBackwards() and
AArch64A57FPLoadBalancing::scavengeRegister():

• The register scavenging code is a bit more efficient since we avoid needless transformation of a register unit live set into a register live set.

• The behaviour of findSurvivorBackwards() is slightly changed: In case of multiple possibilities the first register in the register class instead of the one with the smallest number is picked.

• The AArch64A57LoadBalancing code is using a backwards analysis now which is irrespective of kill flags. This is the main motivation for this change.

[MatzeB]

ping

[qcolombet]

include/llvm/CodeGen/LiveRegUnits.h

81 ↗

(On Diff #63015)

Rename into addRegsNotPreservedByMask.

lib/CodeGen/RegisterScavenging.cpp

358 ↗

(On Diff #63015)

\p To

571 ↗

(On Diff #63015)

You didn’t like the assert :P.

lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

507 ↗

(On Diff #63015)

That would be weird, but, to be safe, shouldn’t we do the test before the call to stepBackward, i.e., if MBB is empty that will crash, right?

[Eugene.Zelenko]

Looks like patch was not committed.

[MatzeB]

In D22082#551191, @Eugene.Zelenko wrote:

Looks like patch was not committed.

This patch depends on D21916: Add LiveRegUnits class. which was committed but subsequently reverted (phab cannot express that). The situation is not resolved yet.

[MatzeB]

In the interest of not having this lying around uncommitted for much longer, I am committing this without the RegisterScavenging parts (the RegisterScavenging rewrite this was based on caused build failures).

llvm/trunk/include/llvm/CodeGen/LiveRegUnits.h

void removeReg(unsigned Reg) {
     for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
       Units.reset(*Unit);
   }
 
   /// Removes register units not preserved by the regmask \p RegMask.
   /// The regmask has the same format as the one in the RegMask machine operand.
   void removeRegsNotPreserved(const uint32_t *RegMask);
 
+  /// Adds register units not preserved by the regmask \p RegMask.
+  /// The regmask has the same format as the one in the RegMask machine operand.
+  void addRegsInMask(const uint32_t *RegMask);
+
   /// Returns true if no part of physical register \p Reg is live.
   bool available(unsigned Reg) const {
     for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
       if (Units.test(*Unit))
         return false;
     }
     return true;
   }
 
   /// Updates liveness when stepping backwards over the instruction \p MI.
   void stepBackward(const MachineInstr &MI);
 
+  /// Mark all register units live during instruction \p MI.
+  /// This can be used to accumulate live/unoccupied registers over a range of
+  /// instructions.
+  void accumulateBackward(const MachineInstr &MI);
+
   /// Adds registers living out of block \p MBB.
   /// Live out registers are the union of the live-in registers of the successor
   /// blocks and pristine registers. Live out registers of the end block are the
   /// callee saved registers.
   void addLiveOuts(const MachineBasicBlock &MBB);
 
   /// Adds registers living into block \p MBB.
   void addLiveIns(const MachineBasicBlock &MBB);

llvm/trunk/lib/CodeGen/LiveRegUnits.cpp

void LiveRegUnits::removeRegsNotPreserved(const uint32_t *RegMask) {
   for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) {
     for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) {
       if (MachineOperand::clobbersPhysReg(RegMask, *RootReg))
         Units.reset(U);
     }
   }
 }
 
+void LiveRegUnits::addRegsInMask(const uint32_t *RegMask) {
+  for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) {
+    for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) {
+      if (MachineOperand::clobbersPhysReg(RegMask, *RootReg))
+        Units.set(U);
+    }
+  }
+}
+
 void LiveRegUnits::stepBackward(const MachineInstr &MI) {
   // Remove defined registers and regmask kills from the set.
   for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
     if (O->isReg()) {
       if (!O->isDef())
         continue;
       unsigned Reg = O->getReg();
       if (!TargetRegisterInfo::isPhysicalRegister(Reg))
if (!O->isReg() || !O->readsReg())
       continue;
     unsigned Reg = O->getReg();
     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
       continue;
     addReg(Reg);
   }
 }
 
+void LiveRegUnits::accumulateBackward(const MachineInstr &MI) {
+  // Add defs, uses and regmask clobbers to the set.
+  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
+    if (O->isReg()) {
+      unsigned Reg = O->getReg();
+      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
+        continue;
+      if (!O->isDef() && !O->readsReg())
+        continue;
+      addReg(Reg);
+    } else if (O->isRegMask())
+      addRegsInMask(O->getRegMask());
+  }
+}
+
 /// Add live-in registers of basic block \p MBB to \p LiveUnits.
 static void addLiveIns(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
   for (const auto &LI : MBB.liveins())
     LiveUnits.addRegMasked(LI.PhysReg, LI.LaneMask);
 }
 
 static void addLiveOuts(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
   // To get the live-outs we simply merge the live-ins of all successors.

llvm/trunk/lib/Target/AArch64/AArch64A57FPLoadBalancing.cpp

while (Chain *G = getAndEraseNext(PreferredColor, GV)) {
     PreferredColor = Parity < 0 ? Color::Even : Color::Odd;
   }
 
   return Changed;
 }
 
 int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C,
                                                 MachineBasicBlock &MBB) {
-  RegScavenger RS;
-  RS.enterBasicBlock(MBB);
-  RS.forward(MachineBasicBlock::iterator(G->getStart()));
-
   // Can we find an appropriate register that is available throughout the life
-  // of the chain?
-  unsigned RegClassID = G->getStart()->getDesc().OpInfo[0].RegClass;
-  BitVector AvailableRegs = RS.getRegsAvailable(TRI->getRegClass(RegClassID));
-  for (MachineBasicBlock::iterator I = G->begin(), E = G->end(); I != E; ++I) {
-    RS.forward(I);
-    AvailableRegs &= RS.getRegsAvailable(TRI->getRegClass(RegClassID));
-
-    // Remove any registers clobbered by a regmask or any def register that is
-    // immediately dead.
-    for (auto J : I->operands()) {
-      if (J.isRegMask())
-        AvailableRegs.clearBitsNotInMask(J.getRegMask());
-
-      if (J.isReg() && J.isDef()) {
-        MCRegAliasIterator AI(J.getReg(), TRI, /*IncludeSelf=*/true);
-        if (J.isDead())
-          for (; AI.isValid(); ++AI)
-            AvailableRegs.reset(*AI);
-#ifndef NDEBUG
-        else
-          for (; AI.isValid(); ++AI)
-            assert(!AvailableRegs[*AI] &&
-                   "Non-dead def should have been removed by now!");
-#endif
-      }
-    }
-  }
+  // of the chain? Simulate liveness backwards until the end of the chain.
+  LiveRegUnits Units(*TRI);
+  Units.addLiveOuts(MBB);
+  MachineBasicBlock::iterator I = MBB.end(), ChainEnd = G->end();
+  do {
+    --I;
+    Units.stepBackward(*I);
+  } while (I != ChainEnd);
+
+  // Check which register units are alive throughout the chain.
+  MachineBasicBlock::iterator ChainBegin = G->begin();
+  assert(ChainBegin != ChainEnd && "Chain should contain instructions");
+  do {
+    --I;
+    Units.accumulateBackward(*I);
+  } while (I != ChainBegin);
 
   // Make sure we allocate in-order, to get the cheapest registers first.
+  unsigned RegClassID = ChainBegin->getDesc().OpInfo[0].RegClass;
   auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID));
   for (auto Reg : Ord) {
-    if (!AvailableRegs[Reg])
+    if (!Units.available(Reg))
       continue;
     if (C == getColor(Reg))
       return Reg;
   }
 
   return -1;
 }