Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

inference: forward Conditional inter-procedurally #42529

Merged
merged 4 commits into from
Oct 21, 2021

Conversation

aviatesk
Copy link
Sponsor Member

@aviatesk aviatesk commented Oct 7, 2021

The PR #38905 only "back-propagates" conditional constraint
(from callee to caller), but currently we don't "forward" it
(caller to callee), and so inter-procedural constraint propagation
won't happen for e.g.:

ifelselike(cnd, x, y) = cnd ? x : y
@test Base.return_types((Any,Int,)) do x, y
    ifelselike(isa(x, Int), x, y)
end |> only == Int

This commit complements #38905 and enables further inter-procedural
conditional constraint propagation by forwarding Conditional to
callees when it imposes a constraint on any other argument,
during constant propagation.


Copy link
Member

@c42f c42f left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This seems great! I had a read through though I don't know the surrounding code well enough to review properly.

base/compiler/abstractinterpretation.jl Outdated Show resolved Hide resolved
base/compiler/abstractinterpretation.jl Outdated Show resolved Hide resolved
@aviatesk aviatesk force-pushed the avi/forwardconditional branch 5 times, most recently from 4d598c7 to 06f196a Compare October 12, 2021 14:28
@aviatesk
Copy link
Sponsor Member Author

Alright, I think this PR is ready to go. @vtjnash can I ask your review on this ?

@aviatesk aviatesk force-pushed the avi/forwardconditional branch 2 times, most recently from 3ed9124 to 018e46d Compare October 18, 2021 09:12
@aviatesk
Copy link
Sponsor Member Author

@vtjnash I'd like to merge this PR tomorrow on my responsibility, but I'd appreciate if you could review it if you have a time.

base/compiler/abstractinterpretation.jl Outdated Show resolved Hide resolved
base/compiler/abstractinterpretation.jl Outdated Show resolved Hide resolved
base/compiler/inferenceresult.jl Outdated Show resolved Hide resolved
base/compiler/inferenceresult.jl Outdated Show resolved Hide resolved
base/compiler/inferenceresult.jl Outdated Show resolved Hide resolved
base/compiler/inferenceresult.jl Outdated Show resolved Hide resolved
Comment on lines 43 to 44
# union-split should never find a more precise information about `fargs[slotid]` than `Conditional`,
# otherwise there should have been a bug around `Conditional` construction or maintainance
Copy link
Sponsor Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't believe this is true, since Conditional is actually tri-stated. Consider:

f(::Int) = 1
f(::Float64) = 2
f(::String) = 3

x::Any
if x isa Union{Int, Float64}
   cond = x isa Int
end
f(cond, x) # x was Any before examining `cond::Conditional(:x, Int, Float64)`, but now the signature for `String` is excluded

Copy link
Sponsor Member Author

@aviatesk aviatesk Oct 21, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Right, thanks for your review.

I added 28f50c6 so that we just propagate Bottom in such a case (where we accidentally prove the method match is impossible).
Now this code snippet doesn't throw:

Base.@constprop :aggressive f(cnd, ::Int) = cnd
Base.@constprop :aggressive f(cnd, ::Float64) = !cnd
Base.@constprop :aggressive f(cnd, ::String) = cnd

function g()
    x = v::Any
    if x isa Union{Int, Float64}
        cnd = x isa Int # ::Conditional(:x, Int, Float64)
    end
    f(cnd, x)
end

@code_typed optimize=false g()

aviatesk and others added 3 commits October 21, 2021 14:59
The PR #38905 only "back-propagates" conditional constraint
(from callee to caller), but currently we don't "forward" it
(caller to callee), and so inter-procedural constraint propagation
won't happen for e.g.:
```julia
ifelselike(cnd, x, y) = cnd ? x : y
@test Base.return_types((Any,Int,)) do x, y
    ifelselike(isa(x, Int), x, y)
end |> only == Int
```

This commit complements #38905 and enables further inter-procedural
conditional constraint propagation by forwarding `Conditional` to
callees when it imposes a constraint on any other argument,
during constant propagation.
- remove `const_prop_rettype_heuristic` since it handles rare cases,
  where const-prop' doens't seem to be worthwhile, e.g. it won't be
  so useful to try to propagate `Const(Tuple{DataType,DataType})` for
  `Const(convert)(::Const(Tuple{DataType,DataType}), ::Tuple{DataType,DataType} -> Tuple{DataType,DataType}`
