C1 crash in LinearScan::eliminate_spill_moves

Thu Feb 11 11:10:37 UTC 2021

>
> Why would there be 131073 indexes? Seems a tad excessive?
>

Some further analysis reveals what I think leads to the pathological case.
It's somehow tripped by replacing RETURNs with GOTOs

First a bit of context:

The agent instruments methods by injecting a local variable for each unique
line number of the line number table using a pair or ICONST_0, ISTORE N for
each line N:

    ICONST_0
    ISTORE 1
    [..]
    ICONST_0
    ISTORE N

This counter is then incremented at each line entry using IINC:

    IINC 1 1
    [..]
    IINC N 1

Finally, before each RETURN we report each line count by calling out ILOAD
X/ INVOKESTATIC (X):

    ILOAD 1
    INVOKESTATIC com/github/eirbjo/JDK8261235Reproducer.countVisits (I)V
    [..]
    ILOAD N
    INVOKESTATIC com/github/eirbjo/JDK8261235Reproducer.countVisits (I)V

This works nicely for methods with one (or a few) RETURNs. For methods with
many returns, the byte code size grows dramatically because the (ILOAD X,
INVOKESTATIC X) sequence is repeated  for every RETURN. (In the agent
actually uses INVOKEVIRTUAL instead, and the method takes the line number
as an additional argument, adding an extra bycode code to load or DUP the
receiver object and a ICONST/BIPUSH/SIPUSH to put the line number on the
stack).

Our example method (org.jaxen.saxpath.base.Verifier::isXMLLetter) has 206
line numbers and 358 IRETURNs.

Each ILOAD, INVOKESTATIC consumes 2 + 3 = 5 bytes. For isXMLLetter, that
means 1040 bytes per RETURN, adding up to a total of 372320 bytes for the
reporting part, bringing us well above the 64K byte code limit.

By replacing each RETURN with a GOTO, we can instead inject the 1040 bytes
only once, which is a considerable saving.

This of course changes the control flow graph of the method considerably,
which is what I think might be tripping up C1's register allocation.

I used -XX:TraceLinearScanLevel=1 to compare the compilations (without the
reporting for the RETURN case, since it would hit the 64K roof).

Here's a compilation using RETURNs:

  518   93       2       org.jaxen.saxpath.base.Verifier::isXMLLetter (5414
bytes)
----- linear-scan block order:
   0: B716    loop: -1  depth:  0                dom: NULL     sux: B717
   1: B717    loop: -1  depth:  0                dom: B716     preds: B716
    sux: B0
   2: B 0    loop: -1  depth:  0                dom: B717     preds: B717
  sux: B2 B1
       [..]
716: B 1    loop: -1  depth:  0                dom: B0     preds: B0

Compare this with a GOTO compilation:

  437   95       3       org.jaxen.saxpath.base.Verifier::isXMLLetter (6130
bytes)
----- linear-scan block order:
   0: B1106    loop: -1  depth:  0                dom: NULL     sux: B1107
   1: B1107    loop: -1  depth:  0                dom: B1106     preds:
B1106     sux: B0
   2: B 0    loop: -1  depth:  0                dom: B1107     preds: B1107
    sux: B2 B1
       [..]
716: B 1    loop: -1  depth:  0                dom: B0     preds: B0
sux: B3
717: B 3    loop: -1  depth:  0                dom: B0     preds: B1 B4 B6
B8 B10 B12 B14 B16 B18 B20 B22 B24 B26 B28 B30 B32 B34 B36 B38 B40 B42 B44
B46 B48 B50 B52 B54 B56 B58 B60 B62 B64 B66 B68 B70 B72 B74 B76 B78 B80 B82
B84 B86 B88 B90 B92 B94 B96 B98 B100 B102 B104 B106 B108 B110 B112 B114
B116 B118 B120 B122 B124 B126 B128 B130 B132 B134 B136 B138 B140 B142 B144
B146 B148 B150 B152 B154 B156 B158 B160 B162 B164 B166 B168 B170 B172 B174
B176 B178 B180 B182 B184 B186 B188 B190 B192 B194 B196 B198 B200 B202 B204
B206 B208 B210 B212 B214 B216 B218 B220 B222 B224 B226 B228 B230 B232 B234
B236 B238 B240 B242 B244 B246 B248 B250 B252 B254 B256 B258 B260 B262 B264
B266 B268 B270 B272 B274 B276 B278 B280 B282 B284 B286 B288 B290 B292 B294
B296 B298 B300 B302 B304 B306 B308 B310 B312 B314 B316 B318 B320 B322 B324
B326 B328 B330 B332 B334 B336 B338 B340 B342 B344 B346 B348 B350 B352 B354
B356 B358 B360 B362 B364 B366 B368 B370 B372 B374 B376 B378 B380 B382 B384
B386 B388 B390 B392 B394 B396 B398 B400 B402 B404 B406 B408 B410 B412 B414
B416 B418 B420 B422 B424 B426 B428 B430 B432 B434 B436 B438 B440 B442 B444
B446 B448 B450 B452 B454 B456 B458 B460 B462 B464 B466 B468 B470 B472 B474
B476 B478 B480 B482 B484 B486 B488 B490 B492 B494 B496 B498 B500 B502 B504
B506 B508 B510 B512 B514 B516 B518 B520 B522 B524 B526 B528 B530 B532 B534
B536 B538 B540 B542 B544 B546 B548 B550 B552 B554 B556 B558 B560 B562 B564
B566 B568 B570 B572 B574 B576 B578 B580 B582 B584 B586 B588 B590 B592 B594
B596 B598 B600 B602 B604 B606 B608 B610 B612 B614 B616 B618 B620 B622 B624
B626 B628 B630 B632 B634 B636 B638 B640 B642 B644 B646 B648 B650 B652 B654
B656 B658 B660 B662 B664 B666 B668 B670 B672 B674 B676 B678 B680 B682 B684
B686 B688 B690 B692 B694 B696 B698 B700 B702 B704 B706 B708 B710 B712 B714
B715

