Segfault in collect in HierarchialUtilities

[KristofferC]

Somewhat of an MWE:

import HierarchicalUtils: NodeType, children

mutable struct Leaf
    n::Int64
end
struct SingletonVertex{T}
    ch::T
end

NodeType(::Type{Nothing}) = LeafNode()
NodeType(::Type{<:Tuple}) = InnerNode()
NodeType(::Type{Leaf}) = LeafNode()
NodeType(::Type{<:SingletonVertex}) = InnerNode()

children(v::Tuple) = v
children(t::SingletonVertex) = (t.ch,)

_childsort(x::Tuple) = x
_children_sorted(n) = _childsort(children(n))

l2 = Leaf(2)
n3t = SingletonVertex(l2)
ts = (n3t, nothing)

chss1 = [_children_sorted(t) for t in ts if !(isnothing(t))] # boom

signal (11): Segmentation fault: 11
in expression starting at HierarchicalUtils.jl/test/utilities.jl:25
iterate at ./tuple.jl:68 [inlined]
iterate at ./iterators.jl:470 [inlined]
iterate at ./generator.jl:44 [inlined]
grow_to! at ./array.jl:882
grow_to! at ./array.jl:864 [inlined]
collect at ./array.jl:784
unknown function (ip: 0x111a3aae9)
_jl_invoke at /Users/kristoffercarlsson/julia/src/gf.c:0 [inlined]
ijl_apply_generic at /Users/kristoffercarlsson/julia/src/gf.c:2540
...

Tested on the backports-release-1.8 branch

[maleadt]

Reduced to the following (which only fails on -O0 anymore, but it looks like the same issue):

struct a
end
struct b{c}
    ch::c
end
children(d) = (d,)
e(i) = children(i)
f = a
g = b(f)
h = g, nothing
[e(d) for d in h if isnothing(d)] 

[vtjnash]

There does seem to be a lot of badness there of this sort:

   %value_phi19 = phi {} addrspace(10)* [ null, %L62 ], [ %119, %L73 ], [ addrspacecast ({}* inttoptr (i64 139967715850432 to {}*) to {} addrspace(10)*), %L68 ]                                  
   %123 = bitcast {} addrspace(10)* %value_phi19 to i64 addrspace(10)*, !dbg !25                                                                                                                  
   %124 = getelementptr inbounds i64, i64 addrspace(10)* %123, i64 -1, !dbg !25                                                                                                                   
   %125 = load atomic i64, i64 addrspace(10)* %124 unordered, align 8, !dbg !25, !tbaa !30, !range !38

Which is confusing to codegen, since it probably wants to union-unbox this from the phi node

│     %82  = φ (#31 => %79)::Union{Tuple{Nothing}, Tuple{b{DataType}}}                                                                                                                            

To make it applicable to the next phi node:

│     %82  = φ (#31 => %79)::Union{Tuple{Nothing}, Tuple{b{DataType}}}
...
│     %86  = φ (#32 => %82, #119 => %286)::Tuple{b{DataType}}

What likely happened here is that the optimizer generates code it knows is illegal (moving non-existent values into places they cannot go), but which it wants to be valid at runtime (since we promise we won't observe the value later, codegen is expected to simply discard the impossible)

julia> begin
       struct b{c}
           ch::c
       end
       e(i) = (i,)
       h = b(Int), nothing
       end
(b{DataType}(Int64), nothing)

julia> # collect(Base.Generator(e, Base.Iterators.Filter(isnothing, h)))

julia> code_llvm(Base.grow_to!, (Array{Tuple{Nothing}, 1}, Base.Generator{Base.Iterators.Filter{typeof(isnothing), typeof(h)}, typeof(e)}, Int64), raw=true, optimize=false)

[KristofferC]

Bump. @vtjnash (or someone else) did you manage to get any further with this?

[vtjnash]

Yes, I wrote a fix for this