Note: There are a few cases of duplicates in user autocompletion which are being worked on.

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

RESOLVED FIXED

Status

()

Core
JavaScript Engine
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: h4writer, Assigned: h4writer)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(3 attachments, 1 obsolete attachment)

(Assignee)

Description

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

Comment 1

6 years ago
typo: case 2 => case 0
(Assignee)

Comment 2

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

Comment 4

6 years ago
Created attachment 560331 [details] [diff] [review]
Sort successors of MTableSwitch
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+
(Assignee)

Comment 6

6 years ago
Created attachment 560527 [details] [diff] [review]
Sort successors of MTableSwitch

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+
(Assignee)

Comment 7

6 years ago
Created attachment 566603 [details] [diff] [review]
2. Small follow up fix

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)
(Assignee)

Comment 8

6 years ago
Created attachment 566604 [details] [diff] [review]
3. Remove some obsolete code

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)
(Assignee)

Updated

6 years ago
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
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.