Do not spill CSR to stack on entry to noreturn functions

[myeisha]

Summary

A noreturn nounwind function can be expected to never return in any way, and by never returning it will also never have to restore any callee-saved registers for its caller. This makes it possible to skip spills of those registers during function entry, saving some stack space and time in the process. This is rather useful for embedded targets with limited stack space.

Initially reported as PR#9970.

[thegameg]

Thanks for working on this!

lib/CodeGen/TargetFrameLoweringImpl.cpp

90

You probably have to check for nounwind as well (check out @MatzeB's comment here: https://reviews.llvm.org/D42509#988553).

[myeisha]

Restricated CSR save skip to noreturn nounwind functions from previously noreturn. Exception handlers might need CSRs restored.

[thegameg]

One last comment and it should be good. Thanks!

Also, next time don't forget to add reviewers to your patch (I don't know if it was intended or not).

test/CodeGen/ARM/noreturn-csr-skip.ll

18

You could write MIR tests instead of using inline asm. This would allow you to test one specific pass at a time, here the PrologueEpilogueInserter.

Here's how it would look like for the function ret:

# RUN: llc -mtriple thumbv7m-none-eabi -run-pass prologepilog %s -o - | FileCheck %s

--- |
  define void @ret() nounwind { ret void }
...
---
# This function may return. Check that $r4 is saved and restored.
# CHECK-LABEL: name: ret
# CHECK: killed $r4
# CHECK: def $r4
name: ret
body: |
  bb.0:
    $r4 = IMPLICIT_DEF
    tBX_RET 14, $noreg
---

For more info on MIR: http://llvm.org/docs/MIRLangRef.html.

[myeisha]

In D42898#998313, @thegameg wrote:

One last comment and it should be good. Thanks!

Nice :)

Also, next time don't forget to add reviewers to your patch (I don't know if it was intended or not).

That was actually intentional. I had not found the code owner for that part of codegen and the blame list seemed unhelpful (looked like mostly NFC or code motion).

[efriedma]

It looks like this transform destroys stack traces on non-x86 platforms. That technically isn't wrong, I guess, but it seems unfriendly (for example, LLVM produces a stack trace on an assertion failure).

[myeisha]

In D42898#998355, @efriedma wrote:

It looks like this transform destroys stack traces on non-x86 platforms. That technically isn't wrong, I guess, but it seems unfriendly (for example, LLVM produces a stack trace on an assertion failure).

I don't quite follow. If I force the frame pointer on (eg by storing into a frame pointer returned by llvm.frameaddress) I see that the old frame pointer is stacked even for noreturn nounwind functions. I'd hate to break stack traces, am I missing something?

[thegameg]

In D42898#998355, @efriedma wrote:

It looks like this transform destroys stack traces on non-x86 platforms. That technically isn't wrong, I guess, but it seems unfriendly (for example, LLVM produces a stack trace on an assertion failure).

I might be wrong but I think at least the ARM and AArch64 backend would still save FP+LR. After calling TargetFrameLowering::determineCalleeSaves, FP and LR are usually added to the list of registers to be saved by the target in the target-specific determineCalleeSaves. From what I can see after a quick glance all the backends (except ARC and Sparc? not sure) special-case FP and LR (or whatever equivalent).

I do agree that if this breaks stack traces it should be under some flag or something.

[myeisha]

In D42898#998371, @thegameg wrote:

I do agree that if this breaks stack traces it should be under some flag or something.

We could also tie it into frame pointer elimination and skip CSR saves only when fp elimination is active, maybe add a per-target option to skip anyway if the target has special handling for fp/lr.

[kparzysz]

This isn't correct in general, only in cases when the non-returning functions terminate the program.

[myeisha]

Can you elaborate on that? I'm primarily interested in programs that do not terminate at all, with nested nonreturning functions. How would not saving CSRs in the outer nonreturning function prolog affect the inner nonreturning function? The only affected thing that comes to my mind right now is a debugger.

[kparzysz]

I was thinking of the case when the non-returning function simply does not return to the caller, but terminates its own execution by going elsewhere (something like continuation-passing). If the function has an infinite loop or something like that, and is not intended to ever leave its own context, then not saving CSR shouldn't make a difference.

[myeisha]

If I understand the IR correctly then this would either involve some nasty inline assembly or some form of tail call. If the target were not itself nonreturning, then the caller could also not be, so the transform would not apply.

I guess this is just way over my head.

[kparzysz]

It could be a call to some library function (from a user-provided library). I agree that this is a very unlikely scenario, but we've had a customer report a bug related to a similar situation.

If you want to proceed with this, could you make it opt-in for targets that want it?

[myeisha]

I would rather make it generic, not break debug, and habe the user decide whether or not to apply this. If libraries are the concern it probably can't be the target's decision either. Would enabling the transform only with fp-elim and a cl option be just as good?

