Make IL instructions a doubly-linked list within basic blocks.

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 310 matching lines @@
 class Definition;
 class BindInstr;
 class PhiInstr;
 
 class UseVal : public Value {
  public:
   explicit UseVal(Definition* definition) : definition_(definition) {}
 
   DECLARE_VALUE(Use)
 
-  Definition* definition() const { return definition_; }
+  inline Definition* definition() const;
   void set_definition(Definition* definition) {
     definition_ = definition;
   }
 
  private:
   Definition* definition_;
 
   DISALLOW_COPY_AND_ASSIGN(UseVal);
 };
 
@@ skipping 1385 matching lines @@
   virtual intptr_t InputCount() const;                                         \
   virtual Value* InputAt(intptr_t i) const;                                    \
   virtual void SetInputAt(intptr_t i, Value* value);                           \
   virtual const char* DebugName() const { return #type; }                      \
   virtual void PrintTo(BufferFormatter* f) const;                              \
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
 
 class Instruction : public ZoneAllocated {
  public:
-  Instruction() : cid_(-1), ic_data_(NULL) {
+  Instruction() : cid_(-1), ic_data_(NULL), successor_(NULL), previous_(NULL) {
     Isolate* isolate = Isolate::Current();
     cid_ = Computation::GetNextCid(isolate);
     ic_data_ = Computation::GetICDataForCid(cid_, isolate);
   }
 
   // Unique computation/instruction id, used for deoptimization, e.g. for
   // ReturnInstr, ThrowInstr and ReThrowInstr.
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
     return IsBlockEntry() ? reinterpret_cast<BlockEntryInstr*>(this) : NULL;
   }
   virtual bool IsDefinition() const { return false; }
   virtual Definition* AsDefinition() { return NULL; }
 
   virtual intptr_t InputCount() const = 0;
   virtual Value* InputAt(intptr_t i) const = 0;
   virtual void SetInputAt(intptr_t i, Value* value) = 0;
 
   // Visiting support.
   virtual Instruction* Accept(FlowGraphVisitor* visitor) = 0;
 
-  virtual Instruction* StraightLineSuccessor() const = 0;
-  virtual void SetSuccessor(Instruction* instr) = 0;
+  Instruction* successor() const { return successor_; }
+  void set_successor(Instruction* instr) {
+    ASSERT(!IsGraphEntry());
+    ASSERT(!IsReturn());
+    ASSERT(!IsBranch());
+    ASSERT(!IsPhi());
+    // TODO(fschneider): Also add Throw and ReThrow to the list of instructions
+    // 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
+    successor_ = instr;
+  }
+
+  Instruction* previous() const { return previous_; }
+  void set_previous(Instruction* instr) {
+    ASSERT(!IsBlockEntry());
+    previous_ = instr;
+  }
+
+  bool is_linked() const;
+
+  // Remove instruction from the graph.
+  void RemoveFromGraph();
 
   // 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;
 
   virtual void replace_computation(Computation* value) {
     UNREACHABLE();
   }
@@ skipping 50 matching lines @@
     return NULL;
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) {
     UNIMPLEMENTED();
   }
 
  private:
   intptr_t cid_;
   ICData* ic_data_;
+  Instruction* successor_;
+  Instruction* previous_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 class InstructionWithInputs : public Instruction {
  public:
   InstructionWithInputs() : locs_(NULL) {
   }
 
   virtual LocationSummary* locs() {
@@ skipping 88 matching lines @@
 
   DECLARE_INSTRUCTION(GraphEntry)
 
   virtual intptr_t PredecessorCount() const { return 0; }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     UNREACHABLE();
     return NULL;
   }
   virtual void AddPredecessor(BlockEntryInstr* predecessor) { UNREACHABLE(); }
 
-  virtual Instruction* StraightLineSuccessor() const { return NULL; }
-  virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
-
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
       GrowableArray<intptr_t>* parent,
       GrowableArray<BitVector*>* assigned_vars,
       intptr_t variable_count);
@@ skipping 12 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
   JoinEntryInstr()
       : BlockEntryInstr(),
         predecessors_(2),  // Two is the assumed to be the common case.
-        successor_(NULL),
         phis_(NULL),
         phi_count_(0) { }
 
   DECLARE_INSTRUCTION(JoinEntry)
 
   virtual intptr_t PredecessorCount() const { return predecessors_.length(); }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     return predecessors_[index];
   }
   virtual void AddPredecessor(BlockEntryInstr* predecessor) {
     predecessors_.Add(predecessor);
   }
 
