irinterp: Consider cfg information from discovered errors#49692
Merged
irinterp: Consider cfg information from discovered errors#49692
Conversation
aviatesk
reviewed
May 9, 2023
Member
aviatesk
left a comment
There was a problem hiding this comment.
I wrote these test cases
Base.@assume_effects :foldable Base.@constprop :aggressive function kill_error_edge(b1, b2, xs, x)
y = b1 ? "julia" : xs[]
if b2
a = length(y)
else
a = sin(y)
end
a + x
end
Base.@assume_effects :foldable Base.@constprop :aggressive function kill_error_edge(b1, b2, xs, ys, x)
y = b1 ? xs[] : ys[]
if b2
a = length(y)
else
a = sin(y)
end
a + x
end
let src = code_typed1((Bool,Base.RefValue{Any},Int,)) do b2, xs, x
kill_error_edge(true, b2, xs, x)
end
@test count(@nospecialize(x)->isa(x, Core.PhiNode), src.code) == 0
end
let src = code_typed1((Bool,Base.RefValue{String}, Base.RefValue{Any},Int,)) do b2, xs, ys, x
kill_error_edge(true, b2, xs, ys, x)
end
@test count(@nospecialize(x)->isa(x, Core.PhiNode), src.code) == 0
endand I confirmed that the first case is optimized as expected, while the second case is not optimized away:
julia> code_typed((Bool,Base.RefValue{Any},Int,)) do b2, xs, x
kill_error_edge(true, b2, xs, x)
end
1-element Vector{Any}:
CodeInfo(
1 ─ nothing::Nothing
└── goto #3
2 ─ nothing::Nothing
3 ┄ goto #5 if not b2
4 ─ goto #6
5 ─ Main.sin("julia")::Union{}
6 ┄ %7 = (5 + x)::Int64
└── goto #7
7 ─ return %7
) => Int64
julia> code_typed((Bool,Base.RefValue{String}, Base.RefValue{Any},Int,)) do b2, xs, ys, x
kill_error_edge(true, b2, xs, ys, x)
end
1-element Vector{Any}:
CodeInfo(
1 ─ nothing::Nothing
│ %2 = Base.getfield(xs, :x)::String
└── goto #3
2 ─ nothing::Nothing
3 ┄ goto #5 if not b2
4 ─ %6 = Main.length(%2)::Int64
└── goto #6
5 ─ %8 = Main.sin(%2)::Union{}
6 ┄ %9 = φ (#4 => %6, #5 => %8)::Int64
│ %10 = (%9 + x)::Int64
└── goto #7
7 ─ return %10
) => Int64
Member
|
I found applying this diff allows the second case to be optimized as well, but I am not sure this is the right fix: diff --git a/base/compiler/ssair/irinterp.jl b/base/compiler/ssair/irinterp.jl
index 7ca3f5352e..7e08c1acf1 100644
--- a/base/compiler/ssair/irinterp.jl
+++ b/base/compiler/ssair/irinterp.jl
@@ -259,12 +259,16 @@ function _ir_abstract_constant_propagation(interp::AbstractInterpreter, irsv::IR
push!(ssa_refined, idx)
end
end
+ if did_reprocess
+ inst = ir.stmts[idx][:inst]
+ typ = ir.stmts[idx][:type]
+ end
if idx == lstmt
# N.B.: Inst could have been updated by reprocess_instruction!
- if did_reprocess
- inst = ir.stmts[idx][:inst]
- end
process_terminator!(ir, inst, idx, bb, all_rets, bb_ip) && @goto residual_scan
+ if typ === Bottom && !(isa(inst, GotoIfNot) || isa(inst, GotoNode))
+ kill_edge!(ir, bb, bb+1, update_phi!(irsv))
+ end
elseif typ === Bottom && !isa(inst, PhiNode)
kill_terminator_edges!(irsv, lstmt, bb)
break |
If we infer a call to `Union{}`, we can terminate further abstract
interpretation. However, this of course also means that we can
make use of that information to refine the types of any phis
that may have originated from the basic block containing the
call that was refined to `Union{}`.
Member
Author
|
Thanks for the test cases. I've incorporated a version of your suggested fix. |
aviatesk
approved these changes
May 10, 2023
Keno
added a commit
that referenced
this pull request
May 11, 2023
I moved around some code in #49692 that broadened the replacement of statements by their const results. This is fine for how we're currently using irinterp in base, because we're requiring some fairly strong effects, but some downstream pipelines (and potentially Base in the future) want to use irinterp on code with arbitrary effects, so put in an appropriate check.
Keno
added a commit
that referenced
this pull request
May 11, 2023
…#49750) I moved around some code in #49692 that broadened the replacement of statements by their const results. This is fine for how we're currently using irinterp in base, because we're requiring some fairly strong effects, but some downstream pipelines (and potentially Base in the future) want to use irinterp on code with arbitrary effects, so put in an appropriate check.
aviatesk
added a commit
that referenced
this pull request
May 11, 2023
aviatesk
added a commit
that referenced
this pull request
May 11, 2023
Keno
added a commit
that referenced
this pull request
May 12, 2023
This is yet another followup to #49692 and #49750. With the introduced change, we kill the CFG edge from the basic block with the discovered error to its successors. However, we have an invariant in the verifier that the CFG should always match the IR. Turns out this is for good reason, as we assume in a number of places (including, ironically in the irinterp) that a GotoNode/GotoIfNot terminator means that the BB has the corresponding number of successors in the IR. Fix all this by killing the rest of the basic block when we discover that it is unreachable and if possible introducing an unreachable node at the end. However, of course if the erroring statement is the fallthrough terminator itself, there is no space for an unreachable node. We fix this by tweaking the verification to allow this case, as its really no worse than the other problems with fall-through terminators (#41476), but of course it would be good to address that as part of a more general IR refactor.
Keno
added a commit
that referenced
this pull request
May 13, 2023
This is yet another followup to #49692 and #49750. With the introduced change, we kill the CFG edge from the basic block with the discovered error to its successors. However, we have an invariant in the verifier that the CFG should always match the IR. Turns out this is for good reason, as we assume in a number of places (including, ironically in the irinterp) that a GotoNode/GotoIfNot terminator means that the BB has the corresponding number of successors in the IR. Fix all this by killing the rest of the basic block when we discover that it is unreachable and if possible introducing an unreachable node at the end. However, of course if the erroring statement is the fallthrough terminator itself, there is no space for an unreachable node. We fix this by tweaking the verification to allow this case, as its really no worse than the other problems with fall-through terminators (#41476), but of course it would be good to address that as part of a more general IR refactor.
Keno
added a commit
that referenced
this pull request
May 14, 2023
If a fall-through terminator was already Bottom, we should not attempt to rekill the successor edge, because it was already deleted. Yet another fix in the #49692, #49750, #49797 series, which is turning out to be quite a rabit hole. Also fix a typo in the verifer tweak where we were looking at the BB idx rather than the terminator idx.
Keno
added a commit
that referenced
this pull request
May 15, 2023
If a fall-through terminator was already Bottom, we should not attempt to rekill the successor edge, because it was already deleted. Yet another fix in the #49692, #49750, #49797 series, which is turning out to be quite a rabit hole. Also fix a typo in the verifer tweak where we were looking at the BB idx rather than the terminator idx.
Keno
added a commit
that referenced
this pull request
Jun 27, 2023
This addresses an existing TODO to terminate irinterp on discovering a :throw_undef_if_not that is dead. The underlying infrastructure to do this was added in #49692, so this just needed to be wired up properly.
Keno
added a commit
that referenced
this pull request
Jun 27, 2023
This addresses an existing TODO to terminate irinterp on discovering a :throw_undef_if_not that is dead. The underlying infrastructure to do this was added in #49692, so this just needed to be wired up properly.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
If we infer a call to
Union{}, we can terminate further abstract interpretation. However, this of course also means that we can make use of that information to refine the types of any phis that may have originated from the basic block containing the call that was refined toUnion{}.