United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-7105605 Use EA info to optimize pointers compare
JDK-7105605 : Use EA info to optimize pointers compare

Details
Type:
Enhancement
Submit Date:
2011-10-27
Status:
Closed
Updated Date:
2012-03-22
Project Name:
JDK
Resolved Date:
2012-01-20
Component:
hotspot
OS:
generic
Sub-Component:
compiler
CPU:
generic
Priority:
P4
Resolution:
Fixed
Affected Versions:
8-pool
Fixed Versions:
hs23 (b08)

Related Reports
Backport:
Backport:
Relates:
Relates:

Sub Tasks

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

                                    

Comments
EVALUATION

http://hg.openjdk.java.net/hsx/hotspot-comp/hotspot/rev/8c57262447d3
                                     
2011-11-15
EVALUATION

http://hg.openjdk.java.net/hsx/hotspot-emb/hotspot/rev/8c57262447d3
                                     
2011-12-15
EVALUATION

http://hg.openjdk.java.net/lambda/lambda/hotspot/rev/8c57262447d3
                                     
2012-03-22



Hardware and Software, Engineered to Work Together