1253544 - Baldr: Take away an indirection in loop backedges

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine: JIT, defect)

Description

[Benjamin Bouvier [:bbouvier] (inactive)]

Currently, in a Loop, all the blocks breaking to the top of the loop join to a single block which is going to be the backedge. In bug 1246116 comment 27, Luke says we can have all blocks being backedges themselves, avoiding the indirection.

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

I've started looking into that, but this is far from trivial:: a lot of places in Ion seem to assume that a loop header only has one single backedge, making this trip into random assertions (in AssertGraphCoherency, AssertExtendedGraphCoherency, etc.). nbp says it should be theoretically possible to have a loop header have several backedges, but this would mean changing assumptions all over the backend.

Moreover, Ion is capable of basic jump threading: if a Basic Block has no single instruction, it won't be emitted at all (there won't be a double jump) [0] [1]. So this means that we're just creating too many basic blocks. It might help with compilation time to create fewer of them, but not even sure about that outcome.

I've confirmed trivial blocks are not emitted with the following wasm code:

assertEq(wasmEvalText(`(module (func (result i32) (local i32)
  (loop
    $break $continue
    (if
      (i32.gt_u (get_local 0) (i32.const 5))
      (br $break)
    )
    (block
     (if
      (i32.gt_u (get_local 0) (i32.const 6))
      (br $continue)
     )
    )
    (set_local 0 (i32.add (get_local 0) (i32.const 1)))
    (br $continue)
  )
  (return (get_local 0))
) (export "" 0))`)(), 6);

which gets compiled into:

   0x7ffff7fe1020:	sub    $0x8,%rsp
   0x7ffff7fe1024:	xor    %eax,%eax
   0x7ffff7fe1026:	cmp    $0x5,%eax
   0x7ffff7fe1029:	ja     0x7ffff7fe1039
   0x7ffff7fe102f:	cmp    $0x6,%eax
   0x7ffff7fe1032:	ja     0x7ffff7fe1026
   0x7ffff7fe1034:	add    $0x1,%eax
   0x7ffff7fe1037:	jmp    0x7ffff7fe1026
   0x7ffff7fe1039:	xchg   %ax,%ax
   0x7ffff7fe103b:	add    $0x8,%rsp
   0x7ffff7fe103f:	retq   

although iongraph shows much more basic blocks (see attached file).

As a matter of fact, I don't think it's that valuable to add this optimization right now, so dumping my WIP patch here, and if anybody wants to take it over, please feel free.

[0] comment above isTrivial https://dxr.mozilla.org/mozilla-central/source/js/src/jit/LIR.h#1026-1027
[1] skipTrivialBlocks https://dxr.mozilla.org/mozilla-central/source/js/src/jit/shared/CodeGenerator-shared.h#346

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Previous function MIR before LIR generation.pdf

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: single-backedge.patch

Comment 4

[Lars T Hansen [:lth]]

A case for Cretonne, one assumes.