Constant propagation in recursive functions

While trying to build a simple example illustrating constant propagation, I made the following test (using the recursive variant of Euclid’s algorithm to compute a GCD):

julia> function gcd_rec(a, b)
           b == 0 && return a
           gcd_rec(b, a%b)
       end
gcd_rec (generic function with 1 method)

julia> f() = gcd_rec(6, 5)
f (generic function with 1 method)

julia> @code_llvm f()

;  @ REPL[13]:1 within `f'
define i64 @julia_f_12256() {
top:
; ┌ @ REPL[12]:3 within `gcd_rec' @ REPL[12]:3
   %0 = call i64 @julia_gcd_rec_12257(i64 1, i64 0)
; └
  ret i64 %0
}

We see here that one level of constant propagation occurred:

  • the b==0 test disappeared
  • b and b%a were replaced with their respective values.

But then gcd_rec is called recursively with these (constant) values and it does not seem that they are propagated.

It left me wondering: would it be possible to propagate constants deeper in the recursive call stack? It seems it is not a problem of depth here: constant propagation seems to happen all the way down to the bottom of the call stack for non-recursive call chains.

1 Like

In a certain sense we have that already?

function gcd_val_rec(::Type{Val{a}}, ::Type{Val{b}}) where {a,b}
    b == 0 && return a
    gcd_val_rec(Val(b), Val(a%b))
end

g() = gcd_val_rec(Val(6), Val(5))

@code_llvm g()

h() = gcd_val_rec(Val(6), Val(3))

@code_llvm h()

resolves to

; Function Attrs: uwtable
define i64 @julia_g_3554() #0 {
top:
  ret i64 1
}
; Function Attrs: uwtable
define i64 @julia_h_3556() #0 {
top:
  ret i64 3
}

Thanks!

This is a fairly old question and I’m not sure anymore what I had in mind at that time. You’re right that when it comes to the type domain, type inference is able to go very deep in the stack trace. Actually, constant propagation happens in very deeply nested calls for “regular values” (i.e. not types) too. I guess that what surprises me in this example is that the recursion seems to stop the constant propagation from happening.

For example: when calculating gcd(377, 610), the recursion ends at depth 14.

If we have cycles of 10 mutually recursive functions, then constants propagate through the 10 first function calls, but suddenly stop when the first cycle completes:

 
julia> n = 10
10

julia> for i in 1:n
           @eval function $(Symbol("gcd_rec$i"))(a, b)
               b == 0 && return a
               $(Symbol("gcd_rec$(1+i%n)"))(b, a%b)  # gcd_recN recurses to gcd_rec1
           end
       end

julia> f() = gcd_rec1(377, 610)
f (generic function with 1 method)

julia> @assert f() == 1

julia> @code_llvm f()
;  @ REPL[3]:1 within `f'
define i64 @julia_f_192() {
top:
; ┌ @ REPL[2]:4 within `gcd_rec1'
; │┌ @ REPL[2]:4 within `gcd_rec2'
; ││┌ @ REPL[2]:4 within `gcd_rec3'
; │││┌ @ REPL[2]:4 within `gcd_rec4'
; ││││┌ @ REPL[2]:4 within `gcd_rec5'
; │││││┌ @ REPL[2]:4 within `gcd_rec6'
; ││││││┌ @ REPL[2]:4 within `gcd_rec7'
; │││││││┌ @ REPL[2]:4 within `gcd_rec8'
; ││││││││┌ @ REPL[2]:4 within `gcd_rec9'
; │││││││││┌ @ REPL[2]:4 within `gcd_rec10'
; ││││││││││┌ @ REPL[2]:4 within `gcd_rec1'
             %0 = call i64 @j_gcd_rec2_194(i64 signext 5, i64 signext 3)
; └└└└└└└└└└└
  ret i64 %0
}

But constants could propagate further down the stack of nested calls if there was no recursion:

julia> n = 20
20

julia> for i in 1:n
           @eval function $(Symbol("gcd_rec$i"))(a, b)
               b == 0 && return a
               $(Symbol("gcd_rec$(1+i%n)"))(b, a%b)
           end
       end

julia> f() = gcd_rec1(377, 610)
f (generic function with 1 method)

julia> @assert f() == 1

julia> @code_llvm f()
;  @ REPL[8]:1 within `f'
define i64 @julia_f_212() {
top:
  ret i64 1
}

So I guess my question is the following: could we not propagate constants further down the stack of nested calls, even if there is a cycle of (possibly mutually) recursive calls? Maybe it would not be interesting/efficient to do so, though…