Revision: 12697
Author:   svenpa...@chromium.org
Date:     Thu Oct 11 03:52:58 2012
Log:      Added a simple dead code removal phase.

We iteratively remove all dead Hydrogen instruction until we reach a fixed  
point. We consider an instruction dead if it is unused, has no observable  
side effects and is deletable. The last part of the condition is currently  
not very nice: We basically have to whitelist "safe" instructions, because  
we are missing more detailed dependencies and/or more detailed tracking of  
side effects.

We disable dead code elimination for now in our test runners, because we  
have tons of poorly written tests which wouldn't test anymore what they are  
supposed to test with this phase enabled. To get test coverage for dead  
code elimination itself, we should enable it on a few build bots. This is  
not really a perfect state, but the best we can do for now.

This patch includes a few const-correctness fixes, most of them were  
necessary for this CL.

Review URL: https://codereview.chromium.org/11088027
http://code.google.com/p/v8/source/detail?r=12697

Modified:
  /branches/bleeding_edge/src/flag-definitions.h
  /branches/bleeding_edge/src/hydrogen-instructions.cc
  /branches/bleeding_edge/src/hydrogen-instructions.h
  /branches/bleeding_edge/src/hydrogen.cc
  /branches/bleeding_edge/src/hydrogen.h
  /branches/bleeding_edge/src/property-details.h
  /branches/bleeding_edge/src/utils.h
  /branches/bleeding_edge/tools/run-tests.py
  /branches/bleeding_edge/tools/test.py

=======================================
--- /branches/bleeding_edge/src/flag-definitions.h      Tue Oct  2 02:58:11 2012
+++ /branches/bleeding_edge/src/flag-definitions.h      Thu Oct 11 03:52:58 2012
@@ -202,6 +202,8 @@
              "perform array bounds checks elimination")
  DEFINE_bool(array_index_dehoisting, true,
              "perform array index dehoisting")
+DEFINE_bool(dead_code_elimination, true, "use dead code elimination")
+DEFINE_bool(trace_dead_code_elimination, false, "trace dead code  
elimination")

  DEFINE_bool(trace_osr, false, "trace on-stack replacement")
  DEFINE_int(stress_runs, 0, "number of stress runs")
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.cc        Tue Sep 18  
04:06:05 2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.cc        Thu Oct 11  
03:52:58 2012
@@ -1854,7 +1854,7 @@
  }

-bool HLoadKeyedFastElement::RequiresHoleCheck() {
+bool HLoadKeyedFastElement::RequiresHoleCheck() const {
    if (IsFastPackedElementsKind(elements_kind())) {
      return false;
    }
@@ -2090,7 +2090,7 @@
  }

-bool HLoadGlobalCell::RequiresHoleCheck() {
+bool HLoadGlobalCell::RequiresHoleCheck() const {
    if (details_.IsDontDelete() && !details_.IsReadOnly()) return false;
    for (HUseIterator it(uses()); !it.Done(); it.Advance()) {
      HValue* use = it.value();
=======================================
--- /branches/bleeding_edge/src/hydrogen-instructions.h Tue Oct  9 06:53:24  
2012
+++ /branches/bleeding_edge/src/hydrogen-instructions.h Thu Oct 11 03:52:58  
2012
@@ -667,7 +667,7 @@

    // Operands.
    virtual int OperandCount() = 0;
-  virtual HValue* OperandAt(int index) = 0;
+  virtual HValue* OperandAt(int index) const = 0;
    void SetOperandAt(int index, HValue* value);

    void DeleteAndReplaceWith(HValue* other);
@@ -777,6 +777,10 @@
    virtual void SetSideEffectDominator(GVNFlag side_effect, HValue*  
dominator) {
      UNREACHABLE();
    }
+
+  bool IsDead() const {
+    return HasNoUses() && !HasObservableSideEffects() && IsDeletable();
+  }

  #ifdef DEBUG
    virtual void Verify() = 0;
@@ -862,6 +866,8 @@
    GVNFlagSet gvn_flags_;

   private:
+  virtual bool IsDeletable() const { return false; }
+
    DISALLOW_COPY_AND_ASSIGN(HValue);
  };

@@ -930,7 +936,7 @@
  class HTemplateInstruction : public HInstruction {
   public:
    int OperandCount() { return V; }
-  HValue* OperandAt(int i) { return inputs_[i]; }
+  HValue* OperandAt(int i) const { return inputs_[i]; }

   protected:
    void InternalSetOperandAt(int i, HValue* value) { inputs_[i] = value; }
@@ -982,7 +988,7 @@
    void SetSuccessorAt(int i, HBasicBlock* block) { successors_[i] = block;  

    int OperandCount() { return V; }
-  HValue* OperandAt(int i) { return inputs_[i]; }
+  HValue* OperandAt(int i) const { return inputs_[i]; }

   protected:
@@ -1027,7 +1033,7 @@
    }

    virtual int OperandCount() { return values_.length(); }
-  virtual HValue* OperandAt(int index) { return values_[index]; }
+  virtual HValue* OperandAt(int index) const { return values_[index]; }
    virtual void PrintDataTo(StringStream* stream);

    virtual int SuccessorCount() { return 0; }
@@ -1284,6 +1290,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1303,6 +1312,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1341,7 +1353,7 @@
      AddValue(kNoIndex, value);
    }
    virtual int OperandCount() { return values_.length(); }
-  virtual HValue* OperandAt(int index) { return values_[index]; }
+  virtual HValue* OperandAt(int index) const { return values_[index]; }

    virtual Representation RequiredInputRepresentation(int index) {
      return Representation::None();
@@ -1514,6 +1526,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1532,6 +1547,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1550,6 +1568,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1595,6 +1616,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1614,6 +1638,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1899,6 +1926,9 @@

   protected:
    virtual bool DataEquals(HValue* other_raw) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1919,6 +1949,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1939,6 +1972,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1958,6 +1994,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -1980,6 +2019,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2062,6 +2104,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    BuiltinFunctionId op_;
  };

@@ -2086,6 +2130,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2109,6 +2156,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2408,7 +2458,7 @@
    }
    virtual HType CalculateInferredType();
    virtual int OperandCount() { return inputs_.length(); }
-  virtual HValue* OperandAt(int index) { return inputs_[index]; }
+  virtual HValue* OperandAt(int index) const { return inputs_[index]; }
    HValue* GetRedundantReplacement();
    void AddInput(HValue* value);
    bool HasRealUses();
@@ -2504,6 +2554,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(ArgumentsObject)
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2632,6 +2685,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    // If this is a numerical constant, handle_ either points to to the
    // HeapObject the constant originated from or is null.  If the
    // constant is non-numeric, handle_ always points to a valid
@@ -2753,6 +2808,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }

    bool from_inlined_;
  };
