Initial implementation of sparse conditional constant propagation.

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 585 matching lines @@
 // graph entry with no predecessor.  Joins are the only nodes with multiple
 // predecessors.  Targets are all other basic block entries.  The types
 // enforce edge-split form---joins are forbidden as the successors of
 // branches.
 class BlockEntryInstr : public Instruction {
  public:
   virtual BlockEntryInstr* AsBlockEntry() { return this; }
 
   virtual intptr_t PredecessorCount() const = 0;
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const = 0;
-  virtual void AddPredecessor(BlockEntryInstr* predecessor) = 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() {
     return dominated_blocks_;
   }
 
   void AddDominatedBlock(BlockEntryInstr* block) {
     dominated_blocks_.Add(block);
   }
+  void ClearDominatedBlocks() { dominated_blocks_.Clear(); }
 
   bool Dominates(BlockEntryInstr* other) const;
 
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
   ParallelMoveInstr* parallel_move() const {
     return parallel_move_;
   }
 
@@ skipping 43 matching lines @@
         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 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.
@@ skipping 68 matching lines @@
  public:
   explicit GraphEntryInstr(TargetEntryInstr* normal_entry);
 
   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 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 14 matching lines @@
     ASSERT(count >= 0);
     spill_slot_count_ = count;
   }
 
   TargetEntryInstr* normal_entry() const { return normal_entry_; }
 
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
  private:
+  virtual void ClearPredecessors() { UNREACHABLE(); }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) { UNREACHABLE(); }
+
   TargetEntryInstr* normal_entry_;
   GrowableArray<TargetEntryInstr*> catch_entries_;
   Environment* start_env_;
   ConstantInstr* constant_null_;
   intptr_t spill_slot_count_;
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
   explicit JoinEntryInstr(intptr_t try_index)
       : BlockEntryInstr(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];
   }
-  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
-    predecessors_.Add(predecessor);
-  }
 
   // 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);
+  }
+
   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),
         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_;
   }
-  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
-    ASSERT(predecessor_ == NULL);
-    predecessor_ = 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_;
   }
 
   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_;
 
   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 };
 
-  Definition()
-      : temp_index_(-1),
-        ssa_temp_index_(-1),
-        propagated_type_(AbstractType::Handle()),
-        propagated_cid_(kIllegalCid),
-        input_use_list_(NULL),
-        env_use_list_(NULL),
-        use_kind_(kValue) {  // Phis and parameters rely on this default.
-  }
+  Definition();
 
   virtual Definition* AsDefinition() { return this; }
 
   bool IsComparison() { return (AsComparison() != NULL); }
   virtual ComparisonInstr* AsComparison() { return NULL; }
 
   // Overridden by definitions that push arguments.
   virtual intptr_t ArgumentCount() const { return 0; }
 
   intptr_t temp_index() const { return temp_index_; }
@@ skipping 101 matching lines @@
 
   // Get the block entry for that instruction.
   virtual BlockEntryInstr* GetBlock() const;
 
   // Printing support. These functions are sometimes overridden for custom
   // formatting. Otherwise, it prints in the format "opcode(op1, op2, op3)".
   virtual void PrintTo(BufferFormatter* f) const;
   virtual void PrintOperandsTo(BufferFormatter* f) const;
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
+  // A value in the constant propagation lattice.
+  //    - non-constant sentinel
+  //    - a constant (any non-sentinel value)
+  //    - unknown sentinel
+  Object& constant_value() const { return constant_value_; }
+
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
   // TODO(regis): GrowableArray<const AbstractType*> propagated_types_;
   // For now:
   AbstractType& propagated_type_;
   intptr_t propagated_cid_;
   Value* input_use_list_;
   Value* env_use_list_;
   UseKind use_kind_;
 
+  Object& constant_value_;
+
   DISALLOW_COPY_AND_ASSIGN(Definition);
 };
 
 
 class PhiInstr : public Definition {
  public:
   explicit PhiInstr(JoinEntryInstr* block, intptr_t num_inputs)
     : block_(block),
       inputs_(num_inputs),
       is_alive_(false),
@@ skipping 50 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 2492 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_