diff --git a/llvm/include/llvm/CodeGen/TargetInstrInfo.h b/llvm/include/llvm/CodeGen/TargetInstrInfo.h
--- a/llvm/include/llvm/CodeGen/TargetInstrInfo.h
+++ b/llvm/include/llvm/CodeGen/TargetInstrInfo.h
@@ -193,7 +193,7 @@
   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();
   }
@@ -211,7 +211,7 @@
   /// 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();
diff --git a/llvm/lib/Target/AVR/AVRInstrInfo.h b/llvm/lib/Target/AVR/AVRInstrInfo.h
--- a/llvm/lib/Target/AVR/AVRInstrInfo.h
+++ b/llvm/lib/Target/AVR/AVRInstrInfo.h
@@ -112,6 +112,10 @@
                                 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;
 };
diff --git a/llvm/lib/Target/AVR/AVRInstrInfo.cpp b/llvm/lib/Target/AVR/AVRInstrInfo.cpp
--- a/llvm/lib/Target/AVR/AVRInstrInfo.cpp
+++ b/llvm/lib/Target/AVR/AVRInstrInfo.cpp
@@ -570,5 +570,24 @@
     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
 
diff --git a/llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll b/llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AVR/bug-2021-01-29-complex-frame-pointer-usage.ll
@@ -0,0 +1,39 @@
+; 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
+}
+