Closed Bug 703376 Opened 13 years ago Closed 13 years ago

IonMonkey: Add alias sets


(Core :: JavaScript Engine, defect)

Not set





(Reporter: jandem, Assigned: jandem)


(Blocks 1 open bug)



(1 file, 4 obsolete files)

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?
Summary: IonMonkey: Add effect analysis based on TI → IonMonkey: Add alias sets
Attached patch Patch (obsolete) — Splinter 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().
Assignee: general → jdemooij
Attached patch Patch (obsolete) — Splinter Review
Some small changes + updated license header, evilpie pointed out it was really old.
Attachment #576784 - Attachment is obsolete: true
Attached patch Patch (obsolete) — Splinter 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.
Attachment #576803 - Attachment is obsolete: true
Attachment #577936 - Flags: review?(dvander)
Btw, naming suggestions etc. are welcome of course.
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.
Attachment #577936 - Flags: review?(dvander)
Attached patch Patch (obsolete) — Splinter 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.
Attachment #577936 - Attachment is obsolete: true
Attachment #580438 - Flags: review?(dvander)
Attachment #580438 - Flags: review?(dvander)
Attached patch PatchSplinter Review
Removed a bogus assert I added (jit-tests passed, but triggered by some perf tests).
Attachment #580438 - Attachment is obsolete: true
Attachment #580505 - Flags: review?(dvander)
David, please ignore the changes to LinearScan.cpp, bug 709731 should fix this too.
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?
Attachment #580505 - Flags: review?(dvander) → review+
Depends on: 710447
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.
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.