Introduce Goto instructions to the flow graph.

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 1664 matching lines @@
 
 // Instructions.
 
 // M is a single argument macro.  It is applied to each concrete instruction
 // type name.  The concrete instruction classes are the name with Instr
 // concatenated.
 #define FOR_EACH_INSTRUCTION(M)                                                \
   M(GraphEntry)                                                                \
   M(JoinEntry)                                                                 \
   M(TargetEntry)                                                               \
+  M(Phi)                                                                       \
   M(Bind)                                                                      \
-  M(Phi)                                                                       \
+  M(Parameter)                                                                 \
+  M(ParallelMove)                                                              \
   M(Return)                                                                    \
   M(Throw)                                                                     \
   M(ReThrow)                                                                   \
+  M(Goto)                                                                      \
   M(Branch)                                                                    \
-  M(ParallelMove)                                                              \
-  M(Parameter)
 
 
 // Forward declarations for Instruction classes.
 class BlockEntryInstr;
 class FlowGraphBuilder;
 class Environment;
 
 #define FORWARD_DECLARATION(type) class type##Instr;
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
@@ skipping 51 matching lines @@
     ASSERT(!IsBlockEntry());
     previous_ = instr;
   }
 
   Instruction* next() const { return next_; }
   void set_next(Instruction* instr) {
     ASSERT(!IsGraphEntry());
     ASSERT(!IsReturn());
     ASSERT(!IsBranch());
     ASSERT(!IsPhi());
+    ASSERT(instr == NULL || !instr->IsBlockEntry());
     // TODO(fschneider): Also add Throw and ReThrow to the list of instructions

[srdjan, 2012/07/12 16:42:26]

parenthesis

     // that do not have a successor. Currently, the graph builder will continue
     // to append instruction in case of a Throw inside an expression. This
     // condition should be handled in the graph builder
     next_ = instr;
   }
 
   // Normal instructions can have 0 (inside a block) or 1 (last instruction in
   // a block) successors. Branch instruction with >1 successors override this
   // function.
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
+  void Goto(JoinEntryInstr* entry);
+
   // 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.
   // The array 'assigned_vars' maps preorder block numbers to the set of
   // assigned frame-allocated local variables in the block.  As a side
@@ skipping 58 matching lines @@
   ICData* ic_data_;
   Instruction* previous_;
   Instruction* next_;
   Environment* env_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 class InstructionWithInputs : public Instruction {
  public:
-  InstructionWithInputs() : locs_(NULL) {
-  }
+  InstructionWithInputs() : locs_(NULL) { }
 
   virtual LocationSummary* locs() {
     if (locs_ == NULL) {
       locs_ = MakeLocationSummary();
     }
     return locs_;
   }
 
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
@@ skipping 412 matching lines @@
  private:
   const intptr_t token_pos_;
   const intptr_t try_index_;
   Value* exception_;
   Value* stack_trace_;
 
   DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
 };
 
 
+class GotoInstr : public InstructionWithInputs {

[srdjan, 2012/07/12 16:42:26]

Why is a goto InstructionWithInputs and not just Instruction? Please add
comment.

[Kevin Millikin (Google), 2012/07/13 15:34:59]

Well, it's an instruction with inputs that happens to have zero of them :)

InstructionWithInputs seems like the wrong name or else the wrong abstraction. 
There's a handful of virtual functions related to the register allocator and
code generator (already, and there will probably become more) that assume that
they will only be called on InstructionWithInputs.  

*Avoiding* to call them requires checking the instruction type in the driver
loop (with a virtual method) rather than just making the virtual method safe to
call in the first place.

I'll add a comment, but it still needs more some cleanup.

+ public:
+  explicit GotoInstr(JoinEntryInstr* entry) : successor_(entry) { }
+
+  DECLARE_INSTRUCTION(Goto)
+
+  JoinEntryInstr* successor() const { return successor_; }
+  void set_successor(JoinEntryInstr* successor) { successor_ = successor; }
+  virtual intptr_t SuccessorCount() const;
+  virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
+
+  virtual LocationSummary* MakeLocationSummary() const;
+
+  virtual void EmitNativeCode(FlowGraphCompiler* compiler);
+
+ private:
+  JoinEntryInstr* successor_;

[srdjan, 2012/07/12 16:42:26]

DISALLOW_...

+};
+
+
 class BranchInstr : public InstructionWithInputs {
  public:
   explicit BranchInstr(Value* value)
       : InstructionWithInputs(),
         value_(value),
         true_successor_(NULL),
         false_successor_(NULL),
         fused_with_comparison_(NULL),
         is_negated_(false) { }
 
@@ skipping 185 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_