https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126236
Bug ID: 126236
Summary: Switch-based interpreter loops should be automatically
transformed to avoid shared indirect dispatch
Product: gcc
Version: 16.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: ktkachov at gcc dot gnu.org
Target Milestone: ---
Created attachment 65025
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65025&action=edit
Motivating reproducer
Portable bytecode interpreters commonly put a dense switch at the header of
an execution loop. An instruction handler here means the source-level path
for one virtual-machine opcode, normally one `case` body. A continuing
handler performs its operation and reaches the switch again to select the
next opcode.
Current GCC lowers this shape to one shared jump-table dispatch. Every
continuing handler branches back to the shared dispatch block, and all opcode
transitions therefore use the same indirect branch instruction:
+-------------------------+
| shared switch dispatch |
| load opcode, range test |
| table lookup, br |
+------------+------------+
|
+-----------------------+-----------------------+
| | |
v v v
case 1 handler case 2 handler default handler
| | |
+-----------------------+-----------------------+
|
+---- back to dispatch
The equivalent GNU labels-as-values form is treated differently. GCC's
existing late computed-goto duplication unfactors the small dispatch block
into its continuing predecessors. The case operations are not copied. Each
continuing handler instead gets a local dispatch copy and therefore a distinct
indirect branch PC:
```
case 1 handler case 2 handler default handler
| | |
v v v
local dispatch 1 local dispatch 2 local dispatch D
| br | br | br
+-----------------------+-----------------------+
|
next handler
```
The attached testcase contains semantically equivalent switch and
labels-as-values interpreters. The 12 explicit values are
enough for normal AArch64 jump-table lowering.
It can be compiled with -O3.
The switch-lowering dump records a dense jump-table cluster selected by
normal AArch64 lowering:
```
JT(values:12 comparisons:12 range:12 density: 100.00%):0-11
```
The resulting functions have these static properties:
| Function | Instructions | Direct redispatch `b` | Conditional branches
| Indirect `br` sites |
| --- | ---: | ---: | ---:
| ---: |
| `switch_interp` | 75 | 11 | 2
| 1 |
| `goto_interp` | 121 | 0 | 0
| 13 |
The 13 computed-goto sites are the entry dispatch plus one local dispatch for
each of the 12 continuing handlers. The `compgotos` dump reports 13
duplications for `goto_interp` and none for `switch_interp`.
Current switch lowering has a branch back to one shared dispatch:
.L15:
ldr w2, [x1]
add x0, x0, 1
add w2, w2, 1
str w2, [x1]
b .L20
.L20:
ldrb w2, [x0]
cmp w2, 11
bhi .L3
.L19:
ldrb w2, [x3,w2,uxtw]
adr x4, .Lrtx5
add x2, x4, w2, sxtb #2
br x2
```
The equivalent labels-as-values handler has a local dispatch copy:
.L24:
ldr w2, [x1]
add w2, w2, 1
str w2, [x1]
ldrb w2, [x0], 1
cmp w2, 12
csel w2, w2, w4, ls
and w2, w2, 255
ldr x2, [x3, w2, sxtw 3]
br x2
Following the handler store, the switch redispatch executes eight
instructions containing three branch instructions on an in-range continuing
path. The computed-goto control executes six instructions containing one
branch instruction. More importantly for indirect-branch prediction, the
switch sends every transition through one `br` PC, while the unfactored form
has a path-local `br` PC for each handler.
This is a speed versus size tradeoff. In this testcase the unfactored control
has more static instructions, and its 13-entry pointer table is larger than
the switch's compact 12-byte table. The opportunity is therefore relevant
where speed is preferred and the growth is profitable. Any implementation
must account for the size cost and avoid duplicating handler bodies.
GCC already performs the required late unfactoring for a generic computed
goto in `pass_duplicate_computed_gotos`, introduced for GCC PR15242. The
current `computed_jump_p` contract explicitly excludes tablejumps and `casesi`
instructions, so an ordinary lowered switch cannot reach that mechanism.
Doing this transformation automatically would improve 714.cpython_r from
SPEC2026, but there are also other interpreters out there that would benefit.
In my research I also found mawk
