Split TypeGuard and BailoutTarget.

lib/compiler/implementation/ssa/bailout.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.
 
 class BailoutInfo {
   int instructionId;
   int bailoutId;
   BailoutInfo(this.instructionId, this.bailoutId);
 }
 
@@ skipping 134 matching lines @@
       if (isNested(userLoopHeader, currentLoopHeader)) return true;
     }
 
     // To speed up computations on values loaded from arrays, we
     // insert type guards for builtin array indexing operations in
     // nested loops. Since this can blow up code size quite
     // significantly, we only do it if type guards have already been
     // inserted for this method. The code size price for an additional
     // type guard is much smaller than the first one that causes the
     // generation of a bailout method.
-    if (instruction is HIndex && instruction.builtin && hasTypeGuards) {
+    if (instruction is HIndex &&
+        (instruction as HIndex).builtin &&
+        hasTypeGuards) {
       HBasicBlock loopHeader = instruction.block.enclosingLoopHeader;
       if (loopHeader != null && loopHeader.parentLoopHeader != null) {
         return true;
       }
     }
 
     // Insert type guards if the method is likely to be called in a
     // loop.
     return calledInLoop;
   }
@@ skipping 16 matching lines @@
     // If the types agree we don't need to check.
     if (speculativeType == computedType) return false;
     // If a bailout check is more expensive than doing the actual operation
     // don't do it either.
     return typeGuardWouldBeValuable(instruction, speculativeType);
   }
 
   void visitInstruction(HInstruction instruction) {
     HType speculativeType = instruction.propagatedType;
     if (shouldInsertTypeGuard(instruction)) {
-      List<HInstruction> inputs = <HInstruction>[instruction];
       HInstruction insertionPoint;
       if (instruction is HPhi) {
         insertionPoint = instruction.block.first;
       } else if (instruction is HParameterValue) {
         // We insert the type guard at the end of the entry block
         // because if a parameter is live, it must be kept in the live
         // environment. Not doing so would mean we could visit a
         // parameter and remove it from the environment before
         // visiting a type guard.
         insertionPoint = instruction.block.last;
       } else {
         insertionPoint = instruction.next;
       }
       // If the previous instruction is also a type guard, then both
       // guards have the same environment, and can therefore share the
       // same state id.
+      HBailoutTarget target;
       int state;
       if (insertionPoint.previous is HTypeGuard) {
         HTypeGuard other = insertionPoint.previous;
-        state = other.state;
+        target = other.bailoutTarget;
       } else {
         state = stateId++;
+        target = new HBailoutTarget(state);
+        insertionPoint.block.addBefore(insertionPoint, target);
       }
-      HTypeGuard guard = new HTypeGuard(speculativeType, state, inputs);
+      HTypeGuard guard = new HTypeGuard(speculativeType, instruction, target);
       guard.propagatedType = speculativeType;
       work.guards.add(guard);
       instruction.block.rewrite(instruction, guard);
       insertionPoint.block.addBefore(insertionPoint, guard);
     }
   }
 }
 
 /**
  * Computes the environment for each SSA instruction: visits the graph
  * in post-dominator order. Removes an instruction from the environment
  * and adds its inputs to the environment at the instruction's
  * definition.
  *
  * At the end of the computation, insert type guards in the graph.
  */
 class SsaEnvironmentBuilder extends HBaseVisitor implements OptimizationPhase {
   final Compiler compiler;
   final String name = 'SsaEnvironmentBuilder';
 
-  final Map<HInstruction, Environment> capturedEnvironments;
+  final Map<HBailoutTarget, Environment> capturedEnvironments;
   final Map<HBasicBlock, Environment> liveInstructions;
   Environment environment;
 
   SsaEnvironmentBuilder(Compiler this.compiler)
-    : capturedEnvironments = new Map<HInstruction, Environment>(),
+    : capturedEnvironments = new Map<HBailoutTarget, Environment>(),
       liveInstructions = new Map<HBasicBlock, Environment>();
 
 
   void visitGraph(HGraph graph) {
     visitPostDominatorTree(graph);
     if (!liveInstructions[graph.entry].isEmpty()) {
       compiler.internalError('Bailout environment computation',
           node: compiler.currentElement.parseNode(compiler));
     }
     updateLoopMarkers();
@@ skipping 63 matching lines @@
     // If the block is a loop header, we can remove the loop marker,
     // because it will just recompute the loop phis.
     if (block.isLoopHeader()) {
       environment.removeLoopMarker(block);
     }
 
     // Finally save the liveInstructions of that block.
     liveInstructions[block] = environment;
   }
 
-  void visitTypeGuard(HTypeGuard guard) {
-    visitInstruction(guard);
-    capturedEnvironments[guard] = new Environment.from(environment);
+  void visitBailoutTarget(HBailoutTarget target) {
+    visitInstruction(target);
+    capturedEnvironments[target] = new Environment.from(environment);
   }
 
   void visitInstruction(HInstruction instruction) {
     environment.remove(instruction);
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       environment.add(instruction.inputs[i]);
     }
   }
 
+  /**
+   * Stores all live variables in the bailout target and the guards.
+   */
   void insertCapturedEnvironments() {
-    Map<int, HTypeGuard> seenGuardStates = new Map<int, HTypeGuard>();
-    capturedEnvironments.forEach((HTypeGuard guard, Environment env) {
-      storeInGuard(guard, env.lives, seenGuardStates);
+    capturedEnvironments.forEach((HBailoutTarget target, Environment env) {
+      assert(target.inputs.length == 0);
+      target.inputs.addAll(env.lives);
+      // TODO(floitsch): we should add the bailout-target's input variables
+      // as input to the guards only in the optimized version. The
+      // non-optimized version does not use the bailout guards and it is
+      // unnecessary to keep the variables alive until the check.
+      for (HTypeGuard guard in target.usedBy) {
+        assert(guard.inputs.length == 2);

[ricow1, 2012/07/23 12:52:26]

Why is the length of the inputs always 2

[floitsch, 2012/07/23 13:27:48]

Added comment:
// A type-guard initially only has two inputs: the guarded instruction
// and the bailout-target. Only after adding the environment is it
// allowed to have more inputs.

+        guard.inputs.addAll(env.lives);
+      }
+      for (HInstruction live in env.lives) {
+        live.usedBy.add(target);
+        live.usedBy.addAll(target.usedBy);
+      }
     });
   }
-
-  /**
-   * Stores all live variables in the guard.
-   */
-  void storeInGuard(HTypeGuard guard,
-                    Set<HInstruction> lives,
-                    Map<int, HTypeGuard> seenGuardStates) {
-    HInstruction guarded = guard.guarded;
-    List<HInstruction> inputs = guard.inputs;
-    assert(inputs.length == 1);
-    inputs.clear();
-    HTypeGuard other = seenGuardStates[guard.state];
-    if (other !== null) {
-      // The guards are sharing the same state. Also share the same
-      // environment, in the same order.
-      inputs.addAll(other.inputs);
-      assert(inputs.length == lives.length);
-    } else {
-      seenGuardStates[guard.state] = guard;
-      inputs.addAll(lives);
-    }
-
-    for (int i = 0; i < inputs.length; i++) {
-      HInstruction input = inputs[i];
-      if (input == guarded) {
-        guard.checkedInputIndex = i;
-        // No need to update [input.usedBy], the guard is already
-        // there.
-      } else {
-        input.usedBy.add(guard);
-      }
-    }
-  }
 }
 
 /**
  * Propagates bailout information to blocks that need it. This visitor
  * is run before codegen, to know which blocks have to deal with
  * bailouts.
  */
 class SsaBailoutPropagator extends HBaseVisitor {
   final Compiler compiler;
   final List<HBasicBlock> blocks;
   final List<HLabeledBlockInformation> labeledBlockInformations;
   final Set<HInstruction> generateAtUseSite;
   SubGraph subGraph;
   int maxBailoutParameters = 0;
 
   /**
    * If set to true, the graph has either multiple bailouts in
    * different places, or a bailout inside an if or a loop. For such a
    * graph, the code generator will emit a generic switch.
    */
-  bool hasComplexTypeGuards = false;
+  bool hasComplexBailoutTargets = false;
 
   /**
    * The first type guard in the graph.
    */
-  HTypeGuard firstTypeGuard;
+  HBailoutTarget firstBailoutTarget;
 
   /**
    * If set, it is the first block in the graph where we generate
    * code. Blocks before this one are dead code in the bailout
    * version.
    */
 
   SsaBailoutPropagator(this.compiler, this.generateAtUseSite)
       : blocks = <HBasicBlock>[],
         labeledBlockInformations = <HLabeledBlockInformation>[];
@@ skipping 102 matching lines @@
 
     visitBasicBlock(branchBlock.successors[1]);
     // With labeled breaks we can have more dominated blocks.
     if (dominated.length >= 3) {
       for (int i = 2; i < dominated.length; i++) {
         visitBasicBlock(dominated[i]);
       }
     }
   }
 
-  visitTypeGuard(HTypeGuard guard) {
-    int inputLength = guard.inputs.length;
+  visitBailoutTarget(HBailoutTarget target) {
+    int inputLength = target.inputs.length;
     if (inputLength > maxBailoutParameters) {
       maxBailoutParameters = inputLength;
     }
     if (blocks.isEmpty()) {
-      if (firstTypeGuard === null || firstTypeGuard.state === guard.state) {
-        firstTypeGuard = guard;
+      if (firstBailoutTarget === null) {
+        firstBailoutTarget = target;
       } else {
-        hasComplexTypeGuards = true;
+        hasComplexBailoutTargets = true;
       }
     } else {
-      hasComplexTypeGuards = true;
+      hasComplexBailoutTargets = true;
       blocks.forEach((HBasicBlock block) {
-        block.guards.add(guard);
+        block.bailoutTargets.add(target);
       });
     }
   }
 }