878503 - [meta] IonMonkey: Add Resume instructions.

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect, P3)

Description

[Nicolas B. Pierron [:nbp]]

Attachment: Add Resume Instructions

Ion optimizations are constrained by the interpreter/baseline to be able to resume a state which can be used to continue in case of failure.

Currently these constraints are enforced by evaluating everything before the resume point which captures the expressions which are needed.  Resume instructions is a way to weaken such constraint by adding the ability to resume an instruction which has not been executed before.

In practice, this should not give any performance improvements.  On the other hand, this enable a new set of optimizations, such as escape analysis (Bug 856533), where we should be able to move instructions below the resume points or, such as JS branch profiling (Bug 877872), by removing code only used in removed branches.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Prototype: Add Resume Instructions

This patch extract the structure out of the LSnapshot to put them in charge of the LRecover.
A snapshot now contains an index into the recover buffer, which describe its structure, and a list of slots.
A Recover buffer can be shared, in the same way as MResumePoint are implicitly used by multiple MIR.

Before:
  MResumePoint ->* LSnapshot

After:
  MResumePoint structure -> LRecover
  MResumePoint operands ->* LSnapshot (allocations)

SnapshotIterators are made more clever and abstract over the structure given by the RecoverReader and the slots stored in the SnapshotReader.  The SnapshotIterator is now in charge of extracting values when this is possible, and to provide a view on the fact that a value can be read or not.

The Slot, previously located in the SnapshotReader are moved out-side of it to be able to represent locations which are corresponding to the result of the execution of a RInstruction.  A Slot is some-kind of abstract Value pointer which might be located in the code, on the stack, in a register or in the vector of results of RInstructions.  The SnapshotIterator provides way to read the Slot, to check if it is readable and to read the corresponding Value.

Delta with previous patch:
- Rebase previous patch.
- Add comments on Slots and RInstruction.

Comment 2

[Nicolas B. Pierron [:nbp]]

The current patch add a 0.2% - 0.3% regression on sunspider and kraken (checked over 1000 runs each).

Comment 3

[Jan de Mooij [:jandem]]

This looks pretty interesting and I can see how it could be useful to delay work until we actually bailout and need it.

However, what worries me is that it's a big patch that adds a lot of code/complexity but has no immediate perf/memory wins. Do we know how much escape analysis will improve our benchmark score eventually? Do we really need escape analysis, especially once we have GGC? Can we prototype that first before landing this patch?

I really think we need more data to answer these kind of questions before we land this patch.

Comment 4

[Kannan Vijayan [:djvj]]

