[compiler] Introduce a simple store-store elimination, disabled by default.

src/compiler/store-store-elimination.cc

Index: src/compiler/store-store-elimination.cc
diff --git a/src/compiler/store-store-elimination.cc b/src/compiler/store-store-elimination.cc
new file mode 100644
index 0000000000000000000000000000000000000000..15c185e271dcf4855934d125a95ff8f7e2ce74f3
--- /dev/null
+++ b/src/compiler/store-store-elimination.cc
@@ -0,0 +1,227 @@
+// 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 "src/compiler/store-store-elimination.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 {
+
+// A pretty dumb store-store elimination. When the effect chain contains the

[Jarin, 2016/06/21 13:28:33]

"pretty dumb" --> simple

[bgeron, 2016/06/21 17:48:58]

Much better.. Would be good to keep the codebase fully PC :D

+// following sequence,
+//
+// - StoreField[[+off_1]](x1, y1)
+// - StoreField[[+off_2]](x2, y2)
+// - StoreField[[+off_3]](x3, y3)
+//   ...
+// - StoreField[[+off_n]](xn, yn)
+//
+// where the xes are the objects and the ys are the values to be stored, then
+// we are going to assume that those stores can only overlap if they have
+// exactly the same offset. If off_i = off_j and xi=xj and i < j, then we
+// optimize the i'th StoreField away.
+
+// This optimization should be initiated on the last StoreField in such a
+// sequence.
+//
+// The algorithm works by walking the effect chain from the last StoreField
+// upwards. While walking, we maintain a map {nextStore} from offsets to
+// nodes; initially it is empty. As we walk the effect chain upwards, if
+// nextStore[off] = n, then next StoreField in the effect chain will have
+// object input n. For example, for this effect chain
+//
+// 71: StoreField(60, 0)
+// 72: StoreField(65, 8)
+// 73: StoreField(63, 8)
+// 74: StoreField(65, 16)
+// 75: StoreField(62, 8)
+//
+// just before we get to 72, we will have nextStore = {8: 63, 16: 65}.
+
+// Here is the complete process.
+//
+// - We are at the end of a sequence of consecutive StoreFields.
+// - We start out with nextStore = empty.
+// - We then walk the effect chain upwards to find the next StoreField [1].
+//
+//   - If the offset is not a key of {nextStore} yet, we put it in.
+
+//   - If the offset is a key of {nextStore}, but nextStore[offset] is a
+//     different node, we overwrite nextStore[offset] with the current node.
+//   - If the offset is a key of {nextStore} and nextStore[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.
+//
+// [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.
+
+StoreStoreElimination::StoreStoreElimination(JSGraph* js_graph, Zone* zone)
+    : jsgraph_(js_graph), zone_(zone) {}
+
+StoreStoreElimination::~StoreStoreElimination() {}
+
+// 16 bits was chosen fairly arbitrarily; it seems enough now. 8 bits is too
+// few.
+typedef uint16_t Offset;

[Jarin, 2016/06/21 13:28:32]

Please, put the file-local definitions into an anonymous namespace. Then you do
not even have to use static. Something like:

namespace {

typedef ...;

Offset toOffset(int offset) { ... }

bool IsEndOfStoreFieldChain(Node* node) { ... }

}  // namespace

[bgeron, 2016/06/21 17:48:58]

Done.

