813606 - BaselineCompiler: Add IC for monitoring types

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Kannan Vijayan [:djvj]]

Baseline will need to monitor the types of values resulting from operations like GETPROP and GETELEM and CALL.  This can be handled by a nested typecheck IC hanging off of each regular stub for the operation.

Comment 1

[Kannan Vijayan [:djvj]]

After talking with Jan on IRC, we have settled on the following rough design for typecheck ICs.  Comment for feedback.

//
// Type ICs
//
// Type ICs are otherwise regular ICs that are actually nested within
// other IC chains.  They serve to optimize locations in the code where the
// baseline compiler would have otherwise had to perform a type Monitor operation
// (e.g. the result of GetProp, GetElem, etc.), or locations where the baseline
// compiler would have had to modify a heap typeset using the type of an input
// value (e.g. SetProp, SetElem, etc.)
//
// There are two kinds of Type ICs: Monitor and Update.
//
// TypeMonitor ICs
// ---------------
// Monitor ICs are shared between stubs in the general IC, and monitor the resulting
// types of getter operations (call returns, getprop outputs, etc.)
//
//        +-----------+     +-----------+     +-----------+     +-----------+
//   ---->| Stub 1    |---->| Stub 2    |---->| Stub 3    |---->| FB Stub   |
//        +-----------+     +-----------+     +-----------+     +-----------+
//             |                  |                 |                  |
//             |------------------/-----------------/                  |
//             v                                                       |
//        +-----------+     +-----------+     +-----------+            |
//        | Type 1    |---->| Type 2    |---->| Type FB   |            |
//        +-----------+     +-----------+     +-----------+            |
//             |                 |                  |                  |
//  <----------/-----------------/------------------/------------------/
//                r e t u r n    p a t h
//
// After an optimized IC stub successfully executes, it passes control to the type stub
// chain to check the resulting type.  If no type stub succeeds, and the monitor fallback
// stub is reached, the monitor fallback stub performs a manual monitor, and also adds the
// appropriate type stub to the chain.
//
// The IC's main fallback, in addition to generating new mainline stubs, also generates
// type stubs as reflected by its returned value.
//
// NOTE: The type IC chain returns directly to the mainline code, not back to the
// stub it was entered from.  Thus, entering a type IC is a matter of a |jump|, not
// a |call|.  This allows us to safely call a VM Monitor function from within the monitor IC's
// fallback chain, since the return address (needed for stack inspection) is preserved.
// 
//
// TypeUpdate ICs
// --------------
// Update ICs update heap typesets and monitor the input types of setter operations
// (getprop, setprop inputs, etc.).  Unlike monitor ICs, they are not shared
// between stubs on an IC, but instead are kept track of on a per-stub basis.
//
// This is because the main stubs for the operation will each identify a potentially
// different TypeObject to update.  New input types must be tracked on a typeobject-to-
// typeobject basis.
//
// However, the typechains for TypeUpdate ICs do not have their own fallbacks.  This
// is because the type update stubs do NOT return to the mainline code (as with monitor
// ICs).  They return back to the stub they were entered from.  This means that they
// must be entered via a |call|, which alters the return address, and makes it
// difficult to make VMCalls while still allowing for stack inspection.
//
// To deal with this issue, we take the following steps:
//  [1] We guarantee that the type update IC is entered with the stack state and
//      registers R0 & R1 reflecting what the main IC stubs expect.
//
//  [2] The original return address is passed as a register argument into the type
//      update ICs (in R2.scratchReg())
//
//  [3] The last type check stub in any individual chain sends control flow to
//      an "Update fallback" stub, which is shared beteen all chains on an IC.
//      the update fallback stub has the sole job of jumping to a different entry
//      point on the regular fallback stub.
//
//  [4] The IC's main fallback stub has two entry points: the regular one that
//      is entered when all IC stubs fail their guards, and a special entry
//      point for when an IC stub succeeded, but its subsequent typechecks all
//      failed.  In the latter case, the fallback stub fixes its stack state,
//      and jumps into main fallback stub codepath, which does the operation as
//      well as the typeset update manually.  Along with adding a new IC stub
//      for the operation (if that's possible), it also initializes the type
//      stub chain for that IC stub to include the input type seen.
//
//                                 r e t u r n    p a t h
//   <--------------.-----------------.-----------------.-----------------.
//                  |                 |                 |                 |
//        +-----------+     +-----------+     +-----------+     +-----------+
//   ---->| Stub 1    |---->| Stub 2    |---->| Stub 3    |---->| FB Stub   |
//        +-----------+     +-----------+     +-----------+     +-----------+
//          |   ^             |   ^             |   ^                ^
//          |   |             |   |             |   |                |
//          |   |             |   |             |   |                |
//          |   |             |   |             v   |                |
//          |   |             |   |         +-----------+    +-----------+
//          |   |             |   |         | Type 3.1  |--->| Update FB |
//          |   |             |   |         +-----------+    +-----------+
//          |   |             |   |                                   ^
//          |   |             |   \-------------.-----------------.   |
//          |   |             |   |             |                 |   \------.
//          |   |             v   |             |                 |          |
//          |   |         +-----------+     +-----------+     +-----------+  |
//          |   |         | Type 2.1  |---->| Type 2.2  |---->| Type 2.3  |--/
//          |   |         +-----------+     +-----------+     +-----------+  |
//          |   |                                                            |
//          |   \-------------.                                              |
//          |   |             |                                              |
//          v   |             |                                              |
//     +-----------+     +-----------+                                       |
//     | Type 1.1  |---->| Type 1.2  |---------------------------------------/
//     +-----------+     +-----------+
//

