733353 - IonMonkey: LICM: Use a linked list for the work list

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Loop::insertInWorklist shows up in a profile of SS crypto-md5, because it adds instructions to the front of a vector. I think the easiest fix is to use a linked list.

Comment 1

[Jan de Mooij [:jandem]]

Wow I forgot all about this bug after I filed it > 2 years ago. Thanks for taking it!

Comment 2

[Dan Gohman [:sunfish]]

Attachment: licm-move-preserves-id.patch

MBasicBlock::insertBefore assigns the inserted instruction a new id number, so avoid using it when moving an existing instruction, to avoid needless id number churn.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: licm-loop-marking-unmarking.patch

Factor out code for marking loop blocks, since it's needed in several places, and optimize it to avoid using a worklist, taking advantage of IonMonkey's built-in RPO.

Comment 4

[Dan Gohman [:sunfish]]

The previous patch depends on make-loops-contiguous.patch in bug 844779, which will hopefully land soon.

Comment 5

[Dan Gohman [:sunfish]]

Attachment: licm.patch

Rewrite LICM to eliminate both the worklist and the queue, by taking advantage of IonMonkey's builtin RPO.

Comment 6

[Dan Gohman [:sunfish]]

These patches speed up asm.js compile time on sqlite by about 8% on my machine.

Comment 7

[Luke Wagner [:luke]]

Impressive.

Comment 8

[Jan de Mooij [:jandem]]

Comment on attachment 8434267 [details] [diff] [review]
licm-move-preserves-id.patch

Review of attachment 8434267 [details] [diff] [review]:
-----------------------------------------------------------------

I had no idea we were renumbering them, but this could explain the weird numbering I've seen sometimes.

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 8434276 [details] [diff] [review]
licm-loop-marking-unmarking.patch

Review of attachment 8434276 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/IonAnalysis.cpp
@@ +2574,5 @@
> +    MBasicBlock *backedge = header->backedge();
> +    backedge->mark();
> +    size_t numMarked = 1;
> +    for (PostorderIterator i = graph.poBegin(backedge); ; ++i) {
> +        JS_ASSERT(i != graph.poEnd());

Nit: MOZ_ASSERT for consistency.

@@ +2603,5 @@
> +jit::UnmarkLoopBlocks(MIRGraph &graph, MBasicBlock *header)
> +{
> +    MBasicBlock *backedge = header->backedge();
> +    for (ReversePostorderIterator i = graph.rpoBegin(header); ; ++i) {
> +        JS_ASSERT(i != graph.rpoEnd());

Same here.

Comment 10

[Jan de Mooij [:jandem]]

Comment on attachment 8434282 [details] [diff] [review]
licm.patch

Review of attachment 8434282 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great! Nice perf win too.

Probably good to test Kraken and Octane too before landing to make sure there are no significant/silly perf regressions.

::: js/src/jit/LICM.cpp
@@ +40,3 @@
>  
> +/// Test whether the given instruction is inside the loop (and thus not
> +/// loop-invariant).

Nit: we don't use these ///-comments anywhere else; could you change all of them to // ?

@@ +48,5 @@
>  
> +/// Test whether the given instruction is cheap and not worth hoisting unless
> +/// one of its users will be hoisted as well.
> +static bool
> +RequiresHoistedUse(const MDefinition *ins, bool calls)

Nit: could you rename "bool calls" to hasCalls/containsCalls/makesCalls/etc, something a little more bool-ish?

@@ +128,5 @@
>      // TODO: determine if instructions within this block are worth hoisting.
>      // They might not be if the block is cold enough within the loop.
>      // BUG 669517
>      return true;
>  }

Feel free to just remove this. I don't really mind keeping it though.

Comment 11

[Dan Gohman [:sunfish]]

(In reply to Jan de Mooij [:jandem] from comment #10)
> Comment on attachment 8434282 [details] [diff] [review]
> licm.patch
> 
> Review of attachment 8434282 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Looks great! Nice perf win too.
> 
> Probably good to test Kraken and Octane too before landing to make sure
> there are no significant/silly perf regressions.
> 
> ::: js/src/jit/LICM.cpp
> @@ +40,3 @@
> >  
> > +/// Test whether the given instruction is inside the loop (and thus not
> > +/// loop-invariant).
> 
> Nit: we don't use these ///-comments anywhere else; could you change all of
> them to // ?

Fixed.

> @@ +48,5 @@
> >  
> > +/// Test whether the given instruction is cheap and not worth hoisting unless
> > +/// one of its users will be hoisted as well.
> > +static bool
> > +RequiresHoistedUse(const MDefinition *ins, bool calls)
> 
> Nit: could you rename "bool calls" to hasCalls/containsCalls/makesCalls/etc,
> something a little more bool-ish?

Renamed to hasCalls.

> @@ +128,5 @@
> >      // TODO: determine if instructions within this block are worth hoisting.
> >      // They might not be if the block is cold enough within the loop.
> >      // BUG 669517
> >      return true;
> >  }
> 
> Feel free to just remove this. I don't really mind keeping it though.

Ok, I removed it. It shouldn't be hard to re-introduce if someone wants to implement that feature.

I also fixed some bugs found during testing related to discontiguous loops.

https://hg.mozilla.org/integration/mozilla-inbound/rev/5429275a038d
https://hg.mozilla.org/integration/mozilla-inbound/rev/c3a7683c8c9e
https://hg.mozilla.org/integration/mozilla-inbound/rev/9ca38df81607

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/5429275a038d
https://hg.mozilla.org/mozilla-central/rev/c3a7683c8c9e
https://hg.mozilla.org/mozilla-central/rev/9ca38df81607