schedule.cc 15.2 KB
Newer Older
1 2 3 4
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6
#include "src/compiler/schedule.h"

7
#include "src/compiler/node-properties.h"
8
#include "src/compiler/node.h"
9
#include "src/utils/ostreams.h"
10 11 12 13 14

namespace v8 {
namespace internal {
namespace compiler {

15
BasicBlock::BasicBlock(Zone* zone, Id id)
16
    : loop_number_(-1),
17 18
      rpo_number_(-1),
      deferred_(false),
19
      dominator_depth_(-1),
20 21 22 23
      dominator_(nullptr),
      rpo_next_(nullptr),
      loop_header_(nullptr),
      loop_end_(nullptr),
24 25
      loop_depth_(0),
      control_(kNone),
26
      control_input_(nullptr),
27 28 29
      nodes_(zone),
      successors_(zone),
      predecessors_(zone),
30 31 32 33 34
#if DEBUG
      debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
#endif
      id_(id) {
}
35 36 37

bool BasicBlock::LoopContains(BasicBlock* block) const {
  // RPO numbers must be initialized.
38 39
  DCHECK_LE(0, rpo_number_);
  DCHECK_LE(0, block->rpo_number_);
40
  if (loop_end_ == nullptr) return false;  // This is not a loop.
41 42
  return block->rpo_number_ >= rpo_number_ &&
         block->rpo_number_ < loop_end_->rpo_number_;
43 44 45 46 47 48 49 50 51 52
}

void BasicBlock::AddSuccessor(BasicBlock* successor) {
  successors_.push_back(successor);
}

void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
  predecessors_.push_back(predecessor);
}

53 54 55 56
void BasicBlock::RemovePredecessor(size_t index) {
  predecessors_.erase(predecessors_.begin() + index);
}

57 58
void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }

59
void BasicBlock::set_control(Control control) { control_ = control; }
60 61

void BasicBlock::set_control_input(Node* control_input) {
62 63 64
  if (!nodes_.empty() && control_input == nodes_.back()) {
    nodes_.pop_back();
  }
65 66 67 68 69 70 71 72 73 74 75
  control_input_ = control_input;
}

void BasicBlock::set_loop_depth(int32_t loop_depth) {
  loop_depth_ = loop_depth;
}

void BasicBlock::set_rpo_number(int32_t rpo_number) {
  rpo_number_ = rpo_number;
}

76
void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
77 78 79 80 81

void BasicBlock::set_loop_header(BasicBlock* loop_header) {
  loop_header_ = loop_header;
}

82 83 84 85 86 87 88 89 90 91 92 93 94
void BasicBlock::TrimNodes(iterator new_end) { nodes_.erase(new_end, end()); }

void BasicBlock::ResetRPOInfo() {
  loop_number_ = -1;
  rpo_number_ = -1;
  dominator_depth_ = -1;
  dominator_ = nullptr;
  rpo_next_ = nullptr;
  loop_header_ = nullptr;
  loop_end_ = nullptr;
  loop_depth_ = 0;
}

95 96 97 98 99 100 101 102 103 104 105 106
// static
BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
  while (b1 != b2) {
    if (b1->dominator_depth() < b2->dominator_depth()) {
      b2 = b2->dominator();
    } else {
      b1 = b1->dominator();
    }
  }
  return b1;
}

107
void BasicBlock::Print() { StdoutStream{} << *this << "\n"; }
108

109
std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
110
  os << "id:" << block.id();
111 112 113 114 115 116 117 118 119
#if DEBUG
  AssemblerDebugInfo info = block.debug_info();
  if (info.name) os << info;
  // Print predecessor blocks for better debugging.
  const int kMaxDisplayedBlocks = 4;
  int i = 0;
  const BasicBlock* current_block = &block;
  while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
    current_block = current_block->predecessors().front();
120
    os << " <= id:" << current_block->id();
121 122 123 124 125 126
    info = current_block->debug_info();
    if (info.name) os << info;
  }
#endif
  return os;
}
127

128
std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
129
  switch (c) {
130
    case BasicBlock::kNone:
131
      return os << "none";
132
    case BasicBlock::kGoto:
133
      return os << "goto";
134 135
    case BasicBlock::kCall:
      return os << "call";
136
    case BasicBlock::kBranch:
137
      return os << "branch";
138 139
    case BasicBlock::kSwitch:
      return os << "switch";
140 141
    case BasicBlock::kDeoptimize:
      return os << "deoptimize";
142 143
    case BasicBlock::kTailCall:
      return os << "tailcall";
144
    case BasicBlock::kReturn:
145
      return os << "return";
146
    case BasicBlock::kThrow:
147 148 149 150 151
      return os << "throw";
  }
  UNREACHABLE();
}

