17d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 27d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Use of this source code is governed by a BSD-style license that can be 37d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// found in the LICENSE file. 47d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org#include <deque> 6fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org#include <queue> 7fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 87d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/scheduler.h" 97d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/graph.h" 117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/graph-inl.h" 127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node.h" 137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node-properties.h" 147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node-properties-inl.h" 157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/data-flow.h" 167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace v8 { 187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace internal { 197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace compiler { 207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 21e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.orgstatic inline void Trace(const char* msg, ...) { 22e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if (FLAG_trace_turbo_scheduler) { 23e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org va_list arguments; 24e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org va_start(arguments, msg); 25e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org base::OS::VPrint(msg, arguments); 26e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org va_end(arguments); 27e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 28e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org} 29e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 30e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 31e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org// Internal class to build a control flow graph (i.e the basic blocks and edges 32e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org// between them within a Schedule) from the node graph. 33fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org// Visits the control edges of the graph backwards from end in order to find 34fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org// the connected control subgraph, needed for scheduling. 35fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgclass CFGBuilder { 36e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org public: 37fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler* scheduler_; 38e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Schedule* schedule_; 39fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ZoneQueue<Node*> queue_; 40fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org NodeVector control_; 41fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 42fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org CFGBuilder(Zone* zone, Scheduler* scheduler) 43fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org : scheduler_(scheduler), 44fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org schedule_(scheduler->schedule_), 45fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue_(zone), 46fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org control_(zone) {} 47fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 48fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Run the control flow graph construction algorithm by walking the graph 49fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // backwards from end through control edges, building and connecting the 50fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // basic blocks for control nodes. 51fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org void Run() { 52fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Graph* graph = scheduler_->graph_; 53fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org FixNode(schedule_->start(), graph->start()); 54fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Queue(graph->end()); 55fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 56fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org while (!queue_.empty()) { // Breadth-first backwards traversal. 57fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* node = queue_.front(); 58fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue_.pop(); 59fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org int max = NodeProperties::PastControlIndex(node); 60fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { 61fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Queue(node->InputAt(i)); 62fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 63fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 64fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 65fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) { 66fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ConnectBlocks(*i); // Connect block to its predecessor/successors. 67fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 68fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 69fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org FixNode(schedule_->end(), graph->end()); 70fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 71fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 72fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org void FixNode(BasicBlock* block, Node* node) { 73fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org schedule_->AddNode(block, node); 74fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->GetData(node)->is_connected_control_ = true; 75fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->GetData(node)->placement_ = Scheduler::kFixed; 76fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 77e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 78fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org void Queue(Node* node) { 79fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Mark the connected control nodes as they queued. 80fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler::SchedulerData* data = scheduler_->GetData(node); 81fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (!data->is_connected_control_) { 82fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BuildBlocks(node); 83fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue_.push(node); 84fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org control_.push_back(node); 85fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->is_connected_control_ = true; 86fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 87fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 88e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 89fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org void BuildBlocks(Node* node) { 90e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org switch (node->opcode()) { 91e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kLoop: 92e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kMerge: 93e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BuildBlockForNode(node); 94e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 95e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kBranch: 96e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BuildBlocksForSuccessors(node, IrOpcode::kIfTrue, IrOpcode::kIfFalse); 97e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 98e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org default: 99e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 100e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 101e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 102e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 103fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org void ConnectBlocks(Node* node) { 104e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org switch (node->opcode()) { 105e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kLoop: 106e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kMerge: 107e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org ConnectMerge(node); 108e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 109e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kBranch: 110fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->schedule_root_nodes_.push_back(node); 111e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org ConnectBranch(node); 112e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 113e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org case IrOpcode::kReturn: 114fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->schedule_root_nodes_.push_back(node); 115e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org ConnectReturn(node); 116e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 117e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org default: 118e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org break; 119e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 120e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 121e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 122e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void BuildBlockForNode(Node* node) { 123e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if (schedule_->block(node) == NULL) { 124e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* block = schedule_->NewBasicBlock(); 125fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Create block B%d for #%d:%s\n", block->id(), node->id(), 126fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic()); 127fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org FixNode(block, node); 128e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 129e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 130e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 131e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void BuildBlocksForSuccessors(Node* node, IrOpcode::Value a, 132e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::Value b) { 133e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Node* successors[2]; 134e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org CollectSuccessorProjections(node, successors, a, b); 135e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BuildBlockForNode(successors[0]); 136e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BuildBlockForNode(successors[1]); 137e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 138e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 139e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org // Collect the branch-related projections from a node, such as IfTrue, 140ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org // IfFalse. 141e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org // TODO(titzer): consider moving this to node.h 142e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void CollectSuccessorProjections(Node* node, Node** buffer, 143e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::Value true_opcode, 144e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::Value false_opcode) { 145e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[0] = NULL; 146e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[1] = NULL; 147e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org for (UseIter i = node->uses().begin(); i != node->uses().end(); ++i) { 148e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if ((*i)->opcode() == true_opcode) { 149e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK_EQ(NULL, buffer[0]); 150e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[0] = *i; 151e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 152e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if ((*i)->opcode() == false_opcode) { 153e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK_EQ(NULL, buffer[1]); 154e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[1] = *i; 155e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 156e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 157e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK_NE(NULL, buffer[0]); 158e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK_NE(NULL, buffer[1]); 159e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 160e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 161e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void CollectSuccessorBlocks(Node* node, BasicBlock** buffer, 162e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::Value true_opcode, 163e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::Value false_opcode) { 164e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Node* successors[2]; 165e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org CollectSuccessorProjections(node, successors, true_opcode, false_opcode); 166e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[0] = schedule_->block(successors[0]); 167e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org buffer[1] = schedule_->block(successors[1]); 168e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 169e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 170e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void ConnectBranch(Node* branch) { 171e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Node* branch_block_node = NodeProperties::GetControlInput(branch); 172e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* branch_block = schedule_->block(branch_block_node); 173e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK(branch_block != NULL); 174e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 175e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* successor_blocks[2]; 176e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org CollectSuccessorBlocks(branch, successor_blocks, IrOpcode::kIfTrue, 177e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org IrOpcode::kIfFalse); 178e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 179e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org TraceConnect(branch, branch_block, successor_blocks[0]); 180e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org TraceConnect(branch, branch_block, successor_blocks[1]); 181e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 182e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org schedule_->AddBranch(branch_block, branch, successor_blocks[0], 183e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org successor_blocks[1]); 184e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 185e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 186e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void ConnectMerge(Node* merge) { 187e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* block = schedule_->block(merge); 188e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK(block != NULL); 189e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org // For all of the merge's control inputs, add a goto at the end to the 190e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org // merge's basic block. 191e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org for (InputIter j = merge->inputs().begin(); j != merge->inputs().end(); 192e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org ++j) { 193e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* predecessor_block = schedule_->block(*j); 194ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org if ((*j)->opcode() != IrOpcode::kReturn) { 195e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org TraceConnect(merge, predecessor_block, block); 196e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org schedule_->AddGoto(predecessor_block, block); 197e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 198e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 199e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 200e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 201e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void ConnectReturn(Node* ret) { 202e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Node* return_block_node = NodeProperties::GetControlInput(ret); 203e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org BasicBlock* return_block = schedule_->block(return_block_node); 204e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org TraceConnect(ret, return_block, NULL); 205e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org schedule_->AddReturn(return_block, ret); 206e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 207e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 208e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) { 209e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org DCHECK_NE(NULL, block); 210e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if (succ == NULL) { 211fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Connect #%d:%s, B%d -> end\n", node->id(), node->op()->mnemonic(), 212fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block->id()); 213e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } else { 214fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Connect #%d:%s, B%d -> B%d\n", node->id(), node->op()->mnemonic(), 215fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block->id(), succ->id()); 216e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 217e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org } 218e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org}; 219e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 220e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 221fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgScheduler::SchedulerData Scheduler::DefaultSchedulerData() { 222fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SchedulerData def = {0, 0, false, false, kUnknown}; 223fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org return def; 224fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org} 225fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 226fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 2277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgScheduler::Scheduler(Zone* zone, Graph* graph, Schedule* schedule) 2285e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org : zone_(zone), 2295e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org graph_(graph), 2307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org schedule_(schedule), 231fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduled_nodes_(zone), 232fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org schedule_root_nodes_(zone), 233fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node_data_(graph_->NodeCount(), DefaultSchedulerData(), zone), 234fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org has_floating_control_(false) {} 2357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 23731c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.orgSchedule* Scheduler::ComputeSchedule(Graph* graph) { 238fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Schedule* schedule; 239fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org bool had_floating_control = false; 240fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org do { 241fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Zone tmp_zone(graph->zone()->isolate()); 242fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org schedule = new (graph->zone()) Schedule(graph->zone()); 243fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler scheduler(&tmp_zone, graph, schedule); 244e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 245fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler.BuildCFG(); 2467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 247fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler::ComputeSpecialRPO(schedule); 248fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler.GenerateImmediateDominatorTree(); 249e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org 250fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler.PrepareUses(); 251fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler.ScheduleEarly(); 252fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler.ScheduleLate(); 2537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 254fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org had_floating_control = scheduler.ConnectFloatingControl(); 255fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } while (had_floating_control); 2567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 25731c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org return schedule; 2587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 2597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 261fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgScheduler::Placement Scheduler::GetPlacement(Node* node) { 262fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SchedulerData* data = GetData(node); 263fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (data->placement_ == kUnknown) { // Compute placement, once, on demand. 264fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org switch (node->opcode()) { 265fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org case IrOpcode::kParameter: 266fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Parameters are always fixed to the start node. 267fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->placement_ = kFixed; 268fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org break; 269fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org case IrOpcode::kPhi: 270fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org case IrOpcode::kEffectPhi: { 271fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Phis and effect phis are fixed if their control inputs are. 272fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->placement_ = GetPlacement(NodeProperties::GetControlInput(node)); 273fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org break; 274fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 275fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org#define DEFINE_FLOATING_CONTROL_CASE(V) case IrOpcode::k##V: 276fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org CONTROL_OP_LIST(DEFINE_FLOATING_CONTROL_CASE) 277fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org#undef DEFINE_FLOATING_CONTROL_CASE 278fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org { 279fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Control nodes that were not control-reachable from end may float. 280fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->placement_ = kSchedulable; 281fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (!data->is_connected_control_) { 282fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->is_floating_control_ = true; 283fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org has_floating_control_ = true; 284fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Floating control found: #%d:%s\n", node->id(), 285fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic()); 286fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 287fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org break; 288fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 289fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org default: 290fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->placement_ = kSchedulable; 291fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org break; 292fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 293fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 294fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org return data->placement_; 2955e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org} 2965e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org 2975e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org 298fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgvoid Scheduler::BuildCFG() { 299e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("---------------- CREATING CFG ------------------\n"); 300fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org CFGBuilder cfg_builder(zone_, this); 301fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org cfg_builder.Run(); 302fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Initialize per-block data. 303fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduled_nodes_.resize(schedule_->BasicBlockCount(), NodeVector(zone_)); 3047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 3057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgBasicBlock* Scheduler::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) { 3087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (b1 != b2) { 3097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int b1_rpo = GetRPONumber(b1); 3107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int b2_rpo = GetRPONumber(b2); 311e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(b1_rpo != b2_rpo); 3127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (b1_rpo < b2_rpo) { 313fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org b2 = b2->dominator_; 3147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 315fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org b1 = b1->dominator_; 3167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return b1; 3197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 3207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgvoid Scheduler::GenerateImmediateDominatorTree() { 3237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Build the dominator graph. TODO(danno): consider using Lengauer & Tarjan's 3247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // if this becomes really slow. 325e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("------------ IMMEDIATE BLOCK DOMINATORS -----------\n"); 3267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (size_t i = 0; i < schedule_->rpo_order_.size(); i++) { 3277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* current_rpo = schedule_->rpo_order_[i]; 3285e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org if (current_rpo != schedule_->start()) { 3297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock::Predecessors::iterator current_pred = 3307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_rpo->predecessors().begin(); 3317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock::Predecessors::iterator end = 3327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_rpo->predecessors().end(); 333e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(current_pred != end); 3347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* dominator = *current_pred; 3357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++current_pred; 3367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // For multiple predecessors, walk up the rpo ordering until a common 3377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // dominator is found. 3387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int current_rpo_pos = GetRPONumber(current_rpo); 3397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (current_pred != end) { 3407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Don't examine backwards edges 3417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* pred = *current_pred; 3427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (GetRPONumber(pred) < current_rpo_pos) { 3437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org dominator = GetCommonDominator(dominator, *current_pred); 3447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++current_pred; 3467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 347fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org current_rpo->dominator_ = dominator; 348e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("Block %d's idom is %d\n", current_rpo->id(), dominator->id()); 3497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 3527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass ScheduleEarlyNodeVisitor : public NullNodeVisitor { 3557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 3567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit ScheduleEarlyNodeVisitor(Scheduler* scheduler) 3577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : has_changed_rpo_constraints_(true), 3587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org scheduler_(scheduler), 3597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org schedule_(scheduler->schedule_) {} 3607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Control Pre(Node* node) { 3627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int max_rpo = 0; 3637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Fixed nodes already know their schedule early position. 364fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { 3657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = schedule_->block(node); 366e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block != NULL); 3677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org max_rpo = block->rpo_number_; 368fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) { 3697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org has_changed_rpo_constraints_ = true; 3707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 371fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->GetData(node)->minimum_rpo_ = max_rpo; 372fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Preschedule #%d:%s minimum_rpo = %d\n", node->id(), 373fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), max_rpo); 3747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 3767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Control Post(Node* node) { 3797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int max_rpo = 0; 3807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Otherwise, the minimum rpo for the node is the max of all of the inputs. 381fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetPlacement(node) != Scheduler::kFixed) { 3827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (InputIter i = node->inputs().begin(); i != node->inputs().end(); 3837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++i) { 384fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org int control_rpo = scheduler_->GetData(*i)->minimum_rpo_; 3857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (control_rpo > max_rpo) { 3867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org max_rpo = control_rpo; 3877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 389fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetData(node)->minimum_rpo_ != max_rpo) { 3907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org has_changed_rpo_constraints_ = true; 3917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 392fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->GetData(node)->minimum_rpo_ = max_rpo; 393fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Postschedule #%d:%s minimum_rpo = %d\n", node->id(), 394fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), max_rpo); 3957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 3977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 3987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // TODO(mstarzinger): Dirty hack to unblock others, schedule early should be 4007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // rewritten to use a pre-order traversal from the start instead. 4017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool has_changed_rpo_constraints_; 4027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 4047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Scheduler* scheduler_; 4057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Schedule* schedule_; 4067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 4077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgvoid Scheduler::ScheduleEarly() { 410e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("------------------- SCHEDULE EARLY ----------------\n"); 4117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int fixpoint_count = 0; 4137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ScheduleEarlyNodeVisitor visitor(this); 4147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (visitor.has_changed_rpo_constraints_) { 4157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org visitor.has_changed_rpo_constraints_ = false; 4167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org graph_->VisitNodeInputsFromEnd(&visitor); 4177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org fixpoint_count++; 4187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 4197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 420e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("It took %d iterations to determine fixpoint\n", fixpoint_count); 4217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 4227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass PrepareUsesVisitor : public NullNodeVisitor { 4257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 4267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit PrepareUsesVisitor(Scheduler* scheduler) 4277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : scheduler_(scheduler), schedule_(scheduler->schedule_) {} 4287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Control Pre(Node* node) { 430fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetPlacement(node) == Scheduler::kFixed) { 431fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Fixed nodes are always roots for schedule late. 4327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org scheduler_->schedule_root_nodes_.push_back(node); 433fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (!schedule_->IsScheduled(node)) { 434fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Make sure root nodes are scheduled in their respective blocks. 435fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Scheduling fixed position node #%d:%s\n", node->id(), 436fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic()); 437fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org IrOpcode::Value opcode = node->opcode(); 438fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* block = 439fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org opcode == IrOpcode::kParameter 440fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ? schedule_->start() 441fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org : schedule_->block(NodeProperties::GetControlInput(node)); 442fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK(block != NULL); 443fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org schedule_->AddNode(block, node); 444fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 4457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 4467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 4487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 4497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void PostEdge(Node* from, int index, Node* to) { 4517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // If the edge is from an unscheduled node, then tally it in the use count 4527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // for all of its inputs. The same criterion will be used in ScheduleLate 4537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // for decrementing use counts. 454e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if (!schedule_->IsScheduled(from)) { 455fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from)); 456fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ++(scheduler_->GetData(to)->unscheduled_count_); 457fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Use count of #%d:%s (used by #%d:%s)++ = %d\n", to->id(), 458fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org to->op()->mnemonic(), from->id(), from->op()->mnemonic(), 459fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org scheduler_->GetData(to)->unscheduled_count_); 4607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 4617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 4627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 4647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Scheduler* scheduler_; 4657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Schedule* schedule_; 4667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 4677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgvoid Scheduler::PrepareUses() { 470e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("------------------- PREPARE USES ------------------\n"); 4717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Count the uses of every node, it will be used to ensure that all of a 4727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // node's uses are scheduled before the node itself. 4737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrepareUsesVisitor prepare_uses(this); 4747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org graph_->VisitNodeInputsFromEnd(&prepare_uses); 4757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 4767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass ScheduleLateNodeVisitor : public NullNodeVisitor { 4797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 4807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit ScheduleLateNodeVisitor(Scheduler* scheduler) 4817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : scheduler_(scheduler), schedule_(scheduler_->schedule_) {} 4827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Control Pre(Node* node) { 484e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org // Don't schedule nodes that are already scheduled. 485e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org if (schedule_->IsScheduled(node)) { 4867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 4877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 488fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler::SchedulerData* data = scheduler_->GetData(node); 489fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_EQ(Scheduler::kSchedulable, data->placement_); 4907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // If all the uses of a node have been scheduled, then the node itself can 4927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // be scheduled. 493fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org bool eligible = data->unscheduled_count_ == 0; 494fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Testing for schedule eligibility for #%d:%s = %s\n", node->id(), 495fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), eligible ? "true" : "false"); 4967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (!eligible) return GenericGraphVisit::DEFER; 4977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 4987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Determine the dominating block for all of the uses of this node. It is 4997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // the latest block that this node can be scheduled in. 5007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = NULL; 5017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (Node::Uses::iterator i = node->uses().begin(); i != node->uses().end(); 5027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++i) { 5037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* use_block = GetBlockForUse(i.edge()); 5047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block = block == NULL ? use_block : use_block == NULL 5057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ? block 5067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : scheduler_->GetCommonDominator( 5077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block, use_block); 5087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 509e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block != NULL); 5107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 511fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org int min_rpo = data->minimum_rpo_; 512e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace( 513fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org "Schedule late conservative for #%d:%s is B%d at loop depth %d, " 514fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org "minimum_rpo = %d\n", 515fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->id(), node->op()->mnemonic(), block->id(), block->loop_depth_, 516fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org min_rpo); 5177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively 518fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // into enclosing loop pre-headers until they would preceed their 5197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // ScheduleEarly position. 5207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* hoist_block = block; 5217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (hoist_block != NULL && hoist_block->rpo_number_ >= min_rpo) { 5227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (hoist_block->loop_depth_ < block->loop_depth_) { 5237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block = hoist_block; 524fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" hoisting #%d:%s to block %d\n", node->id(), 525fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), block->id()); 5267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Try to hoist to the pre-header of the loop header. 5287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org hoist_block = hoist_block->loop_header(); 5297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (hoist_block != NULL) { 530fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* pre_header = hoist_block->dominator_; 531e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(pre_header == NULL || 5327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org *hoist_block->predecessors().begin() == pre_header); 533e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace( 534fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org " hoist to pre-header B%d of loop header B%d, depth would be %d\n", 535e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org pre_header->id(), hoist_block->id(), pre_header->loop_depth_); 5367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org hoist_block = pre_header; 5377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ScheduleNode(block, node); 5417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return GenericGraphVisit::CONTINUE; 5437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 5467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* GetBlockForUse(Node::Edge edge) { 5477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* use = edge.from(); 5487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org IrOpcode::Value opcode = use->opcode(); 5497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (opcode == IrOpcode::kPhi || opcode == IrOpcode::kEffectPhi) { 550fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // If the use is from a fixed (i.e. non-floating) phi, use the block 551fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // of the corresponding control input to the merge. 5527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int index = edge.index(); 553fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (scheduler_->GetPlacement(use) == Scheduler::kFixed) { 554fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" input@%d into a fixed phi #%d:%s\n", index, use->id(), 555fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org use->op()->mnemonic()); 556fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* merge = NodeProperties::GetControlInput(use, 0); 557fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org opcode = merge->opcode(); 558fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK(opcode == IrOpcode::kMerge || opcode == IrOpcode::kLoop); 559fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org use = NodeProperties::GetControlInput(merge, index); 560fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 5617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* result = schedule_->block(use); 5637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (result == NULL) return NULL; 564fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" must dominate use #%d:%s in B%d\n", use->id(), 565fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org use->op()->mnemonic(), result->id()); 5667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return result; 5677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void ScheduleNode(BasicBlock* block, Node* node) { 5707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org schedule_->PlanNode(block, node); 5717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org scheduler_->scheduled_nodes_[block->id()].push_back(node); 5727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Reduce the use count of the node's inputs to potentially make them 574fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // schedulable. 5757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (InputIter i = node->inputs().begin(); i != node->inputs().end(); ++i) { 576fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Scheduler::SchedulerData* data = scheduler_->GetData(*i); 577fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK(data->unscheduled_count_ > 0); 578fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org --data->unscheduled_count_; 5797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (FLAG_trace_turbo_scheduler) { 580fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Use count for #%d:%s (used by #%d:%s)-- = %d\n", (*i)->id(), 581fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org (*i)->op()->mnemonic(), i.edge().from()->id(), 582fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org i.edge().from()->op()->mnemonic(), data->unscheduled_count_); 583fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (data->unscheduled_count_ == 0) { 584fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" newly eligible #%d:%s\n", (*i)->id(), 585fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org (*i)->op()->mnemonic()); 5867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 5907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Scheduler* scheduler_; 5927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Schedule* schedule_; 5937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 5947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 5967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgvoid Scheduler::ScheduleLate() { 597e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("------------------- SCHEDULE LATE -----------------\n"); 598fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (FLAG_trace_turbo_scheduler) { 599fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("roots: "); 600fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (NodeVectorIter i = schedule_root_nodes_.begin(); 601fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org i != schedule_root_nodes_.end(); ++i) { 602fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("#%d:%s ", (*i)->id(), (*i)->op()->mnemonic()); 603fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 604fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("\n"); 605fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 6067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 6077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Schedule: Places nodes in dominator block of all their uses. 6087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ScheduleLateNodeVisitor schedule_late_visitor(this); 6097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 6105e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org { 6115e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org Zone zone(zone_->isolate()); 6127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org GenericGraphVisit::Visit<ScheduleLateNodeVisitor, 6137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeInputIterationTraits<Node> >( 6145e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org graph_, &zone, schedule_root_nodes_.begin(), schedule_root_nodes_.end(), 6155e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org &schedule_late_visitor); 6167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 6177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 6187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Add collected nodes for basic blocks to their blocks in the right order. 6197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int block_num = 0; 6207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (NodeVectorVectorIter i = scheduled_nodes_.begin(); 6217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org i != scheduled_nodes_.end(); ++i) { 6227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (NodeVectorRIter j = i->rbegin(); j != i->rend(); ++j) { 6237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org schedule_->AddNode(schedule_->all_blocks_.at(block_num), *j); 6247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 6257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block_num++; 6267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 6277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 6287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 6297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 630fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgbool Scheduler::ConnectFloatingControl() { 631fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (!has_floating_control_) return false; 632fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 633fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("Connecting floating control...\n"); 634fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 635fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Process blocks and instructions backwards to find and connect floating 636fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // control nodes into the control graph according to the block they were 637fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // scheduled into. 638fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org int max = static_cast<int>(schedule_->rpo_order()->size()); 639fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (int i = max - 1; i >= 0; i--) { 640fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* block = schedule_->rpo_order()->at(i); 6419e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org // TODO(titzer): we place at most one floating control structure per 6429e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org // basic block because scheduling currently can interleave phis from 6439e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org // one subgraph with the merges from another subgraph. 6449e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org bool one_placed = false; 645fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (int j = static_cast<int>(block->nodes_.size()) - 1; j >= 0; j--) { 646fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* node = block->nodes_[j]; 647fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SchedulerData* data = GetData(node); 6489e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org if (data->is_floating_control_ && !data->is_connected_control_ && 6499e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org !one_placed) { 650fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Floating control #%d:%s was scheduled in B%d\n", node->id(), 651fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), block->id()); 652fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ConnectFloatingControlSubgraph(block, node); 6539e2b466e4b4a2026caefa79afe6737f1bad83a19machenbach@chromium.org one_placed = true; 654fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 655fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 656fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 657fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 658fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org return true; 659fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org} 660fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 661fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 662fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgvoid Scheduler::ConnectFloatingControlSubgraph(BasicBlock* block, Node* end) { 663fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* block_start = block->nodes_[0]; 664fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK(IrOpcode::IsControlOpcode(block_start->opcode())); 665fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Find the current "control successor" of the node that starts the block 666fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // by searching the control uses for a control input edge from a connected 667fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // control node. 668fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* control_succ = NULL; 669fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (UseIter i = block_start->uses().begin(); i != block_start->uses().end(); 670fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ++i) { 671fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node::Edge edge = i.edge(); 672fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (NodeProperties::IsControlEdge(edge) && 673fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org GetData(edge.from())->is_connected_control_) { 674fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_EQ(NULL, control_succ); 675fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org control_succ = edge.from(); 676fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org control_succ->ReplaceInput(edge.index(), end); 677fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 678fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 679fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_NE(NULL, control_succ); 680fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Inserting floating control end %d:%s between %d:%s -> %d:%s\n", 681fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org end->id(), end->op()->mnemonic(), control_succ->id(), 682fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org control_succ->op()->mnemonic(), block_start->id(), 683fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block_start->op()->mnemonic()); 684fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 685fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Find the "start" node of the control subgraph, which should be the 686fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // unique node that is itself floating control but has a control input that 687fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // is not floating. 688fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* start = NULL; 689fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org ZoneQueue<Node*> queue(zone_); 690fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue.push(end); 691fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org GetData(end)->is_connected_control_ = true; 692fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org while (!queue.empty()) { 693fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* node = queue.front(); 694fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue.pop(); 695fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Search #%d:%s for control subgraph start\n", node->id(), 696fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic()); 697fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org int max = NodeProperties::PastControlIndex(node); 698fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) { 699fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Node* input = node->InputAt(i); 700fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SchedulerData* data = GetData(input); 701fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (data->is_floating_control_) { 702fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // {input} is floating control. 703fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (!data->is_connected_control_) { 704fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // First time seeing {input} during this traversal, queue it. 705fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org queue.push(input); 706fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org data->is_connected_control_ = true; 707fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 708fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } else { 709fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // Otherwise, {node} is the start node, because it is floating control 710fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // but is connected to {input} that is not floating control. 711fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_EQ(NULL, start); // There can be only one. 712fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org start = node; 713fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 714fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 715fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 716fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 717fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org DCHECK_NE(NULL, start); 718fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org start->ReplaceInput(NodeProperties::FirstControlIndex(start), block_start); 719fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 720fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace(" Connecting floating control start %d:%s to %d:%s\n", start->id(), 721fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org start->op()->mnemonic(), block_start->id(), 722fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block_start->op()->mnemonic()); 723fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org} 724fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 725fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org 7267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Numbering for BasicBlockData.rpo_number_ for this block traversal: 7277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic const int kBlockOnStack = -2; 7287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic const int kBlockVisited1 = -3; 7297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic const int kBlockVisited2 = -4; 7307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic const int kBlockUnvisited1 = -1; 7317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic const int kBlockUnvisited2 = kBlockVisited1; 7327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstruct SpecialRPOStackFrame { 7347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block; 7357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int index; 7367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 7377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstruct BlockList { 7397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block; 7407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* next; 7417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* Add(Zone* zone, BasicBlock* b) { 7437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* list = static_cast<BlockList*>(zone->New(sizeof(BlockList))); 7447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org list->block = b; 7457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org list->next = this; 7467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return list; 7477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 7487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void Serialize(BasicBlockVector* final_order) { 7507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (BlockList* l = this; l != NULL; l = l->next) { 7517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org l->block->rpo_number_ = static_cast<int>(final_order->size()); 7527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org final_order->push_back(l->block); 7537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 7547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 7557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 7567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstruct LoopInfo { 7587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* header; 7597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ZoneList<BasicBlock*>* outgoing; 7607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BitVector* members; 7617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* prev; 7627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* end; 7637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* start; 7647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddOutgoing(Zone* zone, BasicBlock* block) { 7667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (outgoing == NULL) outgoing = new (zone) ZoneList<BasicBlock*>(2, zone); 7677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org outgoing->Add(block, zone); 7687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 7697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 7707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic int Push(SpecialRPOStackFrame* stack, int depth, BasicBlock* child, 7737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int unvisited) { 7747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (child->rpo_number_ == unvisited) { 7757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack[depth].block = child; 7767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack[depth].index = 0; 7777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org child->rpo_number_ = kBlockOnStack; 7787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return depth + 1; 7797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 7807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return depth; 7817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 7827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Computes loop membership from the backedges of the control flow graph. 7857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic LoopInfo* ComputeLoopInfo( 7867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Zone* zone, SpecialRPOStackFrame* queue, int num_loops, int num_blocks, 7877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ZoneList<std::pair<BasicBlock*, int> >* backedges) { 7887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* loops = zone->NewArray<LoopInfo>(num_loops); 7897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org memset(loops, 0, num_loops * sizeof(LoopInfo)); 7907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 7917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Compute loop membership starting from backedges. 7927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // O(max(loop_depth) * max(|loop|) 7937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < backedges->length(); i++) { 7947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* member = backedges->at(i).first; 7957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* header = member->SuccessorAt(backedges->at(i).second); 7967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int loop_num = header->loop_end_; 7977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (loops[loop_num].header == NULL) { 7987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loops[loop_num].header = header; 7997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loops[loop_num].members = new (zone) BitVector(num_blocks, zone); 8007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int queue_length = 0; 8037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (member != header) { 8047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // As long as the header doesn't have a backedge to itself, 8057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Push the member onto the queue and process its predecessors. 8067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (!loops[loop_num].members->Contains(member->id())) { 8077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loops[loop_num].members->Add(member->id()); 8087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org queue[queue_length++].block = member; 8107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Propagate loop membership backwards. All predecessors of M up to the 8137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // loop header H are members of the loop too. O(|blocks between M and H|). 8147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (queue_length > 0) { 8157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = queue[--queue_length].block; 8167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < block->PredecessorCount(); i++) { 8177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* pred = block->PredecessorAt(i); 8187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (pred != header) { 8197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (!loops[loop_num].members->Contains(pred->id())) { 8207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loops[loop_num].members->Add(pred->id()); 8217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org queue[queue_length++].block = pred; 8227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return loops; 8287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 8297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#if DEBUG 8327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic void PrintRPO(int num_loops, LoopInfo* loops, BasicBlockVector* order) { 8337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("-- RPO with %d loops ", num_loops); 8347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (num_loops > 0) { 8357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("("); 8367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < num_loops; i++) { 8377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (i > 0) PrintF(" "); 8387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("B%d", loops[i].header->id()); 8397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF(") "); 8417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("-- \n"); 8437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < static_cast<int>(order->size()); i++) { 8457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = (*order)[i]; 8467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int bid = block->id(); 8477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("%5d:", i); 8487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < num_loops; i++) { 8497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool membership = loops[i].members->Contains(bid); 8507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool range = loops[i].header->LoopContains(block); 8517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF(membership ? " |" : " "); 8527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF(range ? "x" : " "); 8537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF(" B%d: ", bid); 8557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (block->loop_end_ >= 0) { 8567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF(" range: [%d, %d)", block->rpo_number_, block->loop_end_); 8577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org PrintF("\n"); 8597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 8617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgstatic void VerifySpecialRPO(int num_loops, LoopInfo* loops, 8647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlockVector* order) { 865e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(order->size() > 0); 866e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK((*order)[0]->id() == 0); // entry should be first. 8677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int i = 0; i < num_loops; i++) { 8697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* loop = &loops[i]; 8707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* header = loop->header; 8717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 872e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header != NULL); 873e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header->rpo_number_ >= 0); 874e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header->rpo_number_ < static_cast<int>(order->size())); 875e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header->loop_end_ >= 0); 876e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header->loop_end_ <= static_cast<int>(order->size())); 877e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(header->loop_end_ > header->rpo_number_); 8787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Verify the start ... end list relationship. 8807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int links = 0; 8817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* l = loop->start; 882e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(l != NULL && l->block == header); 8837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool end_found; 8847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (true) { 8857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (l == NULL || l == loop->end) { 8867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org end_found = (loop->end == l); 8877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 8887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 8897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // The list should be in same order as the final result. 890e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(l->block->rpo_number_ == links + loop->header->rpo_number_); 8917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org links++; 8927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org l = l->next; 893e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(links < static_cast<int>(2 * order->size())); // cycle? 8947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 895e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(links > 0); 896e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(links == (header->loop_end_ - header->rpo_number_)); 897e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(end_found); 8987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 8997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Check the contiguousness of loops. 9007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int count = 0; 9017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (int j = 0; j < static_cast<int>(order->size()); j++) { 9027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = order->at(j); 903e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->rpo_number_ == j); 9047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (j < header->rpo_number_ || j >= header->loop_end_) { 905e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(!loop->members->Contains(block->id())); 9067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 9077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (block == header) { 908e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(!loop->members->Contains(block->id())); 9097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 910e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(loop->members->Contains(block->id())); 9117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org count++; 9137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 915e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(links == count); 9167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 9187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#endif // DEBUG 9197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Compute the special reverse-post-order block ordering, which is essentially 9227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// a RPO of the graph where loop bodies are contiguous. Properties: 9237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// 1. If block A is a predecessor of B, then A appears before B in the order, 9247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// unless B is a loop header and A is in the loop headed at B 9257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// (i.e. A -> B is a backedge). 9267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// => If block A dominates block B, then A appears before B in the order. 9277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// => If block A is a loop header, A appears before all blocks in the loop 9287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// headed at A. 9297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// 2. All loops are contiguous in the order (i.e. no intervening blocks that 9307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// do not belong to the loop.) 9317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// Note a simple RPO traversal satisfies (1) but not (3). 93231c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.orgBasicBlockVector* Scheduler::ComputeSpecialRPO(Schedule* schedule) { 93331c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org Zone tmp_zone(schedule->zone()->isolate()); 93431c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org Zone* zone = &tmp_zone; 935e2a8937454723a720c81acc3f9e4162b18999b43machenbach@chromium.org Trace("------------- COMPUTING SPECIAL RPO ---------------\n"); 9367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // RPO should not have been computed for this schedule yet. 9375e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org CHECK_EQ(kBlockUnvisited1, schedule->start()->rpo_number_); 93831c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org CHECK_EQ(0, static_cast<int>(schedule->rpo_order_.size())); 9397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Perform an iterative RPO traversal using an explicit stack, 9417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // recording backedges that form cycles. O(|B|). 94231c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org ZoneList<std::pair<BasicBlock*, int> > backedges(1, zone); 9437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SpecialRPOStackFrame* stack = 94431c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org zone->NewArray<SpecialRPOStackFrame>(schedule->BasicBlockCount()); 9455e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org BasicBlock* entry = schedule->start(); 9467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* order = NULL; 9477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int stack_depth = Push(stack, 0, entry, kBlockUnvisited1); 9487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int num_loops = 0; 9497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (stack_depth > 0) { 9517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int current = stack_depth - 1; 9527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SpecialRPOStackFrame* frame = stack + current; 9537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (frame->index < frame->block->SuccessorCount()) { 9557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Process the next successor. 9567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* succ = frame->block->SuccessorAt(frame->index++); 9577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->rpo_number_ == kBlockVisited1) continue; 9587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->rpo_number_ == kBlockOnStack) { 9597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // The successor is on the stack, so this is a backedge (cycle). 9607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org backedges.Add( 96131c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org std::pair<BasicBlock*, int>(frame->block, frame->index - 1), zone); 9627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->loop_end_ < 0) { 9637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Assign a new loop number to the header if it doesn't have one. 9647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org succ->loop_end_ = num_loops++; 9657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 9677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Push the successor onto the stack. 968e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(succ->rpo_number_ == kBlockUnvisited1); 9697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited1); 9707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 9727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Finished with all successors; pop the stack and add the block. 97331c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org order = order->Add(zone, frame->block); 9747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org frame->block->rpo_number_ = kBlockVisited1; 9757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack_depth--; 9767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 9787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // If no loops were encountered, then the order we computed was correct. 9807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* loops = NULL; 9817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (num_loops != 0) { 9827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Otherwise, compute the loop information from the backedges in order 9837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // to perform a traversal that groups loop bodies together. 98431c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org loops = ComputeLoopInfo(zone, stack, num_loops, schedule->BasicBlockCount(), 98531c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org &backedges); 9867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Initialize the "loop stack". Note the entry could be a loop header. 9887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* loop = entry->IsLoopHeader() ? &loops[entry->loop_end_] : NULL; 9897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org order = NULL; 9907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 9917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Perform an iterative post-order traversal, visiting loop bodies before 9927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // edges that lead out of loops. Visits each block once, but linking loop 9937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // sections together is linear in the loop size, so overall is 9947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // O(|B| + max(loop_depth) * max(|loop|)) 9957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack_depth = Push(stack, 0, entry, kBlockUnvisited2); 9967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (stack_depth > 0) { 9977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SpecialRPOStackFrame* frame = stack + (stack_depth - 1); 9987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = frame->block; 9997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* succ = NULL; 10007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 10017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (frame->index < block->SuccessorCount()) { 10027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Process the next normal successor. 10037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org succ = block->SuccessorAt(frame->index++); 10047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else if (block->IsLoopHeader()) { 10057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Process additional outgoing edges from the loop header. 10067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (block->rpo_number_ == kBlockOnStack) { 10077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Finish the loop body the first time the header is left on the 10087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // stack. 1009e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(loop != NULL && loop->header == block); 101031c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org loop->start = order->Add(zone, block); 10117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org order = loop->end; 10127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->rpo_number_ = kBlockVisited2; 10137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Pop the loop stack and continue visiting outgoing edges within the 10147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // the context of the outer loop, if any. 10157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop = loop->prev; 10167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // We leave the loop header on the stack; the rest of this iteration 10177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // and later iterations will go through its outgoing edges list. 10187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 10207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Use the next outgoing edge if there are any. 10217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int outgoing_index = frame->index - block->SuccessorCount(); 10227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* info = &loops[block->loop_end_]; 1023e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(loop != info); 10247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (info->outgoing != NULL && 10257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org outgoing_index < info->outgoing->length()) { 10267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org succ = info->outgoing->at(outgoing_index); 10277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org frame->index++; 10287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 10317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ != NULL) { 10327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Process the next successor. 10337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->rpo_number_ == kBlockOnStack) continue; 10347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->rpo_number_ == kBlockVisited2) continue; 1035e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(succ->rpo_number_ == kBlockUnvisited2); 10367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (loop != NULL && !loop->members->Contains(succ->id())) { 10377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // The successor is not in the current loop or any nested loop. 10387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Add it to the outgoing edges of this loop and visit it later. 103931c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org loop->AddOutgoing(zone, succ); 10407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 10417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Push the successor onto the stack. 10427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack_depth = Push(stack, stack_depth, succ, kBlockUnvisited2); 10437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (succ->IsLoopHeader()) { 10447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Push the inner loop onto the loop stack. 1045e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(succ->loop_end_ >= 0 && succ->loop_end_ < num_loops); 10467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* next = &loops[succ->loop_end_]; 10477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org next->end = order; 10487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org next->prev = loop; 10497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop = next; 10507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 10537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Finished with all successors of the current block. 10547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (block->IsLoopHeader()) { 10557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // If we are going to pop a loop header, then add its entire body. 10567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* info = &loops[block->loop_end_]; 10577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (BlockList* l = info->start; true; l = l->next) { 10587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (l->next == info->end) { 10597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org l->next = order; 10607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org info->end = order; 10617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org break; 10627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org order = info->start; 10657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 10667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Pop a single node off the stack and add it to the order. 106731c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org order = order->Add(zone, block); 10687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->rpo_number_ = kBlockVisited2; 10697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org stack_depth--; 10717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 10747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 10757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Construct the final order from the list. 107631c0e32e19ad3df48525fa9e7b2d1c0c07496d00machenbach@chromium.org BasicBlockVector* final_order = &schedule->rpo_order_; 10777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org order->Serialize(final_order); 10787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 10797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Compute the correct loop header for every block and set the correct loop 10807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // ends. 10817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org LoopInfo* current_loop = NULL; 10827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* current_header = NULL; 10837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int loop_depth = 0; 10847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (BasicBlockVectorIter i = final_order->begin(); i != final_order->end(); 10857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org ++i) { 10867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* current = *i; 10877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current->loop_header_ = current_header; 10887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (current->IsLoopHeader()) { 10897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop_depth++; 10907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_loop = &loops[current->loop_end_]; 10917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BlockList* end = current_loop->end; 10927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current->loop_end_ = end == NULL ? static_cast<int>(final_order->size()) 10937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : end->block->rpo_number_; 10947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_header = current_loop->header; 1095fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("B%d is a loop header, increment loop depth to %d\n", current->id(), 1096fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org loop_depth); 10977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } else { 10987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org while (current_header != NULL && 10997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current->rpo_number_ >= current_header->loop_end_) { 1100e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(current_header->IsLoopHeader()); 1101e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(current_loop != NULL); 11027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_loop = current_loop->prev; 11037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current_header = current_loop == NULL ? NULL : current_loop->header; 11047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org --loop_depth; 11057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 11067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 11077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org current->loop_depth_ = loop_depth; 1108fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (current->loop_header_ == NULL) { 1109fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("B%d is not in a loop (depth == %d)\n", current->id(), 1110fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org current->loop_depth_); 1111fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } else { 1112fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org Trace("B%d has loop header B%d, (depth == %d)\n", current->id(), 1113fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org current->loop_header_->id(), current->loop_depth_); 1114fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 11157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 11167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 11177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#if DEBUG 11187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (FLAG_trace_turbo_scheduler) PrintRPO(num_loops, loops, final_order); 11197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org VerifySpecialRPO(num_loops, loops, final_order); 11207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#endif 11217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return final_order; 11227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 11237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 11247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 11257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} // namespace v8::internal::compiler 1126