schedule.h revision 3b9bc31999c9787eb726ecdbfd5796bfdec32a18
1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_COMPILER_SCHEDULE_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_COMPILER_SCHEDULE_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier#include <iosfwd> 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 10014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/zone-containers.h" 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 16014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Forward declarations. 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass BasicBlock; 18958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass BasicBlockInstrumentor; 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node; 20014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<BasicBlock*> BasicBlockVector; 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<Node*> NodeVector; 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 26958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A basic block contains an ordered list of nodes and ends with a control 27958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// node. Note that if a basic block has phis, then all phis must appear as the 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// first nodes in the block. 29014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass BasicBlock final : public ZoneObject { 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Possible control nodes that can end a block. 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch enum Control { 33014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kNone, // Control not initialized yet. 34014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kGoto, // Goto a single successor block. 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kCall, // Call with continuation as first successor, exception 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // second. 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kBranch, // Branch if true to first successor, otherwise second. 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kSwitch, // Table dispatch to one of the successor blocks. 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kDeoptimize, // Return a value from this method. 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kTailCall, // Tail call another method from this method. 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kReturn, // Return a value from this method. 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kThrow // Throw an exception. 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 45958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier class Id { 46958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 47958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int ToInt() const { return static_cast<int>(index_); } 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t ToSize() const { return index_; } 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static Id FromSize(size_t index) { return Id(index); } 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static Id FromInt(int index) { return Id(static_cast<size_t>(index)); } 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Id(size_t index) : index_(index) {} 54958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t index_; 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 57958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock(Zone* zone, Id id); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Id id() const { return id_; } 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Predecessors. 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector& predecessors() { return predecessors_; } 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const BasicBlockVector& predecessors() const { return predecessors_; } 64958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t PredecessorCount() const { return predecessors_.size(); } 65958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; } 66958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ClearPredecessors() { predecessors_.clear(); } 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddPredecessor(BasicBlock* predecessor); 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Successors. 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector& successors() { return successors_; } 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const BasicBlockVector& successors() const { return successors_; } 72958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t SuccessorCount() const { return successors_.size(); } 73958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* SuccessorAt(size_t index) { return successors_[index]; } 74958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ClearSuccessors() { successors_.clear(); } 75958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessor(BasicBlock* successor); 76958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Nodes in the basic block. 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node* value_type; 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool empty() const { return nodes_.empty(); } 80014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t size() const { return nodes_.size(); } 81958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* NodeAt(size_t index) { return nodes_[index]; } 82958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t NodeCount() const { return nodes_.size(); } 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch value_type& front() { return nodes_.front(); } 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch value_type const& front() const { return nodes_.front(); } 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::iterator iterator; 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch iterator begin() { return nodes_.begin(); } 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch iterator end() { return nodes_.end(); } 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::const_iterator const_iterator; 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const_iterator begin() const { return nodes_.begin(); } 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const_iterator end() const { return nodes_.end(); } 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::reverse_iterator reverse_iterator; 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reverse_iterator rbegin() { return nodes_.rbegin(); } 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reverse_iterator rend() { return nodes_.rend(); } 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 99958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddNode(Node* node); 100958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier template <class InputIterator> 101958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void InsertNodes(iterator insertion_point, InputIterator insertion_start, 102958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier InputIterator insertion_end) { 103958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodes_.insert(insertion_point, insertion_start, insertion_end); 104958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 105958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 106958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Accessors. 107958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Control control() const { return control_; } 108958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_control(Control control); 109958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 110958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* control_input() const { return control_input_; } 111958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_control_input(Node* control_input); 112958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 113958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool deferred() const { return deferred_; } 114958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_deferred(bool deferred) { deferred_ = deferred; } 115958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 116958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t dominator_depth() const { return dominator_depth_; } 117958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; } 118958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 119958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* dominator() const { return dominator_; } 120958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_dominator(BasicBlock* dominator) { dominator_ = dominator; } 121958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 122958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* rpo_next() const { return rpo_next_; } 123958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; } 124958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 125958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_header() const { return loop_header_; } 126958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_header(BasicBlock* loop_header); 127958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 128958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_end() const { return loop_end_; } 129958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_end(BasicBlock* loop_end); 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_depth() const { return loop_depth_; } 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_depth(int32_t loop_depth); 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 134958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_number() const { return loop_number_; } 135958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; } 136958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t rpo_number() const { return rpo_number_; } 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_rpo_number(int32_t rpo_number); 139958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 140958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Loop membership helpers. 141014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline bool IsLoopHeader() const { return loop_end_ != nullptr; } 142958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool LoopContains(BasicBlock* block) const; 143958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 144014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Computes the immediate common dominator of {b1} and {b2}. The worst time 145014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // complexity is O(N) where N is the height of the dominator tree. 146014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); 147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 149958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_number_; // loop number of the block. 150958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t rpo_number_; // special RPO number of the block. 151958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool deferred_; // true if the block contains deferred code. 152958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t dominator_depth_; // Depth within the dominator tree. 153958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* dominator_; // Immediate dominator of the block. 154958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* rpo_next_; // Link to next block in special RPO order. 155958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_header_; // Pointer to dominating loop header basic block, 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // nullptr if none. For loop headers, this points to 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // enclosing loop header. 158958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_end_; // end of the loop, if this block is a loop header. 159958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_depth_; // loop nesting, 0 is top-level 160958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 161958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Control control_; // Control at the end of the block. 162958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* control_input_; // Input value for control. 163958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier NodeVector nodes_; // nodes of this block in forward order. 164958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector successors_; 166014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector predecessors_; 167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Id id_; 168958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DISALLOW_COPY_AND_ASSIGN(BasicBlock); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 172014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream&, const BasicBlock::Control&); 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream&, const BasicBlock::Id&); 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A schedule represents the result of assigning nodes to basic blocks 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// and ordering them within basic blocks. Prior to computing a schedule, 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// a graph has no notion of control flow ordering other than that induced 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// by the graph's dependencies. A schedule is required to generate code. 180014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Schedule final : public ZoneObject { 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 182958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Schedule(Zone* zone, size_t node_count_hint = 0); 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return the block which contains {node}, if any. 185958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* block(Node* node) const; 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 187958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool IsScheduled(Node* node); 188958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* GetBlockById(BasicBlock::Id block_id); 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 190958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t BasicBlockCount() const { return all_blocks_.size(); } 191958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t RpoBlockCount() const { return rpo_order_.size(); } 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Check if nodes {a} and {b} are in the same block. 194958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool SameBasicBlock(Node* a, Node* b) const; 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: create a new block. 197958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* NewBasicBlock(); 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: records that a node will later be added to a block but 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // doesn't actually add the node to the block. 201958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void PlanNode(BasicBlock* block, Node* node); 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a node to the end of the block. 204958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddNode(BasicBlock* block, Node* node); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a goto to the end of {block}. 207958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddGoto(BasicBlock* block, BasicBlock* succ); 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 209014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a call at the end of {block}. 210014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 211014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock* exception_block); 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 213b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a branch at the end of {block}. 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 215958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* fblock); 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 217014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a switch at the end of {block}. 218014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 219014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t succ_count); 220014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 221014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a deoptimize at the end of {block}. 222014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddDeoptimize(BasicBlock* block, Node* input); 223014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 224014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a tailcall at the end of {block}. 225014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddTailCall(BasicBlock* block, Node* input); 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a return at the end of {block}. 228958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddReturn(BasicBlock* block, Node* input); 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a throw at the end of {block}. 231958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddThrow(BasicBlock* block, Node* input); 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 233958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // BasicBlock mutation: insert a branch into the end of {block}. 234958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 235958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* tblock, BasicBlock* fblock); 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 237014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock mutation: insert a switch into the end of {block}. 238014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 239014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock** succ_blocks, size_t succ_count); 240014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 241958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Exposed publicly for testing only. 242958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) { 243958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return AddSuccessor(block, succ); 244b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2463b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const BasicBlockVector* all_blocks() const { return &all_blocks_; } 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector* rpo_order() { return &rpo_order_; } 248958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const BasicBlockVector* rpo_order() const { return &rpo_order_; } 249958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 250958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* start() { return start_; } 251958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* end() { return end_; } 252958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 253958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* zone() const { return zone_; } 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 256958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Scheduler; 257958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class BasicBlockInstrumentor; 2583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch friend class RawMachineAssembler; 2593b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 2603b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Ensure split-edge form for a hand-assembled schedule. 2613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch void EnsureSplitEdgeForm(); 2623b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Copy deferred block markers down as far as possible 2633b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch void PropagateDeferredMark(); 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 265958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessor(BasicBlock* block, BasicBlock* succ); 266958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void MoveSuccessors(BasicBlock* from, BasicBlock* to); 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 268958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void SetControlInput(BasicBlock* block, Node* node); 269958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void SetBlockForNode(BasicBlock* block, Node* node); 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone_; 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector all_blocks_; // All basic blocks in the schedule. 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector nodeid_to_block_; // Map from node to containing block. 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector rpo_order_; // Reverse-post-order block list. 275958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* start_; 276958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* end_; 277958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 278958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(Schedule); 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 281014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream&, const Schedule&); 282958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 283958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 284958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 285958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_COMPILER_SCHEDULE_H_ 288