1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_COMPILER_LOOP_ANALYSIS_H_
6#define V8_COMPILER_LOOP_ANALYSIS_H_
7
8#include "src/base/iterator.h"
9#include "src/compiler/graph.h"
10#include "src/compiler/node.h"
11#include "src/globals.h"
12#include "src/zone/zone-containers.h"
13
14namespace v8 {
15namespace internal {
16namespace compiler {
17
18// TODO(titzer): don't assume entry edges have a particular index.
19static const int kAssumedLoopEntryIndex = 0;  // assume loops are entered here.
20
21class LoopFinderImpl;
22
23typedef base::iterator_range<Node**> NodeRange;
24
25// Represents a tree of loops in a graph.
26class LoopTree : public ZoneObject {
27 public:
28  LoopTree(size_t num_nodes, Zone* zone)
29      : zone_(zone),
30        outer_loops_(zone),
31        all_loops_(zone),
32        node_to_loop_num_(static_cast<int>(num_nodes), -1, zone),
33        loop_nodes_(zone) {}
34
35  // Represents a loop in the tree of loops, including the header nodes,
36  // the body, and any nested loops.
37  class Loop {
38   public:
39    Loop* parent() const { return parent_; }
40    const ZoneVector<Loop*>& children() const { return children_; }
41    size_t HeaderSize() const { return body_start_ - header_start_; }
42    size_t BodySize() const { return exits_start_ - body_start_; }
43    size_t ExitsSize() const { return exits_end_ - exits_start_; }
44    size_t TotalSize() const { return exits_end_ - header_start_; }
45    size_t depth() const { return static_cast<size_t>(depth_); }
46
47   private:
48    friend class LoopTree;
49    friend class LoopFinderImpl;
50
51    explicit Loop(Zone* zone)
52        : parent_(nullptr),
53          depth_(0),
54          children_(zone),
55          header_start_(-1),
56          body_start_(-1),
57          exits_start_(-1),
58          exits_end_(-1) {}
59    Loop* parent_;
60    int depth_;
61    ZoneVector<Loop*> children_;
62    int header_start_;
63    int body_start_;
64    int exits_start_;
65    int exits_end_;
66  };
67
68  // Return the innermost nested loop, if any, that contains {node}.
69  Loop* ContainingLoop(Node* node) {
70    if (node->id() >= node_to_loop_num_.size()) return nullptr;
71    int num = node_to_loop_num_[node->id()];
72    return num > 0 ? &all_loops_[num - 1] : nullptr;
73  }
74
75  // Check if the {loop} contains the {node}, either directly or by containing
76  // a nested loop that contains {node}.
77  bool Contains(Loop* loop, Node* node) {
78    for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
79      if (c == loop) return true;
80    }
81    return false;
82  }
83
84  // Return the list of outer loops.
85  const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }
86
87  // Return the unique loop number for a given loop. Loop numbers start at {1}.
88  int LoopNum(Loop* loop) const {
89    return 1 + static_cast<int>(loop - &all_loops_[0]);
90  }
91
92  // Return a range which can iterate over the header nodes of {loop}.
93  NodeRange HeaderNodes(Loop* loop) {
94    return NodeRange(&loop_nodes_[0] + loop->header_start_,
95                     &loop_nodes_[0] + loop->body_start_);
96  }
97
98  // Return the header control node for a loop.
99  Node* HeaderNode(Loop* loop);
100
101  // Return a range which can iterate over the body nodes of {loop}.
102  NodeRange BodyNodes(Loop* loop) {
103    return NodeRange(&loop_nodes_[0] + loop->body_start_,
104                     &loop_nodes_[0] + loop->exits_start_);
105  }
106
107  // Return a range which can iterate over the body nodes of {loop}.
108  NodeRange ExitNodes(Loop* loop) {
109    return NodeRange(&loop_nodes_[0] + loop->exits_start_,
110                     &loop_nodes_[0] + loop->exits_end_);
111  }
112
113  // Return a range which can iterate over the nodes of {loop}.
114  NodeRange LoopNodes(Loop* loop) {
115    return NodeRange(&loop_nodes_[0] + loop->header_start_,
116                     &loop_nodes_[0] + loop->exits_end_);
117  }
118
119  // Return the node that represents the control, i.e. the loop node itself.
120  Node* GetLoopControl(Loop* loop) {
121    // TODO(turbofan): make the loop control node always first?
122    for (Node* node : HeaderNodes(loop)) {
123      if (node->opcode() == IrOpcode::kLoop) return node;
124    }
125    UNREACHABLE();
126    return nullptr;
127  }
128
129  Zone* zone() const { return zone_; }
130
131 private:
132  friend class LoopFinderImpl;
133
134  Loop* NewLoop() {
135    all_loops_.push_back(Loop(zone_));
136    Loop* result = &all_loops_.back();
137    return result;
138  }
139
140  void SetParent(Loop* parent, Loop* child) {
141    if (parent != nullptr) {
142      parent->children_.push_back(child);
143      child->parent_ = parent;
144      child->depth_ = parent->depth_ + 1;
145    } else {
146      outer_loops_.push_back(child);
147    }
148  }
149
150  Zone* zone_;
151  ZoneVector<Loop*> outer_loops_;
152  ZoneVector<Loop> all_loops_;
153  ZoneVector<int> node_to_loop_num_;
154  ZoneVector<Node*> loop_nodes_;
155};
156
157class V8_EXPORT_PRIVATE LoopFinder {
158 public:
159  // Build a loop tree for the entire graph.
160  static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone);
161};
162
163
164}  // namespace compiler
165}  // namespace internal
166}  // namespace v8
167
168#endif  // V8_COMPILER_LOOP_ANALYSIS_H_
169