Optimizer: Re-use CFG from type inference#50924
Merged
Keno merged 3 commits intoJuliaLang:masterfrom Aug 18, 2023
Merged
Conversation
Member
|
Potentially we could call adopt_thread on these threads but I would hold off on that until we figure some of the weird behaviour around them. |
vchuravy
reviewed
Aug 15, 2023
72e319c to
5c0b04a
Compare
2 tasks
Keno
reviewed
Aug 16, 2023
Keno
reviewed
Aug 16, 2023
Keno
approved these changes
Aug 16, 2023
This change will allow us to re-use Inference-collected information at
the basic block level, such as the `bb_vartables`.
There were a couple of spots where the `unreachable` insertion pass at
IRCode conversion (i.e. optimizer entry) was ignoring statically
divergent code that inference had discovered:
- `%x = SlotNumber(3)` can throw and cause the following statements to
be statically unreachable
- `goto #b if not %cond` can be statically throwing if %cond is known
to never be Bool (or to always throw during its own evaluation)
CFG re-computation was hiding these bugs by flowing through the
"Core.Const(...)"-wrapped statements that would follow, inserting
unnecessary but harmless extra branches in the CFG.
These checks are important to make sure that `verify_ir` does not end up triggering out-of-bounds errors as it checks IR. It also fills out some of the verification: - Confirms that cfg.index is correct - Confirms that cfg.blocks[i].stmts cover the complete IR
For some reason the recent CFG change caused us to generate:
```
1-element Vector{Any}:
CodeInfo(
1 ─ nothing::Nothing
└── return true
) => Bool
```
instead of
```
1-element Vector{Any}:
CodeInfo(
1 ─ return true
) => Bool
```
but I believe this difference is harmless.
5c0b04a to
ce6b332
Compare
aviatesk
reviewed
Aug 19, 2023
Member
aviatesk
left a comment
There was a problem hiding this comment.
Looks very nice. Sorry for comments after merge, but we can address them later anyway.
| # either because we are the outermost code, or we might use this later | ||
| doopt = (me.cached || me.parent !== nothing) | ||
| recompute_cfg = type_annotate!(interp, me, doopt) | ||
| type_annotate!(interp, me, doopt) |
Member
There was a problem hiding this comment.
We can eliminate anything related to any_unreachable within type_annotate! now.
| prevloc = codeloc | ||
| end | ||
| if code[idx] isa Expr && ssavaluetypes[idx] === Union{} | ||
| if ssavaluetypes[idx] === Union{} && !(code[idx] isa Core.Const) |
Member
There was a problem hiding this comment.
Maybe we want to set up a special and explicit marker type instead of Const to indicate a statement is known to be unreachable, e.g.
struct Unreachable
stmt
Unreachable(@nospecialize stmt) = new(stmt)
end
aviatesk
added a commit
that referenced
this pull request
Aug 25, 2023
topolarity
added a commit
to topolarity/julia
that referenced
this pull request
Feb 28, 2024
This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements when re-building the CFG during IRCode conversion. This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and observe a control-flow edge that never should have existed, such as an edge into a catch block. Such an edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. We should follow-up with a tweak to `compute_basic_blocks` to enforce this requirement.
topolarity
added a commit
to topolarity/julia
that referenced
this pull request
Feb 29, 2024
This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements when re-building the CFG during IRCode conversion. This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and observe a control-flow edge that never should have existed, such as an edge into a catch block. Such an edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. We should follow-up with a tweak to `compute_basic_blocks` to enforce this requirement.
topolarity
added a commit
to topolarity/julia
that referenced
this pull request
Feb 29, 2024
This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements when re-building the CFG during IRCode conversion. This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and observe a control-flow edge that never should have existed, such as an edge into a catch block. Such an edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. We should follow-up with a tweak to `compute_basic_blocks` to enforce this requirement.
topolarity
added a commit
to topolarity/julia
that referenced
this pull request
Mar 7, 2024
This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements when re-building the CFG during IRCode conversion. This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and observe a control-flow edge that never should have existed, such as an edge into a catch block. Such an edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. We should follow-up with a tweak to `compute_basic_blocks` to enforce this requirement. The test added here is very brittle, but it's better than nothing until we have utilities to provide hand-written (pre-optimizer) IR and pass it through part of our pipeline.
topolarity
added a commit
to topolarity/julia
that referenced
this pull request
Mar 7, 2024
This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements when re-building the CFG during IRCode conversion. This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and observe a control-flow edge that never should have existed, such as an edge into a catch block. Such an edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. We should follow-up with a tweak to `compute_basic_blocks` to enforce this requirement. The test added here is very brittle, but it's better than nothing until we have utilities to provide hand-written (pre-optimizer) IR and pass it through part of our pipeline.
topolarity
added a commit
that referenced
this pull request
Mar 7, 2024
This is a partial back-port of #50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and end up observing a control-flow edge that never existed. If the spurious edge is to a catch block, then the edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. Resolves part of #53366.
Drvi
pushed a commit
to RelationalAI/julia
that referenced
this pull request
Mar 8, 2024
…53512) This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and end up observing a control-flow edge that never existed. If the spurious edge is to a catch block, then the edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. Resolves part of JuliaLang#53366. (cherry picked from commit 035d17a)
nickrobinson251
pushed a commit
to RelationalAI/julia
that referenced
this pull request
Feb 26, 2025
…53512) This is a partial back-port of JuliaLang#50924, where we discovered that the optimizer would ignore: 1. must-throw `%XX = SlotNumber(_)` statements 2. must-throw `goto #bb if not %x` statements This is mostly harmless, except that in the case of (1) we can accidentally fall through the statically deleted (`Const()`-wrapped) code from inference and end up observing a control-flow edge that never existed. If the spurious edge is to a catch block, then the edge is invalid semantically and breaks our SSA conversion. This one-line change fixes (1) but not (2), which is enough for IR validity. Resolves part of JuliaLang#53366. (cherry picked from commit 035d17a)
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
6 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.
This change will allow us to re-use Inference-collected information at the basic block level, such as the
bb_vartables.There were a couple of spots where the
unreachableinsertion pass at IRCode conversion (i.e. optimizer entry) was ignoring statically divergent code that inference had discovered:%x = SlotNumber(3)can throw and cause the following statements to be statically unreachablegoto #b if not %condcan be statically throwing if %cond is known to never be Bool (or to always throw during its own evaluation)CFG re-computation was hiding these bugs by flowing through the "Core.Const(...)"-wrapped statements that would follow, inserting unnecessary but harmless extra branches in the CFG.