[AVR] Fix the eliminateCallFramePseudos method so that it always expands STDWSPQRr and STDSPQRr

[dylanmckay]

Summary

Before this bug was fixed, the newly added testcase would fail with the message:

LLVM ERROR: Not supported instr: <MCInst XXX <MCOperand Reg:1> <MCOperand Imm:15> <MCOperand Reg:53>>

  where XXX is the OpCode of either the STDWSPQRr instruction or the STDSPQRr instruction.

The issue was that the ISel lowering pass would lower many stack slot stores to these
instructions, but the frame pointer elimination code (that is designed to rewrite these two
instructions to real instructions) was only designed to run for STDWSPQRr/STDSPQRr instructions
that appeared in the basic blocks that contained the FrameSetup/FrameDestroy instructions.

The bug was fixed by modifying the code so that it unconditionally runs on STDWSPQRr/STDSPQRr
instructions and always expands them with the relevant STDWPtrQRr or STDPtrQRr instructions.

The bug is fixed by making the TargetInstrInfo::{isFrameInstr(), getFrameSize()} methods
virtual, and overriding them in the AVR backend. The LLVM middle end now
treats STDWSPQRr/STDSPQRr instructions as zero-sized frame instructions
so that they get the same treatment and are rewritten during call frame
pseudo elimination process, which is the one time we have enough
information to correctly rewrite STDWSPQRr/STDSPQRr operations to the stack
pointer.

This bug was originally discovered due to the Rust compiler_builtins library. Its 0.1.37 release
contained a 128-bit software division/remainder routine that exercised this buggy branch in the code.

[dylanmckay]

I've discovered an issue, this is not yet ready for review.

[dylanmckay]

Fix an assertion error caused by attempting to get the frame size of non-frame instructions

[arsenm]

This seems like a confusion of what frame instructions means. What do these stores have to do with call frames? The stores should reference frame indexes representing fixed frame objects in the incoming arguments or local objects. The frame adjust instructions are for SP modifications in call sequences where instructions are directly referencing offsets off of the SP, which do not have corresponding frame indexes

llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll

2–3

Disassembling here is a little bit weird. Why isn't directly emitting asm sufficent?

15–18

This sentence doesn't make sense to me. Frame index elimination is unrelated to frame setup / frame destroy.

[arsenm]

I just realized I've been reading "frame pointer elimination" as "frame index elimination" but this change still doesn't make sense to me. Why do you want to treat these stores as frame instructions when they don't modify the stack pointer?

[Rahix]

llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll

2–3

Maybe I can shed some light on this: The underlying bug manifested itself in the LLVM ERROR: Not supported instr: error shown below. This happens because the generated assembly actually still contains the STDWSPQRr or STDSPQRr pseudo instructions and it only starts failing once it is attempted to encode those in machine code (obviously, as they do not exist). Thus, if the test just generated the assembly, it would pass erroneously.

[stappers]

@arsenm and/or @bogner (plus other reviewers)

Please tell / explain / elaborate / make clear that the flag "This revision now requires changes to proceed." is still valid after the "it only starts failing once it is attempted to encode those pseudo instructions in machine code" comment from a month ago.

Other information for the "AVR instruction set world" what more to do as being patience, is also appreciated.

[wt]

I'm curious what needs to be done to push this forward. I would be happy to help if there's something I can do.

At the very least, I can confirm that the bug is real. And this issue it making it impossible to use a current toolchain to build software for AVR microcontrollers. If there's more that I can do, I'm willing to learn.

[mhjacobson]

In D95664#2660051, @arsenm wrote:

I just realized I've been reading "frame pointer elimination" as "frame index elimination" but this change still doesn't make sense to me. Why do you want to treat these stores as frame instructions when they don't modify the stack pointer?

Stepping in to try to answer this since I'm interested in a fix here.

It's true that these stack-store pseudos do not modify the stack pointer. However, their expansion depends on which register is used as the stack pointer (Y or Z), and AVRFrameLowering::eliminateCallFramePseudoInstr() is currently the place where that is known.

