Skip to content

LLVM backend: redundant code for functions calling themselves

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.

Edited by jmoy
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information