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

runtime/vm/intermediate_language.h

+// 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_INTERMEDIATE_LANGUAGE_H_
+#define VM_INTERMEDIATE_LANGUAGE_H_
+
+#include "vm/allocation.h"
+#include "vm/growable_array.h"
+
+namespace dart {
+
+class AbstractType;
+class Function;
+class Instance;
+class LocalVariable;
+
+// Computations and values.
+//
+// <Computation> ::= <Value>
+//                 | AssertAssignable <Value> <AbstractType>
+//                 | InstanceCall <cstring> <Value> ...
+//                 | StaticCall <Function> <Value> ...
+//                 | LoadLocal <LocalVariable>
+//                 | StoreLocal <LocalVariable> <Value>
+//
+// <Value> ::= Temp <int>
+//           | Constant <Instance>
+
+class Computation : public ZoneAllocated {
+ public:
+  Computation() { }
+
+  // Prints a computation without indentation or trailing newlines.
+  virtual void Print() const = 0;

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

I would suggest to move printing to a separate class, like AST Printer. 

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

I generally dislike visitors because they don't seem to add much more than
boilerplate and indirection.

I guess it could help here, and we might use it for other things, so I'll take a
stab at it.  Let me save that for another change so this one doesn't get any
bigger.

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

No urgency in that change, especially while the printing is simple.

+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Computation);
+};
+
+
+class Value : public Computation {
+ public:
+  Value() { }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Value);
+};
+
+
+class AssertAssignableComp : public Computation {
+ public:
+  AssertAssignableComp(Value* value, const AbstractType& type)
+      : value_(value), type_(type) { }
+
+  virtual void Print() const;
+
+ private:
+  Value* value_;
+  const AbstractType& type_;
+
+  DISALLOW_COPY_AND_ASSIGN(AssertAssignableComp);
+};
+
+
+class InstanceCallComp : public Computation {
+ public:
+  InstanceCallComp(const char* name, ZoneGrowableArray<Value*>* arguments)
+      : name_(name), arguments_(arguments) { }
+
+  virtual void Print() const;
+
+ private:
+  const char* name_;
+  ZoneGrowableArray<Value*>* arguments_;
+
+  DISALLOW_COPY_AND_ASSIGN(InstanceCallComp);
+};
+
+
+class StaticCallComp : public Computation {
+ public:
+  StaticCallComp(const Function& function, ZoneGrowableArray<Value*>* arguments)
+      : function_(function), arguments_(arguments) { }

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

Add ASSERT(function.IsZoneHandle());

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

OK.  I guess there are more places we will want such asserts?

Or, we can leave them off for things that 'obviously' must come from the AST
(unfortunately it requires including vm/handles_impl.h in this file for
IsZoneHandle and it requires including vm/object.h for the definition of class
Function, and for some reason vm/handles_impl.h needs the definition of class
ObjectVisitor and doesn't have it).

+
+  virtual void Print() const;
+
+ private:
+  const Function& function_;
+  ZoneGrowableArray<Value*>* arguments_;
+
+  DISALLOW_COPY_AND_ASSIGN(StaticCallComp);
+};
+
+
+class LoadLocalComp : public Computation {
+ public:
+  explicit LoadLocalComp(const LocalVariable& local) : local_(local) { }
+
+  virtual void Print() const;
+
+ private:
+  const LocalVariable& local_;
+
+  DISALLOW_COPY_AND_ASSIGN(LoadLocalComp);
+};
+
+
+class StoreLocalComp : public Computation {
+ public:
+  StoreLocalComp(const LocalVariable& local, Value* value)
+      : local_(local), value_(value) { }
+
+  virtual void Print() const;
+
+ private:
+  const LocalVariable& local_;
+  Value* value_;
+
+  DISALLOW_COPY_AND_ASSIGN(StoreLocalComp);
+};
+
+
+class TempValue : public Value {
+ public:
+  explicit TempValue(intptr_t index) : index_(index) { }
+
+  virtual void Print() const;
+
+ private:
+  uintptr_t index_;

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

intptr_t

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

Done.

+
+  DISALLOW_COPY_AND_ASSIGN(TempValue);
+};
+
+
+class ConstantValue: public Value {
+ public:
+  explicit ConstantValue(const Instance& instance) : instance_(instance) { }
+
+  virtual void Print() const;
+
+ private:
+  const Instance& instance_;
+
+  DISALLOW_COPY_AND_ASSIGN(ConstantValue);
+};
+
+
+// Instructions.
+//
+// <Instruction> ::= Do <Computation> <Instruction>
+//                 | Bind <int> <Computation> <Instruction>
+//                 | Return <Value>
+//                 | Branch <Value> <Instruction> <Instruction>
+//                 | Empty <Instruction>
+
+class Instruction : public ZoneAllocated {
+ public:
+  Instruction() : mark_(false) { }
+
+  virtual void set_successor(Instruction* instr) = 0;
+
+  // Perform a postorder traversal of the instruction graph reachable from
+  // this instruction.  Append the result to the end of the in/out parameter
+  // visited.
+  virtual void Postorder(GrowableArray<Instruction*>* visited) = 0;
+
+  // Print an instruction without indentation, instruction number, or a
+  // trailing newline.
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const = 0;
+
+  // Mark bit to support non-reentrant recursive traversal (i.e.,
+  // identification of cycles).  Before and after a traversal, all the nodes
+  // must have the same mark.
+  bool mark() const { return mark_; }
+  void flip_mark() { mark_ = !mark_; }
+
+ protected:
+  // Helper for print handling of successors of nodes with a single successor.
+  // "goto %d" is printed if the successor is not the next instruction.
+  void PrintGotoSuccessor(
+      Instruction* successor,
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  bool mark_;
+};
+
+
+class DoInstr : public Instruction {
+ public:
+  explicit DoInstr(Computation* comp) : computation_(comp), successor_(NULL) { }

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

Must call super constructor Instruction() to initialize mark_ (here and
everywhere below).

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

Done.  Is that a style issue (the superclass constructor will be invoked in any
case)?

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

I find that the explicitness clarifies that the super constructor has also some
work to do.

+
+  virtual void set_successor(Instruction* instr) {
+    ASSERT(successor_ == NULL);
+    successor_ = instr;
+  }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  Computation* computation_;
+  Instruction* successor_;
+};
+
+
+class BindInstr : public Instruction {
+ public:
+  BindInstr(intptr_t temp_index, Computation* computation)
+      : temp_index_(temp_index), computation_(computation), successor_(NULL) { }
+
+  virtual void set_successor(Instruction* instr) {
+    ASSERT(successor_ == NULL);
+    successor_ = instr;
+  }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  intptr_t temp_index_;

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

const

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

Done.

+  Computation* computation_;
+  Instruction* successor_;
+};
+
+
+class JoinEntryInstr : public Instruction {
+ public:
+  JoinEntryInstr() : successor_(NULL) { }
+
+  virtual void set_successor(Instruction* instr) {
+    ASSERT(successor_ == NULL);
+    successor_ = instr;
+  }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  Instruction* successor_;
+};
+
+
+class TargetEntryInstr : public Instruction {
+ public:
+  TargetEntryInstr() : successor_(NULL) { }
+
+  virtual void set_successor(Instruction* instr) {
+    ASSERT(successor_ == NULL);
+    successor_ = instr;
+  }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  Instruction* successor_;
+};
+
+
+class ReturnInstr : public Instruction {
+ public:
+  explicit ReturnInstr(Value* value) : value_(value) { }
+
+  virtual void set_successor(Instruction* instr) { UNREACHABLE(); }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  Value* value_;
+};
+
+
+class BranchInstr : public Instruction {
+ public:
+  explicit BranchInstr(Value* value)
+      : value_(value), true_successor_(NULL), false_successor_(NULL) { }
+
+  virtual void set_successor(Instruction* instr) { UNREACHABLE(); }
+
+  TargetEntryInstr** true_successor_address() { return &true_successor_; }
+  TargetEntryInstr** false_successor_address() { return &false_successor_; }
+
+  virtual void Postorder(GrowableArray<Instruction*>* visited);
+
+  virtual void Print(
+      intptr_t instruction_index,
+      const GrowableArray<Instruction*>& instruction_list) const;
+
+ private:
+  Value* value_;
+  TargetEntryInstr* true_successor_;
+  TargetEntryInstr* false_successor_;
+};
+
+
+}  // namespace dart
+
+#endif  // VM_INTERMEDIATE_LANGUAGE_H_