Skip to content

JDK 8/11/17/18 - incorrect result from JIT compilation due to erroneous loop condition evaluation #17249

Closed
eclipse-omr/omr
#7155

Description

@JeffersonYu1

System / OS / Java Runtime Information

Java version

$ java -version

openjdk 17.0.6 2023-01-17
IBM Semeru Runtime Open Edition 17.0.6.0 (build 17.0.6+10)
Eclipse OpenJ9 VM 17.0.6.0 (build openj9-0.36.0, JRE 17 Linux amd64-64-Bit Compressed References 20230117_397 (JIT enabled, AOT enabled)
OpenJ9   - e68fb241f
OMR      - f491bbf6f
JCL      - 927b34f84c8 based on jdk-17.0.6+10)

Operating system details

$ cat /etc/*release

DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=20.04
DISTRIB_CODENAME=focal
DISTRIB_DESCRIPTION="Ubuntu 20.04.3 LTS"
NAME="Ubuntu"
VERSION="20.04.3 LTS (Focal Fossa)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 20.04.3 LTS"
VERSION_ID="20.04"
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
VERSION_CODENAME=focal
UBUNTU_CODENAME=focal
$ 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
    }
}

Workaround

Disable JIT.

$ java -Xnojit C

Activity

  1. pshipton commented on Apr 24, 2023

    @pshipton
    Member
  2. hzongaro commented on Apr 25, 2023

    @hzongaro
    Member

    It looks like this is a problem with Loop Versioner. I can usually reproduce the failure with, where opt index 81 is Loop Versioner:

    java -Xnoaot -Xjit:count=10,disableAsyncCompilation,limit={C.m\(*},optLevel=hot,lastOptIndex=81 C
    

    Not sure beyond that what the bad transformation might be.

  3. hzongaro commented on May 8, 2023

    @hzongaro
    Member

    @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.

  4. llxia commented on May 8, 2023

    @llxia
    Contributor

    @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.

  5. JeffersonYu1 commented on May 9, 2023

    @JeffersonYu1
    Author

    @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.

  6. hzongaro commented on Jun 14, 2023

    @hzongaro
    Member

    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.

  7. hzongaro commented on Jun 28, 2023

    @hzongaro
    Member

    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:

    block_2:   #351 = 0x989680; #352 = 0
    block_3:   if (#351 < 1) goto block_24
    block_35:  if ((#351 - 1) > 0x7f2815) goto block_34  // maxLoopIternGuard
    block_23:  goto block_4
    block_34:  goto block_32
    block_24:  goto block_12
    block_25:  if (#351 < 1) goto block_12
    block_4:   // Empty
    block_16:  if (#352 >= 100) goto block_12
    block_8:   if (#349 < 8) goto block_28
    block_11:  #351 = #351 + (-1)
               #352 = #352 - (-1)
    block_28:  if (0 != 0) goto block_27
    block_19:  goto block_21
    block_27:  goto block_26
    block_21:  DIVCHK (1 / 0)
               asynccheck
               goto block_21
    block_12:  ireturn 0
    block_26:  DIVCHK (1 / 0)
               asynccheck
               goto block_26
    block_33:  if (#351 < 1) goto block_12
    block_32:  // Empty
    block_31:  if (#352 >= 100) goto block_12
    block_30:  if (#349 < 8) goto block_28
    block_29:  #351 = #351 + (-1)
               #352 = #352 - (-1)
               asynccheck
               goto block_33
    

    with both asynccheck versioning and versioning for invariant conditionals, it looks like this:

    block_2:   #351 = 0x989680; #352 = 0
    block_3:   if (#351 < 1) goto block_24
    block_36:  if ((#351 - 1) > 0x7f2815) goto block_35
    block_37:  if (#349 < 8) goto block_34
    block_23:  goto block_4
    block_34:  goto block_32
    block_24:  goto block_12
    block_25:  if (#351 < 1) goto block_12
    block_4:   // Empty
    block_16   if (#352 >= 100) goto block_12
    block_8:   if (0 == 1) goto block_28
    block_11:  #351 = #351 + (-1)
               #352 = #352 - (-1)
    block_28:  if (0 != 0) goto block_27
    block_19:  goto block_21
    block_27:  goto block_26
    block_21:  DIVCHK (1 / 0)
               asynccheck
               goto block_21
    block_12:  ireturn 0
    block_26:  DIVCHK ( 1 / 0)
               asynccheck
               goto block_26
    block_33:  if (#351 < 1) goto block_12
    block_32:  // Empty
    block_31:  if (#352 >= 100) goto block_12
    block_30   if (1 != 0) goto block_28
    block_29:  #351 = #351 + (-1)
               #352 = #352 - (-1)
               asynccheck
               goto block_33
    block_35:  goto block_34
    

    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.

    It could be related to the conditions under which changeConditionalToUnconditionalInBothVersions is set to true in TR_LoopVersioner::buildConditionalTree.

  8. hzongaro commented on Aug 14, 2023

    @hzongaro
    Member

    I don't expect to have a fix for this ready for 0.41. Moving it out to the 0.43 release.

  9. 7 remaining items

  10. jdmpapin commented on Oct 17, 2023

    @jdmpapin
    Contributor

    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:

    1. Detect that we're trying to fold a conditional in both loops and suppress asynccheck versioning in that case, or
    2. 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.

  11. a7ehuo commented on Oct 18, 2023

    @a7ehuo
    Contributor

    @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

    1. Set _conditionalTree back to null to prevent folding in the duplicate loop when we decide to version asynccheck.

    It is because folding _duplicateConditionalTree is determined by changeConditionalToUnconditionalInBothVersions

    However I don’t fully understand solution 1.

    1. 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?

  12. jdmpapin commented on Oct 19, 2023

    @jdmpapin
    Contributor

    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

    1. 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

  13. a7ehuo commented on Oct 20, 2023

    @a7ehuo
    Contributor

    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.

  14. jdmpapin commented on Oct 23, 2023

    @jdmpapin
    Contributor

    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

    I'm taking a look at your commit

  15. jdmpapin commented on Oct 23, 2023

    @jdmpapin
    Contributor

    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

  16. jdmpapin commented on Oct 23, 2023

    @jdmpapin
    Contributor

    Write barrier versioning:

    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

  17. a7ehuo commented on Oct 23, 2023

    @a7ehuo
    Contributor

    @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!

  18. jdmpapin commented on Oct 23, 2023

    @jdmpapin
    Contributor

    Seeing the highlyBiasedBranch logic 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 _neitherLoopCold

    Looks good otherwise! Thanks for the updates

  19. a7ehuo commented on Oct 24, 2023

    @a7ehuo
    Contributor

    ... 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 away
    
          bool 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))
             {
    #if 0 // 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
              ...
  20. jdmpapin commented on Oct 24, 2023

    @jdmpapin
    Contributor

    Yes, I think that should be good. By the way I think this sentence has the implication backwards:

    _conditionalTree is set when_neitherLoopCold is true

    unless you want to specify that

    _conditionalTree is set only when_neitherLoopCold is true

  21. added 3 commits that reference this issue on Oct 25, 2023
    36ca08b
    88c3544
    250f161
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions