wrong tbaa for ptr_phi in codegen (causes Transducers segfault)

[KristofferC]

Pasting this into the REPL segfaults

using Transducers
using Transducers: AdHocXF, @next
using Accessors: @reset

using Test

@testset "AdHocXF" begin
    flushlast(rf, result) = rf(@next(rf, result, result.state));
    xf = AdHocXF(nothing, flushlast) do rf, result, input
        m = match(r"^name:(.*)", input)
        if m === nothing
            push!(result.state.lines, input)
            return result
        else
            chunk = result.state
            @reset result.state = (name=strip(m.captures[1]), lines=String[])
            push!(result.state.lines, input)
            if chunk === nothing
                return result
            else
                return rf(result, chunk)
            end
        end
    end;
    @test collect(xf, split("""
name: Map
type: onetoone
name: Cat
type: expansive
name: Filter
type: contractive
name: Cat |> Filter
type: chaotic
""", "\n"; keepempty=false)) == [(name = "Map", lines = ["name: Map", "type: onetoone"])
                                 (name = "Cat", lines = ["name: Cat", "type: expansive"])
                                 (name = "Filter", lines = ["name: Filter", "type: contractive"])
                                 (name = "Cat |> Filter", lines = ["name: Cat |> Filter", "type: chaotic"])]
end

[31366] signal 11 (2): Segmentation fault: 11
in expression starting at REPL[9]:1
size at ./array.jl:194 [inlined]
axes at ./abstractarray.jl:98 [inlined]
axes1 at ./abstractarray.jl:137 [inlined]
eachindex at ./abstractarray.jl:389 [inlined]
lastindex at ./abstractarray.jl:426 [inlined]
_collect_to!! at /Users/kristoffercarlsson/.julia/packages/BangBang/g5v4f/src/collectors.jl:83 [inlined]
__append!!__ at /Users/kristoffercarlsson/.julia/packages/BangBang/g5v4f/src/collectors.jl:66 [inlined]
append!! at /Users/kristoffercarlsson/.julia/packages/BangBang/g5v4f/src/base.jl:118 [inlined]
next at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/combinators.jl:290 [inlined]
next at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/core.jl:287 [inlined]
next at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/library.jl:54 [inlined]
RFShim at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/library.jl:1392 [inlined]
#13 at ./REPL[9]:15
#52 at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/library.jl:1400 [inlined]
wrapping at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/core.jl:734 [inlined]
next at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/library.jl:1398 [inlined]
macro expansion at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/core.jl:181 [inlined]
macro expansion at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:199 [inlined]
macro expansion at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/simd.jl:41 [inlined]
_foldl_linear_bulk at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:198 [inlined]
macro expansion at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:192 [inlined]
macro expansion at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/basics.jl:98 [inlined]
_foldl_array at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:188 [inlined]
__foldl__ at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:182 [inlined]
#transduce#141 at /Users/kristoffercarlsson/PkgEvalAnalysis/dev/Transducers.jl/src/processes.jl:519 [inlined]

[vtjnash]

I started looking into this a bit. Didn't find anything useful yet, but did confirm where it reliably segfaults

[vtjnash]

It looks like this happens because %.fca.1.0.extract514 is NULL during this call, which appears may be because this phinode value is only non-null in LLVM after the call:

julia> code_llvm(eval(Expr(:new, Transducers.var"##transduce#140")), Tuple{Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}}, typeof(Transducers.transduce), Transducers.Composition{Transducers.AdHocXF{typeof(Main.f), Nothing, typeof(Main.flushlast)}, Transducers.Map{Type{BangBang.NoBang.SingletonVector{T} where T}}}, Transducers.AdHocRF{typeof(BangBang.collector), typeof(Base.identity), typeof(BangBang.append!!), typeof(Base.identity), typeof(Base.identity), Nothing}, BangBang.SafeCollector{BangBang.NoBang.Empty{Array{Union{}, 1}}}, Array{Base.SubString{String}, 1}}, raw=true)

          %value_phi102739 = phi { ptr, i64 } [ %.result_ptr101.unbox.fca.1.insert, %L170.thread ], [ zeroinitializer, %L170 ]                                                                                                                            

          %value_phi70661 = phi { ptr, i64 } [ zeroinitializer, %L120.lr.ph ], [ %value_phi102739, %guard_exit343 ]                                                                                                                                       

            %.fca.1.0.extract514 = extractvalue { ptr, i64 } %value_phi70661, 0, !dbg !209                                                                                                                                                                
            store ptr %.fca.1.0.extract514, ptr %gc_slot_addr13, align 8                                                                                                                                                                                  
            store ptr %.fca.1.0.extract514, ptr %.fca.1.0.gep515, align 8, !dbg !209                                                                                                                                                                      
            %.fca.1.1.extract = extractvalue { ptr, i64 } %value_phi70661, 1, !dbg !209                                                                                                                                                                   
            store i64 %.fca.1.1.extract, ptr %.fca.1.1.gep, align 8, !dbg !209                                                                                                                                                                            
            store ptr %.unpack559, ptr %gc_slot_addr12, align 16                                                                                                                                                                                          
            store ptr %.unpack559, ptr %10, align 8, !dbg !209                                                                                                                                                                                            
            store <2 x i64> %127, ptr %.fca.1.gep503, align 8, !dbg !209                                                                                                                                                                                  
            call swiftcc void @j_f_6638(ptr noalias nocapture noundef nonnull sret({ { { ptr, i64, i64 }, ptr }, { ptr, i64 } }) %8, ptr noalias nocapture noundef nonnull %0, ptr nonnull swiftself %pgcstack, ptr nocapture nonnull readonly %3, ptr noc
apture nonnull readonly %9, ptr nocapture nonnull readonly %10), !dbg !209                  
            ...
          %.result_ptr101.unbox.fca.1.insert = insertvalue { ptr, i64 } %.result_ptr101.unbox.fca.0.insert, i64 %.result_ptr101.unbox.fca.1.load, 1, !dbg !225                                                                                            

