• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/codegen/tick-counter.h"
8 #include "src/compiler/common-operator.h"
9 #include "src/compiler/graph.h"
10 #include "src/compiler/node-marker.h"
11 #include "src/compiler/node-properties.h"
12 #include "src/compiler/node.h"
13 #include "src/zone/zone.h"
14 
15 #if V8_ENABLE_WEBASSEMBLY
16 #include "src/wasm/wasm-code-manager.h"
17 #endif
18 
19 namespace v8 {
20 namespace internal {
21 
22 class TickCounter;
23 
24 namespace compiler {
25 
26 #define OFFSET(x) ((x)&0x1F)
27 #define BIT(x) (1u << OFFSET(x))
28 #define INDEX(x) ((x) >> 5)
29 
30 // Temporary information for each node during marking.
31 struct NodeInfo {
32   Node* node;
33   NodeInfo* next;  // link in chaining loop members
34   bool backwards_visited;
35 };
36 
37 
38 // Temporary loop info needed during traversal and building the loop tree.
39 struct TempLoopInfo {
40   Node* header;
41   NodeInfo* header_list;
42   NodeInfo* exit_list;
43   NodeInfo* body_list;
44   LoopTree::Loop* loop;
45 };
46 
47 // Encapsulation of the loop finding algorithm.
48 // -----------------------------------------------------------------------------
49 // Conceptually, the contents of a loop are those nodes that are "between" the
50 // loop header and the backedges of the loop. Graphs in the soup of nodes can
51 // form improper cycles, so standard loop finding algorithms that work on CFGs
52 // aren't sufficient. However, in valid TurboFan graphs, all cycles involve
53 // either a {Loop} node or a phi. The {Loop} node itself and its accompanying
54 // phis are treated together as a set referred to here as the loop header.
55 // This loop finding algorithm works by traversing the graph in two directions,
56 // first from nodes to their inputs, starting at {end}, then in the reverse
57 // direction, from nodes to their uses, starting at loop headers.
58 // 1 bit per loop per node per direction are required during the marking phase.
59 // To handle nested loops correctly, the algorithm must filter some reachability
60 // marks on edges into/out-of the loop header nodes.
61 // Note: this algorithm assumes there are no unreachable loop header nodes
62 // (including loop phis).
63 class LoopFinderImpl {
64  public:
LoopFinderImpl(Graph * graph,LoopTree * loop_tree,TickCounter * tick_counter,Zone * zone)65   LoopFinderImpl(Graph* graph, LoopTree* loop_tree, TickCounter* tick_counter,
66                  Zone* zone)
67       : zone_(zone),
68         end_(graph->end()),
69         queue_(zone),
70         queued_(graph, 2),
71         info_(graph->NodeCount(), {nullptr, nullptr, false}, zone),
72         loops_(zone),
73         loop_num_(graph->NodeCount(), -1, zone),
74         loop_tree_(loop_tree),
75         loops_found_(0),
76         width_(0),
77         backward_(nullptr),
78         forward_(nullptr),
79         tick_counter_(tick_counter) {}
80 
Run()81   void Run() {
82     PropagateBackward();
83     PropagateForward();
84     FinishLoopTree();
85   }
86 
Print()87   void Print() {
88     // Print out the results.
89     for (NodeInfo& ni : info_) {
90       if (ni.node == nullptr) continue;
91       for (int i = 1; i <= loops_found_; i++) {
92         int index = ni.node->id() * width_ + INDEX(i);
93         bool marked_forward = forward_[index] & BIT(i);
94         bool marked_backward = backward_[index] & BIT(i);
95         if (marked_forward && marked_backward) {
96           PrintF("X");
97         } else if (marked_forward) {
98           PrintF(">");
99         } else if (marked_backward) {
100           PrintF("<");
101         } else {
102           PrintF(" ");
103         }
104       }
105       PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
106     }
107 
108     int i = 0;
109     for (TempLoopInfo& li : loops_) {
110       PrintF("Loop %d headed at #%d\n", i, li.header->id());
111       i++;
112     }
113 
114     for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
115       PrintLoop(loop);
116     }
117   }
118 
119  private:
120   Zone* zone_;
121   Node* end_;
122   NodeDeque queue_;
123   NodeMarker<bool> queued_;
124   ZoneVector<NodeInfo> info_;
125   ZoneVector<TempLoopInfo> loops_;
126   ZoneVector<int> loop_num_;
127   LoopTree* loop_tree_;
128   int loops_found_;
129   int width_;
130   uint32_t* backward_;
131   uint32_t* forward_;
132   TickCounter* const tick_counter_;
133 
num_nodes()134   int num_nodes() {
135     return static_cast<int>(loop_tree_->node_to_loop_num_.size());
136   }
137 
138   // Tb = Tb | (Fb - loop_filter)
PropagateBackwardMarks(Node * from,Node * to,int loop_filter)139   bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
140     if (from == to) return false;
141     uint32_t* fp = &backward_[from->id() * width_];
142     uint32_t* tp = &backward_[to->id() * width_];
143     bool change = false;
144     for (int i = 0; i < width_; i++) {
145       uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
146       uint32_t prev = tp[i];
147       uint32_t next = prev | (fp[i] & mask);
148       tp[i] = next;
149       if (!change && (prev != next)) change = true;
150     }
151     return change;
152   }
153 
154   // Tb = Tb | B
SetBackwardMark(Node * to,int loop_num)155   bool SetBackwardMark(Node* to, int loop_num) {
156     uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
157     uint32_t prev = tp[0];
158     uint32_t next = prev | BIT(loop_num);
159     tp[0] = next;
160     return next != prev;
161   }
162 
163   // Tf = Tf | B
SetForwardMark(Node * to,int loop_num)164   bool SetForwardMark(Node* to, int loop_num) {
165     uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
166     uint32_t prev = tp[0];
167     uint32_t next = prev | BIT(loop_num);
168     tp[0] = next;
169     return next != prev;
170   }
171 
172   // Tf = Tf | (Ff & Tb)
PropagateForwardMarks(Node * from,Node * to)173   bool PropagateForwardMarks(Node* from, Node* to) {
174     if (from == to) return false;
175     bool change = false;
176     int findex = from->id() * width_;
177     int tindex = to->id() * width_;
178     for (int i = 0; i < width_; i++) {
179       uint32_t marks = backward_[tindex + i] & forward_[findex + i];
180       uint32_t prev = forward_[tindex + i];
181       uint32_t next = prev | marks;
182       forward_[tindex + i] = next;
183       if (!change && (prev != next)) change = true;
184     }
185     return change;
186   }
187 
IsInLoop(Node * node,int loop_num)188   bool IsInLoop(Node* node, int loop_num) {
189     int offset = node->id() * width_ + INDEX(loop_num);
190     return backward_[offset] & forward_[offset] & BIT(loop_num);
191   }
192 
193   // Propagate marks backward from loop headers.
PropagateBackward()194   void PropagateBackward() {
195     ResizeBackwardMarks();
196     SetBackwardMark(end_, 0);
197     Queue(end_);
198 
199     while (!queue_.empty()) {
200       tick_counter_->TickAndMaybeEnterSafepoint();
201       Node* node = queue_.front();
202       info(node).backwards_visited = true;
203       queue_.pop_front();
204       queued_.Set(node, false);
205 
206       int loop_num = -1;
207       // Setup loop headers first.
208       if (node->opcode() == IrOpcode::kLoop) {
209         // found the loop node first.
210         loop_num = CreateLoopInfo(node);
211       } else if (NodeProperties::IsPhi(node)) {
212         // found a phi first.
213         Node* merge = node->InputAt(node->InputCount() - 1);
214         if (merge->opcode() == IrOpcode::kLoop) {
215           loop_num = CreateLoopInfo(merge);
216         }
217       } else if (node->opcode() == IrOpcode::kLoopExit) {
218         // Intentionally ignore return value. Loop exit node marks
219         // are propagated normally.
220         CreateLoopInfo(node->InputAt(1));
221       } else if (node->opcode() == IrOpcode::kLoopExitValue ||
222                  node->opcode() == IrOpcode::kLoopExitEffect) {
223         Node* loop_exit = NodeProperties::GetControlInput(node);
224         // Intentionally ignore return value. Loop exit node marks
225         // are propagated normally.
226         CreateLoopInfo(loop_exit->InputAt(1));
227       }
228 
229       // Propagate marks backwards from this node.
230       for (int i = 0; i < node->InputCount(); i++) {
231         Node* input = node->InputAt(i);
232         if (IsBackedge(node, i)) {
233           // Only propagate the loop mark on backedges.
234           if (SetBackwardMark(input, loop_num) ||
235               !info(input).backwards_visited) {
236             Queue(input);
237           }
238         } else {
239           // Entry or normal edge. Propagate all marks except loop_num.
240           // TODO(manoskouk): Add test that needs backwards_visited to function
241           // correctly, probably using wasm loop unrolling when it is available.
242           if (PropagateBackwardMarks(node, input, loop_num) ||
243               !info(input).backwards_visited) {
244             Queue(input);
245           }
246         }
247       }
248     }
249   }
250 
251   // Make a new loop if necessary for the given node.
CreateLoopInfo(Node * node)252   int CreateLoopInfo(Node* node) {
253     DCHECK_EQ(IrOpcode::kLoop, node->opcode());
254     int loop_num = LoopNum(node);
255     if (loop_num > 0) return loop_num;
256 
257     loop_num = ++loops_found_;
258     if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
259 
260     // Create a new loop.
261     loops_.push_back({node, nullptr, nullptr, nullptr, nullptr});
262     loop_tree_->NewLoop();
263     SetLoopMarkForLoopHeader(node, loop_num);
264     return loop_num;
265   }
266 
SetLoopMark(Node * node,int loop_num)267   void SetLoopMark(Node* node, int loop_num) {
268     info(node);  // create the NodeInfo
269     SetBackwardMark(node, loop_num);
270     loop_tree_->node_to_loop_num_[node->id()] = loop_num;
271   }
272 
SetLoopMarkForLoopHeader(Node * node,int loop_num)273   void SetLoopMarkForLoopHeader(Node* node, int loop_num) {
274     DCHECK_EQ(IrOpcode::kLoop, node->opcode());
275     SetLoopMark(node, loop_num);
276     for (Node* use : node->uses()) {
277       if (NodeProperties::IsPhi(use)) {
278         SetLoopMark(use, loop_num);
279       }
280 
281       // Do not keep the loop alive if it does not have any backedges.
282       if (node->InputCount() <= 1) continue;
283 
284       if (use->opcode() == IrOpcode::kLoopExit) {
285         SetLoopMark(use, loop_num);
286         for (Node* exit_use : use->uses()) {
287           if (exit_use->opcode() == IrOpcode::kLoopExitValue ||
288               exit_use->opcode() == IrOpcode::kLoopExitEffect) {
289             SetLoopMark(exit_use, loop_num);
290           }
291         }
292       }
293     }
294   }
295 
ResizeBackwardMarks()296   void ResizeBackwardMarks() {
297     int new_width = width_ + 1;
298     int max = num_nodes();
299     uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
300     memset(new_backward, 0, new_width * max * sizeof(uint32_t));
301     if (width_ > 0) {  // copy old matrix data.
302       for (int i = 0; i < max; i++) {
303         uint32_t* np = &new_backward[i * new_width];
304         uint32_t* op = &backward_[i * width_];
305         for (int j = 0; j < width_; j++) np[j] = op[j];
306       }
307     }
308     width_ = new_width;
309     backward_ = new_backward;
310   }
311 
ResizeForwardMarks()312   void ResizeForwardMarks() {
313     int max = num_nodes();
314     forward_ = zone_->NewArray<uint32_t>(width_ * max);
315     memset(forward_, 0, width_ * max * sizeof(uint32_t));
316   }
317 
318   // Propagate marks forward from loops.
PropagateForward()319   void PropagateForward() {
320     ResizeForwardMarks();
321     for (TempLoopInfo& li : loops_) {
322       SetForwardMark(li.header, LoopNum(li.header));
323       Queue(li.header);
324     }
325     // Propagate forward on paths that were backward reachable from backedges.
326     while (!queue_.empty()) {
327       tick_counter_->TickAndMaybeEnterSafepoint();
328       Node* node = queue_.front();
329       queue_.pop_front();
330       queued_.Set(node, false);
331       for (Edge edge : node->use_edges()) {
332         Node* use = edge.from();
333         if (!IsBackedge(use, edge.index())) {
334           if (PropagateForwardMarks(node, use)) Queue(use);
335         }
336       }
337     }
338   }
339 
IsLoopHeaderNode(Node * node)340   bool IsLoopHeaderNode(Node* node) {
341     return node->opcode() == IrOpcode::kLoop || NodeProperties::IsPhi(node);
342   }
343 
IsLoopExitNode(Node * node)344   bool IsLoopExitNode(Node* node) {
345     return node->opcode() == IrOpcode::kLoopExit ||
346            node->opcode() == IrOpcode::kLoopExitValue ||
347            node->opcode() == IrOpcode::kLoopExitEffect;
348   }
349 
IsBackedge(Node * use,int index)350   bool IsBackedge(Node* use, int index) {
351     if (LoopNum(use) <= 0) return false;
352     if (NodeProperties::IsPhi(use)) {
353       return index != NodeProperties::FirstControlIndex(use) &&
354              index != kAssumedLoopEntryIndex;
355     } else if (use->opcode() == IrOpcode::kLoop) {
356       return index != kAssumedLoopEntryIndex;
357     }
358     DCHECK(IsLoopExitNode(use));
359     return false;
360   }
361 
LoopNum(Node * node)362   int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
363 
info(Node * node)364   NodeInfo& info(Node* node) {
365     NodeInfo& i = info_[node->id()];
366     if (i.node == nullptr) i.node = node;
367     return i;
368   }
369 
Queue(Node * node)370   void Queue(Node* node) {
371     if (!queued_.Get(node)) {
372       queue_.push_back(node);
373       queued_.Set(node, true);
374     }
375   }
376 
AddNodeToLoop(NodeInfo * node_info,TempLoopInfo * loop,int loop_num)377   void AddNodeToLoop(NodeInfo* node_info, TempLoopInfo* loop, int loop_num) {
378     if (LoopNum(node_info->node) == loop_num) {
379       if (IsLoopHeaderNode(node_info->node)) {
380         node_info->next = loop->header_list;
381         loop->header_list = node_info;
382       } else {
383         DCHECK(IsLoopExitNode(node_info->node));
384         node_info->next = loop->exit_list;
385         loop->exit_list = node_info;
386       }
387     } else {
388       node_info->next = loop->body_list;
389       loop->body_list = node_info;
390     }
391   }
392 
FinishLoopTree()393   void FinishLoopTree() {
394     DCHECK(loops_found_ == static_cast<int>(loops_.size()));
395     DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));
396 
397     // Degenerate cases.
398     if (loops_found_ == 0) return;
399     if (loops_found_ == 1) return FinishSingleLoop();
400 
401     for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i);
402 
403     size_t count = 0;
404     // Place the node into the innermost nested loop of which it is a member.
405     for (NodeInfo& ni : info_) {
406       if (ni.node == nullptr) continue;
407 
408       TempLoopInfo* innermost = nullptr;
409       int innermost_index = 0;
410       int pos = ni.node->id() * width_;
411       // Search the marks word by word.
412       for (int i = 0; i < width_; i++) {
413         uint32_t marks = backward_[pos + i] & forward_[pos + i];
414 
415         for (int j = 0; j < 32; j++) {
416           if (marks & (1u << j)) {
417             int loop_num = i * 32 + j;
418             if (loop_num == 0) continue;
419             TempLoopInfo* loop = &loops_[loop_num - 1];
420             if (innermost == nullptr ||
421                 loop->loop->depth_ > innermost->loop->depth_) {
422               innermost = loop;
423               innermost_index = loop_num;
424             }
425           }
426         }
427       }
428       if (innermost == nullptr) continue;
429 
430       // Return statements should never be found by forward or backward walk.
431       CHECK(ni.node->opcode() != IrOpcode::kReturn);
432 
433       AddNodeToLoop(&ni, innermost, innermost_index);
434       count++;
435     }
436 
437     // Serialize the node lists for loops into the loop tree.
438     loop_tree_->loop_nodes_.reserve(count);
439     for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
440       SerializeLoop(loop);
441     }
442   }
443 
444   // Handle the simpler case of a single loop (no checks for nesting necessary).
FinishSingleLoop()445   void FinishSingleLoop() {
446     // Place nodes into the loop header and body.
447     TempLoopInfo* li = &loops_[0];
448     li->loop = &loop_tree_->all_loops_[0];
449     loop_tree_->SetParent(nullptr, li->loop);
450     size_t count = 0;
451     for (NodeInfo& ni : info_) {
452       if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
453 
454       // Return statements should never be found by forward or backward walk.
455       CHECK(ni.node->opcode() != IrOpcode::kReturn);
456 
457       AddNodeToLoop(&ni, li, 1);
458       count++;
459     }
460 
461     // Serialize the node lists for the loop into the loop tree.
462     loop_tree_->loop_nodes_.reserve(count);
463     SerializeLoop(li->loop);
464   }
465 
466   // Recursively serialize the list of header nodes and body nodes
467   // so that nested loops occupy nested intervals.
SerializeLoop(LoopTree::Loop * loop)468   void SerializeLoop(LoopTree::Loop* loop) {
469     int loop_num = loop_tree_->LoopNum(loop);
470     TempLoopInfo& li = loops_[loop_num - 1];
471 
472     // Serialize the header.
473     loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
474     for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
475       loop_tree_->loop_nodes_.push_back(ni->node);
476       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
477     }
478 
479     // Serialize the body.
480     loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
481     for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
482       loop_tree_->loop_nodes_.push_back(ni->node);
483       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
484     }
485 
486     // Serialize nested loops.
487     for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
488 
489     // Serialize the exits.
490     loop->exits_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
491     for (NodeInfo* ni = li.exit_list; ni != nullptr; ni = ni->next) {
492       loop_tree_->loop_nodes_.push_back(ni->node);
493       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
494     }
495 
496     loop->exits_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
497   }
498 
499   // Connect the LoopTree loops to their parents recursively.
ConnectLoopTree(int loop_num)500   LoopTree::Loop* ConnectLoopTree(int loop_num) {
501     TempLoopInfo& li = loops_[loop_num - 1];
502     if (li.loop != nullptr) return li.loop;
503 
504     NodeInfo& ni = info(li.header);
505     LoopTree::Loop* parent = nullptr;
506     for (int i = 1; i <= loops_found_; i++) {
507       if (i == loop_num) continue;
508       if (IsInLoop(ni.node, i)) {
509         // recursively create potential parent loops first.
510         LoopTree::Loop* upper = ConnectLoopTree(i);
511         if (parent == nullptr || upper->depth_ > parent->depth_) {
512           parent = upper;
513         }
514       }
515     }
516     li.loop = &loop_tree_->all_loops_[loop_num - 1];
517     loop_tree_->SetParent(parent, li.loop);
518     return li.loop;
519   }
520 
PrintLoop(LoopTree::Loop * loop)521   void PrintLoop(LoopTree::Loop* loop) {
522     for (int i = 0; i < loop->depth_; i++) PrintF("  ");
523     PrintF("Loop depth = %d ", loop->depth_);
524     int i = loop->header_start_;
525     while (i < loop->body_start_) {
526       PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
527     }
528     while (i < loop->exits_start_) {
529       PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
530     }
531     while (i < loop->exits_end_) {
532       PrintF(" E#%d", loop_tree_->loop_nodes_[i++]->id());
533     }
534     PrintF("\n");
535     for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
536   }
537 };
538 
BuildLoopTree(Graph * graph,TickCounter * tick_counter,Zone * zone)539 LoopTree* LoopFinder::BuildLoopTree(Graph* graph, TickCounter* tick_counter,
540                                     Zone* zone) {
541   LoopTree* loop_tree =
542       graph->zone()->New<LoopTree>(graph->NodeCount(), graph->zone());
543   LoopFinderImpl finder(graph, loop_tree, tick_counter, zone);
544   finder.Run();
545   if (FLAG_trace_turbo_loop) {
546     finder.Print();
547   }
548   return loop_tree;
549 }
550 
551 #if V8_ENABLE_WEBASSEMBLY
552 // static
FindSmallInnermostLoopFromHeader(Node * loop_header,Zone * zone,size_t max_size,bool calls_are_large)553 ZoneUnorderedSet<Node*>* LoopFinder::FindSmallInnermostLoopFromHeader(
554     Node* loop_header, Zone* zone, size_t max_size, bool calls_are_large) {
555   auto* visited = zone->New<ZoneUnorderedSet<Node*>>(zone);
556   std::vector<Node*> queue;
557 
558   DCHECK_EQ(loop_header->opcode(), IrOpcode::kLoop);
559 
560   queue.push_back(loop_header);
561 
562 #define ENQUEUE_USES(use_name, condition)                                      \
563   for (Node * use_name : node->uses()) {                                       \
564     if (condition && visited->count(use_name) == 0) queue.push_back(use_name); \
565   }
566 
567   while (!queue.empty()) {
568     Node* node = queue.back();
569     queue.pop_back();
570     if (node->opcode() == IrOpcode::kEnd) {
571       // We reached the end of the graph. The end node is not part of the loop.
572       continue;
573     }
574     visited->insert(node);
575     if (visited->size() > max_size) return nullptr;
576     switch (node->opcode()) {
577       case IrOpcode::kLoop:
578         // Found nested loop.
579         if (node != loop_header) return nullptr;
580         ENQUEUE_USES(use, true);
581         break;
582       case IrOpcode::kLoopExit:
583         // Found nested loop.
584         if (node->InputAt(1) != loop_header) return nullptr;
585         // LoopExitValue/Effect uses are inside the loop. The rest are not.
586         ENQUEUE_USES(use, (use->opcode() == IrOpcode::kLoopExitEffect ||
587                            use->opcode() == IrOpcode::kLoopExitValue))
588         break;
589       case IrOpcode::kLoopExitEffect:
590       case IrOpcode::kLoopExitValue:
591         if (NodeProperties::GetControlInput(node)->InputAt(1) != loop_header) {
592           // Found nested loop.
593           return nullptr;
594         }
595         // All uses are outside the loop, do nothing.
596         break;
597       // If {calls_are_large}, call nodes are considered to have unbounded size,
598       // i.e. >max_size, with the exception of certain wasm builtins.
599       case IrOpcode::kTailCall:
600       case IrOpcode::kJSWasmCall:
601       case IrOpcode::kJSCall:
602         if (calls_are_large) return nullptr;
603         ENQUEUE_USES(use, true)
604         break;
605       case IrOpcode::kCall: {
606         if (!calls_are_large) {
607           ENQUEUE_USES(use, true);
608           break;
609         }
610         Node* callee = node->InputAt(0);
611         if (callee->opcode() != IrOpcode::kRelocatableInt32Constant &&
612             callee->opcode() != IrOpcode::kRelocatableInt64Constant) {
613           return nullptr;
614         }
615         intptr_t info =
616             OpParameter<RelocatablePtrConstantInfo>(callee->op()).value();
617         using WasmCode = v8::internal::wasm::WasmCode;
618         constexpr intptr_t unrollable_builtins[] = {
619             // Exists in every stack check.
620             WasmCode::kWasmStackGuard,
621             // Fast table operations.
622             WasmCode::kWasmTableGet, WasmCode::kWasmTableSet,
623             WasmCode::kWasmTableGrow,
624             // Atomics.
625             WasmCode::kWasmAtomicNotify, WasmCode::kWasmI32AtomicWait32,
626             WasmCode::kWasmI32AtomicWait64, WasmCode::kWasmI64AtomicWait32,
627             WasmCode::kWasmI64AtomicWait64,
628             // Exceptions.
629             WasmCode::kWasmAllocateFixedArray, WasmCode::kWasmThrow,
630             WasmCode::kWasmRethrow, WasmCode::kWasmRethrowExplicitContext,
631             // Fast wasm-gc operations.
632             WasmCode::kWasmRefFunc};
633         if (std::count(unrollable_builtins,
634                        unrollable_builtins + arraysize(unrollable_builtins),
635                        info) == 0) {
636           return nullptr;
637         }
638         ENQUEUE_USES(use, true)
639         break;
640       }
641       default:
642         ENQUEUE_USES(use, true)
643         break;
644     }
645   }
646 
647   // Check that there is no floating control other than direct nodes to start().
648   // We do this by checking that all non-start control inputs of loop nodes are
649   // also in the loop.
650   // TODO(manoskouk): This is a safety check. Consider making it DEBUG-only when
651   // we are confident there is no incompatible floating control generated in
652   // wasm.
653   for (Node* node : *visited) {
654     // The loop header is allowed to point outside the loop.
655     if (node == loop_header) continue;
656 
657     for (Edge edge : node->input_edges()) {
658       Node* input = edge.to();
659       if (NodeProperties::IsControlEdge(edge) && visited->count(input) == 0 &&
660           input->opcode() != IrOpcode::kStart) {
661         FATAL(
662             "Floating control detected in wasm turbofan graph: Node #%d:%s is "
663             "inside loop headed by #%d, but its control dependency #%d:%s is "
664             "outside",
665             node->id(), node->op()->mnemonic(), loop_header->id(), input->id(),
666             input->op()->mnemonic());
667       }
668     }
669   }
670 
671   return visited;
672 }
673 #endif  // V8_ENABLE_WEBASSEMBLY
674 
HasMarkedExits(LoopTree * loop_tree,const LoopTree::Loop * loop)675 bool LoopFinder::HasMarkedExits(LoopTree* loop_tree,
676                                 const LoopTree::Loop* loop) {
677   // Look for returns and if projections that are outside the loop but whose
678   // control input is inside the loop.
679   Node* loop_node = loop_tree->GetLoopControl(loop);
680   for (Node* node : loop_tree->LoopNodes(loop)) {
681     for (Node* use : node->uses()) {
682       if (!loop_tree->Contains(loop, use)) {
683         bool unmarked_exit;
684         switch (node->opcode()) {
685           case IrOpcode::kLoopExit:
686             unmarked_exit = (node->InputAt(1) != loop_node);
687             break;
688           case IrOpcode::kLoopExitValue:
689           case IrOpcode::kLoopExitEffect:
690             unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node);
691             break;
692           default:
693             unmarked_exit = (use->opcode() != IrOpcode::kTerminate);
694         }
695         if (unmarked_exit) {
696           if (FLAG_trace_turbo_loop) {
697             PrintF(
698                 "Cannot peel loop %i. Loop exit without explicit mark: Node %i "
699                 "(%s) is inside loop, but its use %i (%s) is outside.\n",
700                 loop_node->id(), node->id(), node->op()->mnemonic(), use->id(),
701                 use->op()->mnemonic());
702           }
703           return false;
704         }
705       }
706     }
707   }
708   return true;
709 }
710 
HeaderNode(const Loop * loop)711 Node* LoopTree::HeaderNode(const Loop* loop) {
712   Node* first = *HeaderNodes(loop).begin();
713   if (first->opcode() == IrOpcode::kLoop) return first;
714   DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
715   Node* header = NodeProperties::GetControlInput(first);
716   DCHECK_EQ(IrOpcode::kLoop, header->opcode());
717   return header;
718 }
719 
map(Node * node,uint32_t copy_index)720 Node* NodeCopier::map(Node* node, uint32_t copy_index) {
721   DCHECK_LT(copy_index, copy_count_);
722   if (node_map_.Get(node) == 0) return node;
723   return copies_->at(node_map_.Get(node) + copy_index);
724 }
725 
Insert(Node * original,const NodeVector & new_copies)726 void NodeCopier::Insert(Node* original, const NodeVector& new_copies) {
727   DCHECK_EQ(new_copies.size(), copy_count_);
728   node_map_.Set(original, copies_->size() + 1);
729   copies_->push_back(original);
730   copies_->insert(copies_->end(), new_copies.begin(), new_copies.end());
731 }
732 
Insert(Node * original,Node * copy)733 void NodeCopier::Insert(Node* original, Node* copy) {
734   DCHECK_EQ(copy_count_, 1);
735   node_map_.Set(original, copies_->size() + 1);
736   copies_->push_back(original);
737   copies_->push_back(copy);
738 }
739 
740 }  // namespace compiler
741 }  // namespace internal
742 }  // namespace v8
743