You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
JDK 8/11/17/18 - incorrect result from JIT compilation due to erroneous loop condition evaluation #17249
$ uname -a
Linux luzhou 5.4.0-86-generic #97-Ubuntu SMP Fri Sep 17 19:19:40 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
Description
Incorrect result is given when running the following program. The bug affects 8u362, 11.0.18.0, 17.0.6.0, 18.0.2.1 using the hot and veryhot optlevels.
Steps to reproduce
The following steps shows how to reproduce the bug on JDK 17.0.6.0 in a Ubuntu Linux environment.
Compile
$ javac C.java
Execute
$ java -Xjit:optlevel=hot C
10142 // nondeterministic value
$ java -Xjit:optlevel=veryhot C
14331 // nondeterministic value
$ java -Xnojit C
0 // correct value
Source code for an executable test case
// C.java
public class C {
public static int m(int len) {
int[] arr = new int[8];
for (int i = 10000000, j = 0; (boolean) (i >= 1) && j < 100; i--, j++) {
// should not enter inner loop.
for (int k = 0; len < arr.length; ++k) {
// throws ArithmeticException to break out.
int x = 1 / 0;
}
}
return 0;
}
public static void main(String[] args) {
int sum = 0;
for (int i = 0; i < 100_000; ++i) {
try {
m(13);
} catch (ArithmeticException e) {
sum += 1;
}
}
System.out.println(sum); // expected 0
}
}
@JeffersonYu1, you have reported several issues against OpenJ9 in recent weeks, that have exposed some problems with JIT compilation in some uncommon cases. We really appreciate the effort required to expose these bugs.
I was speaking with @llxia about your tests, and she indicated that it would be good if we were able to include your tests (those for which OpenJ9 has failed and any which OpenJ9 currently executes successfully). If you hold the license for those tests, would you be willing to contribute them for inclusion in OpenJ9 testing? You wouldn't need to adapt them to the testing framework that we use, but you would need to sign the Eclipse Foundation Contributor agreement, which you can find in Contributing to Eclipse OpenJ9.
@hzongaro and @llxia, thanks for reaching out. @CptGit and I are researchers at the University of Texas at Austin. We work with Dr. Milos Gligoric, and the best way forward would be to sync with him. If it's okay, he will likely organize a group meeting between your team and our team for discussion.
Thanks for your interest in our work. We are excited about potential closer collaboration with you.
I mentioned in an earlier comment that the problem appeared to be in Loop Versioner. It looks like there's some interaction between asynccheck versioning and handling of invariant conditionals. Specifying the disableAsyncCheckVersioning seems to suppress the problem.
I'll try to distill the trees to show the problem.
In the previous comment I had promised a distillation of the trees to show the problem. If the test is run with lastSubOptIndex set to allow asynccheck versioning (the value of lastSubOptIndex differs by platform), but prevent versioning for invariant conditionals, the method looks something like this:
In the second version, block_3 falls through to block_36, which branches to block_35 to block_34, bypassing the conditional #349 < 8 in block_37. block_34 branches to block_32, falls through to block_31, then block_30, which branches unconditionally to block_28. block_28 falls through to block_19, which branches to block_21, performing the division by zero in the inner loop.
The branch is already reversed in the !_original case. Reversing it again by inverting the meaning of _reverseBranch will cause the conditional to be folded the same way in the duplicate loop as in the original loop. While that allows this particular test to pass, it's incorrect. We would transform
while (...) {
if (invariantCondition) { T; } else { E; }
}
into
if (invariantCondition) {
while (...) { T; }
} else {
while (...) { T; } // BUG: invariantCondition is false here
}
In this issue the problem with the duplicate conditional is not that it's folded the wrong way, but rather that it's folded at all. With the max iteration guard, we end up with something like this:
if (invariantCondition && iters < bound) {
while (...) { T; } // ok: invariantCondition is true
} else {
while (...) { E; } // BUG: invariantCondition is unknown
}
Normally other versioning tests would prevent folding in the duplicate loop: _conditionalTree would be null and so changeConditionalToUnconditionalInBothVersions would be false. But this is determined when calling detectInvariantConditionals(), and versioner doesn't decide whether to version asynccheck until later on.
It should be possible to fix this in one of two ways:
Detect that we're trying to fold a conditional in both loops and suppress asynccheck versioning in that case, or
Set _conditionalTree back to null to prevent folding in the duplicate loop when we decide to version asynccheck.
We also decide late whether to version write barriers, so they could hit a similar problem. That decision is even after buildConditionalTree(), so for write barriers I think we'd have to do (1).
Note that even if we're only trying to version w.r.t. a single conditional, we might have additional versioning tests generated by depsForLoopEntryPrep(). Those are OK though because they check conditions that are required to be able to safely evaluate the conditional, so if any of them fail then the conditional won't even run anyway.
@jdmpapin Thank you very much for your insight! I have some questions.
(1)
I looked at the above example of why the attempted fix is incorrect. Is my below understanding of what the correct logic after the loop version transformation should look like correct?
Before loop versioner
while (...) {
if (invariantCondition) { T; } else { E; }
}
After loop versioner
if (invariantCondition) {
while (...) { T; }
} else {
while (...) { E; }
}
Before conditional tree folding
Original:
ificmplt --> T
iload <parm 0 I>
iconst 8
E
Duplicated:
ificmplt --> T
iload <parm 0 I>
iconst 8
E
After conditional tree folding
Original
ificmpeq --> T // logic falls through to E
iconst 0
iconst 1
E
Duplicated
ificmpne --> T // logic jumps to T
iconst 0
iconst 1
E
(2)
I understand how the proposed solution 2 that sets _conditionalTree to null would fix the issue
Set _conditionalTree back to null to prevent folding in the duplicate loop when we decide to version asynccheck.
Detect that we're trying to fold a conditional in both loops and suppress asynccheck versioning in that case, or
I know suppressing versioning asynchCheck will make the problem go away, but I haven’t connected the dots on how versioning asynchCheck contributes to the issue. Could you elaborate?
Regarding to the Detect that we're trying to fold a conditional in both loops, is it to check if _conditionalTree and (conditionalTrees->getSize() == 1) to decide whether or not to avoid version async check or write barriers?
Is my below understanding of what the correct logic after the loop version transformation should look like correct?
Yes, though I was intentionally a bit imprecise in the pseudocode, so in order for the trees to correspond properly to the pseudocode loop in this case, the version containing T would be the duplicate, and the version containing E would be the original/hot loop, which is the opposite of what I originally intended in my example
I believe that versioner already handles this folding correctly
Detect that we're trying to fold a conditional in both loops and suppress asynccheck versioning in that case, or
I know suppressing versioning asynchCheck will make the problem go away, but I haven’t connected the dots on how versioning asynchCheck contributes to the issue. Could you elaborate?
Consider the case where we have only one versioning test, and it determines the direction of this conditional:
if (len < 8) goto dup_loop
We can only get into the duplicate loop if len < 8, so it's fine to fold the conditional in both versions
OTOH, suppose now we version something else and we end up with a second versioning test unrelated to len < 8. In particular, let's suppose we version asynccheck with a max loop iteration guard:
if (len < 8) goto dup_loop
if (iters > 0x...) goto dup_loop // max loop iteration guard
Now it's possible to reach the duplicate loop by failing the other versioning test even if len >= 8. That means that in the duplicate loop we no longer know whether len < 8 or len >= 8, and we can't fold anymore
So it's not possible to (correctly) fold in the duplicate loop and also have another unrelated versioning test. To avoid that situation, we need to either avoid generating an unrelated versioning test (suggestion 1) or avoid folding in the duplicate loop (suggestion 2)
Regarding to the Detect that we're trying to fold a conditional in both loops, is it to check if _conditionalTree and (conditionalTrees->getSize() == 1) to decide whether or not to avoid version async check or write barriers?
I don't think that condition is specific enough. We'd want to know whether we've generated a FoldConditional in the duplicate loop (here)
By the way, I don't think one of the options is better than the other in all cases. If the branch is highly biased, then it's probably best to allow for more versioning in the original loop (and prevent folding in the duplicate). But OTOH if the branch is relatively unbiased it might be better to prevent additional versioning and improve both loops. That said, the highly biased case should be more typical
Thanks again for the clarification @jdmpapin! One more question: Wouldn't folding the conditional in the original loop be a problem as well if we version either async check or write barrier? It can reach origin_loop even if len <8.
if (len < 8) goto dup_loop
fall through to origin_loop
if (iters > 0x...) goto dup_loop // max loop iteration guard
fall through to origin_loop
I have a proto fix based on the sequence of events in loop versioning, which fixes folding in the duplicated loop. Could you help take a look?
- Clone blocks and trees
- This is where `_duplicateConditionalTree` is created if `_conditionalTree` exists
- Decide whether or not to version async check
- Construct the tests for invariant conditionals
- `buildConditionalTree` could generate a `FoldConditional` in the duplicate loop
- Decide whether or not to version write barrier: `awrtbariVersioningOK`
- Emit loop entry prep and transform the loop for each loop improvement
To fix versioning async check, it sets _conditionalTree back to null to prevent FoldConditional being generated later in the duplicate loop because buildConditionalTree hasn't taken place yet
To fix versioning write barrier, it detects if we are trying to fold a conditional in the duplicated loop because FoldConditional could have already been generated in buildConditionalTree before determining versioning write barrier.
Wouldn't folding the conditional in the original loop be a problem as well if we version either async check or write barrier? It can reach origin_loop even if len <8.
No, it's always OK to fold in the original loop (given that we've generated the appropriate versioning test(s)). That's because in order to enter into the original/hot loop, all versioning tests must pass. In general a versioning test falls through not directly to the original loop, but rather to the sequence of all the versioning tests that follow it. So it's not possible to enter the original loop with len < 8. It's this same logic that normally allows us to version more than one check in a loop
asynccheck versioning: This part of the change looks good. However, I think we should also check before reaching that point for a _conditionalTree with a nontrivial chance of being taken, and if we have one, then we should prevent asynccheck versioning instead
Usually we version branches only when they're highly biased, but when there doesn't seem to be any other versioning going on and we want to try folding a single conditional in both loops, it can be allowed to be unbiased. In that case, if we later decide to version asynccheck, then we'll make two improvements in the original loop and none in the duplicate even though the original is not necessarily hotter. But if OTOH we avoid versioning asynccheck, then we can still fold the conditional in both loops as originally intended
Rather than searching for a FoldConditional of _duplicateConditionalTree, it seems to me it could be simpler to remember whether we've generated one, e.g. by setting a flag when we do. Then we wouldn't need to introduce all of these queries on LoopEntryPrep. What do you think?
Also, IMO it would be better to suppress write barrier versioning when awrtbariVersioningOK is initialized, before the fixed-point analysis. It doesn't make a difference to the speed of convergence, but similar changes to the other variables (e.g. _privatizationOK) would, so they're generally set to false at the beginning if we know they won't be possible. Also it would stop the dumpOptDetails() messages from claiming that we're considering allowing write barrier versioning
... we could just consult _conditionalTree, since it only gets set on a path that also sets _neitherLoopCold
If I understand it correctly, it means we will never version async tree as long as _conditionalTree exists? And the previous proto fix that sets _conditionalTree to null after deciding to version async versioning should be removed because it will never get to that logic if _duplicateConditionalTree exists.
// `_duplicateConditionalTree` is set only when `_conditionalTree` is set. `_conditionalTree` // is set when`_neitherLoopCold` is true. If `_duplicateConditionalTree` exists, the loops are// unbiased. When the loops are unbiased, do not allow versioning asynch check so that// the conditional in both loops can be folded awaybool asyncCheckVersioningOK = _duplicateConditionalTree ? false : true;
if (asyncCheckVersioningOK &&
!comp()->getOption(TR_DisableAsyncCheckVersioning) &&
!refineAliases() && _canPredictIters && comp()->getProfilingMode() != JitProfiling &&
performTransformation(comp(), "%s Creating test outside loop for deciding if async check is required\n", OPT_DETAILS_LOOP_VERSIONER))
{
#if0 // This part of the code should be removed
if (_duplicateConditionalTree)
{
if (trace())
traceMsg(comp(), "%s: Fix set _conditionalTree to NULL to avoid folding conditional in the duplicated loop\n", __FUNCTION__);
_conditionalTree = NULL;
}
#endif
...
Activity
pshipton commentedon Apr 24, 2023
@hzongaro @0xdaryl fyi
hzongaro commentedon Apr 25, 2023
It looks like this is a problem with Loop Versioner. I can usually reproduce the failure with, where opt index 81 is Loop Versioner:
Not sure beyond that what the bad transformation might be.
hzongaro commentedon May 8, 2023
@JeffersonYu1, you have reported several issues against OpenJ9 in recent weeks, that have exposed some problems with JIT compilation in some uncommon cases. We really appreciate the effort required to expose these bugs.
I was speaking with @llxia about your tests, and she indicated that it would be good if we were able to include your tests (those for which OpenJ9 has failed and any which OpenJ9 currently executes successfully). If you hold the license for those tests, would you be willing to contribute them for inclusion in OpenJ9 testing? You wouldn't need to adapt them to the testing framework that we use, but you would need to sign the Eclipse Foundation Contributor agreement, which you can find in Contributing to Eclipse OpenJ9.
llxia commentedon May 8, 2023
@JeffersonYu1 if you do not mind, could you please create a new folder under https://github.com/eclipse-openj9/openj9/tree/master/test/functional with your test code? We will take it from there and incorporate the tests into our framework/pipeline. Thanks.
JeffersonYu1 commentedon May 9, 2023
@hzongaro and @llxia, thanks for reaching out. @CptGit and I are researchers at the University of Texas at Austin. We work with Dr. Milos Gligoric, and the best way forward would be to sync with him. If it's okay, he will likely organize a group meeting between your team and our team for discussion.
Thanks for your interest in our work. We are excited about potential closer collaboration with you.
hzongaro commentedon Jun 14, 2023
I mentioned in an earlier comment that the problem appeared to be in Loop Versioner. It looks like there's some interaction between asynccheck versioning and handling of invariant conditionals. Specifying the
disableAsyncCheckVersioningseems to suppress the problem.I'll try to distill the trees to show the problem.
hzongaro commentedon Jun 28, 2023
In the previous comment I had promised a distillation of the trees to show the problem. If the test is run with
lastSubOptIndexset to allow asynccheck versioning (the value oflastSubOptIndexdiffers by platform), but prevent versioning for invariant conditionals, the method looks something like this:with both asynccheck versioning and versioning for invariant conditionals, it looks like this:
In the second version, block_3 falls through to block_36, which branches to block_35 to block_34, bypassing the conditional
#349 < 8in block_37. block_34 branches to block_32, falls through to block_31, then block_30, which branches unconditionally to block_28. block_28 falls through to block_19, which branches to block_21, performing the division by zero in the inner loop.It could be related to the conditions under which
changeConditionalToUnconditionalInBothVersionsis set to true inTR_LoopVersioner::buildConditionalTree.hzongaro commentedon Aug 14, 2023
I don't expect to have a fix for this ready for 0.41. Moving it out to the 0.43 release.
7 remaining items
jdmpapin commentedon Oct 17, 2023
The branch is already reversed in the
!_originalcase. Reversing it again by inverting the meaning of_reverseBranchwill cause the conditional to be folded the same way in the duplicate loop as in the original loop. While that allows this particular test to pass, it's incorrect. We would transforminto
In this issue the problem with the duplicate conditional is not that it's folded the wrong way, but rather that it's folded at all. With the max iteration guard, we end up with something like this:
Normally other versioning tests would prevent folding in the duplicate loop:
_conditionalTreewould be null and sochangeConditionalToUnconditionalInBothVersionswould be false. But this is determined when callingdetectInvariantConditionals(), and versioner doesn't decide whether to versionasynccheckuntil later on.It should be possible to fix this in one of two ways:
asynccheckversioning in that case, or_conditionalTreeback to null to prevent folding in the duplicate loop when we decide to versionasynccheck.We also decide late whether to version write barriers, so they could hit a similar problem. That decision is even after
buildConditionalTree(), so for write barriers I think we'd have to do (1).Note that even if we're only trying to version w.r.t. a single conditional, we might have additional versioning tests generated by
depsForLoopEntryPrep(). Those are OK though because they check conditions that are required to be able to safely evaluate the conditional, so if any of them fail then the conditional won't even run anyway.a7ehuo commentedon Oct 18, 2023
@jdmpapin Thank you very much for your insight! I have some questions.
(1)
I looked at the above example of why the attempted fix is incorrect. Is my below understanding of what the correct logic after the loop version transformation should look like correct?
Before loop versioner
After loop versioner
Before conditional tree folding
After conditional tree folding
(2)
I understand how the proposed solution 2 that sets
_conditionalTreeto null would fix the issueIt is because folding
_duplicateConditionalTreeis determined bychangeConditionalToUnconditionalInBothVersionschangeConditionalToUnconditionalInBothVersionsis determined by the existence of_conditionalTree_conditionalTreeis set ifcontainsNonInlineGuardis truecontainsNonInlineGuardis set indetectInvariantConditionalsif the node branches.However I don’t fully understand solution 1.
I know suppressing versioning asynchCheck will make the problem go away, but I haven’t connected the dots on how versioning asynchCheck contributes to the issue. Could you elaborate?
Regarding to the
Detect that we're trying to fold a conditional in both loops, is it to check if_conditionalTreeand(conditionalTrees->getSize() == 1)to decide whether or not to avoid version async check or write barriers?jdmpapin commentedon Oct 19, 2023
Yes, though I was intentionally a bit imprecise in the pseudocode, so in order for the trees to correspond properly to the pseudocode loop in this case, the version containing
Twould be the duplicate, and the version containingEwould be the original/hot loop, which is the opposite of what I originally intended in my exampleI believe that versioner already handles this folding correctly
Consider the case where we have only one versioning test, and it determines the direction of this conditional:
We can only get into the duplicate loop if
len < 8, so it's fine to fold the conditional in both versionsOTOH, suppose now we version something else and we end up with a second versioning test unrelated to
len < 8. In particular, let's suppose we versionasynccheckwith a max loop iteration guard:Now it's possible to reach the duplicate loop by failing the other versioning test even if
len >= 8. That means that in the duplicate loop we no longer know whetherlen < 8orlen >= 8, and we can't fold anymoreSo it's not possible to (correctly) fold in the duplicate loop and also have another unrelated versioning test. To avoid that situation, we need to either avoid generating an unrelated versioning test (suggestion 1) or avoid folding in the duplicate loop (suggestion 2)
I don't think that condition is specific enough. We'd want to know whether we've generated a
FoldConditionalin the duplicate loop (here)By the way, I don't think one of the options is better than the other in all cases. If the branch is highly biased, then it's probably best to allow for more versioning in the original loop (and prevent folding in the duplicate). But OTOH if the branch is relatively unbiased it might be better to prevent additional versioning and improve both loops. That said, the highly biased case should be more typical
a7ehuo commentedon Oct 20, 2023
Thanks again for the clarification @jdmpapin! One more question: Wouldn't folding the conditional in the original loop be a problem as well if we version either async check or write barrier? It can reach origin_loop even if len <8.
I have a proto fix based on the sequence of events in loop versioning, which fixes folding in the duplicated loop. Could you help take a look?
To fix versioning async check, it sets
_conditionalTreeback to null to preventFoldConditionalbeing generated later in the duplicate loop becausebuildConditionalTreehasn't taken place yetTo fix versioning write barrier, it detects if we are trying to fold a conditional in the duplicated loop because
FoldConditionalcould have already been generated inbuildConditionalTreebefore determining versioning write barrier.jdmpapin commentedon Oct 23, 2023
No, it's always OK to fold in the original loop (given that we've generated the appropriate versioning test(s)). That's because in order to enter into the original/hot loop, all versioning tests must pass. In general a versioning test falls through not directly to the original loop, but rather to the sequence of all the versioning tests that follow it. So it's not possible to enter the original loop with
len < 8. It's this same logic that normally allows us to version more than one check in a loopI'm taking a look at your commit
jdmpapin commentedon Oct 23, 2023
asynccheckversioning: This part of the change looks good. However, I think we should also check before reaching that point for a_conditionalTreewith a nontrivial chance of being taken, and if we have one, then we should preventasynccheckversioning insteadUsually we version branches only when they're highly biased, but when there doesn't seem to be any other versioning going on and we want to try folding a single conditional in both loops, it can be allowed to be unbiased. In that case, if we later decide to version
asynccheck, then we'll make two improvements in the original loop and none in the duplicate even though the original is not necessarily hotter. But if OTOH we avoid versioningasynccheck, then we can still fold the conditional in both loops as originally intendedjdmpapin commentedon Oct 23, 2023
Write barrier versioning:
Rather than searching for a
FoldConditionalof_duplicateConditionalTree, it seems to me it could be simpler to remember whether we've generated one, e.g. by setting a flag when we do. Then we wouldn't need to introduce all of these queries onLoopEntryPrep. What do you think?Also, IMO it would be better to suppress write barrier versioning when
awrtbariVersioningOKis initialized, before the fixed-point analysis. It doesn't make a difference to the speed of convergence, but similar changes to the other variables (e.g._privatizationOK) would, so they're generally set to false at the beginning if we know they won't be possible. Also it would stop thedumpOptDetails()messages from claiming that we're considering allowing write barrier versioninga7ehuo commentedon Oct 23, 2023
@jdmpapin The proto fix is updated. If there is no major issue, I'll clean up the code, run sanity test, and prep for PR. Thank you!
jdmpapin commentedon Oct 23, 2023
Seeing the
highlyBiasedBranchlogic now, I think we should probably try to avoid duplicating it 😅I took another look and I think that we could just consult
_conditionalTree, since it only gets set on a path that also sets_neitherLoopColdLooks good otherwise! Thanks for the updates
a7ehuo commentedon Oct 24, 2023
If I understand it correctly, it means we will never version async tree as long as
_conditionalTreeexists? And the previous proto fix that sets_conditionalTreeto null after deciding to version async versioning should be removed because it will never get to that logic if_duplicateConditionalTreeexists.jdmpapin commentedon Oct 24, 2023
Yes, I think that should be good. By the way I think this sentence has the implication backwards:
unless you want to specify that
Fix issue in folding the conditional in the duplicated loop
Fix issue in folding the conditional in the duplicated loop
Fix issue in folding the conditional in the duplicated loop