Revision 53401f1cb4e829b3a0d74295473c9a48fff2bbab authored by Keno Fischer on 29 October 2020, 21:36:53 UTC, committed by Keno Fischer on 29 October 2020, 21:48:17 UTC
When inference detects a call cycle, one of two things could happen:
1. It determines that in order for inference to converge it needs
   to limit the signatures of some methods to something more general, or
2. The cycle is determined to be harmless at the inference level (because
   though there is a cycle in the CFG there is no dependency cycle of
   type information).

In the first case, we simply disable optimizations, which is sensible,
because we're likely to have to recompute some information anyway,
when we actually get there dynamically.

In the second case however, we do do optimizations, but it's a bit
of an unusual case. In particular, inference usually delivers
methods to inlining in postorder (meaning callees get optimized
before their callers) such that a caller can always inline a callee.

However, if there is a cycle, there is of course no unique postorder
of functions, since by definition we're looking a locally strongly
connected component. In this case, we would just essentially pick
an arbitrary order (and moreover, depending on the point at which
we enter the cycle and subsequently cached, leading to potential
performance instabilities, depending on function order).
However, the arbitrary order is quite possibly
suboptimal. For example in #36414, we have a cycle
randn -> _randn -> randn_unlikely -> rand. In this cycle the author
of this code expected both `randn` and `_randn` to inline and
annotated the functions as such. However, in 1.5+ the order we happed
to pick would have inlined randn_unlikely into _randn (had it not
been marked noinline), with a hard call break between randn and
_randn, whch is problematic from a performance standpoint.

This PR aims to address this by introducing a heuristic: If some
functions in a cycle are marked as `@noinline`, we want to make
sure to infer these last (since they won't ever be inlined anyway).
To ensure this happens, while restoring postorder if this happens
to break the cycle, we perform a DFS traversal rooted at any `@noinline`
functions and then optimize the functions in the cycle in DFS-postorder.
Of course still may still not be a true postorder in the inlining
graph (if the `@noinline` functions don't break the cycle), but
even in that case, it should be no worse than the default order.

Fixes #36414
Closes #37234
1 parent 0d5c38b
History
File Mode Size
.devcontainer
base
cli
contrib
deps
doc
etc
src
stdlib
test
.clang-format -rw-r--r-- 3.3 KB
.gitattributes -rw-r--r-- 65 bytes
.gitignore -rw-r--r-- 273 bytes
.mailmap -rw-r--r-- 11.0 KB
CITATION.bib -rw-r--r-- 2.6 KB
CONTRIBUTING.md -rw-r--r-- 19.9 KB
HISTORY.md -rw-r--r-- 292.0 KB
LICENSE.md -rw-r--r-- 5.0 KB
Make.inc -rw-r--r-- 47.5 KB
Makefile -rw-r--r-- 27.5 KB
NEWS.md -rw-r--r-- 16.7 KB
README.md -rw-r--r-- 6.9 KB
VERSION -rw-r--r-- 10 bytes
sysimage.mk -rw-r--r-- 3.9 KB

README.md

back to top