Added def-use chain to the intermediate language.

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 164 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 66 matching lines @@
     return sentinel;
   }
 };
 
 
 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) { inputs_[i] = value; }
+  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 TemplateComputation<0> {
  public:
   Value() { }
 
   bool CompileTypeIsMoreSpecificThan(const AbstractType& dst_type) const;
 
+  virtual void RemoveFromUseList() = 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 {                           \
     return Computation::k##ShortName;                                          \
@@ skipping 20 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) : definition_(definition) {}
+  explicit UseVal(Definition* definition);
 
   DECLARE_VALUE(Use)
 
   inline Definition* definition() const;
-  void set_definition(Definition* definition) {
-    definition_ = definition;
-  }
+  void SetDefinition(Definition* definition);
 
   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(); }
+
  private:
+  void AddToUseList();
   Definition* definition_;
+  UseVal* next_use_;
+  UseVal* previous_use_;
 
   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_; }
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual void RemoveFromUseList() { }
+
  private:
   const Object& value_;
 
   DISALLOW_COPY_AND_ASSIGN(ConstantVal);
 };
 
 #undef DECLARE_VALUE
 
 
 class AssertAssignableComp : public TemplateComputation<3> {
@@ skipping 410 matching lines @@
 };
 
 
 class StoreLocalComp : public TemplateComputation<1> {
  public:
   StoreLocalComp(const LocalVariable& local,
                  Value* value,
                  intptr_t context_level)
       : local_(local),
         context_level_(context_level) {
+    ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StoreLocal)
 
   const LocalVariable& local() const { return local_; }
   Value* value() const { return inputs_[0]; }
   intptr_t context_level() const { return context_level_; }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars,
@@ skipping 203 matching lines @@
 class StoreIndexedComp : public TemplateComputation<3> {
  public:
   StoreIndexedComp(intptr_t token_pos,
                    intptr_t try_index,
                    Value* array,
                    Value* index,
                    Value* value)
       : token_pos_(token_pos),
         try_index_(try_index),
         receiver_type_(kIllegalCid) {
+    ASSERT(array != NULL);
+    ASSERT(index != NULL);
+    ASSERT(value != NULL);
     inputs_[0] = array;
     inputs_[1] = index;
     inputs_[2] = value;
   }
 
   DECLARE_COMPUTATION(StoreIndexed)
 
   intptr_t token_pos() const { return token_pos_; }
   intptr_t try_index() const { return try_index_; }
   Value* array() const { return inputs_[0]; }
@@ skipping 16 matching lines @@
   intptr_t receiver_type_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreIndexedComp);
 };
 
 
 // Note overrideable, built-in: value? false : true.
 class BooleanNegateComp : public TemplateComputation<1> {
  public:
   explicit BooleanNegateComp(Value* value) {
+    ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(BooleanNegate)
 
   Value* value() const { return inputs_[0]; }
 
   virtual bool CanDeoptimize() const { return false; }
 
  private:
@@ skipping 226 matching lines @@
 
 
 class StoreVMFieldComp : public TemplateComputation<2> {
  public:
   StoreVMFieldComp(Value* dest,
                    intptr_t offset_in_bytes,
                    Value* value,
                    const AbstractType& type)
       : offset_in_bytes_(offset_in_bytes), type_(type) {
     ASSERT(value != NULL);
+    ASSERT(dest != NULL);
     ASSERT(type.IsZoneHandle());  // May be null if field is not an instance.
     inputs_[0] = value;
     inputs_[1] = dest;
   }
 
   DECLARE_COMPUTATION(StoreVMField)
 
   Value* value() const { return inputs_[0]; }
   Value* dest() const { return inputs_[1]; }
   intptr_t offset_in_bytes() const { return offset_in_bytes_; }
@@ skipping 483 matching lines @@
     ASSERT(instr == NULL || !instr->IsBlockEntry());
     // 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 uses in this instruction from the def-use chains.

[zerny-google, 2012/08/10 12:20:18]

I'll change this comment.

+  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
@@ skipping 66 matching lines @@
 };
 
 
 template<intptr_t N>
 class TemplateInstruction: public Instruction {
  public:
   TemplateInstruction<N>() : locs_(NULL) { }
 
   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) { inputs_[i] = value; }
+  virtual void SetInputAt(intptr_t i, Value* value) {
+    ASSERT(value != NULL);
+    inputs_[i] = value;
+  }
 
   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 203 matching lines @@
   DISALLOW_COPY_AND_ASSIGN(TargetEntryInstr);
 };
 
 
 // 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_type_(AbstractType::Handle()),
+        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 17 matching lines @@
     if (propagated_type.IsNull()) {
       // Not a typed definition, e.g. access to a VM field.
       return false;
     }
     const bool changed =
         propagated_type_.IsNull() || !propagated_type.Equals(propagated_type_);
     propagated_type_ = propagated_type.raw();
     return changed;
   }
 
+  UseVal* use_list() { return use_list_; }
+  void set_use_list(UseVal* head) {
+    ASSERT(head == NULL || head->previous_use() == NULL);
+    use_list_ = head;
+  }
+
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
   // TODO(regis): GrowableArray<const AbstractType*> propagated_types_;
   // For now:
   AbstractType& propagated_type_;
+  UseVal* 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_;
 }
@@ skipping 31 matching lines @@
 
   virtual void RecordAssignedVars(BitVector* assigned_vars,
                                   intptr_t fixed_parameter_count);
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
+  virtual void RemoveInputUses() { computation()->RemoveInputUses(); }
+
  private:
   Computation* computation_;
   const bool is_used_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class PhiInstr : public Definition {
  public:
   explicit PhiInstr(intptr_t num_inputs)
     : inputs_(num_inputs), is_alive_(false) {
     for (intptr_t i = 0; i < num_inputs; ++i) {
       inputs_.Add(NULL);
     }
   }
 
   virtual RawAbstractType* CompileType() const;
 
   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 17 matching lines @@
 
   virtual intptr_t ArgumentCount() const { return 0; }
 
   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 bool CanDeoptimize() const { return false; }
+  virtual void RemoveInputUses() { }
 
  private:
   const intptr_t index_;
 
   DISALLOW_COPY_AND_ASSIGN(ParameterInstr);
 };
 
 
 class PushArgumentInstr : public TemplateInstruction<1> {
  public:
@@ skipping 332 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_