Notice the 717 line with 715 'preds'?

The next part of the trace shows 'Before Register Allocation', which looks
innocuous until we get to the 714 block:

B714 [5146, 5147] preds: B713 sux: B3
__id_Instruction___________________________________________
6454 label [label:0x00007fb855027ae0]
6456 move [metadata:0x0000000118878000|M] [R1643|M]
6458 add [Base:[R1643|M] Disp: 20320|J] [int:1|I] [Base:[R1643|M] Disp:
20320|J]
6460 move [int:1|I] [R1838|I]
6462 move [int:1|I] [R1837|I]

[..]     // move repeated 191 times!

6844 move [int:1|I] [R1646|I]
6846 move [int:1|I] [R1645|I]
6848 move [int:1|I] [R1644|I]
6850 branch [AL] [B3]

This then repeats for B715 and we get to B712:

B712 [5136, 5137] preds: B711 sux: B3
__id_Instruction___________________________________________
7250 label [label:0x00007fb8550274e0]
7252 move [metadata:0x0000000118878000|M] [R1840|M]
7254 add [Base:[R1840|M] Disp: 20264|J] [int:1|I] [Base:[R1840|M] Disp:
20264|J]
7256 move [int:1|I] [R1838|I]
7258 move [int:1|I] [R1837|I]
7260 move [int:1|I] [R1836|I]

And then in inverse order:

B710 [5123, 5124] preds: B709 sux: B3
(lots of moves)

B708 [5113, 5114] preds: B707 sux: B3
(lots of moves)
(continues for 4MBs)

B1 [624, 625] preds: B0 sux: B3
(lots of moves)

Finally, we get to B3 which actually seems to show some real code:

B3 [5157, 6129] preds: B1 B4 B6 B8 B10 B12 B14 B16 B18 B20 B22 B24 B26 B28
B30 B32 B34 B36 B38 B40 B42 B44 B46 B48 B50 B52 B54 B56 B58 B60 B62 B64 B66
B68 B70 B72 B74 B76 B78 B80 B82 B84 B86 B88 B90 B92 B94 B96 B98 B100 B102
B104 B106 B108 B110 B112 B114 B116 B118 B120 B122 B124 B126 B128 B130 B132
B134 B136 B138 B140 B142 B144 B146 B148 B150 B152 B154 B156 B158 B160 B162
B164 B166 B168 B170 B172 B174 B176 B178 B180 B182 B184 B186 B188 B190 B192
B194 B196 B198 B200 B202 B204 B206 B208 B210 B212 B214 B216 B218 B220 B222
B224 B226 B228 B230 B232 B234 B236 B238 B240 B242 B244 B246 B248 B250 B252
B254 B256 B258 B260 B262 B264 B266 B268 B270 B272 B274 B276 B278 B280 B282
B284 B286 B288 B290 B292 B294 B296 B298 B300 B302 B304 B306 B308 B310 B312
B314 B316 B318 B320 B322 B324 B326 B328 B330 B332 B334 B336 B338 B340 B342
B344 B346 B348 B350 B352 B354 B356 B358 B360 B362 B364 B366 B368 B370 B372
B374 B376 B378 B380 B382 B384 B386 B388 B390 B392 B394 B396 B398 B400 B402
B404 B406 B408 B410 B412 B414 B416 B418 B420 B422 B424 B426 B428 B430 B432
B434 B436 B438 B440 B442 B444 B446 B448 B450 B452 B454 B456 B458 B460 B462
B464 B466 B468 B470 B472 B474 B476 B478 B480 B482 B484 B486 B488 B490 B492
B494 B496 B498 B500 B502 B504 B506 B508 B510 B512 B514 B516 B518 B520 B522
B524 B526 B528 B530 B532 B534 B536 B538 B540 B542 B544 B546 B548 B550 B552
B554 B556 B558 B560 B562 B564 B566 B568 B570 B572 B574 B576 B578 B580 B582
B584 B586 B588 B590 B592 B594 B596 B598 B600 B602 B604 B606 B608 B610 B612
B614 B616 B618 B620 B622 B624 B626 B628 B630 B632 B634 B636 B638 B640 B642
B644 B646 B648 B650 B652 B654 B656 B658 B660 B662 B664 B666 B668 B670 B672
B674 B676 B678 B680 B682 B684 B686 B688 B690 B692 B694 B696 B698 B700 B702
B704 B706 B708 B710 B712 B714 B715
__id_Instruction___________________________________________
148938 label [label:0x00007fb854776bd0]
148940 profile_call isXMLLetter.org/jaxen/saxpath/base/Verifier @ 5158
[R2196|M]  [R2197|J]
148942 move [metadata:0x000000011886d478|M] [R2198|M]
148944 move [Base:[R2198|M] Disp: 284|I] [R2199|I]
148946 add [R2199|I] [int:2|I] [R2199|I]
148948 move [R2199|I] [Base:[R2198|M] Disp: 284|I]
148950 logic_and [R2199|I] [int:2097150|I] [R2199|I]
148952 cmp [EQ] [R2199|I] [int:0|I]
148954 branch [EQ] [CounterOverflowStub: 0x00007fb85715f4d0]
[etc..].

The output then continues with a wall of text which makes a beautiful
pattern if I get my terminal width exactly right, but otherwise makes no
sense to me :-)

Here's hoping that this analysis may be of some use.

Cheers,
Eirik.