Fix for issue 26243 - illegal motion of assignments in instruction merging

pkg/compiler/lib/src/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.
 
 import '../compiler.dart' show Compiler;
 import '../constants/values.dart';
 import '../elements/elements.dart';
 import '../js_backend/js_backend.dart';
 import '../types/types.dart';
 import '../universe/selector.dart' show Selector;
@@ skipping 335 matching lines @@
   void analyzeInputs(HInstruction user, int start) {
     List<HInstruction> inputs = user.inputs;
     for (int i = start; i < inputs.length; i++) {
       HInstruction input = inputs[i];
       if (!generateAtUseSite.contains(input) &&
           !input.isCodeMotionInvariant() &&
           input.usedBy.length == 1 &&
           input is! HPhi &&
           input is! HLocalValue &&
           !input.isJsStatement()) {
-        if (input.isPure()) {
+        if (isEffectivelyPure(input)) {
           // Only consider a pure input if it is in the same loop.
           // Otherwise, we might move GVN'ed instruction back into the
           // loop.
           if (user.hasSameLoopHeaderAs(input)) {
             // Move it closer to [user], so that instructions in
             // between do not prevent making it generate at use site.
             input.moveBefore(user);
             pureInputs.add(input);
             // Previous computations done on [input] are now invalid
             // because we moved [input] to another place. So all
             // non code motion invariant instructions need
             // to be removed from the [generateAtUseSite] set.
             input.inputs.forEach((instruction) {
               if (!instruction.isCodeMotionInvariant()) {
                 generateAtUseSite.remove(instruction);
               }
             });
             // Visit the pure input now so that the expected inputs
             // are after the expected inputs of [user].
             input.accept(this);
           }
         } else {
           expectedInputs.add(input);
         }
       }
     }
   }
 
+  // Some non-pure instructions may be treated as pure. HLocalGet depends on
+  // assignments, but we can ignore the initializing assignment since it will by
+  // construction always precede a use.
+  bool isEffectivelyPure(HInstruction instruction) {
+    if (instruction is HLocalGet) return !isAssignedLocal(instruction.local);
+    return instruction.isPure();
+  }
+
+  bool isAssignedLocal(HLocalValue local) {
+    // [HLocalValue]s have an initializing assignment which is guaranteed to
+    // precede the use, except for [HParameterValue]s which are 'assigned' at
+    // entry.
+    int initializingAssignmentCount = (local is HParameterValue) ? 0 : 1;
+    return local.usedBy
+        .where((user) => user is HLocalSet)
+        .skip(initializingAssignmentCount)
+        .isNotEmpty;
+  }
+
   void visitInstruction(HInstruction instruction) {
     // A code motion invariant instruction is dealt before visiting it.
     assert(!instruction.isCodeMotionInvariant());
     analyzeInputs(instruction, 0);
   }
 
   void visitInvokeSuper(HInvokeSuper instruction) {
     Element superMethod = instruction.element;
     Selector selector = instruction.selector;
     // If aliased super members cannot be used, we will generate code like
@@ skipping 79 matching lines @@
     // included in the expression.
 
     // The expectedInputs list holds non-trivial instructions that may
     // be generated at their use site, if they occur in the correct order.
     if (expectedInputs == null) expectedInputs = new List<HInstruction>();
     if (pureInputs == null) pureInputs = new Set<HInstruction>();
 
     // Pop instructions from expectedInputs until instruction is found.
     // Return true if it is found, or false if not.
     bool findInInputsAndPopNonMatching(HInstruction instruction) {
-      assert(!instruction.isPure());
+      assert(!isEffectivelyPure(instruction));
       while (!expectedInputs.isEmpty) {
         HInstruction nextInput = expectedInputs.removeLast();
         assert(!generateAtUseSite.contains(nextInput));
         assert(nextInput.usedBy.length == 1);
         if (identical(nextInput, instruction)) {
           return true;
         }
       }
       return false;
     }
 
     block.last.accept(this);
     for (HInstruction instruction = block.last.previous;
         instruction != null;
         instruction = instruction.previous) {
       if (generateAtUseSite.contains(instruction)) {
         continue;
       }
       if (instruction.isCodeMotionInvariant()) {
         markAsGenerateAtUseSite(instruction);
         continue;
       }
-      if (instruction.isPure()) {
+      if (isEffectivelyPure(instruction)) {
         if (pureInputs.contains(instruction)) {
           tryGenerateAtUseSite(instruction);
         } else {
           // If the input is not in the [pureInputs] set, it has not
           // 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:
@@ skipping 25 matching lines @@
           //   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
           // 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();
+          //   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.
             List<HInstruction> newInputs = expectedInputs.sublist(oldLength);
             int newCount = newInputs.length;
             expectedInputs.setRange(
@@ skipping 194 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);
     }
   }
 }