1040738 - IonMonkey: Abstract memory emulation traversal.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Nicolas B. Pierron [:nbp]]

As we can see in Bug 992845 and in Bug 1040027, we have a simple pattern which can be used to abstract the traversal made by the program transformation which known as Scalar Replacement.

This traversal of the code is in fact way more common and can be used for adding thing which is emulating memory and which need to be represented in the code with Phi nodes.  Scalar replacement of object is one of them, but this is what IonBuilder does when it adds resume points and also what Alias analysis does with the MDefinitionVector (except that its does not properly handle branches).

The goal here is to extract the common bases which are used by Scalar Replacement transformation and make it viable for Alias Analysis, such as we can later (as part of another bug) improve our alias analysis and make it precise.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Extract the graph traversal from the state manipulation.

This patch move the manipulation of the graph away from the manipulation of
the state, in particular the object state.  Moving the ArrayState (from Bug
1040027) should be almost the same thing.

Comment 2

[Dan Gohman [:sunfish]]

Comment on attachment 8458932 [details] [diff] [review]
Extract the graph traversal from the state manipulation.

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

::: js/src/jit/ScalarReplacement.cpp
@@ +57,5 @@
> +    enum IterState {
> +        Iter_Continue,
> +        Iter_Discard,
> +        Iter_Error,
> +        Iter_NotInitialized

Iter_NotInitialized is not actually used anywhere at the moment.

@@ +64,5 @@
> +  private:
> +    IterState iterState_;
> +
> +  public:
> +    void setIterState(IterState val) {

Should this function be protected? It's probably not super important, but it would help me when I want to look at the class and determine what its public interface is.

@@ +67,5 @@
> +  public:
> +    void setIterState(IterState val) {
> +        iterState_ = val;
> +    }
> +    IterState getIterState() {

This function can be const.

@@ +118,5 @@
> +    MBasicBlock *startBlock = view.startingBlock();
> +    if (!view.initStartingState(&states_[startBlock->id()]))
> +        return false;
> +
> +    // Iterate over each basic block and save the object's layout.

This and other comments below seem to be copied from the ObjectMemoryLayout code and are out of place. It confused me at first before I figured this out.

@@ +135,5 @@
> +            return false;
> +
> +        for (MInstructionIterator ins(block->begin()); ins != block->end(); ) {
> +            if (!ins->accept(&view) || view.getIterState() > MemoryView::Iter_Error)
> +                return false;

MInstructionIterator doesn't visit phis. Is it intended to skip phis, or an oversight? MDefinitionIterator can be used to easily iterate over both normal instructions and phis.

@@ +141,5 @@
> +            // Remove original instruction.
> +            if (view.getIterState() == MemoryView::Iter_Discard) {
> +                ins = block->discardAt(ins);
> +                continue;
> +            }

High-level comment: An alternative approach to this loop and the IterState enum would be to define a new iterator which visits all the instructions (and phis, if desired) and resume points in a block, similar to how MDefinitionIterator iterates over all instructions and phis in a block. Conveniently, MDefinition and MResumePoint have a common base class, MNode, that you can use for this. Then instead of using IterState logic, this loop could just follow the convention of incrementing the iterator before doing anything that might discard the current element.

Assuming this is practical, it would simplify this run function. I wonder if it's possible to simplify it to the point where it's no longer needed?

@@ +155,5 @@
> +        // For each successor, copy/merge the current state as being the initial
> +        // state of the successor block.
> +        for (size_t s = 0; s < block->numSuccessors(); s++) {
> +            MBasicBlock *succ = block->getSuccessor(s);
> +            if (!view.initSuccessorState(*block, succ, &states_[succ->id()]))

It's a little confusing that a function called initSuccessorState does both the initialization of the state and also merging of the state with any existing state.

@@ +360,5 @@
> +        // predecessors. As we need to replace all the inputs, we need
> +        // to check all predecessors against the current block to
> +        // replace the Phi node operands.
> +        size_t numPreds = succ->numPredecessors();
> +        for (size_t p = 0; p < numPreds; p++) {

It looks like this can use MBasicBlock::positionInPhiSuccessor instead of searching for the predecessor index.

@@ +411,5 @@
> +ObjectMemoryView::visitStoreFixedSlot(MStoreFixedSlot *ins)
> +{
> +    // Skip stores made on other objects.
> +    if (ins->object() != obj_) {
> +        setIterState(Iter_Continue);

Instead of calling setIterState directly, perhaps this can call MInstructionDiscardVisitor::visitStoreFixedSlot(ins). This applies to several other places below too.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Add MNodeIterator to iterate over resume points and definitions.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2 - Move the accept function to MDefinition.

Comment 5

[Nicolas B. Pierron [:nbp]]

Attachment: Part 3 - Add MInstructionVisitor with no-op by default.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #2)
> @@ +360,5 @@
> > +        // predecessors. As we need to replace all the inputs, we need
> > +        // to check all predecessors against the current block to
> > +        // replace the Phi node operands.
> > +        size_t numPreds = succ->numPredecessors();
> > +        for (size_t p = 0; p < numPreds; p++) {
> 
> It looks like this can use MBasicBlock::positionInPhiSuccessor instead of
> searching for the predecessor index.

I don't know where this information is updated, but it is not yet there at the time of the current phase of ScalarReplacement.  In the mean time I am using indexForPredecessor, as this transformation is still done after the split edge one.

Comment 7

[Dan Gohman [:sunfish]]

Comment on attachment 8461477 [details] [diff] [review]
Part 1 - Add MNodeIterator to iterate over resume points and definitions.

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

::: js/src/jit/MIRGraph.h
@@ +786,5 @@
> +// Resume points are visited as long as the instruction which holds it is not
> +// discarded.
> +class MNodeIterator
> +{
> +  friend class MBasicBlock;

This friend declaration appears unnecessary.

@@ +794,5 @@
> +    // to walk over the entry resume point, assuming that the last instruction
> +    // is not discarded before we visit it.
> +    MInstruction *last_;
> +
> +    // Definition iterator which is on step ahead when visiting resume points.

"on step" -> "one step"

@@ +811,5 @@
> +    MNode *getNode() {
> +        if (!atResumePoint())
> +            return *defIter_;
> +
> +        if (last_ != block()->lastIns())

Setting last_ to block()->lastIns() to represent the entry resume point is a little subtle. Please add a comment mentioning what's happening here.

@@ +838,5 @@
> +  public:
> +    explicit MNodeIterator(MBasicBlock *block)
> +      : last_(block->lastIns()),
> +        defIter_(block)
> +    { }

Since this starts the iterator at the entry resume point, and since this is a little subtle, MOZ_ASSERT(atResumePoint()).

Actually, what happens if the block doesn't have an entry resume point? Shouldn't we advance the iterator to the first MDefinition in that case?

Comment 8

[Dan Gohman [:sunfish]]

Comment on attachment 8461479 [details] [diff] [review]
Part 2 - Move the accept function to MDefinition.

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

::: js/src/jit/MIR.h
@@ +380,5 @@
>      { }
>  
>      virtual Opcode op() const = 0;
>      virtual const char *opName() const = 0;
> +    virtual bool accept(MInstructionVisitor *visitor) = 0;

MInstructionVisitor was already handling phis, so it was already essentially MDefinitionVisitor, so moving the accept function to MDefinition makes sense. We should also rename it to MDefinitionVisitor.

Comment 9

[Dan Gohman [:sunfish]]

Comment on attachment 8461480 [details] [diff] [review]
Part 3 - Add MInstructionVisitor with no-op by default.

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

::: js/src/jit/MOpcodes.h
@@ +250,5 @@
>      MIR_OPCODE_LIST(VISIT_INS)
>  #undef VISIT_INS
>  };
>  
> +class MInstructionVisitorWithNoop : public MInstructionVisitor

Since MInstructionVisitor should be renamed to MDefinitionVisitor, this should be renamed too.

As an optional suggestion, instead of "WithNoop", how about "DefaultNoop" to kind of describe that it provides default no-op implementations for all the opcodes? Either way is ok with me though. But it would be nice to have a one-line comment describing the class either way.

Comment 10

[Dan Gohman [:sunfish]]

(In reply to Nicolas B. Pierron [:nbp] from comment #6)
> (In reply to Dan Gohman [:sunfish] from comment #2)
> > @@ +360,5 @@
> > > +        // predecessors. As we need to replace all the inputs, we need
> > > +        // to check all predecessors against the current block to
> > > +        // replace the Phi node operands.
> > > +        size_t numPreds = succ->numPredecessors();
> > > +        for (size_t p = 0; p < numPreds; p++) {
> > 
> > It looks like this can use MBasicBlock::positionInPhiSuccessor instead of
> > searching for the predecessor index.
> 
> I don't know where this information is updated, but it is not yet there at
> the time of the current phase of ScalarReplacement.  In the mean time I am
> using indexForPredecessor, as this transformation is still done after the
> split edge one.

Ok, I see now. This code is run after critical edges are split, but currently it runs before EliminatePhis and BuildPhiReverseMapping.

Comment 11

[Nicolas B. Pierron [:nbp]]

Attachment: Part 4 - Extract the graph traversal from the state manipulation.

Delta:
 - Use the MNodeIterator and Visitor with no-op for the refactoring.
 - Use indexOfPredecessor.
 - Update comments.

Comment 12

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman [:sunfish] from comment #7)
> @@ +838,5 @@
> > +  public:
> > +    explicit MNodeIterator(MBasicBlock *block)
> > +      : last_(block->lastIns()),
> > +        defIter_(block)
> > +    { }
> 
> Since this starts the iterator at the entry resume point, and since this is
> a little subtle, MOZ_ASSERT(atResumePoint()).
> 
> Actually, what happens if the block doesn't have an entry resume point?
> Shouldn't we advance the iterator to the first MDefinition in that case?

Indeed, we should and this would matter if we make use of this iterator with AsmJS transformation.  I will handle this case in my new patch, even if scalar replacement is only enabled for Ion at the moment.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1 - Add MNodeIterator to iterate over resume points and definitions.

Delta:
 - Updates comments about last_ being set to the last instruction when we
 are iterating over the entry resume point.
 - Handle the case where there is not entry resume point, and assert in the
 constructor.
 - Assert in the constructor that the last instruction should not have any
 resume point attached to it.

Comment 14

[Dan Gohman [:sunfish]]

Comment on attachment 8462587 [details] [diff] [review]
Part 1 - Add MNodeIterator to iterate over resume points and definitions.

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

Looks good!

Comment 15

[Dan Gohman [:sunfish]]

Comment on attachment 8462567 [details] [diff] [review]
Part 4 - Extract the graph traversal from the state manipulation.

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

Thanks for factoring out MNodeIterator! It makes the main loop very easy to follow.

::: js/src/jit/ScalarReplacement.cpp
@@ +88,5 @@
> +
> +    // Iterate over each basic block which has a valid entry state, and merge
> +    // the state in the successor blocks.
> +    for (ReversePostorderIterator block = graph_.rpoBegin(startBlock); block != graph_.rpoEnd(); block++) {
> +        if (mir_->shouldCancel("Scalar Replacement of Object"))

This shouldCancel string still mentions scalar replacement.

@@ +102,5 @@
> +
> +        // Iterates over resume points, phi and instructions.
> +        for (MNodeIterator iter(*block); iter; ) {
> +            // Increment the iterator before visiting the instruction, as the
> +            // visit function might discard it-self from the basic block.

"it-self" -> "itself"

Comment 16

[Nicolas B. Pierron [:nbp]]

https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=a1c841c6b3b0
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=8a746c3e25be

https://hg.mozilla.org/integration/mozilla-inbound/rev/537d79957a0b
https://hg.mozilla.org/integration/mozilla-inbound/rev/4d91f007db41
https://hg.mozilla.org/integration/mozilla-inbound/rev/9300a79283ee
https://hg.mozilla.org/integration/mozilla-inbound/rev/1b7a349de64e
https://hg.mozilla.org/integration/mozilla-inbound/rev/0614504926f7

Comment 17

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/537d79957a0b
https://hg.mozilla.org/mozilla-central/rev/4d91f007db41
https://hg.mozilla.org/mozilla-central/rev/9300a79283ee
https://hg.mozilla.org/mozilla-central/rev/1b7a349de64e
https://hg.mozilla.org/mozilla-central/rev/0614504926f7