LCOV - code coverage report
Current view: top level - src/compiler - schedule.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 180 218 82.6 %
Date: 2017-04-26 Functions: 33 42 78.6 %

          Line data    Source code
       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     1311610 : 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             : #if DEBUG
      31             :       debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
      32             : #endif
      33    34829472 :       id_(id) {
      34     1311610 : }
      35             : 
      36        1438 : bool BasicBlock::LoopContains(BasicBlock* block) const {
      37             :   // RPO numbers must be initialized.
      38             :   DCHECK(rpo_number_ >= 0);
      39             :   DCHECK(block->rpo_number_ >= 0);
      40        1438 :   if (loop_end_ == nullptr) return false;  // This is not a loop.
      41        2876 :   return block->rpo_number_ >= rpo_number_ &&
      42        2876 :          block->rpo_number_ < loop_end_->rpo_number_;
      43             : }
      44             : 
      45             : 
      46           0 : void BasicBlock::AddSuccessor(BasicBlock* successor) {
      47    19474234 :   successors_.push_back(successor);
      48           0 : }
      49             : 
      50             : 
      51           0 : void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
      52    19177181 :   predecessors_.push_back(predecessor);
      53           0 : }
      54             : 
      55             : 
      56    95030052 : void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
      57             : 
      58             : 
      59           0 : void BasicBlock::set_control(Control control) {
      60    14781568 :   control_ = control;
      61           0 : }
      62             : 
      63             : 
      64           0 : void BasicBlock::set_control_input(Node* control_input) {
      65     7028155 :   control_input_ = control_input;
      66           0 : }
      67             : 
      68             : 
      69    16305869 : void BasicBlock::set_loop_depth(int32_t loop_depth) {
      70    16305869 :   loop_depth_ = loop_depth;
      71    16305869 : }
      72             : 
      73             : 
      74    78308450 : void BasicBlock::set_rpo_number(int32_t rpo_number) {
      75    78308450 :   rpo_number_ = rpo_number;
      76    78308450 : }
      77             : 
      78             : 
      79      147259 : void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
      80             : 
      81             : 
      82    16305827 : void BasicBlock::set_loop_header(BasicBlock* loop_header) {
      83    16305827 :   loop_header_ = loop_header;
      84    16305827 : }
      85             : 
      86             : 
      87             : // static
      88  1135100524 : BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
      89   755980430 :   while (b1 != b2) {
      90   561910340 :     if (b1->dominator_depth() < b2->dominator_depth()) {
      91             :       b2 = b2->dominator();
      92             :     } else {
      93             :       b1 = b1->dominator();
      94             :     }
      95             :   }
      96    97035045 :   return b1;
      97             : }
      98             : 
      99           0 : std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
     100           0 :   os << "B" << block.id();
     101             : #if DEBUG
     102             :   AssemblerDebugInfo info = block.debug_info();
     103             :   if (info.name) os << info;
     104             :   // Print predecessor blocks for better debugging.
     105             :   const int kMaxDisplayedBlocks = 4;
     106             :   int i = 0;
     107             :   const BasicBlock* current_block = &block;
     108             :   while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
     109             :     current_block = current_block->predecessors().front();
     110             :     os << " <= B" << current_block->id();
     111             :     info = current_block->debug_info();
     112             :     if (info.name) os << info;
     113             :   }
     114             : #endif
     115           0 :   return os;
     116             : }
     117             : 
     118           0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
     119           0 :   switch (c) {
     120             :     case BasicBlock::kNone:
     121           0 :       return os << "none";
     122             :     case BasicBlock::kGoto:
     123           0 :       return os << "goto";
     124             :     case BasicBlock::kCall:
     125           0 :       return os << "call";
     126             :     case BasicBlock::kBranch:
     127           0 :       return os << "branch";
     128             :     case BasicBlock::kSwitch:
     129           0 :       return os << "switch";
     130             :     case BasicBlock::kDeoptimize:
     131           0 :       return os << "deoptimize";
     132             :     case BasicBlock::kTailCall:
     133           0 :       return os << "tailcall";
     134             :     case BasicBlock::kReturn:
     135           0 :       return os << "return";
     136             :     case BasicBlock::kThrow:
     137           0 :       return os << "throw";
     138             :   }
     139           0 :   UNREACHABLE();
     140             :   return os;
     141             : }
     142             : 
     143             : 
     144           0 : std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
     145           0 :   return os << id.ToSize();
     146             : }
     147             : 
     148             : 
     149     1315747 : Schedule::Schedule(Zone* zone, size_t node_count_hint)
     150             :     : zone_(zone),
     151             :       all_blocks_(zone),
     152             :       nodeid_to_block_(zone),
     153             :       rpo_order_(zone),
     154     1315747 :       start_(NewBasicBlock()),
     155     2631464 :       end_(NewBasicBlock()) {
     156     1315744 :   nodeid_to_block_.reserve(node_count_hint);
     157     1315740 : }
     158             : 
     159             : 
     160   252951572 : BasicBlock* Schedule::block(Node* node) const {
     161   505903143 :   if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
     162   503013368 :     return nodeid_to_block_[node->id()];
     163             :   }
     164             :   return nullptr;
     165             : }
     166             : 
     167             : 
     168   314911892 : bool Schedule::IsScheduled(Node* node) {
     169   629823784 :   if (node->id() >= nodeid_to_block_.size()) return false;
     170   303696076 :   return nodeid_to_block_[node->id()] != nullptr;
     171             : }
     172             : 
     173             : 
     174    12870449 : BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
     175             :   DCHECK(block_id.ToSize() < all_blocks_.size());
     176    25740898 :   return all_blocks_[block_id.ToSize()];
     177             : }
     178             : 
     179             : 
     180           1 : bool Schedule::SameBasicBlock(Node* a, Node* b) const {
     181             :   BasicBlock* block = this->block(a);
     182           2 :   return block != nullptr && block == this->block(b);
     183             : }
     184             : 
     185             : 
     186    16103140 : BasicBlock* Schedule::NewBasicBlock() {
     187             :   BasicBlock* block = new (zone_)
     188    64412532 :       BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
     189    16103126 :   all_blocks_.push_back(block);
     190    16103396 :   return block;
     191             : }
     192             : 
     193             : 
     194    60270419 : void Schedule::PlanNode(BasicBlock* block, Node* node) {
     195    60270419 :   if (FLAG_trace_turbo_scheduler) {
     196           0 :     OFStream os(stdout);
     197           0 :     os << "Planning #" << node->id() << ":" << node->op()->mnemonic()
     198           0 :        << " for future add to B" << block->id() << "\n";
     199             :   }
     200             :   DCHECK(this->block(node) == nullptr);
     201    60270419 :   SetBlockForNode(block, node);
     202    60270893 : }
     203             : 
     204             : 
     205    95030052 : void Schedule::AddNode(BasicBlock* block, Node* node) {
     206    95030052 :   if (FLAG_trace_turbo_scheduler) {
     207           0 :     OFStream os(stdout);
     208           0 :     os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B"
     209           0 :        << block->id() << "\n";
     210             :   }
     211             :   DCHECK(this->block(node) == nullptr || this->block(node) == block);
     212             :   block->AddNode(node);
     213    95028801 :   SetBlockForNode(block, node);
     214    95029469 : }
     215             : 
     216             : 
     217     7214215 : void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
     218             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     219             :   block->set_control(BasicBlock::kGoto);
     220     7214215 :   AddSuccessor(block, succ);
     221     7214213 : }
     222             : 
     223             : #if DEBUG
     224             : namespace {
     225             : 
     226             : bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
     227             :   switch (opcode) {
     228             : #define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
     229             :     JS_OP_LIST(BUILD_BLOCK_JS_CASE)
     230             : #undef BUILD_BLOCK_JS_CASE
     231             :     case IrOpcode::kCall:
     232             :       return true;
     233             :     default:
     234             :       return false;
     235             :   }
     236             : }
     237             : 
     238             : }  // namespace
     239             : #endif  // DEBUG
     240             : 
     241      463906 : void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
     242             :                        BasicBlock* exception_block) {
     243             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     244             :   DCHECK(IsPotentiallyThrowingCall(call->opcode()));
     245             :   block->set_control(BasicBlock::kCall);
     246      463906 :   AddSuccessor(block, success_block);
     247      463906 :   AddSuccessor(block, exception_block);
     248             :   SetControlInput(block, call);
     249      463906 : }
     250             : 
     251             : 
     252     4282121 : void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
     253             :                          BasicBlock* fblock) {
     254             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     255             :   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
     256             :   block->set_control(BasicBlock::kBranch);
     257     4282121 :   AddSuccessor(block, tblock);
     258     4282150 :   AddSuccessor(block, fblock);
     259             :   SetControlInput(block, branch);
     260     4282187 : }
     261             : 
     262             : 
     263       23140 : void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
     264             :                          size_t succ_count) {
     265             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     266             :   DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
     267             :   block->set_control(BasicBlock::kSwitch);
     268      191444 :   for (size_t index = 0; index < succ_count; ++index) {
     269      168304 :     AddSuccessor(block, succ_blocks[index]);
     270             :   }
     271             :   SetControlInput(block, sw);
     272       23140 : }
     273             : 
     274             : 
     275      298454 : void Schedule::AddTailCall(BasicBlock* block, Node* input) {
     276             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     277             :   block->set_control(BasicBlock::kTailCall);
     278             :   SetControlInput(block, input);
     279      149227 :   if (block != end()) AddSuccessor(block, end());
     280      149227 : }
     281             : 
     282             : 
     283     3239916 : void Schedule::AddReturn(BasicBlock* block, Node* input) {
     284             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     285             :   block->set_control(BasicBlock::kReturn);
     286             :   SetControlInput(block, input);
     287     1619972 :   if (block != end()) AddSuccessor(block, end());
     288     1619952 : }
     289             : 
     290             : 
     291       60260 : void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
     292             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     293             :   block->set_control(BasicBlock::kDeoptimize);
     294             :   SetControlInput(block, input);
     295       30130 :   if (block != end()) AddSuccessor(block, end());
     296       30130 : }
     297             : 
     298             : 
     299      142280 : void Schedule::AddThrow(BasicBlock* block, Node* input) {
     300             :   DCHECK_EQ(BasicBlock::kNone, block->control());
     301             :   block->set_control(BasicBlock::kThrow);
     302             :   SetControlInput(block, input);
     303       71140 :   if (block != end()) AddSuccessor(block, end());
     304       71140 : }
     305             : 
     306             : 
     307      430059 : void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
     308             :                             BasicBlock* tblock, BasicBlock* fblock) {
     309             :   DCHECK_NE(BasicBlock::kNone, block->control());
     310             :   DCHECK_EQ(BasicBlock::kNone, end->control());
     311             :   end->set_control(block->control());
     312             :   block->set_control(BasicBlock::kBranch);
     313      215029 :   MoveSuccessors(block, end);
     314      215032 :   AddSuccessor(block, tblock);
     315      215030 :   AddSuccessor(block, fblock);
     316      215030 :   if (block->control_input() != nullptr) {
     317             :     SetControlInput(end, block->control_input());
     318             :   }
     319             :   SetControlInput(block, branch);
     320      215027 : }
     321             : 
     322             : 
     323           2 : void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
     324             :                             BasicBlock** succ_blocks, size_t succ_count) {
     325             :   DCHECK_NE(BasicBlock::kNone, block->control());
     326             :   DCHECK_EQ(BasicBlock::kNone, end->control());
     327             :   end->set_control(block->control());
     328             :   block->set_control(BasicBlock::kSwitch);
     329           1 :   MoveSuccessors(block, end);
     330           4 :   for (size_t index = 0; index < succ_count; ++index) {
     331           3 :     AddSuccessor(block, succ_blocks[index]);
     332             :   }
     333           1 :   if (block->control_input() != nullptr) {
     334             :     SetControlInput(end, block->control_input());
     335             :   }
     336             :   SetControlInput(block, sw);
     337           1 : }
     338             : 
     339      347839 : void Schedule::EnsureCFGWellFormedness() {
     340             :   // Make a copy of all the blocks for the iteration, since adding the split
     341             :   // edges will allocate new blocks.
     342             :   BasicBlockVector all_blocks_copy(all_blocks_);
     343             : 
     344             :   // Insert missing split edge blocks.
     345     3760511 :   for (auto block : all_blocks_copy) {
     346     2510293 :     if (block->PredecessorCount() > 1) {
     347      554538 :       if (block != end_) {
     348      490632 :         EnsureSplitEdgeForm(block);
     349             :       }
     350      554539 :       if (block->deferred()) {
     351       15681 :         EnsureDeferredCodeSingleEntryPoint(block);
     352             :       }
     353             :     }
     354             :   }
     355      347840 : }
     356             : 
     357      490632 : void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
     358             :   DCHECK(block->PredecessorCount() > 1 && block != end_);
     359     3564912 :   for (auto current_pred = block->predecessors().begin();
     360     1873341 :        current_pred != block->predecessors().end(); ++current_pred) {
     361     1382709 :     BasicBlock* pred = *current_pred;
     362     1382709 :     if (pred->SuccessorCount() > 1) {
     363             :       // Found a predecessor block with multiple successors.
     364      710307 :       BasicBlock* split_edge_block = NewBasicBlock();
     365             :       split_edge_block->set_control(BasicBlock::kGoto);
     366      710307 :       split_edge_block->successors().push_back(block);
     367      710307 :       split_edge_block->predecessors().push_back(pred);
     368      710307 :       split_edge_block->set_deferred(block->deferred());
     369      710307 :       *current_pred = split_edge_block;
     370             :       // Find a corresponding successor in the previous block, replace it
     371             :       // with the split edge block... but only do it once, since we only
     372             :       // replace the previous blocks in the current block one at a time.
     373     2481930 :       for (auto successor = pred->successors().begin();
     374             :            successor != pred->successors().end(); ++successor) {
     375     1061316 :         if (*successor == block) {
     376      710307 :           *successor = split_edge_block;
     377      710307 :           break;
     378             :         }
     379             :       }
     380             :     }
     381             :   }
     382      490632 : }
     383             : 
     384       15681 : void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
     385             :   // If a deferred block has multiple predecessors, they have to
     386             :   // all be deferred. Otherwise, we can run into a situation where a range
     387             :   // that spills only in deferred blocks inserts its spill in the block, but
     388             :   // other ranges need moves inserted by ResolveControlFlow in the predecessors,
     389             :   // which may clobber the register of this range.
     390             :   // To ensure that, when a deferred block has multiple predecessors, and some
     391             :   // are not deferred, we add a non-deferred block to collect all such edges.
     392             : 
     393             :   DCHECK(block->deferred() && block->PredecessorCount() > 1);
     394             :   bool all_deferred = true;
     395      105938 :   for (auto current_pred = block->predecessors().begin();
     396             :        current_pred != block->predecessors().end(); ++current_pred) {
     397       61303 :     BasicBlock* pred = *current_pred;
     398       61303 :     if (!pred->deferred()) {
     399             :       all_deferred = false;
     400             :       break;
     401             :     }
     402             :   }
     403             : 
     404       28954 :   if (all_deferred) return;
     405        2408 :   BasicBlock* merger = NewBasicBlock();
     406             :   merger->set_control(BasicBlock::kGoto);
     407        2408 :   merger->successors().push_back(block);
     408       34099 :   for (auto current_pred = block->predecessors().begin();
     409       29283 :        current_pred != block->predecessors().end(); ++current_pred) {
     410       26875 :     BasicBlock* pred = *current_pred;
     411       26875 :     merger->predecessors().push_back(pred);
     412       26875 :     pred->successors().clear();
     413       26875 :     pred->successors().push_back(merger);
     414             :   }
     415        2408 :   merger->set_deferred(false);
     416             :   block->predecessors().clear();
     417        2408 :   block->predecessors().push_back(merger);
     418             : }
     419             : 
     420      347840 : void Schedule::PropagateDeferredMark() {
     421             :   // Push forward the deferred block marks through newly inserted blocks and
     422             :   // other improperly marked blocks until a fixed point is reached.
     423             :   // TODO(danno): optimize the propagation
     424             :   bool done = false;
     425     1094823 :   while (!done) {
     426             :     done = true;
     427    14046739 :     for (auto block : all_blocks_) {
     428     7157919 :       if (!block->deferred()) {
     429     5309672 :         bool deferred = block->PredecessorCount() > 0;
     430    23731223 :         for (auto pred : block->predecessors()) {
     431    13111879 :           if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
     432             :             deferred = false;
     433             :           }
     434             :         }
     435     5309672 :         if (deferred) {
     436             :           block->set_deferred(true);
     437             :           done = false;
     438             :         }
     439             :       }
     440             :     }
     441             :   }
     442      347840 : }
     443             : 
     444    19177141 : void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
     445             :   block->AddSuccessor(succ);
     446             :   succ->AddPredecessor(block);
     447    19177174 : }
     448             : 
     449             : 
     450      215031 : void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
     451      727157 :   for (BasicBlock* const successor : from->successors()) {
     452             :     to->AddSuccessor(successor);
     453     1665777 :     for (BasicBlock*& predecessor : successor->predecessors()) {
     454     1071587 :       if (predecessor == from) predecessor = to;
     455             :     }
     456             :   }
     457             :   from->ClearSuccessors();
     458      215033 : }
     459             : 
     460             : 
     461           0 : void Schedule::SetControlInput(BasicBlock* block, Node* node) {
     462             :   block->set_control_input(node);
     463     7028155 :   SetBlockForNode(block, node);
     464           0 : }
     465             : 
     466             : 
     467   331015683 : void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
     468   496523493 :   if (node->id() >= nodeid_to_block_.size()) {
     469    24111110 :     nodeid_to_block_.resize(node->id() + 1);
     470             :   }
     471   331015746 :   nodeid_to_block_[node->id()] = block;
     472   165507873 : }
     473             : 
     474             : 
     475          14 : std::ostream& operator<<(std::ostream& os, const Schedule& s) {
     476         364 :   for (BasicBlock* block :
     477          84 :        ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
     478          70 :     if (block->rpo_number() == -1) {
     479           0 :       os << "--- BLOCK id:" << block->id().ToInt();
     480             :     } else {
     481          70 :       os << "--- BLOCK B" << block->rpo_number();
     482             :     }
     483          70 :     if (block->deferred()) os << " (deferred)";
     484          70 :     if (block->PredecessorCount() != 0) os << " <- ";
     485             :     bool comma = false;
     486         280 :     for (BasicBlock const* predecessor : block->predecessors()) {
     487          70 :       if (comma) os << ", ";
     488             :       comma = true;
     489          70 :       if (predecessor->rpo_number() == -1) {
     490           0 :         os << "id:" << predecessor->id().ToInt();
     491             :       } else {
     492          70 :         os << "B" << predecessor->rpo_number();
     493             :       }
     494             :     }
     495          70 :     os << " ---\n";
     496         196 :     for (Node* node : *block) {
     497          56 :       os << "  " << *node;
     498          56 :       if (NodeProperties::IsTyped(node)) {
     499             :         Type* type = NodeProperties::GetType(node);
     500           0 :         os << " : ";
     501           0 :         type->PrintTo(os);
     502             :       }
     503          56 :       os << "\n";
     504             :     }
     505             :     BasicBlock::Control control = block->control();
     506          70 :     if (control != BasicBlock::kNone) {
     507          56 :       os << "  ";
     508          56 :       if (block->control_input() != nullptr) {
     509          28 :         os << *block->control_input();
     510             :       } else {
     511          28 :         os << "Goto";
     512             :       }
     513          56 :       os << " -> ";
     514             :       comma = false;
     515         252 :       for (BasicBlock const* successor : block->successors()) {
     516          70 :         if (comma) os << ", ";
     517             :         comma = true;
     518          70 :         if (successor->rpo_number() == -1) {
     519           0 :           os << "id:" << successor->id().ToInt();
     520             :         } else {
     521          70 :           os << "B" << successor->rpo_number();
     522             :         }
     523             :       }
     524          56 :       os << "\n";
     525             :     }
     526             :   }
     527          14 :   return os;
     528             : }
     529             : 
     530             : }  // namespace compiler
     531             : }  // namespace internal
     532             : }  // namespace v8

Generated by: LCOV version 1.10