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 163 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 RemoveFromDefUseChain() = 0;
+
   static LocationSummary* MakeCallSummary();
 
   // Declare an enum value used to define type-test predicates.
   enum ComputationType {
 #define DECLARE_COMPUTATION_TYPE(ShortName, ClassName) k##ShortName,
 
   FOR_EACH_COMPUTATION(DECLARE_COMPUTATION_TYPE)
 
 #undef DECLARE_COMPUTATION_TYPE
   };
@@ skipping 68 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) { inputs_[i] = value; }
 
+  virtual void RemoveFromDefUseChain() {
+    for (intptr_t i = 0; i < N; ++i) inputs_[i]->RemoveFromDefUseChain();

[srdjan, 2012/08/09 20:07:52]

Can some inputs be NULL? Maybe:

if (inputs_[i] != NULL) {
  inputs_[i]->Remove ...
}

[zerny-google, 2012/08/10 08:08:29]

Indeed, thanks. It is tempting to assert non-null inputs. Almost all inputs_ are
asserted to be non-null at construction time. The exception to the rule being
PhiInstr. However, when removing a phi (after renaming) its inputs should be
actual values. I'll check this assumption and repair the code accordingly.

A side note: there are a few other instructions that do not assert non-null
inputs, but most likely should: StoreLocalComp, StoreIndexedComp,
BooleanNegateComp, and StoreVMFieldComp.

+  }
+
  protected:
   EmbeddedArray<Value*, N> inputs_;
 };
 
 
 class Value : public TemplateComputation<0> {
  public:
   Value() { }
 
   bool StaticTypeIsMoreSpecificThan(const AbstractType& dst_type) const;
@@ skipping 31 matching lines @@
   virtual RawAbstractType* StaticType() 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 set_definition(Definition* definition);

[srdjan, 2012/08/09 20:07:52]

s/set_definition/SetDefinition/

[zerny-google, 2012/08/10 08:08:29]

Ok.

 
   virtual bool CanDeoptimize() const { return false; }
 
+  UseVal* next_use() { return next_use_; }

[Florian Schneider, 2012/08/10 08:35:37]

Maybe add const:

UseVal* next_use() const { return next_use_; }

+  UseVal* previous_use() { return previous_use_; }

[Florian Schneider, 2012/08/10 08:35:37]

Const here as well.

+  virtual void RemoveFromDefUseChain();
+
  private:
+  void AddToDefUseChain();
   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());
@@ skipping 769 matching lines @@
   virtual intptr_t InputCount() const;
   virtual Value* InputAt(intptr_t i) const { return arguments()[i]; }
   virtual void SetInputAt(intptr_t i, Value* value) {
     (*arguments_)[i] = value;
   }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual void RemoveFromDefUseChain() {
+    // TODO(zerny): why are we using an array here?

[Florian Schneider, 2012/08/10 08:35:37]

You're right, we actually don't need to have an array here.

+    arguments()[0]->RemoveFromDefUseChain();
+    arguments()[1]->RemoveFromDefUseChain();
+  }
+
  private:
   const ConstructorCallNode& ast_node_;
   const intptr_t try_index_;
   ZoneGrowableArray<Value*>* const arguments_;
   DISALLOW_COPY_AND_ASSIGN(AllocateObjectComp);
 };
 
 
 class AllocateObjectWithBoundsCheckComp : public Computation {
  public:
@@ skipping 15 matching lines @@
   virtual intptr_t InputCount() const;
   virtual Value* InputAt(intptr_t i) const { return arguments()[i]; }
   virtual void SetInputAt(intptr_t i, Value* value) {
     (*arguments_)[i] = value;
   }
 
   virtual void PrintOperandsTo(BufferFormatter* f) const;
 
   virtual bool CanDeoptimize() const { return false; }
 
+  virtual void RemoveFromDefUseChain() {
+    // TODO(zerny): why are we using an array here?
+    arguments()[0]->RemoveFromDefUseChain();
+    arguments()[1]->RemoveFromDefUseChain();
+  }
+
  private:
   const ConstructorCallNode& ast_node_;
   const intptr_t try_index_;
   ZoneGrowableArray<Value*>* const arguments_;
   DISALLOW_COPY_AND_ASSIGN(AllocateObjectWithBoundsCheckComp);
 };
 
 
 class CreateArrayComp : public TemplateComputation<1> {
  public:
@@ skipping 608 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.
+  void RemoveFromDefUseChain();

[Florian Schneider, 2012/08/10 08:35:37]

This is a declaration without a definition. Is the intention to make it
abstract?

 
   // 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 77 matching lines @@
 
   virtual LocationSummary* locs() {
     if (locs_ == NULL) {
       locs_ = MakeLocationSummary();
     }
     return locs_;
   }
 
   virtual LocationSummary* MakeLocationSummary() const = 0;
 
+  virtual void RemoveFromDefUseChain() {
+    for (intptr_t i = 0; i < N; ++i) inputs_[i]->RemoveFromDefUseChain();

[srdjan, 2012/08/09 20:07:52]

San some inputs_[i] ne NULL?

+  }
+
  protected:
   EmbeddedArray<Value*, N> inputs_;
 
  private:
   LocationSummary* locs_;
 };
 
 
 class MoveOperands : public ZoneAllocated {
  public:
@@ skipping 377 matching lines @@
   BlockEntryInstr* predecessor_;
   const intptr_t try_index_;
 
   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) { }
+  Definition() : temp_index_(-1), ssa_temp_index_(-1), def_use_chain_(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);
     ssa_temp_index_ = index;
   }
   bool HasSSATemp() const { return ssa_temp_index_ >= 0; }
 
   // Static type of the definition.
   virtual RawAbstractType* StaticType() const = 0;
 
+  UseVal* def_use_chain() { return def_use_chain_; }
+  void set_def_use_chain(UseVal* chain) { def_use_chain_ = chain; }

[srdjan, 2012/08/09 20:07:52]

Should you assert that chain is head (previous is NULL).

[zerny-google, 2012/08/10 08:08:29]

Sure.

+
  private:
   intptr_t temp_index_;
   intptr_t ssa_temp_index_;
+  UseVal* def_use_chain_;

[srdjan, 2012/08/09 20:07:52]

This is a chain of uses only, isn't it? Maybe rename to use_chain?

[zerny-google, 2012/08/10 08:08:29]

Ok. What about 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 34 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 RemoveFromDefUseChain() {
+    computation_->RemoveFromDefUseChain();
+  }
+
  private:
   Computation* computation_;
   const bool is_used_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 class PhiInstr : public Definition {
  public:
@@ skipping 398 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_