Fix a long-standing bug in the computation of the live environments for bailouts. When visiting a l…

frog/leg/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;
-  Environment() : lives = new Set<HInstruction>();
+  final Set<HBasicBlock> loopMarkers;
+  Environment() : lives = new Set<HInstruction>(),
+                  loopMarkers = new Set<HBasicBlock>();
   Environment.from(Environment other)
-    : lives = new Set<HInstruction>.from(other.lives);
+    : lives = new Set<HInstruction>.from(other.lives),
+      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
+
+  Environment.forLoop(Environment other)

[floitsch, 2012/03/12 11:35:10]

forLoopBody

[ngeoffray, 2012/03/12 11:53:24]

Done.

+    : lives = new Set<HInstruction>(),
+      loopMarkers = new Set<HBasicBlock>.from(other.loopMarkers);
 
   void remove(HInstruction instruction) {
     lives.remove(instruction);
   }
 
   void add(HInstruction instruction) {
     if (!instruction.generateAtUseSite()) {
       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);
   }
 
   List<HInstruction> buildAndSetLast(HInstruction instruction) {
     remove(instruction);
     List<HInstruction> result = new List<HInstruction>.from(lives);
     result.addLast(instruction);
     add(instruction);
     return result;
   }
 
   bool isEmpty() => lives.isEmpty();
   bool contains(HInstruction instruction) => lives.contains(instruction);
