Closed Bug 1077720 Opened 10 years ago Closed 10 years ago

IonMonkey: Optimize and simplify phi handling

Categories

(Core :: JavaScript Engine: JIT, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla35

People

(Reporter: sunfish, Assigned: sunfish)

Details

Attachments

(5 files, 1 obsolete file)

Looking at Emscripten-generated code, we occasionally see programs with very large numbers of phis, and phis with very large numbers of operands, such that phi processing alone contributes noticeably to Ion/Odin compile time. Attached is a series of patches which simplifies and optimizes phi node manipulation code.

This first patch optimizes MPhi::removeOperand, which removes an operand from the middle of a phi's list. It adds a replaceUse method for replacing a use in a use list, rather than doing a list removal followed by a list insert.
Attachment #8499869 - Flags: review?(nicolas.b.pierron)
This patch proposes to take a stand on InlineList.h's convention of removeAt functions which are intended to be used like this:

      iter = block->discardDefAt(iter);

where iter is passed by reference and assigned to inside discardDefAt, meaning it actually gets assigned to twice in this expression!

The purpose of the non-const reference and extra assignment is that it can help prevent the iterator from being used in a dangling state. However, in practice, this benefit seems offset by the decrease in readability in the above code, since it leads to things like this:

      if (something) {
          iter = block->discardDefAt(iter);
      } else {
          ++iter;
      }

and it can be easy to forget to increment iter on some paths, since it isn't done on all paths.

This patch replaces such code with the post-increment idiom:

      MDefinition *ins = *iter++;
      // ... followed by code which may disconnect |ins| from the list, which is
      // ok since |iter| is already pointing to the next element.

There are cases when the post-increment idiom gets tricky too, but in general, I claim it's simpler and easier to follow, as the examples in this patch show.
Attachment #8499872 - Flags: review?(nicolas.b.pierron)
Attached patch phi-disard.patchSplinter Review
This patch just micro-optimizes some loops to eliminate some overhead that compilers aren't always able to eliminate automatically.
Attachment #8499873 - Flags: review?(nicolas.b.pierron)
Attached patch phi-addinput.patch (obsolete) — Splinter Review
This optimizes MPhi::addInput and related functions.

It introduces a move constructor for InlineListNode, which means that a Vector<MUse> can resize itself, and all the uses will automatically stay in their use lists. This replaces code which manually iterates through the vector to remove all the uses from their lists, do the resize, and then iterate again to re-insert all the uses into their lists.

It also makes MPhi::checkForTypeChange a separate function rather than being part of addInput, since it's only needed in one place.

It also adds infallibleGrowByUninitialized to the Vector class, since MPhi::addInput can use this to construct MUses in place.
Attachment #8499875 - Flags: review?(nicolas.b.pierron)
This patch observes that MPhis never participate in AliasAnalysis dependencies, so it makes dependency() return an MInstruction* instead of an MDefinition*, and makes a bunch of associated changes.

This allows AliasAnalysis to have a separate loop for phis which doesn't call getAliasSet().
Attachment #8499879 - Flags: review?(nicolas.b.pierron)
Cool.  What workloads were you looking at?
Comment on attachment 8499869 [details] [diff] [review]
phi-removeoperand.patch

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

::: js/src/jit/InlineList.h
@@ +344,5 @@
> +        Node *oldPrev = old->prev;
> +        oldPrev->next = now;
> +        oldNext->prev = now;
> +        now->next = oldNext;
> +        now->prev = oldPrev;

nit: s/oldNext/listNext/; s/oldPrev/listPrev/

The old prefix let us think that they are out-dated, and thus that they should not hold "now".

::: js/src/jit/MIR.h
@@ +670,5 @@
>      void addUseUnchecked(MUse *use) {
>          uses_.pushFrontUnchecked(use);
>      }
> +    void replaceUse(MUse *old, MUse *now) {
> +        uses_.replace(old, now);

nit: MOZ_ASSERT(now->producer() == this)
Attachment #8499869 - Flags: review?(nicolas.b.pierron) → review+
Comment on attachment 8499872 [details] [diff] [review]
phi-removeat.patch

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

::: js/src/jit/MIRGraph.h
@@ +564,5 @@
>          successorWithPhis_ = successor;
>          positionInPhiSuccessor_ = id;
>      }
> +    void clearSuccessorWithPhis() {
> +        successorWithPhis_ = nullptr;

This change is unrelated, can you move into its own patch and r=me.
Attachment #8499872 - Flags: review?(nicolas.b.pierron) → review+
Attachment #8499873 - Flags: review?(nicolas.b.pierron) → review+
Comment on attachment 8499875 [details] [diff] [review]
phi-addinput.patch

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

::: js/src/jit/InlineList.h
@@ +213,5 @@
>  
> +    // Move constructor. Nodes may be moved without being removed from their
> +    // containing lists.
> +    InlineListNode(InlineListNode<T> &&other)
> +      : InlineForwardListNode<T>(other.next)

comment-nit: Precise that this is needed for moving elements which stored a resizeable vector.  Also, note that "this" replace "other" in the list.

::: js/src/jit/MIR.h
@@ +5800,5 @@
>  
>      // Use only if capacity has been reserved by reserveLength
> +    void addInput(MDefinition *ins) {
> +        inputs_.infallibleGrowByUninitialized(1);
> +        new (&inputs_.back()) MUse(ins, this);

Use infallibleAppend.

@@ +5810,5 @@
> +        if (!inputs_.growByUninitialized(1))
> +            return false;
> +
> +        new (&inputs_.back()) MUse(ins, this);
> +        return true;

Use inputs_.append(MUse(…))
Attachment #8499875 - Flags: review?(nicolas.b.pierron)
Attachment #8499879 - Flags: review?(nicolas.b.pierron) → review+
(In reply to Nicolas B. Pierron [:nbp] from comment #8)
> Comment on attachment 8499875 [details] [diff] [review]
> phi-addinput.patch
> 
> Review of attachment 8499875 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/InlineList.h
> @@ +213,5 @@
> >  
> > +    // Move constructor. Nodes may be moved without being removed from their
> > +    // containing lists.
> > +    InlineListNode(InlineListNode<T> &&other)
> > +      : InlineForwardListNode<T>(other.next)
> 
> comment-nit: Precise that this is needed for moving elements which stored a
> resizeable vector.  Also, note that "this" replace "other" in the list.

Ok, I added comments for these.

> ::: js/src/jit/MIR.h
> @@ +5800,5 @@
> >  
> >      // Use only if capacity has been reserved by reserveLength
> > +    void addInput(MDefinition *ins) {
> > +        inputs_.infallibleGrowByUninitialized(1);
> > +        new (&inputs_.back()) MUse(ins, this);
> 
> Use infallibleAppend.

Doing input_.infallibleAppend(Muse(ins, this)) would create a temporary MUse, add the temporary to |ins|'s worklist, and then remove the temporary from the list before linking in the final MUse. In practice, there are many pointer loads and stores flying around here, so it's difficult for compilers to optimize everything away. Directly constructing the MUse in the vector avoids all this, so I'd like to keep the code as is. I've updated the patch with comments.

> @@ +5810,5 @@
> > +        if (!inputs_.growByUninitialized(1))
> > +            return false;
> > +
> > +        new (&inputs_.back()) MUse(ins, this);
> > +        return true;
> 
> Use inputs_.append(MUse(…))

Ditto.
Attachment #8499875 - Attachment is obsolete: true
Attachment #8501344 - Flags: review?(nicolas.b.pierron)
Attachment #8501344 - Flags: review?(nicolas.b.pierron) → review+
You need to log in before you can comment on or make changes to this bug.