deps/v8/src/compiler/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.h"
   8 #include "src/compiler/node-properties.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       id_(id) {}
  31
  32
  33 bool 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_ == NULL) 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
  43 void BasicBlock::AddSuccessor(BasicBlock* successor) {
  44   successors_.push_back(successor);
  45 }
  46
  47
  48 void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
  49   predecessors_.push_back(predecessor);
  50 }
  51
  52
  53 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
  54
  55
  56 void BasicBlock::set_control(Control control) {
  57   control_ = control;
  58 }
  59
  60
  61 void BasicBlock::set_control_input(Node* control_input) {
  62   control_input_ = control_input;
  63 }
  64
  65
  66 void BasicBlock::set_loop_depth(int32_t loop_depth) {
  67   loop_depth_ = loop_depth;
  68 }
  69
  70
  71 void BasicBlock::set_rpo_number(int32_t rpo_number) {
  72   rpo_number_ = rpo_number;
  73 }
  74
  75
  76 void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
  77
  78
  79 void BasicBlock::set_loop_header(BasicBlock* loop_header) {
  80   loop_header_ = loop_header;
  81 }
  82
  83
  84 // static
  85 BasicBlock* 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
  97 std::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::kBranch:
 104       return os << "branch";
 105     case BasicBlock::kSwitch:
 106       return os << "switch";
 107     case BasicBlock::kReturn:
 108       return os << "return";
 109     case BasicBlock::kThrow:
 110       return os << "throw";
 111   }
 112   UNREACHABLE();
 113   return os;
 114 }
 115
 116
 117 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
 118   return os << id.ToSize();
 119 }
 120
 121
 122 std::ostream& operator<<(std::ostream& os, const BasicBlock::RpoNumber& rpo) {
 123   return os << rpo.ToSize();
 124 }
 125
 126
 127 Schedule::Schedule(Zone* zone, size_t node_count_hint)
 128     : zone_(zone),
 129       all_blocks_(zone),
 130       nodeid_to_block_(zone),
 131       rpo_order_(zone),
 132       start_(NewBasicBlock()),
 133       end_(NewBasicBlock()) {
 134   nodeid_to_block_.reserve(node_count_hint);
 135 }
 136
 137
 138 BasicBlock* Schedule::block(Node* node) const {
 139   if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
 140     return nodeid_to_block_[node->id()];
 141   }
 142   return NULL;
 143 }
 144
 145
 146 bool Schedule::IsScheduled(Node* node) {
 147   int length = static_cast<int>(nodeid_to_block_.size());
 148   if (node->id() >= length) return false;
 149   return nodeid_to_block_[node->id()] != NULL;
 150 }
 151
 152
 153 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
 154   DCHECK(block_id.ToSize() < all_blocks_.size());
 155   return all_blocks_[block_id.ToSize()];
 156 }
 157
 158
 159 bool Schedule::SameBasicBlock(Node* a, Node* b) const {
 160   BasicBlock* block = this->block(a);
 161   return block != NULL && block == this->block(b);
 162 }
 163
 164
 165 BasicBlock* 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
 173 void 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) == NULL);
 180   SetBlockForNode(block, node);
 181 }
 182
 183
 184 void 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) == NULL || this->block(node) == block);
 191   block->AddNode(node);
 192   SetBlockForNode(block, node);
 193 }
 194
 195
 196 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
 197   DCHECK(block->control() == BasicBlock::kNone);
 198   block->set_control(BasicBlock::kGoto);
 199   AddSuccessor(block, succ);
 200 }
 201
 202
 203 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
 204                          BasicBlock* fblock) {
 205   DCHECK(block->control() == BasicBlock::kNone);
 206   DCHECK(branch->opcode() == IrOpcode::kBranch);
 207   block->set_control(BasicBlock::kBranch);
 208   AddSuccessor(block, tblock);
 209   AddSuccessor(block, fblock);
 210   SetControlInput(block, branch);
 211 }
 212
 213
 214 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
 215                          size_t succ_count) {
 216   DCHECK_EQ(BasicBlock::kNone, block->control());
 217   DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
 218   block->set_control(BasicBlock::kSwitch);
 219   for (size_t index = 0; index < succ_count; ++index) {
 220     AddSuccessor(block, succ_blocks[index]);
 221   }
 222   SetControlInput(block, sw);
 223 }
 224
 225
 226 void Schedule::AddReturn(BasicBlock* block, Node* input) {
 227   DCHECK(block->control() == BasicBlock::kNone);
 228   block->set_control(BasicBlock::kReturn);
 229   SetControlInput(block, input);
 230   if (block != end()) AddSuccessor(block, end());
 231 }
 232
 233
 234 void Schedule::AddThrow(BasicBlock* block, Node* input) {
 235   DCHECK(block->control() == BasicBlock::kNone);
 236   block->set_control(BasicBlock::kThrow);
 237   SetControlInput(block, input);
 238   if (block != end()) AddSuccessor(block, end());
 239 }
 240
 241
 242 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
 243                             BasicBlock* tblock, BasicBlock* fblock) {
 244   DCHECK(block->control() != BasicBlock::kNone);
 245   DCHECK(end->control() == BasicBlock::kNone);
 246   end->set_control(block->control());
 247   block->set_control(BasicBlock::kBranch);
 248   MoveSuccessors(block, end);
 249   AddSuccessor(block, tblock);
 250   AddSuccessor(block, fblock);
 251   if (block->control_input() != nullptr) {
 252     SetControlInput(end, block->control_input());
 253   }
 254   SetControlInput(block, branch);
 255 }
 256
 257
 258 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
 259                             BasicBlock** succ_blocks, size_t succ_count) {
 260   DCHECK_NE(BasicBlock::kNone, block->control());
 261   DCHECK_EQ(BasicBlock::kNone, end->control());
 262   end->set_control(block->control());
 263   block->set_control(BasicBlock::kSwitch);
 264   MoveSuccessors(block, end);
 265   for (size_t index = 0; index < succ_count; ++index) {
 266     AddSuccessor(block, succ_blocks[index]);
 267   }
 268   if (block->control_input() != nullptr) {
 269     SetControlInput(end, block->control_input());
 270   }
 271   SetControlInput(block, sw);
 272 }
 273
 274
 275 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
 276   block->AddSuccessor(succ);
 277   succ->AddPredecessor(block);
 278 }
 279
 280
 281 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
 282   for (BasicBlock* const successor : from->successors()) {
 283     to->AddSuccessor(successor);
 284     for (BasicBlock*& predecessor : successor->predecessors()) {
 285       if (predecessor == from) predecessor = to;
 286     }
 287   }
 288   from->ClearSuccessors();
 289 }
 290
 291
 292 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
 293   block->set_control_input(node);
 294   SetBlockForNode(block, node);
 295 }
 296
 297
 298 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
 299   int length = static_cast<int>(nodeid_to_block_.size());
 300   if (node->id() >= length) {
 301     nodeid_to_block_.resize(node->id() + 1);
 302   }
 303   nodeid_to_block_[node->id()] = block;
 304 }
 305
 306
 307 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
 308   for (BasicBlock* block : *s.rpo_order()) {
 309     os << "--- BLOCK B" << block->id();
 310     if (block->deferred()) os << " (deferred)";
 311     if (block->PredecessorCount() != 0) os << " <- ";
 312     bool comma = false;
 313     for (BasicBlock const* predecessor : block->predecessors()) {
 314       if (comma) os << ", ";
 315       comma = true;
 316       os << "B" << predecessor->id();
 317     }
 318     os << " ---\n";
 319     for (Node* node : *block) {
 320       os << "  " << *node;
 321       if (NodeProperties::IsTyped(node)) {
 322         Bounds bounds = NodeProperties::GetBounds(node);
 323         os << " : ";
 324         bounds.lower->PrintTo(os);
 325         if (!bounds.upper->Is(bounds.lower)) {
 326           os << "..";
 327           bounds.upper->PrintTo(os);
 328         }
 329       }
 330       os << "\n";
 331     }
 332     BasicBlock::Control control = block->control();
 333     if (control != BasicBlock::kNone) {
 334       os << "  ";
 335       if (block->control_input() != NULL) {
 336         os << *block->control_input();
 337       } else {
 338         os << "Goto";
 339       }
 340       os << " -> ";
 341       comma = false;
 342       for (BasicBlock const* successor : block->successors()) {
 343         if (comma) os << ", ";
 344         comma = true;
 345         os << "B" << successor->id();
 346       }
 347       os << "\n";
 348     }
 349   }
 350   return os;
 351 }
 352
 353 }  // namespace compiler
 354 }  // namespace internal
 355 }  // namespace v8