[turbofan] Improve the store-store elimination.

src/compiler/store-store-elimination.cc

 // 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.
 
+#include <iterator>
+
 #include "src/compiler/store-store-elimination.h"
 
 #include "src/compiler/all-nodes.h"
 #include "src/compiler/js-graph.h"
 #include "src/compiler/node-properties.h"
 #include "src/compiler/simplified-operator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-#define TRACE(fmt, ...)                                              \
-  do {                                                               \
-    if (FLAG_trace_store_elimination) {                              \
-      PrintF("StoreStoreElimination::ReduceEligibleNode: " fmt "\n", \
-             ##__VA_ARGS__);                                         \
-    }                                                                \
+#define TRACE(fmt, ...)                                     \
+  do {                                                      \
+    if (FLAG_trace_store_elimination) {                     \
+      PrintF("StoreStoreFinder: " fmt "\n", ##__VA_ARGS__); \
+    }                                                       \
   } while (false)
 
-// A simple store-store elimination. When the effect chain contains the
-// following sequence,
+// CHECK_EXTRA is like CHECK, but has two or more arguments: a boolean
+// expression, a format string, and any number of extra arguments. The boolean
+// expression will be evaluated at runtime. If it evaluates to false, then an
+// error message will be shown containing the condition, as well as the extra
+// info formatted like with printf.
+#define CHECK_EXTRA(condition, fmt, ...)                                 \
+  do {                                                                   \
+    if (V8_UNLIKELY(!(condition))) {                                     \
+      V8_Fatal(__FILE__, __LINE__, "Check failed: %s. Extra info: " fmt, \
+               #condition, ##__VA_ARGS__);                               \
+    }                                                                    \
+  } while (0)
+
+#ifdef DEBUG
+#define DCHECK_EXTRA(condition, fmt, ...) \
+  CHECK_EXTRA(condition, fmt, ##__VA_ARGS__)
+#else
+#define DCHECK_EXTRA(condition, fmt, ...) ((void)0)
+#endif
+
+// Store-store elimination.
 //
-// - StoreField[[+off_1]](x1, y1)
-// - StoreField[[+off_2]](x2, y2)
-// - StoreField[[+off_3]](x3, y3)
-//   ...
-// - StoreField[[+off_n]](xn, yn)
+// The aim of this optimization is to detect the following pattern in the
+// effect graph:
 //
-// where the xes are the objects and the ys are the values to be stored, then
-// we are going to say that a store is superfluous if the same offset of the
-// same object will be stored to in the future. If off_i == off_j and xi == xj
-// and i < j, then we optimize the i'th StoreField away.
+// - StoreField[+24, kRepTagged](263, ...)
 //
-// This optimization should be initiated on the last StoreField in such a
-// sequence.
+//   ... lots of nodes from which the field at offset 24 of the object
+//       returned by node #263 cannot be observed ...
 //
-// The algorithm works by walking the effect chain from the last StoreField
-// upwards. While walking, we maintain a map {futureStore} from offsets to
-// nodes; initially it is empty. As we walk the effect chain upwards, if
-// futureStore[off] = n, then any store to node {n} with offset {off} is
-// guaranteed to be useless because we do a tagged-width[2] store to that
-// offset of that object in the near future anyway. For example, for this
-// effect chain
+// - StoreField[+24, kRepTagged](263, ...)
 //
-// 71: StoreField(60, 0)
-// 72: StoreField(65, 8)
-// 73: StoreField(63, 8)
-// 74: StoreField(65, 16)
-// 75: StoreField(62, 8)
+// In such situations, the earlier StoreField cannot be observed, and can be
+// eliminated. This optimization should work for any offset and input node, of
+// course.
 //
-// just before we get to 72, we will have futureStore = {8: 63, 16: 65}.
+// The optimization also works across splits. It currently does not work for
+// loops, because we tend to put a stack check in loops, and like deopts,
+// stack checks can observe anything.
+
+// Assumption: every byte of a JS object is only ever accessed through one
+// offset. For instance, byte 15 of a given object may be accessed using a
+// two-byte read at offset 14, or a four-byte read at offset 12, but never
+// both in the same program.
 //
-// Here is the complete process.
-//
-// - We are at the end of a sequence of consecutive StoreFields.
-// - We start out with futureStore = empty.
-// - We then walk the effect chain upwards to find the next StoreField [1].
-//
-//   1. If the offset is not a key of {futureStore} yet, we put it in.
-//   2. If the offset is a key of {futureStore}, but futureStore[offset] is a
-//      different node, we overwrite futureStore[offset] with the current node.
-//   3. If the offset is a key of {futureStore} and futureStore[offset] equals
-//      this node, we eliminate this StoreField.
-//
-//   As long as the current effect input points to a node with a single effect
-//   output, and as long as its opcode is StoreField, we keep traversing
-//   upwards.
-//
-//
-//
-//       footnotes:
-//
-// [1] We make sure that we only traverse the linear part, that is, the part
-//   where every node has exactly one incoming and one outgoing effect edge.
-//   Also, we only keep walking upwards as long as we keep finding consecutive
-//   StoreFields on the same node.
-//
-// [2] This optimization is sound only in certain cases. Specifically, the
-//   presence of a future store to {off} by itself does not automatically mean
-//   that earlier stores to {off} are superfluous: a future narrow store does
-//   not obviate an earlier wide store. However, future stores of a certain
-//   size do obviate stores to the same offset of lesser or equal size.
-//
-//   It turns out that we are most interested in stores of "tagged" size,
-//   which is 8 bytes on 64-bit archs and 4 bit on 32-bit archs. In
-//   {futureStore}, we record future writes that are of at least this size.
-//   The three cases are actually a bit more subtle.
-//
-//   1. If the offset is not a key of {futureStore} and the StoreField is of
-//      "tagged" size or wider, then we put it in.
-//   2. If the offset is present in {futureStore} but the value is different,
-//      then we overwrite the value if the current StoreField is of "tagged"
-//      size or wider.
-//   3. If the offset is present and the value matches the node, and the
-//      current StoreField is AT MOST of "tagged" size, then we eliminate this
-//      StoreField.
-//
-//   Examples of stores that we do not detect as superfluous: 2-byte stores
-//   followed by 2-byte stores to the same offset; 16-byte stores followed by
-//   16-byte stores to the same offset. On ia32, we do not detect consecutive
-//   float64 stores as superfluous, and on x86 we do not detect consecutive
-//   int32 stores as superfluous.
-
-// At a late stage, we realized that this code is more complicated than it
-// needs to be: if we store a set of pairs (offset, node), the code simplifies
-// to 3 cases instead of 6. We could even store a map from nodes to sets of
-// bytes.
-
-StoreStoreElimination::StoreStoreElimination(JSGraph* js_graph, Zone* temp_zone)
-    : jsgraph_(js_graph), temp_zone_(temp_zone) {}
-
-StoreStoreElimination::~StoreStoreElimination() {}
-
-void StoreStoreElimination::Run() {
-  // The store-store elimination performs work on chains of certain types of
-  // nodes. The elimination must be invoked on the lowest node in such a
-  // chain; we have a helper function IsEligibleNode that returns true
-  // precisely on the lowest node in such a chain.
-  //
-  // Because the elimination removes nodes from the graph, even remove nodes
-  // that the elimination was not invoked on, we cannot use a normal
-  // AdvancedReducer but we manually find which nodes to invoke the
-  // elimination on. Then in a next step, we invoke the elimination for each
-  // node that was eligible.
-
-  NodeVector eligible(temp_zone());  // loops over all nodes
-  AllNodes all(temp_zone(), jsgraph()->graph());
-
-  for (Node* node : all.live) {
-    if (IsEligibleNode(node)) {
-      eligible.push_back(node);
-    }
-  }
-
-  for (Node* node : eligible) {
-    ReduceEligibleNode(node);
-  }
-}
+// This implementation needs all dead nodes removed from the graph, and the
+// graph should be trimmed.
 
 namespace {
 
 // 16 bits was chosen fairly arbitrarily; it seems enough now. 8 bits is too
 // few.
-typedef uint16_t Offset;
+typedef uint16_t StoreOffset;
+
+struct UnobservableStore {
+  NodeId id_;
+  StoreOffset offset_;
+
+  bool operator==(const UnobservableStore) const;
+  bool operator!=(const UnobservableStore) const;
+  bool operator<(const UnobservableStore) const;
+};
+
+}  // namespace
+
+std::ostream& operator<<(std::ostream&, const UnobservableStore);
+
+namespace {
+
+// Instances of UnobservablesSet are immutable. They represent either a set of
+// UnobservableStores, or the "undetermined empty set".
+//
+// We apply some sharing to save memory. The class UnobservablesSet is only a
+// pointer wide, and a copy does not use any heap (or temp_zone) memory. Most
+// changes to an UnobservablesSet might allocate in the temp_zone.
+//
+// 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 Intersect(UnobservablesSet other, Zone* zone) const;
+  UnobservablesSet Add(UnobservableStore obs, Zone* zone) const;
+  UnobservablesSet RemoveSameOffset(StoreOffset off, Zone* zone) const;
+
+  const ZoneSet<UnobservableStore>* set() const { return set_; }
+
+  bool IsUndetermined() const { return set_ == nullptr; }
+  bool IsEmpty() const { return set_ == nullptr || set_->empty(); }
+  bool Contains(UnobservableStore obs) const {
+    return set_ != nullptr && (set_->find(obs) != set_->end());
+  }
+
+  bool operator==(const UnobservablesSet&) const;
+  bool operator!=(const UnobservablesSet&) const;
+
+ private:
+  explicit UnobservablesSet(const ZoneSet<UnobservableStore>* set)
+      : set_(set) {}
+  const ZoneSet<UnobservableStore>* set_;
+};
+
+}  // namespace
+
+std::ostream& operator<<(std::ostream& os, UnobservablesSet set);
+
+namespace {
+
+class StoreStoreFinder final {

[Jarin, 2016/07/25 09:52:13]

Maybe rename to RedundantStoreFinder? (Or UnobservableStoreFinder?)

[bgeron, 2016/07/27 13:40:38]

Done.

+ public:
+  StoreStoreFinder(JSGraph* js_graph, Zone* temp_zone);
+
+  void Find();
+
+  const ZoneSet<Node*>& to_remove_const() { return to_remove_; }
+
+  virtual void Visit(Node* node);
+
+ private:
+  static bool IsEligibleNode(Node* node);
+  void VisitEligibleNode(Node* node);
+  UnobservablesSet RecomputeUseIntersection(Node* node);
+  UnobservablesSet RecomputeSet(Node* node, UnobservablesSet uses);
+  static bool CanObserveNothing(Node* node);
+  static bool CanObserveAnything(Node* node);
+
+  void MarkForRevisit(Node* node);
+
+  JSGraph* jsgraph() const { return jsgraph_; }
+  Zone* temp_zone() const { return temp_zone_; }
+  ZoneVector<UnobservablesSet>& unobservable() { return unobservable_; }
+  UnobservablesSet& unobservable_for_id(NodeId id) {
+    return unobservable().at(id);
+  }
+  ZoneSet<Node*>& to_remove() { return to_remove_; }
+
+  JSGraph* const jsgraph_;
+  Zone* const temp_zone_;
+
+  ZoneStack<Node*> revisit_;
+  ZoneVector<bool> in_revisit_;
+  // Maps node IDs to UnobservableNodeSets.
+  ZoneVector<UnobservablesSet> unobservable_;
+  ZoneSet<Node*> to_remove_;
+};
 
 // To safely cast an offset from a FieldAccess, which has a wider range
 // (namely int).
-Offset ToOffset(int offset) {
-  CHECK(0 <= offset && offset < (1 << 8 * sizeof(Offset)));
-  return (Offset)offset;
+StoreOffset ToOffset(int offset) {
+  CHECK(0 <= offset && offset < (1 << 8 * sizeof(StoreOffset)));
+  return (StoreOffset)offset;
 }
 
-Offset ToOffset(const FieldAccess& access) { return ToOffset(access.offset); }
+StoreOffset ToOffset(const FieldAccess& access) {
+  return ToOffset(access.offset);
+}
 
 // If node has a single effect use, return that node. If node has no or
 // multiple effect uses, return nullptr.
 Node* SingleEffectUse(Node* node) {
   Node* last_use = nullptr;
   for (Edge edge : node->use_edges()) {
     if (!NodeProperties::IsEffectEdge(edge)) {
       continue;
     }
     if (last_use != nullptr) {
       // more than one

[Jarin, 2016/07/25 09:52:13]

Leave out the comment (or make into a sentence with first capital letter and a
dot at the end.)

[bgeron, 2016/07/27 13:40:37]

Done.

       return nullptr;
     }
     last_use = edge.from();
     DCHECK_NOT_NULL(last_use);
   }
   return last_use;
 }
 
-// Return true if node is the last consecutive StoreField node in a linear
-// part of the effect chain.
-bool IsEndOfStoreFieldChain(Node* node) {
-  Node* next_on_chain = SingleEffectUse(node);
-  return (next_on_chain == nullptr ||
-          next_on_chain->op()->opcode() != IrOpcode::kStoreField);
-}
-
-// The argument must be a StoreField node. If there is a node before it in the
-// effect chain, and if this part of the effect chain is linear (no other
-// effect uses of that previous node), then return that previous node.
-// Otherwise, return nullptr.
-//
-// The returned node need not be a StoreField.
-Node* PreviousEffectBeforeStoreField(Node* node) {
-  DCHECK_EQ(node->op()->opcode(), IrOpcode::kStoreField);
-  DCHECK_EQ(node->op()->EffectInputCount(), 1);
-
-  Node* previous = NodeProperties::GetEffectInput(node);
-  if (previous != nullptr && node == SingleEffectUse(previous)) {
-    return previous;
+// If there is a node before {node} in the effect chain, and if this part of
+// the effect chain is linear (no other effect uses of that previous node),
+// then return that previous node. Otherwise, return nullptr.
+Node* PreviousEffectInChain(Node* node) {
+  if (node->op()->EffectInputCount() == 1) {
+    Node* previous = NodeProperties::GetEffectInput(node);
+    if (previous != nullptr && node == SingleEffectUse(previous)) {
+      return previous;
+    } else {

[Jarin, 2016/07/25 09:52:13]

How about leaving out the else branches and just have unconditional 'return
nullptr;' at the end of the function?

[bgeron, 2016/07/27 13:40:38]

Nice spot. Done.

+      return nullptr;
+    }
   } else {
     return nullptr;
   }
 }
 
 size_t rep_size_of(MachineRepresentation rep) {

[Jarin, 2016/07/25 09:52:13]

CamelCase, please. (Here and below.)

[bgeron, 2016/07/27 13:40:38]

Done. I left `unobservable_for_id` as is, because the style guide seems to be
okay with that.

   return ((size_t)1) << ElementSizeLog2Of(rep);
 }
 size_t rep_size_of(FieldAccess access) {
   return rep_size_of(access.machine_type.representation());
 }
 
 bool AtMostTagged(FieldAccess access) {
   return rep_size_of(access) <= rep_size_of(MachineRepresentation::kTagged);
 }
 
 bool AtLeastTagged(FieldAccess access) {
   return rep_size_of(access) >= rep_size_of(MachineRepresentation::kTagged);
 }
 
+int EffectUseCount(Node* node) {
+  int uses = 0;
+  for (const Edge edge : node->use_edges()) {
+    if (NodeProperties::IsEffectEdge(edge)) {
+      uses++;
+    }
+  }
+  return uses;
+}
+
 }  // namespace
 
-bool StoreStoreElimination::IsEligibleNode(Node* node) {
-  return (node->op()->opcode() == IrOpcode::kStoreField) &&
-         IsEndOfStoreFieldChain(node);
-}
-
-void StoreStoreElimination::ReduceEligibleNode(Node* node) {
-  DCHECK(IsEligibleNode(node));
-
-  // if (FLAG_trace_store_elimination) {
-  //   PrintF("** StoreStoreElimination::ReduceEligibleNode: activated:
-  //   #%d\n",
-  //          node->id());
-  // }
-
-  TRACE("activated: #%d", node->id());
-
-  // Initialize empty futureStore.
-  ZoneMap<Offset, Node*> futureStore(temp_zone());
-
-  Node* current_node = node;
+void StoreStoreFinder::Find() {
+  Visit(jsgraph()->graph()->end());
+
+  while (!revisit_.empty()) {
+    Node* next = revisit_.top();
+    revisit_.pop();
+    in_revisit_.at(next->id()) = false;

[Jarin, 2016/07/25 09:52:13]

Do not use the 'at' method - it can throw exceptions and we do not really want
that.

[bgeron, 2016/07/27 13:40:38]

Done.

+    Visit(next);
+  }
+
+#ifdef DEBUG
+  // Check that we visited all the StoreFields
+  AllNodes all(temp_zone(), jsgraph()->graph());
+  for (Node* node : all.live) {
+    if (node->op()->opcode() == IrOpcode::kStoreField) {
+      UnobservablesSet node_unobservable = unobservable_for_id(node->id());
+      DCHECK_EXTRA(!node_unobservable.IsUndetermined(), "#%d:%s", node->id(),
+                   node->op()->mnemonic());
+    }
+  }

[Jarin, 2016/07/25 09:52:13]

Niiiice, I love this check; will use this elsewhere.

[bgeron, 2016/07/27 13:40:38]

We should put it in src/base/logging.h :D

+#endif
+}
+
+void StoreStoreFinder::MarkForRevisit(Node* node) {
+  if (!in_revisit_.at(node->id())) {
+    revisit_.push(node);
+    in_revisit_[node->id()] = true;
+  }
+}
+
+void StoreStoreElimination::Run(JSGraph* js_graph, Zone* temp_zone) {
+  // Find superfluous nodes
+  StoreStoreFinder finder(js_graph, temp_zone);
+  finder.Find();
+
+  // Remove superfluous nodes
+
+  for (Node* node : finder.to_remove_const()) {
+    if (FLAG_trace_store_elimination) {
+      PrintF("StoreStoreElimination::Run: Eliminating node #%d:%s\n",
+             node->id(), node->op()->mnemonic());
+    }
+    Node* previous_effect = NodeProperties::GetEffectInput(node);
+    NodeProperties::ReplaceUses(node, nullptr, previous_effect, nullptr,
+                                nullptr);
+    node->Kill();
+  }
+}
+
+bool StoreStoreFinder::IsEligibleNode(Node* node) {
+  DCHECK_LE(node->op()->EffectOutputCount(), 1);
+
+  bool isEffectful = (node->op()->EffectInputCount() >= 1);
+  bool endsEffectChain = (EffectUseCount(node) != 1) ||
+                         (SingleEffectUse(node)->op()->EffectInputCount() >= 2);
+  if (endsEffectChain && EffectUseCount(node) >= 1 &&

[Jarin, 2016/07/25 09:52:13]

The if is here just for the DCHECK, please fold the condition into the DCHECK,
so that we do not compute it needlessly in release mode.

[bgeron, 2016/07/27 13:40:38]

Method disappeared during refactoring.

+      node->op()->opcode() != IrOpcode::kStart) {
+    DCHECK_EXTRA(isEffectful, "#%d:%s", node->id(), node->op()->mnemonic());
+  }
+  return isEffectful && endsEffectChain;
+}
+
+// Recompute unobservables-set for a node. Will also mark superfluous nodes
+// as to be removed.
+
+UnobservablesSet StoreStoreFinder::RecomputeSet(Node* node,
+                                                UnobservablesSet uses) {
+  // Usually, we decide using the operator properties that an operator
+  // observes everything or observes nothing (see CanObserveAnything,
+  // CanObserveNothing), but there are some opcodes we treat specially.

[Jarin, 2016/07/25 09:52:13]

This comment basically just states what is obvious from the code below, so maybe
remove it?

[bgeron, 2016/07/27 13:40:38]

Done.

+  switch (node->op()->opcode()) {
+    case IrOpcode::kStoreField: {
+      Node* stored_to = node->InputAt(0);
+      FieldAccess access = OpParameter<FieldAccess>(node->op());
+      StoreOffset offset = ToOffset(access);
+
+      UnobservableStore observation = {stored_to->id(), offset};
+      bool presentInSet = uses.Contains(observation);

[Jarin, 2016/07/25 09:52:13]

presentInSet => isNotObservable?

[bgeron, 2016/07/27 13:40:38]

Done.

+
+      if (presentInSet && AtMostTagged(access)) {
+        TRACE("  #%d is StoreField[+%d,%s](#%d), unobservable", node->id(),
+              offset, MachineReprToString(access.machine_type.representation()),
+              stored_to->id());
+        to_remove().insert(node);
+        return uses;
+      } else if (presentInSet && !AtMostTagged(access)) {
+        TRACE(
+            "  #%d is StoreField[+%d,%s](#%d), repeated in future but too "
+            "big to optimize away",
+            node->id(), offset,
+            MachineReprToString(access.machine_type.representation()),
+            stored_to->id());
+        return uses;
+      } else if (!presentInSet && AtLeastTagged(access)) {
+        TRACE("  #%d is StoreField[+%d,%s](#%d), observable, recording in set",
+              node->id(), offset,
+              MachineReprToString(access.machine_type.representation()),
+              stored_to->id());
+        return uses.Add(observation, temp_zone());
+      } else if (!presentInSet && !AtLeastTagged(access)) {
+        TRACE(
+            "  #%d is StoreField[+%d,%s](#%d), observable but too small to "
+            "record",
+            node->id(), offset,
+            MachineReprToString(access.machine_type.representation()),
+            stored_to->id());
+        return uses;
+      } else {
+        UNREACHABLE();
+      }
+      break;
+    }
+    case IrOpcode::kLoadField: {
+      Node* loaded_from = node->InputAt(0);
+      FieldAccess access = OpParameter<FieldAccess>(node->op());
+      StoreOffset offset = ToOffset(access);
+
+      TRACE(
+          "  #%d is LoadField[+%d,%s](#%d), removing all offsets [+%d] from "
+          "set",
+          node->id(), offset,
+          MachineReprToString(access.machine_type.representation()),
+          loaded_from->id(), offset);
+
+      return uses.RemoveSameOffset(offset, temp_zone());

[Jarin, 2016/07/25 09:52:13]

In future, we could be a bit smarter here and only remove abstract locations
that may alias with the load. In particular, if this load from an allocation
node and the abstract location is from a different allocation, then we do not
have to invalidate that location.

(Not actionable now.)

[bgeron, 2016/07/27 13:40:38]

Ack. Reminds me.. for the load elimination, I encountered multiple references to
the same allocation but some through a CheckIf; I implemented some normalisation
procedure for this in commit 37330 (see link below). I didn't encounter such
indirections yet for StoreField, but if we do, it might be worth porting over
this normalisation.

https://github.com/v8/v8/commit/f416886358c0aeaa5b4d1e83d9c7d6bb8b0e7f2f

+      break;
+    }
+    default:
+      if (CanObserveNothing(node)) {
+        TRACE("  #%d:%s can observe nothing, set stays unchanged", node->id(),
+              node->op()->mnemonic());
+        return uses;
+      } else if (CanObserveAnything(node)) {
+        TRACE("  #%d:%s can observe everything, recording empty set",
+              node->id(), node->op()->mnemonic());
+        return UnobservablesSet::DeterminedEmpty(temp_zone());
+      } else {
+        // It is safe to turn this check off in the future, but it is better
+        // to list opcodes in CanObserveNothing, in CanObserveAnything, or if
+        // you don't know, to add another case inside this DCHECK_EXTRA.
+        DCHECK_EXTRA(node->op()->opcode() == IrOpcode::kCall, "%s",
+                     node->op()->mnemonic());
+        TRACE(
+            "  cannot determine unobservables-set for #%d:%s; "
+            "conservatively recording empty set",
+            node->id(), node->op()->mnemonic());
+        return UnobservablesSet::DeterminedEmpty(temp_zone());
+      }
+  }
+  UNREACHABLE();
+  return UnobservablesSet::Undetermined();
+}
+
+bool StoreStoreFinder::CanObserveNothing(Node* node) {

[Jarin, 2016/07/25 09:52:13]

CannotObserveStoreField?

[bgeron, 2016/07/27 13:40:38]

Done.

+  Operator::Properties mask =
+      Operator::kNoRead | Operator::kNoDeopt | Operator::kNoThrow;
+
+  return (node->op()->properties() & mask) == mask ||
+         node->opcode() == IrOpcode::kAllocate ||
+         node->opcode() == IrOpcode::kCheckedLoad ||
+         node->opcode() == IrOpcode::kLoadElement;
+}
+
+bool StoreStoreFinder::CanObserveAnything(Node* node) {
+  const Operator* op = node->op();
+  auto opcode = op->opcode();
+  if (opcode == IrOpcode::kLoad) {

[Jarin, 2016/07/25 09:52:13]

Benedikt says kLoad should never alias a field, so maybe this is not needed.

[bgeron, 2016/07/27 13:40:38]

Well, if I make it so that Load cannot observe anything, the tests do pass!
Funny. I thought I'd seen Load with computed pointer arguments, but I guess at
the moment we don't happen to use that to access fields.  I've added it to the
new patchset, but I can easily roll that back still.

+    return true;
+  }
+  return !op->HasProperty(Operator::kNoThrow) ||
+         !op->HasProperty(Operator::kNoDeopt);
+}
+
+// Initialize unobservable_ with js_graph->graph->NodeCount() empty sets.
+StoreStoreFinder::StoreStoreFinder(JSGraph* js_graph, Zone* temp_zone)
+    : jsgraph_(js_graph),
+      temp_zone_(temp_zone),
+      revisit_(temp_zone),
+      in_revisit_(js_graph->graph()->NodeCount(), temp_zone),
+      unobservable_(js_graph->graph()->NodeCount(),
+                    UnobservablesSet::Undetermined(), temp_zone),
+      to_remove_(temp_zone) {}
+
+void StoreStoreFinder::Visit(Node* node) {
+  // All eligible nodes should be reachable from the control graph. If this
+  // node was not visited (unobservable_for_id(node->id()).IsUndetermined()),
+  // then visit the control inputs and mark as visited
+  // (unobservable_for_id(node->id() = DeterminedEmpty(..)).
+
+  bool isEffectful = (node->op()->EffectInputCount() >= 1);
+
+  if (IsEligibleNode(node)) {

[Jarin, 2016/07/25 09:52:13]

I do not understand what is the advantage of walking effect chains in the
VisitEligibleNode? Would not it be simpler just to take one node at a time and
propagate the observation information through the queue and the per-node
observation sets?

[bgeron, 2016/07/27 13:40:38]

Good idea; this simplified the file significantly. I couldn't measure a slowdown
in Octane. Changed the tracing to still make sense.

+    VisitEligibleNode(node);
+  } else if (!isEffectful) {
+    // If node was not visited before, then visit its control inputs.
+    if (unobservable_for_id(node->id()).IsUndetermined()) {
+      for (Edge edge : node->input_edges()) {
+        if (NodeProperties::IsControlEdge(edge)) {
+          MarkForRevisit(edge.to());
+        }
+      }
+
+      unobservable_for_id(node->id()) =
+          UnobservablesSet::DeterminedEmpty(temp_zone());
+    }
+  }
+}
+
+void StoreStoreFinder::VisitEligibleNode(Node* node) {
+  TRACE("Found end of effect chain: %4d:%s", node->id(),
+        node->op()->mnemonic());
+
+  Node* cur = node;
+  UnobservablesSet after_set = RecomputeUseIntersection(cur);
+  bool cur_set_changed;
 
   do {
-    FieldAccess access = OpParameter<FieldAccess>(current_node->op());
-    Offset offset = ToOffset(access);
-    Node* object_input = current_node->InputAt(0);
-
-    Node* previous = PreviousEffectBeforeStoreField(current_node);
-
-    // Find the map entry.
-    ZoneMap<Offset, Node*>::iterator find_result = futureStore.find(offset);
-
-    bool present = find_result != futureStore.end();
-    Node* value = present ? find_result->second : nullptr;
-
-    if (present && value == object_input && AtMostTagged(access)) {
-      // Key was present, and the value equalled object_input. This means
-      // that soon after in the effect chain, we will do a StoreField to the
-      // same object with the same offset, therefore current_node can be
-      // optimized away. Also, the future StoreField is at least as big as this
-      // one.
-      //
-      // We don't need to update futureStore.
-
-      Node* previous_effect = NodeProperties::GetEffectInput(current_node);
-
-      NodeProperties::ReplaceUses(current_node, nullptr, previous_effect,
-                                  nullptr, nullptr);
-      current_node->Kill();
-      TRACE("#%d[[+%d,%s]](#%d) -- at most tagged size, eliminated",
-            current_node->id(), offset,
-            MachineReprToString(access.machine_type.representation()),
-            object_input->id());
-    } else if (present && value == object_input && !AtMostTagged(access)) {
-      TRACE("#%d[[+%d,%s]](#%d) -- too wide, not eliminated",
-            current_node->id(), offset,
-            MachineReprToString(access.machine_type.representation()),
-            object_input->id());
-    } else if (present && value != object_input && AtLeastTagged(access)) {
-      // Key was present, and the value did not equal object_input. This means
-      // that there is a StoreField to this offset in the future, but the
-      // object instance comes from a different Node. We pessimistically
-      // assume that we cannot optimize current_node away. However, we will
-      // guess that the current StoreField is more relevant than the future
-      // one, record the current StoreField in futureStore instead, and
-      // continue ascending up the chain.
-      find_result->second = object_input;
-      TRACE("#%d[[+%d,%s]](#%d) -- wide enough, diff object, updated in map",
-            current_node->id(), offset,
-            MachineReprToString(access.machine_type.representation()),
-            object_input->id());
-    } else if (!present && AtLeastTagged(access)) {
-      // Key was not present. This means that there is no matching
-      // StoreField to this offset in the future, so we cannot optimize
-      // current_node away. However, we will record the current StoreField
-      // in futureStore, and continue ascending up the chain.
-      futureStore.insert(std::make_pair(offset, object_input));
-      TRACE(
-          "#%d[[+%d,%s]](#%d) -- wide enough, key not present, inserted in map",
-          current_node->id(), offset,
-          MachineReprToString(access.machine_type.representation()),
-          object_input->id());
-    } else if (!AtLeastTagged(access)) {
-      TRACE("#%d[[+%d,%s]](#%d) -- too narrow to record", current_node->id(),
-            offset, MachineReprToString(access.machine_type.representation()),
-            object_input->id());
+    UnobservablesSet before_set = RecomputeSet(cur, after_set);
+
+    DCHECK(!before_set.IsUndetermined());
+
+    UnobservablesSet* stored_for_node = &unobservable_for_id(cur->id());
+
+    cur_set_changed =
+        (stored_for_node->IsUndetermined() || *stored_for_node != before_set);
+
+    if (!cur_set_changed) {
+      // We will not be able to update the part of this chain above any more.
+      // Exit.
+      TRACE("+ No change: stabilized. Stopping this chain.");
+      break;
+    } else if (cur_set_changed && before_set.IsEmpty()) {
+      DCHECK(before_set.IsEmpty());

[bgeron, 2016/07/27 13:40:38]

Oops!

+    } else if (cur_set_changed && !before_set.IsEmpty()) {
     } else {
       UNREACHABLE();
     }
 
-    // Regardless of whether we eliminated node {current}, we want to
-    // continue walking up the effect chain.
-
-    current_node = previous;
-  } while (current_node != nullptr &&
-           current_node->op()->opcode() == IrOpcode::kStoreField);
-
-  TRACE("finished");
+    // Overwrite vector in-place.
+    *stored_for_node = before_set;
+
+    Node* previous = PreviousEffectInChain(cur);
+    if (previous == nullptr && cur_set_changed) {
+      TRACE("- Reached top of chain; marking effect inputs for revisiting.");
+      for (int i = 0; i < cur->op()->EffectInputCount(); i++) {
+        Node* input = NodeProperties::GetEffectInput(cur, i);
+        if (!CanObserveAnything(input) ||
+            unobservable_for_id(input->id()).IsUndetermined()) {
+          MarkForRevisit(input);
+        }
+      }
+
+      cur = nullptr;
+    } else if (previous == nullptr && !cur_set_changed) {
+      TRACE("+ Reached top of chain and stabilized.");
+      cur = nullptr;
+    } else {
+      // Update variables for next loop iteration
+      cur = previous;
+      DCHECK(EffectUseCount(previous) == 1);
+      after_set = before_set;
+      if (FLAG_turbo_verify_store_elimination) {
+        DCHECK(after_set == RecomputeUseIntersection(cur));
+      }
+      DCHECK_NOT_NULL(cur);
+    }
+  } while (cur != nullptr);
+}
+
+// Compute the intersection of the UnobservablesSets of all effect uses and
+// return it. This function only works if {node} has an effect use.
+//
+// The result UnobservablesSet will always be determined.
+UnobservablesSet StoreStoreFinder::RecomputeUseIntersection(Node* node) {
+  // {first} == true indicates that we haven't looked at any elements yet.
+  // {first} == false indicates that cur_set is the intersection of at least one
+  // thing.
+
+  bool first = true;
+  UnobservablesSet cur_set = UnobservablesSet::Undetermined();  // irrelevant
+
+  for (Edge edge : node->use_edges()) {
+    // Skip non-effect edges
+    if (!NodeProperties::IsEffectEdge(edge)) {
+      continue;
+    }
+
+    Node* use = edge.from();
+    UnobservablesSet new_set = unobservable_for_id(use->id());
+    // Include new_set in the intersection.
+    if (first) {
+      // Intersection of a one-element set is that one element
+      first = false;
+      cur_set = new_set;
+    } else {
+      // Take the intersection of cur_set and new_set.
+      cur_set = cur_set.Intersect(new_set, temp_zone());
+    }
+
+    if (FLAG_trace_store_elimination) {
+      // Serialise the UnobservablesSet.
+      std::ostringstream os;
+      os << "intersected with " << new_set << ", current intersection is "
+         << cur_set;
+      std::string msg = os.str();
+    }
+  }
+
+  if (first) {
+    // There were no effect uses.
+    auto opcode = node->op()->opcode();
+    // List of opcodes that may end this effect chain. The opcodes are not
+    // important to the soundness of this optimization; this serves as a
+    // general sanity check. Add opcodes to this list as it suits you.
+    //
+    // Everything is observable after these opcodes; return the empty set.
+    DCHECK_EXTRA(
+        opcode == IrOpcode::kReturn || opcode == IrOpcode::kTerminate ||
+            opcode == IrOpcode::kDeoptimize || opcode == IrOpcode::kThrow,
+        "for #%d:%s", node->id(), node->op()->mnemonic());
+    USE(opcode);  // silence warning about unused variable
+
+    return UnobservablesSet::DeterminedEmpty(temp_zone());
+  } else {
+    if (cur_set.IsUndetermined()) {
+      cur_set = UnobservablesSet::DeterminedEmpty(temp_zone());
+    }
+
+    if (FLAG_trace_store_elimination) {
+      // Serialise the UnobservablesSet.
+      std::ostringstream os;
+      os << cur_set;
+      std::string msg = os.str();
+    }
+
+    return cur_set;
+  }
+}
+
+UnobservablesSet UnobservablesSet::Undetermined() { return UnobservablesSet(); }
+
+UnobservablesSet::UnobservablesSet() : set_(nullptr) {}
+
+UnobservablesSet UnobservablesSet::DeterminedEmpty(Zone* zone) {
+  // Create a new empty UnobservablesSet. This allocates in the zone, and
+  // can probably be optimized to use a global singleton.
+  ZoneSet<UnobservableStore>* empty_set =
+      new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
+          ZoneSet<UnobservableStore>(zone);
+  return UnobservablesSet(empty_set);
+}
+
+// Computes the intersection of two UnobservablesSets. May return
+// UnobservablesSet::Undetermined() instead of an empty UnobservablesSet for
+// speed.
+UnobservablesSet UnobservablesSet::Intersect(UnobservablesSet other,
+                                             Zone* zone) const {
+  if (set() == nullptr || other.set() == nullptr) {
+    return Undetermined();
+  } else if (other.set() == nullptr) {
+    return *this;
+  } else {
+    ZoneSet<UnobservableStore>* intersection =
+        new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
+            ZoneSet<UnobservableStore>(zone);
+    // Put the intersection of set() and other.set() in intersection.
+    set_intersection(set()->begin(), set()->end(), other.set()->begin(),
+                     other.set()->end(),
+                     std::inserter(*intersection, intersection->end()));
+
+    return UnobservablesSet(intersection);
+  }
+}
+
+UnobservablesSet UnobservablesSet::Add(UnobservableStore obs,
+                                       Zone* zone) const {
+  bool present = (set()->find(obs) != set()->end());
+  if (present) {
+    return *this;
+  } else {
+    // Make a new empty set.
+    ZoneSet<UnobservableStore>* new_set =
+        new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
+            ZoneSet<UnobservableStore>(zone);
+    // Copy the old elements over.
+    *new_set = *set();
+    // Add the new element.
+    bool inserted = new_set->insert(obs).second;
+    DCHECK(inserted);
+    USE(inserted);  // silence warning about unused variable
+
+    return UnobservablesSet(new_set);
+  }
+}
+
+UnobservablesSet UnobservablesSet::RemoveSameOffset(StoreOffset offset,
+                                                    Zone* zone) const {
+  // Make a new empty set.
+  ZoneSet<UnobservableStore>* new_set =
+      new (zone->New(sizeof(ZoneSet<UnobservableStore>)))
+          ZoneSet<UnobservableStore>(zone);
+  // Copy all elements over that have a different offset.
+  for (auto obs : *set()) {
+    if (obs.offset_ != offset) {
+      new_set->insert(obs);
+    }
+  }
+
+  return UnobservablesSet(new_set);
+}
+
+// Used for debugging.
+std::ostream& operator<<(std::ostream& os, UnobservablesSet set) {
+  if (set.set() == nullptr) {
+    os << "(undetermined)";
+  } else {
+    os << "[";
+    bool first = true;
+    for (UnobservableStore obs : *set.set()) {
+      if (!first) {
+        os << ",";
+      } else {
+        first = false;
+      }
+      os << obs;
+    }
+    os << "]";
+  }
+  return os;
+}
+
+bool UnobservablesSet::operator==(const UnobservablesSet& other) const {
+  if (IsUndetermined() || other.IsUndetermined()) {
+    return IsEmpty() && other.IsEmpty();
+  } else {
+    // Both pointers guaranteed not to be nullptrs.
+    return *set() == *other.set();
+  }
+}
+
+bool UnobservablesSet::operator!=(const UnobservablesSet& other) const {
+  return !(*this == other);
+}
+
+bool UnobservableStore::operator==(const UnobservableStore other) const {
+  return (id_ == other.id_) && (offset_ == other.offset_);
+}
+
+bool UnobservableStore::operator!=(const UnobservableStore other) const {
+  return !(*this == other);
+}
+
+bool UnobservableStore::operator<(const UnobservableStore other) const {
+  return (id_ < other.id_) || (id_ == other.id_ && offset_ < other.offset_);
+}
+
+std::ostream& operator<<(std::ostream& os, UnobservableStore obs) {
+  os << "#" << obs.id_ << "[+" << obs.offset_ << "]";
+  return os;
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8