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