`@code_typed` output is different from the actual IR for recursive Fibonacci function

[xitology]

If I define a simple recursive Fibonacci function and apply @code_typed, I can see that Julia unrolled one level of recursion:

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

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

However in the actual IR, the recursion is not unrolled:

julia> c = first(first(methods(fib)).specializations).cache;

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

It was really unexpected that the output of @code_typed can differ from the actual inferred code. If it's unavoidable, it would be nice to have a warning in the documentation.

It was tested under the latest master and 1.5.0-rc1.0.

[Keno]

I'm not sure "the" actual IR of a function is really a well defined concept. For example, if you inline it into another function, you'll get the unrolling behavior again:

julia> bar() = fib(10)
julia> @code_llvm bar()

;  @ REPL[9]:1 within `bar'
define i64 @julia_bar_410() {
top:
; ┌ @ REPL[1]:1 within `fib' @ REPL[1]:1
   %0 = call i64 @j_fib_414(i64 8)
   %1 = call i64 @j_fib_415(i64 7)
   %2 = call i64 @j_fib_412(i64 7)
   %3 = call i64 @j_fib_413(i64 6)
; │┌ @ int.jl:87 within `+'
    %4 = add i64 %1, %0
    %5 = add i64 %4, %2
; │└
; │ @ REPL[1]:1 within `fib'
; │┌ @ int.jl:87 within `+'
    %6 = add i64 %5, %3
; └└
  ret i64 %6
}

[xitology]

Let me put it differently: I'd expect @code_typed fib(10) to produce the code that is executed by the statement invoke Main.fib(::Int64).

For the function bar() = fib(10), both @code_typed bar() and @code_llvm bar() inline one level of fib(). In this case, the output of @code_llvm is clearly an elaboration of the output of @code_typed.

However, the output of @code_llvm fib(10) does not agree with @code_typed fib(10):

julia> @code_llvm fib(10)

;  @ REPL[9]:1 within `fib'
define i64 @julia_fib_426(i64) {
top:
; ┌ @ int.jl:442 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:86 within `-'
   %2 = add i64 %0, -1
; └
  %3 = call i64 @julia_fib_426(i64 %2)
; ┌ @ int.jl:86 within `-'
   %4 = add i64 %0, -2
; └
  %5 = call i64 @julia_fib_426(i64 %4)
; ┌ @ int.jl:87 within `+'
   %6 = add i64 %5, %3
; └
  ret i64 %6
}

This violates the implied assumption that @code_typed and @code_llvm let you probe different stages of the same compilation pipeline.

There is a warning in the documentation that @code_typed may produce inaccurate results when the function is not fully specialized. However it never states that may produce unexpected results in any other case, or that the output of @code_typed and @code_llvm may disagree.