-  virtual Instruction* StraightLineSuccessor() const {
-    return successor_;
-  }
-  virtual void SetSuccessor(Instruction* instr) {
-    successor_ = instr;
-  }
-
   ZoneGrowableArray<PhiInstr*>* phis() const { return phis_; }
 
   virtual void PrepareEntry(FlowGraphCompiler* compiler);
 
   void InsertPhi(intptr_t var_index, intptr_t var_count);
 
   intptr_t phi_count() const { return phi_count_; }
 
  private:
   ZoneGrowableArray<BlockEntryInstr*> predecessors_;
-  Instruction* successor_;
   ZoneGrowableArray<PhiInstr*>* phis_;
   intptr_t phi_count_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
   TargetEntryInstr()
       : BlockEntryInstr(),
         predecessor_(NULL),
-        successor_(NULL),
         try_index_(CatchClauseNode::kInvalidTryIndex) { }
 
   // Used for exception catch entries.
   explicit TargetEntryInstr(intptr_t try_index)
       : BlockEntryInstr(),
         predecessor_(NULL),
-        successor_(NULL),
         try_index_(try_index) { }
 
   DECLARE_INSTRUCTION(TargetEntry)
 
   virtual intptr_t PredecessorCount() const {
     return (predecessor_ == NULL) ? 0 : 1;
   }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     ASSERT((index == 0) && (predecessor_ != NULL));
     return predecessor_;
   }
   virtual void AddPredecessor(BlockEntryInstr* predecessor) {
     ASSERT(predecessor_ == NULL);
     predecessor_ = predecessor;
   }
 
-  virtual Instruction* StraightLineSuccessor() const {
-    return successor_;
-  }
-  virtual void SetSuccessor(Instruction* instr) {
-    successor_ = instr;
-  }
-
   bool HasTryIndex() const {
     return try_index_ != CatchClauseNode::kInvalidTryIndex;
   }
 
   intptr_t try_index() const {
     ASSERT(HasTryIndex());
     return try_index_;
   }
 
   virtual void PrepareEntry(FlowGraphCompiler* compiler);
 
  private:
   BlockEntryInstr* predecessor_;
