Simplify generated code for trivial bailout methods.

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);
 }
 
 /**
  * Keeps track of the execution environment for instructions. An
  * execution environment contains the SSA instructions that are live.
  */
 class Environment {
   final Set<HInstruction> lives;
   final Set<HBasicBlock> loopMarkers;
   Environment() : lives = new Set<HInstruction>(),
                   loopMarkers = new Set<HBasicBlock>();
   Environment.from(Environment other)
     : lives = new Set<HInstruction>.from(other.lives),
       loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
 
   void remove(HInstruction instruction) {
     lives.remove(instruction);
   }
 
   void add(HInstruction instruction) {
-    if (!instruction.isCodeMotionInvariant()) {
+    // If the instruction is a type guard, we add its checked input
+    // instead. This allows sharing the same environment between
+    // different type guards.
+    // 
+    // Also, we don't need to add code motion invariant instructions
+    // in the live set (because we generate them at use-site), except
+    // for parameters that are not 'this', which is always passed as
+    // the receiver.
+    if (instruction is HTypeGuard) {
+      add(instruction.checkedInput);
+    } else if (!instruction.isCodeMotionInvariant()
+               || (instruction is HParameterValue && instruction is !HThis)) {
       lives.add(instruction);
     } else {
       for (int i = 0, len = instruction.inputs.length; i < len; i++) {
         add(instruction.inputs[i]);
       }
     }
   }
 
   void addLoopMarker(HBasicBlock block) {
     loopMarkers.add(block);
   }
 
   void removeLoopMarker(HBasicBlock block) {
     loopMarkers.remove(block);
   }
 
   void addAll(Environment other) {
     lives.addAll(other.lives);
     loopMarkers.addAll(other.loopMarkers);
   }
 
-  /**
-   * Stores all live variables in the guard. The guarded instruction will be the
-   * last input in the guard's input list.
-   */
-  void storeInGuard(HTypeGuard guard) {
-    HInstruction guarded = guard.guarded;
-    List<HInstruction> inputs = guard.inputs;
-    assert(inputs.length == 1);
-    inputs.clear();
-    // Remove the guarded from the environment, so that we are sure it is last
-    // when we add it again.
-    remove(guarded);
-    inputs.addAll(lives);
-    inputs.addLast(guarded);
-    add(guarded);
-    for (int i = 0; i < inputs.length - 1; i++) {
-      HInstruction input = inputs[i];
-      input.usedBy.add(guard);
-    }
-  }
-
   bool isEmpty() => lives.isEmpty() && loopMarkers.isEmpty();
 }
 
 
 /**
  * Visits the graph in dominator order and inserts TypeGuards in places where
  * we consider the guard to be of value.
  *
  * Might modify the [:propagatedType:] fields of the instructions in an
  * inconsistent way. No further analysis should rely on them.
@@ skipping 95 matching lines @@
     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];
-      HTypeGuard guard = new HTypeGuard(speculativeType, stateId++, inputs);
+      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.
+      int state;
+      if (insertionPoint.previous is HTypeGuard) {
+        HTypeGuard other = insertionPoint.previous;
+        state = other.state;
+      } else {
+        state = stateId++;
+      }
+      HTypeGuard guard = new HTypeGuard(speculativeType, state, inputs);
       guard.propagatedType = speculativeType;
       work.guards.add(guard);
       instruction.block.rewrite(instruction, guard);
-      HInstruction insertionPoint = (instruction is HPhi)
-          ? instruction.block.first
-          : instruction.next;
       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.
@@ skipping 99 matching lines @@
   }
 
   void visitInstruction(HInstruction instruction) {
     environment.remove(instruction);
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       environment.add(instruction.inputs[i]);
     }
   }
 
   void insertCapturedEnvironments() {
+    Map<int, HTypeGuard> seenGuardStates = new Map<int, HTypeGuard>();
     capturedEnvironments.forEach((HTypeGuard guard, Environment env) {
-      env.storeInGuard(guard);
+      storeInGuard(guard, env.lives, seenGuardStates);
     });
   }
+
+  /**
+   * 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;
 
-  SsaBailoutPropagator(Compiler this.compiler)
+  /**
+   * 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;
+
+  /**
+   * The first type guard in the graph.
+   */
+  HTypeGuard firstTypeGuard;
+
+  /**
+   * 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,

[kasperl, 2012/06/13 07:37:05]

Arguments fit on one line.

[ngeoffray, 2012/06/13 07:41:38]

Done.

+                       this.generateAtUseSite)
       : blocks = <HBasicBlock>[],
         labeledBlockInformations = <HLabeledBlockInformation>[];
 
   void visitGraph(HGraph graph) {
     subGraph = new SubGraph(graph.entry, graph.exit);
-    blocks.addLast(graph.entry);
     visitBasicBlock(graph.entry);
-    blocks.removeLast();
     if (!blocks.isEmpty()) {
       compiler.internalError('Bailout propagation',
           node: compiler.currentElement.parseNode(compiler));
     }
   }
 
   void visitBasicBlock(HBasicBlock block) {
     // Abort traversal if we are leaving the currently active sub-graph.
     if (!subGraph.contains(block)) return;
 
     if (block.isLoopHeader()) {
       blocks.addLast(block);
-    } else if (block.isLabeledBlock() && blocks.last() !== block) {
+    } else if (block.isLabeledBlock()
+               && (blocks.isEmpty() || blocks.last() !== block)) {
       HLabeledBlockInformation info = block.blockFlow.body;
       visitStatements(info.body);
       return;
     }
 
     HInstruction instruction = block.first;
     while (instruction != null) {
       instruction.accept(this);
       instruction = instruction.next;
     }
@@ skipping 77 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) {
-    blocks.forEach((HBasicBlock block) {
-      block.guards.add(guard);
-    });
+    if (blocks.isEmpty()) {
+      if (firstTypeGuard === null || firstTypeGuard.state === guard.state) {
+        firstTypeGuard = guard;
+      } else {
+        hasComplexTypeGuards = true;
+      }
+    } else {
+      hasComplexTypeGuards = true;
+      blocks.forEach((HBasicBlock block) {
+        block.guards.add(guard);
+      });
+    }
   }
 }