Initial implementation of a flow-graph builder for Dart's AST.

runtime/vm/flow_graph_builder.h

Index: runtime/vm/flow_graph_builder.h
diff --git a/runtime/vm/flow_graph_builder.h b/runtime/vm/flow_graph_builder.h
new file mode 100644
index 0000000000000000000000000000000000000000..e341c09e594978c656b813830e3e16e20878b7f3
--- /dev/null
+++ b/runtime/vm/flow_graph_builder.h
@@ -0,0 +1,212 @@
+// 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.
+
+#ifndef VM_FLOW_GRAPH_BUILDER_H_
+#define VM_FLOW_GRAPH_BUILDER_H_
+
+#include "vm/allocation.h"
+#include "vm/ast.h"
+#include "vm/growable_array.h"
+#include "vm/intermediate_language.h"
+
+namespace dart {
+
+class Instruction;
+class ParsedFunction;
+
+class FlowGraphBuilder: public ValueObject {

[srdjan, 2012/02/22 00:41:34]

Please add a comment description to this class.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Done.

+ public:
+  explicit FlowGraphBuilder(const ParsedFunction& parsed_function)
+      : parsed_function_(parsed_function), bailout_reason_(NULL) { }

[srdjan, 2012/02/21 14:33:41]

We like to list/initialize all instance fields in initializer list, i.e., please
add postorder_() to the list.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Done.

+
+  void BuildGraph();
+
+  const ParsedFunction& parsed_function() const { return parsed_function_; }
+
+  void Bailout(const char* reason) { bailout_reason_ = reason; }

[srdjan, 2012/02/22 00:41:34]

ASSERT(bailout_reason_ == NULL), otherwise the bailout reason may be lost.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Done.

+  void TraceBailout() const;
+  void PrintGraph() const;
+
+ private:
+  const ParsedFunction& parsed_function_;
+  const char* bailout_reason_;
+  GrowableArray<Instruction*> postorder_;
+};
+
+
+#define DEFINE_VISIT(type, name) virtual void Visit##type(type* node);
+
+class TestGraphVisitor;

[srdjan, 2012/02/22 00:41:34]

Comment: Class name TestGraphVisitor sounds like a class that (unit) tests
GraphVisitor. No better name comes to my mind.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

I agree, but it's nice and short.  Alternatives are ControlVisitor (which sounds
like it controls a visitor) and ConditionVisitor (which is just a bit long for
my taste).

[srdjan, 2012/02/22 14:08:16]

? 
TestGraphVisitor and ConditionVisitor are longest, ControlVisitor is the
shortest.  Your call, I am fine with any of the three names.

+
+// Translate an AstNode to a control-flow graph fragment for its effects
+// (e.g., a statement or an expression in an effect context).  Implements a
+// function from an AstNode and next temporary index to a graph fragment
+// with a single entry and at most one exit.  The fragment is represented by
+// an (entry, exit) pair of Instruction pointers:
+//
+//   - (NULL, NULL): an empty graph fragment

[srdjan, 2012/02/21 14:33:41]

an empty and open graph fragment.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Done.

+//   - (i0, NULL): a closed graph fragment which has only non-local exits
+//   - (i0, i1): an open graph fragment
+class EffectGraphVisitor : public AstNodeVisitor {
+ public:
+  EffectGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index)
+      : owner_(owner),
+        temp_index_(temp_index),
+        entry_(NULL),
+        exit_(NULL),
+        bailing_out_(false) { }
+
+  NODE_LIST(DEFINE_VISIT)
+
+  FlowGraphBuilder* owner() const { return owner_; }
+  intptr_t temp_index() const { return temp_index_; }
+  Instruction* entry() const { return entry_; }
+  Instruction* exit() const { return exit_; }
+
+  bool is_empty() const { return entry_ == NULL; }
+  bool is_open() const { return is_empty() || exit_ != NULL; }
+
+  void Bailout(const char* reason);
+
+  // Append a graph fragment to this graph.  Assumes this graph is open.
+  void Append(const EffectGraphVisitor& other_fragment);
+  // Append a single instruction.  Assumes this graph is open.
+  void AddInstruction(Instruction* instruction);
+
+  // Append a 'diamond' branch and join to this graph, depending on which
+  // parts are reachable.  Assumes this graph is open.
+  void Join(const TestGraphVisitor& test_fragment,
+            const EffectGraphVisitor& true_fragment,
+            const EffectGraphVisitor& false_fragment);
+
+  // Append a 'while loop' test and back edge to this graph, depending on
+  // which parts are reachable.  Afterward, the graph exit is the false
+  // successor of the loop condition.
+  void TieLoop(const TestGraphVisitor& test_fragment,
+               const EffectGraphVisitor& body_fragment);
+
+ protected:
+  bool bailing_out() const { return bailing_out_; }
+
+  // Implement the core part of the translation of expression node types.
+  AssertAssignableComp* TranslateAssignable(AssignableNode* node);

