blob: d33fc13c1cf1e61bba7bd4d52e6f202897441c7f [file] [log] [blame]
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/compiler/schedule.h"
#include "src/compiler/node-properties.h"
#include "src/compiler/node.h"
#include "src/utils/ostreams.h"
namespace v8 {
namespace internal {
namespace compiler {
BasicBlock::BasicBlock(Zone* zone, Id id)
: loop_number_(-1),
rpo_number_(-1),
deferred_(false),
dominator_depth_(-1),
dominator_(nullptr),
rpo_next_(nullptr),
loop_header_(nullptr),
loop_end_(nullptr),
loop_depth_(0),
control_(kNone),
control_input_(nullptr),
nodes_(zone),
successors_(zone),
predecessors_(zone),
#if DEBUG
debug_info_(AssemblerDebugInfo(nullptr, nullptr, -1)),
#endif
id_(id) {
}
bool BasicBlock::LoopContains(BasicBlock* block) const {
// RPO numbers must be initialized.
DCHECK_LE(0, rpo_number_);
DCHECK_LE(0, block->rpo_number_);
if (loop_end_ == nullptr) return false; // This is not a loop.
return block->rpo_number_ >= rpo_number_ &&
block->rpo_number_ < loop_end_->rpo_number_;
}
void BasicBlock::AddSuccessor(BasicBlock* successor) {
successors_.push_back(successor);
}
void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
predecessors_.push_back(predecessor);
}
void BasicBlock::AddNode(Node* node) { nodes_.push_back(node); }
void BasicBlock::set_control(Control control) { control_ = control; }
void BasicBlock::set_control_input(Node* control_input) {
if (!nodes_.empty() && control_input == nodes_.back()) {
nodes_.pop_back();
}
control_input_ = control_input;
}
void BasicBlock::set_loop_depth(int32_t loop_depth) {
loop_depth_ = loop_depth;
}
void BasicBlock::set_rpo_number(int32_t rpo_number) {
rpo_number_ = rpo_number;
}
void BasicBlock::set_loop_end(BasicBlock* loop_end) { loop_end_ = loop_end; }
void BasicBlock::set_loop_header(BasicBlock* loop_header) {
loop_header_ = loop_header;
}
// static
BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
while (b1 != b2) {
if (b1->dominator_depth() < b2->dominator_depth()) {
b2 = b2->dominator();
} else {
b1 = b1->dominator();
}
}
return b1;
}
void BasicBlock::Print() { StdoutStream{} << this; }
std::ostream& operator<<(std::ostream& os, const BasicBlock& block) {
os << "B" << block.id();
#if DEBUG
AssemblerDebugInfo info = block.debug_info();
if (info.name) os << info;
// Print predecessor blocks for better debugging.
const int kMaxDisplayedBlocks = 4;
int i = 0;
const BasicBlock* current_block = &block;
while (current_block->PredecessorCount() > 0 && i++ < kMaxDisplayedBlocks) {
current_block = current_block->predecessors().front();
os << " <= B" << current_block->id();
info = current_block->debug_info();
if (info.name) os << info;
}
#endif
return os;
}
std::ostream& operator<<(std::ostream& os, const BasicBlock::Control& c) {
switch (c) {
case BasicBlock::kNone:
return os << "none";
case BasicBlock::kGoto:
return os << "goto";
case BasicBlock::kCall:
return os << "call";
case BasicBlock::kBranch:
return os << "branch";
case BasicBlock::kSwitch:
return os << "switch";
case BasicBlock::kDeoptimize:
return os << "deoptimize";
case BasicBlock::kTailCall:
return os << "tailcall";
case BasicBlock::kReturn:
return os << "return";
case BasicBlock::kThrow:
return os << "throw";
}
UNREACHABLE();
}
std::ostream& operator<<(std::ostream& os, const BasicBlock::Id& id) {
return os << id.ToSize();
}
Schedule::Schedule(Zone* zone, size_t node_count_hint)
: zone_(zone),
all_blocks_(zone),
nodeid_to_block_(zone),
rpo_order_(zone),
start_(NewBasicBlock()),
end_(NewBasicBlock()) {
nodeid_to_block_.reserve(node_count_hint);
}
BasicBlock* Schedule::block(Node* node) const {
if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
return nodeid_to_block_[node->id()];
}
return nullptr;
}
bool Schedule::IsScheduled(Node* node) {
if (node->id() >= nodeid_to_block_.size()) return false;
return nodeid_to_block_[node->id()] != nullptr;
}
BasicBlock* Schedule::GetBlockById(BasicBlock::Id block_id) {
DCHECK(block_id.ToSize() < all_blocks_.size());
return all_blocks_[block_id.ToSize()];
}
bool Schedule::SameBasicBlock(Node* a, Node* b) const {
BasicBlock* block = this->block(a);
return block != nullptr && block == this->block(b);
}
BasicBlock* Schedule::NewBasicBlock() {
BasicBlock* block = new (zone_)
BasicBlock(zone_, BasicBlock::Id::FromSize(all_blocks_.size()));
all_blocks_.push_back(block);
return block;
}
void Schedule::PlanNode(BasicBlock* block, Node* node) {
#ifndef V8_OS_STARBOARD
if (FLAG_trace_turbo_scheduler) {
StdoutStream{} << "Planning #" << node->id() << ":"
<< node->op()->mnemonic() << " for future add to B"
<< block->id() << "\n";
}
#endif
DCHECK_NULL(this->block(node));
SetBlockForNode(block, node);
}
void Schedule::AddNode(BasicBlock* block, Node* node) {
#ifndef V8_OS_STARBOARD
if (FLAG_trace_turbo_scheduler) {
StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
<< " to B" << block->id() << "\n";
}
#endif
DCHECK(this->block(node) == nullptr || this->block(node) == block);
block->AddNode(node);
SetBlockForNode(block, node);
}
void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
DCHECK_EQ(BasicBlock::kNone, block->control());
block->set_control(BasicBlock::kGoto);
AddSuccessor(block, succ);
}
#if DEBUG
namespace {
bool IsPotentiallyThrowingCall(IrOpcode::Value opcode) {
switch (opcode) {
#define BUILD_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
JS_OP_LIST(BUILD_BLOCK_JS_CASE)
#undef BUILD_BLOCK_JS_CASE
case IrOpcode::kCall:
case IrOpcode::kCallWithCallerSavedRegisters:
return true;
default:
return false;
}
}
} // namespace
#endif // DEBUG
void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
BasicBlock* exception_block) {
DCHECK_EQ(BasicBlock::kNone, block->control());
DCHECK(IsPotentiallyThrowingCall(call->opcode()));
block->set_control(BasicBlock::kCall);
AddSuccessor(block, success_block);
AddSuccessor(block, exception_block);
SetControlInput(block, call);
}
void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
BasicBlock* fblock) {
DCHECK_EQ(BasicBlock::kNone, block->control());
DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
block->set_control(BasicBlock::kBranch);
AddSuccessor(block, tblock);
AddSuccessor(block, fblock);
SetControlInput(block, branch);
}
void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
size_t succ_count) {
DCHECK_EQ(BasicBlock::kNone, block->control());
DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
block->set_control(BasicBlock::kSwitch);
for (size_t index = 0; index < succ_count; ++index) {
AddSuccessor(block, succ_blocks[index]);
}
SetControlInput(block, sw);
}
void Schedule::AddTailCall(BasicBlock* block, Node* input) {
DCHECK_EQ(BasicBlock::kNone, block->control());
block->set_control(BasicBlock::kTailCall);
SetControlInput(block, input);
if (block != end()) AddSuccessor(block, end());
}
void Schedule::AddReturn(BasicBlock* block, Node* input) {
DCHECK_EQ(BasicBlock::kNone, block->control());
block->set_control(BasicBlock::kReturn);
SetControlInput(block, input);
if (block != end()) AddSuccessor(block, end());
}
void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
DCHECK_EQ(BasicBlock::kNone, block->control());
block->set_control(BasicBlock::kDeoptimize);
SetControlInput(block, input);
if (block != end()) AddSuccessor(block, end());
}
void Schedule::AddThrow(BasicBlock* block, Node* input) {
DCHECK_EQ(BasicBlock::kNone, block->control());
block->set_control(BasicBlock::kThrow);
SetControlInput(block, input);
if (block != end()) AddSuccessor(block, end());
}
void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
BasicBlock* tblock, BasicBlock* fblock) {
DCHECK_NE(BasicBlock::kNone, block->control());
DCHECK_EQ(BasicBlock::kNone, end->control());
end->set_control(block->control());
block->set_control(BasicBlock::kBranch);
MoveSuccessors(block, end);
AddSuccessor(block, tblock);
AddSuccessor(block, fblock);
if (block->control_input() != nullptr) {
SetControlInput(end, block->control_input());
}
SetControlInput(block, branch);
}
void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
BasicBlock** succ_blocks, size_t succ_count) {
DCHECK_NE(BasicBlock::kNone, block->control());
DCHECK_EQ(BasicBlock::kNone, end->control());
end->set_control(block->control());
block->set_control(BasicBlock::kSwitch);
MoveSuccessors(block, end);
for (size_t index = 0; index < succ_count; ++index) {
AddSuccessor(block, succ_blocks[index]);
}
if (block->control_input() != nullptr) {
SetControlInput(end, block->control_input());
}
SetControlInput(block, sw);
}
void Schedule::EnsureCFGWellFormedness() {
// Make a copy of all the blocks for the iteration, since adding the split
// edges will allocate new blocks.
BasicBlockVector all_blocks_copy(all_blocks_);
// Insert missing split edge blocks.
for (BasicBlock* block : all_blocks_copy) {
if (block->PredecessorCount() > 1) {
if (block != end_) {
EnsureSplitEdgeForm(block);
}
if (block->deferred()) {
EnsureDeferredCodeSingleEntryPoint(block);
}
}
}
EliminateRedundantPhiNodes();
}
void Schedule::EliminateRedundantPhiNodes() {
// Ensure that useless phi nodes that only have a single input, identical
// inputs, or are a self-referential loop phi,
// -- which can happen with the automatically generated code in the CSA and
// torque -- are pruned.
// Since we have strucured control flow, this is enough to minimize the number
// of phi nodes.
bool reached_fixed_point = false;
while (!reached_fixed_point) {
reached_fixed_point = true;
for (BasicBlock* block : all_blocks_) {
int predecessor_count = static_cast<int>(block->PredecessorCount());
for (size_t node_pos = 0; node_pos < block->NodeCount(); ++node_pos) {
Node* node = block->NodeAt(node_pos);
if (node->opcode() == IrOpcode::kPhi) {
Node* first_input = node->InputAt(0);
bool inputs_equal = true;
for (int i = 1; i < predecessor_count; ++i) {
Node* input = node->InputAt(i);
if (input != first_input && input != node) {
inputs_equal = false;
break;
}
}
if (!inputs_equal) continue;
node->ReplaceUses(first_input);
block->RemoveNode(block->begin() + node_pos);
--node_pos;
reached_fixed_point = false;
}
}
}
}
}
void Schedule::EnsureSplitEdgeForm(BasicBlock* block) {
#ifdef DEBUG
DCHECK(block->PredecessorCount() > 1 && block != end_);
for (auto current_pred = block->predecessors().begin();
current_pred != block->predecessors().end(); ++current_pred) {
BasicBlock* pred = *current_pred;
DCHECK_LE(pred->SuccessorCount(), 1);
}
#endif
}
void Schedule::EnsureDeferredCodeSingleEntryPoint(BasicBlock* block) {
// If a deferred block has multiple predecessors, they have to
// all be deferred. Otherwise, we can run into a situation where a range
// that spills only in deferred blocks inserts its spill in the block, but
// other ranges need moves inserted by ResolveControlFlow in the predecessors,
// which may clobber the register of this range.
// To ensure that, when a deferred block has multiple predecessors, and some
// are not deferred, we add a non-deferred block to collect all such edges.
DCHECK(block->deferred() && block->PredecessorCount() > 1);
bool all_deferred = true;
for (auto current_pred = block->predecessors().begin();
current_pred != block->predecessors().end(); ++current_pred) {
BasicBlock* pred = *current_pred;
if (!pred->deferred()) {
all_deferred = false;
break;
}
}
if (all_deferred) return;
BasicBlock* merger = NewBasicBlock();
merger->set_control(BasicBlock::kGoto);
merger->successors().push_back(block);
for (auto current_pred = block->predecessors().begin();
current_pred != block->predecessors().end(); ++current_pred) {
BasicBlock* pred = *current_pred;
merger->predecessors().push_back(pred);
pred->successors().clear();
pred->successors().push_back(merger);
}
merger->set_deferred(false);
block->predecessors().clear();
block->predecessors().push_back(merger);
MovePhis(block, merger);
}
void Schedule::MovePhis(BasicBlock* from, BasicBlock* to) {
for (size_t i = 0; i < from->NodeCount();) {
Node* node = from->NodeAt(i);
if (node->opcode() == IrOpcode::kPhi) {
to->AddNode(node);
from->RemoveNode(from->begin() + i);
DCHECK_EQ(nodeid_to_block_[node->id()], from);
nodeid_to_block_[node->id()] = to;
} else {
++i;
}
}
}
void Schedule::PropagateDeferredMark() {
// Push forward the deferred block marks through newly inserted blocks and
// other improperly marked blocks until a fixed point is reached.
// TODO(danno): optimize the propagation
bool done = false;
while (!done) {
done = true;
for (auto block : all_blocks_) {
if (!block->deferred()) {
bool deferred = block->PredecessorCount() > 0;
for (auto pred : block->predecessors()) {
if (!pred->deferred() && (pred->rpo_number() < block->rpo_number())) {
deferred = false;
}
}
if (deferred) {
block->set_deferred(true);
done = false;
}
}
}
}
}
void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
block->AddSuccessor(succ);
succ->AddPredecessor(block);
}
void Schedule::MoveSuccessors(BasicBlock* from, BasicBlock* to) {
for (BasicBlock* const successor : from->successors()) {
to->AddSuccessor(successor);
for (BasicBlock*& predecessor : successor->predecessors()) {
if (predecessor == from) predecessor = to;
}
}
from->ClearSuccessors();
}
void Schedule::SetControlInput(BasicBlock* block, Node* node) {
block->set_control_input(node);
SetBlockForNode(block, node);
}
void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
if (node->id() >= nodeid_to_block_.size()) {
nodeid_to_block_.resize(node->id() + 1);
}
nodeid_to_block_[node->id()] = block;
}
std::ostream& operator<<(std::ostream& os, const Schedule& s) {
for (BasicBlock* block :
((s.RpoBlockCount() == 0) ? *s.all_blocks() : *s.rpo_order())) {
if (block->rpo_number() == -1) {
os << "--- BLOCK id:" << block->id().ToInt();
} else {
os << "--- BLOCK B" << block->rpo_number();
}
if (block->deferred()) os << " (deferred)";
if (block->PredecessorCount() != 0) os << " <- ";
bool comma = false;
for (BasicBlock const* predecessor : block->predecessors()) {
if (comma) os << ", ";
comma = true;
if (predecessor->rpo_number() == -1) {
os << "id:" << predecessor->id().ToInt();
} else {
os << "B" << predecessor->rpo_number();
}
}
os << " ---\n";
for (Node* node : *block) {
os << " " << *node;
if (NodeProperties::IsTyped(node)) {
os << " : " << NodeProperties::GetType(node);
}
os << "\n";
}
BasicBlock::Control control = block->control();
if (control != BasicBlock::kNone) {
os << " ";
if (block->control_input() != nullptr) {
os << *block->control_input();
} else {
os << "Goto";
}
os << " -> ";
comma = false;
for (BasicBlock const* successor : block->successors()) {
if (comma) os << ", ";
comma = true;
if (successor->rpo_number() == -1) {
os << "id:" << successor->id().ToInt();
} else {
os << "B" << successor->rpo_number();
}
}
os << "\n";
}
}
return os;
}
} // namespace compiler
} // namespace internal
} // namespace v8