[GHC] #9387: LLVM backend: redundant code for functions calling themselves

[GHC]

#9387: LLVM backend: redundant code for functions calling themselves
-------------------------------------+-------------------------------------
              Reporter:  jmoy        |            Owner:
                  Type:  feature     |           Status:  new
  request                            |        Milestone:
              Priority:  normal      |          Version:  7.6.3
             Component:  Compiler    |         Keywords:
  (LLVM)                             |     Architecture:  x86_64 (amd64)
            Resolution:              |       Difficulty:  Unknown
      Operating System:  Linux       |       Blocked By:
       Type of failure:              |  Related Tickets:
  None/Unknown                       |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
Description changed by jmoy:

Old description:

> It seems that the LLVM backed does not recognize when a function calls
> itself. As a result it generates redundant load and store instructions.
>
> I am compiling the following simple recursive Fibonacci function
>
> {{{
> fib::Int->Int
> fib n
>   = loop n 0 1
>   where
>     loop !n !a !b
>       = if n==1 then
>           a
>         else
>           loop (n-1) b (a+b)
> }}}
>
> I am attaching the files produced by
>
> {{{
> ghc -c -O3 -fllvm -ddump-stg -ddump-cmm -ddump-llvm -ddump-to-file Fib.hs
> }}}
>
> I rename the generated LLVM file with a `.ll` extension and run `llc -O3`
> on it to generate the attached `.s` file (LLVM version 3.4.2).
>
> The actual work gets done in `Fib_zdwloop_info`. It begins as:
>
> {{{
> Fib_zdwloop_info:                       # @Fib_zdwloop_info
> # BB#0:                                 # %css
>         pushq   %rax
>         movq    %r13, (%rsp)
>         movq    %rbp, -8(%rsp)
>         movq    %r12, -16(%rsp)
>         movq    %rbx, -24(%rsp)
>         movq    %r14, -32(%rsp)
>         movq    %rsi, -40(%rsp)
>         movq    %rdi, -48(%rsp)
>         movq    %r8, -56(%rsp)
>         movq    %r9, -64(%rsp)
>         movq    %r15, -72(%rsp)
>         movss   %xmm1, -76(%rsp)
>         movss   %xmm2, -80(%rsp)
>         movss   %xmm3, -84(%rsp)
>         movss   %xmm4, -88(%rsp)
>         movsd   %xmm5, -96(%rsp)
>         movsd   %xmm6, -104(%rsp)
> }}}
>
> Later on when the function makes a recursive call to itself the code
> generated is
>
> {{{
>         movq    -8(%rsp), %rbp
>         movq    -16(%rsp), %r12
>         movq    -24(%rsp), %rbx
>         movq    -32(%rsp), %r14
>         movq    -40(%rsp), %rsi
>         movq    -72(%rsp), %r15
>         popq    %rax
>         jmp     Fib_zdwloop_info        # TAILCALL
> }}}
>
> Given that the values are being loaded from the stack to the registers in
> the second excerpt, it is redundant to re-store the same values into the
> stack at the entry of the function.
>
> It seems to me that this is happening because LLVM uses a general
> function call instruction to translate a function calling itself. I was
> wondering if it is possible to recognize this special case in the LLVM
> backed or earlier so that instead of a function call we can translate
> this as the LLVM level as a jump to some point after the function entry.

New description:

 It seems that the LLVM backed does not recognize when a function calls
 itself. As a result it generates redundant load and store instructions.

 I am compiling the following simple recursive Fibonacci function

 {{{
 fib::Int->Int
 fib n
   = loop n 0 1
   where
     loop !n !a !b
       = if n==1 then
           a
         else
           loop (n-1) b (a+b)
 }}}

 I am attaching the files produced by

 {{{
 ghc -c -O3 -fllvm -ddump-stg -ddump-cmm -ddump-llvm -ddump-to-file Fib.hs
 }}}

 I rename the generated LLVM file with a `.ll` extension and run `llc -O3`
 on it to generate the attached `.s` file (LLVM version 3.4.2).

 The actual work gets done in `Fib_zdwloop_info`. It begins as:

 {{{
 Fib_zdwloop_info:                       # @Fib_zdwloop_info
 # BB#0:                                 # %css
         pushq   %rax
         movq    %r13, (%rsp)
         movq    %rbp, -8(%rsp)
         movq    %r12, -16(%rsp)
         movq    %rbx, -24(%rsp)
         movq    %r14, -32(%rsp)
         movq    %rsi, -40(%rsp)
         movq    %rdi, -48(%rsp)
         movq    %r8, -56(%rsp)
         movq    %r9, -64(%rsp)
         movq    %r15, -72(%rsp)
         movss   %xmm1, -76(%rsp)
         movss   %xmm2, -80(%rsp)
         movss   %xmm3, -84(%rsp)
         movss   %xmm4, -88(%rsp)
         movsd   %xmm5, -96(%rsp)
         movsd   %xmm6, -104(%rsp)
 }}}

 Later on when the function makes a recursive call to itself the code
 generated is

 {{{
         movq    -8(%rsp), %rbp
         movq    -16(%rsp), %r12
         movq    -24(%rsp), %rbx
         movq    -32(%rsp), %r14
         movq    -40(%rsp), %rsi
         movq    -72(%rsp), %r15
         popq    %rax
         jmp     Fib_zdwloop_info        # TAILCALL
 }}}

 Given that the values are being loaded from the stack to the registers in
 the second excerpt, it is redundant to re-store the same values into the
 stack at the entry of the function.

 It seems to me that this is happening because LLVM uses a general function
 call instruction to translate a function calling itself. I was wondering
 if it is possible to recognize this special case in the LLVM backed or
 earlier so that instead of a function call we can translate this at the
 LLVM level as a jump to some point after the function entry.

--

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9387#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler