X86, PEI, WIP: Convert to backwards frame index elimination

[foad]

Summary

Add support for call sequences to the backwards implementation of frame
index elimination and convert X86 to use it.

The goal is to convert all targets to backwards frame index elimination
and backwards register scavenging, which is preferred because it does
not rely on accurate kill flags.

X86 does not actually scavenge registers during frame index elimination
but doing the conversion is useful for flushing out problems in the call
sequence handling.

[foad]

This is WIP. Some codegen tests fail. I need help on a couple of X86 things please:

1. X86InstrInfo::getSPAdjust gets information about the stack adjustment of a CALL by searching for the following ADJCALLSTACKUP. That doesn't work if you're processing the basic block backwards, since the ADJCALLSTACKUP will already have been eliminated. Can I somehow put the information in the preceding ADJCALLSTACKDOWN instead? I see that both opcodes take two immediate values but I have not found good documentation on what they mean.

2. When PEI::replaceFrameIndicesBackward(MachineFunction &) processes a basic block that ends with a return, it assumes that SPAdj is 0 at the end of the block. I think it needs to account for return instructions like "RET 4", which move SP by 4, but currently PEI only calls getSPAdjust on instructions which are "frame setup" or "frame destroy" or part of a call sequence - and RET is none of those things. Is there a clean way to handle this?

llvm/lib/Target/X86/X86InstrInfo.cpp

427

I now think that this is just wrong, since operand(1) of ADJCALLSTACKDOWN is a completely different thing from operand(1) of ADJCALLSTACKUP.

[foad]

Rebase.

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);
 
+  bool InsideCallSequence = false;
   for (MachineBasicBlock::iterator I = BB->end(); I != BB->begin();) {
     MachineInstr &MI = *std::prev(I);
 
     if (TII.isFrameInstr(MI)) {
+      InsideCallSequence = !TII.isFrameSetup(MI);
       SPAdj -= TII.getSPAdjust(MI);
       TFI.eliminateCallFramePseudoInstr(MF, *BB, &MI);
       continue;
     }
 
+    // If we are looking at a call sequence, we need to keep track of
+    // the SP adjustment made by each instruction in the sequence.
+    // This includes both the frame setup/destroy pseudos (handled above),
+    // as well as other instructions that have side effects w.r.t the SP.
+    if (InsideCallSequence)
+      SPAdj -= TII.getSPAdjust(MI);
+
     // Step backwards to get the liveness state at (immedately after) MI.
     if (LocalRS)
       LocalRS->backward(MI);
 
     bool RemovedMI = false;
     for (const auto &[Idx, Op] : enumerate(MI.operands())) {
       if (!Op.isFI())
         continue;

llvm/lib/Target/X86/X86InstrInfo.cpp

if (isFrameInstr(MI)) {
     int SPAdj = alignTo(getFrameSize(MI), TFI->getStackAlign());
     SPAdj -= getFrameAdjustment(MI);
     if (!isFrameSetup(MI))
       SPAdj = -SPAdj;
     return SPAdj;
   }
 
   // To know whether a call adjusts the stack, we need information
-  // that is bound to the following ADJCALLSTACKUP pseudo.
-  // Look for the next ADJCALLSTACKUP that follows the call.
+  // that is bound to the preceding ADJCALLSTACKDOWN pseudo.
+  // Look for the next ADJCALLSTACKDOWN that precedes the call.
   if (MI.isCall()) {
     const MachineBasicBlock *MBB = MI.getParent();
-    auto I = ++MachineBasicBlock::const_iterator(MI);
-    for (auto E = MBB->end(); I != E; ++I) {
-      if (I->getOpcode() == getCallFrameDestroyOpcode() ||
+    auto I = MachineBasicBlock::const_iterator(MI);
+    for (auto E = MBB->begin(); I-- != E; ) {
+      if (I->getOpcode() == getCallFrameSetupOpcode() ||
           I->isCall())
         break;
     }
 
-    // If we could not find a frame destroy opcode, then it has already
+    // If we could not find a frame setup opcode, then it has already
     // been simplified, so we don't care.
-    if (I->getOpcode() != getCallFrameDestroyOpcode())
+    if (I->getOpcode() != getCallFrameSetupOpcode())
       return 0;
 
-    return -(I->getOperand(1).getImm());
+    return I->getOperand(1).getImm();
   }
 
   // Currently handle only PUSHes we can reasonably expect to see
   // in call sequences
   switch (MI.getOpcode()) {
   default:
     return 0;
   case X86::PUSH32r:

llvm/lib/Target/X86/X86RegisterInfo.h

public:
   void eliminateFrameIndex(MachineBasicBlock::iterator II,
                            unsigned FIOperandNum, Register BaseReg,
                            int FIOffset) const;
 
   bool eliminateFrameIndex(MachineBasicBlock::iterator MI,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS = nullptr) const override;
 
+  bool supportsBackwardScavenger() const override { return true; }
+
   /// findDeadCallerSavedReg - Return a caller-saved register that isn't live
   /// when it reaches the "return" instruction. We can then pop a stack object
   /// to this register without worry about clobbering it.
   unsigned findDeadCallerSavedReg(MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator &MBBI) const;
 
   // Debug information queries.
   Register getFrameRegister(const MachineFunction &MF) const override;