Added def-use chain to the intermediate language.

runtime/vm/intermediate_language.h

Index: runtime/vm/intermediate_language.h
diff --git a/runtime/vm/intermediate_language.h b/runtime/vm/intermediate_language.h
index babd95f27b1ecddb4e72eaf5c7a9c124d95b3cbf..fccbcdce0244453b5796cff54cfd42d0f12c662f 100644
--- a/runtime/vm/intermediate_language.h
+++ b/runtime/vm/intermediate_language.h
@@ -181,6 +181,8 @@ class Computation : public ZoneAllocated {
   // 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.
@@ -269,6 +271,10 @@ class TemplateComputation : public Computation {
   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_;
 };
@@ -320,19 +326,24 @@ 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);
 };
@@ -1122,6 +1133,12 @@ class AllocateObjectComp : public Computation {
 
   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_;
@@ -1157,6 +1174,12 @@ class AllocateObjectWithBoundsCheckComp : public Computation {
 
   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_;
@@ -1785,6 +1808,8 @@ class Instruction : public ZoneAllocated {
 
   // 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
@@ -1882,6 +1907,10 @@ class TemplateInstruction: public Instruction {
 
   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_;
 
@@ -2279,7 +2308,7 @@ class TargetEntryInstr : public BlockEntryInstr {
 // 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; }
@@ -2297,9 +2326,13 @@ class Definition : public Instruction {
   // 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);
 };
@@ -2354,6 +2387,10 @@ class BindInstr : public Definition {
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
+  virtual void RemoveFromDefUseChain() {
+    computation_->RemoveFromDefUseChain();
+  }
+
  private:
   Computation* computation_;
   const bool is_used_;