V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
schedule.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/schedule.h"
6 
7 #include "src/compiler/node-properties.h"
8 #include "src/compiler/node.h"
9 #include "src/ostreams.h"
10 
11 namespace v8 {
12 namespace internal {
13 namespace compiler {
14 
15 BasicBlock::BasicBlock(Zone* zone, Id id)
16  : loop_number_(-1),
17  rpo_number_(-1),
18  deferred_(false),
19  dominator_depth_(-1),
20  dominator_(nullptr),
21  rpo_next_(nullptr),
22  loop_header_(nullptr),
23  loop_end_(nullptr),
24  loop_depth_(0),
25  control_(kNone),
26  control_input_(nullptr),
27  nodes_(zone),
28  successors_(zone),
29  predecessors_(zone),
30 #if DEBUG
31  debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
32 #endif
33  id_(id) {
34 }
35 
36 bool BasicBlock::LoopContains(BasicBlock* block) const {
37  // RPO numbers must be initialized.
38  DCHECK_LE(0, rpo_number_);
39  DCHECK_LE(0, block->rpo_number_);
40  if (loop_end_ == nullptr) return false; // This is not a loop.
41  return block->rpo_number_ >= rpo_number_ &&
42  block->rpo_number_ < loop_end_->rpo_number_;
43 }
44 
45 void BasicBlock::AddSuccessor(BasicBlock* successor) {
46  successors_.push_back(successor);
47 }
48 
49 void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
50  predecessors_.push_back(predecessor);
51 }
52 
53 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
54 
55 void BasicBlock::set_control(Control control) { control_ = control; }
56 
57 void BasicBlock::set_control_input(Node* control_input) {
58  if (!nodes_.empty() && control_input == nodes_.back()) {
59  nodes_.pop_back();
60  }
61  control_input_ = control_input;
62 }
63 
64 void BasicBlock::set_loop_depth(int32_t loop_depth) {
65  loop_depth_ = loop_depth;
66 }
67 
68 void BasicBlock::set_rpo_number(int32_t rpo_number) {
69  rpo_number_ = rpo_number;
70 }
71 
72 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
73 
74 void BasicBlock::set_loop_header(BasicBlock* loop_header) {
75  loop_header_ = loop_header;
76 }
77 
78 // static
79 BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
80  while (b1 != b2) {
81  if (b1->dominator_depth() < b2->dominator_depth()) {
82  b2 = b2->dominator();
83  } else {
84  b1 = b1->dominator();
85  }
86  }
87  return b1;
88 }
89 
90 void BasicBlock::Print() { StdoutStream{} << this; }
91 
92 std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
93  os << "B" << block.id();
94 #if DEBUG
95  AssemblerDebugInfo info = block.debug_info();
96  if (info.name) os << info;
97  // Print predecessor blocks for better debugging.
98  const int kMaxDisplayedBlocks = 4;
99  int i = 0;
100  const BasicBlock* current_block = &block;
101  while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
102  current_block = current_block->predecessors().front();
103  os << " <= B" << current_block->id();
104  info = current_block->debug_info();
105  if (info.name) os << info;
106  }
107 #endif
108  return os;
109 }
110 
111 std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
112  switch (c) {
113  case BasicBlock::kNone:
114  return os << "none";
115  case BasicBlock::kGoto:
116  return os << "goto";
117  case BasicBlock::kCall:
118  return os << "call";
119  case BasicBlock::kBranch:
120  return os << "branch";
121  case BasicBlock::kSwitch:
122  return os << "switch";
123  case BasicBlock::kDeoptimize:
124  return os << "deoptimize";
125  case BasicBlock::kTailCall:
126  return os << "tailcall";
127  case BasicBlock::kReturn:
128  return os << "return";
129  case BasicBlock::kThrow:
130  return os << "throw";
131  }
132  UNREACHABLE();
133 }
134 
135 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
136  return os << id.ToSize();
137 }
138 
139 Schedule::Schedule(Zone* zone, size_t node_count_hint)
140  : zone_(zone),
141  all_blocks_(zone),
142  nodeid_to_block_(zone),
143  rpo_order_(zone),
144  start_(NewBasicBlock()),
145  end_(NewBasicBlock()) {
146  nodeid_to_block_.reserve(node_count_hint);
147 }
148 
149 BasicBlock* Schedule::block(Node* node) const {
150  if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
151  return nodeid_to_block_[node->id()];
152  }
153  return nullptr;
154 }
155 
156 bool Schedule::IsScheduled(Node* node) {
157  if (node->id() >= nodeid_to_block_.size()) return false;
158  return nodeid_to_block_[node->id()] != nullptr;
159 }
160 
161 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
162  DCHECK(block_id.ToSize() < all_blocks_.size());
163  return all_blocks_[block_id.ToSize()];
164 }
165 
166 bool Schedule::SameBasicBlock(Node* a, Node* b) const {
167  BasicBlock* block = this->block(a);
168  return block != nullptr && block == this->block(b);
169 }
170 
171 BasicBlock* Schedule::NewBasicBlock() {
172  BasicBlock* block = new (zone_)
173  BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
174  all_blocks_.push_back(block);
175  return block;
176 }
177 
178 void Schedule::PlanNode(BasicBlock* block, Node* node) {
179  if (FLAG_trace_turbo_scheduler) {
180  StdoutStream{} << "Planning #" << node->id() << ":"
181  << node->op()->mnemonic() << " for future add to B"
182  << block->id() << "\n";
183  }
184  DCHECK_NULL(this->block(node));
185  SetBlockForNode(block, node);
186 }
187 
188 void Schedule::AddNode(BasicBlock* block, Node* node) {
189  if (FLAG_trace_turbo_scheduler) {
190  StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
191  << " to B" << block->id() << "\n";
192  }
193  DCHECK(this->block(node) == nullptr || this->block(node) == block);
194  block->AddNode(node);
195  SetBlockForNode(block, node);
196 }
197 
198 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
199  DCHECK_EQ(BasicBlock::kNone, block->control());
200  block->set_control(BasicBlock::kGoto);
201  AddSuccessor(block, succ);
202 }
203 
204 #if DEBUG
205 namespace {
206 
207 bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
208  switch (opcode) {
209 #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
210  JS_OP_LIST(BUILD_BLOCK_JS_CASE)
211 #undef BUILD_BLOCK_JS_CASE
212  case IrOpcode::kCall:
213  case IrOpcode::kCallWithCallerSavedRegisters:
214  return true;
215  default:
216  return false;
217  }
218 }
219 
220 } // namespace
221 #endif // DEBUG
222 
223 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
224  BasicBlock* exception_block) {
225  DCHECK_EQ(BasicBlock::kNone, block->control());
226  DCHECK(IsPotentiallyThrowingCall(call->opcode()));
227  block->set_control(BasicBlock::kCall);
228  AddSuccessor(block, success_block);
229  AddSuccessor(block, exception_block);
230  SetControlInput(block, call);
231 }
232 
233 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
234  BasicBlock* fblock) {
235  DCHECK_EQ(BasicBlock::kNone, block->control());
236  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
237  block->set_control(BasicBlock::kBranch);
238  AddSuccessor(block, tblock);
239  AddSuccessor(block, fblock);
240  SetControlInput(block, branch);
241 }
242 
243 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
244  size_t succ_count) {
245  DCHECK_EQ(BasicBlock::kNone, block->control());
246  DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
247  block->set_control(BasicBlock::kSwitch);
248  for (size_t index = 0; index < succ_count; ++index) {
249  AddSuccessor(block, succ_blocks[index]);
250  }
251  SetControlInput(block, sw);
252 }
253 
254 void Schedule::AddTailCall(BasicBlock* block, Node* input) {
255  DCHECK_EQ(BasicBlock::kNone, block->control());
256  block->set_control(BasicBlock::kTailCall);
257  SetControlInput(block, input);
258  if (block != end()) AddSuccessor(block, end());
259 }
260 
261 void Schedule::AddReturn(BasicBlock* block, Node* input) {
262  DCHECK_EQ(BasicBlock::kNone, block->control());
263  block->set_control(BasicBlock::kReturn);
264  SetControlInput(block, input);
265  if (block != end()) AddSuccessor(block, end());
266 }
267 
268 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
269  DCHECK_EQ(BasicBlock::kNone, block->control());
270  block->set_control(BasicBlock::kDeoptimize);
271  SetControlInput(block, input);
272  if (block != end()) AddSuccessor(block, end());
273 }
274 
275 void Schedule::AddThrow(BasicBlock* block, Node* input) {
276  DCHECK_EQ(BasicBlock::kNone, block->control());
277  block->set_control(BasicBlock::kThrow);
278  SetControlInput(block, input);
279  if (block != end()) AddSuccessor(block, end());
280 }
281 
282 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
283  BasicBlock* tblock, BasicBlock* fblock) {
284  DCHECK_NE(BasicBlock::kNone, block->control());
285  DCHECK_EQ(BasicBlock::kNone, end->control());
286  end->set_control(block->control());
287  block->set_control(BasicBlock::kBranch);
288  MoveSuccessors(block, end);
289  AddSuccessor(block, tblock);
290  AddSuccessor(block, fblock);
291  if (block->control_input() != nullptr) {
292  SetControlInput(end, block->control_input());
293  }
294  SetControlInput(block, branch);
295 }
296 
297 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
298  BasicBlock** succ_blocks, size_t succ_count) {
299  DCHECK_NE(BasicBlock::kNone, block->control());
300  DCHECK_EQ(BasicBlock::kNone, end->control());
301  end->set_control(block->control());
302  block->set_control(BasicBlock::kSwitch);
303  MoveSuccessors(block, end);
304  for (size_t index = 0; index < succ_count; ++index) {
305  AddSuccessor(block, succ_blocks[index]);
306  }
307  if (block->control_input() != nullptr) {
308  SetControlInput(end, block->control_input());
309  }
310  SetControlInput(block, sw);
311 }
312 
313 void Schedule::EnsureCFGWellFormedness() {
314  // Make a copy of all the blocks for the iteration, since adding the split
315  // edges will allocate new blocks.
316  BasicBlockVector all_blocks_copy(all_blocks_);
317 
318  // Insert missing split edge blocks.
319  for (BasicBlock* block : all_blocks_copy) {
320  if (block->PredecessorCount() > 1) {
321  if (block != end_) {
322  EnsureSplitEdgeForm(block);
323  }
324  if (block->deferred()) {
325  EnsureDeferredCodeSingleEntryPoint(block);
326  }
327  }
328  }
329 
330  EliminateRedundantPhiNodes();
331 }
332 
333 void Schedule::EliminateRedundantPhiNodes() {
334  // Ensure that useless phi nodes that only have a single input, identical
335  // inputs, or are a self-referential loop phi,
336  // -- which can happen with the automatically generated code in the CSA and
337  // torque -- are pruned.
338  // Since we have strucured control flow, this is enough to minimize the number
339  // of phi nodes.
340  bool reached_fixed_point = false;
341  while (!reached_fixed_point) {
342  reached_fixed_point = true;
343  for (BasicBlock* block : all_blocks_) {
344  int predecessor_count = static_cast<int>(block->PredecessorCount());
345  for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
346  Node* node = block->NodeAt(node_pos);
347  if (node->opcode() == IrOpcode::kPhi) {
348  Node* first_input = node->InputAt(0);
349  bool inputs_equal = true;
350  for (int i = 1; i < predecessor_count; ++i) {
351  Node* input = node->InputAt(i);
352  if (input != first_input && input != node) {
353  inputs_equal = false;
354  break;
355  }
356  }
357  if (!inputs_equal) continue;
358  node->ReplaceUses(first_input);
359  block->RemoveNode(block->begin() + node_pos);
360  --node_pos;
361  reached_fixed_point = false;
362  }
363  }
364  }
365  }
366 }
367 
368 void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
369 #ifdef DEBUG
370  DCHECK(block->PredecessorCount() > 1 && block != end_);
371  for (auto current_pred = block->predecessors().begin();
372  current_pred != block->predecessors().end(); ++current_pred) {
373  BasicBlock* pred = *current_pred;
374  DCHECK_LE(pred->SuccessorCount(), 1);
375  }
376 #endif
377 }
378 
379 void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
380  // If a deferred block has multiple predecessors, they have to
381  // all be deferred. Otherwise, we can run into a situation where a range
382  // that spills only in deferred blocks inserts its spill in the block, but
383  // other ranges need moves inserted by ResolveControlFlow in the predecessors,
384  // which may clobber the register of this range.
385  // To ensure that, when a deferred block has multiple predecessors, and some
386  // are not deferred, we add a non-deferred block to collect all such edges.
387 
388  DCHECK(block->deferred() && block->PredecessorCount() > 1);
389  bool all_deferred = true;
390  for (auto current_pred = block->predecessors().begin();
391  current_pred != block->predecessors().end(); ++current_pred) {
392  BasicBlock* pred = *current_pred;
393  if (!pred->deferred()) {
394  all_deferred = false;
395  break;
396  }
397  }
398 
399  if (all_deferred) return;
400  BasicBlock* merger = NewBasicBlock();
401  merger->set_control(BasicBlock::kGoto);
402  merger->successors().push_back(block);
403  for (auto current_pred = block->predecessors().begin();
404  current_pred != block->predecessors().end(); ++current_pred) {
405  BasicBlock* pred = *current_pred;
406  merger->predecessors().push_back(pred);
407  pred->successors().clear();
408  pred->successors().push_back(merger);
409  }
410  merger->set_deferred(false);
411  block->predecessors().clear();
412  block->predecessors().push_back(merger);
413  MovePhis(block, merger);
414 }
415 
416 void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
417  for (size_t i = 0; i < from->NodeCount();) {
418  Node* node = from->NodeAt(i);
419  if (node->opcode() == IrOpcode::kPhi) {
420  to->AddNode(node);
421  from->RemoveNode(from->begin() + i);
422  DCHECK_EQ(nodeid_to_block_[node->id()], from);
423  nodeid_to_block_[node->id()] = to;
424  } else {
425  ++i;
426  }
427  }
428 }
429 
430 void Schedule::PropagateDeferredMark() {
431  // Push forward the deferred block marks through newly inserted blocks and
432  // other improperly marked blocks until a fixed point is reached.
433  // TODO(danno): optimize the propagation
434  bool done = false;
435  while (!done) {
436  done = true;
437  for (auto block : all_blocks_) {
438  if (!block->deferred()) {
439  bool deferred = block->PredecessorCount() > 0;
440  for (auto pred : block->predecessors()) {
441  if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
442  deferred = false;
443  }
444  }
445  if (deferred) {
446  block->set_deferred(true);
447  done = false;
448  }
449  }
450  }
451  }
452 }
453 
454 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
455  block->AddSuccessor(succ);
456  succ->AddPredecessor(block);
457 }
458 
459 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
460  for (BasicBlock* const successor : from->successors()) {
461  to->AddSuccessor(successor);
462  for (BasicBlock*& predecessor : successor->predecessors()) {
463  if (predecessor == from) predecessor = to;
464  }
465  }
466  from->ClearSuccessors();
467 }
468 
469 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
470  block->set_control_input(node);
471  SetBlockForNode(block, node);
472 }
473 
474 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
475  if (node->id() >= nodeid_to_block_.size()) {
476  nodeid_to_block_.resize(node->id() + 1);
477  }
478  nodeid_to_block_[node->id()] = block;
479 }
480 
481 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
482  for (BasicBlock* block :
483  ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
484  if (block->rpo_number() == -1) {
485  os << "--- BLOCK id:" << block->id().ToInt();
486  } else {
487  os << "--- BLOCK B" << block->rpo_number();
488  }
489  if (block->deferred()) os << " (deferred)";
490  if (block->PredecessorCount() != 0) os << " <- ";
491  bool comma = false;
492  for (BasicBlock const* predecessor : block->predecessors()) {
493  if (comma) os << ", ";
494  comma = true;
495  if (predecessor->rpo_number() == -1) {
496  os << "id:" << predecessor->id().ToInt();
497  } else {
498  os << "B" << predecessor->rpo_number();
499  }
500  }
501  os << " ---\n";
502  for (Node* node : *block) {
503  os << " " << *node;
504  if (NodeProperties::IsTyped(node)) {
505  os << " : " << NodeProperties::GetType(node);
506  }
507  os << "\n";
508  }
509  BasicBlock::Control control = block->control();
510  if (control != BasicBlock::kNone) {
511  os << " ";
512  if (block->control_input() != nullptr) {
513  os << *block->control_input();
514  } else {
515  os << "Goto";
516  }
517  os << " -> ";
518  comma = false;
519  for (BasicBlock const* successor : block->successors()) {
520  if (comma) os << ", ";
521  comma = true;
522  if (successor->rpo_number() == -1) {
523  os << "id:" << successor->id().ToInt();
524  } else {
525  os << "B" << successor->rpo_number();
526  }
527  }
528  os << "\n";
529  }
530  }
531  return os;
532 }
533 
534 } // namespace compiler
535 } // namespace internal
536 } // namespace v8
Definition: libplatform.h:13