@@ -2773,6 +2831,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2898,6 +2959,8 @@
    DECLARE_ABSTRACT_INSTRUCTION(BitwiseBinaryOperation)

   private:
+  virtual bool IsDeletable() const { return true; }
+
    Representation observed_input_representation_[3];
  };

@@ -2921,6 +2984,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -2953,6 +3019,9 @@
      }
      return HValue::InferredRepresentation();
    }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -3238,6 +3307,9 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -3342,7 +3414,7 @@
    }

    HValue* left() { return OperandAt(0); }
-  HValue* right() { return OperandAt(1); }
+  HValue* right() const { return OperandAt(1); }

    virtual Representation RequiredInputRepresentation(int index) {
      return index == 0
@@ -3354,6 +3426,11 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+ private:
+  virtual bool IsDeletable() const {
+    return !right()->representation().IsTagged();
+  }
  };

@@ -3371,6 +3448,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(Random)
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -3761,7 +3841,7 @@
    }

    Handle<JSGlobalPropertyCell>  cell() const { return cell_; }
-  bool RequiresHoleCheck();
+  bool RequiresHoleCheck() const;

    virtual void PrintDataTo(StringStream* stream);

@@ -3783,6 +3863,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return !RequiresHoleCheck(); }
+
    Handle<JSGlobalPropertyCell> cell_;
    PropertyDetails details_;
  };
@@ -3943,7 +4025,7 @@
      return mode_ == kCheckDeoptimize;
    }

-  bool RequiresHoleCheck() {
+  bool RequiresHoleCheck() const {
      return mode_ != kNoCheck;
    }

@@ -3962,6 +4044,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return !RequiresHoleCheck(); }
+
    int slot_index_;
    Mode mode_;
  };
@@ -4054,6 +4138,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    bool is_in_object_;
    int offset_;
  };
@@ -4200,7 +4286,7 @@

    virtual void PrintDataTo(StringStream* stream);

-  bool RequiresHoleCheck();
+  bool RequiresHoleCheck() const;

    DECLARE_CONCRETE_INSTRUCTION(LoadKeyedFastElement)

@@ -4214,6 +4300,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return !RequiresHoleCheck(); }
+
    class ElementsKindField:  public BitField<ElementsKind, 0, 4> {};
    class IndexOffsetField:   public BitField<uint32_t, 4, 27> {};
    class IsDehoistedField:   public BitField<bool, 31, 1> {};
@@ -4260,7 +4348,7 @@
      return Representation::None();
    }

