https://github.com/JuliaLang/julia
Revision 396abe4fdc8615e162462910bfc16729be7c95ed authored by Keno Fischer on 13 April 2024, 03:16:52 UTC, committed by GitHub on 13 April 2024, 03:16:52 UTC
This is a bit of a tricky one. What happens here is that
IncrementalCompact finds that one branch of an if/else is dead, so one
of the incoming values of the PhiNode goes away. This may have the
effect of narrowing the type of the PhiNode (if the branches have
different types). In the latest iteration of our compiler, such
situations need to be annotated with IR_FLAG_REFINED or `Refined()`,
otherwise irinterp will skip them on revisit.

In theory, the fix is quite simple: Check whether the type is being
refined and if so, set the flag. However, this code sits inside
IncrementalCompcat, which currently neither performs lattice operations
nor sets any Refined flags by itself. The three possible options here
are:

1. Thread lattice through IncrementalCompact.
2. Use an egal check inside IncrementalCompact rather than the proper
lattice query. This is legal, but may overapproximate the need for
`Refined`, thus causing unnecessary work later.
3. Move the phi node narrowing outside of IncrementalCompact.

This PR takes a hybrid approach of 2 and 3. Approach 1 is undesirable,
because we do not want to recompile all of IncrementalCompact for every
lattice, just for this one query. I almost took approach 2, but it is
unsatisfying, because of the imprecision, which could cuase a lot of
extra work in pathological cases.

The primary downside of approach 3 is that now every pass that performs
IncrementalCompact with CFG manipulation enabled will need to call the
`reprocess_phi_node!` helper. We have two of these in base (adce_pass!
and `compact!(..., true)` although only the former as access to a
lattice.

The compromise I came up with here is to do the egality check, except
leaving the PhiNode in place when it fails rather than setting `Refined`
internally. I think this is ok. There's a bit of an issue with duplicate
work, because the first thing that the lattice check will do is check
for equality, but that only happens in the case where a refinement
actually is required, which is both rarer and profitable.

Finally, I'm pretty sure I've found this issue before, but I cannot find
any writeup on it, so if somebody remembers me writing it up somewhere,
please let me know so I can add appropriate cross references.

---------

Co-authored-by: Shuhei Kadowaki <40514306+aviatesk@users.noreply.github.com>
1 parent d47cbf6
History
Tip revision: 396abe4fdc8615e162462910bfc16729be7c95ed authored by Keno Fischer on 13 April 2024, 03:16:52 UTC
ir: Set refined when narrowing PhiNode in IncrementalCompact (#54061)
Tip revision: 396abe4
File Mode Size
.devcontainer
.github
base
cli
contrib
deps
doc
etc
src
stdlib
test
.buildkite-external-version -rw-r--r-- 5 bytes
.clang-format -rw-r--r-- 3.3 KB
.clangd -rw-r--r-- 114 bytes
.codecov.yml -rw-r--r-- 52 bytes
.git-blame-ignore-revs -rw-r--r-- 371 bytes
.gitattributes -rw-r--r-- 65 bytes
.gitignore -rw-r--r-- 571 bytes
.mailmap -rw-r--r-- 12.7 KB
CITATION.bib -rw-r--r-- 513 bytes
CITATION.cff -rw-r--r-- 1012 bytes
CONTRIBUTING.md -rw-r--r-- 23.4 KB
HISTORY.md -rw-r--r-- 388.0 KB
LICENSE.md -rw-r--r-- 1.3 KB
Make.inc -rw-r--r-- 56.4 KB
Makefile -rw-r--r-- 30.4 KB
NEWS.md -rw-r--r-- 4.4 KB
README.md -rw-r--r-- 7.4 KB
THIRDPARTY.md -rw-r--r-- 3.9 KB
VERSION -rw-r--r-- 11 bytes
julia.spdx.json -rw-r--r-- 37.8 KB
pkgimage.mk -rw-r--r-- 1.4 KB
sysimage.mk -rw-r--r-- 4.2 KB
typos.toml -rw-r--r-- 78 bytes

README.md

back to top