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 : using NodeRange = base::iterator_range<Node**>;
24 :
25 : // Represents a tree of loops in a graph.
26 : class LoopTree : public ZoneObject {
27 : public:
28 623720 : 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 1871163 : 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 2606836 : class Loop {
38 : public:
39 : Loop* parent() const { return parent_; }
40 : const ZoneVector<Loop*>& children() const { return children_; }
41 491165 : size_t HeaderSize() const { return body_start_ - header_start_; }
42 491165 : size_t BodySize() const { return exits_start_ - body_start_; }
43 : size_t ExitsSize() const { return exits_end_ - exits_start_; }
44 63361 : size_t TotalSize() const { return exits_end_ - header_start_; }
45 2 : 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 1064750 : 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 24871796 : if (node->id() >= node_to_loop_num_.size()) return nullptr;
71 12841353 : int num = node_to_loop_num_[node->id()];
72 12841353 : 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 10069401 : bool Contains(Loop* loop, Node* node) {
78 27078825 : for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
79 17891107 : 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 532364 : 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 1098860 : return NodeRange(&loop_nodes_[0] + loop->header_start_,
95 1098860 : &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 4626062 : return NodeRange(&loop_nodes_[0] + loop->body_start_,
104 4626062 : &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 26667 : return NodeRange(&loop_nodes_[0] + loop->exits_start_,
110 26667 : &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 36659 : return NodeRange(&loop_nodes_[0] + loop->header_start_,
116 36659 : &loop_nodes_[0] + loop->exits_end_);
117 : }
118 :
119 : // Return the node that represents the control, i.e. the loop node itself.
120 63325 : Node* GetLoopControl(Loop* loop) {
121 : // TODO(turbofan): make the loop control node always first?
122 411511 : for (Node* node : HeaderNodes(loop)) {
123 237418 : if (node->opcode() == IrOpcode::kLoop) return node;
124 : }
125 0 : UNREACHABLE();
126 : }
127 :
128 : Zone* zone() const { return zone_; }
129 :
130 : private:
131 : friend class LoopFinderImpl;
132 :
133 532375 : Loop* NewLoop() {
134 1597126 : all_loops_.push_back(Loop(zone_));
135 : Loop* result = &all_loops_.back();
136 532376 : return result;
137 : }
138 :
139 506874 : void SetParent(Loop* parent, Loop* child) {
140 506874 : if (parent != nullptr) {
141 331911 : parent->children_.push_back(child);
142 331911 : child->parent_ = parent;
143 331911 : child->depth_ = parent->depth_ + 1;
144 : } else {
145 200465 : outer_loops_.push_back(child);
146 : }
147 506874 : }
148 :
149 : Zone* zone_;
150 : ZoneVector<Loop*> outer_loops_;
151 : ZoneVector<Loop> all_loops_;
152 : ZoneVector<int> node_to_loop_num_;
153 : ZoneVector<Node*> loop_nodes_;
154 : };
155 :
156 : class V8_EXPORT_PRIVATE LoopFinder {
157 : public:
158 : // Build a loop tree for the entire graph.
159 : static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone);
160 : };
161 :
162 :
163 : } // namespace compiler
164 : } // namespace internal
165 : } // namespace v8
166 :
167 : #endif // V8_COMPILER_LOOP_ANALYSIS_H_
|
