V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
scheduler.cc
1 // Copyright 2013 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/scheduler.h"
6 
7 #include <iomanip>
8 
9 #include "src/base/adapters.h"
10 #include "src/bit-vector.h"
11 #include "src/compiler/common-operator.h"
12 #include "src/compiler/control-equivalence.h"
13 #include "src/compiler/graph.h"
14 #include "src/compiler/node-marker.h"
15 #include "src/compiler/node-properties.h"
16 #include "src/compiler/node.h"
17 #include "src/zone/zone-containers.h"
18 
19 namespace v8 {
20 namespace internal {
21 namespace compiler {
22 
23 #define TRACE(...) \
24  do { \
25  if (FLAG_trace_turbo_scheduler) PrintF(__VA_ARGS__); \
26  } while (false)
27 
28 Scheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
29  size_t node_count_hint)
30  : zone_(zone),
31  graph_(graph),
32  schedule_(schedule),
33  flags_(flags),
34  scheduled_nodes_(zone),
35  schedule_root_nodes_(zone),
36  schedule_queue_(zone),
37  node_data_(zone) {
38  node_data_.reserve(node_count_hint);
39  node_data_.resize(graph->NodeCount(), DefaultSchedulerData());
40 }
41 
42 Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags) {
43  Zone* schedule_zone =
44  (flags & Scheduler::kTempSchedule) ? zone : graph->zone();
45 
46  // Reserve 10% more space for nodes if node splitting is enabled to try to
47  // avoid resizing the vector since that would triple its zone memory usage.
48  float node_hint_multiplier = (flags & Scheduler::kSplitNodes) ? 1.1 : 1;
49  size_t node_count_hint = node_hint_multiplier * graph->NodeCount();
50 
51  Schedule* schedule =
52  new (schedule_zone) Schedule(schedule_zone, node_count_hint);
53  Scheduler scheduler(zone, graph, schedule, flags, node_count_hint);
54 
55  scheduler.BuildCFG();
56  scheduler.ComputeSpecialRPONumbering();
57  scheduler.GenerateImmediateDominatorTree();
58 
59  scheduler.PrepareUses();
60  scheduler.ScheduleEarly();
61  scheduler.ScheduleLate();
62 
63  scheduler.SealFinalSchedule();
64 
65  return schedule;
66 }
67 
68 
69 Scheduler::SchedulerData Scheduler::DefaultSchedulerData() {
70  SchedulerData def = {schedule_->start(), 0, kUnknown};
71  return def;
72 }
73 
74 
75 Scheduler::SchedulerData* Scheduler::GetData(Node* node) {
76  return &node_data_[node->id()];
77 }
78 
79 Scheduler::Placement Scheduler::InitializePlacement(Node* node) {
80  SchedulerData* data = GetData(node);
81  if (data->placement_ == kFixed) {
82  // Nothing to do for control nodes that have been already fixed in
83  // the schedule.
84  return data->placement_;
85  }
86  DCHECK_EQ(kUnknown, data->placement_);
87  switch (node->opcode()) {
88  case IrOpcode::kParameter:
89  case IrOpcode::kOsrValue:
90  // Parameters and OSR values are always fixed to the start block.
91  data->placement_ = kFixed;
92  break;
93  case IrOpcode::kPhi:
94  case IrOpcode::kEffectPhi: {
95  // Phis and effect phis are fixed if their control inputs are, whereas
96  // otherwise they are coupled to a floating control node.
97  Placement p = GetPlacement(NodeProperties::GetControlInput(node));
98  data->placement_ = (p == kFixed ? kFixed : kCoupled);
99  break;
100  }
101 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
102  CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
103 #undef DEFINE_CONTROL_CASE
104  {
105  // Control nodes that were not control-reachable from end may float.
106  data->placement_ = kSchedulable;
107  break;
108  }
109  default:
110  data->placement_ = kSchedulable;
111  break;
112  }
113  return data->placement_;
114 }
115 
116 Scheduler::Placement Scheduler::GetPlacement(Node* node) {
117  return GetData(node)->placement_;
118 }
119 
120 bool Scheduler::IsLive(Node* node) { return GetPlacement(node) != kUnknown; }
121 
122 void Scheduler::UpdatePlacement(Node* node, Placement placement) {
123  SchedulerData* data = GetData(node);
124  if (data->placement_ == kUnknown) {
125  // We only update control nodes from {kUnknown} to {kFixed}. Ideally, we
126  // should check that {node} is a control node (including exceptional calls),
127  // but that is expensive.
128  DCHECK_EQ(Scheduler::kFixed, placement);
129  data->placement_ = placement;
130  return;
131  }
132 
133  switch (node->opcode()) {
134  case IrOpcode::kParameter:
135  // Parameters are fixed once and for all.
136  UNREACHABLE();
137  break;
138  case IrOpcode::kPhi:
139  case IrOpcode::kEffectPhi: {
140  // Phis and effect phis are coupled to their respective blocks.
141  DCHECK_EQ(Scheduler::kCoupled, data->placement_);
142  DCHECK_EQ(Scheduler::kFixed, placement);
143  Node* control = NodeProperties::GetControlInput(node);
144  BasicBlock* block = schedule_->block(control);
145  schedule_->AddNode(block, node);
146  break;
147  }
148 #define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
149  CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
150 #undef DEFINE_CONTROL_CASE
151  {
152  // Control nodes force coupled uses to be placed.
153  for (auto use : node->uses()) {
154  if (GetPlacement(use) == Scheduler::kCoupled) {
155  DCHECK_EQ(node, NodeProperties::GetControlInput(use));
156  UpdatePlacement(use, placement);
157  }
158  }
159  break;
160  }
161  default:
162  DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
163  DCHECK_EQ(Scheduler::kScheduled, placement);
164  break;
165  }
166  // Reduce the use count of the node's inputs to potentially make them
167  // schedulable. If all the uses of a node have been scheduled, then the node
168  // itself can be scheduled.
169  for (Edge const edge : node->input_edges()) {
170  DecrementUnscheduledUseCount(edge.to(), edge.index(), edge.from());
171  }
172  data->placement_ = placement;
173 }
174 
175 
176 bool Scheduler::IsCoupledControlEdge(Node* node, int index) {
177  return GetPlacement(node) == kCoupled &&
178  NodeProperties::FirstControlIndex(node) == index;
179 }
180 
181 
182 void Scheduler::IncrementUnscheduledUseCount(Node* node, int index,
183  Node* from) {
184  // Make sure that control edges from coupled nodes are not counted.
185  if (IsCoupledControlEdge(from, index)) return;
186 
187  // Tracking use counts for fixed nodes is useless.
188  if (GetPlacement(node) == kFixed) return;
189 
190  // Use count for coupled nodes is summed up on their control.
191  if (GetPlacement(node) == kCoupled) {
192  Node* control = NodeProperties::GetControlInput(node);
193  return IncrementUnscheduledUseCount(control, index, from);
194  }
195 
196  ++(GetData(node)->unscheduled_count_);
197  if (FLAG_trace_turbo_scheduler) {
198  TRACE(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
199  node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
200  GetData(node)->unscheduled_count_);
201  }
202 }
203 
204 
205 void Scheduler::DecrementUnscheduledUseCount(Node* node, int index,
206  Node* from) {
207  // Make sure that control edges from coupled nodes are not counted.
208  if (IsCoupledControlEdge(from, index)) return;
209 
210  // Tracking use counts for fixed nodes is useless.
211  if (GetPlacement(node) == kFixed) return;
212 
213  // Use count for coupled nodes is summed up on their control.
214  if (GetPlacement(node) == kCoupled) {
215  Node* control = NodeProperties::GetControlInput(node);
216  return DecrementUnscheduledUseCount(control, index, from);
217  }
218 
219  DCHECK_LT(0, GetData(node)->unscheduled_count_);
220  --(GetData(node)->unscheduled_count_);
221  if (FLAG_trace_turbo_scheduler) {
222  TRACE(" Use count of #%d:%s (used by #%d:%s)-- = %d\n", node->id(),
223  node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
224  GetData(node)->unscheduled_count_);
225  }
226  if (GetData(node)->unscheduled_count_ == 0) {
227  TRACE(" newly eligible #%d:%s\n", node->id(), node->op()->mnemonic());
228  schedule_queue_.push(node);
229  }
230 }
231 
232 
233 // -----------------------------------------------------------------------------
234 // Phase 1: Build control-flow graph.
235 
236 
237 // Internal class to build a control flow graph (i.e the basic blocks and edges
238 // between them within a Schedule) from the node graph. Visits control edges of
239 // the graph backwards from an end node in order to find the connected control
240 // subgraph, needed for scheduling.
241 class CFGBuilder : public ZoneObject {
242  public:
243  CFGBuilder(Zone* zone, Scheduler* scheduler)
244  : zone_(zone),
245  scheduler_(scheduler),
246  schedule_(scheduler->schedule_),
247  queued_(scheduler->graph_, 2),
248  queue_(zone),
249  control_(zone),
250  component_entry_(nullptr),
251  component_start_(nullptr),
252  component_end_(nullptr) {}
253 
254  // Run the control flow graph construction algorithm by walking the graph
255  // backwards from end through control edges, building and connecting the
256  // basic blocks for control nodes.
257  void Run() {
258  ResetDataStructures();
259  Queue(scheduler_->graph_->end());
260 
261  while (!queue_.empty()) { // Breadth-first backwards traversal.
262  Node* node = queue_.front();
263  queue_.pop();
264  int max = NodeProperties::PastControlIndex(node);
265  for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
266  Queue(node->InputAt(i));
267  }
268  }
269 
270  for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
271  ConnectBlocks(*i); // Connect block to its predecessor/successors.
272  }
273  }
274 
275  // Run the control flow graph construction for a minimal control-connected
276  // component ending in {exit} and merge that component into an existing
277  // control flow graph at the bottom of {block}.
278  void Run(BasicBlock* block, Node* exit) {
279  ResetDataStructures();
280  Queue(exit);
281 
282  component_entry_ = nullptr;
283  component_start_ = block;
284  component_end_ = schedule_->block(exit);
285  scheduler_->equivalence_->Run(exit);
286  while (!queue_.empty()) { // Breadth-first backwards traversal.
287  Node* node = queue_.front();
288  queue_.pop();
289 
290  // Use control dependence equivalence to find a canonical single-entry
291  // single-exit region that makes up a minimal component to be scheduled.
292  if (IsSingleEntrySingleExitRegion(node, exit)) {
293  TRACE("Found SESE at #%d:%s\n", node->id(), node->op()->mnemonic());
294  DCHECK(!component_entry_);
295  component_entry_ = node;
296  continue;
297  }
298 
299  int max = NodeProperties::PastControlIndex(node);
300  for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
301  Queue(node->InputAt(i));
302  }
303  }
304  DCHECK(component_entry_);
305 
306  for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
307  ConnectBlocks(*i); // Connect block to its predecessor/successors.
308  }
309  }
310 
311  private:
312  friend class ScheduleLateNodeVisitor;
313  friend class Scheduler;
314 
315  void FixNode(BasicBlock* block, Node* node) {
316  schedule_->AddNode(block, node);
317  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
318  }
319 
320  void Queue(Node* node) {
321  // Mark the connected control nodes as they are queued.
322  if (!queued_.Get(node)) {
323  BuildBlocks(node);
324  queue_.push(node);
325  queued_.Set(node, true);
326  control_.push_back(node);
327  }
328  }
329 
330  void BuildBlocks(Node* node) {
331  switch (node->opcode()) {
332  case IrOpcode::kEnd:
333  FixNode(schedule_->end(), node);
334  break;
335  case IrOpcode::kStart:
336  FixNode(schedule_->start(), node);
337  break;
338  case IrOpcode::kLoop:
339  case IrOpcode::kMerge:
340  BuildBlockForNode(node);
341  break;
342  case IrOpcode::kTerminate: {
343  // Put Terminate in the loop to which it refers.
344  Node* loop = NodeProperties::GetControlInput(node);
345  BasicBlock* block = BuildBlockForNode(loop);
346  FixNode(block, node);
347  break;
348  }
349  case IrOpcode::kBranch:
350  case IrOpcode::kSwitch:
351  BuildBlocksForSuccessors(node);
352  break;
353 #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
354  JS_OP_LIST(BUILD_BLOCK_JS_CASE)
355 // JS opcodes are just like calls => fall through.
356 #undef BUILD_BLOCK_JS_CASE
357  case IrOpcode::kCall:
358  case IrOpcode::kCallWithCallerSavedRegisters:
359  if (NodeProperties::IsExceptionalCall(node)) {
360  BuildBlocksForSuccessors(node);
361  }
362  break;
363  default:
364  break;
365  }
366  }
367 
368  void ConnectBlocks(Node* node) {
369  switch (node->opcode()) {
370  case IrOpcode::kLoop:
371  case IrOpcode::kMerge:
372  ConnectMerge(node);
373  break;
374  case IrOpcode::kBranch:
375  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
376  ConnectBranch(node);
377  break;
378  case IrOpcode::kSwitch:
379  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
380  ConnectSwitch(node);
381  break;
382  case IrOpcode::kDeoptimize:
383  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
384  ConnectDeoptimize(node);
385  break;
386  case IrOpcode::kTailCall:
387  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
388  ConnectTailCall(node);
389  break;
390  case IrOpcode::kReturn:
391  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
392  ConnectReturn(node);
393  break;
394  case IrOpcode::kThrow:
395  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
396  ConnectThrow(node);
397  break;
398 #define CONNECT_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
399  JS_OP_LIST(CONNECT_BLOCK_JS_CASE)
400 // JS opcodes are just like calls => fall through.
401 #undef CONNECT_BLOCK_JS_CASE
402  case IrOpcode::kCall:
403  case IrOpcode::kCallWithCallerSavedRegisters:
404  if (NodeProperties::IsExceptionalCall(node)) {
405  scheduler_->UpdatePlacement(node, Scheduler::kFixed);
406  ConnectCall(node);
407  }
408  break;
409  default:
410  break;
411  }
412  }
413 
414  BasicBlock* BuildBlockForNode(Node* node) {
415  BasicBlock* block = schedule_->block(node);
416  if (block == nullptr) {
417  block = schedule_->NewBasicBlock();
418  TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
419  node->op()->mnemonic());
420  FixNode(block, node);
421  }
422  return block;
423  }
424 
425  void BuildBlocksForSuccessors(Node* node) {
426  size_t const successor_cnt = node->op()->ControlOutputCount();
427  Node** successors = zone_->NewArray<Node*>(successor_cnt);
428  NodeProperties::CollectControlProjections(node, successors, successor_cnt);
429  for (size_t index = 0; index < successor_cnt; ++index) {
430  BuildBlockForNode(successors[index]);
431  }
432  }
433 
434  void CollectSuccessorBlocks(Node* node, BasicBlock** successor_blocks,
435  size_t successor_cnt) {
436  Node** successors = reinterpret_cast<Node**>(successor_blocks);
437  NodeProperties::CollectControlProjections(node, successors, successor_cnt);
438  for (size_t index = 0; index < successor_cnt; ++index) {
439  successor_blocks[index] = schedule_->block(successors[index]);
440  }
441  }
442 
443  BasicBlock* FindPredecessorBlock(Node* node) {
444  BasicBlock* predecessor_block = nullptr;
445  while (true) {
446  predecessor_block = schedule_->block(node);
447  if (predecessor_block != nullptr) break;
448  node = NodeProperties::GetControlInput(node);
449  }
450  return predecessor_block;
451  }
452 
453  void ConnectCall(Node* call) {
454  BasicBlock* successor_blocks[2];
455  CollectSuccessorBlocks(call, successor_blocks, arraysize(successor_blocks));
456 
457  // Consider the exception continuation to be deferred.
458  successor_blocks[1]->set_deferred(true);
459 
460  Node* call_control = NodeProperties::GetControlInput(call);
461  BasicBlock* call_block = FindPredecessorBlock(call_control);
462  TraceConnect(call, call_block, successor_blocks[0]);
463  TraceConnect(call, call_block, successor_blocks[1]);
464  schedule_->AddCall(call_block, call, successor_blocks[0],
465  successor_blocks[1]);
466  }
467 
468  void ConnectBranch(Node* branch) {
469  BasicBlock* successor_blocks[2];
470  CollectSuccessorBlocks(branch, successor_blocks,
471  arraysize(successor_blocks));
472 
473  // Consider branch hints.
474  switch (BranchHintOf(branch->op())) {
475  case BranchHint::kNone:
476  break;
477  case BranchHint::kTrue:
478  successor_blocks[1]->set_deferred(true);
479  break;
480  case BranchHint::kFalse:
481  successor_blocks[0]->set_deferred(true);
482  break;
483  }
484 
485  if (branch == component_entry_) {
486  TraceConnect(branch, component_start_, successor_blocks[0]);
487  TraceConnect(branch, component_start_, successor_blocks[1]);
488  schedule_->InsertBranch(component_start_, component_end_, branch,
489  successor_blocks[0], successor_blocks[1]);
490  } else {
491  Node* branch_control = NodeProperties::GetControlInput(branch);
492  BasicBlock* branch_block = FindPredecessorBlock(branch_control);
493  TraceConnect(branch, branch_block, successor_blocks[0]);
494  TraceConnect(branch, branch_block, successor_blocks[1]);
495  schedule_->AddBranch(branch_block, branch, successor_blocks[0],
496  successor_blocks[1]);
497  }
498  }
499 
500  void ConnectSwitch(Node* sw) {
501  size_t const successor_count = sw->op()->ControlOutputCount();
502  BasicBlock** successor_blocks =
503  zone_->NewArray<BasicBlock*>(successor_count);
504  CollectSuccessorBlocks(sw, successor_blocks, successor_count);
505 
506  if (sw == component_entry_) {
507  for (size_t index = 0; index < successor_count; ++index) {
508  TraceConnect(sw, component_start_, successor_blocks[index]);
509  }
510  schedule_->InsertSwitch(component_start_, component_end_, sw,
511  successor_blocks, successor_count);
512  } else {
513  Node* switch_control = NodeProperties::GetControlInput(sw);
514  BasicBlock* switch_block = FindPredecessorBlock(switch_control);
515  for (size_t index = 0; index < successor_count; ++index) {
516  TraceConnect(sw, switch_block, successor_blocks[index]);
517  }
518  schedule_->AddSwitch(switch_block, sw, successor_blocks, successor_count);
519  }
520  }
521 
522  void ConnectMerge(Node* merge) {
523  // Don't connect the special merge at the end to its predecessors.
524  if (IsFinalMerge(merge)) return;
525 
526  BasicBlock* block = schedule_->block(merge);
527  DCHECK_NOT_NULL(block);
528  // For all of the merge's control inputs, add a goto at the end to the
529  // merge's basic block.
530  for (Node* const input : merge->inputs()) {
531  BasicBlock* predecessor_block = FindPredecessorBlock(input);
532  TraceConnect(merge, predecessor_block, block);
533  schedule_->AddGoto(predecessor_block, block);
534  }
535  }
536 
537  void ConnectTailCall(Node* call) {
538  Node* call_control = NodeProperties::GetControlInput(call);
539  BasicBlock* call_block = FindPredecessorBlock(call_control);
540  TraceConnect(call, call_block, nullptr);
541  schedule_->AddTailCall(call_block, call);
542  }
543 
544  void ConnectReturn(Node* ret) {
545  Node* return_control = NodeProperties::GetControlInput(ret);
546  BasicBlock* return_block = FindPredecessorBlock(return_control);
547  TraceConnect(ret, return_block, nullptr);
548  schedule_->AddReturn(return_block, ret);
549  }
550 
551  void ConnectDeoptimize(Node* deopt) {
552  Node* deoptimize_control = NodeProperties::GetControlInput(deopt);
553  BasicBlock* deoptimize_block = FindPredecessorBlock(deoptimize_control);
554  TraceConnect(deopt, deoptimize_block, nullptr);
555  schedule_->AddDeoptimize(deoptimize_block, deopt);
556  }
557 
558  void ConnectThrow(Node* thr) {
559  Node* throw_control = NodeProperties::GetControlInput(thr);
560  BasicBlock* throw_block = FindPredecessorBlock(throw_control);
561  TraceConnect(thr, throw_block, nullptr);
562  schedule_->AddThrow(throw_block, thr);
563  }
564 
565  void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
566  DCHECK_NOT_NULL(block);
567  if (succ == nullptr) {
568  TRACE("Connect #%d:%s, id:%d -> end\n", node->id(),
569  node->op()->mnemonic(), block->id().ToInt());
570  } else {
571  TRACE("Connect #%d:%s, id:%d -> id:%d\n", node->id(),
572  node->op()->mnemonic(), block->id().ToInt(), succ->id().ToInt());
573  }
574  }
575 
576  bool IsFinalMerge(Node* node) {
577  return (node->opcode() == IrOpcode::kMerge &&
578  node == scheduler_->graph_->end()->InputAt(0));
579  }
580 
581  bool IsSingleEntrySingleExitRegion(Node* entry, Node* exit) const {
582  size_t entry_class = scheduler_->equivalence_->ClassOf(entry);
583  size_t exit_class = scheduler_->equivalence_->ClassOf(exit);
584  return entry != exit && entry_class == exit_class;
585  }
586 
587  void ResetDataStructures() {
588  control_.clear();
589  DCHECK(queue_.empty());
590  DCHECK(control_.empty());
591  }
592 
593  Zone* zone_;
594  Scheduler* scheduler_;
595  Schedule* schedule_;
596  NodeMarker<bool> queued_; // Mark indicating whether node is queued.
597  ZoneQueue<Node*> queue_; // Queue used for breadth-first traversal.
598  NodeVector control_; // List of encountered control nodes.
599  Node* component_entry_; // Component single-entry node.
600  BasicBlock* component_start_; // Component single-entry block.
601  BasicBlock* component_end_; // Component single-exit block.
602 };
603 
604 
605 void Scheduler::BuildCFG() {
606  TRACE("--- CREATING CFG -------------------------------------------\n");
607 
608  // Instantiate a new control equivalence algorithm for the graph.
609  equivalence_ = new (zone_) ControlEquivalence(zone_, graph_);
610 
611  // Build a control-flow graph for the main control-connected component that
612  // is being spanned by the graph's start and end nodes.
613  control_flow_builder_ = new (zone_) CFGBuilder(zone_, this);
614  control_flow_builder_->Run();
615 
616  // Initialize per-block data.
617  // Reserve an extra 10% to avoid resizing vector when fusing floating control.
618  scheduled_nodes_.reserve(schedule_->BasicBlockCount() * 1.1);
619  scheduled_nodes_.resize(schedule_->BasicBlockCount());
620 }
621 
622 
623 // -----------------------------------------------------------------------------
624 // Phase 2: Compute special RPO and dominator tree.
625 
626 
627 // Compute the special reverse-post-order block ordering, which is essentially
628 // a RPO of the graph where loop bodies are contiguous. Properties:
629 // 1. If block A is a predecessor of B, then A appears before B in the order,
630 // unless B is a loop header and A is in the loop headed at B
631 // (i.e. A -> B is a backedge).
632 // => If block A dominates block B, then A appears before B in the order.
633 // => If block A is a loop header, A appears before all blocks in the loop
634 // headed at A.
635 // 2. All loops are contiguous in the order (i.e. no intervening blocks that
636 // do not belong to the loop.)
637 // Note a simple RPO traversal satisfies (1) but not (2).
639  public:
640  SpecialRPONumberer(Zone* zone, Schedule* schedule)
641  : zone_(zone),
642  schedule_(schedule),
643  order_(nullptr),
644  beyond_end_(nullptr),
645  loops_(zone),
646  backedges_(zone),
647  stack_(zone),
648  previous_block_count_(0),
649  empty_(0, zone) {}
650 
651  // Computes the special reverse-post-order for the main control flow graph,
652  // that is for the graph spanned between the schedule's start and end blocks.
653  void ComputeSpecialRPO() {
654  DCHECK_EQ(0, schedule_->end()->SuccessorCount());
655  DCHECK(!order_); // Main order does not exist yet.
656  ComputeAndInsertSpecialRPO(schedule_->start(), schedule_->end());
657  }
658 
659  // Computes the special reverse-post-order for a partial control flow graph,
660  // that is for the graph spanned between the given {entry} and {end} blocks,
661  // then updates the existing ordering with this new information.
662  void UpdateSpecialRPO(BasicBlock* entry, BasicBlock* end) {
663  DCHECK(order_); // Main order to be updated is present.
664  ComputeAndInsertSpecialRPO(entry, end);
665  }
666 
667  // Serialize the previously computed order as a special reverse-post-order
668  // numbering for basic blocks into the final schedule.
669  void SerializeRPOIntoSchedule() {
670  int32_t number = 0;
671  for (BasicBlock* b = order_; b != nullptr; b = b->rpo_next()) {
672  b->set_rpo_number(number++);
673  schedule_->rpo_order()->push_back(b);
674  }
675  BeyondEndSentinel()->set_rpo_number(number);
676  }
677 
678  // Print and verify the special reverse-post-order.
679  void PrintAndVerifySpecialRPO() {
680 #if DEBUG
681  if (FLAG_trace_turbo_scheduler) PrintRPO();
682  VerifySpecialRPO();
683 #endif
684  }
685 
686  const ZoneVector<BasicBlock*>& GetOutgoingBlocks(BasicBlock* block) {
687  if (HasLoopNumber(block)) {
688  LoopInfo const& loop = loops_[GetLoopNumber(block)];
689  if (loop.outgoing) return *loop.outgoing;
690  }
691  return empty_;
692  }
693 
694  private:
695  typedef std::pair<BasicBlock*, size_t> Backedge;
696 
697  // Numbering for BasicBlock::rpo_number for this block traversal:
698  static const int kBlockOnStack = -2;
699  static const int kBlockVisited1 = -3;
700  static const int kBlockVisited2 = -4;
701  static const int kBlockUnvisited1 = -1;
702  static const int kBlockUnvisited2 = kBlockVisited1;
703 
704  struct SpecialRPOStackFrame {
705  BasicBlock* block;
706  size_t index;
707  };
708 
709  struct LoopInfo {
710  BasicBlock* header;
711  ZoneVector<BasicBlock*>* outgoing;
712  BitVector* members;
713  LoopInfo* prev;
714  BasicBlock* end;
715  BasicBlock* start;
716 
717  void AddOutgoing(Zone* zone, BasicBlock* block) {
718  if (outgoing == nullptr) {
719  outgoing = new (zone->New(sizeof(ZoneVector<BasicBlock*>)))
721  }
722  outgoing->push_back(block);
723  }
724  };
725 
726  int Push(ZoneVector<SpecialRPOStackFrame>& stack, int depth,
727  BasicBlock* child, int unvisited) {
728  if (child->rpo_number() == unvisited) {
729  stack[depth].block = child;
730  stack[depth].index = 0;
731  child->set_rpo_number(kBlockOnStack);
732  return depth + 1;
733  }
734  return depth;
735  }
736 
737  BasicBlock* PushFront(BasicBlock* head, BasicBlock* block) {
738  block->set_rpo_next(head);
739  return block;
740  }
741 
742  static int GetLoopNumber(BasicBlock* block) { return block->loop_number(); }
743  static void SetLoopNumber(BasicBlock* block, int loop_number) {
744  return block->set_loop_number(loop_number);
745  }
746  static bool HasLoopNumber(BasicBlock* block) {
747  return block->loop_number() >= 0;
748  }
749 
750  // TODO(mstarzinger): We only need this special sentinel because some tests
751  // use the schedule's end block in actual control flow (e.g. with end having
752  // successors). Once this has been cleaned up we can use the end block here.
753  BasicBlock* BeyondEndSentinel() {
754  if (beyond_end_ == nullptr) {
755  BasicBlock::Id id = BasicBlock::Id::FromInt(-1);
756  beyond_end_ = new (schedule_->zone()) BasicBlock(schedule_->zone(), id);
757  }
758  return beyond_end_;
759  }
760 
761  // Compute special RPO for the control flow graph between {entry} and {end},
762  // mutating any existing order so that the result is still valid.
763  void ComputeAndInsertSpecialRPO(BasicBlock* entry, BasicBlock* end) {
764  // RPO should not have been serialized for this schedule yet.
765  CHECK_EQ(kBlockUnvisited1, schedule_->start()->loop_number());
766  CHECK_EQ(kBlockUnvisited1, schedule_->start()->rpo_number());
767  CHECK_EQ(0, static_cast<int>(schedule_->rpo_order()->size()));
768 
769  // Find correct insertion point within existing order.
770  BasicBlock* insertion_point = entry->rpo_next();
771  BasicBlock* order = insertion_point;
772 
773  // Perform an iterative RPO traversal using an explicit stack,
774  // recording backedges that form cycles. O(|B|).
775  DCHECK_LT(previous_block_count_, schedule_->BasicBlockCount());
776  stack_.resize(schedule_->BasicBlockCount() - previous_block_count_);
777  previous_block_count_ = schedule_->BasicBlockCount();
778  int stack_depth = Push(stack_, 0, entry, kBlockUnvisited1);
779  int num_loops = static_cast<int>(loops_.size());
780 
781  while (stack_depth > 0) {
782  int current = stack_depth - 1;
783  SpecialRPOStackFrame* frame = &stack_[current];
784 
785  if (frame->block != end &&
786  frame->index < frame->block->SuccessorCount()) {
787  // Process the next successor.
788  BasicBlock* succ = frame->block->SuccessorAt(frame->index++);
789  if (succ->rpo_number() == kBlockVisited1) continue;
790  if (succ->rpo_number() == kBlockOnStack) {
791  // The successor is on the stack, so this is a backedge (cycle).
792  backedges_.push_back(Backedge(frame->block, frame->index - 1));
793  if (!HasLoopNumber(succ)) {
794  // Assign a new loop number to the header if it doesn't have one.
795  SetLoopNumber(succ, num_loops++);
796  }
797  } else {
798  // Push the successor onto the stack.
799  DCHECK_EQ(kBlockUnvisited1, succ->rpo_number());
800  stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited1);
801  }
802  } else {
803  // Finished with all successors; pop the stack and add the block.
804  order = PushFront(order, frame->block);
805  frame->block->set_rpo_number(kBlockVisited1);
806  stack_depth--;
807  }
808  }
809 
810  // If no loops were encountered, then the order we computed was correct.
811  if (num_loops > static_cast<int>(loops_.size())) {
812  // Otherwise, compute the loop information from the backedges in order
813  // to perform a traversal that groups loop bodies together.
814  ComputeLoopInfo(stack_, num_loops, &backedges_);
815 
816  // Initialize the "loop stack". Note the entry could be a loop header.
817  LoopInfo* loop =
818  HasLoopNumber(entry) ? &loops_[GetLoopNumber(entry)] : nullptr;
819  order = insertion_point;
820 
821  // Perform an iterative post-order traversal, visiting loop bodies before
822  // edges that lead out of loops. Visits each block once, but linking loop
823  // sections together is linear in the loop size, so overall is
824  // O(|B| + max(loop_depth) * max(|loop|))
825  stack_depth = Push(stack_, 0, entry, kBlockUnvisited2);
826  while (stack_depth > 0) {
827  SpecialRPOStackFrame* frame = &stack_[stack_depth - 1];
828  BasicBlock* block = frame->block;
829  BasicBlock* succ = nullptr;
830 
831  if (block != end && frame->index < block->SuccessorCount()) {
832  // Process the next normal successor.
833  succ = block->SuccessorAt(frame->index++);
834  } else if (HasLoopNumber(block)) {
835  // Process additional outgoing edges from the loop header.
836  if (block->rpo_number() == kBlockOnStack) {
837  // Finish the loop body the first time the header is left on the
838  // stack.
839  DCHECK(loop != nullptr && loop->header == block);
840  loop->start = PushFront(order, block);
841  order = loop->end;
842  block->set_rpo_number(kBlockVisited2);
843  // Pop the loop stack and continue visiting outgoing edges within
844  // the context of the outer loop, if any.
845  loop = loop->prev;
846  // We leave the loop header on the stack; the rest of this iteration
847  // and later iterations will go through its outgoing edges list.
848  }
849 
850  // Use the next outgoing edge if there are any.
851  size_t outgoing_index = frame->index - block->SuccessorCount();
852  LoopInfo* info = &loops_[GetLoopNumber(block)];
853  DCHECK(loop != info);
854  if (block != entry && info->outgoing != nullptr &&
855  outgoing_index < info->outgoing->size()) {
856  succ = info->outgoing->at(outgoing_index);
857  frame->index++;
858  }
859  }
860 
861  if (succ != nullptr) {
862  // Process the next successor.
863  if (succ->rpo_number() == kBlockOnStack) continue;
864  if (succ->rpo_number() == kBlockVisited2) continue;
865  DCHECK_EQ(kBlockUnvisited2, succ->rpo_number());
866  if (loop != nullptr && !loop->members->Contains(succ->id().ToInt())) {
867  // The successor is not in the current loop or any nested loop.
868  // Add it to the outgoing edges of this loop and visit it later.
869  loop->AddOutgoing(zone_, succ);
870  } else {
871  // Push the successor onto the stack.
872  stack_depth = Push(stack_, stack_depth, succ, kBlockUnvisited2);
873  if (HasLoopNumber(succ)) {
874  // Push the inner loop onto the loop stack.
875  DCHECK(GetLoopNumber(succ) < num_loops);
876  LoopInfo* next = &loops_[GetLoopNumber(succ)];
877  next->end = order;
878  next->prev = loop;
879  loop = next;
880  }
881  }
882  } else {
883  // Finished with all successors of the current block.
884  if (HasLoopNumber(block)) {
885  // If we are going to pop a loop header, then add its entire body.
886  LoopInfo* info = &loops_[GetLoopNumber(block)];
887  for (BasicBlock* b = info->start; true; b = b->rpo_next()) {
888  if (b->rpo_next() == info->end) {
889  b->set_rpo_next(order);
890  info->end = order;
891  break;
892  }
893  }
894  order = info->start;
895  } else {
896  // Pop a single node off the stack and add it to the order.
897  order = PushFront(order, block);
898  block->set_rpo_number(kBlockVisited2);
899  }
900  stack_depth--;
901  }
902  }
903  }
904 
905  // Publish new order the first time.
906  if (order_ == nullptr) order_ = order;
907 
908  // Compute the correct loop headers and set the correct loop ends.
909  LoopInfo* current_loop = nullptr;
910  BasicBlock* current_header = entry->loop_header();
911  int32_t loop_depth = entry->loop_depth();
912  if (entry->IsLoopHeader()) --loop_depth; // Entry might be a loop header.
913  for (BasicBlock* b = order; b != insertion_point; b = b->rpo_next()) {
914  BasicBlock* current = b;
915 
916  // Reset BasicBlock::rpo_number again.
917  current->set_rpo_number(kBlockUnvisited1);
918 
919  // Finish the previous loop(s) if we just exited them.
920  while (current_header != nullptr &&
921  current == current_header->loop_end()) {
922  DCHECK(current_header->IsLoopHeader());
923  DCHECK_NOT_NULL(current_loop);
924  current_loop = current_loop->prev;
925  current_header =
926  current_loop == nullptr ? nullptr : current_loop->header;
927  --loop_depth;
928  }
929  current->set_loop_header(current_header);
930 
931  // Push a new loop onto the stack if this loop is a loop header.
932  if (HasLoopNumber(current)) {
933  ++loop_depth;
934  current_loop = &loops_[GetLoopNumber(current)];
935  BasicBlock* end = current_loop->end;
936  current->set_loop_end(end == nullptr ? BeyondEndSentinel() : end);
937  current_header = current_loop->header;
938  TRACE("id:%d is a loop header, increment loop depth to %d\n",
939  current->id().ToInt(), loop_depth);
940  }
941 
942  current->set_loop_depth(loop_depth);
943 
944  if (current->loop_header() == nullptr) {
945  TRACE("id:%d is not in a loop (depth == %d)\n", current->id().ToInt(),
946  current->loop_depth());
947  } else {
948  TRACE("id:%d has loop header id:%d, (depth == %d)\n",
949  current->id().ToInt(), current->loop_header()->id().ToInt(),
950  current->loop_depth());
951  }
952  }
953  }
954 
955  // Computes loop membership from the backedges of the control flow graph.
956  void ComputeLoopInfo(ZoneVector<SpecialRPOStackFrame>& queue,
957  size_t num_loops, ZoneVector<Backedge>* backedges) {
958  // Extend existing loop membership vectors.
959  for (LoopInfo& loop : loops_) {
960  loop.members->Resize(static_cast<int>(schedule_->BasicBlockCount()),
961  zone_);
962  }
963 
964  // Extend loop information vector.
965  loops_.resize(num_loops, LoopInfo());
966 
967  // Compute loop membership starting from backedges.
968  // O(max(loop_depth) * max(|loop|)
969  for (size_t i = 0; i < backedges->size(); i++) {
970  BasicBlock* member = backedges->at(i).first;
971  BasicBlock* header = member->SuccessorAt(backedges->at(i).second);
972  size_t loop_num = GetLoopNumber(header);
973  if (loops_[loop_num].header == nullptr) {
974  loops_[loop_num].header = header;
975  loops_[loop_num].members = new (zone_)
976  BitVector(static_cast<int>(schedule_->BasicBlockCount()), zone_);
977  }
978 
979  int queue_length = 0;
980  if (member != header) {
981  // As long as the header doesn't have a backedge to itself,
982  // Push the member onto the queue and process its predecessors.
983  if (!loops_[loop_num].members->Contains(member->id().ToInt())) {
984  loops_[loop_num].members->Add(member->id().ToInt());
985  }
986  queue[queue_length++].block = member;
987  }
988 
989  // Propagate loop membership backwards. All predecessors of M up to the
990  // loop header H are members of the loop too. O(|blocks between M and H|).
991  while (queue_length > 0) {
992  BasicBlock* block = queue[--queue_length].block;
993  for (size_t i = 0; i < block->PredecessorCount(); i++) {
994  BasicBlock* pred = block->PredecessorAt(i);
995  if (pred != header) {
996  if (!loops_[loop_num].members->Contains(pred->id().ToInt())) {
997  loops_[loop_num].members->Add(pred->id().ToInt());
998  queue[queue_length++].block = pred;
999  }
1000  }
1001  }
1002  }
1003  }
1004  }
1005 
1006 #if DEBUG
1007  void PrintRPO() {
1008  StdoutStream os;
1009  os << "RPO with " << loops_.size() << " loops";
1010  if (loops_.size() > 0) {
1011  os << " (";
1012  for (size_t i = 0; i < loops_.size(); i++) {
1013  if (i > 0) os << " ";
1014  os << "id:" << loops_[i].header->id();
1015  }
1016  os << ")";
1017  }
1018  os << ":\n";
1019 
1020  for (BasicBlock* block = order_; block != nullptr;
1021  block = block->rpo_next()) {
1022  os << std::setw(5) << "B" << block->rpo_number() << ":";
1023  for (size_t i = 0; i < loops_.size(); i++) {
1024  bool range = loops_[i].header->LoopContains(block);
1025  bool membership = loops_[i].header != block && range;
1026  os << (membership ? " |" : " ");
1027  os << (range ? "x" : " ");
1028  }
1029  os << " id:" << block->id() << ": ";
1030  if (block->loop_end() != nullptr) {
1031  os << " range: [B" << block->rpo_number() << ", B"
1032  << block->loop_end()->rpo_number() << ")";
1033  }
1034  if (block->loop_header() != nullptr) {
1035  os << " header: id:" << block->loop_header()->id();
1036  }
1037  if (block->loop_depth() > 0) {
1038  os << " depth: " << block->loop_depth();
1039  }
1040  os << "\n";
1041  }
1042  }
1043 
1044  void VerifySpecialRPO() {
1045  BasicBlockVector* order = schedule_->rpo_order();
1046  DCHECK_LT(0, order->size());
1047  DCHECK_EQ(0, (*order)[0]->id().ToInt()); // entry should be first.
1048 
1049  for (size_t i = 0; i < loops_.size(); i++) {
1050  LoopInfo* loop = &loops_[i];
1051  BasicBlock* header = loop->header;
1052  BasicBlock* end = header->loop_end();
1053 
1054  DCHECK_NOT_NULL(header);
1055  DCHECK_LE(0, header->rpo_number());
1056  DCHECK_LT(header->rpo_number(), order->size());
1057  DCHECK_NOT_NULL(end);
1058  DCHECK_LE(end->rpo_number(), order->size());
1059  DCHECK_GT(end->rpo_number(), header->rpo_number());
1060  DCHECK_NE(header->loop_header(), header);
1061 
1062  // Verify the start ... end list relationship.
1063  int links = 0;
1064  BasicBlock* block = loop->start;
1065  DCHECK_EQ(header, block);
1066  bool end_found;
1067  while (true) {
1068  if (block == nullptr || block == loop->end) {
1069  end_found = (loop->end == block);
1070  break;
1071  }
1072  // The list should be in same order as the final result.
1073  DCHECK(block->rpo_number() == links + header->rpo_number());
1074  links++;
1075  block = block->rpo_next();
1076  DCHECK_LT(links, static_cast<int>(2 * order->size())); // cycle?
1077  }
1078  DCHECK_LT(0, links);
1079  DCHECK_EQ(links, end->rpo_number() - header->rpo_number());
1080  DCHECK(end_found);
1081 
1082  // Check loop depth of the header.
1083  int loop_depth = 0;
1084  for (LoopInfo* outer = loop; outer != nullptr; outer = outer->prev) {
1085  loop_depth++;
1086  }
1087  DCHECK_EQ(loop_depth, header->loop_depth());
1088 
1089  // Check the contiguousness of loops.
1090  int count = 0;
1091  for (int j = 0; j < static_cast<int>(order->size()); j++) {
1092  BasicBlock* block = order->at(j);
1093  DCHECK_EQ(block->rpo_number(), j);
1094  if (j < header->rpo_number() || j >= end->rpo_number()) {
1095  DCHECK(!header->LoopContains(block));
1096  } else {
1097  DCHECK(header->LoopContains(block));
1098  DCHECK_GE(block->loop_depth(), loop_depth);
1099  count++;
1100  }
1101  }
1102  DCHECK_EQ(links, count);
1103  }
1104  }
1105 #endif // DEBUG
1106 
1107  Zone* zone_;
1108  Schedule* schedule_;
1109  BasicBlock* order_;
1110  BasicBlock* beyond_end_;
1111  ZoneVector<LoopInfo> loops_;
1112  ZoneVector<Backedge> backedges_;
1114  size_t previous_block_count_;
1115  ZoneVector<BasicBlock*> const empty_;
1116 };
1117 
1118 
1119 BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
1120  SpecialRPONumberer numberer(zone, schedule);
1121  numberer.ComputeSpecialRPO();
1122  numberer.SerializeRPOIntoSchedule();
1123  numberer.PrintAndVerifySpecialRPO();
1124  return schedule->rpo_order();
1125 }
1126 
1127 
1128 void Scheduler::ComputeSpecialRPONumbering() {
1129  TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n");
1130 
1131  // Compute the special reverse-post-order for basic blocks.
1132  special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_);
1133  special_rpo_->ComputeSpecialRPO();
1134 }
1135 
1136 
1137 void Scheduler::PropagateImmediateDominators(BasicBlock* block) {
1138  for (/*nop*/; block != nullptr; block = block->rpo_next()) {
1139  auto pred = block->predecessors().begin();
1140  auto end = block->predecessors().end();
1141  DCHECK(pred != end); // All blocks except start have predecessors.
1142  BasicBlock* dominator = *pred;
1143  bool deferred = dominator->deferred();
1144  // For multiple predecessors, walk up the dominator tree until a common
1145  // dominator is found. Visitation order guarantees that all predecessors
1146  // except for backwards edges have been visited.
1147  for (++pred; pred != end; ++pred) {
1148  // Don't examine backwards edges.
1149  if ((*pred)->dominator_depth() < 0) continue;
1150  dominator = BasicBlock::GetCommonDominator(dominator, *pred);
1151  deferred = deferred & (*pred)->deferred();
1152  }
1153  block->set_dominator(dominator);
1154  block->set_dominator_depth(dominator->dominator_depth() + 1);
1155  block->set_deferred(deferred | block->deferred());
1156  TRACE("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(),
1157  dominator->id().ToInt(), block->dominator_depth());
1158  }
1159 }
1160 
1161 
1162 void Scheduler::GenerateImmediateDominatorTree() {
1163  TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
1164 
1165  // Seed start block to be the first dominator.
1166  schedule_->start()->set_dominator_depth(0);
1167 
1168  // Build the block dominator tree resulting from the above seed.
1169  PropagateImmediateDominators(schedule_->start()->rpo_next());
1170 }
1171 
1172 
1173 // -----------------------------------------------------------------------------
1174 // Phase 3: Prepare use counts for nodes.
1175 
1176 
1178  public:
1179  explicit PrepareUsesVisitor(Scheduler* scheduler)
1180  : scheduler_(scheduler), schedule_(scheduler->schedule_) {}
1181 
1182  void Pre(Node* node) {
1183  if (scheduler_->InitializePlacement(node) == Scheduler::kFixed) {
1184  // Fixed nodes are always roots for schedule late.
1185  scheduler_->schedule_root_nodes_.push_back(node);
1186  if (!schedule_->IsScheduled(node)) {
1187  // Make sure root nodes are scheduled in their respective blocks.
1188  TRACE("Scheduling fixed position node #%d:%s\n", node->id(),
1189  node->op()->mnemonic());
1190  IrOpcode::Value opcode = node->opcode();
1191  BasicBlock* block =
1192  opcode == IrOpcode::kParameter
1193  ? schedule_->start()
1194  : schedule_->block(NodeProperties::GetControlInput(node));
1195  DCHECK_NOT_NULL(block);
1196  schedule_->AddNode(block, node);
1197  }
1198  }
1199  }
1200 
1201  void PostEdge(Node* from, int index, Node* to) {
1202  // If the edge is from an unscheduled node, then tally it in the use count
1203  // for all of its inputs. The same criterion will be used in ScheduleLate
1204  // for decrementing use counts.
1205  if (!schedule_->IsScheduled(from)) {
1206  DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
1207  scheduler_->IncrementUnscheduledUseCount(to, index, from);
1208  }
1209  }
1210 
1211  private:
1212  Scheduler* scheduler_;
1213  Schedule* schedule_;
1214 };
1215 
1216 
1217 void Scheduler::PrepareUses() {
1218  TRACE("--- PREPARE USES -------------------------------------------\n");
1219 
1220  // Count the uses of every node, which is used to ensure that all of a
1221  // node's uses are scheduled before the node itself.
1222  PrepareUsesVisitor prepare_uses(this);
1223 
1224  // TODO(turbofan): simplify the careful pre/post ordering here.
1225  BoolVector visited(graph_->NodeCount(), false, zone_);
1227  Node* node = graph_->end();
1228  prepare_uses.Pre(node);
1229  visited[node->id()] = true;
1230  stack.push(node->input_edges().begin());
1231  while (!stack.empty()) {
1232  Edge edge = *stack.top();
1233  Node* node = edge.to();
1234  if (visited[node->id()]) {
1235  prepare_uses.PostEdge(edge.from(), edge.index(), edge.to());
1236  if (++stack.top() == edge.from()->input_edges().end()) stack.pop();
1237  } else {
1238  prepare_uses.Pre(node);
1239  visited[node->id()] = true;
1240  if (node->InputCount() > 0) stack.push(node->input_edges().begin());
1241  }
1242  }
1243 }
1244 
1245 
1246 // -----------------------------------------------------------------------------
1247 // Phase 4: Schedule nodes early.
1248 
1249 
1251  public:
1252  ScheduleEarlyNodeVisitor(Zone* zone, Scheduler* scheduler)
1253  : scheduler_(scheduler), schedule_(scheduler->schedule_), queue_(zone) {}
1254 
1255  // Run the schedule early algorithm on a set of fixed root nodes.
1256  void Run(NodeVector* roots) {
1257  for (Node* const root : *roots) {
1258  queue_.push(root);
1259  while (!queue_.empty()) {
1260  VisitNode(queue_.front());
1261  queue_.pop();
1262  }
1263  }
1264  }
1265 
1266  private:
1267  // Visits one node from the queue and propagates its current schedule early
1268  // position to all uses. This in turn might push more nodes onto the queue.
1269  void VisitNode(Node* node) {
1270  Scheduler::SchedulerData* data = scheduler_->GetData(node);
1271 
1272  // Fixed nodes already know their schedule early position.
1273  if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
1274  data->minimum_block_ = schedule_->block(node);
1275  TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1276  node->id(), node->op()->mnemonic(),
1277  data->minimum_block_->id().ToInt(),
1278  data->minimum_block_->dominator_depth());
1279  }
1280 
1281  // No need to propagate unconstrained schedule early positions.
1282  if (data->minimum_block_ == schedule_->start()) return;
1283 
1284  // Propagate schedule early position.
1285  DCHECK_NOT_NULL(data->minimum_block_);
1286  for (auto use : node->uses()) {
1287  if (scheduler_->IsLive(use)) {
1288  PropagateMinimumPositionToNode(data->minimum_block_, use);
1289  }
1290  }
1291  }
1292 
1293  // Propagates {block} as another minimum position into the given {node}. This
1294  // has the net effect of computing the minimum dominator block of {node} that
1295  // still post-dominates all inputs to {node} when the queue is processed.
1296  void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) {
1297  Scheduler::SchedulerData* data = scheduler_->GetData(node);
1298 
1299  // No need to propagate to fixed node, it's guaranteed to be a root.
1300  if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;
1301 
1302  // Coupled nodes influence schedule early position of their control.
1303  if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1304  Node* control = NodeProperties::GetControlInput(node);
1305  PropagateMinimumPositionToNode(block, control);
1306  }
1307 
1308  // Propagate new position if it is deeper down the dominator tree than the
1309  // current. Note that all inputs need to have minimum block position inside
1310  // the dominator chain of {node}'s minimum block position.
1311  DCHECK(InsideSameDominatorChain(block, data->minimum_block_));
1312  if (block->dominator_depth() > data->minimum_block_->dominator_depth()) {
1313  data->minimum_block_ = block;
1314  queue_.push(node);
1315  TRACE("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
1316  node->id(), node->op()->mnemonic(),
1317  data->minimum_block_->id().ToInt(),
1318  data->minimum_block_->dominator_depth());
1319  }
1320  }
1321 
1322 #if DEBUG
1323  bool InsideSameDominatorChain(BasicBlock* b1, BasicBlock* b2) {
1324  BasicBlock* dominator = BasicBlock::GetCommonDominator(b1, b2);
1325  return dominator == b1 || dominator == b2;
1326  }
1327 #endif
1328 
1329  Scheduler* scheduler_;
1330  Schedule* schedule_;
1331  ZoneQueue<Node*> queue_;
1332 };
1333 
1334 
1335 void Scheduler::ScheduleEarly() {
1336  TRACE("--- SCHEDULE EARLY -----------------------------------------\n");
1337  if (FLAG_trace_turbo_scheduler) {
1338  TRACE("roots: ");
1339  for (Node* node : schedule_root_nodes_) {
1340  TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1341  }
1342  TRACE("\n");
1343  }
1344 
1345  // Compute the minimum block for each node thereby determining the earliest
1346  // position each node could be placed within a valid schedule.
1347  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
1348  schedule_early_visitor.Run(&schedule_root_nodes_);
1349 }
1350 
1351 
1352 // -----------------------------------------------------------------------------
1353 // Phase 5: Schedule nodes late.
1354 
1355 
1357  public:
1358  ScheduleLateNodeVisitor(Zone* zone, Scheduler* scheduler)
1359  : zone_(zone),
1360  scheduler_(scheduler),
1361  schedule_(scheduler_->schedule_),
1362  marked_(scheduler->zone_),
1363  marking_queue_(scheduler->zone_) {}
1364 
1365  // Run the schedule late algorithm on a set of fixed root nodes.
1366  void Run(NodeVector* roots) {
1367  for (Node* const root : *roots) {
1368  ProcessQueue(root);
1369  }
1370  }
1371 
1372  private:
1373  void ProcessQueue(Node* root) {
1374  ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
1375  for (Node* node : root->inputs()) {
1376  // Don't schedule coupled nodes on their own.
1377  if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
1378  node = NodeProperties::GetControlInput(node);
1379  }
1380 
1381  // Test schedulability condition by looking at unscheduled use count.
1382  if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;
1383 
1384  queue->push(node);
1385  do {
1386  Node* const node = queue->front();
1387  queue->pop();
1388  VisitNode(node);
1389  } while (!queue->empty());
1390  }
1391  }
1392 
1393  // Visits one node from the queue of schedulable nodes and determines its
1394  // schedule late position. Also hoists nodes out of loops to find a more
1395  // optimal scheduling position.
1396  void VisitNode(Node* node) {
1397  DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1398 
1399  // Don't schedule nodes that are already scheduled.
1400  if (schedule_->IsScheduled(node)) return;
1401  DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));
1402 
1403  // Determine the dominating block for all of the uses of this node. It is
1404  // the latest block that this node can be scheduled in.
1405  TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
1406  BasicBlock* block = GetCommonDominatorOfUses(node);
1407  DCHECK_NOT_NULL(block);
1408 
1409  // The schedule early block dominates the schedule late block.
1410  BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
1411  DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
1412  TRACE(
1413  "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n",
1414  node->id(), node->op()->mnemonic(), block->id().ToInt(),
1415  block->loop_depth(), min_block->id().ToInt());
1416 
1417  // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
1418  // into enclosing loop pre-headers until they would precede their schedule
1419  // early position.
1420  BasicBlock* hoist_block = GetHoistBlock(block);
1421  if (hoist_block &&
1422  hoist_block->dominator_depth() >= min_block->dominator_depth()) {
1423  do {
1424  TRACE(" hoisting #%d:%s to block id:%d\n", node->id(),
1425  node->op()->mnemonic(), hoist_block->id().ToInt());
1426  DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
1427  block = hoist_block;
1428  hoist_block = GetHoistBlock(hoist_block);
1429  } while (hoist_block &&
1430  hoist_block->dominator_depth() >= min_block->dominator_depth());
1431  } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
1432  // Split the {node} if beneficial and return the new {block} for it.
1433  block = SplitNode(block, node);
1434  }
1435 
1436  // Schedule the node or a floating control structure.
1437  if (IrOpcode::IsMergeOpcode(node->opcode())) {
1438  ScheduleFloatingControl(block, node);
1439  } else if (node->opcode() == IrOpcode::kFinishRegion) {
1440  ScheduleRegion(block, node);
1441  } else {
1442  ScheduleNode(block, node);
1443  }
1444  }
1445 
1446  bool IsMarked(BasicBlock* block) const {
1447  DCHECK_LT(block->id().ToSize(), marked_.size());
1448  return marked_[block->id().ToSize()];
1449  }
1450 
1451  void Mark(BasicBlock* block) { marked_[block->id().ToSize()] = true; }
1452 
1453  // Mark {block} and push its non-marked predecessor on the marking queue.
1454  void MarkBlock(BasicBlock* block) {
1455  DCHECK_LT(block->id().ToSize(), marked_.size());
1456  Mark(block);
1457  for (BasicBlock* pred_block : block->predecessors()) {
1458  if (IsMarked(pred_block)) continue;
1459  marking_queue_.push_back(pred_block);
1460  }
1461  }
1462 
1463  BasicBlock* SplitNode(BasicBlock* block, Node* node) {
1464  // For now, we limit splitting to pure nodes.
1465  if (!node->op()->HasProperty(Operator::kPure)) return block;
1466  // TODO(titzer): fix the special case of splitting of projections.
1467  if (node->opcode() == IrOpcode::kProjection) return block;
1468 
1469  // The {block} is common dominator of all uses of {node}, so we cannot
1470  // split anything unless the {block} has at least two successors.
1471  DCHECK_EQ(block, GetCommonDominatorOfUses(node));
1472  if (block->SuccessorCount() < 2) return block;
1473 
1474  // Clear marking bits.
1475  DCHECK(marking_queue_.empty());
1476  std::fill(marked_.begin(), marked_.end(), false);
1477  marked_.resize(schedule_->BasicBlockCount() + 1, false);
1478 
1479  // Check if the {node} has uses in {block}.
1480  for (Edge edge : node->use_edges()) {
1481  if (!scheduler_->IsLive(edge.from())) continue;
1482  BasicBlock* use_block = GetBlockForUse(edge);
1483  if (use_block == nullptr || IsMarked(use_block)) continue;
1484  if (use_block == block) {
1485  TRACE(" not splitting #%d:%s, it is used in id:%d\n", node->id(),
1486  node->op()->mnemonic(), block->id().ToInt());
1487  marking_queue_.clear();
1488  return block;
1489  }
1490  MarkBlock(use_block);
1491  }
1492 
1493  // Compute transitive marking closure; a block is marked if all its
1494  // successors are marked.
1495  do {
1496  BasicBlock* top_block = marking_queue_.front();
1497  marking_queue_.pop_front();
1498  if (IsMarked(top_block)) continue;
1499  bool marked = true;
1500  for (BasicBlock* successor : top_block->successors()) {
1501  if (!IsMarked(successor)) {
1502  marked = false;
1503  break;
1504  }
1505  }
1506  if (marked) MarkBlock(top_block);
1507  } while (!marking_queue_.empty());
1508 
1509  // If the (common dominator) {block} is marked, we know that all paths from
1510  // {block} to the end contain at least one use of {node}, and hence there's
1511  // no point in splitting the {node} in this case.
1512  if (IsMarked(block)) {
1513  TRACE(" not splitting #%d:%s, its common dominator id:%d is perfect\n",
1514  node->id(), node->op()->mnemonic(), block->id().ToInt());
1515  return block;
1516  }
1517 
1518  // Split {node} for uses according to the previously computed marking
1519  // closure. Every marking partition has a unique dominator, which get's a
1520  // copy of the {node} with the exception of the first partition, which get's
1521  // the {node} itself.
1522  ZoneMap<BasicBlock*, Node*> dominators(scheduler_->zone_);
1523  for (Edge edge : node->use_edges()) {
1524  if (!scheduler_->IsLive(edge.from())) continue;
1525  BasicBlock* use_block = GetBlockForUse(edge);
1526  if (use_block == nullptr) continue;
1527  while (IsMarked(use_block->dominator())) {
1528  use_block = use_block->dominator();
1529  }
1530  auto& use_node = dominators[use_block];
1531  if (use_node == nullptr) {
1532  if (dominators.size() == 1u) {
1533  // Place the {node} at {use_block}.
1534  block = use_block;
1535  use_node = node;
1536  TRACE(" pushing #%d:%s down to id:%d\n", node->id(),
1537  node->op()->mnemonic(), block->id().ToInt());
1538  } else {
1539  // Place a copy of {node} at {use_block}.
1540  use_node = CloneNode(node);
1541  TRACE(" cloning #%d:%s for id:%d\n", use_node->id(),
1542  use_node->op()->mnemonic(), use_block->id().ToInt());
1543  scheduler_->schedule_queue_.push(use_node);
1544  }
1545  }
1546  edge.UpdateTo(use_node);
1547  }
1548  return block;
1549  }
1550 
1551  BasicBlock* GetHoistBlock(BasicBlock* block) {
1552  if (block->IsLoopHeader()) return block->dominator();
1553  // We have to check to make sure that the {block} dominates all
1554  // of the outgoing blocks. If it doesn't, then there is a path
1555  // out of the loop which does not execute this {block}, so we
1556  // can't hoist operations from this {block} out of the loop, as
1557  // that would introduce additional computations.
1558  if (BasicBlock* header_block = block->loop_header()) {
1559  for (BasicBlock* outgoing_block :
1560  scheduler_->special_rpo_->GetOutgoingBlocks(header_block)) {
1561  if (BasicBlock::GetCommonDominator(block, outgoing_block) != block) {
1562  return nullptr;
1563  }
1564  }
1565  return header_block->dominator();
1566  }
1567  return nullptr;
1568  }
1569 
1570  BasicBlock* GetCommonDominatorOfUses(Node* node) {
1571  BasicBlock* block = nullptr;
1572  for (Edge edge : node->use_edges()) {
1573  if (!scheduler_->IsLive(edge.from())) continue;
1574  BasicBlock* use_block = GetBlockForUse(edge);
1575  block = block == nullptr
1576  ? use_block
1577  : use_block == nullptr
1578  ? block
1579  : BasicBlock::GetCommonDominator(block, use_block);
1580  }
1581  return block;
1582  }
1583 
1584  BasicBlock* FindPredecessorBlock(Node* node) {
1585  return scheduler_->control_flow_builder_->FindPredecessorBlock(node);
1586  }
1587 
1588  BasicBlock* GetBlockForUse(Edge edge) {
1589  // TODO(titzer): ignore uses from dead nodes (not visited in PrepareUses()).
1590  // Dead uses only occur if the graph is not trimmed before scheduling.
1591  Node* use = edge.from();
1592  if (IrOpcode::IsPhiOpcode(use->opcode())) {
1593  // If the use is from a coupled (i.e. floating) phi, compute the common
1594  // dominator of its uses. This will not recurse more than one level.
1595  if (scheduler_->GetPlacement(use) == Scheduler::kCoupled) {
1596  TRACE(" inspecting uses of coupled #%d:%s\n", use->id(),
1597  use->op()->mnemonic());
1598  // TODO(titzer): reenable once above TODO is addressed.
1599  // DCHECK_EQ(edge.to(), NodeProperties::GetControlInput(use));
1600  return GetCommonDominatorOfUses(use);
1601  }
1602  // If the use is from a fixed (i.e. non-floating) phi, we use the
1603  // predecessor block of the corresponding control input to the merge.
1604  if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1605  TRACE(" input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(),
1606  use->op()->mnemonic());
1607  Node* merge = NodeProperties::GetControlInput(use, 0);
1608  DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
1609  Node* input = NodeProperties::GetControlInput(merge, edge.index());
1610  return FindPredecessorBlock(input);
1611  }
1612  } else if (IrOpcode::IsMergeOpcode(use->opcode())) {
1613  // If the use is from a fixed (i.e. non-floating) merge, we use the
1614  // predecessor block of the current input to the merge.
1615  if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
1616  TRACE(" input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(),
1617  use->op()->mnemonic());
1618  return FindPredecessorBlock(edge.to());
1619  }
1620  }
1621  BasicBlock* result = schedule_->block(use);
1622  if (result == nullptr) return nullptr;
1623  TRACE(" must dominate use #%d:%s in id:%d\n", use->id(),
1624  use->op()->mnemonic(), result->id().ToInt());
1625  return result;
1626  }
1627 
1628  void ScheduleFloatingControl(BasicBlock* block, Node* node) {
1629  scheduler_->FuseFloatingControl(block, node);
1630  }
1631 
1632  void ScheduleRegion(BasicBlock* block, Node* region_end) {
1633  // We only allow regions of instructions connected into a linear
1634  // effect chain. The only value allowed to be produced by a node
1635  // in the chain must be the value consumed by the FinishRegion node.
1636 
1637  // We schedule back to front; we first schedule FinishRegion.
1638  CHECK_EQ(IrOpcode::kFinishRegion, region_end->opcode());
1639  ScheduleNode(block, region_end);
1640 
1641  // Schedule the chain.
1642  Node* node = NodeProperties::GetEffectInput(region_end);
1643  while (node->opcode() != IrOpcode::kBeginRegion) {
1644  DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1645  DCHECK_EQ(1, node->op()->EffectInputCount());
1646  DCHECK_EQ(1, node->op()->EffectOutputCount());
1647  DCHECK_EQ(0, node->op()->ControlOutputCount());
1648  // The value output (if there is any) must be consumed
1649  // by the EndRegion node.
1650  DCHECK(node->op()->ValueOutputCount() == 0 ||
1651  node == region_end->InputAt(0));
1652  ScheduleNode(block, node);
1653  node = NodeProperties::GetEffectInput(node);
1654  }
1655  // Schedule the BeginRegion node.
1656  DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
1657  ScheduleNode(block, node);
1658  }
1659 
1660  void ScheduleNode(BasicBlock* block, Node* node) {
1661  schedule_->PlanNode(block, node);
1662  size_t block_id = block->id().ToSize();
1663  if (!scheduler_->scheduled_nodes_[block_id]) {
1664  scheduler_->scheduled_nodes_[block_id] =
1665  new (zone_->New(sizeof(NodeVector))) NodeVector(zone_);
1666  }
1667  scheduler_->scheduled_nodes_[block_id]->push_back(node);
1668  scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
1669  }
1670 
1671  Node* CloneNode(Node* node) {
1672  int const input_count = node->InputCount();
1673  for (int index = 0; index < input_count; ++index) {
1674  Node* const input = node->InputAt(index);
1675  scheduler_->IncrementUnscheduledUseCount(input, index, node);
1676  }
1677  Node* const copy = scheduler_->graph_->CloneNode(node);
1678  TRACE(("clone #%d:%s -> #%d\n"), node->id(), node->op()->mnemonic(),
1679  copy->id());
1680  scheduler_->node_data_.resize(copy->id() + 1,
1681  scheduler_->DefaultSchedulerData());
1682  scheduler_->node_data_[copy->id()] = scheduler_->node_data_[node->id()];
1683  return copy;
1684  }
1685 
1686  Zone* zone_;
1687  Scheduler* scheduler_;
1688  Schedule* schedule_;
1689  BoolVector marked_;
1690  ZoneDeque<BasicBlock*> marking_queue_;
1691 };
1692 
1693 
1694 void Scheduler::ScheduleLate() {
1695  TRACE("--- SCHEDULE LATE ------------------------------------------\n");
1696  if (FLAG_trace_turbo_scheduler) {
1697  TRACE("roots: ");
1698  for (Node* node : schedule_root_nodes_) {
1699  TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1700  }
1701  TRACE("\n");
1702  }
1703 
1704  // Schedule: Places nodes in dominator block of all their uses.
1705  ScheduleLateNodeVisitor schedule_late_visitor(zone_, this);
1706  schedule_late_visitor.Run(&schedule_root_nodes_);
1707 }
1708 
1709 
1710 // -----------------------------------------------------------------------------
1711 // Phase 6: Seal the final schedule.
1712 
1713 
1714 void Scheduler::SealFinalSchedule() {
1715  TRACE("--- SEAL FINAL SCHEDULE ------------------------------------\n");
1716 
1717  // Serialize the assembly order and reverse-post-order numbering.
1718  special_rpo_->SerializeRPOIntoSchedule();
1719  special_rpo_->PrintAndVerifySpecialRPO();
1720 
1721  // Add collected nodes for basic blocks to their blocks in the right order.
1722  int block_num = 0;
1723  for (NodeVector* nodes : scheduled_nodes_) {
1724  BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++);
1725  BasicBlock* block = schedule_->GetBlockById(id);
1726  if (nodes) {
1727  for (Node* node : base::Reversed(*nodes)) {
1728  schedule_->AddNode(block, node);
1729  }
1730  }
1731  }
1732 }
1733 
1734 
1735 // -----------------------------------------------------------------------------
1736 
1737 
1738 void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
1739  TRACE("--- FUSE FLOATING CONTROL ----------------------------------\n");
1740  if (FLAG_trace_turbo_scheduler) {
1741  StdoutStream{} << "Schedule before control flow fusion:\n" << *schedule_;
1742  }
1743 
1744  // Iterate on phase 1: Build control-flow graph.
1745  control_flow_builder_->Run(block, node);
1746 
1747  // Iterate on phase 2: Compute special RPO and dominator tree.
1748  special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
1749  // TODO(mstarzinger): Currently "iterate on" means "re-run". Fix that.
1750  for (BasicBlock* b = block->rpo_next(); b != nullptr; b = b->rpo_next()) {
1751  b->set_dominator_depth(-1);
1752  b->set_dominator(nullptr);
1753  }
1754  PropagateImmediateDominators(block->rpo_next());
1755 
1756  // Iterate on phase 4: Schedule nodes early.
1757  // TODO(mstarzinger): The following loop gathering the propagation roots is a
1758  // temporary solution and should be merged into the rest of the scheduler as
1759  // soon as the approach settled for all floating loops.
1760  NodeVector propagation_roots(control_flow_builder_->control_);
1761  for (Node* node : control_flow_builder_->control_) {
1762  for (Node* use : node->uses()) {
1763  if (NodeProperties::IsPhi(use) && IsLive(use)) {
1764  propagation_roots.push_back(use);
1765  }
1766  }
1767  }
1768  if (FLAG_trace_turbo_scheduler) {
1769  TRACE("propagation roots: ");
1770  for (Node* node : propagation_roots) {
1771  TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
1772  }
1773  TRACE("\n");
1774  }
1775  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
1776  schedule_early_visitor.Run(&propagation_roots);
1777 
1778  // Move previously planned nodes.
1779  // TODO(mstarzinger): Improve that by supporting bulk moves.
1780  scheduled_nodes_.resize(schedule_->BasicBlockCount());
1781  MovePlannedNodes(block, schedule_->block(node));
1782 
1783  if (FLAG_trace_turbo_scheduler) {
1784  StdoutStream{} << "Schedule after control flow fusion:\n" << *schedule_;
1785  }
1786 }
1787 
1788 
1789 void Scheduler::MovePlannedNodes(BasicBlock* from, BasicBlock* to) {
1790  TRACE("Move planned nodes from id:%d to id:%d\n", from->id().ToInt(),
1791  to->id().ToInt());
1792  NodeVector* from_nodes = scheduled_nodes_[from->id().ToSize()];
1793  NodeVector* to_nodes = scheduled_nodes_[to->id().ToSize()];
1794  if (!from_nodes) return;
1795 
1796  for (Node* const node : *from_nodes) {
1797  schedule_->SetBlockForNode(to, node);
1798  }
1799  if (to_nodes) {
1800  to_nodes->insert(to_nodes->end(), from_nodes->begin(), from_nodes->end());
1801  from_nodes->clear();
1802  } else {
1803  std::swap(scheduled_nodes_[from->id().ToSize()],
1804  scheduled_nodes_[to->id().ToSize()]);
1805  }
1806 }
1807 
1808 #undef TRACE
1809 
1810 } // namespace compiler
1811 } // namespace internal
1812 } // namespace v8
Definition: libplatform.h:13