loop-variable-optimizer.h 3.69 KB
Newer Older
1 2 3 4 5 6 7
// 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_

8 9
#include "src/compiler/functional-list.h"
#include "src/compiler/node-aux-data.h"
10
#include "src/zone/zone-containers.h"
11 12 13 14 15 16 17 18 19 20 21 22

namespace v8 {
namespace internal {
namespace compiler {

class CommonOperatorBuilder;
class Graph;
class Node;

class InductionVariable : public ZoneObject {
 public:
  Node* phi() const { return phi_; }
23
  Node* effect_phi() const { return effect_phi_; }
24 25 26 27 28
  Node* arith() const { return arith_; }
  Node* increment() const { return increment_; }
  Node* init_value() const { return init_value_; }

  enum ConstraintKind { kStrict, kNonStrict };
29
  enum ArithmeticType { kAddition, kSubtraction };
30 31 32 33 34 35 36 37 38 39
  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_; }

40 41
  ArithmeticType Type() { return arithmeticType_; }

42 43
 private:
  friend class LoopVariableOptimizer;
44
  friend Zone;
45

46 47
  InductionVariable(Node* phi, Node* effect_phi, Node* arith, Node* increment,
                    Node* init_value, Zone* zone, ArithmeticType arithmeticType)
48
      : phi_(phi),
49
        effect_phi_(effect_phi),
50 51 52 53
        arith_(arith),
        increment_(increment),
        init_value_(init_value),
        lower_bounds_(zone),
54 55
        upper_bounds_(zone),
        arithmeticType_(arithmeticType) {}
56

57 58
  void AddUpperBound(Node* bound, ConstraintKind kind);
  void AddLowerBound(Node* bound, ConstraintKind kind);
59 60

  Node* phi_;
61
  Node* effect_phi_;
62 63 64 65 66
  Node* arith_;
  Node* increment_;
  Node* init_value_;
  ZoneVector<Bound> lower_bounds_;
  ZoneVector<Bound> upper_bounds_;
67
  ArithmeticType arithmeticType_;
68 69 70 71 72 73 74 75 76 77 78 79 80 81
};

class LoopVariableOptimizer {
 public:
  void Run();

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

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

  void ChangeToInductionVariablePhis();
82
  void ChangeToPhisAndInsertGuards();
83 84 85 86 87

 private:
  const int kAssumedLoopEntryIndex = 0;
  const int kFirstBackedge = 1;

88 89 90 91 92 93 94 95 96 97 98
  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>;
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

  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_;
124 125 126
  NodeAuxData<VariableLimits> limits_;
  NodeAuxData<bool> reduced_;

127 128 129 130 131 132 133 134
  ZoneMap<int, InductionVariable*> induction_vars_;
};

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_