152
std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
  return os << id.ToSize();
}

Schedule::Schedule(Zone* zone, size_t node_count_hint)
    : zone_(zone),
      all_blocks_(zone),
      nodeid_to_block_(zone),
      rpo_order_(zone),
      start_(NewBasicBlock()),
      end_(NewBasicBlock()) {
  nodeid_to_block_.reserve(node_count_hint);
}

BasicBlock* Schedule::block(Node* node) const {
  if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
    return nodeid_to_block_[node->id()];
  }
170
  return nullptr;
171 172 173
}

bool Schedule::IsScheduled(Node* node) {
174
  if (node->id() >= nodeid_to_block_.size()) return false;
175
  return nodeid_to_block_[node->id()] != nullptr;
176 177 178 179 180 181 182
}

BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
  DCHECK(block_id.ToSize() < all_blocks_.size());
  return all_blocks_[block_id.ToSize()];
}

183 184 185 186 187
void Schedule::ClearBlockById(BasicBlock::Id block_id) {
  DCHECK(block_id.ToSize() < all_blocks_.size());
  all_blocks_[block_id.ToSize()] = nullptr;
}

188 189
bool Schedule::SameBasicBlock(Node* a, Node* b) const {
  BasicBlock* block = this->block(a);
190
  return block != nullptr && block == this->block(b);
191 192 193
}

BasicBlock* Schedule::NewBasicBlock() {
194 195
  BasicBlock* block = zone_->New<BasicBlock>(
      zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
196 197 198 199 200 201
  all_blocks_.push_back(block);
  return block;
}

void Schedule::PlanNode(BasicBlock* block, Node* node) {
  if (FLAG_trace_turbo_scheduler) {
202
    StdoutStream{} << "Planning #" << node->id() << ":"
203 204
                   << node->op()->mnemonic()
                   << " for future add to id:" << block->id() << "\n";
205
  }
206
  DCHECK_NULL(this->block(node));
207 208 209 210 211
  SetBlockForNode(block, node);
}

void Schedule::AddNode(BasicBlock* block, Node* node) {
  if (FLAG_trace_turbo_scheduler) {
212
    StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
213
                   << " to id:" << block->id() << "\n";
214
  }
215
  DCHECK(this->block(node) == nullptr || this->block(node) == block);
216 217 218 219 220
  block->AddNode(node);
  SetBlockForNode(block, node);
}

void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
221
  CHECK_EQ(BasicBlock::kNone, block->control());
222 223 224 225
  block->set_control(BasicBlock::kGoto);
  AddSuccessor(block, succ);
}

226 227 228 229 230
#if DEBUG
namespace {

bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
  switch (opcode) {
231
#define BUILD_BLOCK_JS_CASE(Name, ...) case IrOpcode::k##Name:
232 233 234 235 236 237 238 239 240 241 242
    JS_OP_LIST(BUILD_BLOCK_JS_CASE)
#undef BUILD_BLOCK_JS_CASE
    case IrOpcode::kCall:
      return true;
    default:
      return false;
  }
}

}  // namespace
#endif  // DEBUG
243

244 245
void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
                       BasicBlock* exception_block) {
246
  CHECK_EQ(BasicBlock::kNone, block->control());
247
  DCHECK(IsPotentiallyThrowingCall(call->opcode()));
248 249 250 251 252 253
  block->set_control(BasicBlock::kCall);
  AddSuccessor(block, success_block);
  AddSuccessor(block, exception_block);
  SetControlInput(block, call);
}

254 255
void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
                         BasicBlock* fblock) {
256
  CHECK_EQ(BasicBlock::kNone, block->control());
257
  DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
258 259 260 261 262 263
  block->set_control(BasicBlock::kBranch);
  AddSuccessor(block, tblock);
  AddSuccessor(block, fblock);
  SetControlInput(block, branch);
}

264 265
void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
                         size_t succ_count) {
266
  CHECK_EQ(BasicBlock::kNone, block->control());
267 268 269 270 271 272
  DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
  block->set_control(BasicBlock::kSwitch);
  for (size_t index = 0; index < succ_count; ++index) {
    AddSuccessor(block, succ_blocks[index]);
  }
  SetControlInput(block, sw);
273 274 275
}

