[AggressiveAntiDepBreaker] Refix renaming a subregister of a live register

[foad]

Summary

This patch reworks the fix from D20627 "Do not rename registers that do
not start an independent live range". That fix depended on the scheduler
dependency graph having redundant edges. Those edges are removed by
D156552 "[MachineScheduler] Track physical register dependencies
per-regunit" with the result that on several Hexagon lit tests, the
post-RA scheduler would schedule the code in a way that fails machine
verification.

Consider this code where D11 is a pair R23:R22:

SU(0): %R2<def> = A2_add %R23, %R17<kill>
    (anti dependency on R23 here)
SU(8): %R23<def> = S2_asr_i_r %R22, 31
    (data dependency on R23->D11 here)
SU(10): %D0<def> = A2_tfrp %D11<kill>

The original fix would detect this situation by examining the dependency
from SU(8) to SU(10) and seeing that D11 is not a subreg of R23.

A slightly more complicated example:

SU(0): %R2<def> = A2_add %R23, %R17<kill>
    (anti dependency on R23 here)
SU(8): %R23<def> = S2_asr_i_r %R22, 31
    (data dependency on R23 here)
SU(9): %R23<def> = S2_asr_i_r %R23, 31
    (data dependency on R23->D11 here)
SU(10): %D0<def> = A2_tfrp %D11<kill>

The original fix also worked on this example, but only because
ScheduleDAGInstrs adds an extra data dependency edge directly from SU(8)
to SU(10). This edge is redundant, since you could infer it transitively
from the edges SU(8)->SU(9) and SU(9)->SU(10), and since none of the
data that SU(8) writes to R23 is read by SU(10).

After D156552 the redundant edge SU(8)->SU(10) will not be present, so
when we examine the successors of SU(8) we will not find any that read
from a superreg of R23.

This patch removes the original fix from D20627, which examined edges in
the dependency graph. Instead it extends a check that was already being
done in FindSuitableFreeRegisters: instead of checking that *some*
register is a superreg of all registers in the rename group, we now
check that the specific register that carries the anti-dependency that
we want to break is a superreg of all registers in the rename group.

[arsenm]

llvm/lib/CodeGen/AggressiveAntiDepBreaker.h

179–181

use Register instead of unsigned

[arsenm]

I don't know if there are any legitimate reasons to use MCRegAliasIterator anymore, deleting them is good

[foad]

llvm/lib/CodeGen/AggressiveAntiDepBreaker.h

179–181

Good idea, but I'd prefer to do that as a separate cleanup for all the code in this pass.

llvm/lib/CodeGen/AggressiveAntiDepBreaker.h

private:
     void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag,
                        const char *header = nullptr,
                        const char *footer = nullptr);
 
     void PrescanInstruction(MachineInstr &MI, unsigned Count,
                             std::set<unsigned> &PassthruRegs);
     void ScanInstruction(MachineInstr &MI, unsigned Count);
     BitVector GetRenameRegisters(unsigned Reg);
-    bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex,
-                                   RenameOrderType& RenameOrder,
+    bool FindSuitableFreeRegisters(unsigned SuperReg,
+                                   unsigned AntiDepGroupIndex,
+                                   RenameOrderType &RenameOrder,
                                    std::map<unsigned, unsigned> &RenameMap);
   };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H

llvm/lib/CodeGen/AggressiveAntiDepBreaker.cpp

for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) {
 
     LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC));
   }
 
   return BV;
 }
 
 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters(
-                                unsigned AntiDepGroupIndex,
-                                RenameOrderType& RenameOrder,
-                                std::map<unsigned, unsigned> &RenameMap) {
+    unsigned SuperReg, unsigned AntiDepGroupIndex, RenameOrderType &RenameOrder,
   std::vector<unsigned> &KillIndices = State->GetKillIndices();
   std::vector<unsigned> &DefIndices = State->GetDefIndices();
   std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>&
     RegRefs = State->GetRegRefs();
 
   // Collect all referenced registers in the same group as
   // AntiDepReg. These all need to be renamed together if we are to
   // break the anti-dependence.
   std::vector<unsigned> Regs;
   State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs);
   assert(!Regs.empty() && "Empty register group!");
   if (Regs.empty())
     return false;
 
-  // Find the "superest" register in the group. At the same time,
-  // collect the BitVector of registers that can be used to rename
+  // Collect the BitVector of registers that can be used to rename
   // each register.
   LLVM_DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex
                     << ":\n");
   std::map<unsigned, BitVector> RenameRegisterMap;
-  unsigned SuperReg = 0;
   for (unsigned Reg : Regs) {
-    if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg))
-      SuperReg = Reg;
-
     // If Reg has any references, then collect possible rename regs
     if (RegRefs.count(Reg) > 0) {
       LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":");
 
       BitVector &BV = RenameRegisterMap[Reg];
       assert(BV.empty());
       BV = GetRenameRegisters(Reg);
 
if (!MI.isKill()) {
                        (Pred.getKind() == SDep::Data) &&
                        (Pred.getReg() == AntiDepReg)) {
               LLVM_DEBUG(dbgs() << " (other dependency)\n");
               AntiDepReg = 0;
               break;
             }
           }
 
-          if (AntiDepReg == 0) continue;
-
-          // If the definition of the anti-dependency register does not start
-          // a new live range, bail out. This can happen if the anti-dep
-          // register is a sub-register of another register whose live range
-          // spans over PathSU. In such case, PathSU defines only a part of
-          // the larger register.
-          RegAliases.reset();
-          for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI)
-            RegAliases.set(*AI);
-          for (SDep S : PathSU->Succs) {
-            SDep::Kind K = S.getKind();
-            if (K != SDep::Data)
-              continue;
-            unsigned R = S.getReg();
-            if (!RegAliases[R])
-              continue;
-            if (TRI->isSubRegisterEq(AntiDepReg, R))
-              continue;
-            AntiDepReg = 0;
-            break;
-          }
-
-          if (AntiDepReg == 0) continue;
+          if (AntiDepReg == 0)
         }
 
         assert(AntiDepReg != 0);
 
         // Determine AntiDepReg's register group.
         const unsigned GroupIndex = State->GetGroup(AntiDepReg);
         if (GroupIndex == 0) {
           LLVM_DEBUG(dbgs() << " (zero group)\n");
           continue;
         }
 
         LLVM_DEBUG(dbgs() << '\n');
 
         // Look for a suitable register to use to break the anti-dependence.
         std::map<unsigned, unsigned> RenameMap;
-        if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) {
+        if (FindSuitableFreeRegisters(AntiDepReg, GroupIndex, RenameOrder,
+                                      RenameMap)) {
           LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on "
                             << printReg(AntiDepReg, TRI) << ":");
 
           // Handle each group register...
           for (const auto &P : RenameMap) {
             unsigned CurrReg = P.first;
             unsigned NewReg = P.second;