src/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/node.h"
   6 #include "src/compiler/node-properties.h"
   7 #include "src/compiler/node-properties-inl.h"
   8 #include "src/compiler/schedule.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     : ao_number_(-1),
  17       rpo_number_(-1),
  18       deferred_(false),
  19       dominator_(NULL),
  20       loop_header_(NULL),
  21       loop_depth_(0),
  22       loop_end_(-1),
  23       control_(kNone),
  24       control_input_(NULL),
  25       nodes_(zone),
  26       successors_(zone),
  27       predecessors_(zone),
  28       id_(id) {}
  29
  30
  31 bool BasicBlock::LoopContains(BasicBlock* block) const {
  32   // RPO numbers must be initialized.
  33   DCHECK(rpo_number_ >= 0);
  34   DCHECK(block->rpo_number_ >= 0);
  35   if (loop_end_ < 0) return false;  // This is not a loop.
  36   return block->rpo_number_ >= rpo_number_ && block->rpo_number_ < loop_end_;
  37 }
  38
  39
  40 void BasicBlock::AddSuccessor(BasicBlock* successor) {
  41   successors_.push_back(successor);
  42 }
  43
  44
  45 void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
  46   predecessors_.push_back(predecessor);
  47 }
  48
  49
  50 void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
  51
  52
  53 void BasicBlock::set_control(Control control) {
  54   control_ = control;
  55 }
  56
  57
  58 void BasicBlock::set_control_input(Node* control_input) {
  59   control_input_ = control_input;
  60 }
  61
  62
  63 void BasicBlock::set_dominator(BasicBlock* dominator) {
  64   dominator_ = dominator;
  65 }
  66
  67
  68 void BasicBlock::set_loop_depth(int32_t loop_depth) {
  69   loop_depth_ = loop_depth;
  70 }
  71
  72
  73 void BasicBlock::set_rpo_number(int32_t rpo_number) {
  74   rpo_number_ = rpo_number;
  75 }
  76
  77
  78 void BasicBlock::set_loop_end(int32_t loop_end) { loop_end_ = loop_end; }
  79
  80
  81 void BasicBlock::set_loop_header(BasicBlock* loop_header) {
  82   loop_header_ = loop_header;
  83 }
  84
  85
  86 std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
  87   switch (c) {
  88     case BasicBlock::kNone:
  89       return os << "none";
  90     case BasicBlock::kGoto:
  91       return os << "goto";
  92     case BasicBlock::kBranch:
  93       return os << "branch";
  94     case BasicBlock::kReturn:
  95       return os << "return";
  96     case BasicBlock::kThrow:
  97       return os << "throw";
  98   }
  99   UNREACHABLE();
 100   return os;
 101 }
 102
 103
 104 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
 105   return os << id.ToSize();
 106 }
 107
 108
 109 std::ostream& operator<<(std::ostream& os, const BasicBlock::RpoNumber& rpo) {
 110   return os << rpo.ToSize();
 111 }
 112
 113
 114 Schedule::Schedule(Zone* zone, size_t node_count_hint)
 115     : zone_(zone),
 116       all_blocks_(zone),
 117       nodeid_to_block_(zone),
 118       rpo_order_(zone),
 119       start_(NewBasicBlock()),
 120       end_(NewBasicBlock()) {
 121   nodeid_to_block_.reserve(node_count_hint);
 122 }
 123
 124
 125 BasicBlock* Schedule::block(Node* node) const {
 126   if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
 127     return nodeid_to_block_[node->id()];
 128   }
 129   return NULL;
 130 }
 131
 132
 133 bool Schedule::IsScheduled(Node* node) {
 134   int length = static_cast<int>(nodeid_to_block_.size());
 135   if (node->id() >= length) return false;
 136   return nodeid_to_block_[node->id()] != NULL;
 137 }
 138
 139
 140 BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
 141   DCHECK(block_id.ToSize() < all_blocks_.size());
 142   return all_blocks_[block_id.ToSize()];
 143 }
 144
 145
 146 bool Schedule::SameBasicBlock(Node* a, Node* b) const {
 147   BasicBlock* block = this->block(a);
 148   return block != NULL && block == this->block(b);
 149 }
 150
 151
 152 BasicBlock* Schedule::NewBasicBlock() {
 153   BasicBlock* block = new (zone_)
 154       BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
 155   all_blocks_.push_back(block);
 156   return block;
 157 }
 158
 159
 160 void Schedule::PlanNode(BasicBlock* block, Node* node) {
 161   if (FLAG_trace_turbo_scheduler) {
 162     OFStream os(stdout);
 163     os << "Planning #" << node->id() << ":" << node->op()->mnemonic()
 164        << " for future add to B" << block->id() << "\n";
 165   }
 166   DCHECK(this->block(node) == NULL);
 167   SetBlockForNode(block, node);
 168 }
 169
 170
 171 void Schedule::AddNode(BasicBlock* block, Node* node) {
 172   if (FLAG_trace_turbo_scheduler) {
 173     OFStream os(stdout);
 174     os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B"
 175        << block->id() << "\n";
 176   }
 177   DCHECK(this->block(node) == NULL || this->block(node) == block);
 178   block->AddNode(node);
 179   SetBlockForNode(block, node);
 180 }
 181
 182
 183 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
 184   DCHECK(block->control() == BasicBlock::kNone);
 185   block->set_control(BasicBlock::kGoto);
 186   AddSuccessor(block, succ);
 187 }
 188
 189
 190 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
 191                          BasicBlock* fblock) {
 192   DCHECK(block->control() == BasicBlock::kNone);
 193   DCHECK(branch->opcode() == IrOpcode::kBranch);
 194   block->set_control(BasicBlock::kBranch);
 195   AddSuccessor(block, tblock);
 196   AddSuccessor(block, fblock);
 197   SetControlInput(block, branch);
 198 }
 199
 200
 201 void Schedule::AddReturn(BasicBlock* block, Node* input) {
 202   DCHECK(block->control() == BasicBlock::kNone);
 203   block->set_control(BasicBlock::kReturn);
 204   SetControlInput(block, input);
 205   if (block != end()) AddSuccessor(block, end());
 206 }
 207
 208
 209 void Schedule::AddThrow(BasicBlock* block, Node* input) {
 210   DCHECK(block->control() == BasicBlock::kNone);
 211   block->set_control(BasicBlock::kThrow);
 212   SetControlInput(block, input);
 213   if (block != end()) AddSuccessor(block, end());
 214 }
 215
 216
 217 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
 218                             BasicBlock* tblock, BasicBlock* fblock) {
 219   DCHECK(block->control() != BasicBlock::kNone);
 220   DCHECK(end->control() == BasicBlock::kNone);
 221   end->set_control(block->control());
 222   block->set_control(BasicBlock::kBranch);
 223   MoveSuccessors(block, end);
 224   AddSuccessor(block, tblock);
 225   AddSuccessor(block, fblock);
 226   if (block->control_input() != NULL) {
 227     SetControlInput(end, block->control_input());
 228   }
 229   SetControlInput(block, branch);
 230 }
 231
 232
 233 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
 234   block->AddSuccessor(succ);
 235   succ->AddPredecessor(block);
 236 }
 237
 238
 239 void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
 240   for (BasicBlock::Predecessors::iterator i = from->successors_begin();
 241        i != from->successors_end(); ++i) {
 242     BasicBlock* succ = *i;
 243     to->AddSuccessor(succ);
 244     for (BasicBlock::Predecessors::iterator j = succ->predecessors_begin();
 245          j != succ->predecessors_end(); ++j) {
 246       if (*j == from) *j = to;
 247     }
 248   }
 249   from->ClearSuccessors();
 250 }
 251
 252
 253 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
 254   block->set_control_input(node);
 255   SetBlockForNode(block, node);
 256 }
 257
 258
 259 void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
 260   int length = static_cast<int>(nodeid_to_block_.size());
 261   if (node->id() >= length) {
 262     nodeid_to_block_.resize(node->id() + 1);
 263   }
 264   nodeid_to_block_[node->id()] = block;
 265 }
 266
 267
 268 std::ostream& operator<<(std::ostream& os, const Schedule& s) {
 269   // TODO(svenpanne) Const-correct the RPO stuff/iterators.
 270   BasicBlockVector* rpo = const_cast<Schedule*>(&s)->rpo_order();
 271   for (BasicBlockVectorIter i = rpo->begin(); i != rpo->end(); ++i) {
 272     BasicBlock* block = *i;
 273     os << "--- BLOCK B" << block->id();
 274     if (block->deferred()) os << " (deferred)";
 275     if (block->PredecessorCount() != 0) os << " <- ";
 276     bool comma = false;
 277     for (BasicBlock::Predecessors::iterator j = block->predecessors_begin();
 278          j != block->predecessors_end(); ++j) {
 279       if (comma) os << ", ";
 280       comma = true;
 281       os << "B" << (*j)->id();
 282     }
 283     os << " ---\n";
 284     for (BasicBlock::const_iterator j = block->begin(); j != block->end();
 285          ++j) {
 286       Node* node = *j;
 287       os << "  " << *node;
 288       if (NodeProperties::IsTyped(node)) {
 289         Bounds bounds = NodeProperties::GetBounds(node);
 290         os << " : ";
 291         bounds.lower->PrintTo(os);
 292         if (!bounds.upper->Is(bounds.lower)) {
 293           os << "..";
 294           bounds.upper->PrintTo(os);
 295         }
 296       }
 297       os << "\n";
 298     }
 299     BasicBlock::Control control = block->control();
 300     if (control != BasicBlock::kNone) {
 301       os << "  ";
 302       if (block->control_input() != NULL) {
 303         os << *block->control_input();
 304       } else {
 305         os << "Goto";
 306       }
 307       os << " -> ";
 308       comma = false;
 309       for (BasicBlock::Successors::iterator j = block->successors_begin();
 310            j != block->successors_end(); ++j) {
 311         if (comma) os << ", ";
 312         comma = true;
 313         os << "B" << (*j)->id();
 314       }
 315       os << "\n";
 316     }
 317   }
 318   return os;
 319 }
 320
 321 }  // namespace compiler
 322 }  // namespace internal
 323 }  // namespace v8