blob: 39032ef6685cab0cb504f0660e58a263935dca1f [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/functional-list.h"
#include "src/compiler/node-aux-data.h"
#include "src/zone/zone-containers.h"
namespace v8 {
namespace internal {
namespace compiler {
class CommonOperatorBuilder;
class Graph;
class Node;
class InductionVariable : public ZoneObject {
Node* phi() const { return phi_; }
Node* effect_phi() const { return effect_phi_; }
Node* arith() const { return arith_; }
Node* increment() const { return increment_; }
Node* init_value() const { return init_value_; }
enum ConstraintKind { kStrict, kNonStrict };
enum ArithmeticType { kAddition, kSubtraction };
struct Bound {
Bound(Node* bound, ConstraintKind kind) : bound(bound), kind(kind) {}
Node* bound;
ConstraintKind kind;
const ZoneVector<Bound>& lower_bounds() { return lower_bounds_; }
const ZoneVector<Bound>& upper_bounds() { return upper_bounds_; }
ArithmeticType Type() { return arithmeticType_; }
friend class LoopVariableOptimizer;
friend Zone;
InductionVariable(Node* phi, Node* effect_phi, Node* arith, Node* increment,
Node* init_value, Zone* zone, ArithmeticType arithmeticType)
: phi_(phi),
arithmeticType_(arithmeticType) {}
void AddUpperBound(Node* bound, ConstraintKind kind);
void AddLowerBound(Node* bound, ConstraintKind kind);
Node* phi_;
Node* effect_phi_;
Node* arith_;
Node* increment_;
Node* init_value_;
ZoneVector<Bound> lower_bounds_;
ZoneVector<Bound> upper_bounds_;
ArithmeticType arithmeticType_;
class LoopVariableOptimizer {
void Run();
LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
Zone* zone);
const ZoneMap<int, InductionVariable*>& induction_variables() {
return induction_vars_;
void ChangeToInductionVariablePhis();
void ChangeToPhisAndInsertGuards();
const int kAssumedLoopEntryIndex = 0;
const int kFirstBackedge = 1;
struct Constraint {
Node* left;
InductionVariable::ConstraintKind kind;
Node* right;
bool operator!=(const Constraint& other) const {
return left != other.left || kind != other.kind || right != other.right;
using VariableLimits = FunctionalList<Constraint>;
void VisitBackedge(Node* from, Node* loop);
void VisitNode(Node* node);
void VisitMerge(Node* node);
void VisitLoop(Node* node);
void VisitIf(Node* node, bool polarity);
void VisitStart(Node* node);
void VisitLoopExit(Node* node);
void VisitOtherControl(Node* node);
void AddCmpToLimits(VariableLimits* limits, Node* node,
InductionVariable::ConstraintKind kind, bool polarity);
void TakeConditionsFromFirstControl(Node* node);
const InductionVariable* FindInductionVariable(Node* node);
InductionVariable* TryGetInductionVariable(Node* phi);
void DetectInductionVariables(Node* loop);
Graph* graph() { return graph_; }
CommonOperatorBuilder* common() { return common_; }
Zone* zone() { return zone_; }
Graph* graph_;
CommonOperatorBuilder* common_;
Zone* zone_;
NodeAuxData<VariableLimits> limits_;
NodeAuxData<bool> reduced_;
ZoneMap<int, InductionVariable*> induction_vars_;
} // namespace compiler
} // namespace internal
} // namespace v8