[turbofan] Initial version of RedundancyElimination.

src/compiler/redundancy-elimination.cc

Index: src/compiler/redundancy-elimination.cc
diff --git a/src/compiler/redundancy-elimination.cc b/src/compiler/redundancy-elimination.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ae87349896921cecc4b54be79fa49ccad2cef580
--- /dev/null
+++ b/src/compiler/redundancy-elimination.cc
@@ -0,0 +1,216 @@
+// 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/redundancy-elimination.h"
+
+#include "src/compiler/node-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+RedundancyElimination::RedundancyElimination(Editor* editor, Zone* zone)
+    : AdvancedReducer(editor), node_checks_(zone), zone_(zone) {}
+
+RedundancyElimination::~RedundancyElimination() {}
+
+Reduction RedundancyElimination::Reduce(Node* node) {
+  switch (node->opcode()) {
+    case IrOpcode::kCheckFloat64Hole:
+    case IrOpcode::kCheckTaggedHole:
+    case IrOpcode::kCheckTaggedPointer:
+    case IrOpcode::kCheckTaggedSigned:
+    case IrOpcode::kCheckedFloat64ToInt32:
+    case IrOpcode::kCheckedInt32Add:
+    case IrOpcode::kCheckedInt32Sub:
+    case IrOpcode::kCheckedTaggedToFloat64:
+    case IrOpcode::kCheckedTaggedToInt32:
+    case IrOpcode::kCheckedUint32ToInt32:
+      return ReduceCheckNode(node);
+    case IrOpcode::kEffectPhi:
+      return ReduceEffectPhi(node);
+    case IrOpcode::kDead:
+      break;
+    case IrOpcode::kStart:
+      return ReduceStart(node);
+    default:
+      return ReduceOtherNode(node);
+  }
+  return NoChange();
+}
+
+// static
+RedundancyElimination::EffectPathChecks*
+RedundancyElimination::EffectPathChecks::Copy(Zone* zone,
+                                              EffectPathChecks const* checks) {
+  return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(*checks);
+}
+
+// static
+RedundancyElimination::EffectPathChecks const*
+RedundancyElimination::EffectPathChecks::Empty(Zone* zone) {
+  return new (zone->New(sizeof(EffectPathChecks))) EffectPathChecks(nullptr, 0);
+}
+
+void RedundancyElimination::EffectPathChecks::Merge(
+    EffectPathChecks const* that) {
+  // Change the current check list to a longest common tail of this check
+  // list and the other list.
+
+  // First, we throw away the prefix of the longer list, so that
+  // we have lists of the same length.
+  Check* that_head = that->head_;
+  size_t that_size = that->size_;
+  while (that_size > size_) {
+    that_head = that_head->next;
+    that_size--;
+  }
+  while (size_ > that_size) {
+    head_ = head_->next;
+    size_--;
+  }
+
+  // Then we go through both lists in lock-step until we find
+  // the common tail.
+  while (head_ != that_head) {
+    DCHECK_LT(0u, size_);
+    DCHECK_NOT_NULL(head_);
+    size_--;
+    head_ = head_->next;
+    that_head = that_head->next;
+  }
+}
+
+RedundancyElimination::EffectPathChecks const*
+RedundancyElimination::EffectPathChecks::AddCheck(Zone* zone,
+                                                  Node* node) const {
+  Check* head = new (zone->New(sizeof(Check))) Check(node, head_);
+  return new (zone->New(sizeof(EffectPathChecks)))
+      EffectPathChecks(head, size_ + 1);
+}
+
+namespace {
+
+bool IsCompatibleCheck(Node const* a, Node const* b) {
+  if (a->op() != b->op()) return false;
+  for (int i = a->op()->ValueInputCount(); --i >= 0;) {
+    if (a->InputAt(i) != b->InputAt(i)) return false;
+  }
+  return true;
+}
+
+}  // namespace
+
+Node* RedundancyElimination::EffectPathChecks::LookupCheck(Node* node) const {
+  for (Check const* check = head_; check != nullptr; check = check->next) {
+    if (IsCompatibleCheck(check->node, node)) {
+      DCHECK(!check->node->IsDead());
+      return check->node;
+    }
+  }
+  return nullptr;
+}
+
+RedundancyElimination::EffectPathChecks const*
+RedundancyElimination::PathChecksForEffectNodes::Get(Node* node) const {
+  size_t const id = node->id();
+  if (id < info_for_node_.size()) return info_for_node_[id];
+  return nullptr;
+}
+
+void RedundancyElimination::PathChecksForEffectNodes::Set(
+    Node* node, EffectPathChecks const* checks) {
+  size_t const id = node->id();
+  if (id >= info_for_node_.size()) info_for_node_.resize(id + 1, nullptr);
+  info_for_node_[id] = checks;
+}
+
+Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  EffectPathChecks const* checks = node_checks_.Get(effect);
+  // If we do not know anything about the predecessor, do not propagate just yet
+  // because we will have to recompute anyway once we compute the predecessor.
+  if (checks == nullptr) return NoChange();
+  // See if we have another check that dominates us.
+  if (Node* check = checks->LookupCheck(node)) {
+    ReplaceWithValue(node, check);
+    return Replace(check);
+  }
+  // Learn from this check.
+  return UpdateChecks(node, checks->AddCheck(zone(), node));
+}
+
+Reduction RedundancyElimination::ReduceEffectPhi(Node* node) {
+  Node* const control = NodeProperties::GetControlInput(node);
+  if (control->opcode() == IrOpcode::kLoop) {
+    // Here we rely on having only reducible loops:
+    // The loop entry edge always dominates the header, so we can just use
+    // the information from the loop entry edge.
+    return TakeChecksFromFirstEffect(node);
+  }
+  DCHECK_EQ(IrOpcode::kMerge, control->opcode());
+
+  // Shortcut for the case when we do not know anything about some input.
+  int const input_count = node->op()->EffectInputCount();
+  for (int i = 0; i < input_count; ++i) {
+    Node* const effect = NodeProperties::GetEffectInput(node, i);
+    if (node_checks_.Get(effect) == nullptr) return NoChange();
+  }
+
+  // Make a copy of the first input's checks and merge with the checks
+  // from other inputs.
+  EffectPathChecks* checks = EffectPathChecks::Copy(
+      zone(), node_checks_.Get(NodeProperties::GetEffectInput(node, 0)));
+  for (int i = 1; i < input_count; ++i) {
+    Node* const input = NodeProperties::GetEffectInput(node, i);
+    checks->Merge(node_checks_.Get(input));
+  }
+  return UpdateChecks(node, checks);
+}
+
+Reduction RedundancyElimination::ReduceStart(Node* node) {
+  return UpdateChecks(node, EffectPathChecks::Empty(zone()));
+}
+
+Reduction RedundancyElimination::ReduceOtherNode(Node* node) {
+  if (node->op()->EffectInputCount() == 1) {
+    if (node->op()->EffectOutputCount() == 1) {
+      return TakeChecksFromFirstEffect(node);
+    } else {
+      // Effect terminators should be handled specially.
+      return NoChange();
+    }
+  }
+  DCHECK_EQ(0, node->op()->EffectInputCount());
+  DCHECK_EQ(0, node->op()->EffectOutputCount());
+  return NoChange();
+}
+
+Reduction RedundancyElimination::TakeChecksFromFirstEffect(Node* node) {
+  DCHECK_EQ(1, node->op()->EffectOutputCount());
+  Node* const effect = NodeProperties::GetEffectInput(node);
+  EffectPathChecks const* checks = node_checks_.Get(effect);
+  // If we do not know anything about the predecessor, do not propagate just yet
+  // because we will have to recompute anyway once we compute the predecessor.
+  if (checks == nullptr) return NoChange();
+  // We just propagate the information from the effect input (ideally,
+  // we would only revisit effect uses if there is change).
+  return UpdateChecks(node, checks);
+}
+
+Reduction RedundancyElimination::UpdateChecks(Node* node,
+                                              EffectPathChecks const* checks) {
+  EffectPathChecks const* original = node_checks_.Get(node);
+  // Only signal that the {node} has Changed, if the information about {checks}
+  // has changed wrt. the {original}.
+  if (checks != original) {
+    node_checks_.Set(node, checks);
+    return Changed(node);
+  }
+  return NoChange();
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8