[PEI][PowerPC] Switch to backwards frame index elimination

[foad]

Summary

This adds support for reprocessing new instructions that were generated
by the target's eliminateFrameIndex.

Backwards frame index elimination uses backwards register scavenging,
which is preferred because it does not rely on accurate kill flags.

llvm/lib/CodeGen/PrologEpilogInserter.cpp

void PEI::replaceFrameIndicesBackward(MachineBasicBlock *BB,
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
 
   RegScavenger *LocalRS = FrameIndexEliminationScavenging ? RS : nullptr;
   if (LocalRS)
     LocalRS->enterBasicBlockEnd(*BB);
 
-  for (MachineInstr &MI : make_early_inc_range(reverse(*BB))) {
+  for (MachineBasicBlock::iterator I = BB->end(); I != BB->begin();) {
+    MachineInstr &MI = *std::prev(I);
+
     if (TII.isFrameInstr(MI)) {
       SPAdj -= TII.getSPAdjust(MI);
       TFI.eliminateCallFramePseudoInstr(MF, *BB, &MI);
       continue;
     }
 
     // Step backwards to get the liveness state at (immedately after) MI.
     if (LocalRS)
       LocalRS->backward(MI);
 
-    for (unsigned i = 0; i != MI.getNumOperands(); ++i) {
-      if (!MI.getOperand(i).isFI())
+    bool RemovedMI = false;
+    for (const auto &[Idx, Op] : enumerate(MI.operands())) {
+      if (!Op.isFI())
         continue;
 
-      if (replaceFrameIndexDebugInstr(MF, MI, i, SPAdj))
+      if (replaceFrameIndexDebugInstr(MF, MI, Idx, SPAdj))
         continue;
 
       // Eliminate this FrameIndex operand.
-      //
-      // Save and restore the scavenger's position around the call to
-      // eliminateFrameIndex in case it erases MI and invalidates the iterator.
-      MachineBasicBlock::iterator Save;
-      if (LocalRS)
-  Save = std::next(LocalRS->getCurrentPosition());
-      bool Removed = TRI.eliminateFrameIndex(MI, SPAdj, i, LocalRS);
-      if (LocalRS)
-  LocalRS->skipTo(std::prev(Save));
-
-      if (Removed)
+      RemovedMI = TRI.eliminateFrameIndex(MI, SPAdj, Idx, LocalRS);
+      if (RemovedMI)
         break;
     }
+
+    // Refresh the scavenger's internal iterator in case MI was removed or more
+    // instructions were inserted after it.
+    if (LocalRS)
+      LocalRS->skipTo(std::prev(I));
+
+    if (!RemovedMI)
+      --I;
   }
 }
 
 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
                               int &SPAdj) {
   assert(MF.getSubtarget().getRegisterInfo() &&
          "getRegisterInfo() must be implemented!");
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();

llvm/lib/Target/PowerPC/PPCRegisterInfo.h

public:
 
   /// We require the register scavenger.
   bool requiresRegisterScavenging(const MachineFunction &MF) const override {
     return true;
   }
 
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override;
 
+  bool supportsBackwardScavenger() const override { return true; }
+
   bool requiresVirtualBaseRegisters(const MachineFunction &MF) const override;
 
   void lowerDynamicAlloc(MachineBasicBlock::iterator II) const;
   void lowerDynamicAreaOffset(MachineBasicBlock::iterator II) const;
   void prepareDynamicAlloca(MachineBasicBlock::iterator II,
                             Register &NegSizeReg, bool &KillNegSizeReg,
                             Register &FramePointer) const;
   void lowerPrepareProbedAlloca(MachineBasicBlock::iterator II) const;