Wrap block-informations when embedding them in the graph.

lib/compiler/implementation/ssa/nodes.dart

 // Copyright (c) 2011, 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.
 
 interface HVisitor<R> {
   R visitAdd(HAdd node);
   R visitBitAnd(HBitAnd node);
   R visitBitNot(HBitNot node);
   R visitBitOr(HBitOr node);
   R visitBitXor(HBitXor node);
@@ skipping 121 matching lines @@
     blocks.add(block);
     assert(blocks[id] === block);
   }
 
   HBasicBlock addNewBlock() {
     HBasicBlock result = new HBasicBlock();
     addBlock(result);
     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;
   }
 
   static HType mapConstantTypeToSsaType(Constant constant) {
     if (constant.isNull()) return HType.UNKNOWN;
     if (constant.isBool()) return HType.BOOLEAN;
     if (constant.isInt()) return HType.INTEGER;
     if (constant.isDouble()) return HType.DOUBLE;
     if (constant.isString()) return HType.STRING;
     if (constant.isList()) return HType.READABLE_ARRAY;
@@ skipping 258 matching lines @@
   // this [id]. The exception are back-edges.
   int id;
 
   static final int STATUS_NEW = 0;
   static final int STATUS_OPEN = 1;
   static final int STATUS_CLOSED = 2;
   int status = STATUS_NEW;
 
   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;
 
   final List<HBasicBlock> predecessors;
   List<HBasicBlock> successors;
 
   HBasicBlock dominator = null;
   final List<HBasicBlock> dominatedBlocks;
 
   HBasicBlock() : this.withId(null);
   HBasicBlock.withId(this.id)
       : phis = new HInstructionList(),
         predecessors = <HBasicBlock>[],
         successors = const <HBasicBlock>[],
         dominatedBlocks = <HBasicBlock>[],
         guards = <HTypeGuard>[];
 
   int hashCode() => id;
 
   bool isNew() => status == STATUS_NEW;
   bool isOpen() => status == STATUS_OPEN;
   bool isClosed() => status == STATUS_CLOSED;
 
   bool isLoopHeader() {
-    if (blockInformation is HLoopInformation) {
-      HLoopInformation info = blockInformation;
-      return (this === info.header);
-    }
-    return false;
+    return loopInformation !== null;
   }
-  bool isLabeledBlock() => blockInformation is HLabeledBlockInformation;
+
+  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 !== null &&
+    blockInformation.body is HLabeledBlockInformation;
 
   HBasicBlock get enclosingLoopHeader() {
     if (isLoopHeader()) return this;
     return parentLoopHeader;
   }
 
   bool hasGuards() => !guards.isEmpty();
 
   void open() {
     assert(isNew());
@@ skipping 93 matching lines @@
     } else {
       successors.add(block);
     }
     block.predecessors.add(this);
   }
 
   void postProcessLoopHeader() {
     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]);
     }
   }
 
   /**
    * Rewrites all uses of the [from] instruction to using the [to]
    * instruction instead.
    */
   void rewrite(HInstruction from, HInstruction to) {
@@ skipping 1066 matching lines @@
   HParameterValue exception;
   HBasicBlock finallyBlock;
   HTry() : super(const <HInstruction>[]);
   toString() => 'try';
   accept(HVisitor visitor) => visitor.visitTry(this);
   HBasicBlock get joinBlock() => this.block.successors.last();
 }
 
 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);
 
   HBasicBlock get thenBlock() {
     assert(block.dominatedBlocks[0] === block.successors[0]);
     return block.successors[0];
   }
 
   HBasicBlock get elseBlock() {
     if (hasElse) {
       assert(block.dominatedBlocks[1] === block.successors[1]);
       return block.successors[1];
     } else {
       return null;
     }
   }
 
-  HBasicBlock get joinBlock() => blockInformation.joinBlock;
+  HBasicBlock get joinBlock() => blockInformation.continuation;
 }
 
 class HLoopBranch extends HConditionalBranch {
   static final int CONDITION_FIRST_LOOP = 0;
   static final int DO_WHILE_LOOP = 1;
 
   final int kind;
   HLoopBranch(HInstruction condition, [this.kind = CONDITION_FIRST_LOOP])
       : super(<HInstruction>[condition]);
   toString() => 'loop-branch';
@@ skipping 468 matching lines @@
     assert(!hasSideEffects());
     setUseGvn();
   }
 
   accept(HVisitor visitor) => visitor.visitTypeConversion(this);
   int typeCode() => 27;
   bool typeEquals(other) => other is HTypeConversion;
   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.

+}
+
+
 /**
- * Information about a syntactic-like structure that can be attached
- * to a [HBasicBlock].
+ * 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.
  */
 interface HBlockInformation {
   HBasicBlock get start();
   HBasicBlock get end();
   bool accept(HBlockInformationVisitor visitor);
 }
 
+
 /**
  * Information about a statement-like structure.
  */
 interface HStatementInformation extends HBlockInformation {
   bool accept(HStatementInformationVisitor visitor);
 }
 
+
 /**
  * Information about an expression-like structure.
  */
 interface HExpressionInformation extends HBlockInformation {
   bool accept(HExpressionInformationVisitor visitor);
   HInstruction get conditionExpression();
 }
 
 
 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.
  */
 class HSubGraphBlockInformation implements HStatementInformation {
   final SubGraph subGraph;
   HSubGraphBlockInformation(this.subGraph);
 
   HBasicBlock get start() => subGraph.start;
   HBasicBlock get end() => subGraph.end;
@@ skipping 14 matching lines @@
   HBasicBlock get start() => subExpression.start;
   HBasicBlock get end() => subExpression.end;
 
   HInstruction get conditionExpression() => subExpression.conditionExpression;
 
   bool accept(HExpressionInformationVisitor visitor) =>
     visitor.visitSubExpressionInfo(this);
 }
 
 
+/** 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>[];
 
   HBasicBlock get start() => body.start;
   HBasicBlock get end() => body.end;
 
   bool accept(HStatementInformationVisitor visitor) =>
     visitor.visitLabeledBlockInfo(this);
 }
 
 class LoopTypeVisitor extends AbstractVisitor {
   const LoopTypeVisitor();
   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 HExpressionInformation initializer;
+  final HExpressionInformation condition;
+  final HStatementInformation body;
+  final HExpressionInformation updates;
+  final TargetElement target;
   final List<LabelElement> labels;
-  final TargetElement target;
-  HExpressionInformation initializer = null;
-  HExpressionInformation condition = null;
-  HStatementInformation body = null;
-  HExpressionInformation updates = null;
-  HBasicBlock joinBlock;
 
-  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;
     if (kind == DO_WHILE_LOOP) {
       return body.start;
     }
     return condition.start;
   }
 
   HBasicBlock get end() {
     if (updates !== null) return updates.end;
     if (kind == DO_WHILE_LOOP) {
       return condition.end;
     }
     return body.end;
   }
 
   static int loopType(Node node) {
     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);
 }
 
 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;
 
   bool accept(HStatementInformationVisitor visitor) =>
     visitor.visitIfInfo(this);
 }
 
 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;
 
   // We don't currently use HAndOrBlockInformation.
   HInstruction get conditionExpression() { unreachable(); }
   bool accept(HExpressionInformationVisitor visitor) =>
     visitor.visitAndOrInfo(this);
 }
 
 class HTryBlockInformation implements HStatementInformation {
   final HStatementInformation body;
   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() =>
       finallyBlock === null ? catchBlock.end : finallyBlock.end;
 
   bool accept(HStatementInformationVisitor visitor) =>
     visitor.visitTryInfo(this);
 }