dart2js cps: Better side-effect tracking in loops.

pkg/compiler/lib/src/cps_ir/bounds_checker.dart

 // Copyright (c) 2015, 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.
 
 library dart2js.cps_ir.bounds_checker;
 
 import 'cps_ir_nodes.dart';
 import 'optimizers.dart' show Pass;
 import 'octagon.dart';
 import '../constants/values.dart';
 import 'cps_fragment.dart';
 import 'type_mask_system.dart';
 import '../world.dart';
 import '../elements/elements.dart';
+import 'loop_effects.dart';
+
+
 
 /// Eliminates bounds checks when they can be proven safe.
 ///
 /// In general, this pass will try to eliminate any branch with arithmetic
 /// in the condition, i.e. `x < y`, `x <= y`, `x == y` etc.
 ///
 /// The analysis uses an [Octagon] abstract domain. Unlike traditional octagon
 /// analyzers, we do not use a closed matrix representation, but just maintain
 /// a bucket of constraints.  Constraints can therefore be added and removed
 /// on-the-fly without significant overhead.
 ///
 /// We never copy the constraint system.  While traversing the IR, the
 /// constraint system is mutated to take into account the knowledge that is
 /// valid for the current location.  Constraints are added when entering a
 /// branch, for instance, and removed again after the branch has been processed.
 ///
 /// Loops are analyzed in two passes. The first pass establishes monotonicity
 /// of loop variables, which the second pass uses to compute upper/lower bounds.
-/// The first pass also records whether any side effects occurred in the loop.
 ///
 /// The two-pass scheme is suboptimal compared to a least fixed-point
 /// computation, but does not require repeated iteration.  Repeated iteration
 /// would be expensive, since we cannot perform a sparse analysis with our
 /// mutable octagon representation.
 class BoundsChecker extends TrampolineRecursiveVisitor implements Pass {
   String get passName => 'Bounds checker';
 
   static const int MAX_UINT32 = (1 << 32) - 1;
 
   /// All integers of this magnitude or less are representable as JS numbers.
   static const int MAX_SAFE_INT = (1 << 53) - 1;
 
   /// Marker to indicate that a continuation should get a unique effect number.
   static const int NEW_EFFECT = -1;
 
   final TypeMaskSystem types;
   final World world;
 
   /// Fields for the constraint system and its variables.
   final Octagon octagon = new Octagon();
   final Map<Primitive, SignedVariable> valueOf = {};
   final Map<Primitive, Map<int, SignedVariable>> lengthOf = {};
 
   /// Fields for the two-pass handling of loops.
-  final Set<Continuation> loopsWithSideEffects = new Set<Continuation>();
   final Map<Parameter, Monotonicity> monotonicity = <Parameter, Monotonicity>{};
   bool isStrongLoopPass;
   bool foundLoop = false;
 
   /// Fields for tracking side effects.
   ///
   /// The IR is divided into regions wherein the lengths of indexable objects
   /// are known not to change. Regions are identified by their "effect number".
+  LoopSideEffects loopEffects;
   final Map<Continuation, int> effectNumberAt = <Continuation, int>{};
   int currentEffectNumber = 0;
   int effectNumberCounter = 0;
 
   BoundsChecker(this.types, this.world);
 
   void rewrite(FunctionDefinition node) {
+    loopEffects = new LoopSideEffects(node, world);
     isStrongLoopPass = false;
     visit(node);
     if (foundLoop) {
       isStrongLoopPass = true;
       effectNumberAt.clear();
       visit(node);
     }
   }
 
   // ------------- VARIABLES -----------------
@@ skipping 310 matching lines @@
         Monotonicity mono = monotonicity[param];
         if (mono == null) {
           // Value never changes. This is extremely uncommon.
           initialValue.substituteFor(param);
         } else if (mono == Monotonicity.Increasing) {
           makeGreaterThanOrEqual(getValue(param), initialVariable);
         } else if (mono == Monotonicity.Decreasing) {
           makeLessThanOrEqual(getValue(param), initialVariable);
         }
       }
-      if (loopsWithSideEffects.contains(cont)) {
-        currentEffectNumber = makeNewEffect();
-      }
-    } else {
-      // During the weak pass, conservatively make a new effect number in the
-      // loop body. This may be strengthened during the strong pass.
+    }
+    if (loopEffects.loopChangesLength(cont)) {
       currentEffectNumber = effectNumberAt[cont] = makeNewEffect();
     }
     push(cont);
   }
 
   void analyzeLoopContinue(InvokeContinuation node) {
     Continuation cont = node.continuation.definition;
 
     // During the strong loop phase, there is no need to compute monotonicity,
     // and we already put bounds on the loop variables when we went into the
@@ skipping 12 matching lines @@
         // We couldn't prove that the value does not increase, so assume
         // henceforth that it might be increasing.
         markMonotonicity(cont.parameters[i], Monotonicity.Increasing);
       }
       if (!isDefinitelyGreaterThanOrEqualTo(arg, paramVar)) {
         // We couldn't prove that the value does not decrease, so assume
         // henceforth that it might be decreasing.
         markMonotonicity(cont.parameters[i], Monotonicity.Decreasing);
       }
     }
-
-    // If a side effect has occurred between the entry and continue, mark
-    // the loop as having side effects.
-    if (currentEffectNumber != effectNumberAt[cont]) {
-      loopsWithSideEffects.add(cont);
-    }
   }
 
   void markMonotonicity(Parameter param, Monotonicity mono) {
     Monotonicity current = monotonicity[param];
     if (current == null) {
       monotonicity[param] = mono;
     } else if (current != mono) {
       monotonicity[param] = Monotonicity.NotMonotone;
     }
   }
@@ skipping 148 matching lines @@
     }
     return node.body;
   }
 }
 
 /// Lattice representing the known (weak) monotonicity of a loop variable.
 ///
 /// The lattice bottom is represented by `null` and represents the case where
 /// the loop variable never changes value during the loop.
 enum Monotonicity { NotMonotone, Increasing, Decreasing, }