[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

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/MIRParser/MILexer.h

enum TokenKind {
     kw_pcsections,
     kw_cfi_type,
     kw_bbsections,
     kw_bb_id,
     kw_unknown_size,
     kw_unknown_address,
     kw_ir_block_address_taken,
     kw_machine_block_address_taken,
+    kw_sp_adjustment,
 
     // Metadata types.
     kw_distinct,
 
     // Named metadata keywords
     md_tbaa,
     md_alias_scope,
     md_noalias,

llvm/lib/CodeGen/MIRParser/MILexer.cpp

return StringSwitch<MIToken::TokenKind>(Identifier)
       .Case("bbsections", MIToken::kw_bbsections)
       .Case("bb_id", MIToken::kw_bb_id)
       .Case("unknown-size", MIToken::kw_unknown_size)
       .Case("unknown-address", MIToken::kw_unknown_address)
       .Case("distinct", MIToken::kw_distinct)
       .Case("ir-block-address-taken", MIToken::kw_ir_block_address_taken)
       .Case("machine-block-address-taken",
             MIToken::kw_machine_block_address_taken)
+      .Case("sp-adjustment", MIToken::kw_sp_adjustment)
       .Default(MIToken::Identifier);
 }
 
 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
   if (!isalpha(C.peek()) && C.peek() != '_')
     return std::nullopt;
   auto Range = C;
   while (isIdentifierChar(C.peek()))

llvm/lib/CodeGen/MIRParser/MIParser.cpp

bool parseMachineOperandAndTargetFlags(const unsigned OpCode,
                                          MachineOperand &Dest,
                                          std::optional<unsigned> &TiedDefIdx);
   bool parseOffset(int64_t &Offset);
   bool parseIRBlockAddressTaken(BasicBlock *&BB);
   bool parseAlignment(uint64_t &Alignment);
   bool parseAddrspace(unsigned &Addrspace);
   bool parseSectionID(std::optional<MBBSectionID> &SID);
   bool parseBBID(std::optional<unsigned> &BBID);
+  bool parseSPAdjustment(int &SPAdjustment);
   bool parseOperandsOffset(MachineOperand &Op);
   bool parseIRValue(const Value *&V);
   bool parseMemoryOperandFlag(MachineMemOperand::Flags &Flags);
   bool parseMemoryPseudoSourceValue(const PseudoSourceValue *&PSV);
   bool parseMachinePointerInfo(MachinePointerInfo &Dest);
   bool parseOptionalScope(LLVMContext &Context, SyncScope::ID &SSID);
   bool parseOptionalAtomicOrdering(AtomicOrdering &Order);
   bool parseMachineMemoryOperand(MachineMemOperand *&Dest);
bool MIParser::parseBBID(std::optional<unsigned> &BBID) {
   unsigned Value = 0;
   if (getUnsigned(Value))
     return error("Unknown BB ID");
   BBID = Value;
   lex();
   return false;
 }
 
+// Parse basic block SP adjustment.
+bool MIParser::parseSPAdjustment(int &SPAdjustment) {
+  assert(Token.is(MIToken::kw_sp_adjustment));
+  lex();
+  unsigned Value = 0;
+  if (getUnsigned(Value) || !isInt<32>(Value))
+    return error("Unknown SP adjustment");
+  SPAdjustment = (int)Value;
+  lex();
+  return false;
+}
+
 bool MIParser::parseBasicBlockDefinition(
     DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   assert(Token.is(MIToken::MachineBasicBlockLabel));
   unsigned ID = 0;
   if (getUnsigned(ID))
     return true;
   auto Loc = Token.location();
   auto Name = Token.stringValue();
   lex();
   bool MachineBlockAddressTaken = false;
   BasicBlock *AddressTakenIRBlock = nullptr;
   bool IsLandingPad = false;
   bool IsInlineAsmBrIndirectTarget = false;
   bool IsEHFuncletEntry = false;
   std::optional<MBBSectionID> SectionID;
   uint64_t Alignment = 0;
   std::optional<unsigned> BBID;
+  int SPAdjustment = 0;
   BasicBlock *BB = nullptr;
   if (consumeIfPresent(MIToken::lparen)) {
     do {
       // TODO: Report an error when multiple same attributes are specified.
       switch (Token.kind()) {
       case MIToken::kw_machine_block_address_taken:
         MachineBlockAddressTaken = true;
         lex();
do {
       case MIToken::kw_bbsections:
         if (parseSectionID(SectionID))
           return true;
         break;
       case MIToken::kw_bb_id:
         if (parseBBID(BBID))
           return true;
         break;
+      case MIToken::kw_sp_adjustment:
+        if (parseSPAdjustment(SPAdjustment))
+          return true;
+        break;
       default:
         break;
       }
     } while (consumeIfPresent(MIToken::comma));
     if (expectAndConsume(MIToken::rparen))
       return true;
   }
   if (expectAndConsume(MIToken::colon))
bool MIParser::parseBasicBlockDefinition(
   }
   if (BBID.has_value()) {
     // BBSectionsType is set to `List` if any basic blocks has `SectionID`.
     // Here, we set it to `Labels` if it hasn't been set above.
     if (!MF.hasBBSections())
       MF.setBBSectionsType(BasicBlockSection::Labels);
     MBB->setBBID(BBID.value());
   }
+  MBB->setSPAdjustment(SPAdjustment);
   return false;
 }
 
 bool MIParser::parseBasicBlockDefinitions(
     DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   lex();
   // Skip until the first machine basic block.
   while (Token.is(MIToken::Newline))

llvm/lib/CodeGen/MachineBasicBlock.cpp

if (getSectionID() != MBBSectionID(0)) {
       }
       hasAttributes = true;
     }
     if (getBBID().has_value()) {
       os << (hasAttributes ? ", " : " (");
       os << "bb_id " << *getBBID();
       hasAttributes = true;
     }
+    if (SPAdjustment != 0) {
+      os << (hasAttributes ? ", " : " (");
+      os << "sp-adjustment " << SPAdjustment;
+      hasAttributes = true;
+    }
   }
 
   if (hasAttributes)
     os << ')';
 }
 
 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
                                        bool /*PrintType*/) const {

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 ARMBaseInstrInfo *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()) {

llvm/test/CodeGen/ARM/2013-06-03-ByVal-2Kbytes.ll

 ; RUN: llc < %s -mcpu=cortex-a15 | FileCheck %s
+; RUN: llc < %s -mcpu=cortex-a15 -stop-after=finalize-isel -o %t.mir
+; RUN: llc %t.mir -mcpu=cortex-a15 -start-after=finalize-isel -o - | FileCheck %s
 ; ModuleID = 'attri_16.c'
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:64:128-a0:0:64-n32-S64"
 target triple = "armv4t--linux-gnueabihf"
 
 %big_struct0 = type { [517 x i32] }
 %big_struct1 = type { [516 x i32] }
 
 ;CHECK-LABEL: f:

llvm/test/CodeGen/MIR/Generic/basic-blocks.mir

start:
     ret i32 0
   }
 
   define i32 @test() {
   start:
     ret i32 0
   }
 
