Fix bad generate-at-use-site.

sdk/lib/_internal/compiler/implementation/ssa/codegen_helpers.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of ssa;
 
 /**
  * Replaces some instructions with specialized versions to make codegen easier.
  * Caches codegen information on nodes.
  */
@@ skipping 267 matching lines @@
     for (HInstruction instruction = block.last.previous;
          instruction != null;
          instruction = instruction.previous) {
       if (generateAtUseSite.contains(instruction)) {
         continue;
       }
       if (instruction.isCodeMotionInvariant()) {
         markAsGenerateAtUseSite(instruction);
         continue;
       }
-      if (instruction.isJsStatement()) {
-        expectedInputs.clear();
-      }
       if (instruction.isPure()) {
         if (pureInputs.contains(instruction)) {
           tryGenerateAtUseSite(instruction);
         } else {
           // If the input is not in the [pureInputs] set, it has not
-          // been visited.
+          // been visited or should not be generated at use-site. The most
+          // likely reason for the latter, is that the instruction is used
+          // in more than one location.
+          // We must either clear the expectedInputs, or move the pure
+          // instruction's inputs in front of the existing ones.
+          // Example:
+          //   t1 = foo();  // side-effect.
+          //   t2 = bar();  // side-effect.
+          //   t3 = pure(t2);    // used more than once.
+          //   f(t1, t3);   // expected inputs of 'f': t1.
+          //   use(t3);
+          //
+          // If we don't clear the expected inputs we end up in a situation
+          // where pure pushes "t2" on top of "t1" leading to:
+          //
+          //  t3 = pure(bar());

[kasperl, 2014/03/17 10:38:24]

Indent code with two spaces. Maybe remove leading newline for consistency?

[floitsch, 2014/03/17 11:43:01]

Done.

+          //  f(foo(), t3);
+          //  use(t3);
+          //
+          // If we clear the expected-inputs list we have the correct
+          // output:
+          //   t1 = foo();
+          //   t3 = pure(bar());
+          //   f(t1, t3);
+          //   use(t3);
+          //
+          // Clearing is, however, not optimal.
+          // Example:
+          //   t1 = foo();  // t1 is now used by `pure`.
+          //   t2 = bar();  // t2 is now used by `f`.
+          //   t3 = pure(t1);
+          //   f(t2, t3);
+          //   use(t3);
+          //
+          // If we clear the expected-inputs we can't generate-at-use any of
+          // the instructions.
+          //
+          // The optimal solution is to move the inputs of 'pure' in
+          // front of the expectedInputs list. This makes sense, since we

[kasperl, 2014/03/17 10:38:24]

Front is slightly misleading to me. See next comment.

[floitsch, 2014/03/17 11:43:01]

see next comment.

+          // push expected-inputs from left-to right, and the `pure` function
+          // invocation is "more left" (i.e. before) the first argument of `f`.
+          // With that approach we end up with:
+          //   t3 = pure(foo();
+          //   f(bar(), t3);
+          //   use(t3);
+          //
+          int oldLength = expectedInputs.length;
           instruction.accept(this);
+          if (oldLength != 0 && oldLength != expectedInputs.length) {
+            // Move the pure instruction's inputs to the front.

[kasperl, 2014/03/17 10:38:24]

Front is a little bit of a weird word here. It's the back of the list, right?
Maybe use a word like top instead?

Maybe the ideal would be to change expectedInputs to be a class that wraps a
list that has stack behavior and uses stack terminology rather than list
terminology (push/pop/move to top...)? That probably fits in another CL.

[floitsch, 2014/03/17 11:43:01]

It's actually the front. Since we fill the expressions from the back, it thus
becomes at the bottom of the queue.
Considering adding a data-structure in another CL.

+            List<HInstruction> newInputs = expectedInputs.sublist(oldLength);
+            int newCount = newInputs.length;
+            expectedInputs.setRange(
+                newCount, newCount + oldLength, expectedInputs);
+            expectedInputs.setRange(0, newCount, newInputs);
+          }
         }
       } else {
         if (findInInputsAndPopNonMatching(instruction)) {
           // The current instruction is the next non-trivial
           // expected input.
           tryGenerateAtUseSite(instruction);
         } else {
           assert(expectedInputs.isEmpty);
         }
         instruction.accept(this);
@@ skipping 176 matching lines @@
     }
 
     // If [thenInput] is defined in the first predecessor, then it is only used
     // by [phi] and can be generated at use site.
     if (identical(thenInput.block, end.predecessors[0])) {
       assert(thenInput.usedBy.length == 1);
       markAsGenerateAtUseSite(thenInput);
     }
   }
 }