// 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::kSpeculativeNumberLessThan:
|
AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity);
|
break;
|
case IrOpcode::kJSGreaterThan:
|
AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity);
|
break;
|
case IrOpcode::kJSLessThanOrEqual:
|
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::kSpeculativeNumberAdd ||
|
arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) {
|
arithmeticType = InductionVariable::ArithmeticType::kAddition;
|
} else if (arith->opcode() == IrOpcode::kJSSubtract ||
|
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
|