[srdjan, 2012/02/21 14:33:41]

The node parameter in TranslateXXX could it be a const reference node?

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Yup.  Done.  I think it looks strange to dereference it at the call site, so we
could also make it a pointer to const node.

[srdjan, 2012/02/22 14:08:16]

By passing a reference you guarantee that the value is not NULL, thus less
checks/failures can occur in callee. Dereference at call site makes it clear (at
call site) that it may not be NULL.

+  InstanceCallComp* TranslateBinaryOp(BinaryOpNode* node);
+  InstanceCallComp* TranslateComparison(ComparisonNode* node);
+  StoreLocalComp* TranslateStoreLocal(StoreLocalNode* node);
+  StaticCallComp* TranslateStaticCall(StaticCallNode* node);
+
+  void CloseFragment() { exit_ = NULL; }
+  intptr_t AllocateTempIndex() { return temp_index_++; }
+
+ private:
+  // Helper to append a Do instruction to the graph.
+  void DoComputation(Computation* computation) {
+    AddInstruction(new DoInstr(computation));
+  }
+
+  // Shared global state.
+  FlowGraphBuilder* owner_;
+
+  // Input parameters.
+  intptr_t temp_index_;
+
+  // Output parameters.
+  Instruction* entry_;
+  Instruction* exit_;
+
+  // Local state.
+  bool bailing_out_;
+};
+
+
+// Translate an AstNode to a control-flow graph fragment for both its effects
+// and value (e.g., for an expression in a value context).  Implements a
+// function from an AstNode and next temporary index to a graph fragment (as
+// in the EffectGraphVisitor), a next temporary index, and a intermediate

[srdjan, 2012/02/21 14:33:41]

"an intermediate"

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Done.

+// language Value.
+class ValueGraphVisitor : public EffectGraphVisitor {
+ public:
+  ValueGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index)
+      : EffectGraphVisitor(owner, temp_index), value_(NULL) { }
+
+  NODE_LIST(DEFINE_VISIT)
+
+  Value* value() const { return value_; }
+
+ private:
+  // Helper to set the output state to return a Value.
+  void ReturnValue(Value* value) { value_ = value; }
+
+  // Helper to append a Bind instruction to the graph and return its
+  // temporary value (i.e., set the output parameters).
+  void ReturnValueOf(Computation* computation) {
+    AddInstruction(new BindInstr(temp_index(), computation));
+    value_ = new TempValue(AllocateTempIndex());
+  }
+
+  // Output parameters.
+  Value* value_;
+};
+
+
+// Translate an AstNode to a control-flow graph fragment for both its
+// effects and true/false control flow (e.g., for an expression in a test
+// context).  The resulting graph is always closed (even if it is empty)
+// Successor control flow is explicitly set by a pair of pointers to
+// TargetEntryInstr*.
+//
+// To distinguish between the graphs with only nonlocal exits, graphs that
+// are unconditionally true or else unconditionally false, and graphs with
+// both true and false exits, there are a pair of TargetEntryInstr**:
+//
+//   - Both NULL: only non-local exits, truly closed
+//   - One NULL: unconditionally true or else unconditionally false
+//   - Neither NULL: true and false successors at the given addresses
+class TestGraphVisitor : public EffectGraphVisitor {
+ public:
+  TestGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index)
+      : EffectGraphVisitor(owner, temp_index),
+        true_successor_address_(NULL),
+        false_successor_address_(NULL) {

[srdjan, 2012/02/21 14:33:41]

You need to initialize is_true_. Actually, I do not think that you are using it
at all, so you can remove it.

[Kevin Millikin (Google), 2012/02/22 13:15:42]

Yeah, that's a leftover.  Thanks for spotting it.

+  }
+
+  NODE_LIST(DEFINE_VISIT)
+
+  bool can_be_true() const {
+    return true_successor_address_ != NULL;
+  }
+  bool can_be_false() const {
+    return false_successor_address_ != NULL;
+  }
+

[srdjan, 2012/02/21 14:33:41]

As mentioned, please remove can_be_true and can_be false logic

+  TargetEntryInstr** true_successor_address() const {
+    return true_successor_address_;
+  }
+  TargetEntryInstr** false_successor_address() const {
+    return false_successor_address_;
+  }
+
+ private:
+  // Construct and concatenate a Branch instruction to this graph fragment.
+  // Closes the fragment and sets the output parameters.
+  void BranchOnValue(Value* value);
+
+  // Helper to bind a computation and branch on its value.
+  void BranchOnValueOf(Computation* computation) {
+    AddInstruction(new BindInstr(temp_index(), computation));
+    BranchOnValue(new TempValue(temp_index()));
+  }
+
+  // Output parameters.
+  bool is_true_;
+  TargetEntryInstr** true_successor_address_;
+  TargetEntryInstr** false_successor_address_;
+};
+
+#undef DEFINE_VISIT
+
+
+}  // namespace dart
+
+#endif  // VM_FLOW_GRAPH_BUILDER_H_