+
+// To safely cast an offset from a FieldAccess, which has a wider range
+// (namely int).
+Offset toOffset(int offset) {

[Jarin, 2016/06/21 13:28:33]

toOffset -> ToOffset

(link to style guide: https://www.chromium.org/developers/coding-style)

[bgeron, 2016/06/21 17:48:58]

Done.

+  CHECK(0 <= offset && offset < (1 << 8 * sizeof(Offset)));
+  return (Offset)offset;
+}
+
+Offset 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.
+static 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
+      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.
+static 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;
+  } else {
+    return nullptr;
+  }
+}
+
+bool StoreStoreElimination::IsEligibleNode(Node* node) {
+  return (node->op()->opcode() == IrOpcode::kStoreField) &&
+         IsEndOfStoreFieldChain(node);
+}
+
+void StoreStoreElimination::ReduceEligibleNode(Node* node) {
+  DCHECK(IsEligibleNode(node));
+
+  if (FLAG_trace_turbo_ssel) {
+    printf("** StoreStoreElimination::ReduceEligibleNode activated: #%d\n",
+           node->id());
+  }
+
+  // Initialize empty nextStore.
+  ZoneMap<Offset, Node*> nextStore = ZoneMap<Offset, Node*>(zone());
+
+  Node* current_node = node;
+
+  while (current_node->op()->opcode() == IrOpcode::kStoreField) {
+    Offset offset = toOffset(OpParameter<FieldAccess>(current_node->op()));
+    Node* object_input = current_node->InputAt(0);
+
+    // Try to insert. If it was present, this will preserve the original value.

[Jarin, 2016/06/21 13:28:33]

You should handle field aliasing in some way. Perhaps the easiest way is to only
do store elimination for tagged values
(field_access.machine_type.representation() == MachineRepresentation::kTagged) -
those are aligned and we should never try to store to only some bytes of the
value or some such.

[bgeron, 2016/06/21 17:48:58]

Is there more information on field aliasing? I could add a check, but I don't
know how to generate input that exercises it so I can't hand-test this.

[bgeron, 2016/06/22 18:00:58]

Done.

+    auto insert_result = nextStore.insert(std::make_pair(offset, object_input));
+    if (insert_result.second) {
+      // 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 nextStore, and
+      // continue ascending up the chain.
+      if (FLAG_trace_turbo_ssel) {
+        printf(
+            "   StoreStoreElimination::ReduceEligibleNode: "
+            "#%d[[+%d]] -- key not present\n",
+            current_node->id(), offset);
+      }
+    } else if (insert_result.first->second != object_input) {
+      // 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
+      // record the current StoreField in nextStore, and continue ascending up
+      // the chain.

[Jarin, 2016/06/21 13:28:33]

Note: Actually, I believe you could have a multimap and store both objects for
the offset. In fact, I think you could have a set of <field, object> pairs and
eliminate the store if you find the same pair. No?

However, we should only do this later.

[bgeron, 2016/06/21 17:48:58]

I think you're right!

+      insert_result.first->second = object_input;
+      if (FLAG_trace_turbo_ssel) {
+        printf(
+            "   StoreStoreElimination::ReduceEligibleNode: "
+            "#%d[[+%d]] -- diff object\n",
+            current_node->id(), offset);
+      }
+    } else {
+      // 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. We don't need to update nextStore.
+
+      Node* previous = PreviousEffectBeforeStoreField(current_node);

[Jarin, 2016/06/21 13:28:32]

Can't you move this line to the beginning of the loop (e.g., line 150), replace
the line 211 with 200 and remove lines 197 - 205.

Then you could even turn the loop condition to true (or make it

do { ... 
} while (current_node != nullptr && 
         current_node->op()->opcode() == IrOpcode::kStoreField);

What do you think?

[bgeron, 2016/06/21 17:48:58]

Great idea, I missed that.

+      Node* previous_effect = NodeProperties::GetEffectInput(current_node);
+
+      NodeProperties::ReplaceUses(current_node, nullptr, previous_effect,
+                                  nullptr, nullptr);
+      current_node->Kill();
+      if (FLAG_trace_turbo_ssel) {
+        printf(
+            "   StoreStoreElimination::ReduceEligibleNode: "
+            "#%d[[+%d]] -- eliminated\n",
+            current_node->id(), offset);
+      }
+
+      // {current_node} is now invalid. If {previous} exists, that is, if the
+      // chain continues above, the next loop iteration will resume there.
+
+      current_node = previous;
+      if (current_node != nullptr) {
+        continue;
+      } else {
+        break;
+      }
+    }
+
+    // We did not eliminate node {current}, but we want to continue walking up
+    // the effect chain.
+
+    current_node = PreviousEffectBeforeStoreField(current_node);
+    if (current_node == nullptr ||
+        current_node->op()->opcode() != IrOpcode::kStoreField) {
+      break;
+    }
+  }
+
+  if (FLAG_trace_turbo_ssel) {
+    printf(
+        "   StoreStoreElimination::ReduceEligibleNode: "
+        "stop chain traversal\n");
+  }
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8