diff options
Diffstat (limited to 'deps/v8/src/compiler/loop-variable-optimizer.cc')
| -rw-r--r-- | deps/v8/src/compiler/loop-variable-optimizer.cc | 406 |
1 files changed, 406 insertions, 0 deletions
diff --git a/deps/v8/src/compiler/loop-variable-optimizer.cc b/deps/v8/src/compiler/loop-variable-optimizer.cc new file mode 100644 index 0000000000..8331963a7d --- /dev/null +++ b/deps/v8/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 |