Compute the def-use list on-demand by walking the dominator tree.

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 194 matching lines @@
   virtual ComparisonComp* AsComparison() { return NULL; }
 
   // Create a location summary for this computation.
   // TODO(fschneider): Temporarily returns NULL for instructions
   // that are not yet converted to the location based code generation.
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
   // TODO(fschneider): Make EmitNativeCode and locs const.
   virtual void EmitNativeCode(FlowGraphCompiler* compiler) = 0;
 
-  virtual void RemoveInputUses() = 0;
-
   static LocationSummary* MakeCallSummary();
 
   // Declare an enum value used to define kind-test predicates.
   enum ComputationKind {
 #define DECLARE_COMPUTATION_KIND(ShortName, ClassName) k##ShortName,
 
   FOR_EACH_COMPUTATION(DECLARE_COMPUTATION_KIND)
 
 #undef DECLARE_COMPUTATION_KIND
   };
@@ skipping 70 matching lines @@
 
 template<intptr_t N>
 class TemplateComputation : public Computation {
  public:
   virtual intptr_t InputCount() const { return N; }
   virtual Value* InputAt(intptr_t i) const { return inputs_[i]; }
   virtual void SetInputAt(intptr_t i, Value* value) {
     ASSERT(value != NULL);
     inputs_[i] = value;
   }
-  virtual void RemoveInputUses() {
-    for (intptr_t i = 0; i < N; ++i) {
-      ASSERT(inputs_[i] != NULL);
-      inputs_[i]->RemoveFromUseList();
-    }
-  }
 
  protected:
   EmbeddedArray<Value*, N> inputs_;
 };
 
 
 class Value : public ZoneAllocated {
  public:
   Value() { }
 
@@ skipping 25 matching lines @@
   // Returns true if the value represents constant null.
   virtual bool BindsToConstantNull() const = 0;
 
   // Assert if BindsToConstant() is false, otherwise returns constant.
   virtual const Object& BoundConstant() const = 0;
 
   // Reminder: The type of the constant null is the bottom type, which is more
   // specific than any type.
   bool CompileTypeIsMoreSpecificThan(const AbstractType& dst_type) const;
 
-  virtual void RemoveFromUseList() = 0;
+  virtual bool Equals(Value* other) const = 0;
 
-  virtual bool Equals(Value* other) const = 0;
+  virtual Value* CopyValue() = 0;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Value);
 };
 
 
 // Functions defined in all concrete computation classes.
 #define DECLARE_COMPUTATION(ShortName)                                         \
   virtual void Accept(FlowGraphVisitor* visitor, BindInstr* instr);            \
   virtual ComputationKind computation_kind() const {                           \
@@ skipping 26 matching lines @@
   virtual RawAbstractType* CompileType() const;                                \
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
 
 class Definition;
 class PhiInstr;
 
 class UseVal : public Value {
  public:
-  explicit UseVal(Definition* definition);
+  explicit UseVal(Definition* definition)
+      : definition_(definition),
+        next_use_(NULL),
+        instruction_(NULL),
+        use_index_(-1) { }
 
   DECLARE_VALUE(Use)
 
-  inline Definition* definition() const;
-  void SetDefinition(Definition* definition);
+  inline Definition* definition() const { return definition_; }
+  void set_definition(Definition* definition) { definition_ = definition; }
 
   // Returns true if the value represents a constant.
   virtual bool BindsToConstant() const;
   virtual const Object& BoundConstant() const;
 
   // Returns true if the value represents constant null.
   virtual bool BindsToConstantNull() const;
 
   virtual bool CanDeoptimize() const { return false; }
 
   UseVal* next_use() const { return next_use_; }
-  UseVal* previous_use() const { return previous_use_; }
-  virtual void RemoveFromUseList();
-  virtual void RemoveInputUses() { RemoveFromUseList(); }
+  void set_next_use(UseVal* next) { next_use_ = next; }
+
+  Instruction* instruction() const { return instruction_; }
+  void set_instruction(Instruction* instruction) { instruction_ = instruction; }
+
+  intptr_t use_index() const { return use_index_; }
+  void set_use_index(intptr_t index) { use_index_ = index; }
+
+  void AddToInputUseList();
+  void AddToEnvUseList();
 
   virtual intptr_t ResultCid() const;
 
+  virtual Value* CopyValue() { return new UseVal(definition_); }
+
  private:
-  void AddToUseList();
   Definition* definition_;
   UseVal* next_use_;
-  UseVal* previous_use_;
-
-  friend class Definition;
+  Instruction* instruction_;
+  intptr_t use_index_;
 
   DISALLOW_COPY_AND_ASSIGN(UseVal);
 };
 
 
 class ConstantVal : public Value {
  public:
   explicit ConstantVal(const Object& value)
       : value_(value) {
     ASSERT(value.IsZoneHandle());
     ASSERT(value.IsSmi() || value.IsOld());
   }
 
   DECLARE_VALUE(Constant)
 
   const Object& value() const { return value_; }
 
   // Returns true if the value represents a constant.
   virtual bool BindsToConstant() const { return true; }
   virtual const Object& BoundConstant() const { return value(); }
 
   // Returns true if the value represents constant null.
   virtual bool BindsToConstantNull() const { return value().IsNull(); }
 
   virtual bool CanDeoptimize() const { return false; }
 
-  virtual void RemoveFromUseList() { }
+  virtual intptr_t ResultCid() const;
 
-  virtual intptr_t ResultCid() const;
+  virtual Value* CopyValue() { return this; }
 
  private:
   const Object& value_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstantVal);
 };
 
 #undef DECLARE_VALUE
 
 
