recognize escapes from implicit `throw`s involved with builtins #6

aviatesk · 2021-06-30T08:51:16Z

MRE:

julia> analyze_escapes((Type{Array},)) do t
           sizeof(t)
       end
2 1 ─ %1 = Core.sizeof::typeof(Core.sizeof)                                                                                                                                                                          │╻ sizeof
  │   %2 = (%1)(_2)::Int64                                                                                                                                                                                           ││
  └──      return %2                                                                                                                                                                                                 │ 
  , EscapeAnalysis.EscapeState(                                                                                                                                                                                        
EscapeAnalysis.EscapeInformation[EscapeAnalysis.ReturnEscape(), EscapeAnalysis.ReturnEscape()], EscapeAnalysis.EscapeInformation[EscapeAnalysis.NoInformation(), EscapeAnalysis.ReturnEscape(), EscapeAnalysis.NoInformation()]))

Actually sizeof(t) throws in this case, and thus t escapes as an exception.
We may want to use the existing query to check throw-freeness.

The text was updated successfully, but these errors were encountered:

@noinline

Currently this PR just re-uses ["effect-freeness" of a statement](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/ssair/queries.jl#L6) computed by inliner. This is necessary but we lose much analysis accuracy, e.g. now we can't recognize the target below: ```julia julia> @noinline f_noescape(x) = (broadcast(identity, x); nothing); julia> analyze_escapes() do f_noescape(Ref("Hi")) end var"#3#4"() 1 → 1 ─ %1 = %new(Base.RefValue{String}, "Hi")::Base.RefValue{String} 2 ↑ │ %2 = invoke Main.f_noescape(%1::Base.RefValue{String})::Core.Const(nothing) 3 ◌ └── return %2 ``` This case is particularly because Julia compiler doesn't tell `getfield(::Base.RefValue, :x)` is "effect-free" since it's caught by [this `field <= datatype_min_ninitialized(s)` check](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/tfuncs.jl#L745). We may need to improve inference instead rather than doing something in this pass.

@noinline

Currently this PR just re-uses ["effect-freeness" of a statement](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/ssair/queries.jl#L6) computed by inliner. This is necessary but we lose much analysis accuracy, e.g. now we can't recognize the target below: ```julia julia> @noinline f_noescape(x) = (broadcast(identity, x); nothing); julia> analyze_escapes() do f_noescape(Ref("Hi")) end var"#3#4"() 1 → 1 ─ %1 = %new(Base.RefValue{String}, "Hi")::Base.RefValue{String} 2 ↑ │ %2 = invoke Main.f_noescape(%1::Base.RefValue{String})::Core.Const(nothing) 3 ◌ └── return %2 ``` This case is particularly because Julia compiler doesn't tell `getfield(::Base.RefValue, :x)` is "effect-free" since it's caught by [this `field <= datatype_min_ninitialized(s)` check](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/tfuncs.jl#L745). We may need to improve inference instead rather than doing something in this pass.

@noinline

Currently this PR just re-uses ["effect-freeness" of a statement](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/ssair/queries.jl#L6) computed by inliner. This is necessary but we lose much analysis accuracy, e.g. now we can't recognize the target below: ```julia julia> @noinline f_noescape(x) = (broadcast(identity, x); nothing); julia> analyze_escapes() do f_noescape(Ref("Hi")) end var"#3#4"() 1 → 1 ─ %1 = %new(Base.RefValue{String}, "Hi")::Base.RefValue{String} 2 ↑ │ %2 = invoke Main.f_noescape(%1::Base.RefValue{String})::Core.Const(nothing) 3 ◌ └── return %2 ``` This case is particularly because Julia compiler doesn't tell `getfield(::Base.RefValue, :x)` is "effect-free" since it's caught by [this `field <= datatype_min_ninitialized(s)` check](https://github.com/JuliaLang/julia/blob/94b9d66b10e8e3ebdb268e4be5f7e1f43079ad4e/base/compiler/tfuncs.jl#L745). We may need to improve inference instead rather than doing something in this pass.

This commit implements a simple, flow-insensitive alias analysis using an approach inspired by the escape analysis algorithm explained in the old JVM paper [^JVM05]. `EscapeLattice` is extended so that it also keeps track of possible field values. In more detail, `x::EscapeLattice` has the new field called `x.FieldSet::Union{Vector{IdSet{Any}},Bool}`, where: - `x.FieldSets === false` indicates the fields of `x` isn't analyzed yet - `x.FieldSets === true` indicates the fields of `x` can't be analyzed, e.g. the type of `x` is not concrete and thus the number of its fields can't known precisely - otherwise `x.FieldSets::Vector{IdSet{Any}}` holds all the possible values of each field, where `x.FieldSets[i]` keeps all possibilities that the `i`th field can be And now, in addition to managing escape lattice elements, the analysis state also maintains an "alias set" `state.aliasset::IntDisjointSet{Int}`, which is implemented as a disjoint set of aliased arguments and SSA statements. When the fields of object `x` are known precisely (i.e. `x.FieldSets isa Vector{IdSet{Any}}` holds), the alias set is updated each time `z = getfield(x, y)` is encountered in a way that `z` is aliased to all values of `x.FieldSets[y]`, so that escape information imposed on `z` will be propagated to all the aliased values and `z` can be replaced with an aliased value later. Note that in a case when the fields of object `x` can't known precisely (i.e. `x.FieldSets` is `true`), when `z = getfield(x, y)` is analyzed, escape information of `z` is propagated to `x` rather than any of `x`'s fields, which is the most conservative propagation since escape information imposed on `x` will end up being propagated to all of its fields anyway at definitions of `x` (i.e. `:new` expression or `setfield!` call). [^JVM05]: Escape Analysis in the Context of Dynamic Compilation and Deoptimization. Thomas Kotzmann and Hanspeter Mössenböck, 2005, June. <https://dl.acm.org/doi/10.1145/1064979.1064996>. Now this alias analysis should allow us to implement a "stronger" SROA, which eliminates the allocation of `r` within the following code: ```julia julia> result = analyze_escapes((String,)) do s r = Ref(s) broadcast(identity, r) end 2 ↓ 1 ─ %1 = %new(Base.RefValue{String}, _2)::Base.RefValue{String} │╻╷╷ Ref 3 ✓ │ %2 = Core.tuple(%1)::Tuple{Base.RefValue{String}} │╻ broadcast ↓ │ %3 = Core.getfield(%2, 1)::Base.RefValue{String} ││ ◌ └── goto #3 if not true ││╻╷ materialize ◌ 2 ─ nothing::Nothing │ * 3 ┄ %6 = Base.getfield(%3, :x)::String │││╻╷╷╷╷ copy ◌ └── goto #4 ││││┃ getindex ◌ 4 ─ goto #5 ││││ ◌ 5 ─ goto #6 │││ ◌ 6 ─ goto #7 ││ ◌ 7 ─ return %6 │ julia> EscapeAnalysis.get_aliases(result.state.aliasset, Core.SSAValue(6), result.ir) 2-element Vector{Union{Core.Argument, Core.SSAValue}}: Core.Argument(2) :(%6) ``` Note that the allocation `%1` isn't analyzed as `ReturnEscape`, although it is still analyzed as `ThrownEscape`.

This commit implements a simple, flow-insensitive alias analysis using an approach inspired by the escape analysis algorithm explained in the old JVM paper [^JVM05]. `EscapeLattice` is extended so that it also keeps track of possible field values. In more detail, `x::EscapeLattice` has the new field called `x.FieldSet::Union{Vector{IdSet{Any}},Bool}`, where: - `x.FieldSets === false` indicates the fields of `x` isn't analyzed yet - `x.FieldSets === true` indicates the fields of `x` can't be analyzed, e.g. the type of `x` is not concrete and thus the number of its fields can't known precisely - otherwise `x.FieldSets::Vector{IdSet{Any}}` holds all the possible values of each field, where `x.FieldSets[i]` keeps all possibilities that the `i`th field can be And now, in addition to managing escape lattice elements, the analysis state also maintains an "alias set" `state.aliasset::IntDisjointSet{Int}`, which is implemented as a disjoint set of aliased arguments and SSA statements. When the fields of object `x` are known precisely (i.e. `x.FieldSets isa Vector{IdSet{Any}}` holds), the alias set is updated each time `z = getfield(x, y)` is encountered in a way that `z` is aliased to all values of `x.FieldSets[y]`, so that escape information imposed on `z` will be propagated to all the aliased values and `z` can be replaced with an aliased value later. Note that in a case when the fields of object `x` can't known precisely (i.e. `x.FieldSets` is `true`), when `z = getfield(x, y)` is analyzed, escape information of `z` is propagated to `x` rather than any of `x`'s fields, which is the most conservative propagation since escape information imposed on `x` will end up being propagated to all of its fields anyway at definitions of `x` (i.e. `:new` expression or `setfield!` call). [^JVM05]: Escape Analysis in the Context of Dynamic Compilation and Deoptimization. Thomas Kotzmann and Hanspeter Mössenböck, 2005, June. <https://dl.acm.org/doi/10.1145/1064979.1064996>. Now this alias analysis should allow us to implement a "stronger" SROA, which eliminates the allocation of `r` within the following code: ```julia julia> result = analyze_escapes((String,)) do s r = Ref(s) broadcast(identity, r) end \#3(_2::String *, _3::Base.RefValue{String} ◌) in Main at REPL[2]:2 2 ↓ 1 ─ %1 = %new(Base.RefValue{String}, _2)::Base.RefValue{String} │╻╷╷ Ref 3 ✓ │ %2 = Core.tuple(%1)::Tuple{Base.RefValue{String}} │╻ broadcast ↓ │ %3 = Core.getfield(%2, 1)::Base.RefValue{String} ││ ◌ └── goto #3 if not true ││╻╷ materialize ◌ 2 ─ nothing::Nothing │ * 3 ┄ %6 = Base.getfield(%3, :x)::String │││╻╷╷╷╷ copy ◌ └── goto #4 ││││┃ getindex ◌ 4 ─ goto #5 ││││ ◌ 5 ─ goto #6 │││ ◌ 6 ─ goto #7 ││ ◌ 7 ─ return %6 │ julia> EscapeAnalysis.get_aliases(result.state.aliasset, Core.SSAValue(6), result.ir) 2-element Vector{Union{Core.Argument, Core.SSAValue}}: Core.Argument(2) :(%6) ``` Note that the allocation `%1` isn't analyzed as `ReturnEscape`, still `_2` is analyzed so.

aviatesk mentioned this issue Jun 30, 2021

builtin: add ifelse handling #4

Merged

aviatesk mentioned this issue Jul 5, 2021

circumvent escapes through potential throw calls #15

Closed

aviatesk closed this as completed in b3f705c Jul 5, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

recognize escapes from implicit `throw`s involved with builtins #6

recognize escapes from implicit `throw`s involved with builtins #6

aviatesk commented Jun 30, 2021

recognize escapes from implicit throws involved with builtins #6

recognize escapes from implicit throws involved with builtins #6

Comments

aviatesk commented Jun 30, 2021

recognize escapes from implicit `throw`s involved with builtins #6

recognize escapes from implicit `throw`s involved with builtins #6