Merge V8 5.3.332.45. DO NOT MERGE
Test: Manual
FPIIM-449
Change-Id: Id3254828b068abdea3cb10442e0172a8c9a98e03
(cherry picked from commit 13e2dadd00298019ed862f2b2fc5068bba730bcf)
diff --git a/src/compiler/redundancy-elimination.cc b/src/compiler/redundancy-elimination.cc
new file mode 100644
index 0000000..ae87349
--- /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