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?