Consider rotating loops in IonBuilder

NEW
Unassigned

Status

()

Core
JavaScript Engine
P3
enhancement
5 years ago
2 years ago

People

(Reporter: sunfish, Unassigned)

Tracking

(Blocks: 1 bug, {perf})

Trunk
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

5 years ago
Following up on an observation in bug 881397, the add loop from misc-basic-intops.js looks like this on x64:

[Codegen] movabsq    $0x2ef3d78, %r11    # InterruptCheck
[Codegen] cmpl       $0x0, 0x0(%r11)
[Codegen] jne        ((564))
[Codegen] cmpl       %esi, %ecx          # Loop exit test
[Codegen] jge        ((572))
[Codegen] addl       %edi, %eax          # The add
[Codegen] jo         ((580))             # Overflow test
[Codegen] addl       $0x1, %ecx          # Induction var increment
[Codegen] jmp        ((588))

Would it be feasible to do loop rotation in IonBuilder? In other words, given "while (x) { body; }", just emit it as if it were "if (x) { do { body; } while (x); }", if x is small-ish.

This has the advantage of setting up a nice place for a preheader for LICM and it eliminates an unconditional branch in codegen (because the loop exit test can have a fall-through to exit the loop). For reference, GCC and LLVM both pretty aggressively transform loops to this form (GCC calls it header copying; -ftree-ch). Consequently, emscripten code will typically already be in this form, making this a common difference between asm.js code and regular JavaScript code.
(Reporter)

Updated

4 years ago
Duplicate of this bug: 733662
(Assignee)

Updated

4 years ago
Assignee: general → nobody
Loop rotation wouldn't be that easy. It should be possible but will require a lot of hacks.
We need to find the exact point where to split. During ion we make no difference between
the loop head and body anymore. As a result we will have to cleverly split and reverse the last condition.

Another solution that would give a lot of the benefits, except for the unconditional branch, is loop peeling.
With loop peeling you peel off the first iteration from the loop. As a result you also get a nice place,
after the first iteration and the full loop to have a preheader. That way LICM cannot hoist things in the non-loop path anymore.

V8 is already doing that and they seems to indicate it was important for them.
Blocks: 1307062
Keywords: perf
Priority: -- → P3
(In reply to Hannes Verschore [:h4writer] from comment #2)
> Another solution that would give a lot of the benefits, except for the
> unconditional branch, is loop peeling.
> With loop peeling you peel off the first iteration from the loop. As a
> result you also get a nice place,
> after the first iteration and the full loop to have a preheader. That way
> LICM cannot hoist things in the non-loop path anymore.

With loop-peeling LICM is no longer needed, as the work expected from LICM is already completed by GVN.
On the other hand, loop peeling is costly if the loop body contains hundreds of basic blocks.

Independently of the implementation choice, having a separated path which is guarantee to enter the loop & exit the loop is nice to have, especially if we want to Sink writes out of the loop bodies.
We discussed this a bit further online and it seems loop inverting/rotating would be the better approach.
It would give the same improvements with less duplication of graph blocks (less compilation time) and with possible removal of the unconditional jump.

> while(x) { body }

would get transformed to:

> if (x) {
>    [preheader]
>    do {
>        body
>    while(x);
> }

For loops that are already in that form:

> do { body } while(x)

We can still optimize. In ion we don't make a difference between the "body" and the condition. As a result this code will have to iterate the loop content to find a nice split between "body" and "x". For Ion the following loops will generate similar code:

> do { if (x) break; ... } while(x)
> while(x) { ... }

As a result if we generalize we could move the "if(x) break" outside the loop:

> if (x) {
>    [preheader]
>    do {
>        body
>    while(x);
> }

Generating the same optimization and making sure we have a better location for a preheader.

for do-while loops that don't have any breaks we will not be able to create a preheader for LICM. BUT that is not an issue! Since if there are no breaks in the body it means we will always execute that body once for certain. Hoisting isn't an issue in that case.
You need to log in before you can comment on or make changes to this bug.