+  bool containsLoopMarker(HBasicBlock block) => loopMarkers.contains(block);
   void clear() => lives.clear();
 }
 
 /**
  * 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.
  */
 class SsaEnvironmentBuilder extends HBaseVisitor {
   final Compiler compiler;
   Environment environment;
   SubGraph subGraph;
 
-  SsaEnvironmentBuilder(Compiler this.compiler);
+  final Map<HInstruction, Environment> capturedEnvironments;
+
+  SsaEnvironmentBuilder(Compiler this.compiler)
+    : capturedEnvironments = new Map<HInstruction, Environment>();
 
   void visitGraph(HGraph graph) {
     subGraph = new SubGraph(graph.entry, graph.exit);
     environment = new Environment();
     visitBasicBlock(graph.entry);
     assert(environment.isEmpty());
+    insertCapturedEnvironments();
+  }
+
+  abstract void insertCapturedEnvironments();
+  abstract bool shouldCaptureEnvironment(HInstruction instruction);
+
+  void maybeCaptureEnvironment(HInstruction instruction) {
+    if (shouldCaptureEnvironment(instruction)) {
+      capturedEnvironments[instruction] = new Environment.from(environment);
+    }
   }
 
   void visitSubGraph(SubGraph newSubGraph) {
     SubGraph oldSubGraph = subGraph;
     subGraph = newSubGraph;
     visitBasicBlock(subGraph.start);
     subGraph = oldSubGraph;
   }
 
   void visitBasicBlock(HBasicBlock block) {
     if (!subGraph.contains(block)) return;
     block.last.accept(this);
 
     HInstruction instruction = block.last.previous;
     while (instruction != null) {
       HInstruction previous = instruction.previous;
       instruction.accept(this);
       instruction = previous;
     }
 
     for (HPhi phi = block.phis.first; phi != null; phi = phi.next) {
       phi.accept(this);
     }
+
+    if (block.isLoopHeader()) {

[floitsch, 2012/03/12 11:35:10]

Add a comment, maybe even with an example.

[ngeoffray, 2012/03/12 11:53:24]

Done.

+      environment.removeLoopMarker(block);
+      capturedEnvironments.forEach((instruction, env) {
+        if (env.containsLoopMarker(block)) {
+          env.removeLoopMarker(block);
+          env.addAll(environment);
+        }
+      });
+    }
   }
 
   void visitPhi(HPhi phi) {
+    maybeCaptureEnvironment(phi);
     environment.remove(phi);
     // If the block is a loop header, we insert the incoming values of
     // the phis, and remove the loop values.
     // If the block is not a loop header, the phi will be handled by
     // the control flow instruction.
     if (phi.block.isLoopHeader()) {
       environment.add(phi.inputs[0]);
       for (int i = 1, len = phi.inputs.length; i < len; i++) {
         environment.remove(phi.inputs[i]);
       }
     }
   }
 
   void visitInstruction(HInstruction instruction) {
+    maybeCaptureEnvironment(instruction);
     environment.remove(instruction);
     for (int i = 0, len = instruction.inputs.length; i < len; i++) {
       environment.add(instruction.inputs[i]);
     }
   }
 
   void visitIf(HIf instruction) {
     HIfBlockInformation info = instruction.blockInformation;
     HBasicBlock joinBlock = info.joinBlock;
 
@@ skipping 66 matching lines @@
 
   void visitBreak(HBreak breakInstruction) {
     unimplemented();
   }
 
   void visitLoopBranch(HLoopBranch branch) {
     HBasicBlock block = branch.block;
 
     // Visit the code after the loop.
     visitBasicBlock(block.successors[1]);
-    // TODO(ngeoffray): Remove the instructions of the loop-exit from
-    // the environment.
 
+    Environment joinEnvironment = environment;
+
+    // When visiting the loop body, we don't require the live
+    // instructions after the loop body to be in the environment. They
+    // will be either recomputed in the loop header, or inserted
+    // with the loop marker.

[floitsch, 2012/03/12 11:35:10]

However we need the current environment to transfer already existing loop
markers.

[ngeoffray, 2012/03/12 11:53:24]

Done.

+    environment = new Environment.forLoop(environment);
+
+    // Put the loop phis in the environment.
     HBasicBlock header = block.isLoopHeader() ? block : block.parentLoopHeader;
-    // Put the loop phis in the environment.
     for (HPhi phi = header.phis.first; phi != null; phi = phi.next) {
       for (int i = 1, len = phi.inputs.length; i < len; i++) {
         environment.add(phi.inputs[i]);
       }
     }
 
+    // Add the loop marker
+    environment.addLoopMarker(header);
+
     if (!branch.isDoWhile()) {
       assert(block.successors[0] == block.dominatedBlocks[0]);
       visitBasicBlock(block.successors[0]);
     }
+
+    // We merge the environment required by the code after the loop,
+    // and the code inside the loop.
+    environment.addAll(joinEnvironment);
   }
 
   // Deal with all kinds of control flow instructions. In case we add
   // a new one, we will hit an internal error.
   void visitExit(HExit exit) {}
 
   void visitReturn(HReturn instruction) {
     environment.clear();
     visitInstruction(instruction);
   }
@@ skipping 12 matching lines @@
 /**
  * Visits the graph and replaces guards with guards that capture the
  * environment.
  */
 class SsaTypeGuardBuilder extends SsaEnvironmentBuilder implements OptimizationPhase {
 
   final String name = 'SsaTypeGuardBuilder';
 
   SsaTypeGuardBuilder(Compiler compiler) : super(compiler);
 
-  void tryInsertTypeGuard(HInstruction instruction,
-                          HInstruction insertionPoint) {
-    // If we found a type for the instruction, but the instruction
-    // does not know if it produces that type, add a type guard.
-    if (instruction.type.isKnown() && !instruction.hasExpectedType()) {
-      // The type guard expects the guarded instruction to be at the
-      // end of the inputs.
-      List<HInstruction> inputs = environment.buildAndSetLast(instruction);
+  bool shouldCaptureEnvironment(HInstruction instruction) {
+    return instruction.type.isKnown() && !instruction.hasExpectedType();
+  }
+
+  void insertCapturedEnvironments() {
+    capturedEnvironments.forEach((HInstruction instruction, Environment env) {
+      List<HInstruction> inputs = env.buildAndSetLast(instruction);
       HTypeGuard guard =
           new HTypeGuard(instruction.type, inputs, instruction.id);
       // Remove the instruction's type, the guard is now holding that
       // type.
       instruction.type = HType.UNKNOWN;
       instruction.block.rewrite(instruction, guard);
+      HInstruction insertionPoint = (instruction is HPhi)
+          ? phi.block.first
+          : instruction.next;
       insertionPoint.block.addBefore(insertionPoint, guard);
-    }
-  }
-
-
-  void visitInstruction(HInstruction instruction) {
-    tryInsertTypeGuard(instruction, instruction.next);
-    super.visitInstruction(instruction);
-  }
-
-  void visitPhi(HPhi phi) {
-    tryInsertTypeGuard(phi, phi.block.first);
-    super.visitPhi(phi);
+    });
   }
 }
 
 /*
  * Visits the graph and inserts [HBailoutTarget] instructions where
  * the optimized version had [HTypeGuard] instructions.
  */
 class SsaBailoutBuilder extends SsaEnvironmentBuilder implements OptimizationPhase {
   final Map<int, BailoutInfo> bailouts;
   final String name = 'SsaBailoutBuilder';
 
   SsaBailoutBuilder(Compiler compiler, this.bailouts) : super(compiler);
 
-  void checkBailout(HInstruction instruction, HInstruction insertionPoint) {
-    BailoutInfo info = bailouts[instruction.id];
-    if (info != null) {
-      List<HInstruction> inputs = environment.buildAndSetLast(instruction);
-      HBailoutTarget bailout = new HBailoutTarget(info.bailoutId, inputs);
-      instruction.block.addBefore(insertionPoint, bailout);
-    }
+  bool shouldCaptureEnvironment(HInstruction instruction) {
+    return bailouts[instruction.id] != null;
   }
 
-  void visitInstruction(HInstruction instruction) {
-    checkBailout(instruction, instruction.next);
-    super.visitInstruction(instruction);
-  }
-
-  void visitPhi(HPhi phi) {
-    checkBailout(phi, phi.block.first);
-    super.visitPhi(phi);
+  void insertCapturedEnvironments() {
+    capturedEnvironments.forEach((HInstruction instruction, Environment env) {
+      BailoutInfo info = bailouts[instruction.id];
+      List<HInstruction> inputs = env.buildAndSetLast(instruction);
+      HBailoutTarget bailout = new HBailoutTarget(info.bailoutId, inputs);
+      HInstruction insertionPoint = (instruction is HPhi)
+          ? phi.block.first
+          : instruction.next;
+      instruction.block.addBefore(insertionPoint, bailout);
+    });
   }
 }
 
 /**
  * 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;
@@ skipping 54 matching lines @@
     compiler.internalError('Control flow instructions already dealt with.',
                            instruction: instruction);
   }
 
   visitBailoutTarget(HBailoutTarget target) {
     blocks.forEach((HBasicBlock block) {
       block.bailouts.add(target);
     });
   }
 }