Avoid critical edge for loop-exits.

Avoid critical edge for loop-exits.

BUG= http://dartbug.com/19550
R=lrn@google.com

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

[Lasse Reichstein Nielsen, 2014-06-24 09:35:26]

lgtm

[floitsch, 2014-06-24 09:49:17]

Committed patchset #2 manually as r37649 (presubmit successful).

[ngeoffray, 2014-06-24 12:39:14]

Critical edges bite :-)

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/ssa/builder.dart (right):

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:2576: // Avoid a
critical edge from the condition to the loop-exit body.
Unconditionally? Isn't it when there can be multiple break/return blocks? Can we
detect that beforehand?

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:2795: // Avoid a
critical edge from the condition to the loop-exit body.
ditto

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/codegen.dart:762:
assert(condition.end.successors.last.first.next == null);
Should that be in validator.dart instead?

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
File tests/language/critical_edge2_test.dart (right):

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge2_test.dart:6: // A compiler must not construct a
critical edge on this program.
Maybe add a comment of the reason a critical edge was originally created. Is it
the break + return, or can it be break + break?

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge2_test.dart:35: Expect.equals("good",
parse("dart:_foreign_helper"));
Not very unit for a unit test :-) Seems like the loop is simple enough to
trigger an error.

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
File tests/language/critical_edge_test.dart (right):

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge_test.dart:20: while (true) {
Seems like the "true" is the only difference. Is it to provoke a different path
in builder.dart? I would add a comment.

[floitsch, 2014-06-24 14:44:38]

Comments addressed in https://codereview.chromium.org/350903002/

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/ssa/builder.dart (right):

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:2576: // Avoid a
critical edge from the condition to the loop-exit body.
On 2014/06/24 12:39:13, ngeoffray wrote:
> Unconditionally? Isn't it when there can be multiple break/return blocks? Can
we
> detect that beforehand?

Yes. We could try to avoid them (and I started this way), but then we would need
to special case in the codegen too.
I don't expect an empty basic-block to have a huge impact.

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/builder.dart:2795: // Avoid a
critical edge from the condition to the loop-exit body.
On 2014/06/24 12:39:13, ngeoffray wrote:
> ditto

ditto.

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
File sdk/lib/_internal/compiler/implementation/ssa/codegen.dart (right):

https://codereview.chromium.org/331343004/diff/20001/sdk/lib/_internal/compil...
sdk/lib/_internal/compiler/implementation/ssa/codegen.dart:762:
assert(condition.end.successors.last.first.next == null);
On 2014/06/24 12:39:14, ngeoffray wrote:
> Should that be in validator.dart instead?

Done.

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
File tests/language/critical_edge2_test.dart (right):

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge2_test.dart:6: // A compiler must not construct a
critical edge on this program.
On 2014/06/24 12:39:14, ngeoffray wrote:
> Maybe add a comment of the reason a critical edge was originally created. Is
it
> the break + return, or can it be break + break?

Added comment.

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge2_test.dart:35: Expect.equals("good",
parse("dart:_foreign_helper"));
On 2014/06/24 12:39:14, ngeoffray wrote:
> Not very unit for a unit test :-) Seems like the loop is simple enough to
> trigger an error.

I was not able to reduce the number of instructions in the "parse" functions.
This is pretty much a minimal example.

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
File tests/language/critical_edge_test.dart (right):

https://codereview.chromium.org/331343004/diff/20001/tests/language/critical_...
tests/language/critical_edge_test.dart:20: while (true) {
On 2014/06/24 12:39:14, ngeoffray wrote:
> Seems like the "true" is the only difference. Is it to provoke a different
path
> in builder.dart? I would add a comment.

It also uses more variables after the loop. This leads to different temporaries
being used. The behavior of the two tests is therefore different.
The first test crashes (array-index == -1), whereas this test returns "bad".