When can a single-call optimization be used?

function func(x)
    sum(x) / sum(x)
end

xs = rand(0:.1:1, 1000)
@code_typed func(xs)
julia> @code_typed func(xs)
CodeInfo(
1 ── %1  = Base.identity::typeof(identity)
│    %2  = Base.add_sum::typeof(Base.add_sum)
│    %3  = Base.arraysize(x, 1)::Int64
│    %4  = Base.slt_int(%3, 0)::Bool
│    %5  = Base.ifelse(%4, 0, %3)::Int64
│    %6  = Base.sub_int(%5, 0)::Int64
│    %7  = (%6 === 0)::Bool
└───       goto #3 if not %7
2 ──       goto #11
3 ── %10 = (%6 === 1)::Bool
└───       goto #5 if not %10
4 ── %12 = Base.arrayref(false, x, 1)::Float64
└───       goto #11
5 ── %14 = Base.slt_int(%6, 16)::Bool
└───       goto #10 if not %14
6 ── %16 = Base.arrayref(false, x, 1)::Float64
│    %17 = Base.arrayref(false, x, 2)::Float64
└─── %18 = Base.add_float(%16, %17)::Float64
7 ┄─ %19 = φ (#6 => 2, #8 => %25)::Int64
│    %20 = φ (#6 => %18, #8 => %27)::Float64
│    %21 = Base.slt_int(%5, 0)::Bool
│    %22 = Base.ifelse(%21, 0, %5)::Int64
│    %23 = Base.slt_int(%19, %22)::Bool
└───       goto #9 if not %23
8 ── %25 = Base.add_int(%19, 1)::Int64
│    %26 = Base.arrayref(false, x, %25)::Float64
│    %27 = Base.add_float(%20, %26)::Float64
└───       goto #7
9 ──       goto #11
10 ─ %30 = Base.slt_int(%5, 0)::Bool
│    %31 = Base.ifelse(%30, 0, %5)::Int64
│    %32 = invoke Base.mapreduce_impl(%1::typeof(identity), %2::typeof(Base.add_sum), _2::Array{Float64,1}, 1::Int64, %31::Int64, 1024::Int64)::Float64
└───       goto #11
11 ┄ %34 = φ (#2 => 0.0, #4 => %12, #9 => %20, #10 => %32)::Float64
└───       goto #12
12 ─       goto #13
13 ─       goto #14
14 ─       goto #15
15 ─       goto #16
16 ─       goto #17
17 ─       goto #18
18 ─ %42 = Base.identity::typeof(identity)
│    %43 = Base.add_sum::typeof(Base.add_sum)
│    %44 = Base.arraysize(x, 1)::Int64
│    %45 = Base.slt_int(%44, 0)::Bool
│    %46 = Base.ifelse(%45, 0, %44)::Int64
│    %47 = Base.sub_int(%46, 0)::Int64
│    %48 = (%47 === 0)::Bool
└───       goto #20 if not %48
19 ─       goto #28
20 ─ %51 = (%47 === 1)::Bool
└───       goto #22 if not %51
21 ─ %53 = Base.arrayref(false, x, 1)::Float64
└───       goto #28
22 ─ %55 = Base.slt_int(%47, 16)::Bool
└───       goto #27 if not %55
23 ─ %57 = Base.arrayref(false, x, 1)::Float64
│    %58 = Base.arrayref(false, x, 2)::Float64
└─── %59 = Base.add_float(%57, %58)::Float64
24 ┄ %60 = φ (#23 => 2, #25 => %66)::Int64
│    %61 = φ (#23 => %59, #25 => %68)::Float64
│    %62 = Base.slt_int(%46, 0)::Bool
│    %63 = Base.ifelse(%62, 0, %46)::Int64
│    %64 = Base.slt_int(%60, %63)::Bool
└───       goto #26 if not %64
25 ─ %66 = Base.add_int(%60, 1)::Int64
│    %67 = Base.arrayref(false, x, %66)::Float64
│    %68 = Base.add_float(%61, %67)::Float64
└───       goto #24
26 ─       goto #28
27 ─ %71 = Base.slt_int(%46, 0)::Bool
│    %72 = Base.ifelse(%71, 0, %46)::Int64
│    %73 = invoke Base.mapreduce_impl(%42::typeof(identity), %43::typeof(Base.add_sum), _2::Array{Float64,1}, 1::Int64, %72::Int64, 1024::Int64)::Float64
└───       goto #28
28 ┄ %75 = φ (#19 => 0.0, #21 => %53, #26 => %61, #27 => %73)::Float64
└───       goto #29
29 ─       goto #30
30 ─       goto #31
31 ─       goto #32
32 ─       goto #33
33 ─       goto #34
34 ─       goto #35
35 ─ %83 = Base.div_float(%34, %75)::Float64
└───       return %83
) => Float64

As far as I can tell, Julia calls sum(x) twice. I can pull out the call into a variable, but, being naive about the compiler, I wondered whether it’s possible for Julia to conclude that it can call sum(x) only once. Maybe sometimes it doesn’t even need to call sum(x) at all.

In principle, the compiler could do this (common subexpression elimination) is the function was known to be “pure”, but (1) the sum function is not annotated as @pure (because this is technically only true for certain summand types) and (2) this compiler optimization of @pure functions is not implemented yet except for some special cases AFAIK.

See also constant-propagation for @pure functions · Issue #14324 · JuliaLang/julia · GitHub, Constant Folding openlibm functions · Issue #9942 · JuliaLang/julia · GitHub, constant-folding rational constants · Issue #32024 · JuliaLang/julia · GitHub, LICM for pure functions · Issue #29285 · JuliaLang/julia · GitHub

4 Likes

Note that you can do this, at the level of syntax not compilation:

julia> using CommonSubexpressions

julia> @macroexpand @cse function func(x)
           sum(x) / sum(x)
       end
quote
    function func(x)
        var"##605" = sum(x)
        var"##606" = var"##605" / var"##605"
        begin
            var"##606"
        end
    end
end

julia> @cse function func_2(x)
                  sum(x) / sum(x)
              end
func_2 (generic function with 1 method)

julia> @code_typed func_2(xs)
4 Likes

Whoa, CommonSubexpressions is smart enough to hoist expressions even out of closures, nice!

julia> @macroexpand @cse begin
           foo(i) = i * j^2
           sum(foo(i) for i=1:2)
       end
quote
    var"##266" = j ^ 2
    var"##267" = 1:2
    begin
        #= REPL[3]:2 =#
        foo(i) = begin
                #= REPL[3]:2 =#
                i * var"##266"
            end
        #= REPL[3]:3 =#
        sum((foo(i) for i = var"##267"))
    end
end