Fix PR33031: Cannot scavenge register without an emergency spill slot.

[kristof.beyls]

Summary

Also see the discussion on https://bugs.llvm.org/show_bug.cgi?id=33031.

This patch contains 2 conceptual changes:

• Introducing option -reg-scavenging-always-use-spill-slot to enable writing maintainable tests for register scavenging.
• Fix the underlying reason for PR33031: correct the estimate of maximum offset for instructions spilling/filling the stack.

I think both conceptual changes are implemented in a somewhat non-ideal way here, but those are the best engineering tradeoffs I've found so far.
Do the trade-offs taken here seem acceptable?

[srhines]

lib/Target/AArch64/AArch64FrameLowering.cpp

1202

There is a subtle bug here. You have to use 255 for Limit in the estimateRSStackSizeLimit function now, because you aren't checking for >=. If the stack size is exactly 256 bytes, you wouldn't create the emergency spill slot, which is necessary because 256 can't be encoded as an offset.

[MatzeB]

Introducing option -reg-scavenging-always-use-spill-slot to enable writing maintainable tests for register scavenging.

That seems like a lot of machinery to test this. How about just adding a debug print and matching for that? Alternatively you should be able to match the extra spillslot in the stack: section of the mir file maybe?

lib/Target/AArch64/AArch64FrameLowering.cpp

140

Don't repeat the function name in the doxygen comment (old code does that but we don't do it anymore in new code).

143

Just do it? (Or remove the FIXME)

149

Please spell MachineBasicBlock instead of auto that is friendlier to the reader. We tend to only use auto in contexts where the type is immediately clear such as auto X = dyn_cast<SomeType>(...).
Same with the next loop.

162

Simply return 0;?

[MatzeB]

lib/Target/AArch64/AArch64FrameLowering.cpp

125

unnecessary?

[kristof.beyls]

Thanks all for the review comments!

I believe I've addressed them all in this updated patch.
I've dropped introducing the command line option -reg-scavenging-always-use-spill-slot. In the end I realized (should have realized that earlier), that with running a single pass in llc, it is possible to write a pretty stable test, even if register pressure must be extremely high in exactly the right place in the code.
I think the new regression test for this now looks nice, and definitely nice enough to not pollute the register scavenger with a special mode just for testing.

[MatzeB]

LGTM

[MatzeB]

lib/Target/AArch64/AArch64FrameLowering.cpp

160

How about putting an extra assert(Offset < 255); here to be sure?

[MatzeB]

lib/Target/AArch64/AArch64FrameLowering.cpp

160

or rather assert(Offset < 256); I guess.

[kristof.beyls]

lib/Target/AArch64/AArch64FrameLowering.cpp

160

The AArch64FrameOffsetCannotUpdate return value should already guarantee that Offset must remain 0; but it doesn't hurt to add the assert.
I'll do that and commit after I've finished running a bootstrap test on this patch.
The regression tests (obviously) and the test-suite pass.

[MatzeB]

... test-suite pass.

BTW: I tend to leaving testing of llvm test-suite to the bots, unless I have a reason to believe that a patch breaks it. Otherwise it's hard to get work done if you need an hour or more of testing before pushing a patch...

[kristof.beyls]

committed in r304196.

lib/Target/AArch64/AArch64FrameLowering.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "frame-info"
 
 static cl::opt<bool> EnableRedZone("aarch64-redzone",
                                    cl::desc("enable use of redzone on AArch64"),
                                    cl::init(false), cl::Hidden);
 
 STATISTIC(NumRedZoneFunctions, "Number of functions using red zone");
 
