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

Use EA info to optimize pointers compare

    Details

    • Type: Enhancement
    • Status: Closed
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 8-pool
    • Fix Version/s: hs23
    • Component/s: hotspot
    • Labels:
      None
    • Subcomponent:
    • Resolved In Build:
      b08
    • CPU:
      generic
    • OS:
      generic
    • Verification:
      Verified

      Backports

        Description

        EA Connection Graph can help to optimize pointers compare. For example, when comparing not escaped allocation with globally escaped or external object or NULL.
        "(k = e.key) == key" can be replaced with "false"
        if JIT compiler can see that Key is new object (due to
        inlining get() into test()) so it can not be equal
        to any previously allocated objects (e.key).

        Vladimir

        Paul Thio wrote:
        > Hi Vladimir,
        >
        > Thanks for answering my question. Just out of curiosity how would this be solved ?
        >
        > Thanks,
        > Paul
        >
        > On Nov 29, 2010, at 11:25 PM, Vladimir Kozlov wrote:
        >
        >> Paul,
        >>
        >> It is known problem and it is on our list of EA improvements.
        >> Object key (pointer to it) is used in Cmp instruction in HashMap.get():
        >>
        >> if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        >>
        >> Thanks,
        >> Vladimir
        >>
        >> Paul Thio wrote:
        >>> Hello,
        >>> I am wondering why in the following test program, the allocation at line 15 is not eliminated/replaced.
        >>> Thanks,
        >>> Paul
        >

        % cat Test.java
        import java.util.HashMap;

        public class Test {
            public static void main(String[] anArgs) {
                Test myTest = new Test();
                long s = 0;
                for (int i = 0; i < 1000000; i++)
                    for (int r = 0; r < 10; r++)
                        for (int c = 0; c < 10; c++)
                            s += myTest.test(r, c);
                System.exit((int) (s % 2));
            }

            public int test(int r, int c) {
                Key k = new Key(r, c);
                Integer v = m.get(k);

                if (v == null) {
                    System.out.print('.');
                    v = new Integer(r * c);
                    m.put(new Key(r, c), v);
                }

                return v.intValue();
            }

            class Key {
                public
                Key(int _r, int _c)
                {
                    r = _r;
                    c = _c;
                }

                public boolean equals(Object o) {
                    Key k = (Key) o;
                    return r == k.r && c == k.c;
                }

                public int hashCode() {
                    return r + c;
                }

                int r;
                int c;
            }

            private HashMap<Key, Integer> m = new HashMap<Key, Integer>();
        }

        Without compare pointers optimization (ran with debug version of VM):

        % java -XX:-OptimizePtrCompare -Xbatch -XX:+PrintCompilation -XX:+PrintEscapeAnalysis -XX:+PrintEliminateAllocations Test
        VM option '-OptimizePtrCompare'
        VM option '+PrintCompilation'
        VM option '+PrintEscapeAnalysis'
        VM option '+PrintEliminateAllocations'
        .................................................................................................... 1760 1 Test$Key::equals (33 bytes)
           1777 2 java.util.HashMap::get (79 bytes)
           1790 3 java.lang.Object::<init> (1 bytes)
           1791 4 Test$Key::<init> (20 bytes)
           1792 5 Test$Key::hashCode (10 bytes)
           1793 6 Test::test (75 bytes)

        ======== Connection graph for Test::test
            28 JavaObject NoEscape [[ 62F 95F 98F 101F 104F]] 28 Allocate === 5 6 7 8 1 ( 26 24 25 1 10 11 12 1 1 ) [[ 29 30 31 38 39 40 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, int ) Test::test @ bci:0 !jvms: Test::test @ bci:0
        LocalVar [[ 28P]] 40 Proj === 28 [[ 41 45 62 98 104 ]] #5 !jvms: Test::test @ bci:0
        LocalVar [[ 28P]] 45 CheckCastPP === 42 40 [[ 445 437 392 392 376 376 350 343 101 350 305 292 95 95 101 126 145 274 254 ]] #Test$Key:NotNull:exact * Oop:Test$Key:NotNull:exact * !jvms: Test::test @ bci:0

        NotScalar (Object is referenced by node) 45 CheckCastPP === 42 40 [[ 445 437 392 392 376 376 350 343 274 350 254 145 126 ]] #Test$Key:NotNull:exact *,iid=28 Oop:Test$Key:NotNull:exact *,iid=28 !jvms: Test::test @ bci:0
          >>>> 343 CmpP === _ 342 45 [[ 344 ]] !jvms: HashMap::get @ bci:52 Test::test @ bci:16
           1806 7 java.lang.Integer::intValue (5 bytes)
           1807 1 % Test::main @ 33 (80 bytes)


        With the optimization:

        % java -XX:+OptimizePtrCompare -Xbatch -XX:+PrintCompilation -XX:+PrintEscapeAnalysis -XX:+PrintEliminateAllocations Test
        VM option '+OptimizePtrCompare'
        VM option '+PrintCompilation'
        VM option '+PrintEscapeAnalysis'
        VM option '+PrintEliminateAllocations'
        .................................................................................................... 1669 1 Test$Key::equals (33 bytes)
           1691 2 java.util.HashMap::get (79 bytes)
           1704 3 java.lang.Object::<init> (1 bytes)
           1705 4 Test$Key::<init> (20 bytes)
           1706 5 Test$Key::hashCode (10 bytes)
           1707 6 Test::test (75 bytes)

        ======== Connection graph for Test::test
            28 JavaObject NoEscape [[ 62F 95F 98F 101F 104F]] 28 Allocate === 5 6 7 8 1 ( 26 24 25 1 10 11 12 1 1 ) [[ 29 30 31 38 39 40 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, int ) Test::test @ bci:0 !jvms: Test::test @ bci:0
        LocalVar [[ 28P]] 40 Proj === 28 [[ 41 45 62 98 104 ]] #5 !jvms: Test::test @ bci:0
        LocalVar [[ 28P]] 45 CheckCastPP === 42 40 [[ 445 437 392 392 376 376 350 254 101 350 305 292 95 95 101 126 145 274 ]] #Test$Key:NotNull:exact * Oop:Test$Key:NotNull:exact * !jvms: Test::test @ bci:0

        Scalar 45 CheckCastPP === 42 40 [[ 445 437 392 392 376 376 274 254 145 126 ]] #Test$Key:NotNull:exact *,iid=28 Oop:Test$Key:NotNull:exact *,iid=28 !jvms: Test::test @ bci:0
        ++++ Eliminated: 28 Allocate
           1719 7 java.lang.Integer::intValue (5 bytes)
           1720 1 % Test::main @ 33 (80 bytes)

        ======== Connection graph for Test::main
           159 JavaObject NoEscape [[ 224F 189F 222F]] 159 Allocate === 145 116 155 8 1 ( 32 157 20 1 1 153 1 1 120 121 122 119 1 153 121 122 1 1 ) [[ 160 161 162 169 170 171 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, int ) Test::test @ bci:0 Test::main @ bci:46 !jvms: Test::test @ bci:0 Test::main @ bci:46
        LocalVar [[ 159P]] 171 Proj === 159 [[ 172 176 ]] #5 !jvms: Test::test @ bci:0 Test::main @ bci:46
        LocalVar [[ 159P]] 176 CheckCastPP === 173 171 [[ 559 551 506 506 490 189 189 490 224 464 371 464 222 222 224 244 263 419 407 390 ]] #Test$Key:NotNull:exact * Oop:Test$Key:NotNull:exact * !jvms: Test::test @ bci:0 Test::main @ bci:46

        Scalar 176 CheckCastPP === 173 171 [[ 559 551 506 506 490 263 224 490 224 244 371 390 222 222 ]] #Test$Key:NotNull:exact *,iid=159 Oop:Test$Key:NotNull:exact *,iid=159 !jvms: Test::test @ bci:0 Test::main @ bci:46
        ++++ Eliminated: 159 Allocate

          Attachments

            Issue Links

              Activity

                People

                • Assignee:
                  kvn Vladimir Kozlov
                  Reporter:
                  kvn Vladimir Kozlov
                • Votes:
                  0 Vote for this issue
                  Watchers:
                  0 Start watching this issue

                  Dates

                  • Created:
                    Updated:
                    Resolved:
                    Imported:
                    Indexed: