Write-up and implement the baseline IC infrastructure. These include: 1. A shared global cache of IC stubs. 2. An IC structure that is allocated at sites which stores IC states and also establishes a linked list of IC stubs state structs at each site. 3. A region after every BaselineScript that establishes the meta-information relevant to every IC: the bytecode PC for the IC, the machine-code PC for the stub, and a pointer to the first IC stub state for that location (or NULL)

Adds ascii art summarizing the IC design to BaselineIC.h

Work-in-progress patch to add proper ICs. Asking for early-review.

DESIGN PLAN =========== The overall design is pretty straightforward. Every IC will have a list of stubs that grows to handle all the different polymorphic cases that flow through the IC. At some threshold size, the IC's list of stubs is collapsed into a single megamorphic stub. There are a few key details that influence the specifics of the design: 1. Shared StubCode We'd like to share the stubcode for various kinds of stubs. The current plan is to try to share stubcode aggressively. Under the current approach, there will be exactly one StubCode object for every "kind" of stub (e.g. "Add two integers", "Check a shape and extract the value from some fixed slot", etc..). Sharing stubcode aggressively means that most stub state is factored out of the stubcode. For example, a GetProp stub which checks a shape and retrieves the field from a particular fixed slot offset in the object - would get both the shape it checks for and the slot number from its associated state structure. No such values will be "baked in" to the stub code. 2. Ability to record site-specific information in IC stubs. We'd like the ability to collect data relevant to a site using the IC system. For example, for any given stub in an IC, we may want to store a count of the number of times that stub has been used, for later analysis. 3. Ability to easily parse site-specific information from stubs. We want to simply and easily inspect a script after it's been executed a few times with the BaselineCompiler, and figure out what stubs were generated. The design specifics are focused on enabling these goals. However, if they are found to introduce unacceptable performance issues, they may be adapted or changed entirely. See the ascii art attachment 678380 [details] [diff] [review] for an overview of how ICs are structured. Every IC in the JIT code is associated with a linked list of BaselineICStub structures, of which there can be various subtypes depending on the type of the IC. For example, the add-two-integers stub for the "JSOP_ADD" operation is described by the class |BIC_AddIntInt|. These structures store the specific state relevant to a given stub, as well as a pointer to the JIT code for the stub, and a 'next' pointer to the next BaslineICStub in the IC. This linked list of BaselineICStubs is anchored from a table of BaselineICEntry structs which are inline-allocated at immediately following a BaselineScript. When the code for a stub is entered, it's called with the stub struct and the input operands stored in registers. This is a proper call and not a jump, because the shared stubcode needs to know where to return to once it's done. The stubcode uses the stub struct to retreive and modify any stub-specific state (e.g. shape pointers for shape checks, incrementing use-counts). If the stub's guard fails, then it retreives the next stub by following the 'next' pointer from the current stub, retreives the next stubcode from that struct, and does a Tail-Call to the new stubcode. A BaselineICEntry keeps track of basic IC metadata, such as: 1. The pointer to the first BaselineICStub in the linked list, as mentioned above. 2. The bytecode PC for the instruction which necessitated the IC 3. The offset within the jitcode of the return address to which the called IC stubs return (this can be used to look up the BaselineICEntry from a return address on the stack - helpful for things like GetPCScript from C++ functions called from an IC). C++ code analyzing the ICs can easily traverse the BaselineICEntry table for a script, and the BaselineICStub linked list, to discover exactly what kind of polymorphism each IC site has seen. It can also easily modify this linked list to change the way baseline ICs behave. This offers potential for instrumentation and more advanced analysis down the line.

