Bad graph detected in build_loop_late but I have no clue
Liu, Xin
xxinliu at amazon.com
Fri Oct 23 10:42:39 UTC 2020
Hi, hotspot developers,
I am debugging a structural problem caused by https://github.com/openjdk/jdk/pull/704
So far, I know that 2 cases both crash at PhaseIdealLoop::build_loop_late_post() where MaxLoopUnrolling happens for EA.
That algorithm looks very similar to 2.3 Schedule Late and 2.4 Selecting a Block[1].
Isn’t that paper describe global code motion? Is build_loop_early/late() actually doing code motion before real loop optimizations?
In particular, I don’t understand this statement.
set_ctrl(n, least);
Is this set_ctrl(Y, X) saying Y control dependent on X. The definition of control dependence is in [2]?
So far, I found that PhaseIdealLoop::_nodes[IDX] can be any of 3 different values.
1. NULL, which means IDX is dead.
2. A CFG node with the lowest bit set. Assigned by set_ctrl.
3. IdealLoopTree*, when this node is the head of a loop.
Do I understand this data-structure right? So PhaseIdealLoop doesn’t have “BasicBlocks” and it uses _nodes to mark where a node belongs to?
I understand that (legal->is_Start() && !early->is_Root()) is a legit assertion, I believe I mess up the ideal graph somewhere and cause this fiasco.
Could you give me a pointer which node is broken? Or, could you share me with some hints how to debug this kind of problem?
Thank you in advance!
--lx
[1] Click, Cliff. "Global code motion/global value numbering." Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation. 1995.
[2] Ferrante, Jeanne, Karl J. Ottenstein, and Joe D. Warren. "The program dependence graph and its use in optimization." ACM Transactions on Programming Languages and Systems (TOPLAS) 9.3 (1987): 319-349.
Bad graph detected in build_loop_late
n: 797 Bool === _ 1080 [[ 520 521 ]] [ne] !jvms: Handler::checkNestedProtocol @ bci:7 Handler::parseURL @ bci:94
early(n): 535 CallStaticJava === 519 174 240 53 1 ( 249 214 247 1 1 1 1 248 1 1 1 1 1 1 1 1 249 484 1 1 ) [[ 898 395 715 265 ]] # Static java.net.URL::getFile java/lang/String:exact * ( java/net/URL:NotNull:exact * ) Handler::parseContextSpec @ bci:1 Handler::parseURL @ bci:137 !jvms: String::regionMatches @ bci:30 Handler::parseURL @ bci:75
n->in(1): 1080 CmpP === _ 265 208 [[ 797 ]] !jvms: String::lastIndexOf @ bci:8 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
early(n->in(1)): 535 CallStaticJava === 519 174 240 53 1 ( 249 214 247 1 1 1 1 248 1 1 1 1 1 1 1 1 249 484 1 1 ) [[ 898 395 715 265 ]] # Static java.net.URL::getFile java/lang/String:exact * ( java/net/URL:NotNull:exact * ) Handler::parseContextSpec @ bci:1 Handler::parseURL @ bci:137 !jvms: String::regionMatches @ bci:30 Handler::parseURL @ bci:75
n->in(1)->in(1): 265 Proj === 535 [[ 960 150 758 1080 516 516 128 138 202 203 130 141 139 149 ]] #5 Oop:java/lang/String:exact * !jvms: Handler::parseURL @ bci:41
early(n->in(1)->in(1)): 535 CallStaticJava === 519 174 240 53 1 ( 249 214 247 1 1 1 1 248 1 1 1 1 1 1 1 1 249 484 1 1 ) [[ 898 395 715 265 ]] # Static java.net.URL::getFile java/lang/String:exact * ( java/net/URL:NotNull:exact * ) Handler::parseContextSpec @ bci:1 Handler::parseURL @ bci:137 !jvms: String::regionMatches @ bci:30 Handler::parseURL @ bci:75
n->in(1)->in(2): 208 ConP === 0 [[ 154 154 831 1657 1052 109 1053 111 112 112 384 384 709 709 1015 1015 2138 2239 518 1014 1014 113 1063 114 385 1013 1065 115 342 1066 116 1069 117 1013 1070 118 703 678 1077 120 1080 122 1012 123 1085 124 1087 126 1953 201 2153 1492 616 129 703 1826 1102 134 1012 1148 152 151 1153 1656 1114 140 2165 1968 704 703 1121 142 704 2176 1982 1126 143 1131 144 1132 145 704 148 127 ]] #NULL !jvms: StringLatin1::indexOf @ bci:32 String::indexOf @ bci:13 Handler::parseURL @ bci:11
early(n->in(1)->in(2)): 0 Root === 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 [[ 0 1 110 208 209 207 1009 235 236 810 1092 339 772 283 213 1699 861 238 237 1664 2017 1726 938 242 241 268 943 255 2147 1424 971 2156 280 285 275 263 1889 2250 297 1696 1697 340 944 1248 2093 2246 2229 1706 479 1021 1556 1798 1383 ]]
LCA(n): 1291 Region === 1291 1456 1457 1458 1459 [[ 1291 1583 1079 ]] !jvms: Handler::parseContextSpec @ bci:131 Handler::parseURL @ bci:137
n->out(0): 520 If === 796 797 [[ 959 250 ]] P=0.999999, C=-1.000000 !jvms: String::coder @ bci:-1 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
n->out(0)->out(0): 959 IfTrue === 520 [[ 684 960 ]] #1 !jvms: Handler::parseContextSpec @ bci:23 Handler::parseURL @ bci:137
n->out(0)->out(1): 250 IfFalse === 520 [[ 122 ]] #0 !jvms: Handler::parseURL @ bci:32
n->out(1): 521 If === 798 797 [[ 801 252 ]] P=0.999999, C=-1.000000 !jvms: String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
n->out(1)->out(0): 801 IfTrue === 521 [[ 525 758 ]] #1 !jvms: Handler::checkNestedProtocol @ bci:7 Handler::parseURL @ bci:94
n->out(1)->out(1): 252 IfFalse === 521 [[ 123 ]] #0 !jvms: Handler::parseURL @ bci:32
idoms of early 535:
idom[0] 535 CallStaticJava === 519 174 240 53 1 ( 249 214 247 1 1 1 1 248 1 1 1 1 1 1 1 1 249 484 1 1 ) [[ 898 395 715 265 ]] # Static java.net.URL::getFile java/lang/String:exact * ( java/net/URL:NotNull:exact * ) Handler::parseContextSpec @ bci:1 Handler::parseURL @ bci:137 !jvms: String::regionMatches @ bci:30 Handler::parseURL @ bci:75
idom[1] 519 IfTrue === 514 [[ 535 249 ]] #1 !jvms: String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[2] 514 If === 791 792 [[ 519 243 ]] P=0.999999, C=-1.000000 !jvms: String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[3] 791 IfFalse === 1076 [[ 514 ]] #0 !jvms: Handler::checkNestedProtocol @ bci:7 Handler::parseURL @ bci:94
idom[4] 1076 If === 1289 1290 [[ 880 791 ]] P=0.000000, C=127.000000 !jvms: String::lastIndexOf @ bci:8 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
idom[5] 1289 IfFalse === 957 [[ 1076 ]] #0 !jvms: Handler::parseContextSpec @ bci:131 Handler::parseURL @ bci:137
idom[6] 957 If === 1187 1188 [[ 681 1289 ]] P=0.000000, C=127.000000 !jvms: Handler::parseContextSpec @ bci:23 Handler::parseURL @ bci:137
idom[7] 1187 IfFalse === 513 [[ 957 ]] #0 !orig=[5623] !jvms: Handler::parseURL @ bci:137
idom[8] 513 If === 789 790 [[ 239 1187 ]] P=0.900000, C=-1.000000 !jvms: String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[9] 789 CatchProj === 352 [[ 513 ]] #0 at bci -1 !jvms: Handler::checkNestedProtocol @ bci:7 Handler::parseURL @ bci:94
idom[10] 352 Catch === 627 174 [[ 789 160 ]] !jvms: Handler::parseURL @ bci:51
idom[11] 627 Proj === 393 [[ 352 ]] #0 !jvms: String::regionMatches @ bci:-1 Handler::parseURL @ bci:75
idom[12] 393 CallStaticJava === 676 233 234 53 1 ( 484 235 236 237 236 238 214 247 677 1 1 678 248 1 679 680 1 1 1 1 1 1 ) [[ 627 174 240 1288 ]] # Static java.lang.String::regionMatches bool ( java/lang/String:NotNull:exact *, int, int, java/lang/String:exact *, int, int ) Handler::checkNestedProtocol @ bci:7 Handler::parseURL @ bci:94 !jvms: Handler::parseURL @ bci:61
idom[13] 676 IfTrue === 508 [[ 393 484 ]] #1 !jvms: String::regionMatches @ bci:98 Handler::parseURL @ bci:75
idom[14] 508 If === 509 784 [[ 676 232 ]] P=0.999999, C=-1.000000 !jvms: String::length @ bci:4 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[15] 509 Region === 509 785 786 [[ 509 677 233 234 508 ]] !jvms: String::length @ bci:4 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[16] 1451 If === 1578 1579 [[ 1358 1283 ]] P=0.900000, C=-1.000000 !jvms: String::length @ bci:4 Handler::indexOfBangSlash @ bci:1 Handler::parseURL @ bci:144
idom[17] 1578 CatchProj === 623 [[ 1451 ]] #0 at bci -1 !jvms: String::lastIndexOf @ bci:28 Handler::indexOfBangSlash @ bci:9 Handler::parseURL @ bci:144
idom[18] 623 Catch === 894 389 [[ 1578 348 ]] !jvms: String::coder @ bci:6 String::regionMatches @ bci:70 Handler::parseURL @ bci:75
idom[19] 894 Proj === 672 [[ 623 ]] #0 !jvms: Handler::parseContextSpec @ bci:1 Handler::parseURL @ bci:137
idom[20] 672 CallStaticJava === 940 253 254 53 1 ( 217 210 941 214 247 1 1 1 678 248 1 679 680 1 1 1 1 264 217 210 941 1 ) [[ 894 389 511 ]] # Static java.lang.String::checkBoundsBeginEnd void ( int, int, int ) String::substring @ bci:8 Handler::parseURL @ bci:88 !jvms: String::regionMatches @ bci:98 Handler::parseURL @ bci:75
idom[21] 940 IfTrue === 531 [[ 672 1507 ]] #1 !jvms: Handler::parseContextSpec @ bci:15 Handler::parseURL @ bci:137
idom[22] 531 If === 522 559 [[ 940 261 ]] P=0.999999, C=-1.000000 !jvms: String::coder @ bci:14 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[23] 522 Region === 522 799 800 [[ 522 531 253 254 680 760 ]] !jvms: String::coder @ bci:3 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[24] 1081 If === 1293 1294 [[ 799 1462 ]] P=0.000000, C=127.000000 !jvms: String::lastIndexOf @ bci:8 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
idom[25] 1293 IfTrue === 507 [[ 1081 1784 ]] #1 !jvms: Handler::parseContextSpec @ bci:131 Handler::parseURL @ bci:137
idom[26] 507 If === 533 783 [[ 1293 231 ]] P=0.999999, C=-1.000000 !jvms: String::length @ bci:4 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[27] 533 IfTrue === 503 [[ 507 264 ]] #1 !jvms: String::length @ bci:-1 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[28] 503 If === 504 780 [[ 533 228 ]] P=0.999999, C=-1.000000 !jvms: String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[29] 504 Region === 504 781 782 [[ 504 503 229 230 534 248 679 247 678 ]] !jvms: String::length @ bci:1 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[30] 1060 If === 935 1277 [[ 1067 773 ]] P=1.000000, C=127.000000 !jvms: String::length @ bci:6 String::lastIndexOf @ bci:3 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
idom[31] 935 Region === 935 1170 1171 [[ 935 1060 667 ]] !jvms: Handler::parseContextSpec @ bci:11 Handler::parseURL @ bci:137
idom[32] 1350 If === 500 1282 [[ 1170 1171 ]] P=1.000000, C=127.000000 !jvms: Handler::parseContextSpec @ bci:143 Handler::parseURL @ bci:137
idom[33] 500 Region === 500 774 775 [[ 500 1350 222 223 932 ]] !jvms: String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[34] 931 If === 493 1165 [[ 662 765 ]] P=0.000000, C=147.000000 !jvms: Handler::parseContextSpec @ bci:11 Handler::parseURL @ bci:137
idom[35] 493 IfTrue === 489 [[ 931 216 ]] #1
idom[36] 489 If === 763 764 [[ 493 204 ]] P=0.999999, C=-1.000000 !jvms: String::regionMatches @ bci:21 Handler::parseURL @ bci:75
idom[37] 763 Parm === 110 [[ 489 ]] Control !jvms: Handler::parseURL @ bci:88
idoms of (wrong) LCA 1291:
idom[0] 1291 Region === 1291 1456 1457 1458 1459 [[ 1291 1583 1079 ]] !jvms: Handler::parseContextSpec @ bci:131 Handler::parseURL @ bci:137
idom[1] 1490 If === 1604 1605 [[ 1457 1333 ]] P=0.500000, C=-1.000000 !jvms: String::lastIndexOf @ bci:1 Handler::indexOfBangSlash @ bci:9 Handler::parseURL @ bci:144
idom[2] 1604 IfTrue === 760 [[ 1490 1991 ]] #1 !jvms: Handler::indexOfBangSlash @ bci:15 Handler::parseURL @ bci:144
idom[3] 760 If === 522 559 [[ 1604 486 ]] P=0.999999, C=-1.000000 !jvms: Handler::parseURL @ bci:88
idom[4] 522 Region === 522 799 800 [[ 522 531 253 254 680 760 ]] !jvms: String::coder @ bci:3 String::length @ bci:6 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[5] 1081 If === 1293 1294 [[ 799 1462 ]] P=0.000000, C=127.000000 !jvms: String::lastIndexOf @ bci:8 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
idom[6] 1293 IfTrue === 507 [[ 1081 1784 ]] #1 !jvms: Handler::parseContextSpec @ bci:131 Handler::parseURL @ bci:137
idom[7] 507 If === 533 783 [[ 1293 231 ]] P=0.999999, C=-1.000000 !jvms: String::length @ bci:4 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[8] 533 IfTrue === 503 [[ 507 264 ]] #1 !jvms: String::length @ bci:-1 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[9] 503 If === 504 780 [[ 533 228 ]] P=0.999999, C=-1.000000 !jvms: String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[10] 504 Region === 504 781 782 [[ 504 503 229 230 534 248 679 247 678 ]] !jvms: String::length @ bci:1 String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[11] 1060 If === 935 1277 [[ 1067 773 ]] P=1.000000, C=127.000000 !jvms: String::length @ bci:6 String::lastIndexOf @ bci:3 Handler::parseContextSpec @ bci:72 Handler::parseURL @ bci:137
idom[12] 935 Region === 935 1170 1171 [[ 935 1060 667 ]] !jvms: Handler::parseContextSpec @ bci:11 Handler::parseURL @ bci:137
idom[13] 1350 If === 500 1282 [[ 1170 1171 ]] P=1.000000, C=127.000000 !jvms: Handler::parseContextSpec @ bci:143 Handler::parseURL @ bci:137
idom[14] 500 Region === 500 774 775 [[ 500 1350 222 223 932 ]] !jvms: String::regionMatches @ bci:27 Handler::parseURL @ bci:75
idom[15] 931 If === 493 1165 [[ 662 765 ]] P=0.000000, C=147.000000 !jvms: Handler::parseContextSpec @ bci:11 Handler::parseURL @ bci:137
idom[16] 493 IfTrue === 489 [[ 931 216 ]] #1
idom[17] 489 If === 763 764 [[ 493 204 ]] P=0.999999, C=-1.000000 !jvms: String::regionMatches @ bci:21 Handler::parseURL @ bci:75
idom[18] 763 Parm === 110 [[ 489 ]] Control !jvms: Handler::parseURL @ bci:88
More information about the hotspot-compiler-dev
mailing list