Closed Bug 669984 Opened 13 years ago Closed 13 years ago

IonMonkey: Rewrite snapshot mechanism and type analysis algorithm

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
normal

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
Attached file Test case
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.
Blocks: 657816
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: general → dvander
Status: NEW → ASSIGNED
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)
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)
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.
fix to clean up Lowering handling of phis.
Attachment #546281 - Attachment is obsolete: true
Attachment #546503 - Flags: review?(adrake)
Attachment #546281 - Flags: review?(adrake)
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)
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)
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)
This patch replaces MUseIterator with stuff that looks a lot more like our other iterators.
Attachment #546508 - Flags: review?(ascheff)
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)
Still to do: type policies for the rest of the instructions, correctly handle snapshots in register allocators.
Summary: IonMonkey: Unbox snapshots appear to incorrectly include forward instructions → IonMonkey: Rewrite snapshot mechanism and type analysis algorithm
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+
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+
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+
Attachment #546507 - Flags: review+
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 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 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 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+
(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.
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 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 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+
You need to log in before you can comment on or make changes to this bug.