Make the CFG depth-first traversal do more work for us.

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 785 matching lines @@
 
   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 DepthFirstSearch(
+
+  // Discover basic-block structure by performing a recursive depth first
+  // traversal of the instruction graph reachable from this instruction.  As
+  // a side effect, the block entry instructions in the graph are assigned
+  // numbers in both preorder and postorder.  The array 'preorder' maps
+  // preorder block numbers to the block entry instruction with that number
+  // and analogously for the array 'postorder'.  The depth first spanning
+  // tree is recorded in the array 'parent', which maps preorder block
+  // numbers to the preorder number of the block's spanning-tree parent.  As
+  // a side effect, the set of basic block predecessors (e.g., block entry
+  // instructions of predecessor blocks) and also the last instruction in
+  // the block is recorded in each entry instruction.
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder) = 0;
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent) = 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:
   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 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; }
 
+  Instruction* last_instruction() const { return last_instruction_; }
+  void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
+
  protected:
-  BlockEntryInstr() : preorder_number_(-1), postorder_number_(-1) { }
+  BlockEntryInstr()
+      : preorder_number_(-1),
+        postorder_number_(-1),
+        last_instruction_(NULL) { }
 
  private:
   intptr_t preorder_number_;
   intptr_t postorder_number_;
+  Instruction* last_instruction_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
-  JoinEntryInstr() : BlockEntryInstr(), successor_(NULL) { }
+  JoinEntryInstr()
+      : BlockEntryInstr(),
+        predecessors_(2),  // Two is the assumed to be the common case.
+        successor_(NULL) { }
 
   DECLARE_INSTRUCTION(JoinEntry)
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  private:
+  ZoneGrowableArray<BlockEntryInstr*> predecessors_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
-  TargetEntryInstr() : BlockEntryInstr(), successor_(NULL) {
-  }
+  TargetEntryInstr()
+      : BlockEntryInstr(), predecessor_(NULL), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(TargetEntry)
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  private:
+  BlockEntryInstr* predecessor_;

[srdjan, 2012/03/19 18:43:35]

It is not publicly accessible, what is its use? Future use? Add getter? Ditto
for JoinEntryInstr.

[Kevin Millikin (Google), 2012/03/19 18:53:55]

The dominator computation needs to iterate predecessors.

Let me leave it private for now with no accessor.  We might expose an accessor,
but what we really want is some kind of iterator interface, because we don't
want to have to distinguish between Target and Join in most cases just to
iterate the predecessors.

   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)
       : 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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  private:
   const intptr_t destination_;
   const intptr_t source_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(PickTempInstr);
 };
 
 
@@ skipping 14 matching lines @@
   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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  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)
       : computation_(comp), successor_(NULL) { }
 
   DECLARE_INSTRUCTION(Do)
 
   Computation* computation() const { return computation_; }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
 class BindInstr : public Instruction {
  public:
   BindInstr(intptr_t temp_index, Computation* computation)
       : 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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  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)
       : 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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  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)
       : 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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  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 DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  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)
       : value_(value),
         true_successor_(NULL),
         false_successor_(NULL) { }
 
   DECLARE_INSTRUCTION(Branch)
 
   Value* value() const { return value_; }
   TargetEntryInstr* true_successor() const { return true_successor_; }
   TargetEntryInstr* false_successor() const { return false_successor_; }
 
   TargetEntryInstr** true_successor_address() { return &true_successor_; }
   TargetEntryInstr** false_successor_address() { return &false_successor_; }
 
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
-  virtual void DepthFirstSearch(
+  virtual void DiscoverBlocks(
+      BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder);
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<BlockEntryInstr*>* parent);
 
  private:
   Value* value_;
   TargetEntryInstr* true_successor_;
   TargetEntryInstr* false_successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
 
 #undef DECLARE_INSTRUCTION
@@ skipping 36 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_