Confusion about optimizations in @code_typed

General Usage Performance
1

I’m trying to learn how to optimize Julia code, and at some point I discovered I don’t understand the behavior of @code_typed.

I defined a simple recursive Fibonacci function:

julia> fib(n) = n <= 1 ? n : fib(n-1) + fib(n-2)
fib (generic function with 1 method)

With @code_typed I can print its lowered form:

julia> @code_typed fib(10)
CodeInfo(
1 ─ %1  = Base.sle_int(n, 1)::Bool
└──       goto #3 if not %1
2 ─       return n
3 ─ %4  = Base.sub_int(n, 1)::Int64
│   %5  = Base.sle_int(%4, 1)::Bool
└──       goto #5 if not %5
4 ─       goto #6
5 ─ %8  = Base.sub_int(%4, 1)::Int64
│   %9  = invoke Main.fib(%8::Int64)::Int64
│   %10 = Base.sub_int(%4, 2)::Int64
│   %11 = invoke Main.fib(%10::Int64)::Int64
│   %12 = Base.add_int(%9, %11)::Int64
└──       goto #6
6 ┄ %14 = φ (#4 => %4, #5 => %12)::Int64
│   %15 = Base.sub_int(n, 2)::Int64
│   %16 = Base.sle_int(%15, 1)::Bool
└──       goto #8 if not %16
7 ─       goto #9
8 ─ %19 = Base.sub_int(%15, 1)::Int64
│   %20 = invoke Main.fib(%19::Int64)::Int64
│   %21 = Base.sub_int(%15, 2)::Int64
│   %22 = invoke Main.fib(%21::Int64)::Int64
│   %23 = Base.add_int(%20, %22)::Int64
└──       goto #9
9 ┄ %25 = φ (#7 => %15, #8 => %23)::Int64
│   %26 = Base.add_int(%14, %25)::Int64
└──       return %26
) => Int64

Here, I could see that Julia unrolled one level of recursion. When I applied @code_llvm, I totally expected it to preserve the unrolling, but that’s not what I got:

julia> @code_llvm fib(10)
;  @ REPL[1]:1 within `fib'
define i64 @julia_fib_285(i64) {
top:
; ┌ @ int.jl:441 within `<='
   %1 = icmp sgt i64 %0, 1
; └
  br i1 %1, label %L4, label %L3

L3:                                               ; preds = %top
  ret i64 %0

L4:                                               ; preds = %top
; ┌ @ int.jl:85 within `-'
   %2 = add i64 %0, -1
; └
  %3 = call i64 @julia_fib_285(i64 %2)
; ┌ @ int.jl:85 within `-'
   %4 = add i64 %0, -2
; └
  %5 = call i64 @julia_fib_285(i64 %4)
; ┌ @ int.jl:86 within `+'
   %6 = add i64 %5, %3
; └
  ret i64 %6
}

At this point, I got confused. I expected @code_typed to give me the code as seen by IR-to-LLVM translator, but apparently this is not the case?

In fact, I was able to extract the real code from a CodeInstance object:

julia> c = first(first(methods(fib)).specializations).cache;
julia> Base._uncompressed_ir(c, c.inferred)
CodeInfo(
    @ REPL[1]:1 within `fib'
   ┌ @ int.jl:441 within `<='
1 ─│ %1 = Base.sle_int(n, 1)::Bool
│  └
└──      goto #3 if not %1
2 ─      return n
   ┌ @ int.jl:85 within `-'
3 ─│ %4 = Base.sub_int(n, 1)::Int64
│  └
│   %5 = invoke Main.fib(%4::Int64)::Int64
│  ┌ @ int.jl:85 within `-'
│  │ %6 = Base.sub_int(n, 2)::Int64
│  └
│   %7 = invoke Main.fib(%6::Int64)::Int64
│  ┌ @ int.jl:86 within `+'
│  │ %8 = Base.add_int(%5, %7)::Int64
│  └
└──      return %8
)

However I don’t understand why @code_typed should give me different output. Is it possibly a bug?

Edit: I was able to make LLVM unroll the recursion with:

julia> fib2(n) = n <= 1 ? n : fib(n-1) + fib(n-2)
julia> @code_llvm fib2(10)

It seems to me that @code_typed treats the function body as top-level code and ignores the fact that the function is recursive?