Comment 2

[Jan de Mooij [:jandem]]

Awesome comment and ASCII art. Looks good, if we can get this to work as described we can collect great type information.

(In reply to Kannan Vijayan [:djvj] from comment #1)
> // Update ICs update heap typesets and monitor the input types of setter
> operations
> // (getprop, setprop inputs, etc.).

Nit: s/getprop/setelem

Comment 3

[Kannan Vijayan [:djvj]]

Attachment: Add type monitor ICs

This patch adds in ICs for type monitoring (no optimized monitor stubs yet, but everything is in place for them).  The beginnings of type update ICs are also there, but they will need more work.

Overview of changes:

Two new stub classes are added: ICMonitoredStub and ICMonitoredFallbackStub.  These classes are intended to serve as base classes for stubs which "are monitored" (not the stubs in the monitor chain itself).

ICMonitoredFallbackStub extends ICFallbackStub with a pointer to an ICTypeMonitor_Fallback stub that represents the type monitoring chain for a given regular IC.

ICMonitoredStub extends ICStub with a pointer to the first monitor stub in the monitoring chain.

ICTypeMonitor_Fallback itself contains the following:
  1. A pointer to the main fallback stub in the IC chain.
  2. A count of the number of optimized monitor stubs in the monitoring chain
  3. A pointer to the first stub in the monitoring chain.  Initial value for this field is |this| (i.e. a pointer to the ICTypeMonitor_Fallback stub itself).


ICMonitoredFallbackStub gets a helpful initializer method called |initMonitoringChain| that creates a new ICTypeMonitor_Fallback instance and sets the local field pointing to it.

This implementation requires writers of new monitored stubs to:

1. We have to remember to call this method in the |getStub| method of the compiler for any stub inheriting from ICMonitoredFallbackStub (see ICGetElem_Fallback for an example).

2. For optimized stubs whose results are monitored, they should inherit ICMonitoredStub, and their compiler should accept an ICStub pointer to pass in for the firstMonitorStub argument during stub construction.

2. During generation of optimized stubs which have their results monitored, the generator (i.e. the fallback stub for that IC) needs to retrieve the firstMonitorStub, and use it to construct the compiler for the optimized stub.  This way, the compiler can then pass that firstMonitorStub into the construction of the actual stub.



Regarding garbage colection: monitor sub chains are traversed a single time - off of the main fallback stub for a regular IC chain.

Comment 4

[Jan de Mooij [:jandem]]

Comment on attachment 684489 [details] [diff] [review]
Add type monitor ICs

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

Looks good, r=me with comments addressed. Later we can probably simplify some parts a bit, but that seems easier to do when the other monitoring parts are in place.

::: js/src/ion/BaselineIC.cpp
@@ +130,5 @@
> +DoTypeMonitorFallback(JSContext *cx, ICTypeMonitor_Fallback *stub, HandleValue value,
> +                      MutableHandleValue res)
> +{
> +    uint8_t *returnAddr;
> +    RootedScript script(cx, GetTopIonJSScript(cx, NULL, (void **)&returnAddr));

Nit: we no longer have to pass the NULL and returnAddr arguments.

::: js/src/ion/BaselineIC.h
@@ +314,1 @@
>      uint16_t kind_;

We should try to use bit fields, so that we can just assign to them:

bool isFallback_ : 1;
bool isMonitored_ : 1;
uint16_t kind_ : 14;

@@ +643,5 @@
> +// can be retreived).
> +class ICTypeMonitor_Fallback : public ICStub
> +{
> +    // Pointer to the main fallback stub for the IC.
> +    ICFallbackStub *    mainFallbackStub_;

Nit: ICMonitoredFallbackStub

@@ +646,5 @@
> +    // Pointer to the main fallback stub for the IC.
> +    ICFallbackStub *    mainFallbackStub_;
> +
> +    // Pointer to the first monitor stub.
> +    ICStub *            firstMonitorStub_;

Nit: ICMonitoredStub

@@ +698,5 @@
> +    }
> +
> +    inline uint32_t
> +    numOptimizedMonitorStubs() const {
> +        return numOptimizedMonitorStubs_;

Nit: no return after uint32_t, same for the 2 other methods.

@@ +704,5 @@
> +
> +    bool addMonitorStubForValue(JSContext *cx, HandleValue val);
> +
> +    // Create a new monitor stub for the type of the given value, and
> +    // add it to this chain.

Nit: move comment before the previous method.

Comment 5

[Kannan Vijayan [:djvj]]

Monitoring code: https://hg.mozilla.org/projects/ionmonkey/rev/8a1f7419c136

Comment 6

[Kannan Vijayan [:djvj]]

Attachment: Type Update ICs

Type Update IC implementation.

NITs: No optimized type-update stubs are there, but the infrastructure for type update ICs is.  Also, ARM is broken because it ARM's MacroAssembler uses |lr| as a scratch register.  This will be fixed when bug 816015 is fixed and merged into our repos.  The design has changed but the ASCII art has not been changed to reflect it.  I'm submitting this so that the review of code can happen while I fix that up.

MAJOR CHANGES:

The design deviates from the previously stated design in comment 1.

TypeUpdate ICs subchains no longer have a shared fallback stub.  They each have their own fallback stub.

Secondly, the TypeUpdate IC's role has changed from ensuring that a typeset contains a given type to simply indicating whether it does or not.  The type-update IC takes its input in R0 and is expected to set R1.scratchReg() to 1 or 0 depending on if the type exists in the typeset or not.  This makes the actual type stubs very simple: optimized stubs set R1.scratchReg() to 1, and the fallback stub sets R1.scratchReg() to 0.

If 0 is returned from the TypeUpdate IC, then the main stub that called the TypeUpdate IC executes a call to a type-update-fallback function that will perform the typeset update manually, as well as generate and attach a new optimized stub to the chain.  Currently, this fallback function is a no-op.

To support the, a new ICUpdatedStub base class has been added.  This class should be the base class for any main IC stub that needs to typecheck its input.  It provides a method |initUpdatingChain|, that can be called after construction to initialize the TypeUpdate IC chain.  Any stub class which subclasses ICUpdatedStub must make sure to call this method when it is being constructed.

This patch also depends on changes that are present in the patch for bug 816503 - namely the addition of the BaselineStub frame type.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 686276 [details] [diff] [review]
Type Update ICs

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

Cool, I thought this would be a lot more complicated.

::: js/src/ion/BaselineIC.cpp
@@ +208,4 @@
>  ICTypeUpdate_Fallback::Compiler::generateStubCode(MacroAssembler &masm)
>  {
> +    // Just store false into R1.scratchReg() and return.
> +    masm.movePtr(ImmWord((uintptr_t) 0), R1.scratchReg());

Nit: masm.move32(Imm32(0), R1.scratchReg());

@@ +736,5 @@
> +
> +    // Stack is now: { ..., rhs-value, object-value, key-value, maybe?-RET-ADDR }
> +    // Load rhs-value in to R0
> +    masm.mov(BaselineStackReg, R1.scratchReg());
> +    masm.loadValue(Address(R1.scratchReg(), 2 * sizeof(Value) + ICStackValueOffset), R0);

Nit: you can use BaselineStackReg directly, since loadValue does not modify it.

::: js/src/ion/BaselineIC.h
@@ +1170,5 @@
> +            ICSetElem_Dense *stub = ICSetElem_Dense::New(getStubCode());
> +            if (!stub)
> +                return NULL;
> +            if (!stub->initUpdatingChain(cx))
> +                return NULL;

Should we "delete stub;" here? (js_delete once we move away from "new")

::: js/src/ion/arm/BaselineHelpers-arm.h
@@ +232,5 @@
> +    IonCode *code = ion->getVMWrapper(DoTypeUpdateFallbackInfo);
> +    if (!code)
> +        return false;
> +
> +    EmitCallVM(code, masm);

I think we should add it as method to ICStubCompiler, like ICStubCompiler::callTypeUpdateIC(...) so that we can use callVM() here. Thoughts?

::: js/src/ion/x64/BaselineHelpers-x64.h
@@ +215,5 @@
> +
> +    // The update IC will store 0 or 1 in R1.scratchReg() reflecting if the
> +    // value in R0 type-checked properly or not.
> +    Label success;
> +    masm.cmpPtr(R1.scratchReg(), ImmWord(1));

Nit: cmp32

::: js/src/ion/x86/BaselineHelpers-x86.h
@@ +154,5 @@
>  
>  inline void
> +EmitStowICValues(MacroAssembler &masm, int values)
> +{
> +    JS_ASSERT(values >= 0 && values <= 2);

Nit: if you make "values" unsigned or size_t, you can just assert <= 2.

Comment 8

[Kannan Vijayan [:djvj]]

Attachment: Modify SetElem_Dense to keep and guard on TypeObject

This patch should be applied on top of the TypeUpdate ICs patch posted earlier.  It modifies SetElem_Dense to guard on the TypeObject for a dense array.

Comment 9

[Jan de Mooij [:jandem]]

Comment on attachment 686861 [details] [diff] [review]
Modify SetElem_Dense to keep and guard on TypeObject

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

Looks good, but we also have to update TraceStub to call MarkTypeObject.

::: js/src/ion/BaselineIC.h
@@ +1160,5 @@
> +    static size_t offsetOfType() {
> +        return offsetof(ICSetElem_Dense, type_);
> +    }
> +
> +    types::TypeObject *type() const {

Can you make this HeapPtrTypeObject &type(), so that you can use MarkTypeObject instead of MarkTypeObjectRoot? The former is preferred according to the big comment in Marking.h

Comment 10

[Kannan Vijayan [:djvj]]

https://hg.mozilla.org/projects/ionmonkey/rev/3b7beec0c6e4

Comments and nits addressed.  Marking of TypeObjects referenced from ICSetElem_Dense stubs added.

Both patches posted above for review were checked in as a single unified patch.