Last Comment Bug 682021 - IonMonkey: the successors in MTableSwitch need to get sorted by pc
: IonMonkey: the successors in MTableSwitch need to get sorted by pc
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Hannes Verschore [:h4writer]
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on:
Blocks: 692208
  Show dependency treegraph
 
Reported: 2011-08-25 10:37 PDT by Hannes Verschore [:h4writer]
Modified: 2011-10-13 12:41 PDT (History)
1 user (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Sort successors of MTableSwitch (3.78 KB, patch)
2011-09-15 04:43 PDT, Hannes Verschore [:h4writer]
dvander: review+
Details | Diff | Splinter Review
Sort successors of MTableSwitch (3.84 KB, patch)
2011-09-16 01:14 PDT, Hannes Verschore [:h4writer]
hv1989: review+
Details | Diff | Splinter Review
2. Small follow up fix (1.80 KB, patch)
2011-10-12 12:13 PDT, Hannes Verschore [:h4writer]
dvander: review+
Details | Diff | Splinter Review
3. Remove some obsolete code (1.97 KB, patch)
2011-10-12 12:19 PDT, Hannes Verschore [:h4writer]
dvander: review+
Details | Diff | Splinter Review

Description Hannes Verschore [:h4writer] 2011-08-25 10:37:22 PDT
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)
Comment 1 Hannes Verschore [:h4writer] 2011-08-25 10:38:11 PDT
typo: case 2 => case 0
Comment 2 Hannes Verschore [:h4writer] 2011-09-14 14:38:28 PDT
@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?
Comment 3 David Anderson [:dvander] 2011-09-14 16:41:34 PDT
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.
Comment 4 Hannes Verschore [:h4writer] 2011-09-15 04:43:51 PDT
Created attachment 560331 [details] [diff] [review]
Sort successors of MTableSwitch
Comment 5 David Anderson [:dvander] 2011-09-15 15:47:55 PDT
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'
Comment 6 Hannes Verschore [:h4writer] 2011-09-16 01:14:29 PDT
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.
Comment 7 Hannes Verschore [:h4writer] 2011-10-12 12:13:53 PDT
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)
Comment 8 Hannes Verschore [:h4writer] 2011-10-12 12:19:04 PDT
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
Comment 9 David Anderson [:dvander] 2011-10-13 12:41:50 PDT
Thanks!

https://hg.mozilla.org/projects/ionmonkey/rev/b2cc6f0cc580

Note You need to log in before you can comment on or make changes to this bug.