Wasmtime GitHub notifications bot (Jul 31 2020 at 02:16): Wasmtime GitHub notifications bot (Jul 31 2020 at 02:16):cfallin opened PR #2083 from machinst-branch-bug to main:
When one branch target label in a MachBuffer is redirected to another,
we eventually fix up branches targetting the first to refer to the
redirected target instead. Separately, we have a branch-folding
optimization that, when an unconditional branch occurs as the only
instruction in a block (right at a label) and the previous instruction
is also an unconditional branch (hence no fallthrough), we can elide
that block entirely and redirect the label. Finally, we prevented
infinite loops when resolving label aliases by chasing only one alias
deep.Unfortunately, these three facts interacted poorly, and this is a result
of our correctness arguments assuming a fully-general "redirect" that
was not limited to one indirection level. In particular, we could have
some label A that redirected to B, then remove the block at B because it
is just a single branch to C, redirecting B to C. A would still redirect
to B, though, without chasing to C, and hence a branch to B would fall
through to the unrelated block that came after block B.Thanks to @bnjbvr for finding this bug while debugging the x64 backend
and reducing a failure to the function in issue #2082. (This is a very
subtle bug and it seems to have been quite difficult to chase; my
apologies!)The fix is to (i) chase redirects arbitrarily deep, but also (ii) ensure
that we do not form a cycle of redirects. The latter is done by very
carefully checking the existing fully-resolved target of the label we
are about to redirect to; if it resolves back to the branch that
is causing this redirect, then we avoid making the alias. The comments
in this patch make a slightly more detailed argument why this should be
correct.Unfortunately we cannot directly test the CLIF that @bnjbvr reduced
because we don't have a way to assert anything about the machine-code
that comes after the branch folding and emission. However, the dedicated
unit tests in this patch replicate an equivalent folding case, and also
test that we handle branch cycles properly (as argued above).Fixes #2082.
<!--
Please ensure that the following steps are all taken care of before submitting
the PR.
[ ] This has been discussed in issue #..., or if not, please tell us why
here.[ ] A short description of what this does, why it is needed; if the
description becomes long, the matter should probably be discussed in an issue
first.[ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
If you don't know who could review this, please indicate so. The list of
suggested reviewers on the right can help you.Please ensure all communication adheres to the code of conduct.
-->
Wasmtime GitHub notifications bot (Jul 31 2020 at 02:16):cfallin requested bnjbvr and julian-seward1 for a review on PR #2083.
Wasmtime GitHub notifications bot (Jul 31 2020 at 02:16):cfallin requested bnjbvr and julian-seward1 for a review on PR #2083.
Wasmtime GitHub notifications bot (Jul 31 2020 at 11:53):julian-seward1 submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 11:53):julian-seward1 created PR Review Comment:
Is there anything you can do here to stop this looping infinitely in the case of incorrectly constructed
self.label_aliases? On the basis that an assertion failure, in the field, is more informative than a hang. Like, for example, counting iterations and release-asserting at 1 million? (I think RA only allows 1 million BBs anyway).
Wasmtime GitHub notifications bot (Jul 31 2020 at 11:59):julian-seward1 submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 13:39):bnjbvr submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 13:39):bnjbvr submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 13:39):bnjbvr created PR Review Comment:
Unless I'm missing something, the exact opposite of this condition is checked right above on line 826, with no apparent side-effects in between, so this is unreachable code, and the existing code already does the right thing. In this case, moving the comment up could be useful.
Wasmtime GitHub notifications bot (Jul 31 2020 at 16:34):cfallin updated PR #2083 from machinst-branch-bug to main:
When one branch target label in a MachBuffer is redirected to another,
we eventually fix up branches targetting the first to refer to the
redirected target instead. Separately, we have a branch-folding
optimization that, when an unconditional branch occurs as the only
instruction in a block (right at a label) and the previous instruction
is also an unconditional branch (hence no fallthrough), we can elide
that block entirely and redirect the label. Finally, we prevented
infinite loops when resolving label aliases by chasing only one alias
deep.Unfortunately, these three facts interacted poorly, and this is a result
of our correctness arguments assuming a fully-general "redirect" that
was not limited to one indirection level. In particular, we could have
some label A that redirected to B, then remove the block at B because it
is just a single branch to C, redirecting B to C. A would still redirect
to B, though, without chasing to C, and hence a branch to B would fall
through to the unrelated block that came after block B.Thanks to @bnjbvr for finding this bug while debugging the x64 backend
and reducing a failure to the function in issue #2082. (This is a very
subtle bug and it seems to have been quite difficult to chase; my
apologies!)The fix is to (i) chase redirects arbitrarily deep, but also (ii) ensure
that we do not form a cycle of redirects. The latter is done by very
carefully checking the existing fully-resolved target of the label we
are about to redirect to; if it resolves back to the branch that
is causing this redirect, then we avoid making the alias. The comments
in this patch make a slightly more detailed argument why this should be
correct.Unfortunately we cannot directly test the CLIF that @bnjbvr reduced
because we don't have a way to assert anything about the machine-code
that comes after the branch folding and emission. However, the dedicated
unit tests in this patch replicate an equivalent folding case, and also
test that we handle branch cycles properly (as argued above).Fixes #2082.
<!--
Please ensure that the following steps are all taken care of before submitting
the PR.
[ ] This has been discussed in issue #..., or if not, please tell us why
here.[ ] A short description of what this does, why it is needed; if the
description becomes long, the matter should probably be discussed in an issue
first.[ ] This PR contains test cases, if meaningful.
- [ ] A reviewer from the core maintainer team has been assigned for this PR.
If you don't know who could review this, please indicate so. The list of
suggested reviewers on the right can help you.Please ensure all communication adheres to the code of conduct.
-->
Wasmtime GitHub notifications bot (Jul 31 2020 at 16:35):cfallin created PR Review Comment:
Excellent point, I had missed this. I made a slight change to the existing
if: we need anelsethat stops the branch-folding loop entirely, to preserve invariants.
Wasmtime GitHub notifications bot (Jul 31 2020 at 16:35):cfallin submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 16:36):cfallin submitted PR Review.
Wasmtime GitHub notifications bot (Jul 31 2020 at 16:36):cfallin created PR Review Comment:
Done!
Wasmtime GitHub notifications bot (Jul 31 2020 at 17:52):bnjbvr merged PR #2083.
Last updated: Nov 22 2024 at 16:03 UTC