Closed Bug 733353 Opened 8 years ago Closed 6 years ago

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

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla32

People

(Reporter: jandem, Assigned: sunfish)

References

(Blocks 1 open bug)

Details

(Whiteboard: [ion:p2])

Attachments

(3 files)

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.
Assignee: general → sunfish
Wow I forgot all about this bug after I filed it > 2 years ago. Thanks for taking it!
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.
Attachment #8434267 - Flags: review?(jdemooij)
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.
Attachment #8434276 - Flags: review?(jdemooij)
The previous patch depends on make-loops-contiguous.patch in bug 844779, which will hopefully land soon.
Depends on: 844779
Attached patch licm.patchSplinter Review
Rewrite LICM to eliminate both the worklist and the queue, by taking advantage of IonMonkey's builtin RPO.
Attachment #8434282 - Flags: review?(jdemooij)
These patches speed up asm.js compile time on sqlite by about 8% on my machine.
Impressive.
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.
Attachment #8434267 - Flags: review?(jdemooij) → review+
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.
Attachment #8434276 - Flags: review?(jdemooij) → review+
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.
Attachment #8434282 - Flags: review?(jdemooij) → review+
(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
Duplicate of this bug: 678229
You need to log in before you can comment on or make changes to this bug.