Wrap block-informations when embedding them in the graph.

lib/compiler/implementation/ssa/nodes.dart

Index: lib/compiler/implementation/ssa/nodes.dart
diff --git a/lib/compiler/implementation/ssa/nodes.dart b/lib/compiler/implementation/ssa/nodes.dart
index 0208834cec5c3f57bd86eac21a0d448404b7d1f6..cca37216e97358b246e38ea0905d1e945a1c9a4c 100644
--- a/lib/compiler/implementation/ssa/nodes.dart
+++ b/lib/compiler/implementation/ssa/nodes.dart
@@ -139,12 +139,11 @@ class HGraph {
     return result;
   }
 
-  HBasicBlock addNewLoopHeaderBlock(int kind,
-                                    TargetElement target,
+  HBasicBlock addNewLoopHeaderBlock(TargetElement target,
                                     List<LabelElement> labels) {
     HBasicBlock result = addNewBlock();
-    result.blockInformation =
-        new HLoopInformation(kind, result, target, labels);
+    result.loopInformation =
+        new HLoopInformation(result, target, labels);
     return result;
   }
 
@@ -423,7 +422,8 @@ class HBasicBlock extends HInstructionList implements Hashable {
 
   HInstructionList phis;
 
-  HBlockInformation blockInformation = null;
+  HLoopInformation loopInformation = null;
+  HBlockFlow blockInformation = null;

[karlklose, 2012/05/08 08:02:46]

Consider renaming this to blockFlow.

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Done.

   HBasicBlock parentLoopHeader = null;
   List<HTypeGuard> guards;
 
@@ -448,13 +448,16 @@ class HBasicBlock extends HInstructionList implements Hashable {
   bool isClosed() => status == STATUS_CLOSED;
 
   bool isLoopHeader() {
-    if (blockInformation is HLoopInformation) {
-      HLoopInformation info = blockInformation;
-      return (this === info.header);
-    }
-    return false;
+    return loopInformation !== null;
+  }
+
+  void setBlockInfo(HBlockInformation blockInfo, HBasicBlock continuation) {

[karlklose, 2012/05/08 08:02:46]

I would prefer calling this method setBlockInformation.

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Changed to setBlockFlow.

+    blockInformation = new HBlockFlow(blockInfo, continuation);
   }
-  bool isLabeledBlock() => blockInformation is HLabeledBlockInformation;
+
+  bool isLabeledBlock() =>
+    blockInformation !== null &&
+    blockInformation.body is HLabeledBlockInformation;
 
   HBasicBlock get enclosingLoopHeader() {
     if (isLoopHeader()) return this;
@@ -568,7 +571,6 @@ class HBasicBlock extends HInstructionList implements Hashable {
     assert(isLoopHeader());
     // Only the first entry into the loop is from outside the
     // loop. All other entries must be back edges.
-    HLoopInformation loopInformation = this.blockInformation;
     for (int i = 1, length = predecessors.length; i < length; i++) {
       loopInformation.addBackEdge(predecessors[i]);
     }
@@ -1655,7 +1657,7 @@ class HTry extends HControlFlow {
 
 class HIf extends HConditionalBranch {
   bool hasElse;
-  HIfBlockInformation blockInformation = null;
+  HBlockFlow blockInformation = null;
   HIf(HInstruction condition, this.hasElse) : super(<HInstruction>[condition]);
   toString() => 'if';
   accept(HVisitor visitor) => visitor.visitIf(this);
@@ -1674,7 +1676,7 @@ class HIf extends HConditionalBranch {
     }
   }
 
-  HBasicBlock get joinBlock() => blockInformation.joinBlock;
+  HBasicBlock get joinBlock() => blockInformation.continuation;
 }
 
 class HLoopBranch extends HConditionalBranch {
@@ -2163,9 +2165,74 @@ class HTypeConversion extends HInstruction {
   bool dataEquals(HTypeConversion other) => type == other.type;
 }
 
+// Non-block-based loop information.

[karlklose, 2012/05/08 08:02:46]

Doc-style (/** ... *)?

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Done.

+class HLoopInformation {
+  final HBasicBlock header;
+  final List<HBasicBlock> blocks;
+  final List<HBasicBlock> backEdges;
+  final List<LabelElement> labels;
+  final TargetElement target;
+  /** The corresponding block information */

[karlklose, 2012/05/08 08:02:46]

Is this intended to be in doc-style?

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Yes. Missing a final '.' I can see.

+  HLoopBlockInformation loopBlockInformation;
+
+  HLoopInformation(this.header, this.target, this.labels)
+      : blocks = new List<HBasicBlock>(),
+        backEdges = new List<HBasicBlock>();
+
+  void addBackEdge(HBasicBlock predecessor) {
+    backEdges.add(predecessor);
+    addBlock(predecessor);
+  }
+
+  // Adds a block and transitively all its predecessors in the loop as
+  // loop blocks.
+  void addBlock(HBasicBlock block) {
+    if (block === header) return;
+    HBasicBlock parentHeader = block.parentLoopHeader;
+    if (parentHeader === header) {
+      // Nothing to do in this case.
+    } else if (parentHeader !== null) {
+      addBlock(parentHeader);
+    } else {
+      block.parentLoopHeader = header;
+      blocks.add(block);
+      for (int i = 0, length = block.predecessors.length; i < length; i++) {
+        addBlock(block.predecessors[i]);
+      }
+    }
+  }
+
+  HBasicBlock getLastBackEdge() {
+    int maxId = -1;
+    HBasicBlock result = null;
+    for (int i = 0, length = backEdges.length; i < length; i++) {
+      HBasicBlock current = backEdges[i];
+      if (current.id > maxId) {
+        maxId = current.id;
+        result = current;
+      }
+    }
+    return result;
+  }
+

[karlklose, 2012/05/08 08:02:46]

Remove line.

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Done.

+}
+
+
+/**
+ * Embedding of a [HBlockInformation] for block-structure based traversal
+ * in a dominator based flow traversal by attaching it to a basic block.
+ * To go back to dominator-based traversal, a [HSubGraphBlockInformation]
+ * structure can be added in the block structure.
+ */
+class HBlockFlow {
+  final HBlockInformation body;
+  final HBasicBlock continuation;
+  HBlockFlow(this.body, this.continuation);
+}
+
+
 /**
- * Information about a syntactic-like structure that can be attached
- * to a [HBasicBlock].
+ * Information about a syntactic-like structure.
  */
 interface HBlockInformation {
   HBasicBlock get start();
@@ -2173,6 +2240,7 @@ interface HBlockInformation {
   bool accept(HBlockInformationVisitor visitor);
 }
 
+
 /**
  * Information about a statement-like structure.
  */
@@ -2180,6 +2248,7 @@ interface HStatementInformation extends HBlockInformation {
   bool accept(HStatementInformationVisitor visitor);
 }
 
+
 /**
  * Information about an expression-like structure.
  */
@@ -2191,21 +2260,27 @@ interface HExpressionInformation extends HBlockInformation {
 
 interface HStatementInformationVisitor {
   bool visitLabeledBlockInfo(HLabeledBlockInformation info);
-  bool visitLoopInfo(HLoopInformation info);
+  bool visitLoopInfo(HLoopBlockInformation info);
   bool visitIfInfo(HIfBlockInformation info);
   bool visitTryInfo(HTryBlockInformation info);
+  bool visitSequenceInfo(HStatementSequenceInformation info);
+  // Pseudo-structure embedding a dominator-based traversal into
+  // the block-structure traversal. This will eventually go away.
   bool visitSubGraphInfo(HSubGraphBlockInformation info);
 }
 
+
 interface HExpressionInformationVisitor {
   bool visitAndOrInfo(HAndOrBlockInformation info);
   bool visitSubExpressionInfo(HSubExpressionBlockInformation info);
 }
 
+
 interface HBlockInformationVisitor extends HStatementInformationVisitor,
                                            HExpressionInformationVisitor {
 }
 
+
 /**
  * Generic class wrapping a [SubGraph] as a block-information until
  * all structures are handled properly.
@@ -2240,20 +2315,31 @@ class HSubExpressionBlockInformation implements HExpressionInformation {
 }
 
 
+/** A sequence of separate statements. */
+class HStatementSequenceInformation implements HStatementInformation {
+  final List<HStatementInformation> statements;
+  HStatementSequenceInformation(this.statements);
+
+  HBasicBlock get start() => statements[0].start;
+  HBasicBlock get end() => statements.last().end;
+
+  bool accept(HStatementInformationVisitor visitor) =>
+    visitor.visitSequenceInfo(this);
+}
+
+
 class HLabeledBlockInformation implements HStatementInformation {
   final HStatementInformation body;
-  final HBasicBlock joinBlock;
   final List<LabelElement> labels;
   final TargetElement target;
   final bool isContinue;
 
-  HLabeledBlockInformation(this.body, this.joinBlock,
+  HLabeledBlockInformation(this.body,
                            List<LabelElement> labels,
                            [this.isContinue = false]) :
       this.labels = labels, this.target = labels[0].target;
 
   HLabeledBlockInformation.implicit(this.body,
-                                    this.joinBlock,
                                     this.target,
                                     [this.isContinue = false])
       : this.labels = const<LabelElement>[];
@@ -2270,33 +2356,30 @@ class LoopTypeVisitor extends AbstractVisitor {
   int visitNode(Node node) {
     unreachable();
   }
-  int visitWhile(While node) => HLoopInformation.WHILE_LOOP;
-  int visitFor(For node) => HLoopInformation.FOR_LOOP;
-  int visitDoWhile(DoWhile node) => HLoopInformation.DO_WHILE_LOOP;
-  int visitForIn(ForIn node) => HLoopInformation.FOR_IN_LOOP;
+  int visitWhile(While node) => HLoopBlockInformation.WHILE_LOOP;
+  int visitFor(For node) => HLoopBlockInformation.FOR_LOOP;
+  int visitDoWhile(DoWhile node) => HLoopBlockInformation.DO_WHILE_LOOP;
+  int visitForIn(ForIn node) => HLoopBlockInformation.FOR_IN_LOOP;
 }
 
-class HLoopInformation implements HStatementInformation {
+class HLoopBlockInformation implements HStatementInformation {
   static final int WHILE_LOOP = 0;
   static final int FOR_LOOP = 1;
   static final int DO_WHILE_LOOP = 2;
   static final int FOR_IN_LOOP = 3;
 
   final int kind;
-  final HBasicBlock header;
-  final List<HBasicBlock> blocks;
-  final List<HBasicBlock> backEdges;
-  final List<LabelElement> labels;
+  final HExpressionInformation initializer;
+  final HExpressionInformation condition;
+  final HStatementInformation body;
+  final HExpressionInformation updates;
   final TargetElement target;
-  HExpressionInformation initializer = null;
-  HExpressionInformation condition = null;
-  HStatementInformation body = null;
-  HExpressionInformation updates = null;
-  HBasicBlock joinBlock;
+  final List<LabelElement> labels;
 
-  HLoopInformation(this.kind, this.header, this.target, this.labels)
-      : blocks = new List<HBasicBlock>(),
-        backEdges = new List<HBasicBlock>();
+  HLoopBlockInformation(
+      this.kind,

[karlklose, 2012/05/08 08:02:46]

Start parameters on the same line as constructor?

[Lasse Reichstein Nielsen, 2012/05/08 11:40:34]

Done.

+      this.initializer, this.condition, this.body, this.updates,
+      this.target, this.labels);
 
   HBasicBlock get start() {
     if (initializer !== null) return initializer.start;
@@ -2318,42 +2401,6 @@ class HLoopInformation implements HStatementInformation {
     return node.accept(const LoopTypeVisitor());
   }
 
-  void addBackEdge(HBasicBlock predecessor) {
-    backEdges.add(predecessor);
-    addBlock(predecessor);
-  }
-
-  // Adds a block and transitively all its predecessors in the loop as
-  // loop blocks.
-  void addBlock(HBasicBlock block) {
-    if (block === header) return;
-    HBasicBlock parentHeader = block.parentLoopHeader;
-    if (parentHeader === header) {
-      // Nothing to do in this case.
-    } else if (parentHeader !== null) {
-      addBlock(parentHeader);
-    } else {
-      block.parentLoopHeader = header;
-      blocks.add(block);
-      for (int i = 0, length = block.predecessors.length; i < length; i++) {
-        addBlock(block.predecessors[i]);
-      }
-    }
-  }
-
-  HBasicBlock getLastBackEdge() {
-    int maxId = -1;
-    HBasicBlock result = null;
-    for (int i = 0, length = backEdges.length; i < length; i++) {
-      HBasicBlock current = backEdges[i];
-      if (current.id > maxId) {
-        maxId = current.id;
-        result = current;
-      }
-    }
-    return result;
-  }
-
   bool accept(HStatementInformationVisitor visitor) =>
     visitor.visitLoopInfo(this);
 }
@@ -2362,11 +2409,9 @@ class HIfBlockInformation implements HStatementInformation {
   final HExpressionInformation condition;
   final HStatementInformation thenGraph;
   final HStatementInformation elseGraph;
-  final HBasicBlock joinBlock;
   HIfBlockInformation(this.condition,
                       this.thenGraph,
-                      this.elseGraph,
-                      this.joinBlock);
+                      this.elseGraph);
 
   HBasicBlock get start() => condition.start;
   HBasicBlock get end() => elseGraph === null ? thenGraph.end : elseGraph.end;
@@ -2379,11 +2424,9 @@ class HAndOrBlockInformation implements HExpressionInformation {
   final bool isAnd;
   final HExpressionInformation left;
   final HExpressionInformation right;
-  final HBasicBlock joinBlock;
   HAndOrBlockInformation(this.isAnd,
                          this.left,
-                         this.right,
-                         this.joinBlock);
+                         this.right);
 
   HBasicBlock get start() => left.start;
   HBasicBlock get end() => right.end;
@@ -2399,14 +2442,10 @@ class HTryBlockInformation implements HStatementInformation {
   final HParameterValue catchVariable;
   final HStatementInformation catchBlock;
   final HStatementInformation finallyBlock;
-  // TODO: Move joinBlock out of the structure, and into the surrounding
-  // structure.
-  final HBasicBlock joinBlock;
   HTryBlockInformation(this.body,
                        this.catchVariable,
                        this.catchBlock,
-                       this.finallyBlock,
-                       this.joinBlock);
+                       this.finallyBlock);
 
   HBasicBlock get start() => body.start;
   HBasicBlock get end() =>