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 10c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/base/compiler-specific.h" 11c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/globals.h" 12f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace compiler { 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Forward declarations. 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass BasicBlock; 20958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernierclass BasicBlockInstrumentor; 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node; 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<BasicBlock*> BasicBlockVector; 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochtypedef ZoneVector<Node*> NodeVector; 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 28958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// A basic block contains an ordered list of nodes and ends with a control 29958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// node. Note that if a basic block has phis, then all phis must appear as the 30958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier// first nodes in the block. 31c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE BasicBlock final 32c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch : public NON_EXPORTED_BASE(ZoneObject) { 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Possible control nodes that can end a block. 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch enum Control { 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kNone, // Control not initialized yet. 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kGoto, // Goto a single successor block. 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kCall, // Call with continuation as first successor, exception 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // second. 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kBranch, // Branch if true to first successor, otherwise second. 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kSwitch, // Table dispatch to one of the successor blocks. 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kDeoptimize, // Return a value from this method. 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kTailCall, // Tail call another method from this method. 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kReturn, // Return a value from this method. 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch kThrow // Throw an exception. 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 48958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier class Id { 49958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier public: 50958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int ToInt() const { return static_cast<int>(index_); } 51958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t ToSize() const { return index_; } 52958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static Id FromSize(size_t index) { return Id(index); } 53958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier static Id FromInt(int index) { return Id(static_cast<size_t>(index)); } 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 55958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier private: 56958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Id(size_t index) : index_(index) {} 57958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t index_; 58958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier }; 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 60958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock(Zone* zone, Id id); 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 62958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Id id() const { return id_; } 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Predecessors. 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector& predecessors() { return predecessors_; } 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const BasicBlockVector& predecessors() const { return predecessors_; } 67958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t PredecessorCount() const { return predecessors_.size(); } 68958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; } 69958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ClearPredecessors() { predecessors_.clear(); } 70958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddPredecessor(BasicBlock* predecessor); 71958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Successors. 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector& successors() { return successors_; } 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const BasicBlockVector& successors() const { return successors_; } 75958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t SuccessorCount() const { return successors_.size(); } 76958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* SuccessorAt(size_t index) { return successors_[index]; } 77958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void ClearSuccessors() { successors_.clear(); } 78958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessor(BasicBlock* successor); 79958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 80958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Nodes in the basic block. 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch typedef Node* value_type; 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool empty() const { return nodes_.empty(); } 83014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t size() const { return nodes_.size(); } 84958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* NodeAt(size_t index) { return nodes_[index]; } 85958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t NodeCount() const { return nodes_.size(); } 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch value_type& front() { return nodes_.front(); } 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch value_type const& front() const { return nodes_.front(); } 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::iterator iterator; 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch iterator begin() { return nodes_.begin(); } 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch iterator end() { return nodes_.end(); } 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::const_iterator const_iterator; 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const_iterator begin() const { return nodes_.begin(); } 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const_iterator end() const { return nodes_.end(); } 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef NodeVector::reverse_iterator reverse_iterator; 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reverse_iterator rbegin() { return nodes_.rbegin(); } 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch reverse_iterator rend() { return nodes_.rend(); } 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 102958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddNode(Node* node); 103958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier template <class InputIterator> 104958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void InsertNodes(iterator insertion_point, InputIterator insertion_start, 105958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier InputIterator insertion_end) { 106958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier nodes_.insert(insertion_point, insertion_start, insertion_end); 107958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier } 108958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 109958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Accessors. 110958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Control control() const { return control_; } 111958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_control(Control control); 112958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 113958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* control_input() const { return control_input_; } 114958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_control_input(Node* control_input); 115958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 116958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool deferred() const { return deferred_; } 117958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_deferred(bool deferred) { deferred_ = deferred; } 118958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 119958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t dominator_depth() const { return dominator_depth_; } 120958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; } 121958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 122958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* dominator() const { return dominator_; } 123958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_dominator(BasicBlock* dominator) { dominator_ = dominator; } 124958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 125958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* rpo_next() const { return rpo_next_; } 126958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; } 127958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 128958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_header() const { return loop_header_; } 129958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_header(BasicBlock* loop_header); 130958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 131958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_end() const { return loop_end_; } 132958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_end(BasicBlock* loop_end); 133958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 134958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_depth() const { return loop_depth_; } 135958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_depth(int32_t loop_depth); 136958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 137958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_number() const { return loop_number_; } 138958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; } 139958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 140958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t rpo_number() const { return rpo_number_; } 141958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void set_rpo_number(int32_t rpo_number); 142958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 143958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Loop membership helpers. 144014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch inline bool IsLoopHeader() const { return loop_end_ != nullptr; } 145958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool LoopContains(BasicBlock* block) const; 146958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Computes the immediate common dominator of {b1} and {b2}. The worst time 148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // complexity is O(N) where N is the height of the dominator tree. 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); 150014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 152958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_number_; // loop number of the block. 153958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t rpo_number_; // special RPO number of the block. 154958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool deferred_; // true if the block contains deferred code. 155958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t dominator_depth_; // Depth within the dominator tree. 156958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* dominator_; // Immediate dominator of the block. 157958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* rpo_next_; // Link to next block in special RPO order. 158958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_header_; // Pointer to dominating loop header basic block, 159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // nullptr if none. For loop headers, this points to 160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // enclosing loop header. 161958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* loop_end_; // end of the loop, if this block is a loop header. 162958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier int32_t loop_depth_; // loop nesting, 0 is top-level 163958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 164958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Control control_; // Control at the end of the block. 165958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Node* control_input_; // Input value for control. 166958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier NodeVector nodes_; // nodes of this block in forward order. 167958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 168014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector successors_; 169014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlockVector predecessors_; 170958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Id id_; 171958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DISALLOW_COPY_AND_ASSIGN(BasicBlock); 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 175014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream&, const BasicBlock::Control&); 176014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochstd::ostream& operator<<(std::ostream&, const BasicBlock::Id&); 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A schedule represents the result of assigning nodes to basic blocks 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// and ordering them within basic blocks. Prior to computing a schedule, 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// a graph has no notion of control flow ordering other than that induced 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// by the graph's dependencies. A schedule is required to generate code. 183c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE Schedule final : public NON_EXPORTED_BASE(ZoneObject) { 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 185958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier explicit Schedule(Zone* zone, size_t node_count_hint = 0); 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Return the block which contains {node}, if any. 188958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* block(Node* node) const; 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 190958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool IsScheduled(Node* node); 191958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* GetBlockById(BasicBlock::Id block_id); 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 193958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t BasicBlockCount() const { return all_blocks_.size(); } 194958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier size_t RpoBlockCount() const { return rpo_order_.size(); } 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Check if nodes {a} and {b} are in the same block. 197958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier bool SameBasicBlock(Node* a, Node* b) const; 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: create a new block. 200958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* NewBasicBlock(); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: records that a node will later be added to a block but 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // doesn't actually add the node to the block. 204958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void PlanNode(BasicBlock* block, Node* node); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a node to the end of the block. 207958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddNode(BasicBlock* block, Node* node); 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a goto to the end of {block}. 210958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddGoto(BasicBlock* block, BasicBlock* succ); 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 212014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a call at the end of {block}. 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 214014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock* exception_block); 215014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a branch at the end of {block}. 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 218958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* fblock); 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 220014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a switch at the end of {block}. 221014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 222014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t succ_count); 223014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 224014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a deoptimize at the end of {block}. 225014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddDeoptimize(BasicBlock* block, Node* input); 226014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 227014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock building: add a tailcall at the end of {block}. 228014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddTailCall(BasicBlock* block, Node* input); 229014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a return at the end of {block}. 231958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddReturn(BasicBlock* block, Node* input); 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // BasicBlock building: add a throw at the end of {block}. 234958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddThrow(BasicBlock* block, Node* input); 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 236958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // BasicBlock mutation: insert a branch into the end of {block}. 237958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 238958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* tblock, BasicBlock* fblock); 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 240014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // BasicBlock mutation: insert a switch into the end of {block}. 241014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 242014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BasicBlock** succ_blocks, size_t succ_count); 243014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 244958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier // Exposed publicly for testing only. 245958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) { 246958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier return AddSuccessor(block, succ); 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2493b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const BasicBlockVector* all_blocks() const { return &all_blocks_; } 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector* rpo_order() { return &rpo_order_; } 251958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier const BasicBlockVector* rpo_order() const { return &rpo_order_; } 252958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 253958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* start() { return start_; } 254958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* end() { return end_; } 255958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 256958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier Zone* zone() const { return zone_; } 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 259958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class Scheduler; 260958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier friend class BasicBlockInstrumentor; 2613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch friend class RawMachineAssembler; 2623b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch 263bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // Ensure properties of the CFG assumed by further stages. 264bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnsureCFGWellFormedness(); 2653b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Ensure split-edge form for a hand-assembled schedule. 266bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnsureSplitEdgeForm(BasicBlock* block); 267bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch // Ensure entry into a deferred block happens from a single hot block. 268bcf72ee8e3b26f1d0726869c7ddb3921c68b09a8Ben Murdoch void EnsureDeferredCodeSingleEntryPoint(BasicBlock* block); 2693b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // Copy deferred block markers down as far as possible 2703b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch void PropagateDeferredMark(); 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 272958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void AddSuccessor(BasicBlock* block, BasicBlock* succ); 273958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void MoveSuccessors(BasicBlock* from, BasicBlock* to); 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 275958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void SetControlInput(BasicBlock* block, Node* node); 276958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier void SetBlockForNode(BasicBlock* block, Node* node); 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Zone* zone_; 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector all_blocks_; // All basic blocks in the schedule. 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector nodeid_to_block_; // Map from node to containing block. 281b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch BasicBlockVector rpo_order_; // Reverse-post-order block list. 282958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* start_; 283958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier BasicBlock* end_; 284958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 285958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier DISALLOW_COPY_AND_ASSIGN(Schedule); 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 288c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen MurdochV8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream&, const Schedule&); 289958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier 290958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace compiler 291958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace internal 292958fae7ec3f466955f8e5b50fa5b8d38b9e91675Emily Bernier} // namespace v8 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_COMPILER_SCHEDULE_H_ 295