- rename `is_allconst` to `is_all_overridden`
- also minor refactors and improvements added
@aviatesk aviatesk force-pushed the avi/forwardconditional branch 3 times, most recently from 701a2a1 to 28f50c6 Compare October 21, 2021 11:28
@vtjnash vtjnash merged commit 9557259 into master Oct 21, 2021
@vtjnash vtjnash deleted the avi/forwardconditional branch October 21, 2021 16:56
aviatesk added a commit to aviatesk/JET.jl that referenced this pull request Oct 21, 2021
aviatesk added a commit that referenced this pull request Oct 21, 2021
JET reported:
```julia
julia> report_package(JET)
...
[toplevel-info] analyzing from top-level definitions ... 671/671
═════ 12 possible errors found ═════
...
┌ @ avi-/JET/src/JET.jl:990 #self#(text, "top-level")
│┌ @ avi-/JET/src/JET.jl:990 JET.#report_text#124(JET.JETAnalyzer, JET.nothing, Base.pairs(Core.NamedTuple()), #self#, text, filename)
││┌ @ avi-/JET/src/JET.jl:993 res = JET.virtual_process(text, filename, analyzer′, config)
│││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:301 res = JET._virtual_process!(x, filename, analyzer, config, context, JET.VirtualProcessResult(actual2virtual, context))
││││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:432 res = JET._virtual_process!(toplevelex, filename, analyzer, config, context, res)
│││││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:637 JET.analyze_toplevel!(analyzer, src)
││││││┌ @ avi-/JET/src/JET.jl:1142 JET.#analyze_toplevel!#133(true, #self#, analyzer, src)
│││││││┌ @ avi-/JET/src/JET.jl:1160 JET.analyze_frame!(analyzer, frame)
││││││││┌ @ avi-/JET/src/JET.jl:747 JET.typeinf(analyzer, frame)
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 Core.Compiler.lastindex(fargs)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.lastindex), Nothing})): Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 fargs′ = Core.Compiler.getindex(fargs, Core.Compiler.:(3, Core.Compiler.lastindex(fargs)))
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Core.Compiler.UnitRange{Int64}})): fargs′ = Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, Core.Compiler.:(3, Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})::Int64)::Core.Compiler.UnitRange{Int64})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1244 Core.Compiler.getindex(fargs, 1)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Int64})): Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, 1)
│││││││││└───────────────────────────────────────────
...
```
aviatesk added a commit that referenced this pull request Oct 21, 2021
JET reported:
```julia
julia> report_package(JET)
...
[toplevel-info] analyzing from top-level definitions ... 671/671
═════ 12 possible errors found ═════
...
┌ @ avi-/JET/src/JET.jl:990 #self#(text, "top-level")
│┌ @ avi-/JET/src/JET.jl:990 JET.#report_text#124(JET.JETAnalyzer, JET.nothing, Base.pairs(Core.NamedTuple()), #self#, text, filename)
││┌ @ avi-/JET/src/JET.jl:993 res = JET.virtual_process(text, filename, analyzer′, config)
│││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:301 res = JET._virtual_process!(x, filename, analyzer, config, context, JET.VirtualProcessResult(actual2virtual, context))
││││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:432 res = JET._virtual_process!(toplevelex, filename, analyzer, config, context, res)
│││││┌ @ avi-/JET/src/toplevel/virtualprocess.jl:637 JET.analyze_toplevel!(analyzer, src)
││││││┌ @ avi-/JET/src/JET.jl:1142 JET.#analyze_toplevel!#133(true, #self#, analyzer, src)
│││││││┌ @ avi-/JET/src/JET.jl:1160 JET.analyze_frame!(analyzer, frame)
││││││││┌ @ avi-/JET/src/JET.jl:747 JET.typeinf(analyzer, frame)
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 Core.Compiler.lastindex(fargs)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.lastindex), Nothing})): Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 fargs′ = Core.Compiler.getindex(fargs, Core.Compiler.:(3, Core.Compiler.lastindex(fargs)))
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Core.Compiler.UnitRange{Int64}})): fargs′ = Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, Core.Compiler.:(3, Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})::Int64)::Core.Compiler.UnitRange{Int64})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1244 Core.Compiler.getindex(fargs, 1)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Int64})): Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, 1)
│││││││││└───────────────────────────────────────────
...
```
aviatesk added a commit that referenced this pull request Oct 22, 2021
…#42746)