This comes via these julia IR snippets, which seem to be correct:

│    │││││││││││ %129 = Base.getfield(%127, :result)::BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}

│    ││││││││││ %133 = invoke f(%131::Transducers.RFShim{Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), type
of(identity), Nothing}}}}, %132::Transducers.ResultShim{@NamedTuple{name::SubString{String}, lines::Vector{String}}, BangBang.SafeCollector{Empty{Vector{Union{}}}}}, %122::SubString{String})::Union{Transducers.ResultShim{@NamedTuple{name::SubString{S
tring}, lines::Vector{String}}, BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}}, Transducers.ResultShim{@NamedTuple{name::SubString{String}, lines::Vector{String}}, BangBang.SafeCollector{Empty{Vector{Unio
n{}}}}}}                                                                                                                                                                                                                                                  
│    │││││││││││ %146 = Base.getfield(%133, :result)::BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}
│    │││││││││││ %149 = Base.getfield(%133, :result)::BangBang.SafeCollector{Empty{Vector{Union{}}}}

│    ││││││││││ %152 = φ (#49 => %146, #50 => %149)::Union{BangBang.SafeCollector{Empty{Vector{Union{}}}}, BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}}

│    │││││││││ %159 = φ (#54 => %152)::BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}

58 ┄─│││││││ %170 = φ (#44 => %129, #57 => %159)::BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}

│    │││││││ %103 = φ (#62 => %170)::BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}

│    │││││││││││ %126 = %new(Transducers.ResultShim{@NamedTuple{name::SubString{String}, lines::Vector{String}}, BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}}, %102, %103)

│    ││││││││││ %127 = invoke f(%125::Transducers.RFShim{Transducers.Reduction{Map{Type{BangBang.NoBang.SingletonVector}}, Transducers.BottomRF{Transducers.AdHocRF{typeof(BangBang.collector), typeof(identity), typeof(append!!), typeof(identity), typeof(identity), Nothing}}}}, %126::Transducers.ResultShim{@NamedTuple{name::SubString{String}, lines::Vector{String}}, BangBang.SafeCollector{Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}}}, %122::SubString{String})

So it seems like we might be missing the copy of %152 => %159 when done with LLVM optimizations that was present in the Julia IR?

[vtjnash]

Since julia -O1 doesn't fail here, and opt -O3 looks like it generates correct IR here also when fed the output of code_llvm, I suspect either we are annotating something incorrectly and LLVM is doing an AA pass to delete the code or LLVM is doing something wrong because of our specific pass ordering.

julia> collect(xf, split("""
      name: Map
      type: onetoone
      name: Cat
      type: expansive
      name: Filter
      type: contractive
      name: Cat |> Filter
      type: chaotic
      """, "\n"; keepempty=false))
4-element Vector{@NamedTuple{name::SubString{String}, lines::Vector{String}}}:
(name = "Map", lines = ["name: Map", "type: onetoone"])
(name = "Cat", lines = ["name: Cat", "type: expansive"])
(name = "Filter", lines = ["name: Filter", "type: contractive"])
(name = "Cat |> Filter", lines = ["name: Cat |> Filter", "type: chaotic"])

[vtjnash]

The segfault specifically goes away if we run with -enable-gvn-memdep=false. Specifically, if opt -passes=gvn is run on this file, the phinode value for %value_phi102 gets replaced with a nullpointer:
dump4.ll.txt

The debug remarks say this is because we sort of specifically told it to do so via the aliasing info:

  call void @llvm.memcpy.p10.p11.i64(ptr addrspace(10) noundef nonnull align 8 dereferenceable(16) %"box::SafeCollector412", ptr addrspace(11) noundef align 8 dereferenceable(16) %.result_ptr279, i64 16, i1 false), !tbaa !43, !alias.scope !47, !noalias !48
  %69 = addrspacecast ptr addrspace(10) %"box::SafeCollector412" to ptr addrspace(11)

  %.unbox422.fca.0.load = load ptr addrspace(10), ptr addrspace(11) %69, align 8, !tbaa !37, !alias.scope !39, !noalias !40

!37 = !{!38, !38, i64 0}
!38 = !{!"jtbaa_stack", !5, i64 0}

!43 = !{!44, !44, i64 0}
!44 = !{!"jtbaa_immut", !45, i64 0}

!47 = !{!16}
!48 = !{!14, !15, !17, !11}
!16 = !{!"jnoalias_data", !12}

!39 = !{!15}
!40 = !{!14, !16, !17, !11}
!15 = !{!"jnoalias_stack", !12}

I don't know precisely when we generate the tbaa info for ptr_phi, but we are not being consistent with the usage here:

            %ptr_phi = phi ptr addrspace(10) [ %"box::SafeCollector412", %guard_exit272 ], [ null, %guard_exit290 ]
...
            %249 = select i1 %246, ptr addrspace(11) %248, ptr addrspace(11) %247, !dbg !287

This may be relevant:

julia/src/codegen.cpp

Line 5637 in 6335386

jl_cgval_t val = mark_julia_slot(ptr, phiType, Tindex_phi, ctx.tbaa().tbaa_stack); // XXX: this TBAA is wrong for ptr_phi