Home | History | Annotate | Download | only in compiler 
      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_ == 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 
     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::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 
    123 std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
    124   return os << id.ToSize();
    125 }
    126 
    127 
    128 Schedule::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 
    139 BasicBlock* 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 
    147 bool 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 
    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 != nullptr && 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) == nullptr);
    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) == nullptr || 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_EQ(BasicBlock::kNone, block->control());
    198   block->set_control(BasicBlock::kGoto);
    199   AddSuccessor(block, succ);
    200 }
    201 
    202 #if DEBUG
    203 namespace {
    204 
    205 bool 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 
    220 void 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 
    231 void 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 
    242 void 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 
    254 void 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 
    262 void 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 
    270 void 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 
    278 void 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 
    286 void 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 
    302 void 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 
    318 void 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 
    336 void 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 
    363 void 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 
    399 void 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 
    423 void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
    424   block->AddSuccessor(succ);
    425   succ->AddPredecessor(block);
    426 }
    427 
    428 
    429 void 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 
    440 void Schedule::SetControlInput(BasicBlock* block, Node* node) {
    441   block->set_control_input(node);
    442   SetBlockForNode(block, node);
    443 }
    444 
    445 
    446 void 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 
    454 std::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