Repository: rust
Issue: Rust does not optimize register save/restore for early exit (slower than nim)
Labels: A-LLVM,I-slow,C-enhancement,T-compiler,C-optimization

<!--
Thank you for filing a bug report! 🐛 Please provide a short summary of the bug,
along with any information you feel relevant to replicating the bug.
-->

Note: This is a synthetic benchmark, however I believe it has the potential to improve runtime performance across the board for function calls because the push/pop register optimization in case of "early exit" seems like a low-hanging fruit. See assembly analysis below.

I used the following code 

**Rust 1.44.1:**
compiler options: -C opt-level=3 -C lto=fat
```rust
pub fn fib(n: u64) -> u64 {
  if n <= 1 { return 1 }
  fib(n - 1) + fib(n - 2)
}

fn main() {
  println!("{}", fib(48));
}
```
TotalSeconds      : 12.3482073
TotalMilliseconds : 12348.2073 **5% slower**

**Nim 1.2.0:**
compiler options: cpp -d:release --passC:-fno-inline-small-functions
```nim
proc fib(n: uint64): uint64 =
    if n <= 1: return 1
    return fib(n - 1) + fib(n - 2)

echo fib(48)
```
TotalSeconds      : 11.7725467
TotalMilliseconds : 11772.5467

**I expected to see this happen:** Rust-generated assembly (see below) to only save and restore register if needed

Instead, this happened: Rust-generated assembly saves registers even in the "early exit" case, when `n <= 1`. Compared to nim's assembly, we see that the registers are not saved/restored for the early exit case. 

Note: Given with the exponential count of the "early exit" case, this makes the benchmark perform significantly slower. However, I suspect even in real life we will benefit from having an early exit optimization.

### Meta
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

`rustc --version --verbose`:
```
rustc 1.44.1 (c7087fe00 2020-06-17)
binary: rustc
commit-hash: c7087fe00d2ba919df1d813c040a5d47e43b0fe7
commit-date: 2020-06-17
host: x86_64-pc-windows-msvc
release: 1.44.1
LLVM version: 9.0
```

### Analysis: generated assembly and likely reason for slowdown
For the assembly analysis I use https://rust.godbolt.org/ with the above sample code and options.
Here's the relevant assembly and source:
**Rust:**

![image](https://user-images.githubusercontent.com/6869225/85957512-c8703b80-b942-11ea-85a4-464e208c65bf.png)


```asm
example::fib:
        push    r15
        push    r14
        push    rbx
        mov     r14d, 1    # function init

        cmp     rdi, 2      # if n <= 1
        jb      .LBB0_3     # return 1
        mov     rbx, rdi
        mov     r14d, 1
        mov     r15, qword ptr [rip + example::fib@GOTPCREL]
.LBB0_2:
        lea     rdi, [rbx - 1]
        call    r15
        add     rbx, -2
        add     r14, rax
        cmp     rbx, 1
        ja      .LBB0_2
.LBB0_3:
        mov     rax, r14
        pop     rbx
        pop     r14
        pop     r15
        ret
```

**Nim:**

![image](https://user-images.githubusercontent.com/6869225/85957543-171dd580-b943-11ea-9381-7f26cb0e4ee3.png)

```nim
proc fib(n: uint64): uint64 =
    if n <= 1: return 1
    return fib(n - 1) + fib(n - 2)

echo fib(48)
```

```asm
fib__Q9chlIZts06QqO9cyt9cUDmlg(unsigned long):
 cmp    rdi,0x1
 ja     20 <fib__Q9chlIZts06QqO9cyt9cUDmlg(unsigned long)+0x10>
 mov    eax,0x1
 ret    
 nop    DWORD PTR [rax+0x0]
 push   r12
 lea    r12,[rdi-0x3]
 push   rbp
 lea    rbp,[rdi-0x1]
 sub    rdi,0x2
 push   rbx
 and    rdi,0xfffffffffffffffe
 xor    ebx,ebx
 sub    r12,rdi
 mov    rdi,rbp
 sub    rbp,0x2
 call   45 <fib__Q9chlIZts06QqO9cyt9cUDmlg(unsigned long)+0x35>
 add    rbx,rax
 cmp    rbp,r12
 jne    39 <fib__Q9chlIZts06QqO9cyt9cUDmlg(unsigned long)+0x29>
 lea    rax,[rbx+0x1]
 pop    rbx
 pop    rbp
 pop    r12
 ret    
 nop    WORD PTR cs:[rax+rax*1+0x0]
```

### Analysis:
1. Rust will always save registers (push on function entry, pop on exit) even for cases that doesn't need it. In contrast, nim's generated code will not.
2. This may or may not end up being beneficial in real-life scenarios, I suspect the optimization may be important.