[kparzysz]

You can make it generic, but turned off by default, or dependent on a target hook.

[myeisha]

Added a target hook to enable CSR spill skipping, default off and enabled currently only for ARM because that's what I know best.

[thegameg]

In D42898#999350, @kparzysz wrote:

It could be a call to some library function (from a user-provided library). I agree that this is a very unlikely scenario, but we've had a customer report a bug related to a similar situation.

Just out of curiosity, can you please share some more information about that?

From what I understand,

A (nounwind) calls B (nounwind, noreturn)
B (nounwind, noreturn) calls library function C (nounwind?)
C (nounwind?) returns to A (nounwind) ?

In that case, B not saving the CSRs will destroy A's CSRs, but I can't really understand how we can end up in this case.

My assumptions are:

• can't (tail-)call throwing functions from nounwind functions
• can't (tail-)call returning functions from noreturn functions

but I might be wrong on that.

[kparzysz]

By library function I simply meant a function that is provided by the user, which the compiler doesn't see the definition of. The problem I remember seeing was that he didn't restore a callee-saved register, but I don't remember exactly where this was in relation to a noreturn function. The code that we were compiling was written in C, not C++. I suspect there was something similar to longjmp (but probably not a longjmp itself) somewhere in the user code that aborted some processing routines and "returned" to a top-level function. It's just a guess though (I couldn't find that bug with a quick search).

My main concern here is that this should not be a default behavior for all targets. As long as we have an option to opt out of this, I don't have objections, especially because a problematic case is not very common. The added callback should take care of it.

[thegameg]

I might be missing a few details of what this change might affect.

[efriedma]

Unfortunately there's still a hole in the safety analysis. Specifically, "nounwind" does not mean what you want it to mean. Consider the following testcase:

#include <setjmp.h>
void foo(void* x, int y) { longjmp(x,y); }

This compiles to a "noreturn nounwind" function, but we can't throw away callee-save register values. Granted, we probably *should* have some attribute which indicates we won't longjmp() out of a function, but that doesn't exist at the moment.

[myeisha]

I did think about that, but came to the conclusion that longjmp would have to restore all callee-saves to the state they had at setjmp, and that setjmp would have to store them into the jmp_buf. If longjmp uses CSR spills the transform is indeed unsound, but I'm not sure how it would access those without being an llvm builtin. I've checked with what musl does on ARM (because that's what I'm familiar with) to confirm that idea, so at least on ARM the transform should be safe?

[efriedma]

I did think about that, but came to the conclusion that longjmp would have to restore all callee-saves to the state they had at setjmp, and that setjmp would have to store them into the jmp_buf.

Huh. I guess that works? But you probably want to explicitly note that in a comment in the code.

[myeisha]

Added a comment about setjmp/longjmp and CSR spills.

[myeisha]

Gentle ping.

[myeisha]

Ping.

[myeisha]

Ping.

[myeisha]

Ping.

[lebedev.ri]

Hopefully added some more reviewers (as per git shortlog -sne), that might be interested/qualified in this.

[myeisha]

Another week, another ping.

[echristo]

Other than an inline comment (of no consequence) this looks like it's probably ok here. The naming of the function isn't great (welcome to fabulous bikesheds in programming), but I don't have a better idea off the top of my head so let's go with that.

Since Eli had already started a review let's give him a bit of time (Or Matthias) after this email to take a last look, otherwise I'll approve next week.

Thanks!

-eric

lib/Target/ARM/ARMFrameLowering.cpp

95 ↗

(On Diff #133479)

I'd probably like to see an assert here (and in the general case) that we've got a noreturn and nounwind function.

[myeisha]

added assertions for noreturn nounwind to the generic and ARM csr spill skip predicates.

[efriedma]

LGTM

[myeisha]

awesome, thank you :) i do not have commit access, so i won't be able to merge it myself.

[myeisha]

Ping--do I still have to do something to get this committed?

[t.p.northover]

Sorry about the delay, I've committed this for you as r329287.

[vitalybuka]

I had to revert it in r329486
It breaks UBSAN test http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-android/builds/9418/steps/run%20lit%20tests%20%5Barm%2Faosp_marlin-userdebug%2FOPR4.170623.016%5D/logs/stdio
Looks like UBSAN crashes unrolling the stack for such functions.

[t.p.northover]

I managed to track down the issue, and I think the patch needs to respect the "uwtable" attribute too (otherwise the tables produced are useless). So I've recommitted with that change applied; hopefully it'll stick this time.

lib/CodeGen/TargetFrameLoweringImpl.cpp

void TargetFrameLowering::determineCalleeSaves(MachineFunction &MF,
   // Early exit if there are no callee saved registers.
   if (!CSRegs || CSRegs[0] == 0)
     return;
 
   // In Naked functions we aren't going to save any registers.
   if (MF.getFunction().hasFnAttribute(Attribute::Naked))
     return;
 
+  // Noreturn+nounwind functions never restore CSR, so no saves are needed.
+  // Purely noreturn functions may still return through throws, so those must
+  // save CSR for caller exception handlers.
+  if (MF.getFunction().hasFnAttribute(Attribute::NoReturn) &&
+        MF.getFunction().hasFnAttribute(Attribute::NoUnwind))
+    return;
+
   // Functions which call __builtin_unwind_init get all their registers saved.
   bool CallsUnwindInit = MF.callsUnwindInit();
   const MachineRegisterInfo &MRI = MF.getRegInfo();
   for (unsigned i = 0; CSRegs[i]; ++i) {
     unsigned Reg = CSRegs[i];
     if (CallsUnwindInit || MRI.isPhysRegModified(Reg))
       SavedRegs.set(Reg);
   }

test/CodeGen/AArch64/arm64-shrink-wrapping.ll

 ; CHECK: ldp [[CSR3]], [[CSR4]], [sp, #16]
 ; CHECK-NEXT: ldp [[CSR1]], [[CSR2]], [sp], #32
 ; CHECK-NEXT: ret
 ;
 ; ENABLE: [[ELSE_LABEL]]: ; %if.else
 ; Shift second argument by one and store into returned register.
 ; ENABLE: lsl w0, w1, #1
 ; ENABLE: ret
-define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) #0 {
+define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) nounwind {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void bitcast (void (...)* @somethingElse to void ()*)()
   br label %for.body
 

 ; Epilogue code.
 ; CHECK: add sp, sp, #16
 ; CHECK-NEXT: ret
 ;
 ; CHECK: [[ELSE_LABEL]]: ; %if.else
 ; CHECK-NEXT: lsl w0, w1, #1
 ; DISABLE-NEXT: add sp, sp, #16
 ; CHECK-NEXT: ret
-define i32 @variadicFunc(i32 %cond, i32 %count, ...) #0 {
+define i32 @variadicFunc(i32 %cond, i32 %count, ...) nounwind {
 entry:
   %ap = alloca i8*, align 8
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   %ap1 = bitcast i8** %ap to i8*
   call void @llvm.va_start(i8* %ap1)

test/CodeGen/ARM/arm-shrink-wrapping.ll

 ; DISABLE: pop {r4, r7, pc}
 ;
 ; CHECK: [[ELSE_LABEL]]: @ %if.else
 ; Shift second argument by one and store into returned register.
 ; CHECK: lsl{{s?}} r0, r1, #1
 ; DISABLE-NEXT: pop {r4, r7, pc}
 ;
 ; ENABLE-NEXT: bx lr
-define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) "no-frame-pointer-elim"="true" #0 {
+define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) "no-frame-pointer-elim"="true" nounwind {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void asm "nop", "~{r4}"()
   br label %for.body
 

test/CodeGen/ARM/noreturn-csr-skip.ll

+; RUN: llc %s -o -  | FileCheck %s --check-prefix=CHECK
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv7m-none-eabi"
+
+; CHECK-LABEL: ret
+;
+; This function may return. Any CSR must be saved.
+; CHECK: push {r4, lr}
+; CHECK-NEXT: sub sp, #4
+; CHECK: add sp, #4
+; CHECK-NEXT: pop {r4, pc}
+define internal void @ret() nounwind {
+start:
+  %p = alloca i32
+  call void asm sideeffect "", "~{r4}"()
+  ret void
+}
+
+; CHECK-LABEL: throw
+;
+; This function may return through throws. Any CSR must be saved.
+; CHECK: push {r4, lr}
+; CHECK-NEXT: sub sp, #4
+; CHECK: add sp, #4
+; CHECK-NEXT: pop {r4, pc}
+define internal void @throw() noreturn {
+start:
+  %p = alloca i32
+  call void asm sideeffect "", "~{r4}"()
+  ret void
+}
+
+; CHECK-LABEL: noret
+;
+; This function does not return. We need not save any CSR, but
+; other stack adjustments in the prologue are still necessary.
+; CHECK-NOT: push
+; CHECK: sub sp, #4
+define internal void @noret() noreturn nounwind {
+start:
+  %p = alloca i32
+  br label %bb1
+
+bb1:
+  call void asm sideeffect "", "~{r4}"()
+  br label %bb1
+}

test/CodeGen/PowerPC/ppc-shrink-wrapping.ll

 ; Epilogue code.
 ; CHECK: mtlr {{[0-9]+}}
 ; CHECK-NEXT: blr
 ;
 ; ENABLE: .[[ELSE_LABEL]]: # %if.else
 ; Shift second argument by one and store into returned register.
 ; ENABLE: slwi 3, 4, 1
 ; ENABLE-NEXT: blr
-define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) #0 {
+define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) nounwind {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void bitcast (void (...)* @somethingElse to void ()*)()
   br label %for.body
 

test/CodeGen/Thumb/thumb-shrink-wrapping.ll

 ; DISABLE-V5T-NEXT: pop {r4, pc}
 ; DISABLE-V4T-NEXT: [[END_LABEL]]: @ %if.end
 ; DISABLE-V4T-NEXT: pop {r4}
 ; DISABLE-V4T-NEXT: pop {r1}
 ; DISABLE-V4T-NEXT: bx r1
 ;
 ; ENABLE-V5T-NEXT: {{LBB[0-9_]+}}: @ %if.end
 ; ENABLE-NEXT: bx lr
-define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) #0 {
+define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) nounwind {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void asm "nop", "~{r4}"()
   br label %for.body
 

test/CodeGen/X86/2010-02-19-TailCallRetAddrBug.ll

 ; CHECK: movl 76(%esp), [[REGISTER:%[a-z]+]]
 ; Overwrite return addresss
 ; CHECK: movl [[EBX:%[a-z]+]], 76(%esp)
 ; Move return address from temporary register (%ebp) to new stack location (60(%esp))
 ; CHECK: movl [[REGISTER]], 60(%esp)
 
 %tupl = type [9 x i32]
 
-declare fastcc void @l297(i32 %r10, i32 %r9, i32 %r8, i32 %r7, i32 %r6, i32 %r5, i32 %r3, i32 %r2) noreturn nounwind
-declare fastcc void @l298(i32 %r10, i32 %r9, i32 %r4) noreturn nounwind
+declare fastcc void @l297(i32 %r10, i32 %r9, i32 %r8, i32 %r7, i32 %r6, i32 %r5, i32 %r3, i32 %r2) nounwind
+declare fastcc void @l298(i32 %r10, i32 %r9, i32 %r4) nounwind
 
-define fastcc void @l186(%tupl* %r1) noreturn nounwind {
+define fastcc void @l186(%tupl* %r1) nounwind {
 entry:
   %ptr1 = getelementptr %tupl, %tupl* %r1, i32 0, i32 0
   %r2 = load i32, i32* %ptr1
   %ptr3 = getelementptr %tupl, %tupl* %r1, i32 0, i32 1
   %r3 = load i32, i32* %ptr3
   %ptr5 = getelementptr %tupl, %tupl* %r1, i32 0, i32 2
   %r4 = load i32, i32* %ptr5
   %ptr7 = getelementptr %tupl, %tupl* %r1, i32 0, i32 3
   %r5 = load i32, i32* %ptr7
   %ptr9 = getelementptr %tupl, %tupl* %r1, i32 0, i32 4
   %r6 = load i32, i32* %ptr9
   %ptr11 = getelementptr %tupl, %tupl* %r1, i32 0, i32 5
   %r7 = load i32, i32* %ptr11
   %ptr13 = getelementptr %tupl, %tupl* %r1, i32 0, i32 6
   %r8 = load i32, i32* %ptr13
   %ptr15 = getelementptr %tupl, %tupl* %r1, i32 0, i32 7
   %r9 = load i32, i32* %ptr15
   %ptr17 = getelementptr %tupl, %tupl* %r1, i32 0, i32 8
   %r10 = load i32, i32* %ptr17
   %cond = icmp eq i32 %r10, 3
   br i1 %cond, label %true, label %false
 
 true:
-  tail call fastcc void @l297(i32 %r10, i32 %r9, i32 %r8, i32 %r7, i32 %r6, i32 %r5, i32 %r3, i32 %r2) noreturn nounwind
+  tail call fastcc void @l297(i32 %r10, i32 %r9, i32 %r8, i32 %r7, i32 %r6, i32 %r5, i32 %r3, i32 %r2) nounwind
   ret void
 
 false:
-  tail call fastcc void @l298(i32 %r10, i32 %r9, i32 %r4) noreturn nounwind
+  tail call fastcc void @l298(i32 %r10, i32 %r9, i32 %r4) nounwind
   ret void
 }

test/CodeGen/X86/x86-shrink-wrapping.ll

 ; CHECK-DAG: movl %esi, %eax
 ; CHECK: retq
 ;
 ; ENABLE: [[ELSE_LABEL]]: ## %if.else
 ; Shift second argument by one and store into returned register.
 ; ENABLE: addl %esi, %esi
 ; ENABLE-NEXT: movl %esi, %eax
 ; ENABLE-NEXT: retq
-define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) #0 {
+define i32 @loopInfoRestoreOutsideLoop(i32 %cond, i32 %N) nounwind {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   tail call void asm "nop", "~{ebx}"()
   br label %for.body