[v8-dev] [v8] r12697 committed - Added a simple dead code removal phase....

codesite-noreply Thu, 11 Oct 2012 03:55:11 -0700

Revision: 12697
Author:   [email protected]
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 fixedpoint. We consider an instruction dead if it is unused, has no observableside effects and is deletable. The last part of the condition is currentlynot very nice: We basically have to whitelist "safe" instructions, becausewe are missing more detailed dependencies and/or more detailed tracking ofside effects.

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

This patch includes a few const-correctness fixes, most of them werenecessary 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 codeelimination")


 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 1804:06:05 2012+++ /branches/bleeding_edge/src/hydrogen-instructions.cc Thu Oct 1103: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:242012+++ /branches/bleeding_edge/src/hydrogen-instructions.h Thu Oct 11 03:52:582012

@@ -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 forsure.

+  // 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 forsure.

+  // 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 forsure.

+  // 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 forsure.

+  //  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() { returnAttributesField::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 }

--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev

[v8-dev] [v8] r12697 committed - Added a simple dead code removal phase....

Reply via email to