void Schedule::AddTailCall(BasicBlock* block, Node* input) {
276
  CHECK_EQ(BasicBlock::kNone, block->control());
277 278 279
  block->set_control(BasicBlock::kTailCall);
  SetControlInput(block, input);
  if (block != end()) AddSuccessor(block, end());
280 281
}

282
void Schedule::AddReturn(BasicBlock* block, Node* input) {
283
  CHECK_EQ(BasicBlock::kNone, block->control());
284 285
  block->set_control(BasicBlock::kReturn);
  SetControlInput(block, input);
286
  if (block != end()) AddSuccessor(block, end());
287 288
}

289
void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
290
  CHECK_EQ(BasicBlock::kNone, block->control());
291 292 293 294 295
  block->set_control(BasicBlock::kDeoptimize);
  SetControlInput(block, input);
  if (block != end()) AddSuccessor(block, end());
}

296
void Schedule::AddThrow(BasicBlock* block, Node* input) {
297
  CHECK_EQ(BasicBlock::kNone, block->control());
298 299 300 301 302
  block->set_control(BasicBlock::kThrow);
  SetControlInput(block, input);
  if (block != end()) AddSuccessor(block, end());
}

303 304
void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
                            BasicBlock* tblock, BasicBlock* fblock) {
305 306
  CHECK_NE(BasicBlock::kNone, block->control());
  CHECK_EQ(BasicBlock::kNone, end->control());
307 308 309 310 311
  end->set_control(block->control());
  block->set_control(BasicBlock::kBranch);
  MoveSuccessors(block, end);
  AddSuccessor(block, tblock);
  AddSuccessor(block, fblock);
312
  if (block->control_input() != nullptr) {
313 314 315 316 317
    SetControlInput(end, block->control_input());
  }
  SetControlInput(block, branch);
}

318 319
void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
                            BasicBlock** succ_blocks, size_t succ_count) {
320 321
  CHECK_NE(BasicBlock::kNone, block->control());
  CHECK_EQ(BasicBlock::kNone, end->control());
322 323 324 325 326 327 328 329 330 331 332 333
  end->set_control(block->control());
  block->set_control(BasicBlock::kSwitch);
  MoveSuccessors(block, end);
  for (size_t index = 0; index < succ_count; ++index) {
    AddSuccessor(block, succ_blocks[index]);
  }
  if (block->control_input() != nullptr) {
    SetControlInput(end, block->control_input());
  }
  SetControlInput(block, sw);
}

334
void Schedule::EnsureCFGWellFormedness() {
335 336 337 338 339
  // Make a copy of all the blocks for the iteration, since adding the split
  // edges will allocate new blocks.
  BasicBlockVector all_blocks_copy(all_blocks_);

  // Insert missing split edge blocks.
340
  for (BasicBlock* block : all_blocks_copy) {
341 342 343 344
    if (block->PredecessorCount() > 1) {
      if (block != end_) {
        EnsureSplitEdgeForm(block);
      }
345 346 347
    }
  }

348
  EliminateRedundantPhiNodes();
349 350
}

351 352 353 354 355 356 357
void Schedule::EliminateRedundantPhiNodes() {
  // Ensure that useless phi nodes that only have a single input, identical
  // inputs, or are a self-referential loop phi,
  // -- which can happen with the automatically generated code in the CSA and
  // torque -- are pruned.
  // Since we have strucured control flow, this is enough to minimize the number
  // of phi nodes.
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
  bool reached_fixed_point = false;
  while (!reached_fixed_point) {
    reached_fixed_point = true;
    for (BasicBlock* block : all_blocks_) {
      int predecessor_count = static_cast<int>(block->PredecessorCount());
      for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
        Node* node = block->NodeAt(node_pos);
        if (node->opcode() == IrOpcode::kPhi) {
          Node* first_input = node->InputAt(0);
          bool inputs_equal = true;
          for (int i = 1; i < predecessor_count; ++i) {
            Node* input = node->InputAt(i);
            if (input != first_input && input != node) {
              inputs_equal = false;
              break;
            }
          }
          if (!inputs_equal) continue;
          node->ReplaceUses(first_input);
377
          node->Kill();
378 379 380 381
          block->RemoveNode(block->begin() + node_pos);
          --node_pos;
          reached_fixed_point = false;
        }
382
      }
383 384 385 386 387
    }
  }
}

