// 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.

#ifndef V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_
#define V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_

#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 {
 public:
  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_; }

 private:
  friend class LoopVariableOptimizer;

  InductionVariable(Node* phi, Node* effect_phi, Node* arith, Node* increment,
                    Node* init_value, Zone* zone, ArithmeticType arithmeticType)
      : phi_(phi),
        effect_phi_(effect_phi),
        arith_(arith),
        increment_(increment),
        init_value_(init_value),
        lower_bounds_(zone),
        upper_bounds_(zone),
        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 {
 public:
  void Run();

  LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
                        Zone* zone);

  const ZoneMap<int, InductionVariable*>& induction_variables() {
    return induction_vars_;
  }

  void ChangeToInductionVariablePhis();
  void ChangeToPhisAndInsertGuards();

 private:
  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

#endif  // V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_