+/// Look at each instruction that references stack frames and return the stack
+/// size limit beyond which some of these instructions will require a scratch
+/// register during their expansion later.
+static unsigned estimateRSStackSizeLimit(MachineFunction &MF) {
+  // FIXME: For now, just conservatively guestimate based on unscaled indexing
+  // range. We'll end up allocating an unnecessary spill slot a lot, but
+  // realistically that's not a big deal at this stage of the game.
+  for (MachineBasicBlock &MBB : MF) {
+    for (MachineInstr &MI : MBB) {
+      if (MI.isDebugValue() || MI.isPseudo() ||
+          MI.getOpcode() == AArch64::ADDXri ||
+          MI.getOpcode() == AArch64::ADDSXri)
+        continue;
+      for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
+        if (!MI.getOperand(i).isFI())
+          continue;
+
+        int Offset = 0;
+        if (isAArch64FrameOffsetLegal(MI, Offset, nullptr, nullptr, nullptr) ==
+            AArch64FrameOffsetCannotUpdate)
+          return 0;
+      }
+    }
+  }
+  return 255;
+}
+
 bool AArch64FrameLowering::canUseRedZone(const MachineFunction &MF) const {
   if (!EnableRedZone)
     return false;
   // Don't use the red zone if the function explicitly asks us not to.
   // This is typically used for kernel code.
   if (MF.getFunction()->hasFnAttribute(Attribute::NoRedZone))
     return false;
 
DEBUG(dbgs() << "*** determineCalleeSaves\nUsed CSRs:";
         for (unsigned Reg : SavedRegs.set_bits())
           dbgs() << ' ' << PrintReg(Reg, RegInfo);
         dbgs() << "\n";);
 
   // If any callee-saved registers are used, the frame cannot be eliminated.
   unsigned NumRegsSpilled = SavedRegs.count();
   bool CanEliminateFrame = NumRegsSpilled == 0;
 
-  // FIXME: Set BigStack if any stack slot references may be out of range.
-  // For now, just conservatively guestimate based on unscaled indexing
-  // range. We'll end up allocating an unnecessary spill slot a lot, but
-  // realistically that's not a big deal at this stage of the game.
   // The CSR spill slots have not been allocated yet, so estimateStackSize
   // won't include them.
   MachineFrameInfo &MFI = MF.getFrameInfo();
   unsigned CFSize = MFI.estimateStackSize(MF) + 8 * NumRegsSpilled;
   DEBUG(dbgs() << "Estimated stack frame size: " << CFSize << " bytes.\n");
-  bool BigStack = (CFSize >= 256);
+  unsigned EstimatedStackSizeLimit = estimateRSStackSizeLimit(MF);
+  bool BigStack = (CFSize > EstimatedStackSizeLimit);
   if (BigStack || !CanEliminateFrame || RegInfo->cannotEliminateFrame(MF))
     AFI->setHasStackFrame(true);
 
   // Estimate if we might need to scavenge a register at some point in order
   // to materialize a stack offset. If so, either spill one additional
   // callee-saved register or reserve a special spill slot to facilitate
   // register scavenging. If we already spilled an extra callee-saved register
   // above to keep the number of spills even, we don't need to do anything else

test/CodeGen/AArch64/reg-scavenge-frame.mir

+# RUN: llc -run-pass=prologepilog -verify-machineinstrs %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+  target triple = "aarch64-linux-gnu"
+  define void @ScavengeForFrameWithoutOffset() { ret void }
+...
+---
+name:            ScavengeForFrameWithoutOffset
+tracksRegLiveness: true
+stack:
+  - { id: 0, type: spill-slot, offset: 0, size: 32, alignment: 8 }
+body:             |
+  bb.0:
+    liveins: %d16_d17_d18_d19
+    %x0 = COPY %xzr
+    %x1 = COPY %xzr
+    %x2 = COPY %xzr
+    %x3 = COPY %xzr
+    %x4 = COPY %xzr
+    %x5 = COPY %xzr
+    %x6 = COPY %xzr
+    %x7 = COPY %xzr
+    %x8 = COPY %xzr
+    %x9 = COPY %xzr
+    %x10 = COPY %xzr
+    %x11 = COPY %xzr
+    %x12 = COPY %xzr
+    %x13 = COPY %xzr
+    %x14 = COPY %xzr
+    %x15 = COPY %xzr
+    %x16 = COPY %xzr
+    %x17 = COPY %xzr
+    %x18 = COPY %xzr
+    %x19 = COPY %xzr
+    %x20 = COPY %xzr
+    %x21 = COPY %xzr
+    %x22 = COPY %xzr
+    %x23 = COPY %xzr
+    %x24 = COPY %xzr
+    %x25 = COPY %xzr
+    %x26 = COPY %xzr
+    %x27 = COPY %xzr
+    %x28 = COPY %xzr
+    %fp = COPY %xzr
+    %lr = COPY %xzr
+    ST1Fourv1d killed %d16_d17_d18_d19, %stack.0 :: (store 32 into %stack.0, align 8)
+# CHECK:  STRXui killed %[[SCAVREG:x[0-9]+|fp|lr]], %sp, [[SPOFFSET:[0-9]+]] :: (store 8 into %stack.1)
+# CHECK-NEXT:  %[[SCAVREG]] = ADDXri %sp, {{[0-9]+}}, 0
+# CHECK-NEXT:  ST1Fourv1d killed %d16_d17_d18_d19, killed %[[SCAVREG]] :: (store 32 into %stack.0, align 8)
+# CHECK-NEXT:  %[[SCAVREG]] = LDRXui %sp, [[SPOFFSET]] :: (load 8 from %stack.1)
+...