Compute preorder as well as postorder basic block orderings.

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/ast.h"
 #include "vm/growable_array.h"
@@ skipping 774 matching lines @@
 
 // Functions required in all concrete instruction classes.
 #define DECLARE_INSTRUCTION(type)                                              \
   virtual Instruction* Accept(FlowGraphVisitor* visitor);                      \
   virtual bool Is##type() const { return true; }                               \
   virtual type##Instr* As##type() { return this; }                             \
 
 
 class Instruction : public ZoneAllocated {
  public:
-  Instruction() : mark_(false) { }
+  Instruction() { }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
     return IsBlockEntry() ? reinterpret_cast<BlockEntryInstr*>(this) : NULL;
   }
 
   // Visiting support.
   virtual Instruction* Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual void SetSuccessor(Instruction* instr) = 0;
   // Perform a postorder traversal of the instruction graph reachable from
   // this instruction.  Accumulate basic block entries in the order visited
   // in the in/out parameter 'block_entries'.
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries) = 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_; }
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder) = 0;
 
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   virtual bool Is##type() const { return false; }                              \
   virtual type##Instr* As##type() { return NULL; }
 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
  private:
-  bool mark_;
-
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 // Basic block entries are administrative nodes.  Joins are the only nodes
 // with multiple predecessors.  Targets are the other basic block entries.
 // The types enforce edge-split form---joins are forbidden as the successors
 // of branches.
 class BlockEntryInstr : public Instruction {
  public:
   virtual bool IsBlockEntry() const { return true; }
 
-  intptr_t block_number() const { return block_number_; }
-  void set_block_number(intptr_t number) { block_number_ = number; }
+  intptr_t preorder_number() const { return preorder_number_; }
+  void set_preorder_number(intptr_t number) { preorder_number_ = number; }
+
+  intptr_t postorder_number() const { return postorder_number_; }
+  void set_postorder_number(intptr_t number) { postorder_number_ = number; }
 
  protected:
-  BlockEntryInstr() : Instruction(), block_number_(-1) { }
+  BlockEntryInstr() : preorder_number_(-1), postorder_number_(-1) { }
 
  private:
-  intptr_t block_number_;
+  intptr_t preorder_number_;
+  intptr_t postorder_number_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
   JoinEntryInstr() : BlockEntryInstr(), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(JoinEntry)
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
   TargetEntryInstr() : BlockEntryInstr(), successor_(NULL) {
   }
 
   DECLARE_INSTRUCTION(TargetEntry)
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 // The non-optimizing compiler assumes that there is exactly one use of
 // every temporary so they can be deallocated at their use.  Some AST nodes,
 // e.g., expr0[expr1]++, violate this assumption (there are two uses of each
 // of the values expr0 and expr1).
 //
 // PickTemp is used to name (with 'destination') a copy of a live temporary
 // (named 'source') without counting as the use of the source.
 class PickTempInstr : public Instruction {
  public:
   PickTempInstr(intptr_t dst, intptr_t src)
-      : Instruction(), destination_(dst), source_(src), successor_(NULL) { }
+      : destination_(dst), source_(src), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(PickTemp)
 
   intptr_t destination() const { return destination_; }
   intptr_t source() const { return source_; }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL && instr != NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   const intptr_t destination_;
   const intptr_t source_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(PickTempInstr);
 };
 
 
 // The non-optimizing compiler assumes that temporary definitions and uses
 // obey a stack discipline, so they can be allocated and deallocated with
 // push and pop.  Some Some AST nodes, e.g., expr++, violate this assumption
 // (the value expr+1 is produced after the value of expr, and also consumed
 // after it).
 //
 // We 'preallocate' temporaries (named with 'destination') such as the one
 // for expr+1 and use TuckTemp to mutate them by overwriting them with a
 // copy of a temporary (named with 'source').
 class TuckTempInstr : public Instruction {
  public:
   TuckTempInstr(intptr_t dst, intptr_t src)
-      : Instruction(), destination_(dst), source_(src), successor_(NULL) { }
+      : destination_(dst), source_(src), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(TuckTemp)
 
   intptr_t destination() const { return destination_; }
   intptr_t source() const { return source_; }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL && instr != NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   const intptr_t destination_;
   const intptr_t source_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(TuckTempInstr);
 };
 
 
 class DoInstr : public Instruction {
  public:
   explicit DoInstr(Computation* comp)
-      : Instruction(), computation_(comp), successor_(NULL) { }
+      : computation_(comp), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(Do)
 
   Computation* computation() const { return computation_; }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
 class BindInstr : public Instruction {
  public:
   BindInstr(intptr_t temp_index, Computation* computation)
-      : Instruction(),
-        temp_index_(temp_index),
-        computation_(computation),
-        successor_(NULL) { }
+      : temp_index_(temp_index), computation_(computation), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(Bind)
 
   intptr_t temp_index() const { return temp_index_; }
   Computation* computation() const { return computation_; }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   const intptr_t temp_index_;
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class ReturnInstr : public Instruction {
  public:
   ReturnInstr(Value* value, intptr_t token_index)
-      : Instruction(), value_(value), token_index_(token_index) {
+      : value_(value), token_index_(token_index) {
     ASSERT(value_ != NULL);
   }
 
   DECLARE_INSTRUCTION(Return)
 
   Value* value() const { return value_; }
   intptr_t token_index() const { return token_index_; }
 
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   Value* value_;
   intptr_t token_index_;
 
   DISALLOW_COPY_AND_ASSIGN(ReturnInstr);
 };
 
 
 class ThrowInstr : public Instruction {
  public:
   ThrowInstr(intptr_t node_id, intptr_t token_index, Value* exception)
-      : Instruction(),
-        node_id_(node_id),
-        token_index_(token_index),
-        exception_(exception) {
+      : node_id_(node_id), token_index_(token_index), exception_(exception) {
     ASSERT(exception_ != NULL);
   }
 
   DECLARE_INSTRUCTION(Throw)
 
   intptr_t node_id() const { return node_id_; }
   intptr_t token_index() const { return token_index_; }
   Value* exception() const { return exception_; }
 
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   intptr_t node_id_;
   intptr_t token_index_;
   Value* exception_;
 
   DISALLOW_COPY_AND_ASSIGN(ThrowInstr);
 };
 
 
@@ skipping 13 matching lines @@
 
   DECLARE_INSTRUCTION(ReThrow)
 
   intptr_t node_id() const { return node_id_; }
   intptr_t token_index() const { return token_index_; }
   Value* exception() const { return exception_; }
   Value* stack_trace() const { return stack_trace_; }
 
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   intptr_t node_id_;
   intptr_t token_index_;
   Value* exception_;
   Value* stack_trace_;
 
   DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
 };
 
 
 class BranchInstr : public Instruction {
  public:
   explicit BranchInstr(Value* value)
-      : Instruction(),
-        value_(value),
+      : value_(value),
         true_successor_(NULL),
         false_successor_(NULL) { }
 
   DECLARE_INSTRUCTION(Branch)
 
   Value* value() const { return value_; }
   BlockEntryInstr* true_successor() const { return true_successor_; }
   BlockEntryInstr* false_successor() const { return false_successor_; }
 
   BlockEntryInstr** true_successor_address() { return &true_successor_; }
   BlockEntryInstr** false_successor_address() { return &false_successor_; }
 
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
-  virtual void Postorder(GrowableArray<BlockEntryInstr*>* block_entries);
+  virtual void DepthFirstSearch(
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder);
 
  private:
   Value* value_;
   BlockEntryInstr* true_successor_;
   BlockEntryInstr* false_successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
 
 #undef DECLARE_INSTRUCTION
 
 
 // Visitor base class to visit each instruction and computation in a flow
 // graph as defined by a reversed list of basic blocks.
 class FlowGraphVisitor : public ValueObject {
  public:
-  FlowGraphVisitor() { }
+  explicit FlowGraphVisitor(const GrowableArray<BlockEntryInstr*>& block_order)
+      : block_order_(block_order) { }
   virtual ~FlowGraphVisitor() { }
 
-  // Visit each block in the array list in reverse, and for each block its
+  // Visit each block in the block order, and for each block its
   // instructions in order from the block entry to exit.
-  virtual void VisitBlocks(const GrowableArray<BlockEntryInstr*>& block_order);
+  virtual void VisitBlocks();
 
   // Visit functions for instruction and computation classes, with empty
   // default implementations.
 #define DECLARE_VISIT_COMPUTATION(ShortName, ClassName)                        \
   virtual void Visit##ShortName(ClassName* comp) { }
 
 #define DECLARE_VISIT_INSTRUCTION(ShortName)                                   \
   virtual void Visit##ShortName(ShortName##Instr* instr) { }
 
   FOR_EACH_COMPUTATION(DECLARE_VISIT_COMPUTATION)
   FOR_EACH_INSTRUCTION(DECLARE_VISIT_INSTRUCTION)
 
 #undef DECLARE_VISIT_COMPUTATION
 #undef DECLARE_VISIT_INSTRUCTION
 
+ protected:
+  // Map a block number in a forward iteration into the block number in the
+  // corresponding reverse iteration.  Used to obtain an index into
+  // block_order for reverse iterations.
+  intptr_t reverse_index(intptr_t index) {
+    return block_order_.length() - index - 1;
+  }
+
+  const GrowableArray<BlockEntryInstr*>& block_order_;
+
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_