[CodeGen] Store SP adjustment in MachineBasicBlock. NFCI.

[foad]

Summary

Record the SP adjustment on entry to each basic block. This is almost
always zero except on targets like ARM which can split a basic block in
the middle of a call sequence.

This simplifies PEI::replaceFrameIndices which previously had to visit
basic blocks in a specific order and had special handling for
unreachable blocks. More importantly it paves the way for an equally
simple implementation of a backwards version of replaceFrameIndices,
which is required to fully convert PrologEpilogInserter to backwards
register scavenging, which is preferred because it does not rely on
accurate kill flags.

[foad]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

118

On 64-bit hosts this fills a hole in the struct so does not increase the size of MachineBasicBlock.

[arsenm]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

118

Needs mir serialization

[foad]

Add MIR serialization.

[foad]

llvm/lib/CodeGen/MIRParser/MIParser.cpp

685 ↗

(On Diff #536534)

This won't work for negative values but in practice this value is always >= 0 for ARM (and == 0 for all other in-tree targets). I don't know whether it could ever reasonably be negative on other targets.

[arsenm]

Missing MIR parse/print tests

llvm/include/llvm/CodeGen/MachineBasicBlock.h

118

Also the llvm-reduce mir cloner should copy this

llvm/lib/Target/ARM/ARMISelLowering.cpp

11370

[foad]

Update.

[foad]

Missing MIR parse/print tests

Added.

[arsenm]

Should the verifier check the block stored adjustment matches the calls in the block?

[foad]

In D154281#4493465, @arsenm wrote:

Should the verifier check the block stored adjustment matches the calls in the block?

That would be nice, and it would fit naturally in MachineVerifier::verifyStackFrame. But after PEI eliminates call frame setup instructions, you can no longer infer the SP adjustment by examining the instructions in a block. I don't know how to handle that case.

[chapuni]

llvm/lib/CodeGen/PrologEpilogInserter.cpp

1350–1353

Only +Asserts?

[foad]

In D154281#4493757, @foad wrote:

In D154281#4493465, @arsenm wrote:

Should the verifier check the block stored adjustment matches the calls in the block?

That would be nice, and it would fit naturally in MachineVerifier::verifyStackFrame. But after PEI eliminates call frame setup instructions, you can no longer infer the SP adjustment by examining the instructions in a block. I don't know how to handle that case.

I am tempted to revert this patch while I work on the machine verification aspect. I am having second thoughts about whether "sp adjustment" is the right abstraction to store in the basic block - maybe "frame size" or "frame total size" would make more sense.

[olista01]

Hi, this change has caused a regression in one of our tests:

#include <assert.h>
#include <alloca.h>
#include <stdio.h>

struct S51 {
  int M50[20];
};

struct S2 {
  int a, b;
};

struct S2 F38(struct S51 P4) {
  int V0 = 14;
  __asm("" : "+r"(V0));
  char *V1 = (char *)alloca(V0);
  __asm volatile("" : : "r"(V1));

  struct S2 result = {1, 2};
  return result;
}

signed int main(void) {
  struct S51 P4 = {0};
  struct S2 ret = F38(P4);

  assert(ret.a == 1);
  assert(ret.b == 2);

  return 0;
}

$ /work/ac6/build-armclang/bin/clang --target=arm--none-eabi -march=armv7-m -c test.c -O1 -o - -S
...
main:
        .fnstart
@ %bb.0:                                @ %entry
        .save   {r4, r6, r7, lr}
        push    {r4, r6, r7, lr}
        .setfp  r7, sp, #8
        add     r7, sp, #8
        .pad    #160
        sub     sp, #160
        add     r4, sp, #80
        mov     r0, r4
        movs    r1, #80
        bl      __aeabi_memclr4
        mov     r0, sp
        add.w   r1, r4, #12
        movs    r2, #68
.LBB1_1:                                @ %entry
                                        @ =>This Inner Loop Header: Depth=1
        ldr     r3, [r1], #4
        subs    r2, #4
        str     r3, [r0], #4
        bne     .LBB1_1
@ %bb.2:                                @ %entry
        add     r3, sp, #152
        ldm     r3, {r1, r2, r3}
        add     r0, sp, #144
        bl      F38
        ldr     r0, [sp, #144]
        cmp     r0, #1
        bne     .LBB1_5
@ %bb.3:                                @ %cond.end
        ldr     r0, [sp, #76]
        cmp     r0, #2
        ittt    eq
        moveq   r0, #0
        addeq   sp, #160
        popeq   {r4, r6, r7, pc}
.LBB1_4:                                @ %cond.false5
        movw    r0, :lower16:.L.str.2
        movw    r1, :lower16:.L.str.1
        movt    r0, :upper16:.L.str.2
        movt    r1, :upper16:.L.str.1
        movs    r2, #30
        bl      __aeabi_assert
.LBB1_5:                                @ %cond.false
        movw    r0, :lower16:.L.str
        movw    r1, :lower16:.L.str.1
        movt    r0, :upper16:.L.str
        movt    r1, :upper16:.L.str.1
        movs    r2, #29
        bl      __aeabi_assert
.Lfunc_end1:
...

The bug is in the code generated for main: according to the ARM ABI, the return type of F38 should be passed in memory provided by the caller, with a pointer to it passed in r0. The code for main sets this to SP+144, and reads the first member of the struct from that address, but then reads the second member from SP+76, instead of SP+148.

[foad]

@olista01 thanks for the test case! It would be great if there were more like this in the existing lit tests :)

[luporl]

Just for the record, these buildbots were also failing, in llvm-test-suite, with this patch:
https://lab.llvm.org/buildbot/#/builders/174/builds/22768
https://lab.llvm.org/buildbot/#/builders/186/builds/10783

They are passing again now.

[foad]

@luporl thanks, I will check that before trying to reland anything.

llvm/include/llvm/CodeGen/MachineBasicBlock.h

RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
         : PhysReg(PhysReg), LaneMask(LaneMask) {}
   };
 
 private:
   using Instructions = ilist<MachineInstr, ilist_sentinel_tracking<true>>;
 
   const BasicBlock *BB;
   int Number;
+
+  /// The SP adjustment on entry to this basic block due to call frame setup
+  /// instructions in a predecessor. This is almost always zero, unless basic
+  /// blocks are split in the middle of a call sequence.
+  int SPAdjustment = 0;
+
   MachineFunction *xParent;
   Instructions Insts;
 
   /// Keep track of the predecessor / successor basic blocks.
   std::vector<MachineBasicBlock *> Predecessors;
   std::vector<MachineBasicBlock *> Successors;
 
   /// Keep track of the probabilities to the successors. This vector has the
public:
   // Printing method used by LoopInfo.
   void printAsOperand(raw_ostream &OS, bool PrintType = true) const;
 
   /// MachineBasicBlocks are uniquely numbered at the function level, unless
   /// they're not in a MachineFunction yet, in which case this will return -1.
   int getNumber() const { return Number; }
   void setNumber(int N) { Number = N; }
 
+  /// Return the SP adjustment on entry to this basic block.
+  int getSPAdjustment() const { return SPAdjustment; }
+  /// Set the SP adjustment on entry to this basic block.
+  void setSPAdjustment(int N) { SPAdjustment = N; }
+
   /// Return the MCSymbol for this basic block.
   MCSymbol *getSymbol() const;
 
   /// Return the EHCatchret Symbol for this basic block.
   MCSymbol *getEHCatchretSymbol() const;
 
   std::optional<uint64_t> getIrrLoopHeaderWeight() const {
     return IrrLoopHeaderWeight;

llvm/lib/CodeGen/PrologEpilogInserter.cpp

 //
 // This pass must be run after register allocation.  After this pass is
 // executed, it is illegal to construct MO_FrameIndex operands.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
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);
 
-  // Store SPAdj at exit of a basic block.
-  SmallVector<int, 8> SPState;
-  SPState.resize(MF.getNumBlockIDs());
-  df_iterator_default_set<MachineBasicBlock*> Reachable;
-
-  // Iterate over the reachable blocks in DFS order.
-  for (auto DFI = df_ext_begin(&MF, Reachable), DFE = df_ext_end(&MF, Reachable);
-       DFI != DFE; ++DFI) {
-    int SPAdj = 0;
-    // Check the exit state of the DFS stack predecessor.
-    if (DFI.getPathLength() >= 2) {
-      MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
-      assert(Reachable.count(StackPred) &&
-             "DFS stack predecessor is already visited.\n");
-      SPAdj = SPState[StackPred->getNumber()];
-    }
-    MachineBasicBlock *BB = *DFI;
-    replaceFrameIndices(BB, MF, SPAdj);
-    SPState[BB->getNumber()] = SPAdj;
-  }
-
-  // Handle the unreachable blocks.
-  for (auto &BB : MF) {
-    if (Reachable.count(&BB))
-      // Already handled in DFS traversal.
-      continue;
-    int SPAdj = 0;
-    replaceFrameIndices(&BB, MF, SPAdj);
+  for (auto &MBB : MF) {
+    int SPAdj = MBB.getSPAdjustment();
+    replaceFrameIndices(&MBB, MF, SPAdj);
+
+    // If call frame pseudo ops have already been simplified then we can no
+    // longer track the SP adjustment (but that's OK because in that case, frame
+    // index elimination does not care about the SP adjustment).
+    if (!TFI.canSimplifyCallFramePseudos(MF)) {
+      for (auto *Succ : MBB.successors())
+        assert(Succ->getSPAdjustment() == SPAdj);
+    }
   }
 }
 
 bool PEI::replaceFrameIndexDebugInstr(MachineFunction &MF, MachineInstr &MI,
                                       unsigned OpIdx, int SPAdj) {
   const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
   if (MI.isDebugValue()) {

llvm/lib/Target/ARM/ARMISelLowering.h

private:
 
     SDValue OptimizeVFPBrcond(SDValue Op, SelectionDAG &DAG) const;
 
     void SetupEntryBlockForSjLj(MachineInstr &MI, MachineBasicBlock *MBB,
                                 MachineBasicBlock *DispatchBB, int FI) const;
 
     void EmitSjLjDispatchBlock(MachineInstr &MI, MachineBasicBlock *MBB) const;
 
+    int getSPAdjustment(MachineInstr &MI) const;
+
     MachineBasicBlock *EmitStructByval(MachineInstr &MI,
                                        MachineBasicBlock *MBB) const;
 
     MachineBasicBlock *EmitLowered__chkstk(MachineInstr &MI,
                                            MachineBasicBlock *MBB) const;
     MachineBasicBlock *EmitLowered__dbzchk(MachineInstr &MI,
                                            MachineBasicBlock *MBB) const;
     void addMVEVectorTypes(bool HasMVEFP);

llvm/lib/Target/ARM/ARMISelLowering.cpp

BuildMI(*BB, Pos, dl, TII->get(StOpc), AddrOut)
         .addReg(Data)
         .addReg(AddrIn)
         .addReg(0)
         .addImm(StSize)
         .add(predOps(ARMCC::AL));
   }
 }
 
+// Get the SP adjustment just before MI.
+int ARMTargetLowering::getSPAdjustment(MachineInstr &MI) const {
+  const TargetInstrInfo *TII = Subtarget->getInstrInfo();
+
+  // Search backwards from MI for the most recent call frame setup instruction.
+  MachineBasicBlock *MBB = MI.getParent();
+  for (auto &AdjI : reverse(make_range(MBB->instr_begin(), MI.getIterator()))) {
+    if (AdjI.getOpcode() == ARM::ADJCALLSTACKDOWN)
+      return TII->getSPAdjust(AdjI);
+  }
+
+  // If none was found, use the SP adjustment from the start of the basic block.
+  return MBB->getSPAdjustment();
+}
+
 MachineBasicBlock *
 ARMTargetLowering::EmitStructByval(MachineInstr &MI,
                                    MachineBasicBlock *BB) const {
   // This pseudo instruction has 3 operands: dst, src, size
   // We expand it to a loop if size > Subtarget->getMaxInlineSizeThreshold().
   // Otherwise, we will generate unrolled scalar copies.
   const TargetInstrInfo *TII = Subtarget->getInstrInfo();
   const BasicBlock *LLVM_BB = BB->getBasicBlock();
ARMTargetLowering::EmitStructByval(MachineInstr &MI,
   //   epilogue to handle left-over bytes
   //   [scratch, srcOut] = LDRB_POST(srcLoop, 1)
   //   [destOut] = STRB_POST(scratch, destLoop, 1)
   MachineBasicBlock *loopMBB = MF->CreateMachineBasicBlock(LLVM_BB);
   MachineBasicBlock *exitMBB = MF->CreateMachineBasicBlock(LLVM_BB);
   MF->insert(It, loopMBB);
   MF->insert(It, exitMBB);
 
+  // Set the SP adjustment on entry to the new basic blocks.
+  int SPAdj = getSPAdjustment(MI);
+  loopMBB->setSPAdjustment(SPAdj);
+  exitMBB->setSPAdjustment(SPAdj);
+
   // Transfer the remainder of BB and its successor edges to exitMBB.
   exitMBB->splice(exitMBB->begin(), BB,
                   std::next(MachineBasicBlock::iterator(MI)), BB->end());
   exitMBB->transferSuccessorsAndUpdatePHIs(BB);
 
   // Load an immediate to varEnd.
   Register varEnd = MRI.createVirtualRegister(TRC);
   if (Subtarget->useMovt()) {