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::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::kReturn:
 112       return os << "return";
 113     case BasicBlock::kThrow:
 114       return os << "throw";
 115   }
 116   UNREACHABLE();
 117   return os;
 118 }
 119
 120
 121 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
 122   return os << id.ToSize();
 123 }
 124
 125
 126 Schedule::Schedule(Zone* zone, size_t node_count_hint)
 127     : zone_(zone),
 128       all_blocks_(zone),
 129       nodeid_to_block_(zone),
 130       rpo_order_(zone),
 131       start_(NewBasicBlock()),
 132       end_(NewBasicBlock()) {
 133   nodeid_to_block_.reserve(node_count_hint);
 134 }
 135
 136
 137 BasicBlock* Schedule::block(Node* node) const {
 138   if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
 139     return nodeid_to_block_[node->id()];
 140   }
 141   return NULL;
 142 }
 143
 144
 145 bool Schedule::IsScheduled(Node* node) {
 146   int length = static_cast<int>(nodeid_to_block_.size());
 147   if (node->id() >= length) return false;
 148   return nodeid_to_block_[node->id()] != NULL;
 149 }
 150
 151
 152 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
 153   DCHECK(block_id.ToSize() < all_blocks_.size());
 154   return all_blocks_[block_id.ToSize()];
 155 }
 156
 157
 158 bool Schedule::SameBasicBlock(Node* a, Node* b) const {
 159   BasicBlock* block = this->block(a);
 160   return block != NULL && block == this->block(b);
 161 }
 162
 163
 164 BasicBlock* Schedule::NewBasicBlock() {
 165   BasicBlock* block = new (zone_)
 166       BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
 167   all_blocks_.push_back(block);
 168   return block;
 169 }
 170
 171
 172 void Schedule::PlanNode(BasicBlock* block, Node* node) {
 173   if (FLAG_trace_turbo_scheduler) {
 174     OFStream os(stdout);
 175     os << "Planning #" << node->id() << ":" << node->op()->mnemonic()
 176        << " for future add to B" << block->id() << "\n";
 177   }
 178   DCHECK(this->block(node) == NULL);
 179   SetBlockForNode(block, node);
 180 }
 181
 182
 183 void Schedule::AddNode(BasicBlock* block, Node* node) {
 184   if (FLAG_trace_turbo_scheduler) {
 185     OFStream os(stdout);
 186     os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B"
 187        << block->id() << "\n";
 188   }
 189   DCHECK(this->block(node) == NULL || this->block(node) == block);
 190   block->AddNode(node);
 191   SetBlockForNode(block, node);
 192 }
 193
 194
 195 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
 196   DCHECK_EQ(BasicBlock::kNone, block->control());
 197   block->set_control(BasicBlock::kGoto);
 198   AddSuccessor(block, succ);
 199 }
 200
 201
 202 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
 203                        BasicBlock* exception_block) {
 204   DCHECK_EQ(BasicBlock::kNone, block->control());
 205   DCHECK_EQ(IrOpcode::kCall, call->opcode());
 206   block->set_control(BasicBlock::kCall);
 207   AddSuccessor(block, success_block);
 208   AddSuccessor(block, exception_block);
 209   SetControlInput(block, call);
 210 }
 211
 212
 213 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
 214                          BasicBlock* fblock) {
 215   DCHECK_EQ(BasicBlock::kNone, block->control());
 216   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
 217   block->set_control(BasicBlock::kBranch);
 218   AddSuccessor(block, tblock);
 219   AddSuccessor(block, fblock);
 220   SetControlInput(block, branch);
 221 }
 222
 223
 224 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
 225                          size_t succ_count) {
 226   DCHECK_EQ(BasicBlock::kNone, block->control());
 227   DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
 228   block->set_control(BasicBlock::kSwitch);
 229   for (size_t index = 0; index < succ_count; ++index) {
 230     AddSuccessor(block, succ_blocks[index]);
 231   }
 232   SetControlInput(block, sw);
 233 }
 234
 235
 236 void Schedule::AddReturn(BasicBlock* block, Node* input) {
 237   DCHECK_EQ(BasicBlock::kNone, block->control());
 238   block->set_control(BasicBlock::kReturn);
 239   SetControlInput(block, input);
 240   if (block != end()) AddSuccessor(block, end());
 241 }
 242
 243
 244 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
 245   DCHECK_EQ(BasicBlock::kNone, block->control());
 246   block->set_control(BasicBlock::kDeoptimize);
 247   SetControlInput(block, input);
 248   if (block != end()) AddSuccessor(block, end());
 249 }
 250
 251
 252 void Schedule::AddThrow(BasicBlock* block, Node* input) {
 253   DCHECK_EQ(BasicBlock::kNone, block->control());
 254   block->set_control(BasicBlock::kThrow);
 255   SetControlInput(block, input);
 256   if (block != end()) AddSuccessor(block, end());
 257 }
 258
 259
 260 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
 261                             BasicBlock* tblock, BasicBlock* fblock) {
 262   DCHECK_NE(BasicBlock::kNone, block->control());
 263   DCHECK_EQ(BasicBlock::kNone, end->control());
 264   end->set_control(block->control());
 265   block->set_control(BasicBlock::kBranch);
 266   MoveSuccessors(block, end);
 267   AddSuccessor(block, tblock);
 268   AddSuccessor(block, fblock);
 269   if (block->control_input() != nullptr) {
 270     SetControlInput(end, block->control_input());
 271   }
 272   SetControlInput(block, branch);
 273 }
 274
 275
 276 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
 277                             BasicBlock** succ_blocks, size_t succ_count) {
 278   DCHECK_NE(BasicBlock::kNone, block->control());
 279   DCHECK_EQ(BasicBlock::kNone, end->control());
 280   end->set_control(block->control());
 281   block->set_control(BasicBlock::kSwitch);
 282   MoveSuccessors(block, end);
 283   for (size_t index = 0; index < succ_count; ++index) {
 284     AddSuccessor(block, succ_blocks[index]);
 285   }
 286   if (block->control_input() != nullptr) {
 287     SetControlInput(end, block->control_input());
 288   }
 289   SetControlInput(block, sw);
 290 }
 291
 292
 293 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
 294   block->AddSuccessor(succ);
 295   succ->AddPredecessor(block);
 296 }
 297
 298
 299 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
 300   for (BasicBlock* const successor : from->successors()) {
 301     to->AddSuccessor(successor);
 302     for (BasicBlock*& predecessor : successor->predecessors()) {
 303       if (predecessor == from) predecessor = to;
 304     }
 305   }
 306   from->ClearSuccessors();
 307 }
 308
 309
 310 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
 311   block->set_control_input(node);
 312   SetBlockForNode(block, node);
 313 }
 314
 315
 316 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
 317   int length = static_cast<int>(nodeid_to_block_.size());
 318   if (node->id() >= length) {
 319     nodeid_to_block_.resize(node->id() + 1);
 320   }
 321   nodeid_to_block_[node->id()] = block;
 322 }
 323
 324
 325 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
 326   for (BasicBlock* block : *s.rpo_order()) {
 327     os << "--- BLOCK B" << block->rpo_number();
 328     if (block->deferred()) os << " (deferred)";
 329     if (block->PredecessorCount() != 0) os << " <- ";
 330     bool comma = false;
 331     for (BasicBlock const* predecessor : block->predecessors()) {
 332       if (comma) os << ", ";
 333       comma = true;
 334       os << "B" << predecessor->rpo_number();
 335     }
 336     os << " ---\n";
 337     for (Node* node : *block) {
 338       os << "  " << *node;
 339       if (NodeProperties::IsTyped(node)) {
 340         Bounds bounds = NodeProperties::GetBounds(node);
 341         os << " : ";
 342         bounds.lower->PrintTo(os);
 343         if (!bounds.upper->Is(bounds.lower)) {
 344           os << "..";
 345           bounds.upper->PrintTo(os);
 346         }
 347       }
 348       os << "\n";
 349     }
 350     BasicBlock::Control control = block->control();
 351     if (control != BasicBlock::kNone) {
 352       os << "  ";
 353       if (block->control_input() != NULL) {
 354         os << *block->control_input();
 355       } else {
 356         os << "Goto";
 357       }
 358       os << " -> ";
 359       comma = false;
 360       for (BasicBlock const* successor : block->successors()) {
 361         if (comma) os << ", ";
 362         comma = true;
 363         os << "B" << successor->rpo_number();
 364       }
 365       os << "\n";
 366     }
 367   }
 368   return os;
 369 }
 370
 371 }  // namespace compiler
 372 }  // namespace internal
 373 }  // namespace v8