-  Instruction* successor_;
   const intptr_t try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 class DoInstr : public Instruction {
  public:
   explicit DoInstr(Computation* computation)
-      : computation_(computation), successor_(NULL) {
+      : computation_(computation) {
     ASSERT(computation != NULL);
     computation->set_instr(this);
   }
 
   DECLARE_INSTRUCTION(Do)
 
   Computation* computation() const { return computation_; }
   virtual void replace_computation(Computation* value) { computation_ = value; }
 
-  virtual Instruction* StraightLineSuccessor() const {
-    return successor_;
-  }
-
-  virtual void SetSuccessor(Instruction* instr) {
-    successor_ = instr;
-  }
-
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) {
     computation()->EmitNativeCode(compiler);
   }
 
  private:
   Computation* computation_;
-  Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
 // Abstract super-class of all instructions that define a value (Bind, Phi).
 class Definition : public Instruction {
  public:
   Definition() : temp_index_(-1), ssa_temp_index_(-1) { }
 
   virtual bool IsDefinition() const { return true; }
   virtual Definition* AsDefinition() { return this; }
 
   intptr_t temp_index() const { return temp_index_; }
   void set_temp_index(intptr_t index) { temp_index_ = index; }
 
   intptr_t ssa_temp_index() const { return ssa_temp_index_; }
   void set_ssa_temp_index(intptr_t index) { ssa_temp_index_ = index; }
 
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
 
   DISALLOW_COPY_AND_ASSIGN(Definition);
 };
 
 
+Definition* UseVal::definition() const {
+  // Check that the definition is either a Phi or a linked in the the IR.
+  ASSERT(definition_ != NULL);
+  ASSERT(!definition_->IsPhi() || definition_->is_linked());
+  return definition_;
+}
+
+
 class BindInstr : public Definition {
  public:
   explicit BindInstr(Computation* computation)
-      : computation_(computation), successor_(NULL) {
+      : computation_(computation) {
     ASSERT(computation != NULL);
     computation->set_instr(this);
   }
 
   DECLARE_INSTRUCTION(Bind)
 
   Computation* computation() const { return computation_; }
   virtual void replace_computation(Computation* value) { computation_ = value; }
 
-  virtual Instruction* StraightLineSuccessor() const {
-    return successor_;
-  }
-
-  virtual void SetSuccessor(Instruction* instr) {
-    successor_ = instr;
-  }
-
   // Static type of the underlying computation.
   virtual RawAbstractType* StaticType() const {
     return computation()->StaticType();
   }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
   Computation* computation_;
-  Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class PhiInstr: public Definition {
  public:
   explicit PhiInstr(intptr_t num_inputs) : inputs_(num_inputs) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
   }
 
   DECLARE_INSTRUCTION(Phi)
 
-  virtual Instruction* StraightLineSuccessor() const { return NULL; }
-  virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
-
  private:
   GrowableArray<Value*> inputs_;
 
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ReturnInstr : public InstructionWithInputs {
  public:
   ReturnInstr(intptr_t token_pos, Value* value)
       : InstructionWithInputs(), token_pos_(token_pos), value_(value) {
     ASSERT(value_ != NULL);
   }
 
   DECLARE_INSTRUCTION(Return)
 
   Value* value() const { return value_; }
   intptr_t token_pos() const { return token_pos_; }
 
-  virtual Instruction* StraightLineSuccessor() const { return NULL; }
-  virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
-
   virtual LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
   const intptr_t token_pos_;
   Value* value_;
 
   DISALLOW_COPY_AND_ASSIGN(ReturnInstr);
 };
 
 
 class ThrowInstr : public InstructionWithInputs {
  public:
   ThrowInstr(intptr_t token_pos,
              intptr_t try_index,
              Value* exception)
       : InstructionWithInputs(),
         token_pos_(token_pos),
         try_index_(try_index),
-        exception_(exception),
-        successor_(NULL) {
+        exception_(exception) {
     ASSERT(exception_ != NULL);
   }
 
   DECLARE_INSTRUCTION(Throw)
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
   Value* exception() const { return exception_; }
 
-  // Parser can generate a throw within an expression tree.  We never
-  // add successor instructions to the graph.
-  virtual Instruction* StraightLineSuccessor() const { return NULL; }
-  virtual void SetSuccessor(Instruction* instr) {
-    ASSERT(successor_ == NULL);
-  }
-
   virtual LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
   const intptr_t token_pos_;
   const intptr_t try_index_;
   Value* exception_;
-  Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(ThrowInstr);
 };
 
 
 class ReThrowInstr : public InstructionWithInputs {
  public:
   ReThrowInstr(intptr_t token_pos,
                intptr_t try_index,
                Value* exception,
                Value* stack_trace)
       : InstructionWithInputs(),
         token_pos_(token_pos),
         try_index_(try_index),
         exception_(exception),
-        stack_trace_(stack_trace),
-        successor_(NULL) {
+        stack_trace_(stack_trace) {
     ASSERT(exception_ != NULL);
     ASSERT(stack_trace_ != NULL);
   }
 
   DECLARE_INSTRUCTION(ReThrow)
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
   Value* exception() const { return exception_; }
   Value* stack_trace() const { return stack_trace_; }
 
-  // Parser can generate a rethrow within an expression tree.  We
-  // never add successor instructions to the graph.
-  virtual Instruction* StraightLineSuccessor() const {
-    return NULL;
-  }
-  virtual void SetSuccessor(Instruction* instr) {
-    ASSERT(successor_ == NULL);
-  }
-
   virtual LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
   const intptr_t token_pos_;
   const intptr_t try_index_;
   Value* exception_;
   Value* stack_trace_;
-  Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(ReThrowInstr);
 };
 
 
 class BranchInstr : public InstructionWithInputs {
  public:
   explicit BranchInstr(Value* value)
       : InstructionWithInputs(),
         value_(value),
         true_successor_(NULL),
         false_successor_(NULL),
         is_fused_with_comparison_(false),
         is_negated_(false) { }
 
   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 Instruction* StraightLineSuccessor() const { return NULL; }
-  virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
-
   virtual intptr_t SuccessorCount() const;
   virtual BlockEntryInstr* SuccessorAt(intptr_t index) const;
 
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
       GrowableArray<intptr_t>* parent,
       GrowableArray<BitVector*>* assigned_vars,
       intptr_t variable_count);
@@ skipping 88 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_