[XCore] Use backwards scavenging in frame index elimination

[foad]

Summary

This is preferred because it does not rely on accurate kill flags.

[foad]

The lit test shows increased spilling/reloading of scavenged registers. Previously it was:

spill r4
  use r4
spill r5
  use r4 and r5
  use r5
reload r4
reload r5

Now it is:

spill r0
  use r0
reload r0
spill r1
spill r2
  use r1 and r2
reload r2
reload r1
spill r2
  use r2
reload r2

@fhahn this is because RegScavenger::findSurvivorReg[forwards] returns with a "restore point" as late as possible, but findSurvivorBackwards does not return with a "spill before" point as early as possible. It only chooses the earlier To and the earliest vreg operand it saw.

I assume the special handling of vreg operands is because it was designed to be used for PrologEpilogInserter::doScavengeFrameVirtualRegs (D21885). Now that it is being used for frame index elimination too, would it make sense to handle frame index operands similarly?

llvm/lib/Target/XCore/XCoreRegisterInfo.h

public:
   const MCPhysReg *getCalleeSavedRegs(const MachineFunction *MF) const override;
 
   BitVector getReservedRegs(const MachineFunction &MF) const override;
 
   bool requiresRegisterScavenging(const MachineFunction &MF) const override;
 
   bool useFPForScavengingIndex(const MachineFunction &MF) const override;
 
