Julia: Malformed SSA generation

[MikeInnes]

A stripped down version of https://github.com/FluxML/Zygote.jl/issues/54#issuecomment-465378937, which has more description. This IR leads to an internal error in the optimiser when test(1) is called (the function still runs OK, though some variants of this were causing crashes).

Full reproducer:

using Core.Compiler: GotoNode, SSAValue

xcall(m, f, args...) = Expr(:call, GlobalRef(m, f), args...)

function construct()
  ci = @code_lowered identity(1)

  ci.code = Any[
    nothing,
    nothing,
    nothing,
    nothing,
    nothing,
    nothing,
    nothing,
    xcall(Base, :rand, Bool),
    Expr(:gotoifnot, SSAValue(8), 16),
    GotoNode(11),
    nothing,
    xcall(Base, :rand, Bool),
    Expr(:(=), Core.SlotNumber(3), Core.SlotNumber(2)),
    Expr(:gotoifnot, SSAValue(12), 22),
    GotoNode(20),
    Expr(:(=), Core.SlotNumber(4), Core.SlotNumber(2)),
    GotoNode(18),
    Expr(:(=), Core.SlotNumber(3), Core.SlotNumber(4)),
    GotoNode(22),
    Expr(:(=), Core.SlotNumber(4), Core.SlotNumber(3)),
    GotoNode(18),
    xcall(Base, :identity, Core.SlotNumber(3)),
    Expr(:return, Core.SSAValue(22))]

  ci.slotflags = [0x00, 0x00, 0x00, 0x00]
  ci.slotnames = [Symbol("#self#"), :x, :a, :b]
  ci.codelocs = [Int32(0) for x in ci.code]
  ci.ssavaluetypes = length(ci.code)
  return ci
end

@generated function test(x)
  return construct()
end

test(1)

[vtjnash]

julia> ci = @code_lowered test(1)
CodeInfo(
1 ─       nothing
│         nothing
│         nothing
│         nothing
│         nothing
│         nothing
│         nothing
│   %8  = Base.rand(Bool)
└──       goto #5 if not %8
2 ─       goto #3
3 ─       nothing
│   %12 = Base.rand(Bool)
│         a = x
└──       goto #8 if not %12
4 ─       goto #7
5 ─       b = x
└──       goto #6
6 ┄       a = b
└──       goto #8
7 ─       b = a
└──       goto #6
8 ┄ %22 = Base.identity(a)
└──       return %22
)

julia> m = @which test(1);
julia> r = Core.Compiler.code_for_method(m, Tuple{typeof(m), Int}, Core.svec(), typemax(UInt64));
julia> Core.Compiler.Core.Compiler.just_construct_ssa(ci, Base.copy_exprargs(ci.code), 1, Core.Compiler.OptimizationState(r, ci, Core.Compiler.DEFAULT_PARAMS))
 1 ─       nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │         nothing::Any                                                                                                                                                         │
 │   %8  = Base.rand(Bool)::Any                                                                                                                                                 │
 └──       goto #7 if not %8                                                                                                                                                    │
 2 ─       nothing::Any                                                                                                                                                         │
 3 ─       nothing::Any                                                                                                                                                         │
 │   %12 = Base.rand(Bool)::Any                                                                                                                                                 │
 │   %13 = _2::Any                                                                                                                                                              │
 └──       goto #6 if not %12                                                                                                                                                   │
 4 ─       nothing::Any                                                                                                                                                         │
 5 ─ %16 = %13::Any                                                                                                                                                             │
 └──       goto #8                                                                                                                                                              │
 6 ┄ %18 = Base.identity(%22)::Any                                                                                                                                              │
 └──       return %18                                                                                                                                                           │
 7 ─ %20 = _2::Any                                                                                                                                                              │
 └──       nothing::Any                                                                                                                                                         │
 8 ┄ %24 = φ (#5 => %16, #7 => %20)::Any                                                                                                                                        │
 │   %22 = %24::Any
 └──       goto #6                                                                                                                                                              │

note that I think that last IR is mis-sorted also

[Keno]

This does look like a bug in SSA construction. As for the mis-sorting, that's probably ok since that node is likely pending (if so, it should be color coded as such, not sure if that got lost in all the IR printing changes).

[vtjnash]

just lost in the copy-to-text. yes, node%24 is pending. bb#6 still seems potentially to be in the wrong place (it post-dominates the function, and thus I'd expect it to remain last)

julia> Core.Compiler.compact!(ans)
 1 ─ %1  = Base.rand(Bool)::Any                                                                                                                                                            │
 └──       goto #7 if not %1                                                                                                                                                               │
 2 ─       nothing::Nothing                                                                                                                                                                │
 3 ─ %4  = Base.rand(Bool)::Any                                                                                                                                                            │
 └──       goto #6 if not %4                                                                                                                                                               │
 4 ─       nothing::Nothing                                                                                                                                                                │
 5 ─       goto #8                                                                                                                                                                         │
 6 ┄ %8  = Base.identity(%22)::Any                                                                                                                                                         │
 └──       return %8                                                                                                                                                                       │
 7 ─       nothing::Nothing                                                                                                                                                                │
 8 ┄       nothing::Any                                                                                                                                                                    │
 └──       goto #6                                                                                                                                                                         │

[Keno]

Sure, but the phi node is missing before domsorting also.

[Keno]

Looks like an SNCA bug.

with

using AbstractTrees
using Core.Compiler: DomTree

AbstractTrees.treekind(d::DomTree) = AbstractTrees.IndexedTree()
AbstractTrees.childindices(d::DomTree, i::Int) = d[i].children
AbstractTrees.childindices(::DomTree, ::DomTree) = (1,)
AbstractTrees.parentlinks(::DomTree) = AbstractTrees.StoredParents()
AbstractTrees.printnode(io::IO, i::Int, d::DomTree) = print(io, i)
Base.getindex(d::DomTree, i) = d.nodes[i]
Base.show(io::IO, d::DomTree) = print_tree(io, 1; roottree = d)

we see

julia> cfg = Core.Compiler.compute_basic_blocks(ci.code)
1   =>  5, 2
2   =>  3
3   =>  8, 4
4   =>  7
5   =>  6
6   =>  8
7   =>  6
8   =>


julia> Core.Compiler.construct_domtree(cfg)
1
├─ 2
│  └─ 3
│     ├─ 4
│     │  └─ 7
│     └─ 8
├─ 5
└─ 6


julia> Core.eval(Core.Compiler, quote
       function construct_domtree_naive(cfg::CFG)
           idoms = naive_idoms(cfg)
           # Compute children
           nblocks = length(cfg.blocks)
           domtree = DomTreeNode[DomTreeNode() for _ = 1:nblocks]
           for (idx, idom) in Iterators.enumerate(idoms)
               (idx == 1 || idom == 0) && continue
               push!(domtree[idom].children, idx)
           end
           # Recursively set level
           update_level!(domtree, 1, 1)
           DomTree(idoms, domtree)
       end
       end)
construct_domtree_naive (generic function with 1 method)

julia> Core.Compiler.construct_domtree_naive(cfg)
1
├─ 2
│  └─ 3
│     └─ 4
│        └─ 7
├─ 5
├─ 6
└─ 8

[Keno]

This one was fun. I'll use it as a homework if I ever teach a compiler course.