659566 - IonMonkey: Add instruction and basic block renumbering phase

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andrew Drake [:adrake]]

Blocks and instructions may be inserted or reordered by intermediate instructions. It is useful at least for register allocation to have a global ordering attached to instructions, but is complex to maintain it while operating on the structure. We can do a quick sweep to renumber when it's needed.

Comment 1

[Andrew Drake [:adrake]]

Attachment: Patch v0

I split out the renumbering phase from my in-progress patch for bug 657816.

Comment 2

[David Mandelin [:dmandelin]]

Looks nice. It took me a minute to figure out your DFS, but then I remembered that if you don't do it recursively (which is probably the correct decision here), it's more complicated.

One thing I found pretty useful in my prototype was to "assign" an id to the "instruction" after the last in a basic block. That way, if you have something like this:

  block B1
    succs = B2, B3
    id of first isn = 0
    id of last (real) isn = 10

  block B2
    id of first isn = 14
    id of last isn = 20

  block B3
    id of first isn = 24
    id of last isn = 30

there is a unique instruction id associated with every program point. E.g., the id of the point just at the end of B1 is 11, and the id of the point just before B2 is 13. Without the space, they both get 11. It seemed to make LSRA much easier at the borders to have the unique ids.

Comment 3

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

Comment on attachment 535004 [details] [diff] [review]
Patch v0

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

::: js/src/ion/IonAnalysis.cpp
@@ +200,5 @@
> +bool
> +ion::RenumberInstructions(MIRGraph &graph)
> +{
> +    Vector<MBasicBlock *, 0, IonAllocPolicy> pend;
> +    Vector<unsigned int, 0, IonAllocPolicy> succ;

Could you expand these names?

@@ +215,5 @@
> +            if (!pend.append(current) || !succ.append(nextSucc))
> +                return false;
> +
> +            current = current->lastIns()->getSuccessor(nextSucc);
> +            nextSucc = 0;

This can't break cycles, so if you have a graph like:

A -> B, D
B -> C
C -> A

nextSucc will never increment and it'll cycle through A, B, C until the work stack OOMs.

::: js/src/ion/MIR.h
@@ -553,5 @@
>    public:
> -    MControlInstruction()
> -      : successors()
> -    { }
> -

Without this successors[1] might not be initialized for MGoto.

::: js/src/ion/MIRGraph.h
@@ +77,3 @@
>          idGen_ += 2;
> +        ins->setId(idGen_);
> +        return instructions_.putNew(idGen_, ins);

Is it needed to have the hash table around throughout building the IR and all the analysis phases?

Comment 4

[Andrew Drake [:adrake]]

> Could you expand these names?

Done.

> This can't break cycles, so if you have a graph like:

Whoops! That's pend(ing)'s job. Added cycle breaking, but I can't test it due to an infinite loop in the IR generator. There is room for improvement in runtime if we're willing to add a mark field to the blocks.

> Without this successors[1] might not be initialized for MGoto.

Replaced.

> Is it needed to have the hash table around throughout building the IR and
> all the analysis phases?

Not necessarily -- it could be optionally built. I assumed we were going to have a very small number of renumbers (hopefully 1) so generating it while we're here seemed advantageous.

Comment 5

[Andrew Drake [:adrake]]

Attachment: Patch v1

Comment 6

[Andrew Drake [:adrake]]

Infinite loop filed as bug 659782.

Comment 7

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

Yeah, a mark field would be good, might simplify the code too. There's already one in MInstruction, seems like a good thing to just have lying around anyway.

Comment 8

[Andrew Drake [:adrake]]

Attachment: Patch v1

Now it uses a mark field in MBasicBlock for traversal.

Comment 9

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

Comment on attachment 535746 [details] [diff] [review]
Patch v1

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

::: js/src/ion/MIRGraph.h
@@ +77,4 @@
>          idGen_ += 2;
> +        ins->setId(idGen_);
> +        return instructions_.putNew(idGen_, ins);
> +    }

I think it's best to leave this out for now, or as a separate pass as part of LSRA. It's fallible and its callers are (now) infallible, and we'll want the RPO before all the phases that mutate the instruction stream.

@@ +250,5 @@
> +        return mark_;
> +    }
> +    void setMark(bool marked) {
> +        mark_ = marked;
> +    }

Maybe break setMark() into mark() and unmark() or something like MInstruction? Boolean parameters confuse me :)

Comment 10

[Andrew Drake [:adrake]]

http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/5c1e43a63c64