Lattice-based representation inference, powered by left/right specific type feedback for BinaryOps …

src/hydrogen-instructions.h

Index: src/hydrogen-instructions.h
diff --git a/src/hydrogen-instructions.h b/src/hydrogen-instructions.h
index c253d06cf0f0e0c241019b98cbfc4412254443c7..c7f9226d29e037a89eb0afdc1f9f68d332518aec 100644
--- a/src/hydrogen-instructions.h
+++ b/src/hydrogen-instructions.h
@@ -45,6 +45,7 @@ namespace internal {
 // Forward declarations.
 class HBasicBlock;
 class HEnvironment;
+class HInferRepresentation;
 class HInstruction;
 class HLoopInformation;
 class HValue;
@@ -307,9 +308,9 @@ class Representation {
  public:
   enum Kind {
     kNone,
-    kTagged,
-    kDouble,
     kInteger32,
+    kDouble,
+    kTagged,
     kExternal,
     kNumRepresentations
   };
@@ -326,6 +327,12 @@ class Representation {
     return kind_ == other.kind_;
   }
 
+  bool is_more_general_than(const Representation& other) {
+    ASSERT(kind_ != kExternal);
+    ASSERT(other.kind_ != kExternal);
+    return kind_ > other.kind_;
+  }
+
   Kind kind() const { return static_cast<Kind>(kind_); }
   bool IsNone() const { return kind_ == kNone; }
   bool IsTagged() const { return kind_ == kTagged; }
@@ -628,13 +635,15 @@ class HValue: public ZoneObject {
   virtual bool EmitAtUses() { return false; }
   Representation representation() const { return representation_; }
   void ChangeRepresentation(Representation r) {
-    // Representation was already set and is allowed to be changed.
-    ASSERT(!r.IsNone());
     ASSERT(CheckFlag(kFlexibleRepresentation));
     RepresentationChanged(r);
     representation_ = r;
+    if (r.IsTagged()) {
+      // Tagged is the bottom of the lattice, don't go any further.
+      ClearFlag(kFlexibleRepresentation);
+    }
   }
-  void AssumeRepresentation(Representation r);
+  virtual void AssumeRepresentation(Representation r);
 
   virtual bool IsConvertibleToInteger() const { return true; }
 
@@ -732,16 +741,11 @@ class HValue: public ZoneObject {
   void ComputeInitialRange(Zone* zone);
 
   // Representation helpers.
-  virtual Representation RequiredInputRepresentation(int index) = 0;
-
-  virtual Representation InferredRepresentation() {
-    return representation();
-  }
-
-  // Type feedback access.
-  virtual Representation ObservedInputRepresentation(int index) {
-    return RequiredInputRepresentation(index);
+  virtual Representation observed_input_representation(int index) {
+    return Representation::None();
   }
+  virtual Representation RequiredInputRepresentation(int index) = 0;
+  virtual void InferRepresentation(HInferRepresentation* h_infer);
 
   // This gives the instruction an opportunity to replace itself with an
   // instruction that does the same in some better way.  To replace an
@@ -789,7 +793,18 @@ class HValue: public ZoneObject {
     UNREACHABLE();
     return false;
   }
+
+  virtual Representation RepresentationFromInputs() {
+    return representation();
+  }
+  Representation RepresentationFromUses();
+  virtual void UpdateRepresentation(Representation new_rep,
+                                    HInferRepresentation* h_infer,
+                                    const char* reason);
+  void AddDependantsToWorklist(HInferRepresentation* h_infer);
+
   virtual void RepresentationChanged(Representation to) { }
+
   virtual Range* InferRange(Zone* zone);
   virtual void DeleteFromGraph() = 0;
   virtual void InternalSetOperandAt(int index, HValue* value) = 0;
@@ -799,7 +814,6 @@ class HValue: public ZoneObject {
   }
 
   void set_representation(Representation r) {
-    // Representation is set-once.
     ASSERT(representation_.IsNone() && !r.IsNone());
     representation_ = r;
   }
@@ -1112,6 +1126,7 @@ class HBranch: public HUnaryControlInstruction {
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::None();
   }
+  virtual Representation observed_input_representation(int index);
 
   ToBooleanStub::Types expected_input_types() const {
     return expected_input_types_;
@@ -1316,14 +1331,24 @@ class HClampToUint8: public HUnaryOperation {
 };
 
 
+enum RemovableSimulate {
+  REMOVABLE,

[danno, 2012/11/14 10:38:22]

make this REMOVABLE_SIMULATE?

[Jakob Kummerow, 2012/11/14 15:53:23]

Done.

+  FIXED
+};
+
+
 class HSimulate: public HInstruction {
  public:
-  HSimulate(BailoutId ast_id, int pop_count, Zone* zone)
+  HSimulate(BailoutId ast_id,
+            int pop_count,
+            Zone* zone,
+            RemovableSimulate removable)
       : ast_id_(ast_id),
         pop_count_(pop_count),
         values_(2, zone),
         assigned_indexes_(2, zone),
-        zone_(zone) {}
+        zone_(zone),
+        removable_(removable) {}
   virtual ~HSimulate() {}
 
   virtual void PrintDataTo(StringStream* stream);
@@ -1357,6 +1382,9 @@ class HSimulate: public HInstruction {
     return Representation::None();
   }
 
+  void MergeInto(HSimulate* other);
+  bool is_candidate_for_removal() { return removable_ == REMOVABLE; }
+
   DECLARE_CONCRETE_INSTRUCTION(Simulate)
 
 #ifdef DEBUG
@@ -1383,6 +1411,7 @@ class HSimulate: public HInstruction {
   ZoneList<HValue*> values_;
   ZoneList<int> assigned_indexes_;
   Zone* zone_;
+  RemovableSimulate removable_;
 };
 
 
@@ -2009,6 +2038,9 @@ class HBitNot: public HUnaryOperation {
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Integer32();
   }
+  virtual Representation observed_input_representation(int index) {
+    return Representation::Integer32();
+  }
   virtual HType CalculateInferredType();
 
   virtual HValue* Canonicalize();
@@ -2036,7 +2068,7 @@ class HUnaryMathOperation: public HTemplateInstruction<2> {
         set_representation(Representation::Integer32());
         break;
       case kMathAbs:
-        set_representation(Representation::Tagged());
+        // Not setting representation here: it is None intentionally.
         SetFlag(kFlexibleRepresentation);
         SetGVNFlag(kChangesNewSpacePromotion);
         break;
@@ -2216,6 +2248,7 @@ class HCheckMaps: public HTemplateInstruction<2> {
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
+
   virtual void PrintDataTo(StringStream* stream);
   virtual HType CalculateInferredType();
 
@@ -2443,13 +2476,14 @@ class HPhi: public HValue {
       indirect_uses_[i] = 0;
     }
     ASSERT(merged_index >= 0);
-    set_representation(Representation::Tagged());
     SetFlag(kFlexibleRepresentation);
   }
 
-  virtual Representation InferredRepresentation();
+  virtual Representation RepresentationFromInputs();
 
   virtual Range* InferRange(Zone* zone);
+  virtual void InferRepresentation(HInferRepresentation* h_infer);
+  Representation RepresentationFromUseRequirements();
   virtual Representation RequiredInputRepresentation(int index) {
     return representation();
   }
@@ -2513,14 +2547,17 @@ class HPhi: public HValue {
   bool AllOperandsConvertibleToInteger() {
     for (int i = 0; i < OperandCount(); ++i) {
       if (!OperandAt(i)->IsConvertibleToInteger()) {
+        if (FLAG_trace_representation) {
+          HValue* input = OperandAt(i);
+          PrintF("#%d %s: Input #%d %s at %d is NCTI\n",
+                 id(), Mnemonic(), input->id(), input->Mnemonic(), i);
+        }
         return false;
       }
     }
     return true;
   }
 
-  void ResetInteger32Uses();
-
  protected:
   virtual void DeleteFromGraph();
   virtual void InternalSetOperandAt(int index, HValue* value) {
@@ -2704,11 +2741,14 @@ class HConstant: public HTemplateInstruction<0> {
 
 class HBinaryOperation: public HTemplateInstruction<3> {
  public:
-  HBinaryOperation(HValue* context, HValue* left, HValue* right) {
+  HBinaryOperation(HValue* context, HValue* left, HValue* right)
+      : observed_output_representation_(Representation::None()) {
     ASSERT(left != NULL && right != NULL);
     SetOperandAt(0, context);
     SetOperandAt(1, left);
     SetOperandAt(2, right);
+    observed_input_representation_[0] = Representation::None();
+    observed_input_representation_[1] = Representation::None();
   }
 
   HValue* context() { return OperandAt(0); }
@@ -2727,11 +2767,33 @@ class HBinaryOperation: public HTemplateInstruction<3> {
     return right();
   }
 
+  void set_observed_input_representation(Representation left,
+                                         Representation right) {
+    observed_input_representation_[0] = left;
+    observed_input_representation_[1] = right;
+  }
+
+  virtual void initialize_output_representation(Representation observed) {
+    observed_output_representation_ = observed;
+  }
+
+  virtual Representation observed_input_representation(int index) {
+    if (index == 0) return Representation::Tagged();
+    return observed_input_representation_[index - 1];
+  }
+
+  virtual Representation RepresentationFromInputs();
+  virtual void AssumeRepresentation(Representation r);
+
   virtual bool IsCommutative() const { return false; }
 
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_ABSTRACT_INSTRUCTION(BinaryOperation)
+
+ private:
+  Representation observed_input_representation_[2];
+  Representation observed_output_representation_;
 };
 
 
@@ -2901,6 +2963,9 @@ class HBoundsCheck: public HTemplateInstruction<2> {
     }
     return Representation::Integer32();
   }
+  virtual Representation observed_input_representation(int index) {
+    return Representation::Integer32();
+  }
 
   virtual void PrintDataTo(StringStream* stream);
 
@@ -2919,12 +2984,9 @@ class HBitwiseBinaryOperation: public HBinaryOperation {
  public:
   HBitwiseBinaryOperation(HValue* context, HValue* left, HValue* right)
       : HBinaryOperation(context, left, right) {
-    set_representation(Representation::Tagged());
     SetFlag(kFlexibleRepresentation);
+    SetFlag(kTruncatingToInt32);
     SetAllSideEffects();
-    observed_input_representation_[0] = Representation::Tagged();
-    observed_input_representation_[1] = Representation::None();
-    observed_input_representation_[2] = Representation::None();
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
@@ -2937,28 +2999,32 @@ class HBitwiseBinaryOperation: public HBinaryOperation {
     if (!to.IsTagged()) {
       ASSERT(to.IsInteger32());
       ClearAllSideEffects();
-      SetFlag(kTruncatingToInt32);
       SetFlag(kUseGVN);
+    } else {
+      SetAllSideEffects();
+      ClearFlag(kUseGVN);
     }
   }
 
-  virtual HType CalculateInferredType();
-
-  virtual Representation ObservedInputRepresentation(int index) {
-    return observed_input_representation_[index];
+  virtual void UpdateRepresentation(Representation new_rep,
+                                    HInferRepresentation* h_infer,
+                                    const char* reason) {
+    // We only generate either int32 or generic tagged bitwise operations.
+    if (new_rep.IsDouble()) new_rep = Representation::Integer32();
+    HValue::UpdateRepresentation(new_rep, h_infer, reason);
   }
 
-  void InitializeObservedInputRepresentation(Representation r) {
-    observed_input_representation_[1] = r;
-    observed_input_representation_[2] = r;
+  virtual void initialize_output_representation(Representation observed) {
+    if (observed.IsDouble()) observed = Representation::Integer32();
+    HBinaryOperation::initialize_output_representation(observed);
   }
 
+  virtual HType CalculateInferredType();
+
   DECLARE_ABSTRACT_INSTRUCTION(BitwiseBinaryOperation)
 
  private:
   virtual bool IsDeletable() const { return true; }
-
-  Representation observed_input_representation_[3];
 };
 
 
@@ -2991,13 +3057,15 @@ class HArithmeticBinaryOperation: public HBinaryOperation {
  public:
   HArithmeticBinaryOperation(HValue* context, HValue* left, HValue* right)
       : HBinaryOperation(context, left, right) {
-    set_representation(Representation::Tagged());
-    SetFlag(kFlexibleRepresentation);
     SetAllSideEffects();
+    SetFlag(kFlexibleRepresentation);
   }
 
   virtual void RepresentationChanged(Representation to) {
-    if (!to.IsTagged()) {
+    if (to.IsTagged()) {
+      SetAllSideEffects();
+      ClearFlag(kUseGVN);
+    } else {
       ClearAllSideEffects();
       SetFlag(kUseGVN);
     }
@@ -3010,13 +3078,6 @@ class HArithmeticBinaryOperation: public HBinaryOperation {
         : representation();
   }
 
-  virtual Representation InferredRepresentation() {
-    if (left()->representation().Equals(right()->representation())) {
-      return left()->representation();
-    }
-    return HValue::InferredRepresentation();
-  }
-
  private:
   virtual bool IsDeletable() const { return true; }
 };
@@ -3035,11 +3096,9 @@ class HCompareGeneric: public HBinaryOperation {
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
-    return Representation::Tagged();
-  }
-
-  Representation GetInputRepresentation() const {
-    return Representation::Tagged();
+    return index == 0
+        ? Representation::Tagged()
+        : representation();
   }
 
   Token::Value token() const { return token_; }
@@ -3058,6 +3117,7 @@ class HCompareIDAndBranch: public HTemplateControlInstruction<2, 2> {
  public:
   HCompareIDAndBranch(HValue* left, HValue* right, Token::Value token)
       : token_(token) {
+    SetFlag(kFlexibleRepresentation);
     ASSERT(Token::IsCompareOp(token));
     SetOperandAt(0, left);
     SetOperandAt(1, right);
@@ -3067,20 +3127,26 @@ class HCompareIDAndBranch: public HTemplateControlInstruction<2, 2> {
   HValue* right() { return OperandAt(1); }
   Token::Value token() const { return token_; }
 
-  void SetInputRepresentation(Representation r);
-  Representation GetInputRepresentation() const {
-    return input_representation_;
+  void set_observed_input_representation(Representation left,
+                                         Representation right) {
+      observed_input_representation_[0] = left;
+      observed_input_representation_[1] = right;
   }
 
+  virtual void InferRepresentation(HInferRepresentation* h_infer);
+
   virtual Representation RequiredInputRepresentation(int index) {
-    return input_representation_;
+    return representation();
+  }
+  virtual Representation observed_input_representation(int index) {
+    return observed_input_representation_[index];
   }
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(CompareIDAndBranch)
 
  private:
-  Representation input_representation_;
+  Representation observed_input_representation_[2];
   Token::Value token_;
 };
 
@@ -3141,6 +3207,9 @@ class HIsNilAndBranch: public HUnaryControlInstruction {
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
+  virtual Representation observed_input_representation(int index) {
+    return Representation::Tagged();
+  }
 
   DECLARE_CONCRETE_INSTRUCTION(IsNilAndBranch)
 
@@ -3418,6 +3487,9 @@ class HPower: public HTemplateInstruction<2> {
       ? Representation::Double()
       : Representation::None();
   }
+  virtual Representation observed_input_representation(int index) {
+    return RequiredInputRepresentation(index);
+  }
 
   DECLARE_CONCRETE_INSTRUCTION(Power)
 
@@ -3603,14 +3675,19 @@ class HMathMinMax: public HArithmeticBinaryOperation {
         operation_(op) { }
 
   virtual Representation RequiredInputRepresentation(int index) {
-      return index == 0
-          ? Representation::Tagged()
-          : representation();
-    }
+    return index == 0 ? Representation::Tagged()
+                      : representation();
+  }
 
-  virtual Representation InferredRepresentation() {
-    if (left()->representation().IsInteger32() &&
-        right()->representation().IsInteger32()) {
+  virtual Representation observed_input_representation(int index) {
+    return RequiredInputRepresentation(index);
+  }
+
+  virtual Representation RepresentationFromInputs() {
+    Representation left_rep = left()->representation();
+    Representation right_rep = right()->representation();
+    if ((left_rep.IsNone() || left_rep.IsInteger32()) &&
+        (right_rep.IsNone() || right_rep.IsInteger32())) {
       return Representation::Integer32();
     }
     return Representation::Double();
@@ -4317,6 +4394,10 @@ class HLoadKeyed
     return Representation::None();
   }
 
+  virtual Representation observed_input_representation(int index) {
+    return RequiredInputRepresentation(index);
+  }
+
   virtual void PrintDataTo(StringStream* stream);
 
   bool RequiresHoleCheck() const;
@@ -4508,6 +4589,12 @@ class HStoreKeyed
     } else {
       SetGVNFlag(kChangesArrayElements);
     }
+
+    // EXTERNAL_{UNSIGNED_,}{BYTE,SHORT,INT}_ELEMENTS are truncating.
+    if (elements_kind >= EXTERNAL_BYTE_ELEMENTS &&
+        elements_kind <= EXTERNAL_UNSIGNED_INT_ELEMENTS) {
+      SetFlag(kTruncatingToInt32);
+    }
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
@@ -4533,6 +4620,19 @@ class HStoreKeyed
   bool is_external() const {
     return IsExternalArrayElementsKind(elements_kind());
   }
+
+  virtual Representation observed_input_representation(int index) {
+    if (index < 2) return RequiredInputRepresentation(index);
+    if (IsDoubleOrFloatElementsKind(elements_kind())) {
+      return Representation::Double();
+    }
+    if (is_external()) {
+      return Representation::Integer32();
+    }
+    // For fast object elements kinds, don't assume anything.
+    return Representation::None();
+  }
+
   HValue* elements() { return OperandAt(0); }
   HValue* key() { return OperandAt(1); }
   HValue* value() { return OperandAt(2); }