+  bool supportsBackwardScavenger() const override { return true; }
+
   bool eliminateFrameIndex(MachineBasicBlock::iterator II,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
   // Debug information queries.
   Register getFrameRegister(const MachineFunction &MF) const override;
 
   //! Return whether to emit frame moves
   static bool needsFrameMoves(const MachineFunction &MF);
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/Target/XCore/XCoreRegisterInfo.cpp

 static void InsertFPConstInst(MachineBasicBlock::iterator II,
                               const XCoreInstrInfo &TII,
                               unsigned Reg, unsigned FrameReg,
                               int Offset, RegScavenger *RS ) {
   assert(RS && "requiresRegisterScavenging failed");
   MachineInstr &MI = *II;
   MachineBasicBlock &MBB = *MI.getParent();
   DebugLoc dl = MI.getDebugLoc();
-  Register ScratchOffset = RS->scavengeRegister(&XCore::GRRegsRegClass, II, 0);
+  Register ScratchOffset =
+      RS->scavengeRegisterBackwards(XCore::GRRegsRegClass, II, false, 0);
   RS->setRegUsed(ScratchOffset);
   TII.loadImmediate(MBB, II, ScratchOffset, Offset);
 
   switch (MI.getOpcode()) {
   case XCore::LDWFI:
     BuildMI(MBB, II, dl, TII.get(XCore::LDW_3r), Reg)
           .addReg(FrameReg)
           .addReg(ScratchOffset, RegState::Kill)
static void InsertSPConstInst(MachineBasicBlock::iterator II,
   assert(RS && "requiresRegisterScavenging failed");
   MachineInstr &MI = *II;
   MachineBasicBlock &MBB = *MI.getParent();
   DebugLoc dl = MI.getDebugLoc();
   unsigned OpCode = MI.getOpcode();
 
   unsigned ScratchBase;
   if (OpCode==XCore::STWFI) {
-    ScratchBase = RS->scavengeRegister(&XCore::GRRegsRegClass, II, 0);
+    ScratchBase =
+        RS->scavengeRegisterBackwards(XCore::GRRegsRegClass, II, false, 0);
     RS->setRegUsed(ScratchBase);
   } else
     ScratchBase = Reg;
   BuildMI(MBB, II, dl, TII.get(XCore::LDAWSP_ru6), ScratchBase).addImm(0);
-  Register ScratchOffset = RS->scavengeRegister(&XCore::GRRegsRegClass, II, 0);
+  Register ScratchOffset =
+      RS->scavengeRegisterBackwards(XCore::GRRegsRegClass, II, false, 0);
   RS->setRegUsed(ScratchOffset);
   TII.loadImmediate(MBB, II, ScratchOffset, Offset);
 
   switch (OpCode) {
   case XCore::LDWFI:
     BuildMI(MBB, II, dl, TII.get(XCore::LDW_3r), Reg)
           .addReg(ScratchBase, RegState::Kill)
           .addReg(ScratchOffset, RegState::Kill)

llvm/test/CodeGen/XCore/scavenging.ll

entry:
   call void @g(ptr %x1, ptr %1) nounwind
   ret void
 }
 declare void @g(ptr, ptr)
 
 
 ; CHECK: .section .cp.rodata.cst4,"aMc",@progbits,4
 ; CHECK: .p2align  2
-; CHECK: [[ARG5:.LCPI[0-9_]+]]:
-; CHECK: .long   100003
 ; CHECK: [[INDEX0:.LCPI[0-9_]+]]:
-; CHECK: .long   80002
+; CHECK: .long   84002
 ; CHECK: [[INDEX1:.LCPI[0-9_]+]]:
-; CHECK: .long   81002
+; CHECK: .long   83002
 ; CHECK: [[INDEX2:.LCPI[0-9_]+]]:
 ; CHECK: .long   82002
 ; CHECK: [[INDEX3:.LCPI[0-9_]+]]:
-; CHECK: .long   83002
+; CHECK: .long   81002
 ; CHECK: [[INDEX4:.LCPI[0-9_]+]]:
-; CHECK: .long   84002
+; CHECK: .long   80002
+; CHECK: [[ARG5:.LCPI[0-9_]+]]:
+; CHECK: .long   100003
 ; CHECK: .text
 ; !FP + large frame: spill SR+SR = entsp 2 + 100000
 ; CHECK-LABEL: ScavengeSlots:
 ; CHECK: entsp 65535
 ; CHECK: extsp 34467
 ; scavenge r11
 ; CHECK: ldaw r11, sp[0]
-; scavenge r4 using SR spill slot
-; CHECK: stw r4, sp[1]
-; CHECK: ldw r4, cp[[[ARG5]]]
+; scavenge r0 using SR spill slot
+; CHECK: stw r0, sp[1]
+; CHECK: ldw r0, cp[[[ARG5]]]
 ; r11 used to load 5th argument
-; CHECK: ldw r11, r11[r4]
-; CHECK: ldaw r4, sp[0]
-; scavenge r5 using SR spill slot
-; CHECK: stw r5, sp[0]
-; CHECK: ldw r5, cp[[[INDEX0]]]
+; CHECK: ldw r11, r11[r0]
+; CHECK: ldw r0, sp[1]
+; scavenge r1 using SR spill slot
+; CHECK: stw r1, sp[1]
+; CHECK: ldaw r1, sp[0]
+; scavenge r2 using SR spill slot
+; CHECK: stw r2, sp[0]
+; CHECK: ldw r2, cp[[[INDEX4]]]
 ; r4 & r5 used by InsertSPConstInst() to emit STW_l3r instruction.
-; CHECK: stw r0, r4[r5]
+; CHECK: stw r0, r1[r2]
+; CHECK: ldw r2, sp[0]
+; CHECK: ldw r1, sp[1]
 ; CHECK: ldaw r0, sp[0]
-; CHECK: ldw r5, cp[[[INDEX1]]]
-; CHECK: stw r1, r0[r5]
+; scavenge r2 using SR spill slot
+; CHECK: stw r2, sp[1]
+; CHECK: ldw r2, cp[[[INDEX3]]]
+; CHECK: stw r1, r0[r2]
+; CHECK: ldw r2, sp[1]
 ; CHECK: ldw r1, cp[[[INDEX2]]]
 ; CHECK: stw r2, r0[r1]
-; CHECK: ldw r1, cp[[[INDEX3]]]
+; CHECK: ldw r1, cp[[[INDEX1]]]
 ; CHECK: stw r3, r0[r1]
-; CHECK: ldw r1, cp[[[INDEX4]]]
+; CHECK: ldw r1, cp[[[INDEX0]]]
 ; CHECK: stw r11, r0[r1]
 ; CHECK: ldaw sp, sp[65535]
-; CHECK: ldw r4, sp[1]
-; CHECK: ldw r5, sp[0]
 ; CHECK: retsp 34467
 define void @ScavengeSlots(i32 %r0, i32 %r1, i32 %r2, i32 %r3, i32 %r4) nounwind {
 entry:
   %Data = alloca [100000 x i32]
   %i0 = getelementptr inbounds [100000 x i32], ptr %Data, i32 0, i32 80000
   store volatile i32 %r0, ptr %i0
   %i1 = getelementptr inbounds [100000 x i32], ptr %Data, i32 0, i32 81000
   store volatile i32 %r1, ptr %i1
   %i2 = getelementptr inbounds [100000 x i32], ptr %Data, i32 0, i32 82000
   store volatile i32 %r2, ptr %i2
   %i3 = getelementptr inbounds [100000 x i32], ptr %Data, i32 0, i32 83000
   store volatile i32 %r3, ptr %i3
   %i4 = getelementptr inbounds [100000 x i32], ptr %Data, i32 0, i32 84000
   store volatile i32 %r4, ptr %i4
   ret void
 }