loop-analysis.h 5.02 KB
Newer Older
1 2 3 4 5 6 7 8
// Copyright 2014 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_ANALYSIS_H_
#define V8_COMPILER_LOOP_ANALYSIS_H_

#include "src/base/iterator.h"
9
#include "src/common/globals.h"
10 11
#include "src/compiler/graph.h"
#include "src/compiler/node.h"
12
#include "src/zone/zone-containers.h"
13 14 15

namespace v8 {
namespace internal {
16 17 18

class TickCounter;

19 20
namespace compiler {

21 22 23
// TODO(titzer): don't assume entry edges have a particular index.
static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.

24 25
class LoopFinderImpl;

26
using NodeRange = base::iterator_range<Node**>;
27 28 29 30 31 32 33 34

// Represents a tree of loops in a graph.
class LoopTree : public ZoneObject {
 public:
  LoopTree(size_t num_nodes, Zone* zone)
      : zone_(zone),
        outer_loops_(zone),
        all_loops_(zone),
35
        node_to_loop_num_(static_cast<int>(num_nodes), -1, zone),
36 37 38 39 40 41 42 43 44
        loop_nodes_(zone) {}

  // Represents a loop in the tree of loops, including the header nodes,
  // the body, and any nested loops.
  class Loop {
   public:
    Loop* parent() const { return parent_; }
    const ZoneVector<Loop*>& children() const { return children_; }
    size_t HeaderSize() const { return body_start_ - header_start_; }
45 46 47
    size_t BodySize() const { return exits_start_ - body_start_; }
    size_t ExitsSize() const { return exits_end_ - exits_start_; }
    size_t TotalSize() const { return exits_end_ - header_start_; }
48
    size_t depth() const { return static_cast<size_t>(depth_); }
49 50 51 52 53 54 55 56 57 58 59

   private:
    friend class LoopTree;
    friend class LoopFinderImpl;

    explicit Loop(Zone* zone)
        : parent_(nullptr),
          depth_(0),
          children_(zone),
          header_start_(-1),
          body_start_(-1),
60 61
          exits_start_(-1),
          exits_end_(-1) {}
62 63 64 65 66
    Loop* parent_;
    int depth_;
    ZoneVector<Loop*> children_;
    int header_start_;
    int body_start_;
67 68
    int exits_start_;
    int exits_end_;
69 70 71 72
  };

  // Return the innermost nested loop, if any, that contains {node}.
  Loop* ContainingLoop(Node* node) {
73
    if (node->id() >= node_to_loop_num_.size()) return nullptr;
74
    int num = node_to_loop_num_[node->id()];
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
    return num > 0 ? &all_loops_[num - 1] : nullptr;
  }

  // Check if the {loop} contains the {node}, either directly or by containing
  // a nested loop that contains {node}.
  bool Contains(Loop* loop, Node* node) {
    for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
      if (c == loop) return true;
    }
    return false;
  }

  // Return the list of outer loops.
  const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }

  // Return the unique loop number for a given loop. Loop numbers start at {1}.
  int LoopNum(Loop* loop) const {
    return 1 + static_cast<int>(loop - &all_loops_[0]);
  }

  // Return a range which can iterate over the header nodes of {loop}.
  NodeRange HeaderNodes(Loop* loop) {
    return NodeRange(&loop_nodes_[0] + loop->header_start_,
                     &loop_nodes_[0] + loop->body_start_);
  }

101 102 103
  // Return the header control node for a loop.
  Node* HeaderNode(Loop* loop);

104 105 106
  // Return a range which can iterate over the body nodes of {loop}.
  NodeRange BodyNodes(Loop* loop) {
    return NodeRange(&loop_nodes_[0] + loop->body_start_,
107 108 109 110 111 112 113
                     &loop_nodes_[0] + loop->exits_start_);
  }

  // Return a range which can iterate over the body nodes of {loop}.
  NodeRange ExitNodes(Loop* loop) {
    return NodeRange(&loop_nodes_[0] + loop->exits_start_,
                     &loop_nodes_[0] + loop->exits_end_);
114 115
  }

116 117 118
  // Return a range which can iterate over the nodes of {loop}.
  NodeRange LoopNodes(Loop* loop) {
    return NodeRange(&loop_nodes_[0] + loop->header_start_,
119
                     &loop_nodes_[0] + loop->exits_end_);
120 121 122 123 124 125 126 127 128 129 130
  }

  // Return the node that represents the control, i.e. the loop node itself.
  Node* GetLoopControl(Loop* loop) {
    // TODO(turbofan): make the loop control node always first?
    for (Node* node : HeaderNodes(loop)) {
      if (node->opcode() == IrOpcode::kLoop) return node;
    }
    UNREACHABLE();
  }

131 132
  Zone* zone() const { return zone_; }

133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
 private:
  friend class LoopFinderImpl;

  Loop* NewLoop() {
    all_loops_.push_back(Loop(zone_));
    Loop* result = &all_loops_.back();
    return result;
  }

  void SetParent(Loop* parent, Loop* child) {
    if (parent != nullptr) {
      parent->children_.push_back(child);
      child->parent_ = parent;
      child->depth_ = parent->depth_ + 1;
    } else {
      outer_loops_.push_back(child);
    }
  }

  Zone* zone_;
  ZoneVector<Loop*> outer_loops_;
  ZoneVector<Loop> all_loops_;
155
  ZoneVector<int> node_to_loop_num_;
156 157 158
  ZoneVector<Node*> loop_nodes_;
};

159
class V8_EXPORT_PRIVATE LoopFinder {
160 161
 public:
  // Build a loop tree for the entire graph.
162 163
  static LoopTree* BuildLoopTree(Graph* graph, TickCounter* tick_counter,
                                 Zone* temp_zone);
164 165
};

166

167 168 169 170 171
}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_LOOP_ANALYSIS_H_