void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
388
#ifdef DEBUG
389 390 391 392
  DCHECK(block->PredecessorCount() > 1 && block != end_);
  for (auto current_pred = block->predecessors().begin();
       current_pred != block->predecessors().end(); ++current_pred) {
    BasicBlock* pred = *current_pred;
393
    DCHECK_LE(pred->SuccessorCount(), 1);
394
  }
395
#endif
396 397
}

398 399 400 401 402 403 404 405 406 407 408 409
void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
  for (size_t i = 0; i < from->NodeCount();) {
    Node* node = from->NodeAt(i);
    if (node->opcode() == IrOpcode::kPhi) {
      to->AddNode(node);
      from->RemoveNode(from->begin() + i);
      DCHECK_EQ(nodeid_to_block_[node->id()], from);
      nodeid_to_block_[node->id()] = to;
    } else {
      ++i;
    }
  }
410 411
}

412 413 414 415 416 417 418 419 420 421 422
void Schedule::PropagateDeferredMark() {
  // Push forward the deferred block marks through newly inserted blocks and
  // other improperly marked blocks until a fixed point is reached.
  // TODO(danno): optimize the propagation
  bool done = false;
  while (!done) {
    done = true;
    for (auto block : all_blocks_) {
      if (!block->deferred()) {
        bool deferred = block->PredecessorCount() > 0;
        for (auto pred : block->predecessors()) {
423
          if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
424 425 426 427 428 429 430 431 432 433 434
            deferred = false;
          }
        }
        if (deferred) {
          block->set_deferred(true);
          done = false;
        }
      }
    }
  }
}
435

436 437 438 439 440
void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
  block->AddSuccessor(succ);
  succ->AddPredecessor(block);
}

441
void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
442 443 444 445
  for (BasicBlock* const successor : from->successors()) {
    to->AddSuccessor(successor);
    for (BasicBlock*& predecessor : successor->predecessors()) {
      if (predecessor == from) predecessor = to;
446 447 448 449 450
    }
  }
  from->ClearSuccessors();
}

451 452 453 454 455 456
void Schedule::SetControlInput(BasicBlock* block, Node* node) {
  block->set_control_input(node);
  SetBlockForNode(block, node);
}

void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
457
  if (node->id() >= nodeid_to_block_.size()) {
458 459 460 461 462
    nodeid_to_block_.resize(node->id() + 1);
  }
  nodeid_to_block_[node->id()] = block;
}

463
std::ostream& operator<<(std::ostream& os, const Schedule& s) {
464 465
  for (BasicBlock* block :
       ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
466
    if (block == nullptr) continue;
467
    if (block->rpo_number() == -1) {
468
      os << "--- BLOCK id:" << block->id();
469 470 471
    } else {
      os << "--- BLOCK B" << block->rpo_number();
    }
472
    if (block->deferred()) os << " (deferred)";
473 474
    if (block->PredecessorCount() != 0) os << " <- ";
    bool comma = false;
475
    for (BasicBlock const* predecessor : block->predecessors()) {
476 477
      if (comma) os << ", ";
      comma = true;
478
      if (predecessor->rpo_number() == -1) {
479
        os << "id:" << predecessor->id();
480 481 482
      } else {
        os << "B" << predecessor->rpo_number();
      }
483 484
    }
    os << " ---\n";
485
    for (Node* node : *block) {
486
      os << "  " << *node;
487
      if (NodeProperties::IsTyped(node)) {
488
        os << " : " << NodeProperties::GetType(node);
489 490 491
      }
      os << "\n";
    }
492
    BasicBlock::Control control = block->control();
493 494
    if (control != BasicBlock::kNone) {
      os << "  ";
495
      if (block->control_input() != nullptr) {
496
        os << *block->control_input();
497 498 499 500 501
      } else {
        os << "Goto";
      }
      os << " -> ";
      comma = false;
502
      for (BasicBlock const* successor : block->successors()) {
503 504
        if (comma) os << ", ";
        comma = true;
505
        if (successor->rpo_number() == -1) {
506
          os << "id:" << successor->id();
507 508 509
        } else {
          os << "B" << successor->rpo_number();
        }
510 511 512 513 514 515
      }
      os << "\n";
    }
  }
  return os;
}
516

517 518 519
}  // namespace compiler
}  // namespace internal
}  // namespace v8