+  define i32 @spadj() {
+  start:
+    ret i32 0
+  }
+
 ...
 ---
 # CHECK-LABEL: name: foo
 # CHECK: body:
 # CHECK-NEXT: bb.0.entry:
 name:            foo
 body: |
   bb.0.entry:

 # CHECK: body:
 # CHECK-NEXT: bb.0.start (machine-block-address-taken, align 4):
 # CHECK:      bb.1 (machine-block-address-taken, align 4):
 name:            test
 body: |
   bb.0.start (align 4, machine-block-address-taken):
   bb.1 (machine-block-address-taken, align 4):
 ...
+---
+# CHECK-LABEL: name: spadj
+# CHECK: body:
+# CHECK-NEXT: bb.0 (sp-adjustment 100):
+name: spadj
+body: |
+  bb.0 (sp-adjustment 100):
+...

llvm/tools/llvm-reduce/ReducerWorkItem.cpp

static std::unique_ptr<MachineFunction> cloneMF(MachineFunction *SrcMF,
   auto *DstMRI = &DstMF->getRegInfo();
 
   // Clone blocks.
   for (MachineBasicBlock &SrcMBB : *SrcMF) {
     MachineBasicBlock *DstMBB =
         DstMF->CreateMachineBasicBlock(SrcMBB.getBasicBlock());
     Src2DstMBB[&SrcMBB] = DstMBB;
 
+    DstMBB->setSPAdjustment(SrcMBB.getSPAdjustment());
+
     if (SrcMBB.isIRBlockAddressTaken())
       DstMBB->setAddressTakenIRBlock(SrcMBB.getAddressTakenIRBlock());
     if (SrcMBB.isMachineBlockAddressTaken())
       DstMBB->setMachineBlockAddressTaken();
 
     // FIXME: This is not serialized
     if (SrcMBB.hasLabelMustBeEmitted())
       DstMBB->setLabelMustBeEmitted();