Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 1 | // Copyright 2014 the V8 project authors. All rights reserved. |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 5 | #include "src/compiler/loop-analysis.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 6 | |
| 7 | #include "src/compiler/graph.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 8 | #include "src/compiler/node.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 9 | #include "src/compiler/node-marker.h" |
| 10 | #include "src/compiler/node-properties.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 11 | #include "src/zone.h" |
| 12 | |
| 13 | namespace v8 { |
| 14 | namespace internal { |
| 15 | namespace compiler { |
| 16 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 17 | #define OFFSET(x) ((x)&0x1f) |
| 18 | #define BIT(x) (1u << OFFSET(x)) |
| 19 | #define INDEX(x) ((x) >> 5) |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 20 | |
| 21 | // Temporary information for each node during marking. |
| 22 | struct NodeInfo { |
| 23 | Node* node; |
| 24 | NodeInfo* next; // link in chaining loop members |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 25 | }; |
| 26 | |
| 27 | |
| 28 | // Temporary loop info needed during traversal and building the loop tree. |
| 29 | struct LoopInfo { |
| 30 | Node* header; |
| 31 | NodeInfo* header_list; |
| 32 | NodeInfo* body_list; |
| 33 | LoopTree::Loop* loop; |
| 34 | }; |
| 35 | |
| 36 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 37 | // Encapsulation of the loop finding algorithm. |
| 38 | // ----------------------------------------------------------------------------- |
| 39 | // Conceptually, the contents of a loop are those nodes that are "between" the |
| 40 | // loop header and the backedges of the loop. Graphs in the soup of nodes can |
| 41 | // form improper cycles, so standard loop finding algorithms that work on CFGs |
| 42 | // aren't sufficient. However, in valid TurboFan graphs, all cycles involve |
| 43 | // either a {Loop} node or a phi. The {Loop} node itself and its accompanying |
| 44 | // phis are treated together as a set referred to here as the loop header. |
| 45 | // This loop finding algorithm works by traversing the graph in two directions, |
| 46 | // first from nodes to their inputs, starting at {end}, then in the reverse |
| 47 | // direction, from nodes to their uses, starting at loop headers. |
| 48 | // 1 bit per loop per node per direction are required during the marking phase. |
| 49 | // To handle nested loops correctly, the algorithm must filter some reachability |
| 50 | // marks on edges into/out-of the loop header nodes. |
| 51 | class LoopFinderImpl { |
| 52 | public: |
| 53 | LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 54 | : zone_(zone), |
| 55 | end_(graph->end()), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 56 | queue_(zone), |
| 57 | queued_(graph, 2), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 58 | info_(graph->NodeCount(), {nullptr, nullptr}, zone), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 59 | loops_(zone), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 60 | loop_num_(graph->NodeCount(), -1, zone), |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 61 | loop_tree_(loop_tree), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 62 | loops_found_(0), |
| 63 | width_(0), |
| 64 | backward_(nullptr), |
| 65 | forward_(nullptr) {} |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 66 | |
| 67 | void Run() { |
| 68 | PropagateBackward(); |
| 69 | PropagateForward(); |
| 70 | FinishLoopTree(); |
| 71 | } |
| 72 | |
| 73 | void Print() { |
| 74 | // Print out the results. |
| 75 | for (NodeInfo& ni : info_) { |
| 76 | if (ni.node == nullptr) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 77 | for (int i = 1; i <= loops_found_; i++) { |
| 78 | int index = ni.node->id() * width_ + INDEX(i); |
| 79 | bool marked_forward = forward_[index] & BIT(i); |
| 80 | bool marked_backward = backward_[index] & BIT(i); |
| 81 | if (marked_forward && marked_backward) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 82 | PrintF("X"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 83 | } else if (marked_forward) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 84 | PrintF("/"); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 85 | } else if (marked_backward) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 86 | PrintF("\\"); |
| 87 | } else { |
| 88 | PrintF(" "); |
| 89 | } |
| 90 | } |
| 91 | PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic()); |
| 92 | } |
| 93 | |
| 94 | int i = 0; |
| 95 | for (LoopInfo& li : loops_) { |
| 96 | PrintF("Loop %d headed at #%d\n", i, li.header->id()); |
| 97 | i++; |
| 98 | } |
| 99 | |
| 100 | for (LoopTree::Loop* loop : loop_tree_->outer_loops_) { |
| 101 | PrintLoop(loop); |
| 102 | } |
| 103 | } |
| 104 | |
| 105 | private: |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 106 | Zone* zone_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 107 | Node* end_; |
| 108 | NodeDeque queue_; |
| 109 | NodeMarker<bool> queued_; |
| 110 | ZoneVector<NodeInfo> info_; |
| 111 | ZoneVector<LoopInfo> loops_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 112 | ZoneVector<int> loop_num_; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 113 | LoopTree* loop_tree_; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 114 | int loops_found_; |
| 115 | int width_; |
| 116 | uint32_t* backward_; |
| 117 | uint32_t* forward_; |
| 118 | |
| 119 | int num_nodes() { |
| 120 | return static_cast<int>(loop_tree_->node_to_loop_num_.size()); |
| 121 | } |
| 122 | |
| 123 | // Tb = Tb | (Fb - loop_filter) |
| 124 | bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) { |
| 125 | if (from == to) return false; |
| 126 | uint32_t* fp = &backward_[from->id() * width_]; |
| 127 | uint32_t* tp = &backward_[to->id() * width_]; |
| 128 | bool change = false; |
| 129 | for (int i = 0; i < width_; i++) { |
| 130 | uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF; |
| 131 | uint32_t prev = tp[i]; |
| 132 | uint32_t next = prev | (fp[i] & mask); |
| 133 | tp[i] = next; |
| 134 | if (!change && (prev != next)) change = true; |
| 135 | } |
| 136 | return change; |
| 137 | } |
| 138 | |
| 139 | // Tb = Tb | B |
| 140 | bool SetBackwardMark(Node* to, int loop_num) { |
| 141 | uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)]; |
| 142 | uint32_t prev = tp[0]; |
| 143 | uint32_t next = prev | BIT(loop_num); |
| 144 | tp[0] = next; |
| 145 | return next != prev; |
| 146 | } |
| 147 | |
| 148 | // Tf = Tf | B |
| 149 | bool SetForwardMark(Node* to, int loop_num) { |
| 150 | uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)]; |
| 151 | uint32_t prev = tp[0]; |
| 152 | uint32_t next = prev | BIT(loop_num); |
| 153 | tp[0] = next; |
| 154 | return next != prev; |
| 155 | } |
| 156 | |
| 157 | // Tf = Tf | (Ff & Tb) |
| 158 | bool PropagateForwardMarks(Node* from, Node* to) { |
| 159 | if (from == to) return false; |
| 160 | bool change = false; |
| 161 | int findex = from->id() * width_; |
| 162 | int tindex = to->id() * width_; |
| 163 | for (int i = 0; i < width_; i++) { |
| 164 | uint32_t marks = backward_[tindex + i] & forward_[findex + i]; |
| 165 | uint32_t prev = forward_[tindex + i]; |
| 166 | uint32_t next = prev | marks; |
| 167 | forward_[tindex + i] = next; |
| 168 | if (!change && (prev != next)) change = true; |
| 169 | } |
| 170 | return change; |
| 171 | } |
| 172 | |
| 173 | bool IsInLoop(Node* node, int loop_num) { |
| 174 | int offset = node->id() * width_ + INDEX(loop_num); |
| 175 | return backward_[offset] & forward_[offset] & BIT(loop_num); |
| 176 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 177 | |
| 178 | // Propagate marks backward from loop headers. |
| 179 | void PropagateBackward() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 180 | ResizeBackwardMarks(); |
| 181 | SetBackwardMark(end_, 0); |
| 182 | Queue(end_); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 183 | |
| 184 | while (!queue_.empty()) { |
| 185 | Node* node = queue_.front(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 186 | info(node); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 187 | queue_.pop_front(); |
| 188 | queued_.Set(node, false); |
| 189 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 190 | int loop_num = -1; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 191 | // Setup loop headers first. |
| 192 | if (node->opcode() == IrOpcode::kLoop) { |
| 193 | // found the loop node first. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 194 | loop_num = CreateLoopInfo(node); |
| 195 | } else if (NodeProperties::IsPhi(node)) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 196 | // found a phi first. |
| 197 | Node* merge = node->InputAt(node->InputCount() - 1); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 198 | if (merge->opcode() == IrOpcode::kLoop) { |
| 199 | loop_num = CreateLoopInfo(merge); |
| 200 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 201 | } |
| 202 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 203 | // Propagate marks backwards from this node. |
| 204 | for (int i = 0; i < node->InputCount(); i++) { |
| 205 | Node* input = node->InputAt(i); |
| 206 | if (loop_num > 0 && i != kAssumedLoopEntryIndex) { |
| 207 | // Only propagate the loop mark on backedges. |
| 208 | if (SetBackwardMark(input, loop_num)) Queue(input); |
| 209 | } else { |
| 210 | // Entry or normal edge. Propagate all marks except loop_num. |
| 211 | if (PropagateBackwardMarks(node, input, loop_num)) Queue(input); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 212 | } |
| 213 | } |
| 214 | } |
| 215 | } |
| 216 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 217 | // Make a new loop if necessary for the given node. |
| 218 | int CreateLoopInfo(Node* node) { |
| 219 | int loop_num = LoopNum(node); |
| 220 | if (loop_num > 0) return loop_num; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 221 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 222 | loop_num = ++loops_found_; |
| 223 | if (INDEX(loop_num) >= width_) ResizeBackwardMarks(); |
| 224 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 225 | // Create a new loop. |
| 226 | loops_.push_back({node, nullptr, nullptr, nullptr}); |
| 227 | loop_tree_->NewLoop(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 228 | SetBackwardMark(node, loop_num); |
| 229 | loop_tree_->node_to_loop_num_[node->id()] = loop_num; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 230 | |
| 231 | // Setup loop mark for phis attached to loop header. |
| 232 | for (Node* use : node->uses()) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 233 | if (NodeProperties::IsPhi(use)) { |
| 234 | info(use); // create the NodeInfo |
| 235 | SetBackwardMark(use, loop_num); |
| 236 | loop_tree_->node_to_loop_num_[use->id()] = loop_num; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 237 | } |
| 238 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 239 | |
| 240 | return loop_num; |
| 241 | } |
| 242 | |
| 243 | void ResizeBackwardMarks() { |
| 244 | int new_width = width_ + 1; |
| 245 | int max = num_nodes(); |
| 246 | uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max); |
| 247 | memset(new_backward, 0, new_width * max * sizeof(uint32_t)); |
| 248 | if (width_ > 0) { // copy old matrix data. |
| 249 | for (int i = 0; i < max; i++) { |
| 250 | uint32_t* np = &new_backward[i * new_width]; |
| 251 | uint32_t* op = &backward_[i * width_]; |
| 252 | for (int j = 0; j < width_; j++) np[j] = op[j]; |
| 253 | } |
| 254 | } |
| 255 | width_ = new_width; |
| 256 | backward_ = new_backward; |
| 257 | } |
| 258 | |
| 259 | void ResizeForwardMarks() { |
| 260 | int max = num_nodes(); |
| 261 | forward_ = zone_->NewArray<uint32_t>(width_ * max); |
| 262 | memset(forward_, 0, width_ * max * sizeof(uint32_t)); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 263 | } |
| 264 | |
| 265 | // Propagate marks forward from loops. |
| 266 | void PropagateForward() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 267 | ResizeForwardMarks(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 268 | for (LoopInfo& li : loops_) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 269 | SetForwardMark(li.header, LoopNum(li.header)); |
| 270 | Queue(li.header); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 271 | } |
| 272 | // Propagate forward on paths that were backward reachable from backedges. |
| 273 | while (!queue_.empty()) { |
| 274 | Node* node = queue_.front(); |
| 275 | queue_.pop_front(); |
| 276 | queued_.Set(node, false); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 277 | for (Edge edge : node->use_edges()) { |
| 278 | Node* use = edge.from(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 279 | if (!IsBackedge(use, edge)) { |
| 280 | if (PropagateForwardMarks(node, use)) Queue(use); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 281 | } |
| 282 | } |
| 283 | } |
| 284 | } |
| 285 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 286 | bool IsBackedge(Node* use, Edge& edge) { |
| 287 | if (LoopNum(use) <= 0) return false; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 288 | if (edge.index() == kAssumedLoopEntryIndex) return false; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 289 | if (NodeProperties::IsPhi(use)) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 290 | return !NodeProperties::IsControlEdge(edge); |
| 291 | } |
| 292 | return true; |
| 293 | } |
| 294 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 295 | int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; } |
| 296 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 297 | NodeInfo& info(Node* node) { |
| 298 | NodeInfo& i = info_[node->id()]; |
| 299 | if (i.node == nullptr) i.node = node; |
| 300 | return i; |
| 301 | } |
| 302 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 303 | void Queue(Node* node) { |
| 304 | if (!queued_.Get(node)) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 305 | queue_.push_back(node); |
| 306 | queued_.Set(node, true); |
| 307 | } |
| 308 | } |
| 309 | |
| 310 | void FinishLoopTree() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 311 | DCHECK(loops_found_ == static_cast<int>(loops_.size())); |
| 312 | DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size())); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 313 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 314 | // Degenerate cases. |
| 315 | if (loops_found_ == 0) return; |
| 316 | if (loops_found_ == 1) return FinishSingleLoop(); |
| 317 | |
| 318 | for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 319 | |
| 320 | size_t count = 0; |
| 321 | // Place the node into the innermost nested loop of which it is a member. |
| 322 | for (NodeInfo& ni : info_) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 323 | if (ni.node == nullptr) continue; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 324 | |
| 325 | LoopInfo* innermost = nullptr; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 326 | int innermost_index = 0; |
| 327 | int pos = ni.node->id() * width_; |
| 328 | // Search the marks word by word. |
| 329 | for (int i = 0; i < width_; i++) { |
| 330 | uint32_t marks = backward_[pos + i] & forward_[pos + i]; |
| 331 | for (int j = 0; j < 32; j++) { |
| 332 | if (marks & (1u << j)) { |
| 333 | int loop_num = i * 32 + j; |
| 334 | if (loop_num == 0) continue; |
| 335 | LoopInfo* loop = &loops_[loop_num - 1]; |
| 336 | if (innermost == nullptr || |
| 337 | loop->loop->depth_ > innermost->loop->depth_) { |
| 338 | innermost = loop; |
| 339 | innermost_index = loop_num; |
| 340 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 341 | } |
| 342 | } |
| 343 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 344 | if (innermost == nullptr) continue; |
| 345 | if (LoopNum(ni.node) == innermost_index) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 346 | ni.next = innermost->header_list; |
| 347 | innermost->header_list = ∋ |
| 348 | } else { |
| 349 | ni.next = innermost->body_list; |
| 350 | innermost->body_list = ∋ |
| 351 | } |
| 352 | count++; |
| 353 | } |
| 354 | |
| 355 | // Serialize the node lists for loops into the loop tree. |
| 356 | loop_tree_->loop_nodes_.reserve(count); |
| 357 | for (LoopTree::Loop* loop : loop_tree_->outer_loops_) { |
| 358 | SerializeLoop(loop); |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | // Handle the simpler case of a single loop (no checks for nesting necessary). |
| 363 | void FinishSingleLoop() { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 364 | // Place nodes into the loop header and body. |
| 365 | LoopInfo* li = &loops_[0]; |
| 366 | li->loop = &loop_tree_->all_loops_[0]; |
| 367 | loop_tree_->SetParent(nullptr, li->loop); |
| 368 | size_t count = 0; |
| 369 | for (NodeInfo& ni : info_) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 370 | if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue; |
| 371 | if (LoopNum(ni.node) == 1) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 372 | ni.next = li->header_list; |
| 373 | li->header_list = ∋ |
| 374 | } else { |
| 375 | ni.next = li->body_list; |
| 376 | li->body_list = ∋ |
| 377 | } |
| 378 | count++; |
| 379 | } |
| 380 | |
| 381 | // Serialize the node lists for the loop into the loop tree. |
| 382 | loop_tree_->loop_nodes_.reserve(count); |
| 383 | SerializeLoop(li->loop); |
| 384 | } |
| 385 | |
| 386 | // Recursively serialize the list of header nodes and body nodes |
| 387 | // so that nested loops occupy nested intervals. |
| 388 | void SerializeLoop(LoopTree::Loop* loop) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 389 | int loop_num = loop_tree_->LoopNum(loop); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 390 | LoopInfo& li = loops_[loop_num - 1]; |
| 391 | |
| 392 | // Serialize the header. |
| 393 | loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| 394 | for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) { |
| 395 | loop_tree_->loop_nodes_.push_back(ni->node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 396 | loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 397 | } |
| 398 | |
| 399 | // Serialize the body. |
| 400 | loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| 401 | for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) { |
| 402 | loop_tree_->loop_nodes_.push_back(ni->node); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 403 | loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 404 | } |
| 405 | |
| 406 | // Serialize nested loops. |
| 407 | for (LoopTree::Loop* child : loop->children_) SerializeLoop(child); |
| 408 | |
| 409 | loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size()); |
| 410 | } |
| 411 | |
| 412 | // Connect the LoopTree loops to their parents recursively. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 413 | LoopTree::Loop* ConnectLoopTree(int loop_num) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 414 | LoopInfo& li = loops_[loop_num - 1]; |
| 415 | if (li.loop != nullptr) return li.loop; |
| 416 | |
| 417 | NodeInfo& ni = info(li.header); |
| 418 | LoopTree::Loop* parent = nullptr; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 419 | for (int i = 1; i <= loops_found_; i++) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 420 | if (i == loop_num) continue; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 421 | if (IsInLoop(ni.node, i)) { |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 422 | // recursively create potential parent loops first. |
| 423 | LoopTree::Loop* upper = ConnectLoopTree(i); |
| 424 | if (parent == nullptr || upper->depth_ > parent->depth_) { |
| 425 | parent = upper; |
| 426 | } |
| 427 | } |
| 428 | } |
| 429 | li.loop = &loop_tree_->all_loops_[loop_num - 1]; |
| 430 | loop_tree_->SetParent(parent, li.loop); |
| 431 | return li.loop; |
| 432 | } |
| 433 | |
| 434 | void PrintLoop(LoopTree::Loop* loop) { |
| 435 | for (int i = 0; i < loop->depth_; i++) PrintF(" "); |
| 436 | PrintF("Loop depth = %d ", loop->depth_); |
| 437 | int i = loop->header_start_; |
| 438 | while (i < loop->body_start_) { |
| 439 | PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id()); |
| 440 | } |
| 441 | while (i < loop->body_end_) { |
| 442 | PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id()); |
| 443 | } |
| 444 | PrintF("\n"); |
| 445 | for (LoopTree::Loop* child : loop->children_) PrintLoop(child); |
| 446 | } |
| 447 | }; |
| 448 | |
| 449 | |
| 450 | LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) { |
| 451 | LoopTree* loop_tree = |
| 452 | new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone()); |
| 453 | LoopFinderImpl finder(graph, loop_tree, zone); |
| 454 | finder.Run(); |
| 455 | if (FLAG_trace_turbo_graph) { |
| 456 | finder.Print(); |
| 457 | } |
| 458 | return loop_tree; |
| 459 | } |
| 460 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 461 | |
| 462 | Node* LoopTree::HeaderNode(Loop* loop) { |
| 463 | Node* first = *HeaderNodes(loop).begin(); |
| 464 | if (first->opcode() == IrOpcode::kLoop) return first; |
| 465 | DCHECK(IrOpcode::IsPhiOpcode(first->opcode())); |
| 466 | Node* header = NodeProperties::GetControlInput(first); |
| 467 | DCHECK_EQ(IrOpcode::kLoop, header->opcode()); |
| 468 | return header; |
| 469 | } |
| 470 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 471 | } // namespace compiler |
| 472 | } // namespace internal |
| 473 | } // namespace v8 |