Improve GVN handling of ElementTransitions.

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 168 matching lines @@
   V(UnaryMathOperation)                        \
   V(UnknownOSRValue)                           \
   V(UseConst)                                  \
   V(ValueOf)
 
 #define GVN_FLAG_LIST(V)                       \
   V(Calls)                                     \
   V(InobjectFields)                            \
   V(BackingStoreFields)                        \
   V(ElementsKind)                              \
+  V(ElementsPointer)                           \
   V(ArrayElements)                             \
   V(DoubleArrayElements)                       \
   V(SpecializedArrayElements)                  \
   V(GlobalVars)                                \
   V(Maps)                                      \
   V(ArrayLengths)                              \
   V(ContextSlots)                              \
   V(OsrEntries)
 
 #define DECLARE_ABSTRACT_INSTRUCTION(type)          \
@@ skipping 440 matching lines @@
   void ClearAllSideEffects() {
     gvn_flags_.Remove(AllSideEffectsFlagSet());
   }
   bool HasSideEffects() const {
     return gvn_flags_.ContainsAnyOf(AllSideEffectsFlagSet());
   }
   bool HasObservableSideEffects() const {
     return gvn_flags_.ContainsAnyOf(AllObservableSideEffectsFlagSet());
   }
 
+  GVNFlagSet DependsOnFlags() const {
+    GVNFlagSet result = gvn_flags_;
+    result.Intersect(AllDependsOnFlagSet());
+    return result;
+  }
+
+  GVNFlagSet SideEffectFlags() const {
+    GVNFlagSet result = gvn_flags_;
+    result.Intersect(AllSideEffectsFlagSet());
+    return result;
+  }
+
   GVNFlagSet ChangesFlags() const {
     GVNFlagSet result = gvn_flags_;
     result.Intersect(AllChangesFlagSet());
     return result;
   }
 
   GVNFlagSet ObservableChangesFlags() const {
     GVNFlagSet result = gvn_flags_;
     result.Intersect(AllChangesFlagSet());
     result.Intersect(AllObservableSideEffectsFlagSet());
     return result;
   }
 
+  virtual bool HasOneTimeSideEffects() const {
+    return false;
+  }
+
   Range* range() const { return range_; }
   bool HasRange() const { return range_ != NULL; }
   void AddNewRange(Range* r);
   void RemoveLastAddedRange();
   void ComputeInitialRange();
 
   // Representation helpers.
   virtual Representation RequiredInputRepresentation(int index) = 0;
 
   virtual Representation InferredRepresentation() {
@@ skipping 43 matching lines @@
     ASSERT(block_ != NULL);
     block_ = NULL;
   }
 
   void set_representation(Representation r) {
     // Representation is set-once.
     ASSERT(representation_.IsNone() && !r.IsNone());
     representation_ = r;
   }
 
+  static GVNFlagSet AllDependsOnFlagSet() {
+    GVNFlagSet result;
+    // Create changes mask.
+#define ADD_FLAG(type) result.Add(kDependsOn##type);
+  GVN_FLAG_LIST(ADD_FLAG)
+#undef ADD_FLAG
+    return result;
+  }
+
   static GVNFlagSet AllChangesFlagSet() {
     GVNFlagSet result;
     // Create changes mask.
 #define ADD_FLAG(type) result.Add(kChanges##type);
   GVN_FLAG_LIST(ADD_FLAG)
 #undef ADD_FLAG
     return result;
   }
 
   // A flag mask to mark an instruction as having arbitrary side effects.
   static GVNFlagSet AllSideEffectsFlagSet() {
     GVNFlagSet result = AllChangesFlagSet();
     result.Remove(kChangesOsrEntries);
     return result;
   }
 
   // A flag mask of all side effects that can make observable changes in
   // an executing program (i.e. are not safe to repeat, move or remove);
   static GVNFlagSet AllObservableSideEffectsFlagSet() {
     GVNFlagSet result = AllChangesFlagSet();
     result.Remove(kChangesElementsKind);
+    result.Remove(kChangesElementsPointer);
+    result.Remove(kChangesMaps);
     return result;
   }
 
   // Remove the matching use from the use list if present.  Returns the
   // removed list node or NULL.
   HUseListNode* RemoveUse(HValue* value, int index);
 
   void RegisterUse(int index, HValue* new_value);
 
   HBasicBlock* block_;
