// 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/zone-containers.h" #include "src/zone/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_(graph->NodeCount(), zone), reduced_(graph->NodeCount(), 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(!reduced_.Get(node)); bool all_inputs_visited = true; int inputs_end = (node->opcode() == IrOpcode::kLoop) ? kFirstBackedge : node->op()->ControlInputCount(); for (int i = 0; i < inputs_end; i++) { if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) { all_inputs_visited = false; break; } } if (!all_inputs_visited) continue; VisitNode(node); reduced_.Set(node, true); // 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); } } } } } void InductionVariable::AddUpperBound(Node* bound, InductionVariable::ConstraintKind kind) { if (FLAG_trace_turbo_loop) { StdoutStream{} << "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) { StdoutStream{} << "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. for (Constraint constraint : limits_.Get(from)) { 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_.Get(node->InputAt(0)); for (int i = 1; i < node->InputCount(); i++) { merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i))); } limits_.Set(node, 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_.Get(branch); // Normalize to less than comparison. switch (cond->opcode()) { case IrOpcode::kJSLessThan: case IrOpcode::kNumberLessThan: case IrOpcode::kSpeculativeNumberLessThan: AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity); break; case IrOpcode::kJSGreaterThan: AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity); break; case IrOpcode::kJSLessThanOrEqual: case IrOpcode::kNumberLessThanOrEqual: case IrOpcode::kSpeculativeNumberLessThanOrEqual: AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity); break; case IrOpcode::kJSGreaterThanOrEqual: AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity); break; default: break; } limits_.Set(node, 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->PushFront(Constraint{left, kind, right}, zone()); } else { kind = (kind == InductionVariable::kStrict) ? InductionVariable::kNonStrict : InductionVariable::kStrict; limits->PushFront(Constraint{right, kind, left}, zone()); } } } void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); } 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) { limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0))); } 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()); Node* loop = NodeProperties::GetControlInput(phi); DCHECK_EQ(IrOpcode::kLoop, loop->opcode()); Node* initial = phi->InputAt(0); Node* arith = phi->InputAt(1); InductionVariable::ArithmeticType arithmeticType; if (arith->opcode() == IrOpcode::kJSAdd || arith->opcode() == IrOpcode::kNumberAdd || arith->opcode() == IrOpcode::kSpeculativeNumberAdd || arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) { arithmeticType = InductionVariable::ArithmeticType::kAddition; } else if (arith->opcode() == IrOpcode::kJSSubtract || arith->opcode() == IrOpcode::kNumberSubtract || arith->opcode() == IrOpcode::kSpeculativeNumberSubtract || arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) { arithmeticType = InductionVariable::ArithmeticType::kSubtraction; } else { return nullptr; } // TODO(jarin) Support both sides. Node* input = arith->InputAt(0); if (input->opcode() == IrOpcode::kSpeculativeToNumber || input->opcode() == IrOpcode::kJSToNumber || input->opcode() == IrOpcode::kJSToNumberConvertBigInt) { input = input->InputAt(0); } if (input != phi) return nullptr; Node* effect_phi = nullptr; for (Node* use : loop->uses()) { if (use->opcode() == IrOpcode::kEffectPhi) { DCHECK_NULL(effect_phi); effect_phi = use; } } if (!effect_phi) return nullptr; Node* incr = arith->InputAt(1); return new (zone()) InductionVariable(phi, effect_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* loop = NodeProperties::GetControlInput(induction_var->phi()); Node* backedge_control = loop->InputAt(1); Node* backedge_effect = NodeProperties::GetEffectInput(induction_var->effect_phi(), 1); Node* rename = graph()->NewNode(common()->TypeGuard(phi_type), backedge_value, backedge_effect, backedge_control); induction_var->effect_phi()->ReplaceInput(1, rename); induction_var->phi()->ReplaceInput(1, rename); } } } } #undef TRACE } // namespace compiler } // namespace internal } // namespace v8