@@ skipping 1574 matching lines @@
     // 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
     next_ = instr;
   }
 
   // Removed this instruction from the graph.
   Instruction* RemoveFromGraph(bool return_previous = true);
 
-  // Remove value uses within this instruction and its inputs.
-  virtual void RemoveInputUses() = 0;
-
   // 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
@@ skipping 81 matching lines @@
 
   virtual LocationSummary* locs() {
     if (locs_ == NULL) {
       locs_ = MakeLocationSummary();
     }
     return locs_;
   }
 
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
-  virtual void RemoveInputUses() {
-    for (intptr_t i = 0; i < N; ++i) {
-      ASSERT(inputs_[i] != NULL);
-      inputs_[i]->RemoveFromUseList();
-    }
-  }
-
  protected:
   EmbeddedArray<Value*, N> inputs_;
 
  private:
   LocationSummary* locs_;
 };
 
 
 class MoveOperands : public ZoneAllocated {
  public:
@@ skipping 157 matching lines @@
   virtual Value* InputAt(intptr_t i) const {
     UNREACHABLE();
     return NULL;
   }
   virtual void SetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   virtual bool CanDeoptimize() const { return false; }
 
-  virtual void RemoveInputUses() { }
-
  protected:
   BlockEntryInstr()
       : preorder_number_(-1),
         postorder_number_(-1),
         block_id_(-1),
         dominator_(NULL),
         dominated_blocks_(1),
         last_instruction_(NULL),
         parallel_move_(NULL) { }
 
@@ skipping 205 matching lines @@
 
 
 // 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),
         propagated_type_(AbstractType::Handle()),
         propagated_cid_(kIllegalCid),
-        use_list_(NULL) { }
+        input_use_list_(NULL),
+        env_use_list_(NULL) { }
 
   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) {
     ASSERT(index >= 0);
@@ skipping 25 matching lines @@
   }
 
   bool has_propagated_cid() const { return propagated_cid_ != kIllegalCid; }
   intptr_t propagated_cid() const { return propagated_cid_; }
   // May compute and set propagated cid.
   virtual intptr_t GetPropagatedCid() = 0;
 
   // Returns true if the propagated cid has changed.
   bool SetPropagatedCid(intptr_t cid);
 
-  UseVal* use_list() { return use_list_; }
-  void set_use_list(UseVal* head) {
-    ASSERT(head == NULL || head->previous_use() == NULL);
-    use_list_ = head;
-  }
+  UseVal* input_use_list() { return input_use_list_; }
+  void set_input_use_list(UseVal* head) { input_use_list_ = head; }
 
+  UseVal* env_use_list() { return env_use_list_; }
+  void set_env_use_list(UseVal* head) { env_use_list_ = head; }
+
+  // Replace uses of this definition with uses of other definition or value.
+  // Precondition: use lists must be properly calculated.
+  // Postcondition: use lists and use values are still valid.
   void ReplaceUsesWith(Definition* other);
+  void ReplaceUsesWith(Value* 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_;
-  UseVal* use_list_;
+  UseVal* input_use_list_;
+  UseVal* env_use_list_;
 
   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);
-  return definition_;
-}
-
-
 class BindInstr : public Definition {
  public:
   enum UseKind { kUnused, kUsed };
 
   BindInstr(UseKind used, Computation* computation)
       : computation_(computation), is_used_(used != kUnused) {
     ASSERT(computation != NULL);
   }
 
   DECLARE_INSTRUCTION(Bind)
@@ skipping 26 matching lines @@
   bool Equals(BindInstr* other) const {
     return computation()->Equals(other->computation());
   }
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
-  virtual void RemoveInputUses() { computation()->RemoveInputUses(); }
-
   // Insert this instruction before 'next'.
   void InsertBefore(BindInstr* next);
 
  private:
   Computation* computation_;
   const bool is_used_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
@@ skipping 13 matching lines @@
   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; }
 
   virtual bool CanDeoptimize() const { return false; }
 
-  virtual void RemoveInputUses() {
-    for (intptr_t i = 0; i < inputs_.length(); ++i) {
-      ASSERT(inputs_[i] != NULL);
-      inputs_[i]->RemoveFromUseList();
-    }
-  }
-
   // 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; }
 
   DECLARE_INSTRUCTION(Phi)
 
  private:
@@ skipping 21 matching lines @@
 
   intptr_t InputCount() const { return 0; }
   Value* InputAt(intptr_t i) const {
     UNREACHABLE();
     return NULL;
   }
   void SetInputAt(intptr_t i, Value* value) { UNREACHABLE(); }
 
   virtual bool CanDeoptimize() const { return false; }
 
-  virtual void RemoveInputUses() { }
-
  private:
   const intptr_t index_;
 
   DISALLOW_COPY_AND_ASSIGN(ParameterInstr);
 };
 
 
 class PushArgumentInstr : public Definition {
  public:
   explicit PushArgumentInstr(Value* value) : value_(value), locs_(NULL) {
@@ skipping 29 matching lines @@
   LocationSummary* MakeLocationSummary() const;
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
   virtual bool CanDeoptimize() const { return false; }
 
   bool WasEliminated() const {
     return next() == NULL;
   }
 
-  virtual void RemoveInputUses() { value_->RemoveFromUseList(); }
-
  private:
   Value* value_;
   LocationSummary* locs_;
 
   DISALLOW_COPY_AND_ASSIGN(PushArgumentInstr);
 };
 
 
 class ReturnInstr : public TemplateInstruction<1> {
  public:
@@ skipping 311 matching lines @@
   ForwardInstructionIterator* current_iterator_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_