When can a single-call optimization be used?

General Usage Performance
1 
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.

2

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 https://github.com/JuliaLang/julia/issues/14324, https://github.com/JuliaLang/julia/issues/9942, https://github.com/JuliaLang/julia/issues/32024, https://github.com/JuliaLang/julia/issues/29285

4 Likes
3

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
4

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