Last Comment Bug 703376 - IonMonkey: Add alias sets
: IonMonkey: Add alias sets
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
-- normal (vote)
: ---
Assigned To: Jan de Mooij [:jandem]
: Jason Orendorff [:jorendorff]
Depends on: 710447
Blocks: IonMonkey
  Show dependency treegraph
Reported: 2011-11-17 13:38 PST by Jan de Mooij [:jandem]
Modified: 2011-12-19 02:31 PST (History)
8 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

Patch (45.22 KB, patch)
2011-11-24 09:08 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Patch (45.12 KB, patch)
2011-11-24 11:05 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Patch (53.96 KB, patch)
2011-11-30 06:07 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Patch (66.50 KB, patch)
2011-12-09 08:59 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Patch (66.31 KB, patch)
2011-12-09 12:43 PST, Jan de Mooij [:jandem]
dvander: review+
Details | Diff | Splinter Review

Description User image Jan de Mooij [:jandem] 2011-11-17 13:38:41 PST
JM+TI's LICM uses TI to determine the side-effects of instructions, e.g. we can compare the TypeObjects of a setelem/getelem to find out if they refer to the same object. Eventually, I'd like to use the same information for Ion's LICM and GVN optimizations.

My proposal is to add a new optimization pass (which probably only runs when TI is enabled). It traverses the graph in reverse post order and asks every instruction about 1) the effect(s) on which it depends and 2) the effect(s) it has itself. An "effect" can be something like "no side-effects" (probably most instructions), "uses/changes a certain TypeSet and property id" (used for loads and stores), "can modify everything" (used for calls), etc.

The results of these calls can be used, for instance, to maintain a list which maps a (TypeObject, jsid) tuple to the last MDefinition that modified it. When an instruction depends on a previous instruction, we look it up in the list and set its "depends" field to the instruction id we just found. For instance, when we see an MLoadSlot instruction, we set its "depends" field to the last MStoreSlot, MCall, etc instruction that modified the same TypeObject. (Loops will need some special care.)

When GVN decides whether an instruction x is dominated by another instruction y, it can look at the "depends" field of x to see if there is an implicit dependency on an instruction between x and y. LICM can do something similar: we can hoist an instruction only if its "depends" field does not refer to an instruction inside the loop.

Any thoughts?
Comment 1 User image Jan de Mooij [:jandem] 2011-11-24 09:08:09 PST
Created attachment 576784 [details] [diff] [review]

This patch adds alias sets. Tracking properties using TI is more complex, we can add it later though.

The patch adds a new alias analysis pass. It annotates every load with the most recent store on which it depends. The benefit of this approach is that GVN and LICM only need very small changes to use it (2-4 lines I think), and it's easy to improve the algorithm later.

The patch removes the Idempotent flag. It's replaced by isEffectful(), which just calls getAliasSet().isStore().
Comment 2 User image Jan de Mooij [:jandem] 2011-11-24 11:05:19 PST
Created attachment 576803 [details] [diff] [review]

Some small changes + updated license header, evilpie pointed out it was really old.
Comment 3 User image Jan de Mooij [:jandem] 2011-11-30 06:07:15 PST
Created attachment 577936 [details] [diff] [review]

Rebased + various small changes.

Passes tests and fixes check-bitops-bits-in-byte.js with -n. The test does "ret += func(y)" in an inner loop and we were hoisting the MLoadSlot.
Comment 4 User image Jan de Mooij [:jandem] 2011-11-30 06:10:43 PST
Btw, naming suggestions etc. are welcome of course.
Comment 5 User image Jan de Mooij [:jandem] 2011-12-07 13:16:22 PST
The testcase I added triggers an LSRA bug with some Ion flags. No problems with greedy or on x64.

When allocating a result register for an instruction that reuses the register of its first operand, there is a (probably rare) edge case where we can clobber a register of one of the arguments. Fix tomorrow.
Comment 6 User image Jan de Mooij [:jandem] 2011-12-09 08:59:10 PST
Created attachment 580438 [details] [diff] [review]

- Adds a Movable flag. Having GVN and LICM base decisions on isEffectful() only was a bit awkward/wrong for instructions like MPrepareCall, MGoto, MPhi etc. Note that Movable does not imply "not effectful". For instance, MAdd is always Movable, but if one operand is an object it may also be effectful.

- The alias set for an instruction defaults to having all side-effects. This seems safer, but most instructions have no side effects so they have to override this. The alternative is to default to "no side effects" so that only the instructions with side effects have to override the default, let me know if you think that's better.

- Fixed a small LSRA correctness bug. May also help performance in some cases.
Comment 7 User image Jan de Mooij [:jandem] 2011-12-09 12:43:43 PST
Created attachment 580505 [details] [diff] [review]

Removed a bogus assert I added (jit-tests passed, but triggered by some perf tests).
Comment 8 User image Jan de Mooij [:jandem] 2011-12-12 01:37:49 PST
David, please ignore the changes to LinearScan.cpp, bug 709731 should fix this too.
Comment 9 User image David Anderson [:dvander] 2011-12-12 17:47:08 PST
Comment on attachment 580505 [details] [diff] [review]

Review of attachment 580505 [details] [diff] [review]:

Nice work! This was really easy to read and understand.

::: js/src/ion/AliasAnalysis.cpp
@@ +106,5 @@
> +    Vector<MDefinition *, 16, SystemAllocPolicy> stores;
> +
> +    // Initialize to the first instruction.
> +    MDefinition *firstIns = *graph_.begin()->begin();
> +    for (unsigned i=0; i < sizeof(AliasSet) * 8; i++) {

Could this expression be named somewhere, like NUM_ALIAS_SETS?

@@ +143,5 @@
> +                MDefinition *lastStore = NULL;
> +
> +                for (AliasSetIterator iter(set); iter; iter++) {
> +                    MDefinition *store = stores[*iter];
> +                    if (lastStore == NULL || lastStore->id() < store->id())

nit: if (!lastStore || ...

@@ +172,5 @@
> +                parentLoop->addStore(loop_->loopStores());
> +
> +            const InstructionVector &invariant = loop_->invariantLoads();
> +
> +            for (unsigned i=0; i<invariant.length(); i++) {

Nit: space this a little more, i = 0; i < invariant.length()

::: js/src/ion/AliasAnalysis.h
@@ +52,5 @@
> +typedef Vector<MDefinition *, 4, IonAllocPolicy> InstructionVector;
> +
> +class LoopAliasInfo : public TempObject {
> +  private:
> +    LoopAliasInfo *parent_;

Nit: s/parent/outer/, here and when referenced elsewhere.

::: js/src/ion/LICM.h
@@ +114,5 @@
>      bool insertInWorklist(MInstruction *ins);
>      MInstruction* popFromWorklist();
>      inline bool isHoistable(const MDefinition *ins) const {
> +        return ins->isMovable() && !ins->isEffectful() && !ins->isNeverHoisted();

Is "NeverHoisted" still useful now that we have Movable?
Comment 10 User image Jan de Mooij [:jandem] 2011-12-19 02:31:45 PST
Pushed with review comments addressed:

Fixes check-bitops-bits-in-byte and check-bitops-3bit-bits-in-byte.

The testcase for this bug fails on 32-bit (LSRA bug, test passes with greedy), the patches for bug 709731 will fix this.

Note You need to log in before you can comment on or make changes to this bug.