Closed Bug 1598548 Opened 1 year ago Closed 1 year ago

Consider changing bytecode for while/for-in/for-of/for loops to start with condition

Categories

(Core :: JavaScript Engine, task, P2)

task

Tracking

()

RESOLVED FIXED
mozilla73
Tracking Status
firefox73 --- fixed

People

(Reporter: jandem, Assigned: jandem)

References

Details

Attachments

(12 files)

47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review
47 bytes, text/x-phabricator-request
Details | Review

For most loops we emit bytecode like this:

  JSOP_GOTO entry

body:
  JSOP_LOOPHEAD
  ... body ...

entry:
  JSOP_LOOPENTRY
  ... condition ...
  JSOP_IFEQ / JSOP_IFNE body

Goal of this bug is to try changing that to:

start:
  JSOP_LOOPHEAD
  JSOP_LOOPENTRY
  ... condition ...
  JSOP_IFEQ / JSOP_IFNE end

  ... body ...
  JSOP_GOTO start

Benefits of this are:

  • Unifies loop structure because these loops become similar to do-while loops.
  • JSOP_LOOPENTRY will always follow JSOP_LOOPHEAD so we can remove it.
  • Will let us simplify IonBuilder more because it can then compile everything in order.

I wanted to remind myself of the general motivations of the original structure and found this to be a good resource: https://stackoverflow.com/questions/47783926/why-are-loops-always-compiled-into-do-while-style-tail-jump .

Many of those concerns are about really tight native loops and branch predictors. I don't think in the bytecode case that they are really concerns over the simplicity we gain in later JIT tiers. Having IonBuilder run only in forward bytecode order is a nice property for being able to reason about pruning and inlining.

Probably worth seeing if the extra opcode dispatch has any effect on blinterp perf, as well as ensuring Ion doesn't generate dumb code for very tight loops.

It might also be possible to get the best of both worlds by having bytecode use the simple-but-slightly-inefficient structure, and restructuring the loop as an Ion optimization.

(In reply to Iain Ireland [:iain] from comment #2)

It might also be possible to get the best of both worlds by having bytecode use the simple-but-slightly-inefficient structure, and restructuring the loop as an Ion optimization.

Agreed. If we ever want Ion to generate the more optimal loop structure it would probably be best to do it as a backend optimization.

Priority: -- → P2

I've been prototyping this a bit with --no-ion and I think it will work nicely. The BytecodeEmitter code for certain loops (for-in for example) becomes more natural when each iteration first checks the condition, then does something based on that, then jumps back.

The patch stack for this bug has a nice diffstat:

35 files changed, 443 insertions(+), 989 deletions(-)

The old code used the beforeLoopEntry bytecode pc, but this wasn't always
the correct pc and fixing that is a bit annoying (IonBuilder would have to
keep track of the last pc just for this).

Assignee: nobody → jdemooij

This changes all loops to have the following bytecode structure:

JSOP_LOOPHEAD
JSOP_LOOPENTRY
...condition/body...
JSOP_GOTO/JSOP_IFEQ/JSOP_IFNE

This simplifies IonBuilder a lot because it can use the do-while code path
for all loops. For-in loops are also a bit simpler now because they no longer
need to have the next enumerated value on the stack across the backedge.

Later patches in the stack wil fold JSOP_LOOPENTRY into JSOP_LOOPHEAD,
simplify the source notes more and remove more code from IonBuilder.

I verified stepping/breakpoints for the different loop types works in the
debugger the same way as before this patch.

Depends on D55624

All loops now have the same structure. A later patch in the stack
will remove this class.

Depends on D55625

All loops now use State::DoWhileLike so we can don't need to keep track of the
state anymore and can remove some more dead code.

Depends on D55626

In visitTestBackedge we can just get the backedge target from the
bytecode instruction.

Depends on D55628

This is necessary for the next patch: it will merge JSOP_LOOPHEAD
and JSOP_LOOPENTRY but that means there can be multiple callVMs for
that op and this confuses DebugModeOSR (interrupts can trigger debugger
recompilation).

Depends on D55630

Mechanical rename/merge for the most part.

When restarting a loop in IonBuilder, we skip the JSOP_LOOPHEAD so we
now re-add the interrupt check (this used to be done by JSOP_LOOPENTRY)
explicitly by calling emitLoopHeadInstructions.

Depends on D55631

It's now always called from IonBuilder::jsop_loophead.

Depends on D55632

This allows removing the source note offset in the next patch.

Depends on D55633

For now we still need the source note itself to determine the
stackPhiCount in IonBuilder. Hopefully we can fix that later.

Depends on D55634

Attachment #9113149 - Attachment description: Bug 1598548 part 1 - Use loop count from predecessor block for OSR preheader. r?nbp! → Bug 1598548 part 1 - Use hit count from predecessor block for OSR preheader. r?nbp!
Status: NEW → ASSIGNED

Now all loops use either JSOP_IFNE (do-while) or JSOP_GOTO (other loops).

Blocks: 1601599
Blocks: 1601604
Pushed by jdemooij@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/52040f1fc121
part 1 - Use hit count from predecessor block for OSR preheader. r=nbp
https://hg.mozilla.org/integration/autoland/rev/d9c4bffc6734
part 2 - Give all loops the same bytecode structure. r=arai,tcampbell
https://hg.mozilla.org/integration/autoland/rev/1daafcbd8d61
part 3 - Merge loop source note classes into one SrcNote::Loop class. r=arai
https://hg.mozilla.org/integration/autoland/rev/af7ff6a6bec7
part 4 - Remove LoopState::State and some dead code. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/f6e52413de60
part 5 - Remove loopEntry_ and loopHead_ fields from LoopState. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/6e8db5d48533
part 6 - Fold IonBuilder::startLoop into its only caller. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/ae0f08f9946c
part 7 - Add a RetAddrEntry::Kind for interrupt check callVM. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/e8049d20460f
part 8 - Fold JSOP_LOOPENTRY into JSOP_LOOPHEAD. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/5e678528c434
part 9 - Simplify IonBuilder::analyzeNewLoopTypes signature a bit. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/b4562da4b051
part 10 - Remove LoopState::successorStart_. r=tcampbell
https://hg.mozilla.org/integration/autoland/rev/df8387b1e96e
part 11 - Remove source note offset for loop backjump. r=arai,tcampbell
https://hg.mozilla.org/integration/autoland/rev/d07675191e79
part 12 - Don't treat JSOP_IFEQ as a backedge. r=arai
Regressions: 1602390

== Change summary for alert #24288 (as of Fri, 06 Dec 2019 04:10:15 GMT) ==

Improvements:

0.40% Base Content JS windows7-32 opt 3,029,654.67 -> 3,017,438.67
0.40% Base Content JS windows7-32-shippable opt 3,029,649.33 -> 3,017,412.00
0.37% Base Content JS windows10-64-shippable opt 3,950,116.00 -> 3,935,678.67
0.36% Base Content JS windows10-64-shippable-qr opt 3,950,072.00 -> 3,935,697.33
0.29% Base Content JS linux64-shippable opt 3,886,350.67 -> 3,875,265.33
0.29% Base Content JS macosx1014-64-shippable opt 3,887,807.33 -> 3,876,449.33
0.28% Base Content JS linux64 opt 3,886,436.00 -> 3,875,470.67
0.28% Base Content JS linux64-qr opt 3,886,439.33 -> 3,875,476.00
0.28% Base Content JS linux64-shippable-qr opt 3,886,428.00 -> 3,875,404.00

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=24288

Blocks: 1606074
You need to log in before you can comment on or make changes to this bug.