Issue Details (XML | Word | Printable)

Key: RVM-412
Type: Bug Bug
Status: Closed Closed
Resolution: Fixed
Priority: Critical Critical
Assignee: Ian Rogers
Reporter: Ian Rogers
Votes: 0
Watchers: 0
Operations

If you were logged in you would be able to see more operations.
RVM

Latent branch optimization bug when maximizing blocks

Created: 19/Mar/08 05:59 PM   Updated: 09/May/08 09:39 AM
Component/s: Compiler: Optimizing
Affects Version/s: None
Fix Version/s: 2.9.3

Time Tracking:
Not Specified


 Description  « Hide
Eliminating get/set caught exception instructions has exposed latent bugs in the the HIR branch optimizations. In particular from lusearch:

Error trying to merge fall through in: < SystemAppCL, Lorg/apache/lucene/queryParser/QueryParserTokenManager; >.jjMoveNfa_3 (II)I
This block:
Basic block BB330
in: BB257, BB258, BB294, BB298, BB324, BB325, BB327, BB329
normal out: BB332
exceptional out: BB337 (catches java.io.IOException for BB261 BB268 BB286 BB289 BB298 BB325 BB326 BB329 BB330 BB334)
May throw uncaught exceptions, implicit edge to EXIT
In scope exception handlers: BB337 (catches java.io.IOException for BB261 BB268 BB286 BB289 BB298 BB325 BB326 BB329 BB330 BB334)
Next in code order: BB332
Instructions:
97: LABEL330
99: putfield l5746psi(I), t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000000, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferLength>, t5736psv(GUARD)
104: putfield l5746psi(I), t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000004, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferPosition>, t5736psv(GUARD)
109: getfield t6222si(I) = t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x0000000c, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferStart>, t5736psv(GUARD)
113: getfield t6223si(I) = t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000008, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.tokenStart>, t5736psv(GUARD)
116: int_add t6224si(I) = t6222si(I), t6223si(I)
117: putfield t6224si(I), t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x0000000c, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferStart>, t5736psv(GUARD)
122: putfield 0, t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000008, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.tokenStart>, t5736psv(GUARD)
126: getfield t6225sa(Ljava/io/Reader = t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000010, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.input>, t5736psv(GUARD)
130: getfield t9000sa([C) = t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0xfffffffc, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.buffer>, t5736psv(GUARD)
138: EG null_check t6228sv(GUARD) = t9000sa([C)
138: arraylength t6229si(I) = t9000sa([C), t6228sv(GUARD)
140: int_sub t6230si(I) = t6229si(I), l5746psi(I)
141: EG null_check t6234sv(GUARD) = t6225sa(Ljava/io/Reader
141: EG call l6235psi(I) AF CF OF PF ZF ESP = Addr 0x00000044,
virtual"< BootstrapCL, Ljava/io/Reader; >.read ([CII)I", t6234sv(GUARD), t6225sa(Ljava/io/Reader, t9000sa([C), l5746psi(I), t6230si(I) ESP
147: int_ifcmp t6236sv(GUARD) = l6235psi(I), -1, ==, LABEL337, Probability: 0.6666271
-1: bbend BB330

Successor block:
Basic block BB332
in: BB330
normal out: BB333
exceptional out: <none>
In scope exception handlers: BB337 (catches java.io.IOException for BB261 BB268 BB286 BB289 BB298 BB325 BB326 BB329 BB330 BB334)
Next in code order: BB333
Instructions:
160: LABEL332
162: getfield t6250si(I) = t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000000, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferLength>, t5736psv(GUARD)
166: int_add t6251si(I) = t6250si(I), l6235psi(I)
167: putfield t6251si(I), t5728psa(Lorg/apache/lucene/queryParser/FastCharStream;,d), Addr 0x00000000, <mem loc: Lorg/apache/lucene/queryParser/FastCharStream;.bufferLength>, t5736psv(GUARD)
-1: bbend BB332

Failing target: BB337 (catches java.io.IOException for BB261 BB268 BB286 BB289 BB298 BB325 BB326 BB329 BB330 BB334)
-13 LABEL0 (Infrequent) Frequency: 1.0
-2 EG ir_prologue l0psa(Lorg/apache/lucene/queryParser/QueryParserTokenManager;,x,d), l2si(I,d), l3pi(I,d) =
0 G yieldpoint_prologue
1 int_move l5pi(Z) = 0
6 putfield 33, l0psa(Lorg/apache/lucene/queryParser/QueryParserTokenManager;,x,d), Addr 0x00000018, <mem loc: Lorg/apache/lucene/queryParser/QueryParserTokenManager;.jjnewStateCnt>, <TRUEGUARD>
10 int_move l6pi(Z) = 1
13 getfield t3126sa([I) = l0psa(Lorg/apache/lucene/queryParser/QueryParserTokenManager;,x,d), Addr 0x00000008, <mem loc: Lorg/apache/lucene/queryParser/QueryParserTokenManager;.jjstateSet>, <TRUEGUARD>
18 EG null_check t3127sv(GUARD) = t3126sa([I)
18 EG bounds_check t3128sv(GUARD) = t3126sa([I), 0, t3127sv(GUARD)
18 guard_combine t3129sv(GUARD) = t3127sv(GUARD), t3128sv(GUARD)
18 int_astore l2si(I,d), t3126sa([I), 0, <mem loc: array < BootstrapCL, I >[]>, t3129sv(GUARD)
21 int_move l11pi(I) = 0x7fffffff
-1 bbend BB0 (ENTRY)

at [0x7176dc08] Lorg/jikesrvm/VM; _assertionFailure(Ljava/lang/String;Ljava/lang/String;)V at line 550
at [0x7176dc74] Lorg/jikesrvm/VM; _assert(ZLjava/lang/String;Ljava/lang/String;)V at line 533
at [0x7176dc74] Lorg/jikesrvm/VM; _assert(Z)V at line 511
at [0x7176dc74] Lorg/jikesrvm/compilers/opt/ir/BasicBlock; mergeFallThrough(Lorg/jikesrvm/compilers/opt/ir/IR;)Z at line 1594
at [0x7176dcac] Lorg/jikesrvm/compilers/opt/controlflow/BranchOptimizationDriver; maximizeBasicBlocks(Lorg/jikesrvm/compilers/opt/ir/IR;)V at line 223
at [0x7176dcac] Lorg/jikesrvm/compilers/opt/controlflow/BranchOptimizationDriver; perform(Lorg/jikesrvm/compilers/opt/ir/IR;Z)V at line 112
at [0x7176dcd0] Lorg/jikesrvm/compilers/opt/controlflow/BranchOptimizationDriver; perform(Lorg/jikesrvm/compilers/opt/ir/IR;)V at line 91
at [0x7176dd38] Lorg/jikesrvm/compilers/opt/driver/CompilerPhase; performPhase(Lorg/jikesrvm/compilers/opt/ir/IR;)V at line 205
at [0x7176dd94] Lorg/jikesrvm/compilers/opt/driver/OptimizationPlanAtomicElement; perform(Lorg/jikesrvm/compilers/opt/ir/IR;)V at line 89
at [0x7176ddfc] Lorg/jikesrvm/compilers/opt/driver/OptimizationPlanCompositeElement; perform(Lorg/jikesrvm/compilers/opt/ir/IR;)V at line 143
at [0x7176de40] Lorg/jikesrvm/compilers/opt/driver/CompilationPlan; execute()Lorg/jikesrvm/compilers/opt/ir/IR; at line 131
at [0x7176de68] Lorg/jikesrvm/compilers/opt/driver/OptimizingCompiler; compile(Lorg/jikesrvm/compilers/opt/driver/CompilationPlan;)Lorg/jikesrvm/compilers/common/VM_CompiledMethod; at line 224
at [0x7176dec4] Lorg/jikesrvm/compilers/common/VM_RuntimeCompiler; optCompile(Lorg/jikesrvm/classloader/VM_NormalMethod;Lorg/jikesrvm/compilers/opt/driver/CompilationPlan;)Lorg/jikesrvm/compilers/common/VM_CompiledMethod; at line 358
at [0x7176df44] Lorg/jikesrvm/compilers/common/VM_RuntimeCompiler; recompileWithOpt(Lorg/jikesrvm/compilers/opt/driver/CompilationPlan;)I at line 537
at [0x7176dfbc] Lorg/jikesrvm/adaptive/controller/VM_ControllerPlan; doRecompile()Lorg/jikesrvm/compilers/common/VM_CompiledMethod; at line 179
at [0x7176dfd8] Lorg/jikesrvm/adaptive/recompilation/VM_CompilationThread; run()V at line 53
at [0x7176e000] Lorg/jikesrvm/scheduler/VM_Thread; startoff()V at line 617

In other words BB330 has a normal out to BB337 but has no out edge, therefore its not safe to merge it with BB332 even though the branch optimizations are trying. The error is that a previous phase hasn't updated the out edges for BB330 correctly, probably as there is already an exceptional out to BB337.

 All   Comments   Work Log   Change History      Sort Order: Ascending order - Click to sort in descending order
[ Permlink | « Hide ]
Ian Rogers added a comment - 20/Mar/08 05:29 AM
This appears to be the cause of new regressions [1].

[1] http://jikesrvm.anu.edu.au/cattrack/results/rvmx86lnx32.anu.edu.au/perf/3152/regression_report


[ Permlink | « Hide ]
Ian Rogers added a comment - 20/Mar/08 06:35 AM
So the way we handle edges in basic blocks is horrid. If an edge is to a block marked as an exception handler then its an exception edge, if its not then its a normal edge. The problem that's arising is:

bb0
some PEI with an exception edge to BB2
if .. then bb3
end bb0
bb1:
t1 = new Throwable
set_caught_exception t1
goto bb2
end bb1
bb2:
t 2 = get_caught_exception
end bb2
bb3:
...

when we eliminate all the get/set and exception object creation this becomes:

bb0
some PEI with an exception edge to BB2
if .. then bb3
end bb0
bb1:
goto bb2
end bb1
bb2:
end bb2
bb3:
...

as bb0 and bb1 aren't exception handling blocks it appears safe to merge them:

bb0
some PEI with an exception edge to BB2
if .. then bb3
goto bb2
end bb0
bb2:
end bb2
bb3:
...

unfortunately we now have a normal edge to bb2 and an exceptional edge to bb2. When we ask for the normal outs we just see the edge to bb3, but we should see bb2 and bb3. Thinking there is just one normal out we then think we can do more optimizations to bb0.


[ Permlink | « Hide ]
Ian Rogers added a comment - 20/Mar/08 07:39 AM
So the simplest way to fix this is to add a flag to exception handler blocks that we make reachable via normal outs. When we iterate over the outs if any of the exception blocks have a normal in we check our blocks branch instructions to see if they are a normal out to that block. Its unclear to me want we want from the exceptional blocks reached from a block, we could discount a block from being reachable exception handler if it is reached by a normal out. I believe its conservative to consider it a reachable exception handler, so the block should remain in the set.

[ Permlink | « Hide ]
Ian Rogers added a comment - 20/Mar/08 08:57 AM
Patch committed in r14061.


Powered by a free Atlassian JIRA open source license for Codehaus. Try JIRA - bug tracking software for your team.
Atlassian JIRA the Professional Issue Tracker. (Enterprise Edition, Version: 3.13.1-#333) - Bug/feature request - Atlassian news - Contact Administrators