Nicolas B. Pierron [:nbp] Assignee
	Description • 10 years ago

The goal of this bug is to add a sorted vector / list of effectful instructions attached to resume points.  This list needs to be ordered such as (well-scoped) side-effects are done in the same order as if they were executed in the basic block.

This way, we should be able to remove writes which are masked by others within the same basic block.  This way the following function

  function f(o, i, j) {
    o.a = i + j;
    bailout();
    o.a = i;
  }

would be transformed to

  function f(o, i, j) {
    bailout();
    o.a = i;
  }

with the help of the DCE optim made in Bug 990106.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 1 • 10 years ago

This patch adds an extra operand to the resume points, and make sure that
this extra operand is filtered out when constructing the snapshot, and not
considered when constructing the resume points.

This extra operand would be used for chaining side-effects on the resume
points (part 4).

This patch also clean-up the use of numOperand from the MIRGraph and
IonBuilder, such as we use stackDepth when we only mean to iterate over the
definitions of the emulated stack of the interpreter.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 2 • 10 years ago

This patch takes a bit off the Mode of the RValueAllocation to mention that
the value which is read is incomplete without running any of the
side-effects.

The alternative to this additional bit would be to make MDefinition wrapper
which would be recovered on bailout and which are referring to all
side-effects. This alternative would be costly as it would add dummy recover
instructions.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 3 • 10 years ago

This patch is doing almost the same as part 1, but for MObjectState and
MArrayState.

This patch also add the logic for recording the side-effect operand first in
the LRecoverInfo, and ignoring it in the LRecoverInfo::OperandIter.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 4 • 10 years ago

This patch makes use of the side-effect operands introduced by the last
patches.  This whole process replace the operand substitution of resume
points by the construction of a spaghetti-stack of side-effects which would
be recorvered.

The Spaghetti stack solution is the simplest approach for avoiding extra
allocation by sharing incremental construction of the side-effect list of
resume points.

Later, if this becomes a memory issue, we can investigate ways to order the
processing of the side-effects such as the least frequent modifications are
processed first, in which case we would have the minimal memory consumption.

This removes the blocking issue seen in Bug 1073033, and also gives
additional room to experiment with the removal of any Store instructions.

	Hannes Verschore [:h4writer]
	Comment 5 • 10 years ago

After careful consideration and taking the time to fully understand the full patch-set, I really don't think it is a good approach to re-use the "operands" list. The "operands" list contains the inputs to a specific MIR. The "side effect" element is not an element in this list IMHO. Especially since the side-effect could be totally not related to the MIR in question. (E.g. the MArrayState could have an side effect "operand" that points to a totally unrelated MObjectState).

This "side effect" variable looks more like a "dependency()" to me. (Though I don't think we can generalize dependency to also track this side-effect thing. Correct me if I'm wrong ;)).

So I still think we should add a new variable for this. I was thinking about recoverDependency(), since I think the SideEffect is kinda misleading. It just denotes an instruction we need to recover, before being able to recover that MResumePoint/MObjectState.

Note: you mentioned this was sort of the route you first took, but you didn't finish in a lot of places when we iterate over Operands we want to iterate also over this. Lets make it easier and create numXXX and getXXX which counts the operands and the dependency and returns it. I don't think that should be an issue. And it would make it more obvious when we are iterating over which items.

Another issue I have is with the fact that "recoverDependency" is sort of a stack, instead of a list. E.g. having an MResumePoint depend on a MObjectState and a MArrayState, will make MObjectState depend on MArrayState or the other way around. So it can clobber the real dependency and as a result inhibit optimizations? I can imagine we can't remove MObjectState anymore, since it has a dependency. Wouldn't it be better to store the recoverDependency in a list on MResumePoint. In that case MArrayState/MObjectState also don't need this "recoverDependency" field. I think it would be easier to read.

Smaller review issues:
> template <typename MSideEffect>
> MSideEffect *
> MResumePoint::addSideEffect(TempAllocator &alloc, MSideEffect *sideEffect)

Please don't use MXXX for a template name. I went searching for when we added this MIR when seeing the code.