(In reply to Jan de Mooij [:jandem] (PTO June 3-7) from comment #3)
> This looks pretty interesting and I can see how it could be useful to delay
> work until we actually bailout and need it.
> 
> However, what worries me is that it's a big patch that adds a lot of
> code/complexity but has no immediate perf/memory wins. Do we know how much
> escape analysis will improve our benchmark score eventually? Do we really
> need escape analysis, especially once we have GGC? Can we prototype that
> first before landing this patch?
> 
> I really think we need more data to answer these kind of questions before we
> land this patch.

It seems like escape analysis would be a big deal in code such as octane:raytrace, as well as game code which creates lots of temporary small objects.

GGC will be helpful in these cases, but the big win for escape analysis is in allowing us to elide allocations in the first place, avoid doing a number of heavyweight memory writes inside hot code.  Object initialization is expensive, and if we can avoid that, we can see some major wins.

I agree, though, that we should wait to land this until we are ready to start the work on escape analysis.  This patch would make more sense as the first of a series of landings implementing escape analysis.

Comment 5

[David Anderson [:dvander] - inactive, e-mail if emergency]

We definitely need to justify large patches like this. Escape analysis is a wide range of optimizations and knowing which ones we want would help direct how it is constructed. We should be able to (1) know what optimization we're aiming for (2) show that it would apply to a benchmark and (3) prototype that it would have measurable results.

Lacking any of this information, it seems premature to propose large design changes.

Comment 6

[Hannes Verschore [:h4writer]]

Comment on attachment 757058 [details] [diff] [review]
Prototype: Add Resume Instructions

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

Clearing review. We decided it is better to wait until we have an improvement, before pushing this big change into the tree.

Comment 7

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #1)
> Created attachment 757058 [details] [diff] [review]
> Add Resume Instructions

Just as a side note for people who want to see how to use this patch, here is a dummy test case I made a while ago to show how to barely used additions which might be captured in resume points.

https://github.com/nbp/mozilla-central/compare/t/resume-op...t/resume-op-test

Comment 8

[Nicolas B. Pierron [:nbp]]

Attachment: Part 1: Move Slots outside of snapshots.

This extract the Slot data structure such as later we can separate the SnapshotIterator read from the readSlot.  By moving this out-side the SnapshotReader, this avoid including the SnapshotReader header to refer to a Slot when we just want to store them in ResumeInstructions.

Comment 9

[Nicolas B. Pierron [:nbp]]

Attachment: Part 2: Remove SnapshotReader inheritance.

The Snapshot reader is a legacy which is blocking the extraction of the LResumePoint, as we expect every data to come directly from the SnapshotReader.  At the end it makes more sense to separate the two such as the SnapshotIterator becomes just a way to interpret data coming from all the information needed to recover the state of a frame.

Comment 10

[Nicolas B. Pierron [:nbp]]

Attachment: Part 3: Restart reading instead of making copies of Snapshot iterators.

Currently, we store 2 SnapshotIterators to be able to seek at the beginning of the snapshot.  

By adding the restart function, we can avoid duplicating and copying everything every time we go to the next inlined frame.

Comment 11

[Nicolas B. Pierron [:nbp]]

Attachment: Part 4: Clean-up readFrameArgs.

Move readFrameArgs from the SnapshotIterator to the InlineFrameIterator.  The goal of the snapshot iterator is not to interpret frames the data that it recovers.

Rename it to readFormalFrameArgs (which was its former intent), and simplify forEachCanonicalActualArg by separating the formal part from the overflow part.

Comment 12

[Nicolas B. Pierron [:nbp]]

Attachment: Part 5: Move readSlotByIndex to the inline frame iterator.

Move maybeReadSlotByIndex from the SnapshotIterator to the InlineFrameIterator, as the slot referred here are specific to frame usage and not generic to any kind of operations.

Comment 13

[Nicolas B. Pierron [:nbp]]

Attachment: Part 6: Extract the LResumePoint structure out of Snapshots.

Extract the frame layout from the snapshot writer.  Add a new LIR type for the resume point (LResumePoint) which are capturing the number of operands and the MIR node (resume point) which have to be recovered by the SnapshotIterator.  The LResumePoint are then encoded and packed into the RecoverBuffer and read by the SnapshotIterator, which recover the offset of it from the snapshot.

The boundary of the modification is hidden behind the SnapshotIterator which keeps the same interface as before.  And no frame logic is changed.

Comment 14

[Nicolas B. Pierron [:nbp]]

Attachment: Part 7: Add Slot default constructor.

Add a default constructor to be able to include it in other structures without having to initialize all Slots.

Comment 15

[Nicolas B. Pierron [:nbp]]

Attachment: Part 8: Add constant qualifiers on SnapshotIterator methods.

Comment 16

[Nicolas B. Pierron [:nbp]]

Attachment: Part 9: Add RResumePoint to store slots instead of copying SnapshotIterators.

Introduce a RResumePoint structure to track the ResumePoint representation and remember a few useful slots of the |scopeChain|, |argObj| and |this|.  This avoid cloning a new SnapshotIterator every time we need to access these information.

Comment 17

[Nicolas B. Pierron [:nbp]]

Attachment: Part 10: Make SnapshotIterator non-copyable.

Make SnapshotIterator seek-able & reset-able, by remembering the position of the last frame or re-initializing the content.

Create a fake random access SlotVector class to abstract over the readSlot interface.  This SlotVector use the seek feature to reinitialize the SnapshotIterator instead of making copies of it.

Comment 18

[Nicolas B. Pierron [:nbp]]

Attachment: Part 11: Move RResumePoint to the SnapshotIterator.

Move RResumePoint into the SnapshotIterator such as the Bailout code can rely on it, see part 12.

Comment 19

[Nicolas B. Pierron [:nbp]]

Attachment: Part 12: Remove skip & read from the SnapshotIterator.

Use the RResumePoint to read the data contained in the snapshot.  Remove read() & skip() functions, which gives the ability to later split the SnapshotIterator into 2.  One part for the Snapshot-To-Slot reads and the other part for the Slot-to-Value conversions.

Comment 20

[Nicolas B. Pierron [:nbp]]

Attachment: Part 13: Move RResumePoint into its own file.

Comment 21

[Nicolas B. Pierron [:nbp]]

Attachment: Part 14: Encode and decode the RResumePoint at the same location.

Make a parallel between MResumePoint::writeRecover and RResumePoint constructor.

Move the RResumePoint to the RecoverReader to be created for reading the content of the buffer.

Comment 22

[Nicolas B. Pierron [:nbp]]

Attachment: Part 15: Rename frame to instruction in the context of the RecoverReader.

Trivial renaming for adding more meaning to the followup patches.

Comment 23

[Nicolas B. Pierron [:nbp]]

Attachment: Part 16: Generalized RResumePoint to any instructions.

This patch contains the logic to convert the current code to handle any instruction as recovering instruction instead of being a normal instruction in the MIR Graph.

When an instruction is flagged as being a Recovering instruction, it would no longer be lowered and a space would be kept in the LRecover vector of instructions.  For each recovering instruction, we reserve the space for each operand in the snapshot, as well as in the recover buffer (see the parallel in part 14).  Each decoded operation will be resumed during a bailout.

Comment 24

[Nicolas B. Pierron [:nbp]]

Attachment: Part 17: Prevent aliasing of instructions with different flags.

Adding the recovering flag as part of the computation of the valueHash, such as phases like GVN won't fold a Recovering instruction with a non-recovering one.

One example would be that we can have an If branch where we do the same thing on both side of the branch.  GVN will try to fold them, where we might have flagged one as being a Recovering instruction.  In which case, we can prevent the execution in one of the branches.

Comment 25

[Hannes Verschore [:h4writer]]

Comment on attachment 778909 [details] [diff] [review]
Part 1: Move Slots outside of snapshots.

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

::: js/src/ion/Slots.h
@@ +28,5 @@
> +
> +  public:
> +
> +    class Location
> +    {

For me it doesn't make sense to have this inlined in the class Slot. Esp. since Location is also used as input to Slot construction.
Can we move this back to out of the Slot class and rename it SlotLocation ??

@@ +61,5 @@
> +            return stackSlot_ != INVALID_STACK_SLOT;
> +        }
> +    };
> +
> +    enum SlotMode

