Merge V8 5.4.500.40
Test: Manual - built & ran d8
Change-Id: I4edfa2853d3e565b729723645395688ece3193f4
diff --git a/src/compiler/loop-variable-optimizer.cc b/src/compiler/loop-variable-optimizer.cc
new file mode 100644
index 0000000..8331963
--- /dev/null
+++ b/src/compiler/loop-variable-optimizer.cc
@@ -0,0 +1,406 @@
+// 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/loop-variable-optimizer.h"
+
+#include "src/compiler/common-operator.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/node-marker.h"
+#include "src/compiler/node-properties.h"
+#include "src/compiler/node.h"
+#include "src/zone-containers.h"
+#include "src/zone.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Macro for outputting trace information from representation inference.
+#define TRACE(...) \
+ do { \
+ if (FLAG_trace_turbo_loop) PrintF(__VA_ARGS__); \
+ } while (false)
+
+LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph,
+ CommonOperatorBuilder* common,
+ Zone* zone)
+ : graph_(graph),
+ common_(common),
+ zone_(zone),
+ limits_(zone),
+ induction_vars_(zone) {}
+
+void LoopVariableOptimizer::Run() {
+ ZoneQueue<Node*> queue(zone());
+ queue.push(graph()->start());
+ NodeMarker<bool> queued(graph(), 2);
+ while (!queue.empty()) {
+ Node* node = queue.front();
+ queue.pop();
+ queued.Set(node, false);
+
+ DCHECK(limits_.find(node->id()) == limits_.end());
+ bool all_inputs_visited = true;
+ int inputs_end = (node->opcode() == IrOpcode::kLoop)
+ ? kFirstBackedge
+ : node->op()->ControlInputCount();
+ for (int i = 0; i < inputs_end; i++) {
+ auto input = limits_.find(NodeProperties::GetControlInput(node, i)->id());
+ if (input == limits_.end()) {
+ all_inputs_visited = false;
+ break;
+ }
+ }
+ if (!all_inputs_visited) continue;
+
+ VisitNode(node);
+ DCHECK(limits_.find(node->id()) != limits_.end());
+
+ // Queue control outputs.
+ for (Edge edge : node->use_edges()) {
+ if (NodeProperties::IsControlEdge(edge) &&
+ edge.from()->op()->ControlOutputCount() > 0) {
+ Node* use = edge.from();
+ if (use->opcode() == IrOpcode::kLoop &&
+ edge.index() != kAssumedLoopEntryIndex) {
+ VisitBackedge(node, use);
+ } else if (!queued.Get(use)) {
+ queue.push(use);
+ queued.Set(use, true);
+ }
+ }
+ }
+ }
+}
+
+class LoopVariableOptimizer::Constraint : public ZoneObject {
+ public:
+ InductionVariable::ConstraintKind kind() const { return kind_; }
+ Node* left() const { return left_; }
+ Node* right() const { return right_; }
+
+ const Constraint* next() const { return next_; }
+
+ Constraint(Node* left, InductionVariable::ConstraintKind kind, Node* right,
+ const Constraint* next)
+ : left_(left), right_(right), kind_(kind), next_(next) {}
+
+ private:
+ Node* left_;
+ Node* right_;
+ InductionVariable::ConstraintKind kind_;
+ const Constraint* next_;
+};
+
+class LoopVariableOptimizer::VariableLimits : public ZoneObject {
+ public:
+ static VariableLimits* Empty(Zone* zone) {
+ return new (zone) VariableLimits();
+ }
+
+ VariableLimits* Copy(Zone* zone) const {
+ return new (zone) VariableLimits(this);
+ }
+
+ void Add(Node* left, InductionVariable::ConstraintKind kind, Node* right,
+ Zone* zone) {
+ head_ = new (zone) Constraint(left, kind, right, head_);
+ limit_count_++;
+ }
+
+ void Merge(const VariableLimits* other) {
+ // Change the current condition list to a longest common tail
+ // of this condition list and the other list. (The common tail
+ // should correspond to the list from the common dominator.)
+
+ // First, we throw away the prefix of the longer list, so that
+ // we have lists of the same length.
+ size_t other_size = other->limit_count_;
+ const Constraint* other_limit = other->head_;
+ while (other_size > limit_count_) {
+ other_limit = other_limit->next();
+ other_size--;
+ }
+ while (limit_count_ > other_size) {
+ head_ = head_->next();
+ limit_count_--;
+ }
+
+ // Then we go through both lists in lock-step until we find
+ // the common tail.
+ while (head_ != other_limit) {
+ DCHECK(limit_count_ > 0);
+ limit_count_--;
+ other_limit = other_limit->next();
+ head_ = head_->next();
+ }
+ }
+
+ const Constraint* head() const { return head_; }
+
+ private:
+ VariableLimits() {}
+ explicit VariableLimits(const VariableLimits* other)
+ : head_(other->head_), limit_count_(other->limit_count_) {}
+
+ const Constraint* head_ = nullptr;
+ size_t limit_count_ = 0;
+};
+
+void InductionVariable::AddUpperBound(Node* bound,
+ InductionVariable::ConstraintKind kind) {
+ if (FLAG_trace_turbo_loop) {
+ OFStream os(stdout);
+ os << "New upper bound for " << phi()->id() << " (loop "
+ << NodeProperties::GetControlInput(phi())->id() << "): " << *bound
+ << std::endl;
+ }
+ upper_bounds_.push_back(Bound(bound, kind));
+}
+
+void InductionVariable::AddLowerBound(Node* bound,
+ InductionVariable::ConstraintKind kind) {
+ if (FLAG_trace_turbo_loop) {
+ OFStream os(stdout);
+ os << "New lower bound for " << phi()->id() << " (loop "
+ << NodeProperties::GetControlInput(phi())->id() << "): " << *bound;
+ }
+ lower_bounds_.push_back(Bound(bound, kind));
+}
+
+void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) {
+ if (loop->op()->ControlInputCount() != 2) return;
+
+ // Go through the constraints, and update the induction variables in
+ // this loop if they are involved in the constraint.
+ const VariableLimits* limits = limits_[from->id()];
+ for (const Constraint* constraint = limits->head(); constraint != nullptr;
+ constraint = constraint->next()) {
+ if (constraint->left()->opcode() == IrOpcode::kPhi &&
+ NodeProperties::GetControlInput(constraint->left()) == loop) {
+ auto var = induction_vars_.find(constraint->left()->id());
+ if (var != induction_vars_.end()) {
+ var->second->AddUpperBound(constraint->right(), constraint->kind());
+ }
+ }
+ if (constraint->right()->opcode() == IrOpcode::kPhi &&
+ NodeProperties::GetControlInput(constraint->right()) == loop) {
+ auto var = induction_vars_.find(constraint->right()->id());
+ if (var != induction_vars_.end()) {
+ var->second->AddLowerBound(constraint->left(), constraint->kind());
+ }
+ }
+ }
+}
+
+void LoopVariableOptimizer::VisitNode(Node* node) {
+ switch (node->opcode()) {
+ case IrOpcode::kMerge:
+ return VisitMerge(node);
+ case IrOpcode::kLoop:
+ return VisitLoop(node);
+ case IrOpcode::kIfFalse:
+ return VisitIf(node, false);
+ case IrOpcode::kIfTrue:
+ return VisitIf(node, true);
+ case IrOpcode::kStart:
+ return VisitStart(node);
+ case IrOpcode::kLoopExit:
+ return VisitLoopExit(node);
+ default:
+ return VisitOtherControl(node);
+ }
+}
+
+void LoopVariableOptimizer::VisitMerge(Node* node) {
+ // Merge the limits of all incoming edges.
+ VariableLimits* merged = limits_[node->InputAt(0)->id()]->Copy(zone());
+ for (int i = 1; i < node->InputCount(); i++) {
+ merged->Merge(limits_[node->InputAt(i)->id()]);
+ }
+ limits_[node->id()] = merged;
+}
+
+void LoopVariableOptimizer::VisitLoop(Node* node) {
+ DetectInductionVariables(node);
+ // Conservatively take the limits from the loop entry here.
+ return TakeConditionsFromFirstControl(node);
+}
+
+void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) {
+ Node* branch = node->InputAt(0);
+ Node* cond = branch->InputAt(0);
+ VariableLimits* limits = limits_[branch->id()]->Copy(zone());
+ // Normalize to less than comparison.
+ switch (cond->opcode()) {
+ case IrOpcode::kJSLessThan:
+ AddCmpToLimits(limits, cond, InductionVariable::kStrict, polarity);
+ break;
+ case IrOpcode::kJSGreaterThan:
+ AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, !polarity);
+ break;
+ case IrOpcode::kJSLessThanOrEqual:
+ AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, polarity);
+ break;
+ case IrOpcode::kJSGreaterThanOrEqual:
+ AddCmpToLimits(limits, cond, InductionVariable::kStrict, !polarity);
+ break;
+ default:
+ break;
+ }
+ limits_[node->id()] = limits;
+}
+
+void LoopVariableOptimizer::AddCmpToLimits(
+ VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind,
+ bool polarity) {
+ Node* left = node->InputAt(0);
+ Node* right = node->InputAt(1);
+ if (FindInductionVariable(left) || FindInductionVariable(right)) {
+ if (polarity) {
+ limits->Add(left, kind, right, zone());
+ } else {
+ kind = (kind == InductionVariable::kStrict)
+ ? InductionVariable::kNonStrict
+ : InductionVariable::kStrict;
+ limits->Add(right, kind, left, zone());
+ }
+ }
+}
+
+void LoopVariableOptimizer::VisitStart(Node* node) {
+ limits_[node->id()] = VariableLimits::Empty(zone());
+}
+
+void LoopVariableOptimizer::VisitLoopExit(Node* node) {
+ return TakeConditionsFromFirstControl(node);
+}
+
+void LoopVariableOptimizer::VisitOtherControl(Node* node) {
+ DCHECK_EQ(1, node->op()->ControlInputCount());
+ return TakeConditionsFromFirstControl(node);
+}
+
+void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) {
+ const VariableLimits* limits =
+ limits_[NodeProperties::GetControlInput(node, 0)->id()];
+ DCHECK_NOT_NULL(limits);
+ limits_[node->id()] = limits;
+}
+
+const InductionVariable* LoopVariableOptimizer::FindInductionVariable(
+ Node* node) {
+ auto var = induction_vars_.find(node->id());
+ if (var != induction_vars_.end()) {
+ return var->second;
+ }
+ return nullptr;
+}
+
+InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
+ DCHECK_EQ(2, phi->op()->ValueInputCount());
+ DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(phi)->opcode());
+ Node* initial = phi->InputAt(0);
+ Node* arith = phi->InputAt(1);
+ InductionVariable::ArithmeticType arithmeticType;
+ if (arith->opcode() == IrOpcode::kJSAdd) {
+ arithmeticType = InductionVariable::ArithmeticType::kAddition;
+ } else if (arith->opcode() == IrOpcode::kJSSubtract) {
+ arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
+ } else {
+ return nullptr;
+ }
+
+ // TODO(jarin) Support both sides.
+ if (arith->InputAt(0) != phi) {
+ if (arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber ||
+ arith->InputAt(0)->InputAt(0) != phi) {
+ return nullptr;
+ }
+ }
+ Node* incr = arith->InputAt(1);
+ return new (zone())
+ InductionVariable(phi, arith, incr, initial, zone(), arithmeticType);
+}
+
+void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
+ if (loop->op()->ControlInputCount() != 2) return;
+ TRACE("Loop variables for loop %i:", loop->id());
+ for (Edge edge : loop->use_edges()) {
+ if (NodeProperties::IsControlEdge(edge) &&
+ edge.from()->opcode() == IrOpcode::kPhi) {
+ Node* phi = edge.from();
+ InductionVariable* induction_var = TryGetInductionVariable(phi);
+ if (induction_var) {
+ induction_vars_[phi->id()] = induction_var;
+ TRACE(" %i", induction_var->phi()->id());
+ }
+ }
+ }
+ TRACE("\n");
+}
+
+void LoopVariableOptimizer::ChangeToInductionVariablePhis() {
+ for (auto entry : induction_vars_) {
+ // It only make sense to analyze the induction variables if
+ // there is a bound.
+ InductionVariable* induction_var = entry.second;
+ DCHECK_EQ(MachineRepresentation::kTagged,
+ PhiRepresentationOf(induction_var->phi()->op()));
+ if (induction_var->upper_bounds().size() == 0 &&
+ induction_var->lower_bounds().size() == 0) {
+ continue;
+ }
+ // Insert the increment value to the value inputs.
+ induction_var->phi()->InsertInput(graph()->zone(),
+ induction_var->phi()->InputCount() - 1,
+ induction_var->increment());
+ // Insert the bound inputs to the value inputs.
+ for (auto bound : induction_var->lower_bounds()) {
+ induction_var->phi()->InsertInput(
+ graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
+ }
+ for (auto bound : induction_var->upper_bounds()) {
+ induction_var->phi()->InsertInput(
+ graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound);
+ }
+ NodeProperties::ChangeOp(
+ induction_var->phi(),
+ common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1));
+ }
+}
+
+void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() {
+ for (auto entry : induction_vars_) {
+ InductionVariable* induction_var = entry.second;
+ if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) {
+ // Turn the induction variable phi back to normal phi.
+ int value_count = 2;
+ Node* control = NodeProperties::GetControlInput(induction_var->phi());
+ DCHECK_EQ(value_count, control->op()->ControlInputCount());
+ induction_var->phi()->TrimInputCount(value_count + 1);
+ induction_var->phi()->ReplaceInput(value_count, control);
+ NodeProperties::ChangeOp(
+ induction_var->phi(),
+ common()->Phi(MachineRepresentation::kTagged, value_count));
+
+ // If the backedge is not a subtype of the phi's type, we insert a sigma
+ // to get the typing right.
+ Node* backedge_value = induction_var->phi()->InputAt(1);
+ Type* backedge_type = NodeProperties::GetType(backedge_value);
+ Type* phi_type = NodeProperties::GetType(induction_var->phi());
+ if (!backedge_type->Is(phi_type)) {
+ Node* backedge_control =
+ NodeProperties::GetControlInput(induction_var->phi())->InputAt(1);
+ Node* rename = graph()->NewNode(common()->TypeGuard(phi_type),
+ backedge_value, backedge_control);
+ induction_var->phi()->ReplaceInput(1, rename);
+ }
+ }
+ }
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
