Skip to content

inference: forward Conditional inter-procedurally#42529

Merged
vtjnash merged 4 commits intomasterfrom
avi/forwardconditional
Oct 21, 2021
Merged

inference: forward Conditional inter-procedurally#42529
vtjnash merged 4 commits intomasterfrom
avi/forwardconditional

Conversation

@aviatesk
Copy link
Copy Markdown
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.

@aviatesk aviatesk mentioned this pull request Oct 7, 2021
Merged
@aviatesk aviatesk requested a review from vtjnash October 7, 2021 13:17
@aviatesk aviatesk added the compiler:inference Type inference label Oct 7, 2021
c42f
c42f reviewed Oct 8, 2021
View reviewed changes
Copy link
Copy Markdown
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.

@aviatesk aviatesk force-pushed the avi/forwardconditional branch 5 times, most recently from 4d598c7 to 06f196a Compare October 12, 2021 14:28
aviatesk
aviatesk commented Oct 12, 2021
View reviewed changes
@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Oct 12, 2021

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 aviatesk force-pushed the avi/forwardconditional branch from 018e46d to ac5d042 Compare October 20, 2021 07:01
aviatesk
aviatesk commented Oct 20, 2021
View reviewed changes
@aviatesk aviatesk force-pushed the avi/forwardconditional branch from ac5d042 to e9aaea2 Compare October 20, 2021 09:16
@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Oct 20, 2021

@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.

vtjnash
vtjnash requested changes Oct 20, 2021
View reviewed changes
base/compiler/inferenceresult.jl Outdated
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
Copy Markdown
Member

@vtjnash vtjnash Oct 20, 2021

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
Copy Markdown
Member Author

@aviatesk aviatesk Oct 21, 2021 •
edited
Loading

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
@aviatesk
inference: forward Conditional inter-procedurally
a955380 
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.
@aviatesk
inference: improve constant-prop' heuristics
a2fe0ef 
- 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 @vtjnash
Apply suggestions from code review
4ef88d2 
Co-authored-by: Jameson Nash <vtjnash@gmail.com>
@aviatesk aviatesk force-pushed the avi/forwardconditional branch 3 times, most recently from 701a2a1 to 28f50c6 Compare October 21, 2021 11:28
@aviatesk aviatesk force-pushed the avi/forwardconditional branch from 28f50c6 to c641d85 Compare October 21, 2021 11:35
@aviatesk aviatesk requested a review from vtjnash October 21, 2021 15:50
@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
update to JuliaLang/julia#42529
8b099e0
aviatesk added a commit that referenced this pull request Oct 21, 2021
@aviatesk
inference: follow up #42529, handle an edge case in abstract_invoke
b776be4 
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
@aviatesk
inference: follow up #42529, handle an edge case in abstract_invoke
db93f25 
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
@aviatesk
inference: follow up #42529, handle an edge case in abstract_invoke (…
8168daf 
…#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)
│││││││││└───────────────────────────────────────────
...
```
This was referenced Dec 17, 2021
Closed
Closed
LilithHafner pushed a commit to LilithHafner/julia that referenced this pull request Feb 22, 2022
@aviatesk @LilithHafner
inference: forward Conditional inter-procedurally (JuliaLang#42529)
4688307 
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
@aviatesk @LilithHafner
inference: follow up JuliaLang#42529, handle an edge case in `abstrac…
69389ef 
…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
@aviatesk @LilithHafner
inference: forward Conditional inter-procedurally (JuliaLang#42529)
06b55e1 
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
@aviatesk @LilithHafner
inference: follow up JuliaLang#42529, handle an edge case in `abstrac…
ef1b776 
…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

Reviewers

@c42f c42f c42f left review comments

@vtjnash vtjnash vtjnash approved these changes

Assignees

No one assigned

Labels

compiler:inference Type inference

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@aviatesk @vtjnash @c42f