JDK-8159016 : Over-unrolled loop is partially removed
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 9
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2016-06-08
  • Updated: 2019-04-15
  • Resolved: 2016-06-27
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 9
9 b131Fixed
Related Reports
Relates :  
JDK-6675699 - need comprehensive fix for unconstrained ConvI2L with narrowed type
Relates :  
JDK-8151573 - Multiversioning for range check elimination
Relates :  
JDK-8203915 - Induction variable of over-unrolled loop conflicts with range checks
Relates :  
JDK-8202949 - Over-unrolled loop with negative stride is partially removed
Relates :  
JDK-8222417 - compiler/loopopts/TestOverunrolling.java times out
Description
Nightly failure with Tiered off  compiler/escapeAnalysis/6726999/Test.java

#  Internal Error (hotspot/src/share/vm/opto/loopnode.cpp:3202), pid=21924, tid=25292
#  assert(!had_error) failed: bad dominance
#
# JRE version: Java(TM) SE Runtime Environment (9.0) (fastdebug build 9-internal+0-2016-06-06-233204.vkozlov.8156587)
# Java VM: Java HotSpot(TM) 64-Bit Server VM (fastdebug 9-internal+0-2016-06-06-233204.vkozlov.8156587, compiled mode, compressed oops, serial gc, windows-amd64)

