Improve dead code elimination by transitively marking live code and removing all dead code. Replace…

src/hydrogen-instructions.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 776 matching lines @@
     // Track instructions that are dominating side effects. If an instruction
     // sets this flag, it must implement SetSideEffectDominator() and should
     // indicate which side effects to track by setting GVN flags.
     kTrackSideEffectDominators,
     kCanOverflow,
     kBailoutOnMinusZero,
     kCanBeDivByZero,
     kDeoptimizeOnUndefined,
     kIsArguments,
     kTruncatingToInt32,
+    // Set after an instruction is killed.
     kIsDead,
     // Instructions that are allowed to produce full range unsigned integer
     // values are marked with kUint32 flag. If arithmetic shift or a load from
     // EXTERNAL_UNSIGNED_INT_ELEMENTS array is not marked with this flag
     // it will deoptimize if result does not fit into signed integer range.
     // HGraph::ComputeSafeUint32Operations is responsible for setting this
     // flag.
     kUint32,
     // If a phi is involved in the evaluation of a numeric constraint the
     // recursion can cause an endless cycle: we use this flag to exit the loop.
     kNumericConstraintEvaluationInProgress,
     // This flag is set to true after the SetupInformativeDefinitions() pass
     // has processed this instruction.
     kIDefsProcessingDone,
     kHasNoObservableSideEffects,
+    // Indicates the instruction is live during dead code elimination.
+    kIsLive,
     kLastFlag = kIDefsProcessingDone
   };
 
   STATIC_ASSERT(kLastFlag < kBitsPerInt);
 
   static const int kChangesToDependsFlagsLeftShift = 1;
 
   static GVNFlag ChangesFlagFromInt(int x) {
     return static_cast<GVNFlag>(x * 2);
   }
@@ skipping 242 matching lines @@
 
   virtual HType CalculateInferredType();
 
   // This function must be overridden for instructions which have the
   // kTrackSideEffectDominators flag set, to track instructions that are
   // dominating side effects.
   virtual void SetSideEffectDominator(GVNFlag side_effect, HValue* dominator) {
     UNREACHABLE();
   }
 
-  bool IsDead() const {
-    return HasNoUses() && !HasObservableSideEffects() && IsDeletable();
+  // Check if this instruction has some reason that prevents elimination.
+  bool CannotBeEliminated() const {
+    return HasObservableSideEffects() || !IsDeletable();
   }
 
 #ifdef DEBUG
   virtual void Verify() = 0;
 #endif
 
   bool IsRelationTrue(NumericRelation relation,
                       HValue* other,
                       int offset = 0,
                       int scale = 0);
@@ skipping 1876 matching lines @@
   virtual bool DataEquals(HValue* other) { return true; }
 };
 
 
 class HPhi: public HValue {
  public:
   HPhi(int merged_index, Zone* zone)
       : inputs_(2, zone),
         merged_index_(merged_index),
         phi_id_(-1),
-        is_live_(false),
         is_convertible_to_integer_(true) {
     for (int i = 0; i < Representation::kNumRepresentations; i++) {
       non_phi_uses_[i] = 0;
       indirect_uses_[i] = 0;
     }
     ASSERT(merged_index >= 0);
     SetFlag(kFlexibleRepresentation);
   }
 
   virtual Representation RepresentationFromInputs();
 
   virtual Range* InferRange(Zone* zone);
   virtual void InferRepresentation(HInferRepresentation* h_infer);
   Representation RepresentationFromUseRequirements();
   virtual Representation RequiredInputRepresentation(int index) {
     return representation();
   }
   virtual HType CalculateInferredType();
   virtual int OperandCount() { return inputs_.length(); }
   virtual HValue* OperandAt(int index) const { return inputs_[index]; }
   HValue* GetRedundantReplacement();
   void AddInput(HValue* value);
   bool HasRealUses();
 
-  bool IsReceiver() { return merged_index_ == 0; }
+  bool IsReceiver() const { return merged_index_ == 0; }
 
   int merged_index() const { return merged_index_; }
 
   virtual void AddInformativeDefinitions();
 
   virtual void PrintTo(StringStream* stream);
 
 #ifdef DEBUG
   virtual void Verify();
 #endif
@@ skipping 14 matching lines @@
   int tagged_indirect_uses() const {
     return indirect_uses_[Representation::kTagged];
   }
   int int32_indirect_uses() const {
     return indirect_uses_[Representation::kInteger32];
   }
   int double_indirect_uses() const {
     return indirect_uses_[Representation::kDouble];
   }
   int phi_id() { return phi_id_; }
-  bool is_live() { return is_live_; }
-  void set_is_live(bool b) { is_live_ = b; }
 
   static HPhi* cast(HValue* value) {
     ASSERT(value->IsPhi());
     return reinterpret_cast<HPhi*>(value);
   }
   virtual Opcode opcode() const { return HValue::kPhi; }
 
   virtual bool IsConvertibleToInteger() const {
     return is_convertible_to_integer_;
   }
@@ skipping 11 matching lines @@
                  id(), Mnemonic(), input->id(), input->Mnemonic(), i);
         }
         return false;
       }
     }
     return true;
   }
 
   void SimplifyConstantInputs();
 
+  // TODO(titzer): we can't eliminate the receiver for generating backtraces
+  virtual bool IsDeletable() const { return !IsReceiver(); }
+
  protected:
   virtual void DeleteFromGraph();
   virtual void InternalSetOperandAt(int index, HValue* value) {
     inputs_[index] = value;
   }
 
   virtual bool IsRelationTrueInternal(NumericRelation relation,
                                       HValue* other,
                                       int offset = 0,
                                       int scale = 0);
 
  private:
   ZoneList<HValue*> inputs_;
   int merged_index_;
 
   int non_phi_uses_[Representation::kNumRepresentations];
   int indirect_uses_[Representation::kNumRepresentations];
   int phi_id_;
-  bool is_live_;
   bool is_convertible_to_integer_;
 };
 
 
 class HInductionVariableAnnotation : public HUnaryOperation {
  public:
   static HInductionVariableAnnotation* AddToGraph(HPhi* phi,
                                                   NumericRelation relation,
                                                   int operand_index);
 
@@ skipping 3368 matching lines @@
   virtual bool IsDeletable() const { return true; }
 };
 
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_