@@ skipping 1157 matching lines @@
  private:
   BuiltinFunctionId op_;
 };
 
 
 class HLoadElements: public HUnaryOperation {
  public:
   explicit HLoadElements(HValue* value) : HUnaryOperation(value) {
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
-    SetGVNFlag(kDependsOnMaps);
-    SetGVNFlag(kDependsOnElementsKind);
+    SetGVNFlag(kDependsOnElementsPointer);
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
 
   DECLARE_CONCRETE_INSTRUCTION(LoadElements)
 
  protected:
   virtual bool DataEquals(HValue* other) { return true; }
@@ skipping 30 matching lines @@
             CompareMapMode mode = REQUIRE_EXACT_MAP)
       : map_(map),
         mode_(mode) {
     SetOperandAt(0, value);
     // If callers don't depend on a typecheck, they can pass in NULL. In that
     // case we use a copy of the |value| argument as a dummy value.
     SetOperandAt(1, typecheck != NULL ? typecheck : value);
     set_representation(Representation::Tagged());
     SetFlag(kUseGVN);
     SetGVNFlag(kDependsOnMaps);
+    // If the map to check doesn't have the untransitioned elements, it must not
+    // be hoisted above TransitionElements instructions.
+    if (mode == REQUIRE_EXACT_MAP || !map->has_fast_smi_only_elements()) {
+      SetGVNFlag(kDependsOnElementsKind);
+    }
     has_element_transitions_ =
         map->LookupElementsTransitionMap(FAST_DOUBLE_ELEMENTS, NULL) != NULL ||
         map->LookupElementsTransitionMap(FAST_ELEMENTS, NULL) != NULL;
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
   virtual void PrintDataTo(StringStream* stream);
   virtual HType CalculateInferredType();
@@ skipping 2143 matching lines @@
 
 class HTransitionElementsKind: public HTemplateInstruction<1> {
  public:
   HTransitionElementsKind(HValue* object,
                           Handle<Map> original_map,
                           Handle<Map> transitioned_map)
       : original_map_(original_map),
         transitioned_map_(transitioned_map) {
     SetOperandAt(0, object);
     SetFlag(kUseGVN);
+    SetGVNFlag(kDependsOnMaps);

[fschneider, 2012/02/02 14:59:50]

There is currently no instruction that has kChangesMaps set (except calls that
have all side effects).

[danno, 2012/02/06 16:54:57]

But if we ever add one, then it will be incorrect to hoist the transitions about
it, so I'd prefer to keep this in.
On 2012/02/02 14:59:50, fschneider wrote:

     SetGVNFlag(kChangesElementsKind);
+    if (original_map->has_fast_double_elements()) {
+      SetGVNFlag(kChangesElementsPointer);
+      SetGVNFlag(kDependsOnElementsPointer);
+      SetGVNFlag(kDependsOnDoubleArrayElements);
+    } else if (transitioned_map->has_fast_double_elements()) {
+      SetGVNFlag(kChangesElementsPointer);
+      SetGVNFlag(kDependsOnElementsPointer);
+      SetGVNFlag(kDependsOnArrayElements);
+    }
     set_representation(Representation::Tagged());
   }
 
   virtual Representation RequiredInputRepresentation(int index) {
     return Representation::Tagged();
   }
 
+  virtual bool HasOneTimeSideEffects() const {

[fschneider, 2012/02/02 14:59:50]

It may be not worth making a predicate that applies to exactly one instruction a
separate virtual function (unless we plan to get more instructions like this).

 I'd just use IsTransitionElementsKind() for now.

[danno, 2012/02/06 16:54:57]

Done.

+    return true;
+  }
+
   HValue* object() { return OperandAt(0); }
   Handle<Map> original_map() { return original_map_; }
   Handle<Map> transitioned_map() { return transitioned_map_; }
 
   virtual void PrintDataTo(StringStream* stream);
 
   DECLARE_CONCRETE_INSTRUCTION(TransitionElementsKind)
 
  protected:
   virtual bool DataEquals(HValue* other) {
@@ skipping 403 matching lines @@
 
   DECLARE_CONCRETE_INSTRUCTION(In)
 };
 
 #undef DECLARE_INSTRUCTION
 #undef DECLARE_CONCRETE_INSTRUCTION
 
 } }  // namespace v8::internal
 
 #endif  // V8_HYDROGEN_INSTRUCTIONS_H_