Make sure that we don't assign phis before its uses.

Make sure that we don't assign phis before its uses.

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

[ngeoffray, 2012-05-03 07:29:14]

Initial comments on the tests.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange2_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange2_test.dart:5: // This program tripped dart2js.
To highlight the problem, this test can be turn into:

  main() {
    var a = 1;
    var b = 2;
    for (int i = 0; i < 2; i++) {
      if (i == 1) {
        Expect.equals(1, b);
        Expect.equals(32, a);
      }
  
      int temp = a << 5;
      b = a;
      a = temp;
    }
  }

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange3_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange3_test.dart:5: // This program tripped dart2js.
This program works for me?

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange3_test.dart:9: if(i > 0) { // e is not evaluated
before the first iteration
e?

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange4_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange4_test.dart:5: // This program tripped dart2js.
It works for me?

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange_test.dart:1: // Copyright (c) 2012, the Dart
project authors.  Please see the AUTHORS file
It looks like this test is highlighting the exact same bug as as
loop_exchange2_test.dart (or the simplified version of it). Is there another bug
I missed?

[Lasse Reichstein Nielsen, 2012-05-03 08:22:02]

What ngeoffray said!
LGTM.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:923: 
Please add dart-doc describing what the method does.
This *generates* assignments *for* all phis of successor blocks, right?

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:925: Map<HInstruction, String>
phiTemporaries = null;
Can you give a better name to this map? I gives no indication what role the
stored phi/string pairs have. I'm guessing it's temporary *names* for phis, so,
e.g., temporaryNameForPhis?

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:927: void assignPhi(HPhi
canonicalPhi, HInstruction value) {
assignPhi -> generateAssignment.
You don't assign to the phi, you generate an assignment that stores the result
of the phi in a (temporary) variable.
(Where "temporary" means one that isn't in the original source?)

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:957: void
collectInputPhis(HInstruction input, Set<HPhi> inputPhis,
Dart-doc description of what the function does, please.
Would be easier if the condition wasn't parameterized entirely, but only by
targetPhi.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:973: Map<HPhi, HInstruction>
phiAssignments = new Map<HPhi, HInstruction>();
Please add empty line after declaration.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:982: assert(canonicalPhi === phi ||
!isLogicalOperation);
Reading this now, I actually prefer:
  assert(!isLogicalOperation || canonicalPhi === phi);

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:996: 
Remove extra empty line.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1005: });
Inline the shouldBeAdded function in collectInputPhis. It's always the same. Or
if you really want a function, make it a function declaration and call it from
collectInputPhis.

And/or move the declaration of collectInputPhis here, after the declaration of
inputPhis, so you don't need to pass the set as an argument.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1027: for (int i = 0; i < length;
i++) {
You don't use "i", so perhaps just
  for (HPhi phi in phis) {
?

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1042: }
For a later version, maybe we can try sorting the phis in an order where
assignments to phis are after uses, and only introduce temporaries if there is
one or more cycles.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange2_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange2_test.dart:5: // This program tripped dart2js.
Minimal examples are cool!

[floitsch, 2012-05-03 09:11:29]

PTAL.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:923: 
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Please add dart-doc describing what the method does.
> This *generates* assignments *for* all phis of successor blocks, right?

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:925: Map<HInstruction, String>
phiTemporaries = null;
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Can you give a better name to this map? I gives no indication what role the
> stored phi/string pairs have. I'm guessing it's temporary *names* for phis,
so,
> e.g., temporaryNameForPhis?

renamed to temporaryNamesOfPhis. (dart-editor for the win ;)

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:927: void assignPhi(HPhi
canonicalPhi, HInstruction value) {
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> assignPhi -> generateAssignment.
> You don't assign to the phi, you generate an assignment that stores the result
> of the phi in a (temporary) variable.
> (Where "temporary" means one that isn't in the original source?)

Renamed and added doc.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:957: void
collectInputPhis(HInstruction input, Set<HPhi> inputPhis,
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Dart-doc description of what the function does, please.
> Would be easier if the condition wasn't parameterized entirely, but only by
> targetPhi.

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:973: Map<HPhi, HInstruction>
phiAssignments = new Map<HPhi, HInstruction>();
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Please add empty line after declaration.

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:982: assert(canonicalPhi === phi ||
!isLogicalOperation);
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Reading this now, I actually prefer:
>   assert(!isLogicalOperation || canonicalPhi === phi);

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:996: 
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Remove extra empty line.

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1005: });
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> Inline the shouldBeAdded function in collectInputPhis. It's always the same.
Or
> if you really want a function, make it a function declaration and call it from
> collectInputPhis.
> 
> And/or move the declaration of collectInputPhis here, after the declaration of
> inputPhis, so you don't need to pass the set as an argument.

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1027: for (int i = 0; i < length;
i++) {
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> You don't use "i", so perhaps just
>   for (HPhi phi in phis) {
> ?

Done.

https://chromiumcodereview.appspot.com/10342002/diff/3001/lib/compiler/implem...
lib/compiler/implementation/ssa/codegen.dart:1042: }
On 2012/05/03 08:22:02, Lasse Reichstein Nielsen wrote:
> For a later version, maybe we can try sorting the phis in an order where
> assignments to phis are after uses, and only introduce temporaries if there is
> one or more cycles.

That's what the TODO implies.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange2_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange2_test.dart:5: // This program tripped dart2js.
On 2012/05/03 07:29:14, ngeoffray wrote:
> To highlight the problem, this test can be turn into:
> 
>   main() {
>     var a = 1;
>     var b = 2;
>     for (int i = 0; i < 2; i++) {
>       if (i == 1) {
>         Expect.equals(1, b);
>         Expect.equals(32, a);
>       }
>   
>       int temp = a << 5;
>       b = a;
>       a = temp;
>     }
>   }

The other tests are more minimal. But I had different errors depending on the
programs (that's why there are so many different tests).
I can try to reduce the test, but since I'm not encountering the bug anymore I
wouldn't really know where to stop.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange3_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange3_test.dart:5: // This program tripped dart2js.
On 2012/05/03 07:29:14, ngeoffray wrote:
> This program works for me?

I failed this test when I had implemented a bad version of this CL. So yes: no
checked in version of dart2js ever failed this test. But a local one did. I can
remove the comment, though.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange3_test.dart:9: if(i > 0) { // e is not evaluated
before the first iteration
On 2012/05/03 07:29:14, ngeoffray wrote:
> e?

removed.

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange4_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange4_test.dart:5: // This program tripped dart2js.
On 2012/05/03 07:29:14, ngeoffray wrote:
> It works for me?

As before: a bad version of this CL triggered this (in a different way than
exchange3 test).

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
File tests/language/loop_exchange_test.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/3001/tests/language/loop...
tests/language/loop_exchange_test.dart:1: // Copyright (c) 2012, the Dart
project authors.  Please see the AUTHORS file
On 2012/05/03 07:29:14, ngeoffray wrote:
> It looks like this test is highlighting the exact same bug as as
> loop_exchange2_test.dart (or the simplified version of it). Is there another
bug
> I missed?

I had a version of this CL that passed this test, but not exchange2...

[Lasse Reichstein Nielsen, 2012-05-03 12:19:49]

LGTM

https://chromiumcodereview.appspot.com/10342002/diff/11002/lib/compiler/imple...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/11002/lib/compiler/imple...
lib/compiler/implementation/ssa/codegen.dart:934: * then the [canonicalPhi] is
assigned with the temporary.
Still a slightly odd "modal" function. Acceptable, but odd. Does it have to be
one function?

[floitsch, 2012-05-03 12:27:23]

https://chromiumcodereview.appspot.com/10342002/diff/11002/lib/compiler/imple...
File lib/compiler/implementation/ssa/codegen.dart (right):

https://chromiumcodereview.appspot.com/10342002/diff/11002/lib/compiler/imple...
lib/compiler/implementation/ssa/codegen.dart:934: * then the [canonicalPhi] is
assigned with the temporary.
On 2012/05/03 12:19:49, Lasse Reichstein Nielsen wrote:
> Still a slightly odd "modal" function. Acceptable, but odd. Does it have to be
> one function?

It could be split, but there is quite some boiler-plate code... (like is it an
expression, a logical operation, ...)
If you see a nice way to split it, tell me and I will change it in another CL.