PEI::replaceFrameIndices calls eliminateCallFramePseudoInstr() only for instructions for which isFrameInstr() returns true. When AVRFrameLowering::eliminateCallFramePseudoInstr() is called, fixStackStores is called in turn to expand any stack-store pseudos in the remainder of the basic block. So making isFrameInstr() return true for stack-store pseudos causes eliminateCallFramePseudoInstr() to be called for them and fixStackStores() to expand them. (At that point, the loop inside fixStackStores() becomes redundant, I think.)

Perhaps the work of expanding these pseudos should be done elsewhere? AVRExpandPseudoInsts seems like the obvious place, but I'm not sure whether it has access to the requisite knowledge of which register contains the stack pointer.

[mhjacobson]

llvm/lib/Target/AVR/AVRInstrInfo.cpp

578

If fixStackStores() is now being called for each STDWSPQRr and STDSPQRr, does the loop inside fixStackStores() still make sense?

[dylanmckay]

I'm going to close this in favor of https://reviews.llvm.org/D114611 . I agree with Matt's comments about there being a bit of funny business going on in this PR, the concept is being generalized in core unnecessarily and does not strictly make sense in the place I put it. I think the approach in this other patch (thanks @Patryk27) is much more sensible.

Thanks for the reviews everybody. Very well thought out.

Also thanks for chiming in @mhjacobson, that is exactly where I was coming from. Well articulated. The conclusion about moving it to AVRExpandPseudoInsts is a good one that I don't think I made it to when I last looked at this some time ago (too long ago - I know!).

llvm/include/llvm/CodeGen/TargetInstrInfo.h

public:
   /// if they exist (-1 otherwise).  Some targets use pseudo instructions in
   /// order to abstract away the difference between operating with a frame
   /// pointer and operating without, through the use of these two instructions.
   ///
   unsigned getCallFrameSetupOpcode() const { return CallFrameSetupOpcode; }
   unsigned getCallFrameDestroyOpcode() const { return CallFrameDestroyOpcode; }
 
   /// Returns true if the argument is a frame pseudo instruction.
