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

[foad]

Summary

This adds better support for call frame pseudos that adjust SP in
PEI::replaceFrameIndicesBackward.

Running frame index elimination backwards is preferred because it can
do backwards register scavenging (on targets that require scavenging)
which does not rely on accurate kill flags.

llvm/lib/CodeGen/PrologEpilogInserter.cpp

private:
   void replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
                            int &SPAdj);
   // Frame indices in debug values are encoded in a target independent
   // way with simply the frame index and offset rather than any
   // target-specific addressing mode.
   bool replaceFrameIndexDebugInstr(MachineFunction &MF, MachineInstr &MI,
                                    unsigned OpIdx, int SPAdj = 0);
   // Does same as replaceFrameIndices but using the backward MIR walk and
-  // backward register scavenger walk. Does not yet support call sequence
-  // processing.
+  // backward register scavenger walk.
+  void replaceFrameIndicesBackward(MachineFunction &MF);
   void replaceFrameIndicesBackward(MachineBasicBlock *BB, MachineFunction &MF,
                                    int &SPAdj);
 
   void insertPrologEpilogCode(MachineFunction &MF);
   void insertZeroCallUsedRegs(MachineFunction &MF);
 };
 
 } // end anonymous namespace
for (auto &I : EntryDbgValues)
     I.first->insert(I.first->begin(), I.second.begin(), I.second.end());
 
   // Allow the target machine to make final modifications to the function
   // before the frame layout is finalized.
   TFI->processFunctionBeforeFrameIndicesReplaced(MF, RS);
 
   // Replace all MO_FrameIndex operands with physical register references
   // and actual offsets.
-  //
+  if (TFI->needsFrameIndexResolution(MF)) {
+    // Allow the target to determine this after knowing the frame size.
+    FrameIndexEliminationScavenging =
+        (RS && !FrameIndexVirtualScavenging) ||
+        TRI->requiresFrameIndexReplacementScavenging(MF);
+
+    if (TRI->supportsBackwardScavenger())
+      replaceFrameIndicesBackward(MF);
+    else
       replaceFrameIndices(MF);
+  }
 
   // If register scavenging is needed, as we've enabled doing it as a
   // post-pass, scavenge the virtual registers that frame index elimination
   // inserted.
   if (TRI->requiresRegisterScavenging(MF) && FrameIndexVirtualScavenging)
     scavengeFrameVirtualRegs(MF, *RS);
 
   // Warn on stack size when we exceeds the given limit.
for (MCRegister Reg : TRI.sub_and_superregs_inclusive(CSReg))
       RegsToZero.reset(Reg);
 
   const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
   for (MachineBasicBlock &MBB : MF)
     if (MBB.isReturnBlock())
       TFI.emitZeroCallUsedRegs(RegsToZero, MBB);
 }
 
