Closed
Bug 1077720
Opened 10 years ago
Closed 10 years ago
IonMonkey: Optimize and simplify phi handling
Categories
(Core :: JavaScript Engine: JIT, enhancement)
Core
JavaScript Engine: JIT
Tracking
()
RESOLVED
FIXED
mozilla35
People
(Reporter: sunfish, Assigned: sunfish)
Details
Attachments
(5 files, 1 obsolete file)
4.78 KB,
patch
|
nbp
:
review+
|
Details | Diff | Splinter Review |
24.29 KB,
patch
|
nbp
:
review+
|
Details | Diff | Splinter Review |
1.47 KB,
patch
|
nbp
:
review+
|
Details | Diff | Splinter Review |
13.08 KB,
patch
|
nbp
:
review+
|
Details | Diff | Splinter Review |
18.85 KB,
patch
|
nbp
:
review+
|
Details | Diff | Splinter Review |
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)
Assignee | ||
Comment 1•10 years ago
|
||
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)
Assignee | ||
Comment 2•10 years ago
|
||
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)
Assignee | ||
Comment 3•10 years ago
|
||
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)
Assignee | ||
Comment 4•10 years ago
|
||
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)
Comment 5•10 years ago
|
||
Cool. What workloads were you looking at?
Comment 6•10 years ago
|
||
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 7•10 years ago
|
||
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+
Updated•10 years ago
|
Attachment #8499873 -
Flags: review?(nicolas.b.pierron) → review+
Comment 8•10 years ago
|
||
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)
Updated•10 years ago
|
Attachment #8499879 -
Flags: review?(nicolas.b.pierron) → review+
Assignee | ||
Comment 9•10 years ago
|
||
(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)
Updated•10 years ago
|
Attachment #8501344 -
Flags: review?(nicolas.b.pierron) → review+
Assignee | ||
Comment 10•10 years ago
|
||
Nits addessed, and I split the clearSuccessorWithPhis() change into its own patch: https://hg.mozilla.org/integration/mozilla-inbound/rev/c4a22f350c13 https://hg.mozilla.org/integration/mozilla-inbound/rev/49aafe51147f https://hg.mozilla.org/integration/mozilla-inbound/rev/e377dd82cb72 https://hg.mozilla.org/integration/mozilla-inbound/rev/3562875c3899 https://hg.mozilla.org/integration/mozilla-inbound/rev/a850f2bc5824 https://hg.mozilla.org/integration/mozilla-inbound/rev/811aad892522 Thanks!
https://hg.mozilla.org/mozilla-central/rev/c4a22f350c13 https://hg.mozilla.org/mozilla-central/rev/49aafe51147f https://hg.mozilla.org/mozilla-central/rev/e377dd82cb72 https://hg.mozilla.org/mozilla-central/rev/3562875c3899 https://hg.mozilla.org/mozilla-central/rev/a850f2bc5824 https://hg.mozilla.org/mozilla-central/rev/811aad892522
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
You need to log in
before you can comment on or make changes to this bug.
Description
•