-Xcomp -server -XX:-TieredCompilation -Xcomp -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -XX:+IgnoreUnrecognizedVMOptions -XX:-DoEscapeAnalysis -XX:+AggressiveOpts
Comments
Prototype fix: http://cr.openjdk.java.net/~thartmann/8159016/webrev.00/ I changed the implementation of IdealLoopTree::compute_exact_trip_count() to not only compute the exact trip count if the loop limit is constant but to also set the _trip_count field if we are able to determine an upper bound. The checks in IdealLoopTree::policy_unroll() then prevent additional loop unrolling if the trip_count became too small.
21-06-2016
I was able to reproduce this with a simple testcase: Object arr[] = new Object[3]; int lim = (arg & 3); for (int i = 0; i < lim; ++i) { arr[i] = new Object(); } The loop is split into pre, main and post loops. The pre loop is executed for at least one iteration, initializing arr[0]. The main loop is unrolled twice, initializing at least arr[1], arr[2], arr[3] and arr[4]. The arr[3] and arr[4] stores are always out of bounds and removed. However, C2 is unable to remove the "over-unrolled", dead main loop. As a result, there is a control path from the main loop to the PostScalarRce loop (see JDK-8151573) without a memory path since the last store was replaced by TOP. We crash because we use a memory edge from a non-dominating region. The out of bound stores in the over-unrolled loop are removed because their range check dependent CastII nodes are removed by the first optimization in CastIINode::Ideal(): CastII (AddI Phi 2) -> AddI (CastII Phi) 2 -> AddI TOP 2 The CastIINodes are replaced by TOP because the type of the loop Phi is >= 1 and the CastII is [1..2], i.e. there is no value >= 1 that is in the [1..2] range if +2 is added. The underlying problem is the over-unrolling of the loop. Since lim < 3, we always only execute at least 3 loop iterations. With the pre loop executing at least 1 iteration, the main loop should not be unrolled more than once. This problem is similar to JDK-4834191 where we over-unrolled a loop with constant limit.
21-06-2016
I'm now able to reproduce this on Linux as well (need to disable G1): java -XX:+ReplayCompiles -XX:+ReplayIgnoreInitErrors -XX:ReplayDataFile=replay_pid32516.log -XX:-UseG1GC -XX:+UseParallelGC
14-06-2016
I'm able to reproduce this on Windows with replay compilation: Bad graph detected in compute_lca_of_uses n: 690 Phi === 670 799 717 [[ 549 ]] #memory Memory: @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; !orig=616 early(n): 670 Region === 670 769 773 [[ 670 691 603 678 679 686 688 690 ]] n->in(1): 799 Phi === 769 493 716 [[ 690 ]] #memory Memory: @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; early(n->in(1)): 769 Region === 769 768 669 [[ 769 803 670 782 783 797 798 799 ]] n->in(1)->in(1): 493 StoreN === 514 521 496 505 [[ 521 456 717 799 752 467 ]] @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; Memory: @narrowoop: Point *[int:3]:NotNull:exact+any * [narrow], idx=4; !orig=215,673 !jvms: Test::test2_0_2 @ bci:28 early(n->in(1)->in(1)): 514 Proj === 510 [[ 491 493 495 506 515 ]] #0 !orig=132,[190],225 !jvms: Test::test2_0_2 @ bci:21 n->in(1)->in(2): 716 StoreN === 755 717 205 746 [[ 651 799 ]] @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; Memory: @narrowoop: Point *[int:3]:NotNull:exact[2] * [narrow], idx=4; !orig=215,673 !jvms: Test::test2_0_2 @ bci:28 early(n->in(1)->in(2)): 755 Proj === 751 [[ 710 716 725 747 648 ]] #0 !orig=132,[190],225 !jvms: Test::test2_0_2 @ bci:21 n->in(2): 717 StoreN === 741 493 720 731 [[ 711 716 690 ]] @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; Memory: @narrowoop: Point *[int:3]:NotNull:exact+any * [narrow], idx=4; !orig=633,215,673 !jvms: Test::test2_0_2 @ bci:28 early(n->in(2)): 741 Proj === 740 [[ 712 717 719 732 749 ]] #0 !orig=654,132,[190],225 !jvms: Test::test2_0_2 @ bci:21 n->in(2)->in(1): 493 StoreN === 514 521 496 505 [[ 521 456 717 799 752 467 ]] @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; Memory: @narrowoop: Point *[int:3]:NotNull:exact+any * [narrow], idx=4; !orig=215,673 !jvms: Test::test2_0_2 @ bci:28 early(n->in(2)->in(1)): 514 Proj === 510 [[ 491 493 495 506 515 ]] #0 !orig=132,[190],225 !jvms: Test::test2_0_2 @ bci:21 n->in(2)->in(2): 720 AddP === _ 59 721 200 [[ 717 719 ]] !orig=636,205 !jvms: Test::test2_0_2 @ bci:28 early(n->in(2)->in(2)): 741 Proj === 740 [[ 712 717 719 732 749 ]] #0 !orig=654,132,[190],225 !jvms: Test::test2_0_2 @ bci:21 n->in(2)->in(3): 731 EncodeP === _ 732 [[ 717 ]] #narrowoop: Point:NotNull:exact * !orig=[645],[214] !jvms: Test::test2_0_2 @ bci:28 early(n->in(2)->in(3)): 741 Proj === 740 [[ 712 717 719 732 749 ]] #0 !orig=654,132,[190],225 !jvms: Test::test2_0_2 @ bci:21 LCA(n): 603 Region === 603 602 670 [[ 603 617 530 607 608 612 614 ]] n->out(0): 549 Phi === 530 521 690 [[ 478 ]] #memory Memory: @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; later(n->out(0)): 530 Region === 530 529 603 [[ 530 550 465 537 538 545 547 549 ]] n->out(0)->out(0): 478 Phi === 465 456 549 [[ 142 ]] #memory Memory: @narrowoop: java/lang/Object *[int:>=0]+any * [narrow], idx=4; later(n->out(0)->out(0)): 465 Region === 465 464 530 [[ 465 479 138 468 469 474 476 478 ]] idom[0] 603 Region === 603 602 670 [[ 603 617 530 607 608 612 614 ]] idom[1] 736 Catch === 735 727 [[ 737 768 ]] !orig=664,122 !jvms: Test::test2_0_2 @ bci:21 idom[2] 735 Proj === 734 [[ 736 ]] #0 !orig=666,119 !jvms: Test::test2_0_2 @ bci:21 idom[3] 734 Allocate === 758 759 752 8 1 ( 116 115 29 1 10 11 59 62 764 1 59 764 ) [[ 726 727 729 730 733 735 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, top ) Test::test2_0_2 @ bci:21 !orig=648,118 !jvms: Test::test2_0_2 @ bci:21 idom[4] 758 CountedLoop === 758 558 230 [[ 734 753 754 758 759 760 764 ]] inner stride: 4 main of N758 !orig=[657],[406],[400],[107] !jvms: Test::test2_0_2 @ bci:18 idom[5] 558 IfTrue === 557 [[ 758 806 ]] #1 idom[6] 557 If === 553 556 [[ 527 558 ]] P=0.999999, C=-1.000000 idom[7] 553 IfFalse === 515 [[ 557 ]] #0 idom[8] 515 CountedLoopEnd === 514 489 [[ 516 553 ]] [lt] P=0.900000, C=-1.000000 !orig=405,[229] !jvms: Test::test2_0_2 @ bci:15 idom[9] 514 Proj === 510 [[ 491 493 495 506 515 ]] #0 !orig=132,[190],225 !jvms: Test::test2_0_2 @ bci:21 idom[10] 510 Initialize === 525 1 502 1 1 507 [[ 509 514 ]] !orig=131 !jvms: Test::test2_0_2 @ bci:21 idom[11] 525 CatchProj === 524 [[ 510 ]] #0@bci -1 !orig=123 !jvms: Test::test2_0_2 @ bci:21 idom[12] 524 Catch === 526 501 [[ 525 529 ]] !orig=122 !jvms: Test::test2_0_2 @ bci:21 idom[13] 526 Proj === 508 [[ 524 ]] #0 !orig=119 !jvms: Test::test2_0_2 @ bci:21 idom[14] 508 Allocate === 517 523 511 8 1 ( 116 115 29 1 10 11 59 62 520 1 59 520 ) [[ 500 501 503 504 507 526 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, top ) Test::test2_0_2 @ bci:21 !orig=118 !jvms: Test::test2_0_2 @ bci:21 idom[15] 517 CountedLoop === 517 106 516 [[ 508 512 513 517 520 521 522 523 ]] inner stride: 1 pre of N406 !orig=[406],[400],[107] !jvms: Test::test2_0_2 @ bci:18 idom[16] 106 IfTrue === 96 [[ 517 ]] #1 !jvms: Test::test2_0_2 @ bci:18 idom[17] 96 If === 93 95 [[ 97 106 ]] P=0.999999, C=-1.000000 !jvms: Test::test2_0_2 @ bci:18 idom[18] 93 IfTrue === 83 [[ 96 ]] #1 !jvms: Test::test2_0_2 @ bci:18 idom[19] 83 If === 415 82 [[ 84 93 ]] P=0.999999, C=-1.000000 !jvms: Test::test2_0_2 @ bci:18 idom[20] 415 IfTrue === 414 [[ 83 763 454 519 592 ]] #1 idom[21] 414 RangeCheck === 70 421 [[ 415 416 ]] P=0.999999, C=-1.000000 idom[22] 70 IfFalse === 68 [[ 414 ]] #0 !orig=[412] !jvms: Test::test2_0_2 @ bci:15 idom[23] 68 If === 56 67 [[ 69 70 ]] P=0.500000, C=-1.000000 !jvms: Test::test2_0_2 @ bci:15 idom[24] 56 Proj === 55 [[ 68 59 ]] #0 !jvms: Test::test2_0_2 @ bci:1 idom[25] 55 Initialize === 47 1 58 1 1 54 [[ 56 57 ]] !jvms: Test::test2_0_2 @ bci:1 idom[26] 47 CatchProj === 46 [[ 55 ]] #0@bci -1 !jvms: Test::test2_0_2 @ bci:1 idom[27] 46 Catch === 43 45 [[ 47 48 ]] !jvms: Test::test2_0_2 @ bci:1 idom[28] 43 Proj === 42 [[ 46 ]] #0 !jvms: Test::test2_0_2 @ bci:1 idom[29] 42 AllocateArray === 5 6 7 8 1 ( 40 24 29 23 10 11 1 1 1 1 ) [[ 43 44 45 52 53 54 ]] rawptr:NotNull ( int:>=0, java/lang/Object:NotNull *, bool, int ) Test::test2_0_2 @ bci:1 !jvms: Test::test2_0_2 @ bci:1 idom[30] 5 Parm === 3 [[ 42 ]] Control !jvms: Test::test2_0_2 @ bci:-1 *** Use 603 isn't dominated by def 690 *** It seems not to be caused by UseSuperWord but the following flags prevent the crash: -XX:-PostLoopMultiversioning -XX:-PartialPeelLoop -XX:LoopMaxUnroll=0 -XX:-RangeCheckElimination Could be caused by JDK-8151573. Investigating.
13-06-2016
Updated ILW = Assert, able to reproduce, -XX:-PostLoopMultiversioning = MHL = P3
13-06-2016
This happened two days ago and showed up twice. This could very well be a regression, so it's too early to defer to 10. Changing fix version back to 9.
10-06-2016
ILW = assert; single test on windows; none = MLH = P4
09-06-2016