> MInstruction *
> MBasicBlock::safeInsertTop(MDefinition *ins)

getFirstSafeInsertPosition?


> // If we have to recover side-effects, and if we are not interested in the
> // default value of the instruction, then we have to check if the recover
> // instruction results are available.
> if (alloc.needSideEffect() && !(rm & RM_AlwaysDefault)) {

What is this "rm & RM_AlwaysDefault" ?

> _(RecoveredSideEffects) 
The comment above this MIR Flag_accessor contains some garbage. Also this results in set/isRecoveredSideEffects, while this should be more along the line of hasRecoveredSideEffects or hasRecoveredDependencies. What about: "DependingOnEffectfulRecovering", which would translate in:set/isDependingOnEffectfulRecovering.

> bool hasNextSideEffect() const {
> 	return getUseFor(sideEffectIndex())->hasProducer();
> }
> MDefinition *nextSideEffect() const {
> 	return getOperand(sideEffectIndex());
> }
> void setPreviousSideEffect(MDefinition *def) {
> 	MOZ_ASSERT(!hasNextSideEffect());
> 	initProducer(sideEffectIndex(), def);
> }

The "next/previous" thing for just getting the sideEffect is strange. We should loose that! While I think I know why you added it, it is very confusing and doesn't help explaining it better.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 6 • 10 years ago

Just a quick reply …

(In reply to Hannes Verschore [:h4writer] from comment #5)
> Another issue I have is with the fact that "recoverDependency" is sort of a
> stack, instead of a list. E.g. having an MResumePoint depend on a
> MObjectState and a MArrayState, will make MObjectState depend on MArrayState
> or the other way around. So it can clobber the real dependency and as a
> result inhibit optimizations? I can imagine we can't remove MObjectState
> anymore, since it has a dependency.

I am not sure to understand what you mean by "clobber the real dependency".  If you mean that we have an unrelated operand, yes.  Does this inhibit optimizations, no this does not.

The only optimization that is valid on MObjectState / MArrayState is to remove them when they are unused.  Knowing that they are only used by Resume Points in a side-effect stack after these patches.  So havoing these as operands does not inhibit anything optimization.

On the other hand, even if this were to inhibit DCE to remove these side-effect instructions from the MIRGraph, this would be mostly useless as any other optimization ignore the MObjectState / MArrayState.  If they are dead, they would never appear in any Resume Point / Snapshot, and thus the operands of the side-effect will not be captured either.

If you are troubled by the spaghetti stack, and think that we would keep a dead bottom alive, because the top of the stack is live, then this is a not a valid problem.  If we push a side-effect in this stack, is only because we need to recover it in the imaginary side-exit branch which is executed by the bailout.  As soon as something is pushed there, there is no way and no reason to remove it from there.  If they were reasons, this would be to undo the work, in which case this is probably not the right place to address the problem.

> Wouldn't it be better to store the
> recoverDependency in a list on MResumePoint. In that case
> MArrayState/MObjectState also don't need this "recoverDependency" field. I
> think it would be easier to read.

I thought of doing this first.

One of the concern of having side-effects is the memory cost for recording them.
The operation which are needed for side-effects on resume points are "adding" and "iterating". (not removing, see above)

The number of side-effect is always less than the number of resume point, as any side-effect instruction has a resume point. The memory constraint implies that we want to be sharing as much memory as possible between resume points. Sharing is backed up by the lack of removing/replacing operations.

Having a list without any sharing mechanism sounds tempting. Lists are mutable structures, and thus not suited for sharing. This implies that even the worse spaghetti stack order with sharing would always be better memory wise than having a list for each resume point.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 7 • 10 years ago

(In reply to Hannes Verschore [:h4writer] from comment #5)
> > // If we have to recover side-effects, and if we are not interested in the
> > // default value of the instruction, then we have to check if the recover
> > // instruction results are available.
> > if (alloc.needSideEffect() && !(rm & RM_AlwaysDefault)) {
> 
> What is this "rm & RM_AlwaysDefault" ?

This is part 2.0 of Bug 1073033 which is blocked on this issue.

	Hannes Verschore [:h4writer]
	Comment 8 • 10 years ago

(In reply to Nicolas B. Pierron [:nbp] from comment #6)
> Just a quick reply …
> 
> (In reply to Hannes Verschore [:h4writer] from comment #5)
> > Another issue I have is with the fact that "recoverDependency" is sort of a
> > stack, instead of a list. E.g. having an MResumePoint depend on a
> > MObjectState and a MArrayState, will make MObjectState depend on MArrayState
> > or the other way around. So it can clobber the real dependency and as a
> > result inhibit optimizations? I can imagine we can't remove MObjectState
> > anymore, since it has a dependency.
> 
> I am not sure to understand what you mean by "clobber the real dependency". 
> If you mean that we have an unrelated operand, yes.  Does this inhibit
> optimizations, no this does not.
> 
> The only optimization that is valid on MObjectState / MArrayState is to
> remove them when they are unused.  Knowing that they are only used by Resume
> Points in a side-effect stack after these patches.  So havoing these as
> operands does not inhibit anything optimization.

The only optimization !currently! valid on ...
Since you are trying to generalize with using "operands_" you are trying to fit into the system of other optimizations right? If not, this is another argument for having this field not in "operands_". If yes, then I can foresee this will happen.

I think the idea behind this patch is good, but I really think you should not use "operands_" for this. There should be a separate field for it. I think I would have r+ it if only was changed.

> > Wouldn't it be better to store the
> > recoverDependency in a list on MResumePoint. In that case
> > MArrayState/MObjectState also don't need this "recoverDependency" field. I
> > think it would be easier to read.
> 
> I thought of doing this first.
> 
> One of the concern of having side-effects is the memory cost for recording
> them.
> The operation which are needed for side-effects on resume points are
> "adding" and "iterating". (not removing, see above)

FYI, this was just a question. Not a blocker statement. I wanted to know why not going for a list. So I can agree with such a design. Dependency() has a similar idea that it actually can point to something that is totally not related to that MIR. So a stack-like spaghetti stack is fine.

(Looking at dependency() the graph would be more accurate if dependency() was a list, instead of one field. That would allow more optimizations, off course with the trade-off for more memory. I was thinking there is a similar trade-off with this side-effect field. That a list would allow more optimizations with the trade-off of more memory. Seems like your comment agrees with this and that you choose to use less memory, ?since the possible extra optimization will be negligible nexto the increase in memory use?)

	Nicolas B. Pierron [:nbp] Assignee
	Comment 9 • 10 years ago

(In reply to Hannes Verschore [:h4writer] from comment #8)
> I think the idea behind this patch is good, but I really think you should
> not use "operands_" for this. There should be a separate field for it. I
> think I would have r+ it if only was changed.

I will address this issue in a few days.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 10 • 10 years ago

Work around clang3.3 warning which breaks the compilation when compiling with -Werror.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 15 • 10 years ago

Comment on attachment 8529055 [details] [diff] [review]
part 4 - Scalar replacement register side-effects instead of replacing resume points operands. r=

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

::: js/src/jit/ScalarReplacement.cpp
@@ +398,5 @@
>  {
> +    // As long as the MObjectState is not yet seen next to the allocation, we do
> +    // not patch the resume point to recover the side effects.
> +    if (!state_->isInWorklist())
> +        lastSideEffect_ = rp->addSideEffect(alloc_, state_, lastSideEffect_);

fixed: Check the returned value, and return false if the allocation fail.

@@ +884,5 @@
>  {
> +    // As long as the MArrayState is not yet seen next to the allocation, we do
> +    // not patch the resume point to recover the side effects.
> +    if (!state_->isInWorklist())
> +        lastSideEffect_ = rp->addSideEffect(alloc_, state_, lastSideEffect_);

fixed: Check the returned value, and return false if the allocation fail.

	Jan de Mooij [:jandem]
	Comment 16 • 10 years ago

Comment on attachment 8529051 [details] [diff] [review]
no bug - Fix clang 3.3 warning. r=

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

Heh, jsclist.h

::: js/src/vm/Debugger.cpp
@@ +274,5 @@
>  
>  void
>  BreakpointSite::destroyIfEmpty(FreeOp *fop)
>  {
> +    if (false || JS_CLIST_IS_EMPTY(&breakpoints))

I'd prefer:
  if (!!JS_CLIST_IS_EMPTY(&breakpoints))
or
  if (bool(JS_...))

I think they are less confusing.

	Hannes Verschore [:h4writer]
	Comment 17 • 10 years ago

Comment on attachment 8529052 [details] [diff] [review]
part 1 - Add Spaghetti stack. r=

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

::: js/src/jit/InlineList.h
@@ +626,5 @@
> +        InlineSpaghettiStackIterator<T> old(*this);
> +        operator++();
> +        return old;
> +    }
> +    T * operator *() const {

Style nit: T *operator

@@ +629,5 @@
> +    }
> +    T * operator *() const {
> +        return static_cast<T *>(iter);
> +    }
> +    T * operator ->() const {

Style nit: T *operator

	Hannes Verschore [:h4writer]
	Comment 18 • 10 years ago

Comment on attachment 8529053 [details] [diff] [review]
part 2 - Add a spaghetti stack of side-effects on resume points. r=

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

r+ with the adjustment described below fixed.

::: js/src/jit/MIR.cpp
@@ +2762,5 @@
>  
> +const MSideEffectList *
> +MResumePoint::addSideEffect(TempAllocator &alloc, MDefinition *def,
> +                            const MSideEffectList *lastSideEffects)
> +{

- Take MResumePoint as argument instead of the MSideEffectList
- change "addSideEffect" to "addStores"
- change "MDefinition *def" to "MDefinition *store"
- change "const MSideEffectList *lastSideEffects" to "const MResumePoint *cache = nullptr"
- add comment explaining the cache is not required, but will help reduce memory.
- Only return bool for if this failed or not. (instead of the MSideEffectList)

::: js/src/jit/MIR.h
@@ +11351,5 @@
>  
> +// This is an element of a spaghetti stack which is used to represent the memory
> +// context which has to be restored in case of a bailout.
> +struct MSideEffect : public TempObject, public InlineSpaghettiStackNode<MSideEffect>
> +{

1) Change the "MSideEffectList" name to "MStoreToRecover"

@@ +11383,5 @@
>      friend void AssertBasicGraphCoherency(MIRGraph &graph);
>  
> +    // List of stack slots needed to reconstruct the frame corresponding to the
> +    // function which is compiled by IonBuilder. An extra operand is allocated
> +    // to hold the side-effect, in case any are registered later.

Update comment, which is totally wrong now.

@@ +11388,2 @@
>      FixedList<MUse> operands_;
> +    MSideEffectList sideEffects_;

MStoresToRecoverList storesToRecover_;

@@ +11500,5 @@
> +    // returning the side-effect list of the resume point such that the list can
> +    // be shared between resume points, and reconstructed if they do not share a
> +    // common base.
> +    const MSideEffectList *addSideEffect(TempAllocator &alloc, MDefinition *def,
> +                                         const MSideEffectList *lastSideEffects);

Don't return anything in this function. The name only suggests it will add the StoreToRecover, it shouldn't do something

@@ +11506,5 @@
> +        return sideEffects_.begin();
> +    }
> +    MSideEffectList::iterator sideEffectEnd() const {
> +        return sideEffects_.end();
> +    }

adjust to storesBegin() and storesEnd()

	Hannes Verschore [:h4writer]
	Comment 19 • 10 years ago

Comment on attachment 8529054 [details] [diff] [review]
part 3 - Enforce recovery of side-effects before reading object values. r=

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

r+ with the requested changes

r/side-effects/(recovered)stores/g

::: js/src/jit/IonFrames.cpp
@@ +1673,5 @@
>  SnapshotIterator::allocationReadable(const RValueAllocation &alloc, ReadMethod rm)
>  {
> +    // If we have to recover side-effects, and if we are not interested in the
> +    // default value of the instruction, then we have to check if the recover
> +    // instruction results are available.

r/side-effects/stores/

::: js/src/jit/MIR.h
@@ +106,5 @@
> +     * side-effects which were supposed to happen before recovering the state of
> +     * the instruction. This flag is used to annotate instructions which are
> +     * expecting the side-effects to be executed before the recovery of the
> +     * value.
> +     */                                                                         \

Fix comment!

	Hannes Verschore [:h4writer]
	Comment 20 • 10 years ago

Comment on attachment 8529055 [details] [diff] [review]
part 4 - Scalar replacement register side-effects instead of replacing resume points operands. r=

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

r+ with the requested changes

::: js/src/jit/MIRGraph.cpp
@@ +797,5 @@
>  
> +MInstruction *
> +MBasicBlock::safeInsertTop(MDefinition *ins)
> +{
> +    // Beta nodes and interrupt checks are required to be located at the

s/safeInsertTop/firstSafeInsertPosition/g

::: js/src/jit/ScalarReplacement.cpp
@@ +217,5 @@
>      MConstant *undefinedVal_;
>      MInstruction *obj_;
>      MBasicBlock *startBlock_;
>      BlockState *state_;
> +    const MSideEffectList *lastSideEffect_;

// Used to decrease memory usage
const MResumePoint *lastResumePoint_;

@@ +398,5 @@
>  {
> +    // As long as the MObjectState is not yet seen next to the allocation, we do
> +    // not patch the resume point to recover the side effects.
> +    if (!state_->isInWorklist())
> +        lastSideEffect_ = rp->addSideEffect(alloc_, state_, lastSideEffect_);

Do something like:
if (!state_->isInWorklist()) {
   rp->addStores(alloc_, state_, lastResumePoint_);
   lastResumePoint_ = rp;
}

@@ +885,5 @@
> +    // As long as the MArrayState is not yet seen next to the allocation, we do
> +    // not patch the resume point to recover the side effects.
> +    if (!state_->isInWorklist())
> +        lastSideEffect_ = rp->addSideEffect(alloc_, state_, lastSideEffect_);
> +    return true;

Do something like:
if (!state_->isInWorklist()) {
   rp->addStores(alloc_, state_, lastResumePoint_);
   lastResumePoint_ = rp;
}

	Nicolas B. Pierron [:nbp] Assignee
	Comment 21 • 10 years ago

(In reply to Jan de Mooij [:jandem] from comment #16)
> ::: js/src/vm/Debugger.cpp
> @@ +274,5 @@
> >  
> >  void
> >  BreakpointSite::destroyIfEmpty(FreeOp *fop)
> >  {
> > +    if (false || JS_CLIST_IS_EMPTY(&breakpoints))
> 
> I'd prefer:
>   [...]
>   if (bool(JS_...))

I've moved the bool(...) inside the macro, this way this remove the warning and this does not pollute the uses of it.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 22 • 10 years ago

(part 0) https://hg.mozilla.org/integration/mozilla-inbound/rev/ffe14c6ff66f

I am landing these patches separately, as this one is less likely to be the source of any issues.

	Nicolas B. Pierron [:nbp] Assignee
	Comment 23 • 10 years ago

(old try) https://treeherder.mozilla.org/#/jobs?repo=try&revision=194f4ba2be53
(new try) https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=21c3ad179f32
(inbound)
https://hg.mozilla.org/integration/mozilla-inbound/rev/bc4542ef1182
https://hg.mozilla.org/integration/mozilla-inbound/rev/69c510e5fea2
https://hg.mozilla.org/integration/mozilla-inbound/rev/f5497ebe2735
https://hg.mozilla.org/integration/mozilla-inbound/rev/b421cdd4b918

	Ryan VanderMeulen [:RyanVM]
	Comment 24 • 10 years ago

https://hg.mozilla.org/mozilla-central/rev/ffe14c6ff66f
https://hg.mozilla.org/mozilla-central/rev/bc4542ef1182
https://hg.mozilla.org/mozilla-central/rev/69c510e5fea2
https://hg.mozilla.org/mozilla-central/rev/f5497ebe2735
https://hg.mozilla.org/mozilla-central/rev/b421cdd4b918