Repository: rust
Issue: Uses of GlobalAlloc::realloc yield useless code in lto+opt-level=2 builds
Labels: I-slow,A-allocators,T-compiler,C-bug,I-heavy

I noticed this in Firefox (where we do build with `-C lto -C opt-level=2`). Essentially any use of an API that ends up calling __rust_realloc generates useless code. A small testcase is:
```rust
#[no_mangle]
pub extern "C" fn qux(v: &mut Vec<usize>) {
    v.push(42);
}
```
which, with the following `Cargo.toml` config:
```
[profile.release]
lto = true
opt-level = 2
panic = "abort"
codegen-units = 1
rpath = false

[lib]
crate-type = ["cdylib"]
```

generates the following assembly:
```asm
0000000000003200 <qux>:
    3200:       55                      push   %rbp
    3201:       41 57                   push   %r15
    3203:       41 56                   push   %r14
    3205:       41 55                   push   %r13
    3207:       41 54                   push   %r12
    3209:       53                      push   %rbx
    320a:       50                      push   %rax
    320b:       49 89 fd                mov    %rdi,%r13
    320e:       48 8b 4f 10             mov    0x10(%rdi),%rcx
    3212:       48 3b 4f 08             cmp    0x8(%rdi),%rcx
    3216:       75 55                   jne    326d <qux+0x6d>
    3218:       49 89 ce                mov    %rcx,%r14
    321b:       49 83 c6 01             add    $0x1,%r14
    321f:       0f 82 e2 00 00 00       jb     3307 <qux+0x107>
    3225:       48 8d 04 09             lea    (%rcx,%rcx,1),%rax
    3229:       49 39 c6                cmp    %rax,%r14
    322c:       4c 0f 42 f0             cmovb  %rax,%r14
    3230:       ba 08 00 00 00          mov    $0x8,%edx
    3235:       45 31 ff                xor    %r15d,%r15d
    3238:       4c 89 f0                mov    %r14,%rax
    323b:       48 f7 e2                mul    %rdx
    323e:       49 89 c4                mov    %rax,%r12
    3241:       0f 91 c0                setno  %al
    3244:       0f 80 bd 00 00 00       jo     3307 <qux+0x107>
    324a:       41 88 c7                mov    %al,%r15b
    324d:       49 c1 e7 03             shl    $0x3,%r15
    3251:       48 85 c9                test   %rcx,%rcx
    3254:       74 1d                   je     3273 <qux+0x73>
    3256:       49 8b 6d 00             mov    0x0(%r13),%rbp
    325a:       4d 85 e4                test   %r12,%r12
    325d:       74 3f                   je     329e <qux+0x9e>
    325f:       48 89 ef                mov    %rbp,%rdi
    3262:       4c 89 e6                mov    %r12,%rsi
    3265:       ff 15 35 2d 02 00       callq  *0x22d35(%rip)        # 25fa0 <realloc@GLIBC_2.2.5>
    326b:       eb 6a                   jmp    32d7 <qux+0xd7>
    326d:       49 8b 5d 00             mov    0x0(%r13),%rbx
    3271:       eb 78                   jmp    32eb <qux+0xeb>
    3273:       4d 39 e7                cmp    %r12,%r15
    3276:       76 56                   jbe    32ce <qux+0xce>
    3278:       48 c7 04 24 00 00 00    movq   $0x0,(%rsp)
    327f:       00 
    3280:       48 89 e7                mov    %rsp,%rdi
    3283:       4c 89 fe                mov    %r15,%rsi
    3286:       4c 89 e2                mov    %r12,%rdx
    3289:       ff 15 39 2d 02 00       callq  *0x22d39(%rip)        # 25fc8 <posix_memalign@GLIBC_2.2.5>
    328f:       85 c0                   test   %eax,%eax
    3291:       75 7b                   jne    330e <qux+0x10e>
    3293:       48 8b 1c 24             mov    (%rsp),%rbx
    3297:       48 85 db                test   %rbx,%rbx
    329a:       75 43                   jne    32df <qux+0xdf>
    329c:       eb 70                   jmp    330e <qux+0x10e>
    329e:       48 c7 04 24 00 00 00    movq   $0x0,(%rsp)
    32a5:       00 
    32a6:       48 89 e7                mov    %rsp,%rdi
    32a9:       be 08 00 00 00          mov    $0x8,%esi
    32ae:       31 d2                   xor    %edx,%edx
    32b0:       ff 15 12 2d 02 00       callq  *0x22d12(%rip)        # 25fc8 <posix_memalign@GLIBC_2.2.5>
    32b6:       85 c0                   test   %eax,%eax
    32b8:       75 54                   jne    330e <qux+0x10e>
    32ba:       48 8b 1c 24             mov    (%rsp),%rbx
    32be:       48 85 db                test   %rbx,%rbx
    32c1:       74 4b                   je     330e <qux+0x10e>
    32c3:       48 89 ef                mov    %rbp,%rdi
    32c6:       ff 15 d4 2b 02 00       callq  *0x22bd4(%rip)        # 25ea0 <free@GLIBC_2.2.5>
    32cc:       eb 11                   jmp    32df <qux+0xdf>
    32ce:       4c 89 e7                mov    %r12,%rdi
    32d1:       ff 15 a9 2c 02 00       callq  *0x22ca9(%rip)        # 25f80 <malloc@GLIBC_2.2.5>
    32d7:       48 89 c3                mov    %rax,%rbx
    32da:       48 85 db                test   %rbx,%rbx
    32dd:       74 2f                   je     330e <qux+0x10e>
    32df:       49 89 5d 00             mov    %rbx,0x0(%r13)
    32e3:       4d 89 75 08             mov    %r14,0x8(%r13)
    32e7:       49 8b 4d 10             mov    0x10(%r13),%rcx
    32eb:       48 c7 04 cb 2a 00 00    movq   $0x2a,(%rbx,%rcx,8)
    32f2:       00 
    32f3:       49 83 45 10 01          addq   $0x1,0x10(%r13)
    32f8:       48 83 c4 08             add    $0x8,%rsp
    32fc:       5b                      pop    %rbx
    32fd:       41 5c                   pop    %r12
    32ff:       41 5d                   pop    %r13
    3301:       41 5e                   pop    %r14
    3303:       41 5f                   pop    %r15
    3305:       5d                      pop    %rbp
    3306:       c3                      retq   
    3307:       e8 84 9f 00 00          callq  d290 <_ZN5alloc7raw_vec17capacity_overflow17h0432b49d9a8429deE>
    330c:       0f 0b                   ud2    
    330e:       4c 89 e7                mov    %r12,%rdi
    3311:       4c 89 fe                mov    %r15,%rsi
    3314:       e8 87 9f 00 00          callq  d2a0 <_ZN5alloc5alloc18handle_alloc_error17h612a63a56f8c2099E>
    3319:       0f 0b                   ud2    
    331b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
```