-  bool RequiresHoleCheck() {
+  bool RequiresHoleCheck() const {
      return hole_check_mode_ == PERFORM_HOLE_CHECK;
    }

@@ -4277,6 +4365,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return !RequiresHoleCheck(); }
+
    uint32_t index_offset_;
    bool is_dehoisted_;
    HoleCheckMode hole_check_mode_;
@@ -4341,6 +4431,8 @@
    }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    ElementsKind elements_kind_;
    uint32_t index_offset_;
    bool is_dehoisted_;
@@ -4722,6 +4814,10 @@

   protected:
    virtual bool DataEquals(HValue* other) { return true; }
+
+  // TODO(svenpanne) Might be safe, but leave it out until we know for  
sure.
+  // private:
+  //  virtual bool IsDeletable() const { return true; }
  };

@@ -4756,6 +4852,10 @@
    virtual Range* InferRange(Zone* zone) {
      return new(zone) Range(0, String::kMaxUtf16CodeUnit);
    }
+
+  // TODO(svenpanne) Might be safe, but leave it out until we know for  
sure.
+  // private:
+  //  virtual bool IsDeletable() const { return true; }
  };

@@ -4782,6 +4882,10 @@
    virtual bool DataEquals(HValue* other) { return true; }

    DECLARE_CONCRETE_INSTRUCTION(StringCharFromCode)
+
+  // TODO(svenpanne) Might be safe, but leave it out until we know for  
sure.
+  // private:
+  //  virtual bool IsDeletable() const { return true; }
  };

@@ -4810,6 +4914,9 @@
    virtual Range* InferRange(Zone* zone) {
      return new(zone) Range(0, String::kMaxLength);
    }
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -4836,6 +4943,9 @@
    DECLARE_CONCRETE_INSTRUCTION(AllocateObject)

   private:
+  // TODO(svenpanne) Might be safe, but leave it out until we know for  
sure.
+  //  virtual bool IsDeletable() const { return true; }
+
    Handle<JSFunction> constructor_;
  };

@@ -4852,6 +4962,8 @@
    int depth() const { return depth_; }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    int literal_index_;
    int depth_;
  };
@@ -5027,6 +5139,8 @@
    bool pretenure() const { return pretenure_; }

   private:
+  virtual bool IsDeletable() const { return true; }
+
    Handle<SharedFunctionInfo> shared_info_;
    bool pretenure_;
  };
@@ -5051,6 +5165,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(Typeof)
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -5069,6 +5186,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(ToFastProperties)
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -5083,6 +5203,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(ValueOf)
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

@@ -5279,6 +5402,9 @@
    }

    DECLARE_CONCRETE_INSTRUCTION(LoadFieldByIndex);
+
+ private:
+  virtual bool IsDeletable() const { return true; }
  };

=======================================
--- /branches/bleeding_edge/src/hydrogen.cc     Tue Oct  9 06:53:24 2012
+++ /branches/bleeding_edge/src/hydrogen.cc     Thu Oct 11 03:52:58 2012
@@ -3358,6 +3358,7 @@

    EliminateRedundantBoundsChecks();
    DehoistSimpleArrayIndexComputations();
+  if (FLAG_dead_code_elimination) DeadCodeElimination();

    return true;
  }
@@ -3785,6 +3786,36 @@
      }
    }
  }
