A simpler scheme for garbage collection of ureachable phi inputs.

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 637 matching lines @@
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const = 0;
   virtual void PrepareEntry(FlowGraphCompiler* compiler) = 0;
 
   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; }
 
   intptr_t block_id() const { return block_id_; }
-  void set_block_id(intptr_t value) { block_id_ = value; }
 
   void set_start_pos(intptr_t pos) { start_pos_ = pos; }
   intptr_t start_pos() const { return start_pos_; }
   void  set_end_pos(intptr_t pos) { end_pos_ = pos; }
   intptr_t end_pos() const { return end_pos_; }
 
   BlockEntryInstr* dominator() const { return dominator_; }
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
   const GrowableArray<BlockEntryInstr*>& dominated_blocks() {
@@ skipping 48 matching lines @@
   virtual bool HasSideEffect() const { return false; }
 
   intptr_t try_index() const { return try_index_; }
 
   BitVector* loop_info() const { return loop_info_; }
   void set_loop_info(BitVector* loop_info) {
     loop_info_ = loop_info;
   }
 
  protected:
-  explicit BlockEntryInstr(intptr_t try_index)
-      : try_index_(try_index),
+  BlockEntryInstr(intptr_t block_id, intptr_t try_index)
+      : block_id_(block_id),
+        try_index_(try_index),
         preorder_number_(-1),
         postorder_number_(-1),
-        block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
         parallel_move_(NULL),
         loop_info_(NULL) { }
 
  private:
   virtual void ClearPredecessors() = 0;
   virtual void AddPredecessor(BlockEntryInstr* predecessor) = 0;
 
+  const intptr_t block_id_;
   const intptr_t try_index_;
   intptr_t preorder_number_;
   intptr_t postorder_number_;
   // Starting and ending lifetime positions for this block.  Used by
   // the linear scan register allocator.
-  intptr_t block_id_;
   intptr_t start_pos_;
   intptr_t end_pos_;
   BlockEntryInstr* dominator_;  // Immediate dominator, NULL for graph entry.
   // TODO(fschneider): Optimize the case of one child to save space.
   GrowableArray<BlockEntryInstr*> dominated_blocks_;
   Instruction* last_instruction_;
 
   // Parallel move that will be used by linear scan register allocator to
   // connect live ranges at the start of the block.
   ParallelMoveInstr* parallel_move_;
@@ skipping 109 matching lines @@
   GrowableArray<TargetEntryInstr*> catch_entries_;
   GrowableArray<Definition*> initial_definitions_;
   intptr_t spill_slot_count_;
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
-  explicit JoinEntryInstr(intptr_t try_index)
-      : BlockEntryInstr(try_index),
+  JoinEntryInstr(intptr_t block_id, intptr_t try_index)
+      : BlockEntryInstr(block_id, try_index),
         predecessors_(2),  // Two is the assumed to be the common case.
         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];
   }
 
   // Returns -1 if pred is not in the list.
   intptr_t IndexOfPredecessor(BlockEntryInstr* pred) const;
 
   ZoneGrowableArray<PhiInstr*>* phis() const { return phis_; }
 
   virtual void PrepareEntry(FlowGraphCompiler* compiler);
 
   void InsertPhi(intptr_t var_index, intptr_t var_count);
   void RemoveDeadPhis();
 
   intptr_t phi_count() const { return phi_count_; }
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
-  // After recomputing predecessors to eliminate unreachable ones,
-  // reorganize phi inputs to match the predecessor order and to eliminate
-  // unreachable inputs.
-  void EliminateUnreachablePhiInputs();
-
  private:
-  virtual void ClearPredecessors() {
-    // Keep a 'backup' of any existing predecessors to enable garbage
-    // collection of phis after eliminating unreachable code and recomputing
-    // predecessors.
-    stale_predecessors_.Clear();
-    stale_predecessors_.AddArray(predecessors_);
-    predecessors_.Clear();
-  }
-  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
-    predecessors_.Add(predecessor);
-  }
+  virtual void ClearPredecessors() { predecessors_.Clear(); }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor);
 
   GrowableArray<BlockEntryInstr*> predecessors_;
   ZoneGrowableArray<PhiInstr*>* phis_;
   intptr_t phi_count_;
-  GrowableArray<BlockEntryInstr*> stale_predecessors_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
-  explicit TargetEntryInstr(intptr_t try_index)
-      : BlockEntryInstr(try_index),
+  TargetEntryInstr(intptr_t block_id, intptr_t try_index)
+      : BlockEntryInstr(block_id, try_index),
         predecessor_(NULL),
         catch_try_index_(CatchClauseNode::kInvalidTryIndex) { }
 
-  // Used for exception catch entries.
-  TargetEntryInstr(intptr_t try_index, intptr_t catch_try_index)
-      : BlockEntryInstr(try_index),
-        predecessor_(NULL),
-        catch_try_index_(catch_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_;
   }
 
   // Returns true if this Block is an entry of a catch handler.
   bool IsCatchEntry() const {
     return catch_try_index_ != CatchClauseNode::kInvalidTryIndex;
   }
 
   // Returns try index for the try block to which this catch handler
   // corresponds.
   intptr_t catch_try_index() const {
     ASSERT(IsCatchEntry());
     return catch_try_index_;
   }
+  void set_catch_try_index(intptr_t index) { catch_try_index_ = index; }
 
   virtual void PrepareEntry(FlowGraphCompiler* compiler);
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
  private:
   virtual void ClearPredecessors() { predecessor_ = NULL; }
   virtual void AddPredecessor(BlockEntryInstr* predecessor) {
     ASSERT(predecessor_ == NULL);
     predecessor_ = predecessor;
   }
 
   BlockEntryInstr* predecessor_;
-  const intptr_t catch_try_index_;
+  intptr_t catch_try_index_;
 
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 // Abstract super-class of all instructions that define a value (Bind, Phi).
 class Definition : public Instruction {
  public:
   enum UseKind { kEffect, kValue };
 
@@ skipping 129 matching lines @@
   virtual intptr_t GetPropagatedCid();
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t InputCount() const { return inputs_.length(); }
 
   Value* InputAt(intptr_t i) const { return inputs_[i]; }
 
   void SetInputAt(intptr_t i, Value* value) { inputs_[i] = value; }
 
+  void RemoveInputAt(intptr_t i) { inputs_.Remove(i); }
+
   virtual bool CanDeoptimize() const { return false; }
 
   virtual bool HasSideEffect() const { return false; }
 
   // TODO(regis): This helper will be removed once we support type sets.
   RawAbstractType* LeastSpecificInputType() const;
 
   // Phi is alive if it reaches a non-environment use.
   bool is_alive() const { return is_alive_; }
   void mark_alive() { is_alive_ = true; }
@@ skipping 19 matching lines @@
     UNREACHABLE();
     return kIllegalCid;
   }
 
   DECLARE_INSTRUCTION(Phi)
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
  private:
-  friend class JoinEntryInstr;  // Direct access to inputs_ array.
-
   JoinEntryInstr* block_;
   GrowableArray<Value*> inputs_;
   bool is_alive_;
   Representation representation_;
 
   DISALLOW_COPY_AND_ASSIGN(PhiInstr);
 };
 
 
 class ParameterInstr : public Definition {
@@ skipping 2478 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_