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 57d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#ifndef V8_COMPILER_SCHEDULE_H_ 67d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#define V8_COMPILER_SCHEDULE_H_ 77d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 87d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include <vector> 97d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/v8.h" 117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-algorithm.h" 137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-graph.h" 147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-node.h" 157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/generic-node-inl.h" 167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/node.h" 177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/compiler/opcodes.h" 187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/zone.h" 197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace v8 { 217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace internal { 227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgnamespace compiler { 237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass BasicBlock; 257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass Graph; 267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass ConstructScheduleData; 277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass CodeGenerator; // Because of a namespace bug in clang. 287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass BasicBlockData { 307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Possible control nodes that can end a block. 327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org enum Control { 33ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org kNone, // Control not initialized yet. 34ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org kGoto, // Goto a single successor block. 35ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org kBranch, // Branch if true to first successor, otherwise second. 36ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org kReturn, // Return a value from this method. 37ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.org kThrow // Throw an exception. 387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org }; 397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int32_t rpo_number_; // special RPO number of the block. 41fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org BasicBlock* dominator_; // Immediate dominator of the block. 427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* loop_header_; // Pointer to dominating loop header basic block, 437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // NULL if none. For loop headers, this points to 447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // enclosing loop header. 457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int32_t loop_depth_; // loop nesting, 0 is top-level 467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int32_t loop_end_; // end of the loop, if this block is a loop header. 477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int32_t code_start_; // start index of arch-specific code. 487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int32_t code_end_; // end index of arch-specific code. 497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool deferred_; // {true} if this block is considered the slow 507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // path. 517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Control control_; // Control at the end of the block. 527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Node* control_input_; // Input value for control. 537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NodeVector nodes_; // nodes of this block in forward order. 547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit BasicBlockData(Zone* zone) 567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : rpo_number_(-1), 57fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org dominator_(NULL), 587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop_header_(NULL), 597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop_depth_(0), 607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org loop_end_(-1), 617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org code_start_(-1), 627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org code_end_(-1), 637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org deferred_(false), 647d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org control_(kNone), 657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org control_input_(NULL), 66fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org nodes_(zone) {} 677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline bool IsLoopHeader() const { return loop_end_ >= 0; } 697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline bool LoopContains(BasicBlockData* block) const { 707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // RPO numbers must be initialized. 71e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(rpo_number_ >= 0); 72e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->rpo_number_ >= 0); 737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (loop_end_ < 0) return false; // This is not a loop. 747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return block->rpo_number_ >= rpo_number_ && block->rpo_number_ < loop_end_; 757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int first_instruction_index() { 77e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_start_ >= 0); 78e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_end_ > 0); 79e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_end_ >= code_start_); 807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return code_start_; 817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int last_instruction_index() { 83e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_start_ >= 0); 84e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_end_ > 0); 85e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(code_end_ >= code_start_); 867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return code_end_ - 1; 877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgOStream& operator<<(OStream& os, const BasicBlockData::Control& c); 917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// A basic block contains an ordered list of nodes and ends with a control 937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// node. Note that if a basic block has phis, then all phis must appear as the 947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// first nodes in the block. 95ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.orgclass BasicBlock FINAL : public GenericNode<BasicBlockData, BasicBlock> { 967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock(GenericGraphBase* graph, int input_count) 987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : GenericNode<BasicBlockData, BasicBlock>(graph, input_count) {} 997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef Uses Successors; 1017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef Inputs Predecessors; 1027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Successors successors() { return static_cast<Successors>(uses()); } 1047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Predecessors predecessors() { return static_cast<Predecessors>(inputs()); } 1057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int PredecessorCount() { return InputCount(); } 1077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* PredecessorAt(int index) { return InputAt(index); } 1087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int SuccessorCount() { return UseCount(); } 1107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* SuccessorAt(int index) { return UseAt(index); } 1117d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int PredecessorIndexOf(BasicBlock* predecessor) { 1137d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock::Predecessors predecessors = this->predecessors(); 1147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org for (BasicBlock::Predecessors::iterator i = predecessors.begin(); 1157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org i != predecessors.end(); ++i) { 1167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (*i == predecessor) return i.index(); 1177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return -1; 1197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1207d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1217d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline BasicBlock* loop_header() { 1227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return static_cast<BasicBlock*>(loop_header_); 1237d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline BasicBlock* ContainingLoop() { 1257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (IsLoopHeader()) return this; 1267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return static_cast<BasicBlock*>(loop_header_); 1277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef NodeVector::iterator iterator; 1307d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org iterator begin() { return nodes_.begin(); } 1317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org iterator end() { return nodes_.end(); } 1327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef NodeVector::const_iterator const_iterator; 1347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org const_iterator begin() const { return nodes_.begin(); } 1357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org const_iterator end() const { return nodes_.end(); } 1367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef NodeVector::reverse_iterator reverse_iterator; 1387d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org reverse_iterator rbegin() { return nodes_.rbegin(); } 1397d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org reverse_iterator rend() { return nodes_.rend(); } 1407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 1427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org DISALLOW_COPY_AND_ASSIGN(BasicBlock); 1437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 1447d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1457d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgtypedef GenericGraphVisit::NullNodeVisitor<BasicBlockData, BasicBlock> 1467d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org NullBasicBlockVisitor; 1477d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 148fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.orgtypedef ZoneVector<BasicBlock*> BasicBlockVector; 1497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgtypedef BasicBlockVector::iterator BasicBlockVectorIter; 1507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgtypedef BasicBlockVector::reverse_iterator BasicBlockVectorRIter; 1517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1527d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// A schedule represents the result of assigning nodes to basic blocks 1537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// and ordering them within basic blocks. Prior to computing a schedule, 1547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// a graph has no notion of control flow ordering other than that induced 1557d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org// by the graph's dependencies. A schedule is required to generate code. 1567d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass Schedule : public GenericGraph<BasicBlock> { 1577d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org public: 1587d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org explicit Schedule(Zone* zone) 1597d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org : GenericGraph<BasicBlock>(zone), 1607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org zone_(zone), 161fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org all_blocks_(zone), 162fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org nodeid_to_block_(zone), 163fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org rpo_order_(zone) { 1645e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org SetStart(NewBasicBlock()); // entry. 1655e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org SetEnd(NewBasicBlock()); // exit. 1667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1677d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Return the block which contains {node}, if any. 1697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block(Node* node) const { 1707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { 1717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return nodeid_to_block_[node->id()]; 1727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return NULL; 1747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org bool IsScheduled(Node* node) { 1777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int length = static_cast<int>(nodeid_to_block_.size()); 1787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (node->id() >= length) return false; 1797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return nodeid_to_block_[node->id()] != NULL; 1807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; } 1837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int BasicBlockCount() const { return NodeCount(); } 1857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); } 1867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org typedef ContainerPointerWrapper<BasicBlockVector> BasicBlocks; 1887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Return a list of all the blocks in the schedule, in arbitrary order. 1907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlocks all_blocks() { return BasicBlocks(&all_blocks_); } 1917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // Check if nodes {a} and {b} are in the same block. 1937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline bool SameBasicBlock(Node* a, Node* b) const { 1947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = this->block(a); 1957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return block != NULL && block == this->block(b); 1967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 1977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 1987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: create a new block. 1997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline BasicBlock* NewBasicBlock() { 2007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* block = 2017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL)); 2027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org all_blocks_.push_back(block); 2037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org return block; 2047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: records that a node will later be added to a block but 2077d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // doesn't actually add the node to the block. 2087d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline void PlanNode(BasicBlock* block, Node* node) { 2097d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (FLAG_trace_turbo_scheduler) { 210fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org PrintF("Planning #%d:%s for future add to B%d\n", node->id(), 211fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org node->op()->mnemonic(), block->id()); 2127d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 213e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(this->block(node) == NULL); 2147d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetBlockForNode(block, node); 2157d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2167d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2177d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: add a node to the end of the block. 2187d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org inline void AddNode(BasicBlock* block, Node* node) { 2197d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (FLAG_trace_turbo_scheduler) { 220fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(), 221fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org block->id()); 2227d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 223e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(this->block(node) == NULL || this->block(node) == block); 2247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->nodes_.push_back(node); 2257d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetBlockForNode(block, node); 2267d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2277d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2287d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: add a goto to the end of {block}. 2297d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddGoto(BasicBlock* block, BasicBlock* succ) { 230e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->control_ == BasicBlock::kNone); 2317d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->control_ = BasicBlock::kGoto; 2327d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org AddSuccessor(block, succ); 2337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2347d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2357d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: add a branch at the end of {block}. 2367d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 2377d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlock* fblock) { 238e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->control_ == BasicBlock::kNone); 239e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(branch->opcode() == IrOpcode::kBranch); 2407d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->control_ = BasicBlock::kBranch; 2417d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org AddSuccessor(block, tblock); 2427d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org AddSuccessor(block, fblock); 2437d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetControlInput(block, branch); 244fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (branch->opcode() == IrOpcode::kBranch) { 245fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // TODO(titzer): require a Branch node here. (sloppy tests). 246fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SetBlockForNode(block, branch); 247fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 2487d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2497d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2507d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: add a return at the end of {block}. 2517d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddReturn(BasicBlock* block, Node* input) { 252e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->control_ == BasicBlock::kNone); 2537d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->control_ = BasicBlock::kReturn; 2547d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetControlInput(block, input); 2555e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org if (block != end()) AddSuccessor(block, end()); 256fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org if (input->opcode() == IrOpcode::kReturn) { 257fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org // TODO(titzer): require a Return node here. (sloppy tests). 258fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org SetBlockForNode(block, input); 259fa7f914e3bacba481b13da5cf2bc4c935567ebc4machenbach@chromium.org } 2607d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2617d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2627d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org // BasicBlock building: add a throw at the end of {block}. 2637d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddThrow(BasicBlock* block, Node* input) { 264e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(block->control_ == BasicBlock::kNone); 2657d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->control_ = BasicBlock::kThrow; 2667d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetControlInput(block, input); 2675e57059e20217fd540b60c237d326414afe2171emachenbach@chromium.org if (block != end()) AddSuccessor(block, end()); 2687d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2697d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2707d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org friend class Scheduler; 2717d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org friend class CodeGenerator; 2727d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2737d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void AddSuccessor(BasicBlock* block, BasicBlock* succ) { 2747d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org succ->AppendInput(zone_, block); 2757d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2767d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2777d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlockVector* rpo_order() { return &rpo_order_; } 2787d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2797d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org private: 2807d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org friend class ScheduleVisualizer; 2817d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2827d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void SetControlInput(BasicBlock* block, Node* node) { 2837d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org block->control_input_ = node; 2847d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org SetBlockForNode(block, node); 2857d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2867d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2877d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org void SetBlockForNode(BasicBlock* block, Node* node) { 2887d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org int length = static_cast<int>(nodeid_to_block_.size()); 2897d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org if (node->id() >= length) { 2907d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org nodeid_to_block_.resize(node->id() + 1); 2917d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2927d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org nodeid_to_block_[node->id()] = block; 2937d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org } 2947d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 2957d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org Zone* zone_; 2967d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlockVector all_blocks_; // All basic blocks in the schedule. 2977d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlockVector nodeid_to_block_; // Map from node to containing block. 2987d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org BasicBlockVector rpo_order_; // Reverse-post-order block list. 2997d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org}; 3007d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3017d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgOStream& operator<<(OStream& os, const Schedule& s); 3027d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 3037d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} 3047d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org} // namespace v8::internal::compiler 3057d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org 3067d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#endif // V8_COMPILER_SCHEDULE_H_ 307