s/SlotMode/Mode

::: js/src/ion/arm/Architecture-arm.h
@@ -24,5 @@
>  //   +8 for double spills
>  static const uint32_t ION_FRAME_SLACK_SIZE   = 20;
>  
> -// An offset that is illegal for a local variable's stack allocation.
> -static const int32_t INVALID_STACK_SLOT      = -1;

Glad this is moved to platform independent file, since the value is same for all.

Comment 26

[Nicolas B. Pierron [:nbp]]

Comment on attachment 779624 [details] [diff] [review]
Part 16: Generalized RResumePoint to any instructions.

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

::: js/src/ion/MIR.h
@@ +61,5 @@
> +     * way to encode its data into the recover buffer such as the corresponding
> +     * RInstruction can be executed.  A recover instruction should never depends
> +     * on it-self.
> +     */                                                                         \
> +    _(Recovering)                                                               \

sstangl suggested that instead of flagging instructions which will be used as recovering instruction, we should move them out of the graph.

One of the reasons why I kept them in the graph is to make them captured by resume points.  But sstangl still has a good point which is highlighted by Part 17, which is that other optimizations might still work on top of instructions without looking at the flags.  So as long as these instructions are in the graph, they might still be considered in optimizations.

So, I think we should wrap these instructions in a MRecoverInstruction which will hold any instruction as a resume point, and not be considered by any other optimizations.

This way Part 17 will not be necessary and we will not have any issue with any flag that we forgot to check.

Comment 27

[Nicolas B. Pierron [:nbp]]

Jandem: If you are not convinced yet, please have a look at this draft, that I wish I can *publish after* making this refactoring.

Somebody told me that I should write it an publish it before such as I can convince people that we should do it.  But I think you will not like to be the only person standing against it, so I let you review it first:

    https://blog.mozilla.org/javascript/?p=604&preview=true

Comment 28

[Nicolas B. Pierron [:nbp]]

Attachment: IRC Q/A jandem & nbp

Comment 29

[Nicolas B. Pierron [:nbp]]

Comment on attachment 779626 [details] [diff] [review]
Part 17: Prevent aliasing of instructions with different flags.

Sorry for the noise.