1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/schedule.h" 6014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/node.h" 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/compiler/node-properties.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/ostreams.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 15958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierBasicBlock::BasicBlock(Zone* zone, Id id) 16958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : loop_number_(-1), 17958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier rpo_number_(-1), 18958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier deferred_(false), 19958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier dominator_depth_(-1), 20014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch dominator_(nullptr), 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch rpo_next_(nullptr), 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch loop_header_(nullptr), 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch loop_end_(nullptr), 24958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier loop_depth_(0), 25958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier control_(kNone), 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch control_input_(nullptr), 27958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodes_(zone), 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier successors_(zone), 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier predecessors_(zone), 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier id_(id) {} 31958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 32958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 33958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierbool BasicBlock::LoopContains(BasicBlock* block) const { 34958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // RPO numbers must be initialized. 35958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK(rpo_number_ >= 0); 36958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK(block->rpo_number_ >= 0); 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (loop_end_ == nullptr) return false; // This is not a loop. 38958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return block->rpo_number_ >= rpo_number_ && 39958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->rpo_number_ < loop_end_->rpo_number_; 40958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 41958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 42958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 43958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::AddSuccessor(BasicBlock* successor) { 44958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier successors_.push_back(successor); 45958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 46958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::AddPredecessor(BasicBlock* predecessor) { 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier predecessors_.push_back(predecessor); 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::AddNode(Node* node) { nodes_.push_back(node); } 54958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 56958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_control(Control control) { 57958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier control_ = control; 58958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 59958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 60958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 61958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_control_input(Node* control_input) { 62958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier control_input_ = control_input; 63958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 64958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 65958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 66958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_loop_depth(int32_t loop_depth) { 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier loop_depth_ = loop_depth; 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 69958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 70958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 71958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_rpo_number(int32_t rpo_number) { 72958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier rpo_number_ = rpo_number; 73958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 74958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 75958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 76958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; } 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 78958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 79958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid BasicBlock::set_loop_header(BasicBlock* loop_header) { 80958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier loop_header_ = loop_header; 81958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 82958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 83958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// static 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochBasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch while (b1 != b2) { 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (b1->dominator_depth() < b2->dominator_depth()) { 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch b2 = b2->dominator(); 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else { 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch b1 = b1->dominator(); 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 92014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 93014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return b1; 94014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 96014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 97958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierstd::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) { 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch switch (c) { 99958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier case BasicBlock::kNone: 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os << "none"; 101958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier case BasicBlock::kGoto: 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os << "goto"; 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch case BasicBlock::kCall: 104014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return os << "call"; 105958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier case BasicBlock::kBranch: 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os << "branch"; 107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch case BasicBlock::kSwitch: 108014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return os << "switch"; 109014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch case BasicBlock::kDeoptimize: 110014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return os << "deoptimize"; 111014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch case BasicBlock::kTailCall: 112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return os << "tailcall"; 113958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier case BasicBlock::kReturn: 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os << "return"; 115958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier case BasicBlock::kThrow: 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os << "throw"; 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UNREACHABLE(); 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os; 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 123958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierstd::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) { 124958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return os << id.ToSize(); 125958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 126958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 127958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 128958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierSchedule::Schedule(Zone* zone, size_t node_count_hint) 129958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier : zone_(zone), 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier all_blocks_(zone), 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodeid_to_block_(zone), 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier rpo_order_(zone), 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier start_(NewBasicBlock()), 134958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier end_(NewBasicBlock()) { 135958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodeid_to_block_.reserve(node_count_hint); 136958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 139958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierBasicBlock* Schedule::block(Node* node) const { 140958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { 141958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return nodeid_to_block_[node->id()]; 142958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 143014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return nullptr; 144958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 145958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 146958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 147958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierbool Schedule::IsScheduled(Node* node) { 148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (node->id() >= nodeid_to_block_.size()) return false; 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return nodeid_to_block_[node->id()] != nullptr; 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 151958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 152958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 153958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierBasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) { 154958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DCHECK(block_id.ToSize() < all_blocks_.size()); 155958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return all_blocks_[block_id.ToSize()]; 156958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 157958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 158958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 159958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierbool Schedule::SameBasicBlock(Node* a, Node* b) const { 160958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* block = this->block(a); 161014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return block != nullptr && block == this->block(b); 162958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 163958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 164958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 165958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily BernierBasicBlock* Schedule::NewBasicBlock() { 166958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* block = new (zone_) 167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size())); 168958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier all_blocks_.push_back(block); 169958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return block; 170958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 171958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 172958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 173958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::PlanNode(BasicBlock* block, Node* node) { 174958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (FLAG_trace_turbo_scheduler) { 175958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier OFStream os(stdout); 176958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier os << "Planning #" << node->id() << ":" << node->op()->mnemonic() 177958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << " for future add to B" << block->id() << "\n"; 178958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 179014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(this->block(node) == nullptr); 180958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetBlockForNode(block, node); 181958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 182958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 183958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 184958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddNode(BasicBlock* block, Node* node) { 185958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (FLAG_trace_turbo_scheduler) { 186958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier OFStream os(stdout); 187958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier os << "Adding #" << node->id() << ":" << node->op()->mnemonic() << " to B" 188958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier << block->id() << "\n"; 189958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 190014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(this->block(node) == nullptr || this->block(node) == block); 191958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->AddNode(node); 192958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetBlockForNode(block, node); 193958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 194958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 195958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 196958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) { 197014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 198958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control(BasicBlock::kGoto); 199958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier AddSuccessor(block, succ); 200958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 201958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 202bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#if DEBUG 203bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochnamespace { 204bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 205bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochbool IsPotentiallyThrowingCall(IrOpcode::Value opcode) { 206bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch switch (opcode) { 207bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name: 208bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch JS_OP_LIST(BUILD_BLOCK_JS_CASE) 209bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#undef BUILD_BLOCK_JS_CASE 210bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch case IrOpcode::kCall: 211bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return true; 212bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch default: 213bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch return false; 214bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 215bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} 216bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 217bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} // namespace 218bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch#endif // DEBUG 219958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 220014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 221014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock* exception_block) { 222014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 223bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DCHECK(IsPotentiallyThrowingCall(call->opcode())); 224014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->set_control(BasicBlock::kCall); 225014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch AddSuccessor(block, success_block); 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch AddSuccessor(block, exception_block); 227014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(block, call); 228014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 229014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 230014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 231958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 232958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* fblock) { 233014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 234014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(IrOpcode::kBranch, branch->opcode()); 235958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control(BasicBlock::kBranch); 236958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier AddSuccessor(block, tblock); 237958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier AddSuccessor(block, fblock); 238958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetControlInput(block, branch); 239958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 240958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 241958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 242014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 243014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t succ_count) { 244014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 245014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(IrOpcode::kSwitch, sw->opcode()); 246014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->set_control(BasicBlock::kSwitch); 247014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (size_t index = 0; index < succ_count; ++index) { 248014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch AddSuccessor(block, succ_blocks[index]); 249014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 250014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(block, sw); 251014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 252014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 253014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 254014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid Schedule::AddTailCall(BasicBlock* block, Node* input) { 255014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 256014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->set_control(BasicBlock::kTailCall); 257014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(block, input); 258014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block != end()) AddSuccessor(block, end()); 259014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 260014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 261014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 262958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddReturn(BasicBlock* block, Node* input) { 263014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 264958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control(BasicBlock::kReturn); 265958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetControlInput(block, input); 266958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (block != end()) AddSuccessor(block, end()); 267958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 268958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 269958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 270014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid Schedule::AddDeoptimize(BasicBlock* block, Node* input) { 271014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 272014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->set_control(BasicBlock::kDeoptimize); 273014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(block, input); 274014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block != end()) AddSuccessor(block, end()); 275014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 276014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 277014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 278958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddThrow(BasicBlock* block, Node* input) { 279014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, block->control()); 280958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control(BasicBlock::kThrow); 281958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetControlInput(block, input); 282958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (block != end()) AddSuccessor(block, end()); 283958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 284958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 285958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 286958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 287958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* tblock, BasicBlock* fblock) { 288014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NE(BasicBlock::kNone, block->control()); 289014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, end->control()); 290958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier end->set_control(block->control()); 291958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control(BasicBlock::kBranch); 292958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier MoveSuccessors(block, end); 293958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier AddSuccessor(block, tblock); 294958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier AddSuccessor(block, fblock); 295014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->control_input() != nullptr) { 296958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetControlInput(end, block->control_input()); 297958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 298958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetControlInput(block, branch); 299958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 300958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 301958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 302014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 303014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock** succ_blocks, size_t succ_count) { 304014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NE(BasicBlock::kNone, block->control()); 305014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(BasicBlock::kNone, end->control()); 306014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch end->set_control(block->control()); 307014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->set_control(BasicBlock::kSwitch); 308014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MoveSuccessors(block, end); 309014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (size_t index = 0; index < succ_count; ++index) { 310014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch AddSuccessor(block, succ_blocks[index]); 311014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 312014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->control_input() != nullptr) { 313014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(end, block->control_input()); 314014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 315014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch SetControlInput(block, sw); 316014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 317014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 318bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochvoid Schedule::EnsureCFGWellFormedness() { 3193b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Make a copy of all the blocks for the iteration, since adding the split 3203b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // edges will allocate new blocks. 3213b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch BasicBlockVector all_blocks_copy(all_blocks_); 3223b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 3233b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Insert missing split edge blocks. 3243b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (auto block : all_blocks_copy) { 325bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (block->PredecessorCount() > 1) { 326bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (block != end_) { 327bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch EnsureSplitEdgeForm(block); 328bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 329bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (block->deferred()) { 330bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch EnsureDeferredCodeSingleEntryPoint(block); 331bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 332bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 333bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 334bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} 335bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 336bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochvoid Schedule::EnsureSplitEdgeForm(BasicBlock* block) { 337bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DCHECK(block->PredecessorCount() > 1 && block != end_); 338bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch for (auto current_pred = block->predecessors().begin(); 339bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch current_pred != block->predecessors().end(); ++current_pred) { 340bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BasicBlock* pred = *current_pred; 341bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (pred->SuccessorCount() > 1) { 342bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // Found a predecessor block with multiple successors. 343bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BasicBlock* split_edge_block = NewBasicBlock(); 344bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch split_edge_block->set_control(BasicBlock::kGoto); 345bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch split_edge_block->successors().push_back(block); 346bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch split_edge_block->predecessors().push_back(pred); 347c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch split_edge_block->set_deferred(block->deferred()); 348bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch *current_pred = split_edge_block; 349bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // Find a corresponding successor in the previous block, replace it 350bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // with the split edge block... but only do it once, since we only 351bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // replace the previous blocks in the current block one at a time. 352bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch for (auto successor = pred->successors().begin(); 353bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch successor != pred->successors().end(); ++successor) { 354bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (*successor == block) { 355bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch *successor = split_edge_block; 356bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch break; 3573b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 3583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 3593b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 3603b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 3613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 3623b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 363bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdochvoid Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) { 364bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // If a deferred block has multiple predecessors, they have to 365bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // all be deferred. Otherwise, we can run into a situation where a range 366bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // that spills only in deferred blocks inserts its spill in the block, but 367bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // other ranges need moves inserted by ResolveControlFlow in the predecessors, 368bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // which may clobber the register of this range. 369bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // To ensure that, when a deferred block has multiple predecessors, and some 370bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // are not deferred, we add a non-deferred block to collect all such edges. 371bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 372bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch DCHECK(block->deferred() && block->PredecessorCount() > 1); 373bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch bool all_deferred = true; 374bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch for (auto current_pred = block->predecessors().begin(); 375bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch current_pred != block->predecessors().end(); ++current_pred) { 376bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BasicBlock* pred = *current_pred; 377bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (!pred->deferred()) { 378bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch all_deferred = false; 379bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch break; 380bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 381bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 382bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 383bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch if (all_deferred) return; 384bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BasicBlock* merger = NewBasicBlock(); 385bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch merger->set_control(BasicBlock::kGoto); 386bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch merger->successors().push_back(block); 387bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch for (auto current_pred = block->predecessors().begin(); 388bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch current_pred != block->predecessors().end(); ++current_pred) { 389bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch BasicBlock* pred = *current_pred; 390bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch merger->predecessors().push_back(pred); 391bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch pred->successors().clear(); 392bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch pred->successors().push_back(merger); 393bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch } 394bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch merger->set_deferred(false); 395bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch block->predecessors().clear(); 396bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch block->predecessors().push_back(merger); 397bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch} 398bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch 3993b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochvoid Schedule::PropagateDeferredMark() { 4003b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Push forward the deferred block marks through newly inserted blocks and 4013b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // other improperly marked blocks until a fixed point is reached. 4023b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // TODO(danno): optimize the propagation 4033b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch bool done = false; 4043b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch while (!done) { 4053b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch done = true; 4063b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (auto block : all_blocks_) { 4073b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (!block->deferred()) { 4083b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch bool deferred = block->PredecessorCount() > 0; 4093b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (auto pred : block->predecessors()) { 41062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) { 4113b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch deferred = false; 4123b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4133b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4143b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (deferred) { 4153b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch block->set_deferred(true); 4163b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch done = false; 4173b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4183b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4193b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4203b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 4213b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch} 422014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 423958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) { 424958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->AddSuccessor(succ); 425958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier succ->AddPredecessor(block); 426958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 427958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 428958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 429958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) { 430014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (BasicBlock* const successor : from->successors()) { 431014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch to->AddSuccessor(successor); 432014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (BasicBlock*& predecessor : successor->predecessors()) { 433014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (predecessor == from) predecessor = to; 434958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 435958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 436958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier from->ClearSuccessors(); 437958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 438958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 439958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 440958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::SetControlInput(BasicBlock* block, Node* node) { 441958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier block->set_control_input(node); 442958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier SetBlockForNode(block, node); 443958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 444958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 445958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 446958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Berniervoid Schedule::SetBlockForNode(BasicBlock* block, Node* node) { 447014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (node->id() >= nodeid_to_block_.size()) { 448958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodeid_to_block_.resize(node->id() + 1); 449958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 450958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodeid_to_block_[node->id()] = block; 451958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} 452958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 453958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 454958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierstd::ostream& operator<<(std::ostream& os, const Schedule& s) { 4553b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (BasicBlock* block : 4563b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch ((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) { 4573b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (block->rpo_number() == -1) { 4583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "--- BLOCK id:" << block->id().ToInt(); 4593b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } else { 4603b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "--- BLOCK B" << block->rpo_number(); 4613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 462958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (block->deferred()) os << " (deferred)"; 463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (block->PredecessorCount() != 0) os << " <- "; 464b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool comma = false; 465014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (BasicBlock const* predecessor : block->predecessors()) { 466b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (comma) os << ", "; 467b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch comma = true; 4683b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (predecessor->rpo_number() == -1) { 4693b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "id:" << predecessor->id().ToInt(); 4703b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } else { 4713b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "B" << predecessor->rpo_number(); 4723b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 473b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << " ---\n"; 475014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (Node* node : *block) { 476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << " " << *node; 477958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier if (NodeProperties::IsTyped(node)) { 478014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Type* type = NodeProperties::GetType(node); 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << " : "; 480014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch type->PrintTo(os); 481b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 482b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "\n"; 483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 484958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock::Control control = block->control(); 485b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (control != BasicBlock::kNone) { 486b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << " "; 487014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->control_input() != nullptr) { 488958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier os << *block->control_input(); 489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } else { 490b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "Goto"; 491b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 492b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << " -> "; 493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch comma = false; 494014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (BasicBlock const* successor : block->successors()) { 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (comma) os << ", "; 496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch comma = true; 4973b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (successor->rpo_number() == -1) { 4983b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "id:" << successor->id().ToInt(); 4993b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } else { 5003b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch os << "B" << successor->rpo_number(); 5013b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch os << "\n"; 504b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 505b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 506b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return os; 507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 508958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 509b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace compiler 510b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace internal 511b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} // namespace v8 512