inference: inter-procedural conditional constraint back-propagation#38905
inference: inter-procedural conditional constraint back-propagation#38905vtjnash merged 3 commits intoJuliaLang:masterfrom
Conversation
|
Slightly off-topic, but #37342 got accidentally linked for automatic closing. |
|
All tests turned green. Ready for review. |
|
Out of curiosity, any measurements regarding compile times? For example, building the sysimage, time to first plot etc. |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
04655dc to
b13fbcc
Compare
| return Const(Union{}) | ||
| end | ||
| rt = abstract_call(interp, nothing, argtypes_vec, sv, -1).rt | ||
| rt = widenconditional(abstract_call(interp, nothing, argtypes_vec, sv, -1).rt) |
There was a problem hiding this comment.
Now this change isn't necessary for this PR to work (abstract_call no longer returns InterConditional), but I think widenconditional is better here since it may produce more accurate result since it can be widen to Const, so let me include this as is.
|
Okay, I addressed the review comments, and this is good to go, I'd say. Any further comments or reviews ? |
ef2ab51 to
889add5
Compare
- `@isssa`/`@isslotnum` hacks circumvent JuliaLang/julia#37342 and gets rid of type assertions and accompanying inference overheads (they are really, really minor and negligible though) NOTE: well, we won't need them once JuliaLang/julia#38905 gets merged - improve inferrability around `pcexec` within `selective_eval!`
|
Something went wrong when running your job: |
|
I rebased this PR to take in #39512, and I'm facing the following error when creating a system image. |
|
Woa that's just my mistake. Thanks for pointing out ! |
|
Let's see if it is alive: @nanosoldier |
|
@nanosoldier |
1 similar comment
|
@nanosoldier |
|
Something went wrong when running your job: |
This PR propagates `Conditional`s inter-procedurally when a `Conditional` at return site imposes a constraint on the call arguments. When inference exits local frame and the return type is annotated as `Conditional`, it will be converted into `InterConditional` object, which is implemented in `Core` and can be directly put into the global cache. Finally after going back to caller frame, `InterConditional` will be re-converted into `Conditional` in the context of the caller frame. ## improvements So now some simple "is-wrapper" functions will propagate its constraint as expected, e.g.: ```julia isaint(a) = isa(a, Int) @test Base.return_types((Any,)) do a isaint(a) && return a # a::Int return 0 end == Any[Int] isaint2(::Any) = false isaint2(::Int) = true @test Base.return_types((Any,)) do a isaint2(a) && return a # a::Int return 0 end == Any[Int] function isa_int_or_float64(a) isa(a, Int) && return true isa(a, Float64) && return true return false end @test Base.return_types((Any,)) do a isa_int_or_float64(a) && return a # a::Union{Float64,Int} 0 end == Any[Union{Float64,Int}] ``` (and now we don't need something like JuliaLang#38636) ## benchmarks A compile time comparison: > on the current master (82d79ce) ``` Sysimage built. Summary: Total ─────── 55.295376 seconds Base: ─────── 23.359226 seconds 42.2444% Stdlibs: ──── 31.934773 seconds 57.7531% JULIA usr/lib/julia/sys-o.a Generating REPL precompile statements... 29/29 Executing precompile statements... 1283/1283 Precompilation complete. Summary: Total ─────── 91.129162 seconds Generation ── 68.800937 seconds 75.4983% Execution ─── 22.328225 seconds 24.5017% LINK usr/lib/julia/sys.dylib ``` > on this PR (37e279b) ``` Sysimage built. Summary: Total ─────── 51.694730 seconds Base: ─────── 21.943914 seconds 42.449% Stdlibs: ──── 29.748987 seconds 57.5474% JULIA usr/lib/julia/sys-o.a Generating REPL precompile statements... 29/29 Executing precompile statements... 1357/1357 Precompilation complete. Summary: Total ─────── 88.956226 seconds Generation ── 67.077710 seconds 75.4053% Execution ─── 21.878515 seconds 24.5947% LINK usr/lib/julia/sys.dylib ``` Here is a sample code that benefits from this PR: ```julia function summer(ary) r = 0 for a in ary if ispositive(a) r += a end end r end ispositive(a) = isa(a, Int) && a > 0 ary = Any[] for _ in 1:100_000 if rand(Bool) push!(ary, rand(-100:100)) elseif rand(Bool) push!(ary, rand('a':'z')) else push!(ary, nothing) end end using BenchmarkTools @Btime summer($(ary)) ``` > on the current master (82d79ce) ``` ❯ julia summer.jl 1.214 ms (24923 allocations: 389.42 KiB) ``` > on this PR (37e279b) ``` ❯ julia summer.jl 421.223 μs (0 allocations: 0 bytes) ``` ## caveats Within the `Conditional`/`InterConditional` framework, only a single constraint can be back-propagated inter-procedurally. This PR implements a naive heuristic to "pick up" a constraint to be propagated when a return type is a boolean. The heuristic may fail to select an "interesting" constraint in some cases. For example, we may expect `::Expr` constraint to be imposed on the first argument of `Meta.isexpr`, but the current heuristic ends up picking up a constraint on the second argument (i.e. `ex.head === head`). ```julia isexpr(@nospecialize(ex), head::Symbol) = isa(ex, Expr) && ex.head === head @test_broken Base.return_types((Any,)) do x Meta.isexpr(x, :call) && return x # x::Expr, ideally return nothing end == Any[Union{Nothing,Expr}] ``` I think We can get rid of this limitation by extending `Conditional` and `InterConditional` so that they can convey multiple constraints, but I'd like to leave this as a future work. --- - closes JuliaLang#38636 - closes JuliaLang#37342
- within a callee (i.e. `typeinf_local`), we widen conditional return
type if it doesn't refine input argument type (for better cache)
- within a caller (i.e. `abstract_call_gf_by_type`), we re-form a
conditional if needed, which allows us to choose a propagation target
more appropriately
this commit implements the "pick up" logic within a caller
(i.e. within `abstract_call_gf_by_type`), which allows us to choose a
constraint more appropriately, and now the `Meta.isexpr` case is fixed.
Still there is a limitation of multiple conditional constraint
back-propagation; the following broken test case will explain the future
work.
```julia
is_int_and_int(a, b) = isa(a, Int) && isa(b, Int)
@test_broken Base.return_types((Any,Any)) do a, b
is_int_and_int(a, b) && return a, b # (a::Int, b::Int) ideally, but (a::Any, b::Int)
0, 0
end == Any[Tuple{Int,Int}]
```
note that the changes for `isnothing` and `ismissing` aren't necessary, but they reduce the number of method definitions for good reason; the less the number of methods they have, the better we can back-propagate type constraints, because even after a package defines their own new methods for them we can keep to use our `InterConditional` logic as far as far as the number of methods is [≤3](https://github.com/JuliaLang/julia/blob/5c6e21edbfd8f0c7d16ea01c91d1c75c30d4eaa1/base/compiler/types.jl#L119)
|
@nanosoldier |
|
Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @christopher-dG |
|
Looks good |
|
To me there seems to be regressions in |
|
It's running on a new machine that hasn't been fully tuned yet, so as long as there's nothing egregious (which I didn't see) it should be fine. |
|
I've noticed that test can get into some strange bi-stable modes. As long as all of LGTM |
This PR propagates
Conditionals inter-procedurally when aConditionalat return site imposes a constraint on the call arguments.When inference exits local frame and the return type is annotated as
Conditional, it will be converted intoInterConditionalobject,which is implemented in
Coreand can be directly put into the globalcache. Finally after going back to caller frame,
InterConditionalwillbe re-converted into
Conditionalin the context of the caller frame.improvements
So now some simple "is-wrapper" functions will propagate its constraint
as expected, e.g.:
(and now we don't need something like #38636)
benchmarks
A compile time comparison:
Here is a sample code that benefits from this PR:
caveats
Within the
Conditional/InterConditionalframework, only a singleconstraint can be back-propagated inter-procedurally. This PR implements
a naive heuristic to "pick up" a constraint to be propagated when a
return type is a boolean. The heuristic may fail to select an
"interesting" constraint in some cases. For example, we may expect
::Exprconstraint to be imposed on the first argument ofMeta.isexpr, but the current heuristic ends up picking up a constrainton the second argument (i.e.
ex.head === head).I think We can get rid of this limitation by extending
ConditionalandInterConditionalso that they can convey multiple constraints, but I'd like to leave this
as a future work.
EDIT: 3df027a implements the "pick up" logic within a caller
(i.e. within
abstract_call_gf_by_type), which allows us to choose aconstraint more appropriately, and now the
Meta.isexprcase is fixed.Still there is a limitation of multiple conditional constraint
back-propagation; the following broken test case will explain the future
work.
findall(::Union{AbstractString,AbstractPattern}, ::AbstractString)#38636