Constant propagation in recursive functions

#1

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.

0 Likes