-  bool isFrameInstr(const MachineInstr &I) const {
+  virtual bool isFrameInstr(const MachineInstr &I) const {
     return I.getOpcode() == getCallFrameSetupOpcode() ||
            I.getOpcode() == getCallFrameDestroyOpcode();
   }
 
   /// Returns true if the argument is a frame setup pseudo instruction.
   bool isFrameSetup(const MachineInstr &I) const {
     return I.getOpcode() == getCallFrameSetupOpcode();
   }
 
   /// Returns size of the frame associated with the given frame instruction.
   /// For frame setup instruction this is frame that is set up space set up
   /// after the instruction. For frame destroy instruction this is the frame
   /// freed by the caller.
   /// Note, in some cases a call frame (or a part of it) may be prepared prior
   /// to the frame setup instruction. It occurs in the calls that involve
   /// inalloca arguments. This function reports only the size of the frame part
   /// that is set up between the frame setup and destroy pseudo instructions.
-  int64_t getFrameSize(const MachineInstr &I) const {
+  virtual int64_t getFrameSize(const MachineInstr &I) const {
     assert(isFrameInstr(I) && "Not a frame instruction");
     assert(I.getOperand(0).getImm() >= 0);
     return I.getOperand(0).getImm();
   }
 
   /// Returns the total frame size, which is made up of the space set up inside
   /// the pair of frame start-stop instructions and the space that is set up
   /// prior to the pair.

llvm/lib/Target/AVR/AVRInstrInfo.h

public:
   bool isBranchOffsetInRange(unsigned BranchOpc,
                              int64_t BrOffset) const override;
 
   unsigned insertIndirectBranch(MachineBasicBlock &MBB,
                                 MachineBasicBlock &NewDestBB,
                                 const DebugLoc &DL,
                                 int64_t BrOffset,
                                 RegScavenger *RS) const override;
+
+  bool isFrameInstr(const MachineInstr &MI) const override;
+  int64_t getFrameSize(const MachineInstr &I) const override;
+
 private:
   const AVRRegisterInfo RI;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_AVR_INSTR_INFO_H

llvm/lib/Target/AVR/AVRInstrInfo.cpp

unsigned AVRInstrInfo::insertIndirectBranch(MachineBasicBlock &MBB,
     // insertBranch or some hypothetical "insertDirectBranch".
     // See lib/CodeGen/RegisterRelaxation.cpp for details.
     // We end up here when a jump is too long for a RJMP instruction.
     auto &MI = *BuildMI(&MBB, DL, get(AVR::JMPk)).addMBB(&NewDestBB);
 
     return getInstSizeInBytes(MI);
 }
 
+bool AVRInstrInfo::isFrameInstr(const MachineInstr &MI) const {
+  return TargetInstrInfo::isFrameInstr(MI) ||
+         // Treat these pseudo stack store as frame instructions so that they
+         // can be expanded into real instructions and the frame pointer written
+         // out in 'fixStackStores(..)'.
+         MI.getOpcode() == AVR::STDWSPQRr || MI.getOpcode() == AVR::STDSPQRr;
+}
+
+int64_t AVRInstrInfo::getFrameSize(const MachineInstr &I) const {
+  switch (I.getOpcode()) {
+  // The pseudo stack store instructions don't actually change the frame size.
+  case AVR::STDWSPQRr:
+  case AVR::STDSPQRr:
+    return 0;
+  default:
+    return TargetInstrInfo::getFrameSize(I);
+  }
+}
+
 } // end of namespace llvm
 

llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll

+; RUN: llc < %s -march=avr -mcpu=atmega328 -filetype=obj -o /dev/null --print-options 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR
+; RUN: llc < %s -march=avr -mcpu=atmega328 -filetype=obj | llvm-objdump -S - | FileCheck %s --check-prefix=CHECK-OBJDUMP
+
+; This test verifies that the AVR backend can successfully lower code
+; which is very register heavy, containing many references to the frame
+; pointer.
+;
+; Before this bug was fixed, this testcase would fail with the message:
+;
+;   LLVM ERROR: Not supported instr: <MCInst XXX <MCOperand Reg:1> <MCOperand Imm:15> <MCOperand Reg:53>>
+;
+;     where XXX is the OpCode of either the STDWSPQRr instruction or the STDSPQRr instruction.
+;
+; The issue was that the ISel lowering pass would lower many stack slot stores to these
+; instructions, but the frame pointer elimination code (that is designed to rewrite these two
+; instructions to real instructions) was only designed to run for STDWSPQRr/STDSPQRr instructions
+; that appeared in the basic blocks that contained the FrameSetup/FrameDestroy instructions.
+;
+; The bug was fixed by modifying the code so that it unconditionally runs on STDWSPQRr/STDSPQRr
+; instructions and always expands them with the relevant STDWPtrQRr or STDPtrQRr instructions.
+;
+; This bug was originally discovered due to the Rust compiler_builtins library. Its 0.1.37 release
+; contained a 128-bit software division/remainder routine that exercised this buggy branch in the code.
+
+; CHECK-ERROR-NOT: LLVM ERROR: Not supported instr
+
+declare { i128, i128 } @div_rem_u128(i128, i128) addrspace(1)
+
+; CHECK-OBJDUMP-LABEL: main
+define i128 @main(i128 %a, i128 %b) addrspace(1) {
+start:
+  %b_neg = icmp slt i128 %b, 0
+  %divisor = select i1 %b_neg, i128 0, i128 %b
+  %result = tail call fastcc addrspace(1) { i128, i128 } @div_rem_u128(i128 undef, i128 %divisor)
+
+  ; CHECK-OBJDUMP: ret
+  ret i128 0
+}
+