Regression in julia v1.12 in optimisation of recursive function

[giordano]

While looking into JuliaArrays/FixedSizeArrays.jl#142 I realised that in julia v1.12 there's a regression in optimisation of some recursive functions

julia> @noinline function mapreduce_impl(f, op, A::DenseArray,
                                         ifirst::Integer, ilast::Integer, blksize::Int)
           if ifirst == ilast ||  ilast - ifirst < blksize
               return zero(eltype(A))
           else
               imid = ifirst + (ilast - ifirst) >> 1
               v1 = mapreduce_impl(f, op, A, ifirst, imid, blksize)
               v2 = mapreduce_impl(f, op, A, imid+1, ilast, blksize)
               return op(v1, v2)
           end
       end
mapreduce_impl (generic function with 1 method)

julia> code_llvm(mapreduce_impl, (typeof(identity), typeof(+), Vector{Float64}, Int, Int, Int); )

; Function Signature: mapreduce_impl(typeof(Base.identity), typeof(Base.:(+)), Array{Float64, 1}, Int64, Int64, Int64)
;  @ REPL[6]:1 within `mapreduce_impl`
; Function Attrs: noinline
define double @julia_mapreduce_impl_2304(ptr noundef nonnull align 8 dereferenceable(24) %"A::Array", i64 signext %"ifirst::Int64", i64 signext %"ilast::Int64", i64 signext %"blksize::Int64") local_unnamed_addr #0 {
top:
;  @ REPL[6]:3 within `mapreduce_impl`
; ┌ @ promotion.jl:637 within `==`
   %.not = icmp eq i64 %"ifirst::Int64", %"ilast::Int64"
; └
  br i1 %.not, label %common.ret, label %L4

L4:                                               ; preds = %top
; ┌ @ int.jl:86 within `-`
   %0 = sub i64 %"ilast::Int64", %"ifirst::Int64"
; └
; ┌ @ int.jl:83 within `<`
   %.not2 = icmp slt i64 %0, %"blksize::Int64"
; └
  br i1 %.not2, label %common.ret, label %L8

common.ret:                                       ; preds = %L8, %L4, %top
;  @ REPL[6] within `mapreduce_impl`
  ret double 0.000000e+00

L8:                                               ; preds = %L4
;  @ REPL[6]:6 within `mapreduce_impl`
; ┌ @ int.jl:542 within `>>` @ int.jl:535
   %1 = ashr i64 %0, 1
; └
; ┌ @ int.jl:87 within `+`
   %2 = add i64 %1, %"ifirst::Int64"
; └
;  @ REPL[6]:7 within `mapreduce_impl`
  %3 = call double @j_mapreduce_impl_2307(ptr nonnull @"jl_global#2308.jit", ptr nonnull %"A::Array", i64 signext %"ifirst::Int64", i64 signext %2, i64 signext %"blksize::Int64")
;  @ REPL[6]:8 within `mapreduce_impl`
; ┌ @ int.jl:87 within `+`
   %4 = add i64 %2, 1
; └
  %5 = call double @j_mapreduce_impl_2307(ptr nonnull @"jl_global#2308.jit", ptr nonnull %"A::Array", i64 signext %4, i64 signext %"ilast::Int64", i64 signext %"blksize::Int64")
;  @ REPL[6]:9 within `mapreduce_impl`
  br label %common.ret
}

In Julia v1.11.5 the function is just reduced to 0:

julia> code_llvm(mapreduce_impl, (typeof(identity), typeof(+), Vector{Float64}, Int, Int, Int); )

; Function Signature: mapreduce_impl(typeof(Base.identity), typeof(Base.:(+)), Array{Float64, 1}, Int64, Int64, Int64)
;  @ REPL[1]:1 within `mapreduce_impl`
; Function Attrs: noinline
define double @julia_mapreduce_impl_437(ptr noundef nonnull align 8 dereferenceable(24) %"A::Array", i64 signext %"ifirst::Int64", i64 signext %"ilast::Int64", i64 signext %"blksize::Int64") #0 {
top:
;  @ REPL[1] within `mapreduce_impl`
  ret double 0.000000e+00
}

[adienes]

I bisected the regression to

#51092

[giordano]

@adienes while that PR sounds very relevant (it's about recursive functions), I don't understand it: that's in v1.11.0-alpha1 already. How does it explain the fact in v1.11.5 the optimisation is working correctly? Also, how did you run bisection? By definition of bisection I wouldn't expect the offending commit to be outside of the range between the two "good" and "bad" revisions, that's way before both of them.

Edit: I now see that on 1.11.0-alpha1 the IR was already bad, like in v1.12.0-beta4, which would explain how #51092 is relevant, but this also suggests the regression was fixed at some point between v1.11.0-alpha1 and v1.11.5? Edit 2: yes, it looks like the regression was resolved in the v1.11 series between v1.11.0-beta2 and v1.11.0-rc1.

[adienes]

seems as case is cracked 🙂

but for posterity, I've been bisecting based on the history of VERSION file https://github.com/JuliaLang/julia/commits/master/VERSION

in this case, I started with 8a4ab11 which actually I suppose is wider than I might have needed to? but I use git bisect with your original MWE and just keep going until it tells me the commit and I hope that it's right. I definitely saw both good and bad commits during this bisection so whatever was happening I think the range did contain the right one.