Closed Bug 682021 Opened 13 years ago Closed 13 years ago

IonMonkey: the successors in MTableSwitch need to get sorted by pc

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: h4writer, Assigned: h4writer)

References

Details

Attachments

(3 files, 1 obsolete file)

When doing bug #681741 I noticed a little fault in the generation of the MTableSwitch. The successors actually should get sorted by the pc.
The result is that sometimes we have duplicate code in blocks.
(When cases aren't in order and the cases don't have break/return statement)

e.g.
switch (x) {
  case 1: i=1;
  case 0: i=0;
}

will contain the follow blocks:

block (case 1):
  i=1;
  i=0;

block (case 2):
  i=0;


When we actually want block (case 1) to be:
  i=1
  goto block (case 2)
typo: case 2 => case 0
@dvander: So I was thinking what the best way to implement this is and I had some questions about what the best way would be.

So I have to sort the MBasicBlocks that are added to the MTableSwitch as successors. So I have to implement a sorting algorithm. Are there any rules on how to do this? Like is there already a small library I should use. Or should I just implement the algorithm myself. Should I generalize or can I just put it into IonBuilder? I was thinking about a "adaptive sort algorithm", because I think most of the time the order will already be right ...

What do you think?
If it's not too hard you could probably get away with just using qsort(). There's also js_MergeSort. If either of those work I'd do that. The number of items we're working with is small and I think always just calling sort should be okay.
Attached patch Sort successors of MTableSwitch (obsolete) — Splinter Review
Assignee: general → hv1989
Attachment #560331 - Flags: review?(dvander)
Comment on attachment 560331 [details] [diff] [review]
Sort successors of MTableSwitch

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

r=me with:

::: js/src/ion/IonBuilder.cpp
@@ +1314,5 @@
> +IonBuilder::cmpSuccessors(const void *a, const void *b)
> +{
> +    const MBasicBlock *a0 = * (MBasicBlock * const *)a;
> +    const MBasicBlock *b0 = * (MBasicBlock * const *)b;
> +    return a0->pc() - b0->pc();

This will lose the top bits - safer to expand out to actual comparisons.

::: js/src/ion/IonBuilder.h
@@ +168,5 @@
>          static CFGState If(jsbytecode *join, MBasicBlock *ifFalse);
>          static CFGState IfElse(jsbytecode *trueEnd, jsbytecode *falseEnd, MBasicBlock *ifFalse);
>      };
>  
> +static int cmpSuccessors(const void *a, const void *b);

nit: Indent this and capitalize the first 'C'
Attachment #560331 - Flags: review?(dvander) → review+
Comments addressed.
I don't have commit access anymore (my internship is over, so everything related to my mozilla account/ssh key is revoked.) so somebody else will have to land it.
Attachment #560331 - Attachment is obsolete: true
Attachment #560527 - Flags: review+
When I was reading the code again, I saw I made a little mistake in my code. This should fix it. (I assumed the positions of the successors stayed the same. But I altered that the previous commit by sorting it. So now I just save the MBasicBlock pointer instead of the position in the successors array)

(This doesn't fix #692208, but it alters the error message to: Assertion failure: defaultCase_ == NULL, at /home/h4writer/Build/ionmonkey/js/src/ion/MIR.h:651)
Attachment #566603 - Flags: review?(dvander)
Because the successors get sorted now, some code is obsolete now. I forgot to delete it. (That was actually the reason why it should get sorted).

This also fixes bug #692208
Attachment #566604 - Flags: review?(dvander)
Blocks: 692208
Attachment #566603 - Flags: review?(dvander) → review+
Attachment #566604 - Flags: review?(dvander) → review+
Thanks!

https://hg.mozilla.org/projects/ionmonkey/rev/b2cc6f0cc580
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.