That's a lot of code, and the most notable in here is that there's a call to `realloc`, two calls to `posix_memalign`, one to `free` and one to `malloc`.

Now, to understand what's going on, let's write our own copy of the `GlobalAlloc` implementation:
```rust
use std::alloc::{GlobalAlloc, Layout};
use std::cmp;
use std::ptr;
use libc;

#[no_mangle]
pub extern "C" fn qux(v: &mut Vec<usize>) {
    v.push(42);
}

struct System;

const MIN_ALIGN: usize = 16; 

unsafe impl GlobalAlloc for System {
    #[inline]
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
            libc::malloc(layout.size()) as *mut u8
        } else {
            #[cfg(target_os = "macos")]
            {
                if layout.align() > (1 << 31) {
                    return ptr::null_mut()
                }
            }
            aligned_malloc(&layout)
        }
    }   

    #[inline]
    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
            libc::calloc(layout.size(), 1) as *mut u8
        } else {
            let ptr = self.alloc(layout.clone());
            if !ptr.is_null() {
                ptr::write_bytes(ptr, 0, layout.size());
            }
            ptr
        }
    }   

    #[inline]
    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
        libc::free(ptr as *mut libc::c_void)
    }   

    #[inline]
    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
        if layout.align() <= MIN_ALIGN && layout.align() <= new_size {
            libc::realloc(ptr as *mut libc::c_void, new_size) as *mut u8
        } else {
            realloc_fallback(self, ptr, layout, new_size)
        }
    }   
}

unsafe fn aligned_malloc(layout: &Layout) -> *mut u8 {
    let mut out = ptr::null_mut();
    let ret = libc::posix_memalign(&mut out, layout.align(), layout.size());
    if ret != 0 { 
        ptr::null_mut()
    } else {
        out as *mut u8
    }   
}

unsafe fn realloc_fallback(
    alloc: &System,
    ptr: *mut u8, 
    old_layout: Layout,
    new_size: usize,
) -> *mut u8 {
    // Docs for GlobalAlloc::realloc require this to be valid:
    let new_layout = Layout::from_size_align_unchecked(new_size, old_layout.align());

    let new_ptr = GlobalAlloc::alloc(alloc, new_layout);
    if !new_ptr.is_null() {
        let size = cmp::min(old_layout.size(), new_size);
        ptr::copy_nonoverlapping(ptr, new_ptr, size);
        GlobalAlloc::dealloc(alloc, ptr, old_layout);
    }   
    new_ptr
}

#[global_allocator]
static HEAP: System = System;
```
(this compiles to the same assembly)

What's going on here is that `layout.align()` is, in our inlined case, a constant for the alignment of `usize`, which is 8 on x86_64, so `layout.align() <= MIN_ALIGN` is always true. However, because the `new_size` given to `realloc` is not `NonZero` (despite the GlobalAlloc documentation specifying the value can never be 0), LLVM doesn't know that the condition `layout.align() <= new_size` is also always true, so it ends up creating code for both `libc::realloc` and `realloc_fallback` branches.

Changing the condition in `realloc` to force `new_size == 0` to go through `libc::realloc` gets rid of the call to `free` and one call to `posix_memalign`. Sadly, doing the same with `layout.size() == 0` in `alloc` to call `libc::malloc` doesn't get right of the other `posix_memalign` call. I guess the compiler still thinks that the new size computed in `RawVec::reserve_internal` can be somewhere between `layout.align()` and `layout.size()`, which is actually not possible.

Assuming we can somehow get the compiler to get rid of that useless `posix_memalign`, that still leaves us with, essentially, code doing `new_ptr = if ptr { libc::realloc(ptr, new_size) } else { libc::malloc(new_size) }`, which, considering the API guarantees of `libc::realloc`, is a branch and a function call too much, since `new_ptr = libc::realloc(ptr, new_size)` would work just as well, `libc::realloc(ptr::null_mut(), new_size)` being the same as `libc::malloc(new_size)`. Sadly, there's nothing in the Alloc API that would allow to fold this.

Cc: @SimonSapin