Closed
Bug 669984
Opened 13 years ago
Closed 13 years ago
IonMonkey: Rewrite snapshot mechanism and type analysis algorithm
Categories
(Core :: JavaScript Engine, defect)
Tracking
()
RESOLVED
FIXED
People
(Reporter: adrake, Assigned: dvander)
References
Details
Attachments
(10 files, 1 obsolete file)
53 bytes,
application/javascript
|
Details | |
30.18 KB,
patch
|
adrake
:
review+
|
Details | Diff | Splinter Review |
93.78 KB,
patch
|
adrake
:
review+
|
Details | Diff | Splinter Review |
19.83 KB,
patch
|
rpearl
:
review+
|
Details | Diff | Splinter Review |
20.98 KB,
patch
|
adrake
:
review+
|
Details | Diff | Splinter Review |
24.27 KB,
patch
|
ascheff
:
review+
|
Details | Diff | Splinter Review |
8.98 KB,
patch
|
ascheff
:
review+
|
Details | Diff | Splinter Review |
35.18 KB,
patch
|
rpearl
:
review+
|
Details | Diff | Splinter Review |
1.70 KB,
patch
|
rpearl
:
review+
|
Details | Diff | Splinter Review |
14.24 KB,
patch
|
rpearl
:
review+
|
Details | Diff | Splinter Review |
On the attached test case, register allocation produces the following spew: [LSRA] Beginning register allocation reification [LSRA] Visiting instruction 1 [LSRA] Visiting instruction 3 [LSRA] Visiting instruction 5 [LSRA] Visiting instruction 7 [LSRA] Visiting instruction 8 [LSRA] Visiting instruction 6 [LSRA] WARNING: Unsuccessful time travel attempt: Use of 7 in 6 [LSRA] WARNING: Unsuccessful time travel attempt: Use of 8 in 6 [LSRA] Visiting instruction 9 [LSRA] Visiting instruction 10 [LSRA] Visiting instruction 11 [LSRA] Register allocation reification complete The initial LIR looks like: begin_LIR 1 parameter ([t:1 (arg -7)], [d:2 (arg -8)]) <|@ 3 parameter ([t:3 (arg -5)], [d:4 (arg -6)]) <|@ 5 parameter ([t:5 (arg -3)], [d:6 (arg -4)]) <|@ 7 parameter ([t:7 (arg -1)], [d:8 (arg -2)]) <|@ 8 unbox ([i:8 (r)]) (v7:*), (v8:r) <|@ 6 unbox ([i:6 (r)]) (v5:*), (v6:r) <|@ 9 bitop ([i:9 (!)]) (v6:r), (v8:*) <|@ 10 box ([t:10], [d:9 (r)]) (v9:*) <|@ 11 return () (v10:ecx), (v9:edx) <|@ end_LIR The "5 7 8 6 9" ordering is a little scary, too.
Assignee | ||
Comment 1•13 years ago
|
||
For this specific case there is probably a simple hack but there's a more general problem. Consider two cases: SNAPSHOT GETPROP <--- guarded idempotent UNBOX <--- inserted during type analysis SNAPSHOT ADD Here, if the unbox fails, it's safe to rewrite the second snapshot's capture of the GETPROP result. It's safe because we will resume at the first snapshot. However: SNAPSHOT CALL <--- oh, not idempotent at all UNBOX <--- inserted during type analysis SNAPSHOT ADD Now, the inserted UNBOX rewrites the downstream snapshot, but if the unbox fails it will resume and repeat the call. In this case, we must insert the UNBOX *after* the second snapshot. One idea: Pair instructions with snapshots, for example in the CALL case we'd take the SNAPSHOT out of the instruction steam and attach it right to the CALL. Then there would be no possibility for error. "Casual" snapshots like before ADD could still float around in the IR.
Assignee | ||
Updated•13 years ago
|
Assignee: general → dvander
Status: NEW → ASSIGNED
Assignee | ||
Comment 2•13 years ago
|
||
This fix necessitates some refactoring. To start, let's get rid of MOperand. It's a useless heap allocated wrapper around an MInstruction that was created with having one IR in mind. We're not attaching anything to MIR inputs anymore, so we might as well get rid of it.
Attachment #546267 -
Flags: review?(adrake)
Assignee | ||
Comment 3•13 years ago
|
||
More refactoring. This patch makes MInstruction inherit from MDefinition. We discussed this in the JS pit today and people seemed to be on board, but this is a big patch so let's make sure it's the right direction. Everything in MInstruction is moved into MDefinition, except: * InlineListNode inheritance. This is so definitions (like phis) can't appear in a basic block's IR stream. * MInstructionVisitor, MInstructionIterator do not take definitions. This separation is nice in that the type system now separates Phis from other instructions, since they're always special anyway and now that is explicit. On the other hand, other things get weirder: not all definitions are instructions, but not all instructions are definitions (think, a guard or a jump). Whatever. A few things remain weird: * The type analysis pass has to have casts. Ignore this. I am going to remove this pass (or replace it) later in the queue. * emitAtUses() uses def->toInstruction and expects that it is never called on a non-instruction. I'm not sure if there is something cleaner. toInstruction does assert that it is not a Phi.
Attachment #546281 -
Flags: review?(adrake)
Assignee | ||
Comment 4•13 years ago
|
||
This is all working toward splitting MSnapshot out of the instruction stream so we can affix it directly to instructions - eliminating the entire problem in this bug, where inserting "harmless" instructions can break critical invariants. The next patch will introduce an MNode, above MDefinition in the hierarchy, and steal the few relevant things needed for snapshots. Then a use iterator will return nodes, which will probably break the analysis passes, so it'll be a good chance to refactor MUseIterator which is horrible.
Assignee | ||
Comment 5•13 years ago
|
||
fix to clean up Lowering handling of phis.
Attachment #546281 -
Attachment is obsolete: true
Attachment #546503 -
Flags: review?(adrake)
Attachment #546281 -
Flags: review?(adrake)
Assignee | ||
Comment 6•13 years ago
|
||
Big queue coming, I'll try and split up reviews. This patch introduces MNode, which is above an MDefinition, and just contains the operand API. This is so snapshots don't have to be definitions or instructions, but they still participate in use chains.
Attachment #546504 -
Flags: review?(rpearl)
Assignee | ||
Comment 7•13 years ago
|
||
This patch changes how snapshots work. Instead of being implicitly inserted at random points, they are now explicitly taken and directly affixed to instructions. This makes it impossible for an analysis to insert a fallible operation in between an effect and its snapshot, thereby making the fallible operation unsound.
Attachment #546506 -
Flags: review?(adrake)
Assignee | ||
Comment 8•13 years ago
|
||
The type analyzer is pretty bogus and to make the rest of this queue simpler this patch just removes it.
Attachment #546507 -
Flags: review?(ascheff)
Assignee | ||
Comment 9•13 years ago
|
||
This patch replaces MUseIterator with stuff that looks a lot more like our other iterators.
Attachment #546508 -
Flags: review?(ascheff)
Assignee | ||
Comment 10•13 years ago
|
||
This patch introduces a new type analyzer. MInstructions can provide a TypePolicy object, which describes how they interact with type analysis. The actual algorithm: * Determine specializations: (1) Add all non-phis to an RPO worklist. (2) While there are items in the worklist: * Pop an item off the worklist. * If the item's policy needs to change its specialization, add the item's uses back to the worklist. (3) For each phi, * If that phi's inputs are all the same type, or are all specialized to the same type, then specialize the phi, adding its uses back to the worklist. (4) If there are items in the worklist, repeat from (2). * For each instruction, in post order, (1) Ask the instruction to adjust its inputs, applying boxing operations or conversions. (2) If the instruction's output is a value, attempt to specialize the value at its definition based on its uses.
Attachment #546510 -
Flags: review?(rpearl)
Assignee | ||
Comment 11•13 years ago
|
||
Still to do: type policies for the rest of the instructions, correctly handle snapshots in register allocators.
Assignee | ||
Updated•13 years ago
|
Summary: IonMonkey: Unbox snapshots appear to incorrectly include forward instructions → IonMonkey: Rewrite snapshot mechanism and type analysis algorithm
Reporter | ||
Comment 12•13 years ago
|
||
Comment on attachment 546267 [details] [diff] [review] part 1: remove useless MOperand wrapper Review of attachment 546267 [details] [diff] [review]: -----------------------------------------------------------------
Attachment #546267 -
Flags: review?(adrake) → review+
Reporter | ||
Comment 13•13 years ago
|
||
Comment on attachment 546503 [details] [diff] [review] part 2.1: MDefinition; split off MPhi from MInstruction Review of attachment 546503 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/ion/IonAnalysis.cpp @@ +343,5 @@ > block->insertAfter(*block->begin(), unbox); > } else if (block->start() && ins->id() < block->start()->id()) { > block->insertAfter(block->start(), unbox); > } else { > + block->insertAfter((MInstruction *)ins, unbox); This cast is a little scary -- could we have a checked toInstruction function or similar?
Attachment #546503 -
Flags: review?(adrake) → review+
Reporter | ||
Comment 14•13 years ago
|
||
Comment on attachment 546506 [details] [diff] [review] part 4: new snapshot mechanism Review of attachment 546506 [details] [diff] [review]: -----------------------------------------------------------------
Attachment #546506 -
Flags: review?(adrake) → review+
Updated•13 years ago
|
Attachment #546507 -
Flags: review+
Comment 15•13 years ago
|
||
Comment on attachment 546507 [details] [diff] [review] part 5: remove the type analyzer Looks fine, certainly doesn't break anything as far as I can see
Attachment #546507 -
Flags: review?(ascheff)
Comment 16•13 years ago
|
||
Comment on attachment 546508 [details] [diff] [review] part 6: new use iterator Review of attachment 546508 [details] [diff] [review]: ----------------------------------------------------------------- Looks good to me
Attachment #546508 -
Flags: review?(ascheff) → review+
Comment 17•13 years ago
|
||
Comment on attachment 546504 [details] [diff] [review] part 3: introduce MNode Review of attachment 546504 [details] [diff] [review]: ----------------------------------------------------------------- Looks good, r+ with a few things to address. ::: js/src/ion/IonLowering.cpp @@ -312,4 +312,8 @@ > > - MDefinition *use = iter->ins(); > > + MNode *node = iter->node(); > > - if (!ins->isSnapshot() || ins->inWorklist()) { > > + if (node->isDefinition()) { > > - iter.next(); > > + MDefinition *def = node->toDefinition(); > > - continue; > > + if (!def->isSnapshot() || def->inWorklist()) { NaN more ... With the class hierarchy that MNodes are either snapshots or definitions, this code is stale. We don't need the |def->isSnapshot()| check anymore, but rather should check if the MNode is a def or a snapshot, then cast that to an MDefinition. ::: js/src/ion/JSONSpewer.cpp @@ +223,5 @@ > endList(); > > beginListProperty("uses"); > + for (MUseIterator use(*ins); use.more(); use.next()) { > + if (!use->node()->isDefinition()) should be |if (use->node()->isDefinition())| I believe, since it is cast to an definition below. ::: js/src/ion/LICM.cpp @@ -168,3 +173,3 @@ > > - if (!use->ins()->inWorklist() && > > + if (!def->inWorklist() && > > - isInLoop(use->ins()) && > > + isInLoop(def) && > > - use->ins()->estimateHoistWin() != MInstruction::NO_WIN) { > > + def->estimateHoistWin() != MInstruction::NO_WIN) def is an MDefinition, but we have |def->estimateHoistWin()| returning |MInstruction::NO_WIN|? I think we probably want |def->ins()->estimateHoistWin()|, moving estimateHoistWin() to MInstruction, since it doesn't make sense to hoist a phi node. However, that does make this LICM code a bit ugly--we have to check if a use is a "real" use (not a snapshot), then check if the consumer of the use is a real instruction or a phi. An alternative is putting |estimateHoistWin()| in MDefinition, and making phis have no hoist win. @@ -243,1 +251,1 @@ > > Minor nit: The additional |if (use->node()->isDefinition())| makes this code very indented. I think we probably want to do |if (!use->...) continue;| instead, or break up the |if (def->isLoopInvariant()...| line up.
Attachment #546504 -
Flags: review?(rpearl) → review+
Comment 18•13 years ago
|
||
Comment on attachment 546510 [details] [diff] [review] part 7: new type analyzer Review of attachment 546510 [details] [diff] [review]: ----------------------------------------------------------------- Looks good. r+ with a few very tiny issues. Maybe, just maybe, this review won't have the text "NaN more ..." added to it for no discernible reason. ::: js/src/ion/IonAnalysis.cpp @@ +79,5 @@ > > +class TypeAnalyzer > +{ > + MIRGraph &graph; > + js::Vector<MInstruction *, 0, SystemAllocPolicy> worklist_; Don't we have IonAllocPolicy? @@ +85,5 @@ > + bool empty() const { > + return worklist_.empty(); > + } > + MInstruction *pop() { > + MInstruction *ins = worklist_.popCopy(); Minor nit: assert that the worklist isn't empty, since the instruction pointer is dereferenced without checking. @@ +320,5 @@ > + return true; > +} > + > +bool > +TypeAnalyzer::adjustPhiInputs(MPhi *phi) This function's return type is bool, but it never returns false. @@ +339,5 @@ > + MDefinition *in = phi->getOperand(i); > + if (in->type() == MIRType_Value) > + continue; > + > + MBox *box = MBox::New(in); Is this allocation guaranteed to succeed (that might be why this function is bool?)
Attachment #546510 -
Flags: review?(rpearl) → review+
Assignee | ||
Comment 19•13 years ago
|
||
(In reply to comment #17) > Minor nit: The additional |if (use->node()->isDefinition())| makes this code > very indented. I think we probably want to do |if (!use->...) continue;| > instead, or break up the |if (def->isLoopInvariant()...| line up. I agree - lucky, the MUseIterator rewrite a few patches down cleans this all up. I've addressed nits that aren't though. (In reply to comment #18) > Don't we have IonAllocPolicy? Yeah, though that's a pool allocator. In this case the allocation can be trivially freed after the analysis so might as well not hold onto the memory. > Minor nit: assert that the worklist isn't empty, since the instruction > pointer is dereferenced without checking. worklist_.pop() will assert for us, luckily > > +TypeAnalyzer::adjustPhiInputs(MPhi *phi) > > This function's return type is bool, but it never returns false. Yeah, it's mostly just for consistency. Nothing in this patch is OOM safe yet, at some point we'll have to go back and make sure it and other passes ensure the ballast.
Assignee | ||
Comment 20•13 years ago
|
||
Attachment #546617 -
Flags: review?(rpearl)
Assignee | ||
Comment 21•13 years ago
|
||
This adds a bitop policy and makes bitops hook into the type oracle again. I think this queue is done, and the state of affairs is now: * The bug in this patch is fixed. * The type analysis phase is much more stable and flexible. * We should no longer die in type analysis from weird inputs. (Instead, we now have new ops that need to be implemented. Separate bug.)
Attachment #546618 -
Flags: review?(rpearl)
Comment 22•13 years ago
|
||
Comment on attachment 546617 [details] [diff] [review] part 8: apply box input policy to stuff Review of attachment 546617 [details] [diff] [review]: -----------------------------------------------------------------
Attachment #546617 -
Flags: review?(rpearl) → review+
Comment 23•13 years ago
|
||
Comment on attachment 546618 [details] [diff] [review] part 9: add a bitwise policy Review of attachment 546618 [details] [diff] [review]: ----------------------------------------------------------------- Looks good. ::: js/src/ion/MIR.h @@ +817,5 @@ > + return new MTruncateToInt32(def); > + } > +}; > + > +class MBinaryBitInstruction Minor aesthetic nit: MBinaryBitwiseInstruction Or just MBitwiseInstruction? "BinaryBit" seems weird.
Attachment #546618 -
Flags: review?(rpearl) → review+
Assignee | ||
Comment 24•13 years ago
|
||
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/2ad588538941 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/7d3869474687 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/08e3862fbc8a http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/c7f8e17bc91c http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/8a0b747bf1d9 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/b1dda4d02396 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/4c229e3f1f08 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/51ea8220ced7 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/47a0572921e7 http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/d0aea54067f6
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•