JET reported:
```julia
julia> report_package(JET)
...
[toplevel-info] analyzing from top-level definitions ... 671/671
═════ 12 possible errors found ═════
...
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 Core.Compiler.lastindex(fargs)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.lastindex), Nothing})): Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 fargs′ = Core.Compiler.getindex(fargs, Core.Compiler.:(3, Core.Compiler.lastindex(fargs)))
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Core.Compiler.UnitRange{Int64}})): fargs′ = Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, Core.Compiler.:(3, Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})::Int64)::Core.Compiler.UnitRange{Int64})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1244 Core.Compiler.getindex(fargs, 1)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Int64})): Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, 1)
│││││││││└───────────────────────────────────────────
...
```
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Feb 22, 2022
The PR JuliaLang#38905 only "back-propagates" conditional constraint
(from callee to caller), but currently we don't "forward" it
(caller to callee), and so inter-procedural constraint propagation
won't happen for e.g.:
```julia
ifelselike(cnd, x, y) = cnd ? x : y
@test Base.return_types((Any,Int,)) do x, y
    ifelselike(isa(x, Int), x, y)
end |> only == Int
```

This commit complements JuliaLang#38905 and enables further inter-procedural
conditional constraint propagation by forwarding `Conditional` to
callees when it imposes a constraint on any other argument,
during constant propagation.

We also improve constant-prop' heuristics in these ways:

- remove `const_prop_rettype_heuristic` since it handles rare cases,
  where const-prop' doens't seem to be worthwhile, e.g. it won't be
  so useful to try to propagate `Const(Tuple{DataType,DataType})` for
  `Const(convert)(::Const(Tuple{DataType,DataType}), ::Tuple{DataType,DataType} -> Tuple{DataType,DataType}`
- rename `is_allconst` to `is_all_overridden`
- also minor refactors and improvements added
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Feb 22, 2022
…t_invoke` (JuliaLang#42746)

JET reported:
```julia
julia> report_package(JET)
...
[toplevel-info] analyzing from top-level definitions ... 671/671
═════ 12 possible errors found ═════
...
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 Core.Compiler.lastindex(fargs)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.lastindex), Nothing})): Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 fargs′ = Core.Compiler.getindex(fargs, Core.Compiler.:(3, Core.Compiler.lastindex(fargs)))
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Core.Compiler.UnitRange{Int64}})): fargs′ = Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, Core.Compiler.:(3, Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})::Int64)::Core.Compiler.UnitRange{Int64})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1244 Core.Compiler.getindex(fargs, 1)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Int64})): Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, 1)
│││││││││└───────────────────────────────────────────
...
```
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Mar 8, 2022
The PR JuliaLang#38905 only "back-propagates" conditional constraint
(from callee to caller), but currently we don't "forward" it
(caller to callee), and so inter-procedural constraint propagation
won't happen for e.g.:
```julia
ifelselike(cnd, x, y) = cnd ? x : y
@test Base.return_types((Any,Int,)) do x, y
    ifelselike(isa(x, Int), x, y)
end |> only == Int
```

This commit complements JuliaLang#38905 and enables further inter-procedural
conditional constraint propagation by forwarding `Conditional` to
callees when it imposes a constraint on any other argument,
during constant propagation.

We also improve constant-prop' heuristics in these ways:

- remove `const_prop_rettype_heuristic` since it handles rare cases,
  where const-prop' doens't seem to be worthwhile, e.g. it won't be
  so useful to try to propagate `Const(Tuple{DataType,DataType})` for
  `Const(convert)(::Const(Tuple{DataType,DataType}), ::Tuple{DataType,DataType} -> Tuple{DataType,DataType}`
- rename `is_allconst` to `is_all_overridden`
- also minor refactors and improvements added
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Mar 8, 2022
…t_invoke` (JuliaLang#42746)

JET reported:
```julia
julia> report_package(JET)
...
[toplevel-info] analyzing from top-level definitions ... 671/671
═════ 12 possible errors found ═════
...
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 Core.Compiler.lastindex(fargs)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.lastindex), Nothing})): Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1243 fargs′ = Core.Compiler.getindex(fargs, Core.Compiler.:(3, Core.Compiler.lastindex(fargs)))
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Core.Compiler.UnitRange{Int64}})): fargs′ = Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, Core.Compiler.:(3, Core.Compiler.lastindex(fargs::Union{Nothing, Vector{Any}})::Int64)::Core.Compiler.UnitRange{Int64})
│││││││││└───────────────────────────────────────────
│││││││││┌ @ compiler/abstractinterpretation.jl:1244 Core.Compiler.getindex(fargs, 1)
││││││││││ for 1 of union split cases, no matching method found for call signatures (Tuple{typeof(Core.Compiler.getindex), Nothing, Int64})): Core.Compiler.getindex(fargs::Union{Nothing, Vector{Any}}, 1)
│││││││││└───────────────────────────────────────────
...
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler:inference Type inference
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

3 participants