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