Comment on attachment 678387 [details] [diff] [review] In-progress ICs Review of attachment 678387 [details] [diff] [review]: ----------------------------------------------------------------- Looks good overall. Below are the most important issues, once these are addressed I can take another look. ::: js/src/ion/BaselineCompiler.cpp @@ +203,5 @@ > + BaselineICEntry *ent = allocateICEntry(); > + if (!ent) > + return false; > + > + BaselineICStub *stub = BIC_IfneFallback::New(cx); We should use a more generic ToBoolean IC here, so that we can reuse it for similar ops (IFEQ, AND, maybe NOT, etc). Once the value is converted to boolean, these are all trivial to implement. @@ +314,5 @@ > + BaselineICEntry *ent = allocateICEntry(); > + if (!ent) > + return false; > + > + BaselineICStub *stub = BIC_AddFallback::New(cx); This should be a bit more generic, like BinaryArithFallback. The stub can then use the op to generate different instructions. Can you also add emit_JSOP_SUB, and have ADD/SUB call the same private method? @@ +345,5 @@ > + BaselineICEntry *ent = allocateICEntry(); > + if (!ent) > + return false; > + > + BaselineICStub *stub = BIC_LtFallback::New(cx); Can you add JSOP_GT, to see how code sharing for these ops will work? ::: js/src/ion/BaselineIC.h @@ +89,2 @@ > { > +private: Nit: class members are private by default. @@ +94,3 @@ > > + // The PC of this IC's bytecode op within the JSScript. > + uint32_t bytecodePc_; Nit: pcOffset_ to make it clear it's not a jsbytecode *. @@ +137,5 @@ > }; > > +// List of baseline IC stub kinds. > +#define BASELINE_IC_STUB_KIND_LIST(_) \ > + _(IfneFallback, JSOP_IFNE) \ In many cases, multiple ops will use the same IC. ToBoolean IC's etc we don't want to link to a single op and we can share all of them. For ADD and SUB it would be good if we had a single BinaryArith stub kind that could just emit different instructions based on the JSOp. @@ +153,5 @@ > + > +// > +// Base class for all IC stubs. > +// > +class BaselineICStub These will allow variable-length data at the end right? Not sure yet what's the best way to allocate these stubs, cx->malloc_ will probably be fine for now. With a LifoAlloc like compartment->analysisLifoAlloc we could clear them all at once on GC, but I think we also want to do that per-script. @@ +260,5 @@ > +// defining the necessary fields, constructors, and static methods. > +#define BASELINE_IC_STUB_STDDEF(kindName) \ > + private: \ > + static bool STUBCODE_INIT; \ > + static IonCode *STUBCODE; \ We can't and don't want to share stubs between runtimes, so these should be cached in a per-runtime weakmap. ::: js/src/ion/BaselineJIT.cpp @@ +161,5 @@ > return Method_Compiled; > } > > +// Be safe, align IC entry list to 8 in all cases. > +static const unsigned DataAlignment = 8; We should only do this on 64-bit platforms, maybe use sizeof(void *) or sizeof(uintptr_t)? @@ +184,3 @@ > > + script->icEntriesOffset_ = (uint32_t) (icEntryStart - buffer); > + script->icEntries_ = icEntries; When we add more types here, imo using a separate cursor is clearer and it matches the other JITs. ::: js/src/ion/x86/BaselineHelpers-x86.h @@ +32,5 @@ > + // Call the stubcode. > + masm.call(BaselineTailCallReg); > +} > + > +inline void BaselineEmitTailCall(IonCode *target, MacroAssembler &masm) { Would be good to drop the Baseline prefix here. Baseline* seems useful for code that will be used by the VM or Ion code (BaselineScript etc), but for baseline-only code it gets very verbose.

Just thinking, using different stub kinds for AddIntInt/SubIntInt etc may be simpler than using a single Kind with different JSOp's. But it would still be good if they could use the same (BinaryArith or something) stub class, and have codegen switch based on the StubKind.

I just wanted to leave a note about style. It's really nice if you indent public: and private: by two spaces. When you use diff -p (which everyone does), it just scans upwards to find the first bit of code in column 0 to use as the function name. If you don't indent public:, it will just find public:, which isn't very useful. If you do indent public:, it will find the class name, which is a lot more useful.

Thanks for the quick review. Generally agreed on all the comments - I'll just respond to the parts where I have follow-up comments or questions about. I'll work on integrating the other suggestions. (In reply to Jan de Mooij [:jandem] from comment #4) > Comment on attachment 678387 [details] [diff] [review] > ::: js/src/ion/BaselineCompiler.cpp > @@ +203,5 @@ > > + BaselineICEntry *ent = allocateICEntry(); > > + if (!ent) > > + return false; > > + > > + BaselineICStub *stub = BIC_IfneFallback::New(cx); > > We should use a more generic ToBoolean IC here, so that we can reuse it for > similar ops (IFEQ, AND, maybe NOT, etc). Once the value is converted to > boolean, these are all trivial to implement. That sounds like a good idea. I started trying to implement IFNE "for reals" last night and ran into the issue of having to forward the jump targets into the IC to perform the branch, which got really complicated. So I ended up implementing IFNE as a ToBoolean IC anyway, and the test-and-branch instruction itself is emitted in the mainline code, assuming a pure boolean in R0 returned by the IC. Sharing this between all the similar ops should be straightforward. > @@ +314,5 @@ > > + BaselineICEntry *ent = allocateICEntry(); > > + if (!ent) > > + return false; > > + > > + BaselineICStub *stub = BIC_AddFallback::New(cx); > > This should be a bit more generic, like BinaryArithFallback. The stub can > then use the op to generate different instructions. Can you also add > emit_JSOP_SUB, and have ADD/SUB call the same private method? > ... > Can you add JSOP_GT, to see how code sharing for these ops will work? Sure. I'd like to get this working enough that it runs correctly on the simple test program you used to test your prototype, and then commit it, and refactor it after that, though. However, I do think you're right about allowing the design to more easily share kinds-of-stubs, so I'll make those name changes before checking in, and I'll change the Kind names from being like "AddIntInt" to "BinaryOpIntInt", and "LtIntInt" to "CompareOpIntInt". > These will allow variable-length data at the end right? Not sure yet what's > the best way to allocate these stubs, cx->malloc_ will probably be fine for > now. With a LifoAlloc like compartment->analysisLifoAlloc we could clear > them all at once on GC, but I think we also want to do that per-script. Agreed. I'm just using |new| for now to get something up and running. > We can't and don't want to share stubs between runtimes, so these should be > cached in a per-runtime weakmap. Cool. That refactor should be easier to do after checkin. I want to keep the scope of this initial implementation small and then fix up the issues after checkin. > When we add more types here, imo using a separate cursor is clearer and it > matches the other JITs. What do you mean by "separate cursor"?

Updated patch with comments addressed (billm: I fixed the class-visibility-keyword indentation as well). Comments not addressed are noted below. Major changes: 1. Removed the old CPP Macro based system for declaring stub classes and went with a template-based approach, which should be cleaner. 2. Fallback stubs are now shared. AddFallback has been replaced by BinaryArith_Fallback. LtFallback by Compare_Fallback. IfneFallback by ToBool_Fallback. 3. The IfneBool stub went away. All the IFNE, IFEQ, AND, OR, etc. stubs will be ToBool ICs with the branching behaviour emitted in the mainline code operating on the result of the ToBool. 4. Added JSOP_GT support, to provide simple demo of code sharing. 5. Various minor naming changes and cleanups. Things not addressed from comments: 1. Proper allocation of stubs. Currently stubs are just being allocated with "new". 2. Globally static StubCode pointers held in fields of the stub classes. They're still there. Havn't added a per-runtime WeakMap cache yet. I'm hoping these can be addressed after push.

Just for kicks I did some quick measurements on these stubs vs. JM-no-TI vs. JM-with-TI, on the following script, for varying values of CONSTANT. function foo() { var i = 0; while(i < CONSTANT) { i = i + 1; } return i; } Note that these ICs do NOT have any inline paths - they force a call-and-return on EVERY operation of note. Results are in milliseconds. CONSTANT BASELINE JM-NO-TI JM-WITH-TI ------------------------------------------------------------------ 1 Million 6 3 1.4 10 Million 54 24 10 100 Million 532 237 90 Clearly inlining integer ADD and LT, and boolean IFNE in these cases will probably make up the difference between BASELINE and JM-NO-TI, but we shall see. But we're getting in the right ballpark. I'd like to compare this to Jan's original prototype implementation to see what the added overhead of passing stub pointers and not having patchable calls works out to.

Comment on attachment 678970 [details] [diff] [review] Add ICs Review of attachment 678970 [details] [diff] [review]: ----------------------------------------------------------------- I'm fine with fixing the allocation and adding the per-runtime cache later, if you add an XXX comment and file follow-up bugs. I think it would be good to get the IC class structure mostly finished though, since it's going to be one of the most important parts of the compiler. The main problems I think we still have to address are: (1) There will be a large number of very similar stub classes, it would be good to have for instance a single CompareInt32 class and stub kind. (2) The use of templates feels like it could be simplified (virtual methods or something?) (3) It feels like the generateStubCode methods should be a member of the actual stub for which it's generating code. One way to address these is to separate the stub format from the actual stub compilation, a bit like JM IC's: // ---- Structures to define the layout: class BaselineStub { uint16_t kind_; void *stubCode_; BaselineICStub *next_; }; class BaselineGetPropertyStub : public BaselineStub { Shape *shape_; }; class BaselineFallbackStub : public BaselineStub { BaselineICEntry *icEntry_; uint32_t numOptimizedStubs_; BaselineICStub **lastStubPtrAddr_; }; // ---- Classes to generate these: class StubCompiler { private: virtual int32_t getKey() = 0; virtual IonCode *generateStubCode(JSContext *cx) = 0; public: BaselineStub *getStub(JSContext *cx) { int32_t key = getKey(); if (key in map) { code = map[key]; } else { code = generateStubCode(cx); map[key] = code; } return allocateStub(code); } }; class CompareInt32Compiler : public StubCompiler { JSOp op_; virtual IonCode *generateStubCode(JSContext *cx); virtual int32_t getKey() { // Code can be shared iff the op and stubKind are the same. return (op_ << 16) | StubKind_CompareInt32; }; public: CompareInt32Compiler(JSOp op) { } }; // ---- To generate the stub: CompareInt32Compiler gen(op); stub->addStub(gen->getStub()); Let me know if this makes sense... ::: js/src/ion/BaselineCompiler.h @@ +80,5 @@ > OPCODE_LIST(EMIT_OP) > #undef EMIT_OP > + > + // Handles JSOP_LT and JSOP_GT > + bool emit_Compare(); Nit: emitCompare (the emit_* methods are automatically generated, but for others we should follow the style guide). ::: js/src/ion/BaselineIC.cpp @@ +86,5 @@ > + if (lhs.isInt32()) { > + if (rhs.isInt32()) { > + switch(op) { > + case JSOP_LT: { > + BIC_Lt_IntInt *intIntStub = BIC_Lt_IntInt::New(cx); Having a single CompareInt class and passing the stub kind or JSOp to it could simplify this a lot. ::: js/src/ion/BaselineIC.h @@ +190,5 @@ > + // to 2**16 = 64K and grows down until reaching zero. This so that the assembly > + // that maintains this count can do a simple flag-check to figure out when it > + // has reached the threshold. > + uint16_t reverseCount_; > + static const uint16_t REVERSE_COUNT_INIT = 0xffffU; I like the idea, but we should leave this out for now I think, we can keep track of the use count later when we can do something with this information and know whether updating and storing it is worth the overhead. @@ +205,5 @@ > + : kind_((uint16_t) kind | (isFallback ? 0x8000U : 0x0000U)), > + reverseCount_(REVERSE_COUNT_INIT), > + stubCode_(stubCode->raw()), next_(NULL) > + { > + JS_ASSERT(stubCode != NULL); We should assert kind and isFallback are stored correctly (the asserts will fail if kind has the upper bit set or something equally bogus). JS_ASSERT(kind() == kind); JS_ASSERT(isFallback() == isFallback); @@ +374,2 @@ > > +class BIC_Add_IntInt : public BaselineICStdStub<BaselineICStub::Kind_Add_IntInt> Standard naming convention is BICAddInInt, and we can drop the B. What about StubAddInt32 or IAddInt32, a bit similar to Ion's MIR/LIR instructions?

(In reply to Jan de Mooij [:jandem] from comment #10) > I'm fine with fixing the allocation and adding the per-runtime cache later, > if you add an XXX comment and file follow-up bugs. I think it would be good > to get the IC class structure mostly finished though, since it's going to be > one of the most important parts of the compiler. > > The main problems I think we still have to address are: > > (1) There will be a large number of very similar stub classes, it would be > good to have for instance a single CompareInt32 class and stub kind. I agree. Originally, I figured that we would want to have the opcode directly reflected in the kind, but I wasn't considering that during analysis we could get that from the bytecode itself, so yeah, the kind only needs to track specialization info for a given class of opcodes. > (2) The use of templates feels like it could be simplified (virtual methods > or something?) I was trying to avoid using virtual methods mostly to avoid the extra vtable word. On 64-bit systems this would be 8 bytes per stub, which seemed heavyweight, but I guess that may not be that big of an issue in the end. So we're talking about an extra 2 to 6 bytes per stub to go the vtable route as compared to the template route. I suppose that's not actually all that bad. It's not like we're expecting a ton of stubs per script. I might be trying to optimize this too hard. What do you think? > (3) It feels like the generateStubCode methods should be a member of the > actual stub for which it's generating code. > > One way to address these is to separate the stub format from the actual stub > compilation, a bit like JM IC's: > > // ---- Structures to define the layout: > > class BaselineStub > { > uint16_t kind_; > void *stubCode_; > BaselineICStub *next_; > }; > > class BaselineGetPropertyStub : public BaselineStub > { > Shape *shape_; > }; > > class BaselineFallbackStub : public BaselineStub > { > BaselineICEntry *icEntry_; > uint32_t numOptimizedStubs_; > BaselineICStub **lastStubPtrAddr_; > }; > > // ---- Classes to generate these: > > class StubCompiler > { > private: > virtual int32_t getKey() = 0; > virtual IonCode *generateStubCode(JSContext *cx) = 0; > > public: > BaselineStub *getStub(JSContext *cx) { > int32_t key = getKey(); > if (key in map) { > code = map[key]; > } else { > code = generateStubCode(cx); > map[key] = code; > } > return allocateStub(code); > } > }; > > class CompareInt32Compiler : public StubCompiler > { > JSOp op_; > virtual IonCode *generateStubCode(JSContext *cx); > virtual int32_t getKey() { > // Code can be shared iff the op and stubKind are the same. > return (op_ << 16) | StubKind_CompareInt32; > }; > > public: > CompareInt32Compiler(JSOp op) { } > }; > > // ---- To generate the stub: > > CompareInt32Compiler gen(op); > stub->addStub(gen->getStub()); > > Let me know if this makes sense... This seems reasonable enough to me. > @@ +374,2 @@ > > > > +class BIC_Add_IntInt : public BaselineICStdStub<BaselineICStub::Kind_Add_IntInt> > > Standard naming convention is BICAddInInt, and we can drop the B. What about > StubAddInt32 or IAddInt32, a bit similar to Ion's MIR/LIR instructions? IAddInt32 seems too cryptic to me. We need more than an "I". StubAddInt32 sounds ok to me, but I'd like to separate out the specialization part in the name - i.e. "StubAdd_Int32". If we don't we'll get readability issues when we run into more complex names. For example, consider the "ToBool" stub specialized for bool values. It would be named "StubToBoolBool". The camel-casing causes everything to run in together. If we separate it out as "StubToBool_Bool" the intent seems much clearer.

Also, if we're going to go with virtual methods, we can eliminate the storage of |kind| and |isFallback|, instead exposing them via virtual methods - implicitly through the vtable and overridden method definitions. That choice will make them less accessible to JITCode, but that may not really be a problem since I don't expect to need to investigate stub types from jitcode. I'm working on making these changes and we can see what it looks like. You're right that it does simplify the template stuff a lot.

(In reply to Kannan Vijayan [:djvj] from comment #11) > > I was trying to avoid using virtual methods mostly to avoid the extra vtable > word. On 64-bit systems this would be 8 bytes per stub, which seemed > heavyweight, but I guess that may not be that big of an issue in the end. > So we're talking about an extra 2 to 6 bytes per stub to go the vtable route > as compared to the template route. > > I suppose that's not actually all that bad. It's not like we're expecting a > ton of stubs per script. I might be trying to optimize this too hard. > > What do you think? Yeah I think we really want to avoid storing the vtable pointer, there will be a pretty large number of stubs (at least one for every non-trivial JSOp, and likely multiple ones for property access ops) and especially on mobile we should be careful. What I like about the design in comment 10 is that it allows us to use virtual methods when we generate the stub, but it doesn't store any vtable pointers in the stub itself. > IAddInt32 seems too cryptic to me. We need more than an "I". StubAddInt32 > sounds ok to me, but I'd like to separate out the specialization part in the > name - i.e. "StubAdd_Int32". If we don't we'll get readability issues when > we run into more complex names. For example, consider the "ToBool" stub > specialized for bool values. It would be named "StubToBoolBool". The > camel-casing causes everything to run in together. If we separate it out as > "StubToBool_Bool" the intent seems much clearer. Agreed, that makes sense.

Ok I made the changes along the lines you suggested. For naming I went with the convention "IC<NAME>_<SPEC>" e.g. "ICBinaryArith_Int32" for stub classes. Also, the compiler class for a given stub is nested within the stub class itself. E.g.: ICBinaryArith_Int32::Compiler I also dropped the Baseline prefix from the other IC classes.

Comment on attachment 679718 [details] [diff] [review] New ICs Review of attachment 679718 [details] [diff] [review]: ----------------------------------------------------------------- Looks great! Nice idea to put the Compiler inside the class. ::: js/src/ion/BaselineCompiler.h @@ +80,5 @@ > OPCODE_LIST(EMIT_OP) > #undef EMIT_OP > + > + // Handles JSOP_LT and JSOP_GT > + bool emit_Compare(); Nit: emitCompare ::: js/src/ion/BaselineIC.cpp @@ +92,5 @@ > > IonCompartment *ion = cx->compartment->ionCompartment(); > IonCode *wrapper = ion->generateVMWrapper(cx, fun); > if (!wrapper) > return false; Can we move these four lines into a base class method? ::: js/src/ion/x86/BaselineHelpers-x86.h @@ +14,5 @@ > + > +namespace js { > +namespace ion { > + > +inline void EmitCallIC(CodeOffsetLabel *patchOffset, MacroAssembler &masm) { Style nit: line break before EmitCallIC (and functions below)

Nits fixed and pushed. ASCII-art comment patch: https://hg.mozilla.org/projects/ionmonkey/rev/7b13a9d16d62 Actual IC implementation patch: https://hg.mozilla.org/projects/ionmonkey/rev/888e1a60eaea Not closing this bug since this should be a meta-bug for completing ICs for all the relevant JS ops.

(In reply to Kannan Vijayan [:djvj] from comment #16) > Not closing this bug since this should be a meta-bug for completing ICs for > all the relevant JS ops. Please put "leave open" in the whiteboard.