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

Recursion disables constant propagation #39915

Closed
bramtayl opened this issue Mar 4, 2021 · 5 comments · Fixed by #40561
Closed

Recursion disables constant propagation #39915

bramtayl opened this issue Mar 4, 2021 · 5 comments · Fixed by #40561

Comments

@bramtayl
Copy link
Contributor

bramtayl commented Mar 4, 2021

So, this is a very annoying problem, and one that people don't seem to really know about. It's best demonstrated by example:

using Base: tail

function my_getindex(a_tuple, which_ones)
    rest = my_getindex(tail(a_tuple), tail(which_ones))
    if first(which_ones)
        (first(a_tuple), rest...)
    else
        rest
    end
end

function my_getindex(a_tuple::Tuple{}, which_ones::Tuple{})
    ()
end

function constant_select(a_tuple)
    my_getindex(a_tuple, (true, false, true, false))
end

@code_warntype constant_select((1, 1.0, "a", :a))
# Body::Tuple{Int64,Vararg{Any,N} where N}

My naive understanding of what's going on is that when Julia recurs into my_getindex, the compiler detects that which_ones is still a tuple of Bools (just a smaller one), figures out that we are recurring, and bails on constant propagation.

I've always gotten the impression that this is an unfixable problem, but...if it's fixable, that would be super cool.

@simeonschaub
Copy link
Member

simeonschaub commented Mar 4, 2021

This looks odd to me:

julia> @code_typed constant_select((1, 1.0, "a", :a))
CodeInfo(
1%1  = Core.getfield(a_tuple, 3)::String%2  = Core.getfield(a_tuple, 4)::Symbol
└──       goto #3 if not false
2%4  = Core.tuple(%2)::Tuple{Symbol}
└──       goto #4
3 ─       goto #4
4%7  = φ (#2 => %4, #3 => ())::Union{Tuple{}, Tuple{Symbol}}
└──       goto #6 if not true
5%9  = Core.tuple(%1)::Tuple{String}%10 = Core._apply_iterate(Base.iterate, Core.tuple, %9, %7)::Union{Tuple{String}, Tuple{String, Symbol}}
└──       goto #7
6 ─       goto #7
7%13 = φ (#5 => %10, #6 => %7)::Tuple
└──       goto #8
8%15 = Base.getfield(a_tuple, 1, true)::Int64%16 = Core.tuple(%15)::Tuple{Int64}%17 = Core._apply_iterate(Base.iterate, Core.tuple, %16, %13)::Tuple{Int64, Vararg{Any}}
└──       goto #9
9return %17
) => Tuple{Int64, Vararg{Any}}

Shouldn't we be able to just eliminate block #2 here and therefore also avoid the type instability due to the phi node in line 7? (Same for line 13)

@Keno
Copy link
Member

Keno commented Mar 5, 2021

Well, fixing it is easy, you just need to delete the edgecycle check here: https://github.com/JuliaLang/julia/blob/master/base/compiler/abstractinterpretation.jl#L453. The problem is that the check guards against runaway inference (#36148). Regular inference is slightly more forgiving and uses a recursion heuristic defined here: https://github.com/JuliaLang/julia/blob/master/base/compiler/typelimits.jl#L186 to try to prove termination (which worked in this case).

That said, I'm thinking we could maybe improve the condition there to not be quite as strict. Let me play with it.

@Keno
Copy link
Member

Keno commented Mar 5, 2021

Shouldn't we be able to just eliminate block #2 here and therefore also avoid the type instability due to the phi node in line 7? (Same for line 13)

Inlining can often discover information that inference doesn't have access to, particularly in cases involving recursion, because we aggressively limit inference's exploration to avoid blowing up compile times. To investigate issues like this, one needs to look at unoptimized IR. In the near future, Cthulhu will display inference remarks to tell the user why it bailed. In this case it would have said: [constprop] Edge cycle encountered (https://github.com/JuliaLang/julia/blob/master/base/compiler/abstractinterpretation.jl#L460).

Keno added a commit that referenced this issue Mar 5, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes #39915
Keno added a commit that referenced this issue Mar 5, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes #39915
@Keno
Copy link
Member

Keno commented Mar 5, 2021

#39918

aviatesk added a commit to aviatesk/julia that referenced this issue Apr 22, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-Authored-By: Keno Fisher <keno@juliacomputing.com>
aviatesk added a commit to aviatesk/julia that referenced this issue Apr 24, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-Authored-By: Keno Fisher <keno@juliacomputing.com>
aviatesk added a commit to aviatesk/julia that referenced this issue Apr 27, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-Authored-By: Keno Fisher <keno@juliacomputing.com>
aviatesk added a commit to aviatesk/julia that referenced this issue May 6, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-Authored-By: Keno Fisher <keno@juliacomputing.com>
vtjnash pushed a commit that referenced this issue May 26, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes #39915, replaces #39918

Co-authored-by: Keno Fisher <keno@juliacomputing.com>
@bramtayl
Copy link
Contributor Author

Woohoo!

shirodkara pushed a commit to shirodkara/julia that referenced this issue Jun 9, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-authored-by: Keno Fisher <keno@juliacomputing.com>
johanmon pushed a commit to johanmon/julia that referenced this issue Jul 5, 2021
At the moment, we restrict const prop whenever we see a cycle in
methods being called. However, I think this condition can be relaxed
slightly: In particular, if the type complexity limiting did not
decide to limit the growth of the type in question, I think it
should be fine to constant prop as long as there is no cycle in
*method instances* (rather than just methods).

Fixes JuliaLang#39915, replaces JuliaLang#39918

Co-authored-by: Keno Fisher <keno@juliacomputing.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
3 participants