Line data Source code
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 :
14 : namespace v8 {
15 : namespace internal {
16 : namespace compiler {
17 :
18 : // TODO(titzer): don't assume entry edges have a particular index.
19 : static const int kAssumedLoopEntryIndex = 0; // assume loops are entered here.
20 :
21 : class LoopFinderImpl;
22 :
23 : typedef base::iterator_range<Node**> NodeRange;
24 :
25 : // Represents a tree of loops in a graph.
26 : class LoopTree : public ZoneObject {
27 : public:
28 622379 : 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 1867137 : 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 2905170 : class Loop {
38 : public:
39 : Loop* parent() const { return parent_; }
40 : const ZoneVector<Loop*>& children() const { return children_; }
41 1326 : 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 70634 : 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 1484562 : 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 5841322 : Loop* ContainingLoop(Node* node) {
70 11682644 : if (node->id() >= node_to_loop_num_.size()) return nullptr;
71 5840467 : int num = node_to_loop_num_[node->id()];
72 5840467 : 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 5835509 : bool Contains(Loop* loop, Node* node) {
78 5937908 : for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
79 5579392 : 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 742281 : 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 141770 : return NodeRange(&loop_nodes_[0] + loop->header_start_,
95 141770 : &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 33394 : return NodeRange(&loop_nodes_[0] + loop->body_start_,
104 33394 : &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 33394 : return NodeRange(&loop_nodes_[0] + loop->exits_start_,
110 33394 : &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 37180 : return NodeRange(&loop_nodes_[0] + loop->header_start_,
116 37180 : &loop_nodes_[0] + loop->exits_end_);
117 : }
118 :
119 : // Return the node that represents the control, i.e. the loop node itself.
120 70574 : Node* GetLoopControl(Loop* loop) {
121 : // TODO(turbofan): make the loop control node always first?
122 277886 : for (Node* node : HeaderNodes(loop)) {
123 277886 : if (node->opcode() == IrOpcode::kLoop) return node;
124 : }
125 0 : UNREACHABLE();
126 : return nullptr;
127 : }
128 :
129 : Zone* zone() const { return zone_; }
130 :
131 : private:
132 : friend class LoopFinderImpl;
133 :
134 742281 : Loop* NewLoop() {
135 2226843 : all_loops_.push_back(Loop(zone_));
136 : Loop* result = &all_loops_.back();
137 742281 : return result;
138 : }
139 :
140 742281 : void SetParent(Loop* parent, Loop* child) {
141 742281 : if (parent != nullptr) {
142 467764 : parent->children_.push_back(child);
143 467764 : child->parent_ = parent;
144 467764 : child->depth_ = parent->depth_ + 1;
145 : } else {
146 274517 : outer_loops_.push_back(child);
147 : }
148 742281 : }
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 :
157 : class 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_
|