+/// Replace all FrameIndex operands with physical register references and actual
+/// offsets.
+void PEI::replaceFrameIndicesBackward(MachineFunction &MF) {
+  const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
+
+  for (auto &MBB : MF) {
+    int SPAdj = 0;
+    if (!MBB.succ_empty()) {
+      // Get the SP adjustment for the end of MBB from the start of any of its
+      // successors. They should all be the same.
+      assert(all_of(MBB.successors(), [&MBB](const MachineBasicBlock *Succ) {
+        return Succ->getCallFrameSize() ==
+               (*MBB.succ_begin())->getCallFrameSize();
+      }));
+      const MachineBasicBlock &FirstSucc = **MBB.succ_begin();
+      SPAdj = TFI.alignSPAdjust(FirstSucc.getCallFrameSize());
+      if (TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsUp)
+        SPAdj = -SPAdj;
+    }
+
+    replaceFrameIndicesBackward(&MBB, MF, SPAdj);
+
+    // We can't track the call frame size after call frame pseudos have been
+    // eliminated. Set it to zero everywhere to keep MachineVerifier happy.
+    MBB.setCallFrameSize(0);
+  }
+}
+
 /// replaceFrameIndices - Replace all MO_FrameIndex operands with physical
 /// register references and actual offsets.
 void PEI::replaceFrameIndices(MachineFunction &MF) {
-  const auto &ST = MF.getSubtarget();
-  const TargetFrameLowering &TFI = *ST.getFrameLowering();
-  if (!TFI.needsFrameIndexResolution(MF))
-    return;
-
-  const TargetRegisterInfo *TRI = ST.getRegisterInfo();
-
-  // Allow the target to determine this after knowing the frame size.
-  FrameIndexEliminationScavenging = (RS && !FrameIndexVirtualScavenging) ||
-    TRI->requiresFrameIndexReplacementScavenging(MF);
+  const TargetFrameLowering &TFI = *MF.getSubtarget().getFrameLowering();
 
   for (auto &MBB : MF) {
     int SPAdj = TFI.alignSPAdjust(MBB.getCallFrameSize());
     if (TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsUp)
       SPAdj = -SPAdj;
 
     replaceFrameIndices(&MBB, MF, SPAdj);
 
void PEI::replaceFrameIndicesBackward(MachineBasicBlock *BB,
   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))) {
     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())
         continue;
 
       if (replaceFrameIndexDebugInstr(MF, MI, i, 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, RS);
+      bool Removed = TRI.eliminateFrameIndex(MI, SPAdj, i, LocalRS);
       if (LocalRS)
   LocalRS->skipTo(std::prev(Save));
 
       if (Removed)
         break;
     }
   }
 }
 
 void PEI::replaceFrameIndices(MachineBasicBlock *BB, MachineFunction &MF,
                               int &SPAdj) {
   assert(MF.getSubtarget().getRegisterInfo() &&
          "getRegisterInfo() must be implemented!");
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
 
-  if (TRI.supportsBackwardScavenger())
-    return replaceFrameIndicesBackward(BB, MF, SPAdj);
-
   if (RS && FrameIndexEliminationScavenging)
     RS->enterBasicBlock(*BB);
 
   bool InsideCallSequence = false;
 
   for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
     if (TII.isFrameInstr(*I)) {
       InsideCallSequence = TII.isFrameSetup(*I);

llvm/lib/Target/ARM/ARMBaseRegisterInfo.h

emitLoadConstPool(MachineBasicBlock &MBB, MachineBasicBlock::iterator &MBBI,
                     Register PredReg = Register(),
                     unsigned MIFlags = MachineInstr::NoFlags) const;
 
   /// Code Generation virtual methods...
   bool requiresRegisterScavenging(const MachineFunction &MF) const override;
 
   bool requiresFrameIndexScavenging(const MachineFunction &MF) const override;
 
+  bool supportsBackwardScavenger() const override { return true; }
+
   bool requiresVirtualBaseRegisters(const MachineFunction &MF) const override;
 
   bool eliminateFrameIndex(MachineBasicBlock::iterator II,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
   /// SrcRC and DstRC will be morphed into NewRC if this returns true
   bool shouldCoalesce(MachineInstr *MI,

llvm/test/CodeGen/Thumb/emergency-spill-slot.ll

 ; CHECK-LABEL: simple_emergency_spill:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r4, r5, r6, r7, lr}
 ; CHECK-NEXT:    push {r4, r5, r6, r7, lr}
 ; CHECK-NEXT:    ldr r7, .LCPI1_0
 ; CHECK-NEXT:    .pad #8196
 ; CHECK-NEXT:    add sp, r7
 ; CHECK-NEXT:    add r0, sp, #4
-; CHECK-NEXT:    ldr r1, .LCPI1_2
+; CHECK-NEXT:    ldr r1, .LCPI1_3
 ; CHECK-NEXT:    add r1, sp
 ; CHECK-NEXT:    @APP
 ; CHECK-NEXT:    @NO_APP
 ; CHECK-NEXT:    str r0, [sp]
-; CHECK-NEXT:    ldr r0, .LCPI1_3
+; CHECK-NEXT:    ldr r0, .LCPI1_2
 ; CHECK-NEXT:    add r0, sp
 ; CHECK-NEXT:    str r5, [r0]
 ; CHECK-NEXT:    ldr r0, [sp]
 ; CHECK-NEXT:    @APP
 ; CHECK-NEXT:    @NO_APP
 ; CHECK-NEXT:    ldr r7, .LCPI1_1
 ; CHECK-NEXT:    add sp, r7
 ; CHECK-NEXT:    pop {r4, r5, r6, r7, pc}
 ; CHECK-NEXT:    .p2align 2
 ; CHECK-NEXT:  @ %bb.1:
 ; CHECK-NEXT:  .LCPI1_0:
 ; CHECK-NEXT:    .long 4294959100 @ 0xffffdffc
 ; CHECK-NEXT:  .LCPI1_1:
 ; CHECK-NEXT:    .long 8196 @ 0x2004
 ; CHECK-NEXT:  .LCPI1_2:
-; CHECK-NEXT:    .long 4100 @ 0x1004
-; CHECK-NEXT:  .LCPI1_3:
 ; CHECK-NEXT:    .long 5120 @ 0x1400
+; CHECK-NEXT:  .LCPI1_3:
+; CHECK-NEXT:    .long 4100 @ 0x1004
 entry:
   %x = alloca [1024 x i32], align 4
   %y = alloca [1024 x i32], align 4
   %asm1 = call { i32, i32, i32, i32, i32, i32, i32, i32 } asm "", "={r0},={r1},={r2},={r3},={r4},={r5},={r6},={r7},0,1,2,3,4,5,6,7"(ptr %y, ptr %x, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef)
   %asmresult = extractvalue { i32, i32, i32, i32, i32, i32, i32, i32 } %asm1, 0
   %asmresult2 = extractvalue { i32, i32, i32, i32, i32, i32, i32, i32 } %asm1, 1
   %asmresult3 = extractvalue { i32, i32, i32, i32, i32, i32, i32, i32 } %asm1, 2
   %asmresult4 = extractvalue { i32, i32, i32, i32, i32, i32, i32, i32 } %asm1, 3

 ; CHECK-LABEL: simple_emergency_spill_nor7:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r4, r5, r6, lr}
 ; CHECK-NEXT:    push {r4, r5, r6, lr}
 ; CHECK-NEXT:    ldr r6, .LCPI2_0
 ; CHECK-NEXT:    .pad #8196
 ; CHECK-NEXT:    add sp, r6
 ; CHECK-NEXT:    add r0, sp, #4
-; CHECK-NEXT:    ldr r1, .LCPI2_2
+; CHECK-NEXT:    ldr r1, .LCPI2_3
 ; CHECK-NEXT:    add r1, sp
 ; CHECK-NEXT:    @APP
 ; CHECK-NEXT:    @NO_APP
 ; CHECK-NEXT:    str r7, [sp]
-; CHECK-NEXT:    ldr r7, .LCPI2_3
+; CHECK-NEXT:    ldr r7, .LCPI2_2
 ; CHECK-NEXT:    add r7, sp
 ; CHECK-NEXT:    str r5, [r7]
 ; CHECK-NEXT:    ldr r7, [sp]
 ; CHECK-NEXT:    @APP
 ; CHECK-NEXT:    @NO_APP
 ; CHECK-NEXT:    ldr r6, .LCPI2_1
 ; CHECK-NEXT:    add sp, r6
 ; CHECK-NEXT:    pop {r4, r5, r6, pc}
 ; CHECK-NEXT:    .p2align 2
 ; CHECK-NEXT:  @ %bb.1:
 ; CHECK-NEXT:  .LCPI2_0:
 ; CHECK-NEXT:    .long 4294959100 @ 0xffffdffc
 ; CHECK-NEXT:  .LCPI2_1:
 ; CHECK-NEXT:    .long 8196 @ 0x2004
 ; CHECK-NEXT:  .LCPI2_2:
-; CHECK-NEXT:    .long 4100 @ 0x1004
-; CHECK-NEXT:  .LCPI2_3:
 ; CHECK-NEXT:    .long 5120 @ 0x1400
+; CHECK-NEXT:  .LCPI2_3:
+; CHECK-NEXT:    .long 4100 @ 0x1004
 entry:
   %x = alloca [1024 x i32], align 4
   %y = alloca [1024 x i32], align 4
   %asm1 = call { i32, i32, i32, i32, i32, i32, i32 } asm "", "={r0},={r1},={r2},={r3},={r4},={r5},={r6},0,1,2,3,4,5,6"(ptr %y, ptr %x, i32 undef, i32 undef, i32 undef, i32 undef, i32 undef)
   %asmresult = extractvalue { i32, i32, i32, i32, i32, i32, i32 } %asm1, 0
   %asmresult2 = extractvalue { i32, i32, i32, i32, i32, i32, i32 } %asm1, 1
   %asmresult3 = extractvalue { i32, i32, i32, i32, i32, i32, i32 } %asm1, 2
   %asmresult4 = extractvalue { i32, i32, i32, i32, i32, i32, i32 } %asm1, 3