+
+
+void HGraph::DeadCodeElimination() {
+  HPhase phase("H_Dead code elimination", this);
+  ZoneList<HInstruction*> worklist(blocks_.length(), zone());
+  for (int i = 0; i < blocks()->length(); ++i) {
+    for (HInstruction* instr = blocks()->at(i)->first();
+         instr != NULL;
+         instr = instr->next()) {
+      if (instr->IsDead()) worklist.Add(instr, zone());
+    }
+  }
+
+  while (!worklist.is_empty()) {
+    HInstruction* instr = worklist.RemoveLast();
+    if (FLAG_trace_dead_code_elimination) {
+      HeapStringAllocator allocator;
+      StringStream stream(&allocator);
+      instr->PrintNameTo(&stream);
+      stream.Add(" = ");
+      instr->PrintTo(&stream);
+      PrintF("[removing dead instruction %s]\n", *stream.ToCString());
+    }
+    instr->DeleteAndReplaceWith(NULL);
+    for (int i = 0; i < instr->OperandCount(); ++i) {
+      HValue* operand = instr->OperandAt(i);
+      if (operand->IsDead()) worklist.Add(HInstruction::cast(operand),  
zone());
+    }
+  }
+}

  HInstruction* HGraphBuilder::AddInstruction(HInstruction* instr) {
=======================================
--- /branches/bleeding_edge/src/hydrogen.h      Wed Sep 12 05:28:42 2012
+++ /branches/bleeding_edge/src/hydrogen.h      Thu Oct 11 03:52:58 2012
@@ -268,6 +268,7 @@
    void ReplaceCheckedValues();
    void EliminateRedundantBoundsChecks();
    void DehoistSimpleArrayIndexComputations();
+  void DeadCodeElimination();
    void PropagateDeoptimizingMark();

    // Returns false if there are phi-uses of the arguments-object
=======================================
--- /branches/bleeding_edge/src/property-details.h      Mon Aug 27 06:47:34 2012
+++ /branches/bleeding_edge/src/property-details.h      Thu Oct 11 03:52:58 2012
@@ -96,7 +96,9 @@

    PropertyType type() { return TypeField::decode(value_); }

-  PropertyAttributes attributes() { return  
AttributesField::decode(value_); }
+  PropertyAttributes attributes() const {
+    return AttributesField::decode(value_);
+  }

    int dictionary_index() {
      return DictionaryStorageField::decode(value_);
@@ -112,10 +114,10 @@
      return DictionaryStorageField::is_valid(index);
    }

-  bool IsReadOnly() { return (attributes() & READ_ONLY) != 0; }
-  bool IsDontDelete() { return (attributes() & DONT_DELETE) != 0; }
-  bool IsDontEnum() { return (attributes() & DONT_ENUM) != 0; }
-  bool IsDeleted() { return DeletedField::decode(value_) != 0;}
+  bool IsReadOnly() const { return (attributes() & READ_ONLY) != 0; }
+  bool IsDontDelete() const { return (attributes() & DONT_DELETE) != 0; }
+  bool IsDontEnum() const { return (attributes() & DONT_ENUM) != 0; }
+  bool IsDeleted() const { return DeletedField::decode(value_) != 0;}

    // Bit fields in value_ (type, shift, size). Must be public so the
    // constants can be embedded in generated code.
=======================================
--- /branches/bleeding_edge/src/utils.h Wed Sep 26 07:42:08 2012
+++ /branches/bleeding_edge/src/utils.h Thu Oct 11 03:52:58 2012
@@ -862,7 +862,11 @@
   public:
    EmbeddedContainer() : elems_() { }

-  int length() { return NumElements; }
+  int length() const { return NumElements; }
+  const ElementType& operator[](int i) const {
+    ASSERT(i < length());
+    return elems_[i];
+  }
    ElementType& operator[](int i) {
      ASSERT(i < length());
      return elems_[i];
@@ -876,7 +880,12 @@
  template<typename ElementType>
  class EmbeddedContainer<ElementType, 0> {
   public:
-  int length() { return 0; }
+  int length() const { return 0; }
+  const ElementType& operator[](int i) const {
+    UNREACHABLE();
+    static ElementType t = 0;
+    return t;
+  }
    ElementType& operator[](int i) {
      UNREACHABLE();
      static ElementType t = 0;
=======================================
--- /branches/bleeding_edge/tools/run-tests.py  Fri Sep 28 08:53:46 2012
+++ /branches/bleeding_edge/tools/run-tests.py  Thu Oct 11 03:52:58 2012
@@ -56,9 +56,9 @@
                   ["--stress-opt", "--always-opt"],
                   ["--nocrankshaft"]]
  MODE_FLAGS = {
-    "debug"   : ["--nobreak-on-abort", "--enable-slow-asserts",
-                 "--debug-code", "--verify-heap"],
-    "release" : ["--nobreak-on-abort"]}
+    "debug"   : ["--nobreak-on-abort", "--nodead-code-elimination",
+                 "--enable-slow-asserts", "--debug-code", "--verify-heap"],
+    "release" : ["--nobreak-on-abort", "--nodead-code-elimination"]}

  def BuildOptions():
=======================================
--- /branches/bleeding_edge/tools/test.py       Mon Jul 30 02:09:13 2012
+++ /branches/bleeding_edge/tools/test.py       Thu Oct 11 03:52:58 2012
@@ -684,8 +684,9 @@
      'debug'   : '_g',
      'release' : '' }
  FLAGS = {
-    'debug'   :  
['--nobreak-on-abort', '--enable-slow-asserts', '--debug-code', '--verify-heap'],
-    'release' : ['--nobreak-on-abort']}
+    'debug'   : ['--nobreak-on-abort', '--nodead-code-elimination',
+                 '--enable-slow-asserts', '--debug-code', '--verify-heap'],
+    'release' : ['--nobreak-on-abort', '--nodead-code-elimination']}
  TIMEOUT_SCALEFACTOR = {
      'debug'   : 4,
      'release' : 1 }