IonMonkey: Add instruction and basic block renumbering phase

RESOLVED FIXED

Status

()

RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: adrake, Assigned: adrake)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

8 years ago
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.
(Assignee)

Comment 1

8 years ago
Created attachment 535004 [details] [diff] [review]
Patch v0

I split out the renumbering phase from my in-progress patch for bug 657816.
Attachment #535004 - Flags: review?(dvander)
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 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?
Attachment #535004 - Flags: review?(dvander)
(Assignee)

Comment 4

8 years ago
> 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.
(Assignee)

Comment 5

8 years ago
Created attachment 535199 [details] [diff] [review]
Patch v1
Attachment #535004 - Attachment is obsolete: true
Attachment #535199 - Flags: review?(dvander)
(Assignee)

Comment 6

8 years ago
Infinite loop filed as bug 659782.
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.
(Assignee)

Comment 8

8 years ago
Created attachment 535746 [details] [diff] [review]
Patch v1

Now it uses a mark field in MBasicBlock for traversal.
Attachment #535199 - Attachment is obsolete: true
Attachment #535199 - Flags: review?(dvander)
Attachment #535746 - Flags: review?(dvander)
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 :)
Attachment #535746 - Flags: review?(dvander) → review+
(Assignee)

Comment 10

8 years ago
http://hg.mozilla.org/users/danderson_mozilla.com/ionmonkey/rev/5c1e43a63c64
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.