# Towards implementing CSE in the Julia compiler

**URL:** <https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922>\
**Category:** Internals & Design\
**Created:** [August 17, 2023, 6:09pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922 "2023-08-17T18:09:27Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 17, 2023, 5:33pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/1 "2023-08-17T17:33:01Z")

</div>

Specifically implementing CSE on Julia IR could be a pretty good introduction to the compiler for someone. We already have all the analysis needed (it’s the same analysis for dead code elimination), so it’s mostly just a matter of a little plumbing.

---

<div class="post-metadata">

**Author:** ![Krastanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krastanov/32/6817_2.png) [@Krastanov](https://discourse.julialang.org/u/Krastanov)\
**Post date:** [August 17, 2023, 6:09pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/2 "2023-08-17T18:09:27Z")

</div>

I was curious how difficult it is for a novice to do such a project, as described by Oscar.

It seems [the dead code elimination Julia pass](https://github.com/JuliaLang/julia/blob/30a73de68108b9629c4c99a1751d579ef5893bda/base/compiler/ssair/passes.jl#L1715) is not too difficult to find. On one hand, it is a relatively high-level function of just 150 lines of code with relatively easy to follow logic. On the other hand, it seems to require knowing a lot of terms, conventions, and definitions, used only in the Julia internals, and not really known to most folks.

Could one of the core developers give us a minimal example of what it looks like to use this `adce_pass!` function “manually”? E.g., how can I see the effect of `adce_pass` on this method:

```julia
function f(x::Int)
    if false
        return 0
    end
    if isa(x, Float64)
        return 1
    end
    return 2
end

```

How do I transform that method into `IRCode` that I can then call `adce_pass` on?

Lastly, can I modify `adce_pass` in order to have it print debug statements and rely on Revise to take care of reloading it without having to restart (or recompile) Julia?

Maybe this should be split off into a separate thread…

---

<div class="post-metadata">

**Author:** ![vchuravy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vchuravy/32/8_2.png) [@vchuravy](https://discourse.julialang.org/u/vchuravy)\
**Post date:** [August 17, 2023, 7:47pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/3 "2023-08-17T19:47:42Z")

</div>

```julia
function f(x::Int)
    if false
        return 0
    end
    if isa(x, Float64)
        return 1
    end
    return 2
end

julia> IR = only(Base.code_ircode(f, (Int,), optimize_until="SROA")).first
2 1 ─ goto #3 if not false │
  2 ─ nothing::Nothing │
5 3 ┄ goto #5 if not false │
  4 ─ nothing::Nothing │
8 5 ┄ return 2 │
                                                                                                                                                 

julia> Core.Compiler.adce_pass!(IR)

```

---

<div class="post-metadata">

**Author:** ![Krastanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krastanov/32/6817_2.png) [@Krastanov](https://discourse.julialang.org/u/Krastanov)\
**Post date:** [August 17, 2023, 8:01pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/4 "2023-08-17T20:01:28Z")

</div>

Thank you! If I may follow up with some silly questions:

```julia
julia> function f(x::Int)
           y = x^x
           if false
               return 0
           end
           if isa(x, Float64)
               return 1
           end
           return 2
       end
f (generic function with 1 method)

julia> Base.code_ircode(f, (Int,)) |> only |> first |> Core.Compiler.adce_pass!
2 1 ─ invoke Base.power_by_squaring(_2::Int64, _2::Int64)::Int64 │╻ ^
3 └── goto #3 if not false │ 
  2 ─ nothing::Nothing │ 
6 3 ┄ goto #5 if not false │ 
  4 ─ nothing::Nothing │ 
9 5 ┄ return 2

```

1. I would have expected the `power_by_squaring` to be eliminated… Why is it still there? (even after a redundant `adce_pass!` given that `code_ircode` already calls it).

2. Why are all these `goto` to constant locations not skipped?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 17, 2023, 8:22pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/5 "2023-08-17T20:22:44Z")

</div>

It doesn’t get eliminated because `power_by_squaring` will throw for negative integers. If you changed it to `x^7` it will be eliminated. The gotos are there for reasons of annoying everyone who works on our IR.

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [August 19, 2023, 10:17am UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/6 "2023-08-19T10:17:20Z")

</div>

Is there a way to use a `Dict{Expr, Int}` in the compiler, I want a way to map between expressions and their SSAValues. `IdDict` doesn’t seem to work as two `Expr`’s having the same value doesn’t imply their `objectid` is the same.

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [August 19, 2023, 11:58am UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/7 "2023-08-19T11:58:50Z")

</div>

Could someone define the abbreviation CSE?

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [August 19, 2023, 12:00pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/8 "2023-08-19T12:00:09Z")

</div>

Should be [Common Subexpression Elimination](https://en.wikipedia.org/wiki/Common_subexpression_elimination).

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 19, 2023, 5:33pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/9 "2023-08-19T17:33:37Z")

</div>

I don’t think so. You might be able to use an `IdDict` of the args of the call.

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [August 19, 2023, 7:42pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/10 "2023-08-19T19:42:55Z")

</div>

Silly question, but if it really is Common Subexpression Elimination, don’t we need to be sure there are no side-effects? Is that info sufficiently available at the compiler level for CSE to be worthwhile?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 19, 2023, 7:51pm UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/11 "2023-08-19T19:51:30Z")

</div>

Yeah. That’s what the effect system tells you. Specifically, you can only CSE expressions that are consistent, side effect free, terminate and nothrow. (the last two conditions go away if you don’t CSE across control flow).

---

<div class="post-metadata">

**Author:** ![Zentrik](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zentrik/32/35409_2.png) [@Zentrik](https://discourse.julialang.org/u/Zentrik)\
**Post date:** [August 20, 2023, 9:44am UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/12 "2023-08-20T09:44:31Z")

</div>

btw this is the very rough version I have right now (it works in the REPL but not in the compiler because of the Dict)

```julia
import Core: SSAValue
import Core.Compiler: IRCode, IR_FLAG_EFFECT_FREE, IR_FLAG_NOTHROW, IR_FLAG_CONSISTENT, naive_idoms, is_meta_expr_head

# Available Expressions Data Flow Analysis
function available_expressions!(ir::IRCode)
    # @assert eachindex(ir.cfg.blocks) isa OneTo

    outflow = [Dict{Expr, Int}() for _ in eachindex(ir.cfg.blocks)]
    ssamap = IdDict{Int, Int}()

    # which is faster?
    # dom_tree = construct_domtree(ir.cfg.blocks)
    idoms = naive_idoms(ir.cfg.blocks)

    worklist = trues(length(ir.cfg.blocks))
    worklist_active_size = length(ir.cfg.blocks)

    block_idx = firstindex(ir.cfg.blocks)
    while worklist_active_size > 0
        if !worklist[block_idx]
            block_idx = findnext(worklist, block_idx)
        end
        worklist[block_idx] = false
        worklist_active_size -= 1

        block = ir.cfg.blocks[block_idx]

        # idom_idx = domtree.idoms_bb[block_idx]
        idom_idx = idoms[block_idx]
        outflow[block_idx] = idom_idx > 0 ? copy(outflow[idom_idx]) : Dict{Expr, Int}()

        changed = transfer_and_cse_pass!(ir, outflow[block_idx], ssamap, block.stmts)

        block_idx += 1
        if changed
            for succ_idx in block.succs
                if idoms[succ_idx] == block_idx
                    worklist[succ_idx] = true
                    worklist_active_size += !worklist[succ_idx]
                    block_idx = min(block_idx, succ_idx)
                end
            end
        end
    end

    return ir
end

# Tranfer function and CSE pass
function transfer_and_cse_pass!(ir::IRCode, inflow, ssamap, stmt_idxs)
    changed = false
    for i in stmt_idxs
        stmt = ir.stmts.stmt[i]

        stmt isa Expr || continue

       # need to check consistency and terminate?
        effect_free = (ir.stmts.flag[i] & (IR_FLAG_EFFECT_FREE | IR_FLAG_NOTHROW)) == IR_FLAG_EFFECT_FREE | IR_FLAG_NOTHROW
        effect_free || continue

        # copy propagation
        # taken from renumber_ir_elements!
        el = stmt
        if el.head === :(=) && el.args[2] isa Expr
            el = el.args[2]::Expr
        end
        if el.head !== :enter && !is_meta_expr_head(el.head)
            args = el.args
            for i in eachindex(args)
                arg = args[i]
                if isa(arg, SSAValue)
                    stmt.args[i] = SSAValue(get(ssamap, arg.id, arg.id))
                end
            end
        end

        if haskey(inflow, stmt)
            ssamap[i] = inflow[stmt]
            ir.stmts.stmt[i] = SSAValue(inflow[stmt])
        else
            inflow[stmt] = i
            changed = true
        end
    end

    return changed
end

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [August 21, 2023, 3:40am UTC](https://discourse.julialang.org/t/towards-implementing-cse-in-the-julia-compiler/102922/13 "2023-08-21T03:40:34Z")

</div>

Nice! I think you can probably make this work in the compiler by replacing the `Expr` with the `svec` of the function call and the args and then using an `IDDict`.