Skip to content

inference: inter-procedural conditional constraint back-propagation#38905

Merged
vtjnash merged 3 commits intoJuliaLang:masterfrom
aviatesk:backprop2
Feb 26, 2021
Merged

inference: inter-procedural conditional constraint back-propagation#38905
vtjnash merged 3 commits intoJuliaLang:masterfrom
aviatesk:backprop2

Conversation

@aviatesk
Copy link
Copy Markdown
Member

@aviatesk aviatesk commented Dec 16, 2020

This PR propagates Conditionals 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.:

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 #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:

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

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.

EDIT: 3df027a 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.

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}]

@aviatesk aviatesk requested review from JeffBezanson, Keno and vtjnash and removed request for JeffBezanson, Keno and vtjnash December 16, 2020 11:41
@aviatesk aviatesk changed the title inference: inter-procedural conditional constraint back-propagation wip: inference: inter-procedural conditional constraint back-propagation Dec 16, 2020
@jpsamaroo
Copy link
Copy Markdown
Member

Slightly off-topic, but #37342 got accidentally linked for automatic closing.

Comment thread base/compiler/abstractinterpretation.jl Outdated
Comment thread base/compiler/typeinfer.jl Outdated
Comment thread base/compiler/typeinfer.jl Outdated
@aviatesk aviatesk changed the title wip: inference: inter-procedural conditional constraint back-propagation inference: inter-procedural conditional constraint back-propagation Dec 17, 2020
@aviatesk
Copy link
Copy Markdown
Member Author

All tests turned green. Ready for review.

Comment thread base/compiler/typelattice.jl Outdated
@KristofferC
Copy link
Copy Markdown
Member

Out of curiosity, any measurements regarding compile times? For example, building the sysimage, time to first plot etc.

Comment thread base/compiler/typelattice.jl Outdated
@aviatesk

This comment has been minimized.

@aviatesk

This comment has been minimized.

@aviatesk aviatesk force-pushed the backprop2 branch 2 times, most recently from 04655dc to b13fbcc Compare December 18, 2020 03:15
Comment thread base/compiler/tfuncs.jl Outdated
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)
Copy link
Copy Markdown
Member Author

@aviatesk aviatesk Dec 18, 2020

Choose a reason for hiding this comment

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

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.

Comment thread base/compiler/abstractinterpretation.jl Outdated
@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Dec 18, 2020

Okay, I addressed the review comments, and this is good to go, I'd say. Any further comments or reviews ?

@aviatesk aviatesk force-pushed the backprop2 branch 2 times, most recently from ef2ab51 to 889add5 Compare December 19, 2020 16:14
aviatesk added a commit to aviatesk/LoweredCodeUtils.jl that referenced this pull request Dec 21, 2020
- `@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!`
@aviatesk
Copy link
Copy Markdown
Member Author

aviatesk commented Feb 5, 2021

@vtjnash bump. I want to finish this PR and push forward another PRs like #39305 .

@nanosoldier
Copy link
Copy Markdown
Collaborator

Something went wrong when running your job:

ProcessExitedException(3)

cc @christopher-dG

@aviatesk
Copy link
Copy Markdown
Member Author

I rebased this PR to take in #39512, and I'm facing the following error when creating a system image.
It seems that some C code modified in the PR breaks the serialization (I confirmed I could build this PR successfully with reverting #39512 ).
@Keno @vtjnash do you have any idea to fix this ? I'm not so familiar with C code as of now.

Stdlibs: ────  32.658716 seconds 54.2971%

signal (11): Segmentation fault: 11
in expression starting at none:0
jl_serialize_value_ at /Users/aviatesk/julia/julia/src/staticdata.c:414
jl_save_system_image_to_stream at /Users/aviatesk/julia/julia/src/staticdata.c:1538
jl_save_system_image at /Users/aviatesk/julia/julia/src/staticdata.c:1653
jl_write_compiler_output at /Users/aviatesk/julia/julia/src/precompile.c:81
jl_atexit_hook at /Users/aviatesk/julia/julia/src/init.c:211
repl_entrypoint at /Users/aviatesk/julia/julia/src/jlapi.c:703
Allocations: 113758935 (Pool: 113726722; Big: 32213); GC: 149

@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 17, 2021

@aviatesk
Copy link
Copy Markdown
Member Author

Woa that's just my mistake. Thanks for pointing out !

@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 18, 2021

Let's see if it is alive: @nanosoldier runbenchmarks(ALL, vs = ":master")

@aviatesk
Copy link
Copy Markdown
Member Author

@nanosoldier runbenchmarks(ALL, vs = ":master")

1 similar comment
@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 22, 2021

@nanosoldier runbenchmarks(ALL, vs = ":master")

@nanosoldier
Copy link
Copy Markdown
Collaborator

Something went wrong when running your job:

ProcessExitedException(5)

cc @christopher-dG

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)
@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 25, 2021

@nanosoldier runbenchmarks(ALL, vs = ":master")

@nanosoldier
Copy link
Copy Markdown
Collaborator

Your benchmark job has completed - possible performance regressions were detected. A full report can be found here. cc @christopher-dG

@Keno
Copy link
Copy Markdown
Member

Keno commented Feb 26, 2021

Looks good

@aviatesk
Copy link
Copy Markdown
Member Author

To me there seems to be regressions in sort! benchmarks ?
(this is the first time for me to look at an nanosoldier benchmark result and so I'm not sure if "40% regression" is something we can allow to happen, though)

@Keno
Copy link
Copy Markdown
Member

Keno commented Feb 26, 2021

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.

@vtjnash
Copy link
Copy Markdown
Member

vtjnash commented Feb 26, 2021

I've noticed that test can get into some strange bi-stable modes. As long as all of sort! tests in a group aren't showing a trend, it is probably nothing.

LGTM

@aviatesk
Copy link
Copy Markdown
Member Author

I'm very happy we can merge this at last ! I really appreciate your help @vtjnash and @Keno .

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.

Type check in callee does not propagate to caller

7 participants