A simple optimization proposal
Krystal Mok
rednaxelafx at gmail.com
Thu Feb 13 09:11:04 PST 2014
Hi Martin,
Comments inline below:
On Thu, Feb 13, 2014 at 12:37 AM, Martin Grajcar <maaartinus at gmail.com>wrote:
> Hi Kris,
>
> I guess that without the line
>
> if (a.length == 0) throw new Exception();
>
> it looks the same (just throwing another Exception), right?
>
> That's right. Without this line, the generated code would have done
exactly the same check and it'd throw an ArrayOutOfBoundsException instead.
(To John:)
In this case, because the check is really the same thing, the redundant
check is actually dead even during parsing, due to GVN. Which is a good
thing for the compiler, but also means this case is not enough to
demonstrate the optimization.
I've tried another case, and it demonstrates that the current patch needs
more polishing to work well:
private static Object foo2(Object[] a, int x) throws Exception {
a[1] = a[2]; // line 1
return a[x & (a.length - 1)]; // line 2
}
The generated code is at the end of this email.
Here, the code in line 1 should ensure a.length > 2, and that predicate
should propagate to line 2. But in the generated code, there's still a
bounds check (a.length != 0) in line 2, right before the actual element
load.
There are some more issues with the generated code, e.g.
1. There's a redundant array store class check for line 1. Although due to
Java's covariant arrays, an array class check is generally needed, here the
value to store is loaded from the same array, so it shouldn't need a class
check.
2. There's redundant code for type casting:
movq R11, R11 # ptr -> long
I guess that could be addressed in the peephole pass.
These two issues will be addressed separately.
Thanks,
Kris
380 2 ArrayRangeCheck::foo2 (15 bytes)
PrintAssembly request changed to PrintOptoAssembly
{method}
- this oop: 0x0000000113e5a470
- method holder: 'ArrayRangeCheck'
- constants: 0x0000000113e5a068 constant pool [48]
{0x0000000113e5a068} for 'ArrayRangeCheck' cache=0x0000000113e5a5b8
- access: 0x8100000a private static
- name: 'foo2'
- signature: '([Ljava/lang/Object;I)Ljava/lang/Object;'
- max stack: 5
- max locals: 2
- size of params: 2
- method size: 12
- vtable index: -2
- i2i entry: 0x0000000106fc56e0
- adapters: AHE at 0x00007fa1ec072428: 0xba000000 i2c:
0x00000001070b5460 c2i: 0x00000001070b5577 c2iUV: 0x00000001070b554a
- compiled entry 0x00000001070b5577
- code size: 15
- code start: 0x0000000113e5a438
- code end (excl): 0x0000000113e5a447
- method data: 0x0000000113e5a8f0
- checked ex length: 1
- checked ex start: 0x0000000113e5a46c
- linenumber start: 0x0000000113e5a447
- localvar length: 2
- localvar start: 0x0000000113e5a452
#
# java/lang/Object * ( narrowoop: java/lang/Object *[int:>=0] *, int )
#
#r018 rsi:rsi : parm 0: narrowoop: java/lang/Object *[int:>=0] *
#r016 rdx : parm 1: int
# -- Old rsp -- Framesize: 64 --
#r191 rsp+60: in_preserve
#r190 rsp+56: return address
#r189 rsp+52: in_preserve
#r188 rsp+48: saved fp register
#r187 rsp+44: pad2, stack alignment
#r186 rsp+40: pad2, stack alignment
#r185 rsp+36: Fixed slot 1
#r184 rsp+32: Fixed slot 0
#r199 rsp+28: spill
#r198 rsp+24: spill
#r197 rsp+20: spill
#r196 rsp+16: spill
#r195 rsp+12: spill
#r194 rsp+ 8: spill
#r193 rsp+ 4: spill
#r192 rsp+ 0: spill
#
abababab N1: # B1 <- B9 B7 B5 B8 B6 Freq: 1
abababab
000 B1: # B9 B2 <- BLOCK HEAD IS JUNK Freq: 1
000 # stack bang
pushq rbp # Save rbp
subq rsp, #48 # Create frame
00c movl R10, [RSI + #12 (8-bit)] # range
010 NullCheck RSI
010
010 B2: # B7 B3 <- B1 Freq: 0.999999
010 cmpl R10, #2 # unsigned
014 jbe,u B7 P=0.000001 C=-1.000000
014
01a B3: # B8 B4 <- B2 Freq: 0.999998
01a movl RBP, [RSI + #24 (8-bit)] # compressed ptr
01d movl R11, [RSI + #8 (8-bit)] # compressed klass ptr
021 cmpl R11, narrowklass: precise klass [Ljava/lang/Object;:
0x00007fa1ecc72628:Constant:exact * # compressed klass ptr
028 jne,u B8 P=0.000001 C=-1.000000
028
02e B4: # B6 B5 <- B3 Freq: 0.999997
02e movq R11, RSI # spill
031 addq R11, #20 # ptr
035 movl [R11], RBP # compressed ptr
038 movl RBP, R10 # spill
03b decl RBP # int
03d andl RBP, RDX # int
03f movq R11, R11 # ptr -> long
03f shrq R11, #9
043 movq R8, 0x0000000106a67000 # ptr
04d movb [R8 + R11], R12 # short/char (R12_heapbase==0)
051 testl R10, R10
054 je B6 P=0.000001 C=-1.000000
054
05a B5: # N1 <- B4 Freq: 0.999996
05a movl R11, [RSI + #16 + RBP << #2] # compressed ptr
05f decode_heap_oop RAX,R11
0ee addq rsp, 48 # Destroy frame
popq rbp
testl rax, [rip + #offset_to_poll_page] # Safepoint: poll for GC
0f9 ret
0f9
0fa B6: # N1 <- B4 Freq: 1.01328e-06
0fa movq [rsp + #0], RSI # spill
0fe movl RSI, #-28 # int
103 call,static wrapper for: uncommon_trap(reason='range_check'
action='make_not_entrant')
# ArrayRangeCheck::foo2 @ bci:13 L[0]=_ L[1]=_ STK[0]=rsp + #0
STK[1]=RBP
# OopMap{[0]=Oop off=264}
108 int3 # ShouldNotReachHere
108
10d B7: # N1 <- B2 Freq: 9.99999e-07
10d movl [rsp + #0], RDX # spill
110 movq [rsp + #8], RSI # spill
115 movq [rsp + #16], RSI # spill
11a movl RSI, #-28 # int
11f call,static wrapper for: uncommon_trap(reason='range_check'
action='make_not_entrant')
# ArrayRangeCheck::foo2 @ bci:4 L[0]=rsp + #8 L[1]=rsp + #0
STK[0]=rsp + #16 STK[1]=#1 STK[2]=rsp + #8 STK[3]=#2
# OopMap{[8]=Oop [16]=Oop off=292}
124 int3 # ShouldNotReachHere
124
129 B8: # N1 <- B3 Freq: 9.99998e-07
129 movl [rsp + #8], RDX # spill
12d movq [rsp + #16], RSI # spill
132 movl RSI, #-42 # int
137 call,static wrapper for: uncommon_trap(reason='array_check'
action='maybe_recompile')
# ArrayRangeCheck::foo2 @ bci:5 L[0]=rsp + #16 L[1]=rsp + #8
STK[0]=rsp + #16 STK[1]=#1 STK[2]=RBP
# OopMap{rbp=NarrowOop [16]=Oop off=316}
13c int3 # ShouldNotReachHere
13c
141 B9: # N1 <- B1 Freq: 1.01328e-06
141 movl RSI, #-10 # int
nop # 1 bytes pad for loops and calls
147 call,static wrapper for: uncommon_trap(reason='null_check'
action='maybe_recompile')
# ArrayRangeCheck::foo2 @ bci:4 L[0]=_ L[1]=_ STK[0]=_ STK[1]=_
STK[2]=#NULL STK[3]=#2
# OopMap{off=332}
14c int3 # ShouldNotReachHere
14c
> Regards, Martin.
>
>
> On Thu, Feb 13, 2014 at 9:18 AM, Krystal Mok <rednaxelafx at gmail.com>wrote:
>
>> Hi John,
>>
>> Nice to hear from you!
>>
>> I ran a couple of tests on the patch, one of them is:
>>
>> public class ArrayRangeCheck {
>> private static Object foo(Object[] a, int x) throws Exception {
>> if (a.length == 0) throw new Exception();
>> return a[x & (a.length - 1)];
>> }
>>
>> public static void main(String[] args) throws Exception {
>> Object[] a = new Object[8];
>> foo(a, 6);
>> foo(a, 6);
>> System.in.read();
>> }
>> }
>>
>> Ran with:
>>
>> $ java -XX:CompileCommand="compileonly ArrayRangeCheck foo"
>> -XX:-TieredCompilation -XX:CICompilerCount=1 -XX:CompileThreshold=1
>> -XX:PrintIdealGraphLevel=4 -XX:PrintIdealGraphFile=ideal.xml
>> -XX:+PrintCompilation -XX:+PrintAssembly ArrayRangeCheck
>>
>> And confirmed that in this case the range check is indeed elided: there's
>> only one a.length != 0 check dominating the actual element load, and the
>> else branch goes to the exception throwing code.
>>
>> Thanks,
>> Kris
>>
>>
>> On Wed, Feb 12, 2014 at 9:47 PM, John Rose <john.r.rose at oracle.com>wrote:
>>
>>> One point behind the bug report is to give a little reward to Java
>>> coders who write dominating tests that exclude a.length==0, as:
>>>
>>> if (a.length == 0) goAway();
>>> else return a[i & a.length-1];
>>>
>>> Kris, can your patch do this? The logic in IfNode can probably elide
>>> the duplicate dominating test, if the right normalizations occur. ��
>>>
>>> – John
>>>
>>> On Feb 12, 2014, at 6:05 PM, Martin Grajcar <maaartinus at gmail.com>
>>> wrote:
>>>
>>> That's what I've meant with goAway. My point was the jump using already
>>> computed flags
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140213/80fc9474/attachment-0001.html
More information about the hotspot-compiler-dev
mailing list