blob: 1e93de51248f71c2215a83de8698923e91735df0 [file] [log] [blame]
// 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),
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_NULL(limits_[node->id()]);
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 (limits_[NodeProperties::GetControlInput(node, i)->id()] == nullptr) {
all_inputs_visited = false;
break;
}
}
if (!all_inputs_visited) continue;
VisitNode(node);
DCHECK_NOT_NULL(limits_[node->id()]);
// 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_LT(0, limit_count_);
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:
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_[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());
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.
if (arith->InputAt(0) != 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