Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8286638

C2: CmpU needs to do more precise over/underflow analysis

    XMLWordPrintable

    Details

    • Subcomponent:
    • Resolved In Build:
      b23

      Backports

        Description

        Was originally from bug JDK-8283466 that reported multiple domination asserts.
        Creating a separate bug because it is not related to all other issue, was only triggered with the ConvI2L refactoring JDK-8230382.

        Original Bug Reproducer:

        $ build/linux-x86_64-server-fastdebug/images/jdk/bin/java -cp 0029/ -Xmx512m -XX:+UnlockDiagnosticVMOptions -XX:+StressIGVN -Xcomp -XX:CompileOnly=Test -XX:-TieredCompilation Test
        CompileCommand: compileonly Test.* bool compileonly = true
        # To suppress the following error report, specify this argument
        # after -XX: or in .hotspotrc: SuppressErrorAt=/gcm.cpp:766
        #
        # A fatal error has been detected by the Java Runtime Environment:
        #
        # Internal Error (/home/shade/trunks/jdk/src/hotspot/share/opto/gcm.cpp:766), pid=3733508, tid=3733521
        # assert(!LCA_orig->dominates(pred_block) || early->dominates(pred_block)) failed: early is high enough
        #
        # JRE version: OpenJDK Runtime Environment (19.0) (fastdebug build 19-internal-adhoc.shade.jdk)
        # Java VM: OpenJDK 64-Bit Server VM (fastdebug 19-internal-adhoc.shade.jdk, compiled mode, sharing, compressed oops, compressed class ptrs, g1 gc, linux-amd64)
        # Problematic frame:
        # V [libjvm.so+0xdd1fe5] PhaseCFG::insert_anti_dependences(Block*, Node*, bool)+0x18a5


        Copied analysis from comments in JDK-8283466?:

        Scenario:
        type i: [minint...0]
        access to c[i-1]

        Range-check:
        int index = AddI(i, -1)
        -> type index: [minint-1 ... -1] -> underflow -> int
        CmpU(index, c.size()) [lt] -> checks index>=0 and index<c.size()
        Consequence: range-check cannot statically determine that the access is never ok.
        Sad, because we can manually tell that the range [minint-1 ... -1] should not pass the range check.

        Data-flow:
        long index = ConvI2L( AddI(i, -1) )
        -> type of ConvI2L: [0...maxint-1]
        -> why do we know this? Because this is before an array access. We assume range-check guarantees index in range [0...c.size()-1], and c.size()<=maxint.
        Then there is a push_thru_add, and we get:
        long index = AddL( ConvI2L(i), -1)
        -> type of new ConvI2L: [1...maxint-1] - because we correct the lo by 1 for the add. Somehow we do not adjust hi, in my opinion it should now be maxint, to correct by 1.
        Consequence: if hi is maxint or maxint-1, there is no overflow.
        Then, we statically detect that:
        type i: [minint...0]
        type ConvI2L: [1...maxint-1]
        -> filter results in TOP -> data-flow is eliminated sucessfully.

        Result in the end:
        data-flow collapses, while control-flow (range-check) does not collapse. This leads to issues described above.

        With the help of [~thartmann], we tracked it to CmpUNode::Value.
        There, we analyze if the in1 is an AddI.
        We detect that this AddI may have 2 ranges:
        tr1: int:<=-1:www
        tr2: int:max (underflow: minint-1)

        We then check how these ranges compare to in2:
        t2: int:>=0

        For this we compute:
        const Type* cmp1 = sub(tr1, t2); -> TypeInt::CC_GT = [1]
        const Type* cmp2 = sub(tr2, t2); -> TypeInt::CC_GE = [0...1]

        But then, we only do something with this result if cmp1 == cmp2.
        https://github.com/openjdk/jdk/blame/master/src/hotspot/share/opto/subnode.cpp#L832

        However, I wonder if we can not just take the union of cmp1 and cmp2, which would be [0...1] = [GE]
        Then, the output node [655 Bool] checks for [lt], which we could know is never true.
        We could conclude that the Range-check never passes.
        This would then also kill the control-flow, in parallel to the data-flow that is already killed with ConvI2L.

        Implementation:
        const TypeInt* cmp1 = sub(tr1, t2)->is_int();
        const TypeInt* cmp2 = sub(tr2, t2)->is_int();
        // compute union, so that cmp handles all possible results from the two cases
        return cmp1->meet(cmp2);

          Attachments

            Issue Links

              Activity

                People

                Assignee:
                epeter Emanuel Peter
                Reporter:
                epeter Emanuel Peter
                Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                  Dates

                  Created:
                  Updated:
                  Resolved: