Generate code for some switch statements.

Generate code for some switch statements.

Committed: https://code.google.com/p/dart/source/detail?r=5013

[ahe, 2012-03-05 22:58:34]

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:1960: if (isAborted()) {
Not sure about this.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
dart/frog/leg/ssa/optimize.dart:329: if (!livePhis.contains(current) &&
current.usedBy.isEmpty()) {
Not sure about this.

[Lasse Reichstein Nielsen, 2012-03-06 08:57:13]

LGTM

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:1960: if (isAborted()) {
Seems like a reasonable warning. Maybe break the loop, so you only get one
warning.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:2315: }
Am I right that this only handles one case expression per case statement? (In
which case, ignore my request for harder tests :).

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:2319: localsHandler.startLoop(node);
Is this loop just to give a target for unnamed breaks?

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
dart/frog/leg/ssa/optimize.dart:329: if (!livePhis.contains(current) &&
current.usedBy.isEmpty()) {
If it isn't empty, we will hit an assert in removePhi.
If that is actually happening for you, we should make the removal smarter.
If we don't have cycles, a simple recursive removal of the usedBy elements would
work, but if we do have cycles we need to break the cycle somehow (e.g.,
removing the phi from the inputs of its usedBy elements - we know that those
must be dead phis too).

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
File dart/frog/tests/leg_only/src/SwitchTest.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
dart/frog/tests/leg_only/src/SwitchTest.dart:19: break;
That break should be dead code.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
dart/frog/tests/leg_only/src/SwitchTest.dart:23: 
Try pushing it a little :)
E.g., something like:
 switch(val) {
  foo: case 1: case 2: case3: {};
  case 4: case 5: case 6: return val == 4 ? val : 10;
  bar: case 6: case 7: default: break;
 }

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/tests/language/...
File dart/tests/language/language-leg.status (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/tests/language/...
dart/tests/language/language-leg.status:284: Switch7NegativeTest: Fail, OK #
Negative language test.
Why is it OK to fail? Is the test wrong?

[ahe, 2012-03-06 09:16:50]

Hi Lasse,

Thank you for your comments.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:1960: if (isAborted()) {
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> Seems like a reasonable warning. Maybe break the loop, so you only get one
> warning.

I think an IDE wants multiple warnings. Otherwise it wont be able to color all
of the dead code.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:2315: }
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> Am I right that this only handles one case expression per case statement? (In
> which case, ignore my request for harder tests :).

Yes. I called this fall-through and report it as unimplemented on line 2295.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/bu...
dart/frog/leg/ssa/builder.dart:2319: localsHandler.startLoop(node);
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> Is this loop just to give a target for unnamed breaks?

It serves that purpose right now. However, it'll soon be a critical part of the
implementation. Consider:

switch (e) {
  case c1: continue L;
  L: case c2: break;
}

I plan to compile this to:

var tmp1 = e;
var tmp2 = 0; // default.
if (c1 == e) {
  tmp2 = 1;
} else if (c2 == e) {
  tmp2 = 2;
}

while (tmp2 !== null) {
  if (tmp2 === 1) {
    tmp2 = 2;
  } else if (tmp2 === 2) {
    break;
  } else {
    break;
  }
}

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/leg/ssa/op...
dart/frog/leg/ssa/optimize.dart:329: if (!livePhis.contains(current) &&
current.usedBy.isEmpty()) {
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> If it isn't empty, we will hit an assert in removePhi.
> If that is actually happening for you, we should make the removal smarter.
> If we don't have cycles, a simple recursive removal of the usedBy elements
would
> work, but if we do have cycles we need to break the cycle somehow (e.g.,
> removing the phi from the inputs of its usedBy elements - we know that those
> must be dead phis too).

I don't understand what you're talking about. I don't have good understanding of
this part of the compiler. I can add a TODO if you tell me exactly what to write
in it.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
File dart/frog/tests/leg_only/src/SwitchTest.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
dart/frog/tests/leg_only/src/SwitchTest.dart:19: break;
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> That break should be dead code.

I know. I noticed this would cause a crash, so I "fixed" the crash and kept the
dead code. I'll add a comment stating so.

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/frog/tests/leg_...
dart/frog/tests/leg_only/src/SwitchTest.dart:23: 
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> Try pushing it a little :)
> E.g., something like:
>  switch(val) {
>   foo: case 1: case 2: case3: {};
>   case 4: case 5: case 6: return val == 4 ? val : 10;
>   bar: case 6: case 7: default: break;
>  }

Then my code would be untested. I'm not attempting to deal with that yet :-)

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/tests/language/...
File dart/tests/language/language-leg.status (right):

https://chromiumcodereview.appspot.com/9599026/diff/5002/dart/tests/language/...
dart/tests/language/language-leg.status:284: Switch7NegativeTest: Fail, OK #
Negative language test.
On 2012/03/06 08:57:14, Lasse Reichstein Nielsen wrote:
> Why is it OK to fail? Is the test wrong?

The test is fine. It is OK to fail a negative language test this quarter as we
rely on dartc for catching these.

[ngeoffray, 2012-03-06 11:49:48]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2291: Link cases = node.cases.nodes;
Link -> Link<Node> ?

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2302: if (cases.head is DefaultCase) {
is DefaultCase -> asDefaultCase() != null

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2311: Element equalsHelper =
compiler.findHelper(const SourceString('eq'));
maybe make that a method in the Interceptors class to make it consistent with
other uses of findHelper?

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
Err, not really :)

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
dart/frog/leg/ssa/optimize.dart:330: // TODO(ahe): Not sure the following is
correct.
Why did you need to add this? Was it on one test case or all?

[ahe, 2012-03-06 12:24:35]

Hi Nicolas,

Thank you for your comments. I'll follow up with another CL.

Cheers,
Peter

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2291: Link cases = node.cases.nodes;
On 2012/03/06 11:49:48, ngeoffray wrote:
> Link -> Link<Node> ?

Done.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2302: if (cases.head is DefaultCase) {
On 2012/03/06 11:49:48, ngeoffray wrote:
> is DefaultCase -> asDefaultCase() != null

Done.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2311: Element equalsHelper =
compiler.findHelper(const SourceString('eq'));
On 2012/03/06 11:49:48, ngeoffray wrote:
> maybe make that a method in the Interceptors class to make it consistent with
> other uses of findHelper?

Done.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
On 2012/03/06 11:49:48, ngeoffray wrote:
> Err, not really :)

Yes. Really. That is the problem.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
dart/frog/leg/ssa/optimize.dart:330: // TODO(ahe): Not sure the following is
correct.
On 2012/03/06 11:49:48, ngeoffray wrote:
> Why did you need to add this? Was it on one test case or all?

Just one test case, I think.

[ngeoffray, 2012-03-06 12:32:55]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
On 2012/03/06 12:24:35, ahe wrote:
> On 2012/03/06 11:49:48, ngeoffray wrote:
> > Err, not really :)
> 
> Yes. Really. That is the problem.

In 'for loop' I read 'for' as in 'for (;;) {}' :) I think that was the intent of
this message initially but may have been copied without being updated.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
dart/frog/leg/ssa/optimize.dart:330: // TODO(ahe): Not sure the following is
correct.
On 2012/03/06 12:24:35, ahe wrote:
> On 2012/03/06 11:49:48, ngeoffray wrote:
> > Why did you need to add this? Was it on one test case or all?
> 
> Just one test case, I think.

Worth fixing? I'd rather keep the bug and try to fix it the right way.

[Lasse Reichstein Nielsen, 2012-03-06 12:53:50]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
I don't read it as that, but it's still a confusing message for a program with
no loops in it. The loop here is purely synthetic and wasn't in the original
source.
We should probably use a switch statement instead when possible. It also avoids
binding any label-less continues.

[ahe, 2012-03-06 13:10:51]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
On 2012/03/06 12:53:50, Lasse Reichstein Nielsen wrote:
> I don't read it as that, but it's still a confusing message for a program with
> no loops in it. The loop here is purely synthetic and wasn't in the original
> source.

I understand that the loop is purely synthetic and the error message is
confusing. However, this problem is the same as in all our loops: we cannot deal
with aborting bodies.

I have no clue how to fix that, but I would welcome suggestions. I think this
needs to be implemented ASAP.

> We should probably use a switch statement instead when possible. It also
avoids
> binding any label-less continues.

Please read my previous comment. I need the loop.

Presumably, the label-less continues will have been bound by the resolver.
Otherwise, it is a bug in the resolver.

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
dart/frog/leg/ssa/optimize.dart:330: // TODO(ahe): Not sure the following is
correct.
On 2012/03/06 12:32:55, ngeoffray wrote:
> On 2012/03/06 12:24:35, ahe wrote:
> > On 2012/03/06 11:49:48, ngeoffray wrote:
> > > Why did you need to add this? Was it on one test case or all?
> > 
> > Just one test case, I think.
> 
> Worth fixing? I'd rather keep the bug and try to fix it the right way.

I wanted to get rid of the assertion error. This is one of the problematic
assertions I ranted about a few days ago. However, I could not figure out how to
turn it into an internal error.

I think a compiler crash is extremely bad, and I will do whatever it takes to
get rid of them.

As far as I understand, this change is semantically correct, but may generate
suboptimal code.

[Lasse Reichstein Nielsen, 2012-03-06 13:23:36]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
File dart/frog/leg/ssa/builder.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/b...
dart/frog/leg/ssa/builder.dart:2327: compiler.unimplemented("SsaBuilder for loop
with aborting body",
I think that, in the long run, we should have different strategies for different
levels of complexity of switch statements. If there is no continue statements or
only continue as fall-through to the next case, we don't need a loop. If we have
more general continues, we will need a loop (I prefer an implementation with two
switches, the second using only ints as albels being inside a loop).

I would prefer to wait wtih introducing a loop until we're ready to handle the
continues anyway (pure premature-optimization avoidance).


We also definitely need to handle aborting bodies of loops (and try-blocks and
labeled statement blocks and ....). The big question is how much it will
complicate everything else (dominator traversal can get funny when the only exit
from a loop is a break - but switching to subgraph traversal of bodies might
help).

[ngeoffray, 2012-03-07 08:55:31]

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
File dart/frog/leg/ssa/optimize.dart (right):

https://chromiumcodereview.appspot.com/9599026/diff/12001/dart/frog/leg/ssa/o...
dart/frog/leg/ssa/optimize.dart:330: // TODO(ahe): Not sure the following is
correct.
On 2012/03/06 13:10:51, ahe wrote:
> On 2012/03/06 12:32:55, ngeoffray wrote:
> > On 2012/03/06 12:24:35, ahe wrote:
> > > On 2012/03/06 11:49:48, ngeoffray wrote:
> > > > Why did you need to add this? Was it on one test case or all?
> > > 
> > > Just one test case, I think.
> > 
> > Worth fixing? I'd rather keep the bug and try to fix it the right way.
> 
> I wanted to get rid of the assertion error. This is one of the problematic
> assertions I ranted about a few days ago. However, I could not figure out how
to
> turn it into an internal error.
> 
> I think a compiler crash is extremely bad, and I will do whatever it takes to
> get rid of them.
> 
> As far as I understand, this change is semantically correct, but may generate
> suboptimal code.

But you're fixing a symptom, not the bug. I think we both agree that we
definitely prefer *failing* (not crashing) tests compared to adding symptom
fixes. To avoid the crash, why don't you do:

if (!current.usedBy.isEmpty()) compiler.internalError("blah", instruction: phi);

If this does not work, you could also file a bug and reference it here.