[turbofan] Improve the store-store elimination.

src/compiler/store-store-elimination.h

 // Copyright 2016 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_COMPILER_STORE_STORE_ELIMINATION_H_
 #define V8_COMPILER_STORE_STORE_ELIMINATION_H_
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/graph-reducer.h"
 #include "src/compiler/js-graph.h"
+#include "src/zone-containers.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-// Forward declarations.
-class CommonOperatorBuilder;
-class JSGraph;
-
 class StoreStoreElimination final {
  public:
-  StoreStoreElimination(JSGraph* js_graph, Zone* temp_zone);
-  ~StoreStoreElimination();
-  void Run();
+  static void Run(JSGraph* js_graph, Zone* temp_zone);
+};

[Jarin, 2016/07/20 11:43:33]

All the stuff below should go to the .cc file since it is local to the pass.

[bgeron, 2016/07/20 16:27:17]

Done. I put it in an anonymous namespace.

+
+// 16 bits was chosen fairly arbitrarily; it seems enough now. 8 bits is too
+// few.
+typedef uint16_t StoreOffset;
+
+struct StoreObservation {

[Jarin, 2016/07/20 11:43:33]

The name is a bit confusing because it seems to describe a field that is not
observed.

[bgeron, 2016/07/20 16:27:17]

Changed to UnobservableStore.

+  NodeId id_;
+  StoreOffset offset_;
+};
+
+bool operator==(StoreObservation, StoreObservation);
+bool operator<(StoreObservation, StoreObservation);
+std::ostream& operator<<(std::ostream&, StoreObservation);
+
+// Instances of UnobservablesSet are immutable. They represent either a set of
+// StoreObservations, or the "undetermined empty set".
+//
+// The size of an instance should be the size of a pointer, plus additional
+// space in the zone for determined UnobservablesSets. Copying an
+// UnobservablesSet allocates no memory.
+class UnobservablesSet final {
+ public:
+  static UnobservablesSet Undetermined();
+  static UnobservablesSet DeterminedEmpty(Zone* zone);
+  UnobservablesSet();  // undetermined
+  UnobservablesSet(const UnobservablesSet& other) : set_(other.set_) {}
+  ~UnobservablesSet() {}

[Jarin, 2016/07/20 11:43:33]

Why is the destructor here?

[bgeron, 2016/07/20 16:27:17]

Because I thought that the implicitly generated destructor would destroy the
pointer fields. Instead it's an empty method. Removed.

+
+  UnobservablesSet Intersect(UnobservablesSet other, Zone* zone) const;
+  UnobservablesSet Add(StoreObservation obs, Zone* zone) const;
+  UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;
+
+  const ZoneSet<StoreObservation>* set() const { return set_; }
+
+  bool IsUndetermined() const { return set_ == nullptr; }
+  bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
+  bool Contains(StoreObservation obs) const {
+    return set_ != nullptr && (set_->find(obs) != set_->end());
+  }
+
+  bool operator==(const UnobservablesSet& other) const;
+  bool operator!=(const UnobservablesSet& other) const;
+
+ private:
+  explicit UnobservablesSet(const ZoneSet<StoreObservation>* set) : set_(set) {}
+  const ZoneSet<StoreObservation>* set_;
+};
+
+std::ostream& operator<<(std::ostream& os, UnobservablesSet set);
+
+class StoreStoreFinder final : public AdvancedReducer {
+ public:
+  StoreStoreFinder(Editor* editor, JSGraph* js_graph, Zone* temp_zone);
+  ~StoreStoreFinder();
+
+  const ZoneSet<Node*>& to_remove_const() { return to_remove_; }
+
+  virtual Reduction Reduce(Node* node);

[Jarin, 2016/07/20 11:43:33]

I have difficulty understanding why this is a reducer - reducers are forward
passes, store elimination is backwards.

[bgeron, 2016/07/20 16:27:17]

Changed as discussed.

 
  private:
   static bool IsEligibleNode(Node* node);
-  void ReduceEligibleNode(Node* node);
+  Reduction ReduceEligibleNode(Node* node);
+  UnobservablesSet RecomputeUseIntersection(Node* node);
+  UnobservablesSet RecomputeSet(Node* node, UnobservablesSet uses);
+  static bool CanObserveNothing(Node* node);
+  static bool CanObserveAnything(Node* node);
+
   JSGraph* jsgraph() const { return jsgraph_; }
   Zone* temp_zone() const { return temp_zone_; }
+  ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; }
+  ZoneSet<Node*>& to_remove() { return to_remove_; }
 
   JSGraph* const jsgraph_;
   Zone* const temp_zone_;
+  // Maps node IDs to UnobservableNodeSets.
+  ZoneVector<UnobservablesSet> unobservable_;
+  ZoneSet<Node*> to_remove_;
 };
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_COMPILER_STORE_STORE_ELIMINATION_H_