1 // Copyright 2013 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_COMPILER_SCHEDULE_H_ 6 #define V8_COMPILER_SCHEDULE_H_ 7 8 #include <iosfwd> 9 10 #include "src/zone-containers.h" 11 12 namespace v8 { 13 namespace internal { 14 namespace compiler { 15 16 // Forward declarations. 17 class BasicBlock; 18 class BasicBlockInstrumentor; 19 class Node; 20 21 22 typedef ZoneVector<BasicBlock*> BasicBlockVector; 23 typedef ZoneVector<Node*> NodeVector; 24 25 26 // A basic block contains an ordered list of nodes and ends with a control 27 // node. Note that if a basic block has phis, then all phis must appear as the 28 // first nodes in the block. 29 class BasicBlock final : public ZoneObject { 30 public: 31 // Possible control nodes that can end a block. 32 enum Control { 33 kNone, // Control not initialized yet. 34 kGoto, // Goto a single successor block. 35 kCall, // Call with continuation as first successor, exception 36 // second. 37 kBranch, // Branch if true to first successor, otherwise second. 38 kSwitch, // Table dispatch to one of the successor blocks. 39 kDeoptimize, // Return a value from this method. 40 kTailCall, // Tail call another method from this method. 41 kReturn, // Return a value from this method. 42 kThrow // Throw an exception. 43 }; 44 45 class Id { 46 public: 47 int ToInt() const { return static_cast<int>(index_); } 48 size_t ToSize() const { return index_; } 49 static Id FromSize(size_t index) { return Id(index); } 50 static Id FromInt(int index) { return Id(static_cast<size_t>(index)); } 51 52 private: 53 explicit Id(size_t index) : index_(index) {} 54 size_t index_; 55 }; 56 57 BasicBlock(Zone* zone, Id id); 58 59 Id id() const { return id_; } 60 61 // Predecessors. 62 BasicBlockVector& predecessors() { return predecessors_; } 63 const BasicBlockVector& predecessors() const { return predecessors_; } 64 size_t PredecessorCount() const { return predecessors_.size(); } 65 BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; } 66 void ClearPredecessors() { predecessors_.clear(); } 67 void AddPredecessor(BasicBlock* predecessor); 68 69 // Successors. 70 BasicBlockVector& successors() { return successors_; } 71 const BasicBlockVector& successors() const { return successors_; } 72 size_t SuccessorCount() const { return successors_.size(); } 73 BasicBlock* SuccessorAt(size_t index) { return successors_[index]; } 74 void ClearSuccessors() { successors_.clear(); } 75 void AddSuccessor(BasicBlock* successor); 76 77 // Nodes in the basic block. 78 typedef Node* value_type; 79 bool empty() const { return nodes_.empty(); } 80 size_t size() const { return nodes_.size(); } 81 Node* NodeAt(size_t index) { return nodes_[index]; } 82 size_t NodeCount() const { return nodes_.size(); } 83 84 value_type& front() { return nodes_.front(); } 85 value_type const& front() const { return nodes_.front(); } 86 87 typedef NodeVector::iterator iterator; 88 iterator begin() { return nodes_.begin(); } 89 iterator end() { return nodes_.end(); } 90 91 typedef NodeVector::const_iterator const_iterator; 92 const_iterator begin() const { return nodes_.begin(); } 93 const_iterator end() const { return nodes_.end(); } 94 95 typedef NodeVector::reverse_iterator reverse_iterator; 96 reverse_iterator rbegin() { return nodes_.rbegin(); } 97 reverse_iterator rend() { return nodes_.rend(); } 98 99 void AddNode(Node* node); 100 template <class InputIterator> 101 void InsertNodes(iterator insertion_point, InputIterator insertion_start, 102 InputIterator insertion_end) { 103 nodes_.insert(insertion_point, insertion_start, insertion_end); 104 } 105 106 // Accessors. 107 Control control() const { return control_; } 108 void set_control(Control control); 109 110 Node* control_input() const { return control_input_; } 111 void set_control_input(Node* control_input); 112 113 bool deferred() const { return deferred_; } 114 void set_deferred(bool deferred) { deferred_ = deferred; } 115 116 int32_t dominator_depth() const { return dominator_depth_; } 117 void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; } 118 119 BasicBlock* dominator() const { return dominator_; } 120 void set_dominator(BasicBlock* dominator) { dominator_ = dominator; } 121 122 BasicBlock* rpo_next() const { return rpo_next_; } 123 void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; } 124 125 BasicBlock* loop_header() const { return loop_header_; } 126 void set_loop_header(BasicBlock* loop_header); 127 128 BasicBlock* loop_end() const { return loop_end_; } 129 void set_loop_end(BasicBlock* loop_end); 130 131 int32_t loop_depth() const { return loop_depth_; } 132 void set_loop_depth(int32_t loop_depth); 133 134 int32_t loop_number() const { return loop_number_; } 135 void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; } 136 137 int32_t rpo_number() const { return rpo_number_; } 138 void set_rpo_number(int32_t rpo_number); 139 140 // Loop membership helpers. 141 inline bool IsLoopHeader() const { return loop_end_ != nullptr; } 142 bool LoopContains(BasicBlock* block) const; 143 144 // Computes the immediate common dominator of {b1} and {b2}. The worst time 145 // complexity is O(N) where N is the height of the dominator tree. 146 static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); 147 148 private: 149 int32_t loop_number_; // loop number of the block. 150 int32_t rpo_number_; // special RPO number of the block. 151 bool deferred_; // true if the block contains deferred code. 152 int32_t dominator_depth_; // Depth within the dominator tree. 153 BasicBlock* dominator_; // Immediate dominator of the block. 154 BasicBlock* rpo_next_; // Link to next block in special RPO order. 155 BasicBlock* loop_header_; // Pointer to dominating loop header basic block, 156 // nullptr if none. For loop headers, this points to 157 // enclosing loop header. 158 BasicBlock* loop_end_; // end of the loop, if this block is a loop header. 159 int32_t loop_depth_; // loop nesting, 0 is top-level 160 161 Control control_; // Control at the end of the block. 162 Node* control_input_; // Input value for control. 163 NodeVector nodes_; // nodes of this block in forward order. 164 165 BasicBlockVector successors_; 166 BasicBlockVector predecessors_; 167 Id id_; 168 169 DISALLOW_COPY_AND_ASSIGN(BasicBlock); 170 }; 171 172 std::ostream& operator<<(std::ostream&, const BasicBlock::Control&); 173 std::ostream& operator<<(std::ostream&, const BasicBlock::Id&); 174 175 176 // A schedule represents the result of assigning nodes to basic blocks 177 // and ordering them within basic blocks. Prior to computing a schedule, 178 // a graph has no notion of control flow ordering other than that induced 179 // by the graph's dependencies. A schedule is required to generate code. 180 class Schedule final : public ZoneObject { 181 public: 182 explicit Schedule(Zone* zone, size_t node_count_hint = 0); 183 184 // Return the block which contains {node}, if any. 185 BasicBlock* block(Node* node) const; 186 187 bool IsScheduled(Node* node); 188 BasicBlock* GetBlockById(BasicBlock::Id block_id); 189 190 size_t BasicBlockCount() const { return all_blocks_.size(); } 191 size_t RpoBlockCount() const { return rpo_order_.size(); } 192 193 // Check if nodes {a} and {b} are in the same block. 194 bool SameBasicBlock(Node* a, Node* b) const; 195 196 // BasicBlock building: create a new block. 197 BasicBlock* NewBasicBlock(); 198 199 // BasicBlock building: records that a node will later be added to a block but 200 // doesn't actually add the node to the block. 201 void PlanNode(BasicBlock* block, Node* node); 202 203 // BasicBlock building: add a node to the end of the block. 204 void AddNode(BasicBlock* block, Node* node); 205 206 // BasicBlock building: add a goto to the end of {block}. 207 void AddGoto(BasicBlock* block, BasicBlock* succ); 208 209 // BasicBlock building: add a call at the end of {block}. 210 void AddCall(BasicBlock* block, Node* call, BasicBlock* success_block, 211 BasicBlock* exception_block); 212 213 // BasicBlock building: add a branch at the end of {block}. 214 void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, 215 BasicBlock* fblock); 216 217 // BasicBlock building: add a switch at the end of {block}. 218 void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks, 219 size_t succ_count); 220 221 // BasicBlock building: add a deoptimize at the end of {block}. 222 void AddDeoptimize(BasicBlock* block, Node* input); 223 224 // BasicBlock building: add a tailcall at the end of {block}. 225 void AddTailCall(BasicBlock* block, Node* input); 226 227 // BasicBlock building: add a return at the end of {block}. 228 void AddReturn(BasicBlock* block, Node* input); 229 230 // BasicBlock building: add a throw at the end of {block}. 231 void AddThrow(BasicBlock* block, Node* input); 232 233 // BasicBlock mutation: insert a branch into the end of {block}. 234 void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch, 235 BasicBlock* tblock, BasicBlock* fblock); 236 237 // BasicBlock mutation: insert a switch into the end of {block}. 238 void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw, 239 BasicBlock** succ_blocks, size_t succ_count); 240 241 // Exposed publicly for testing only. 242 void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) { 243 return AddSuccessor(block, succ); 244 } 245 246 const BasicBlockVector* all_blocks() const { return &all_blocks_; } 247 BasicBlockVector* rpo_order() { return &rpo_order_; } 248 const BasicBlockVector* rpo_order() const { return &rpo_order_; } 249 250 BasicBlock* start() { return start_; } 251 BasicBlock* end() { return end_; } 252 253 Zone* zone() const { return zone_; } 254 255 private: 256 friend class Scheduler; 257 friend class BasicBlockInstrumentor; 258 friend class RawMachineAssembler; 259 260 // Ensure properties of the CFG assumed by further stages. 261 void EnsureCFGWellFormedness(); 262 // Ensure split-edge form for a hand-assembled schedule. 263 void EnsureSplitEdgeForm(BasicBlock* block); 264 // Ensure entry into a deferred block happens from a single hot block. 265 void EnsureDeferredCodeSingleEntryPoint(BasicBlock* block); 266 // Copy deferred block markers down as far as possible 267 void PropagateDeferredMark(); 268 269 void AddSuccessor(BasicBlock* block, BasicBlock* succ); 270 void MoveSuccessors(BasicBlock* from, BasicBlock* to); 271 272 void SetControlInput(BasicBlock* block, Node* node); 273 void SetBlockForNode(BasicBlock* block, Node* node); 274 275 Zone* zone_; 276 BasicBlockVector all_blocks_; // All basic blocks in the schedule. 277 BasicBlockVector nodeid_to_block_; // Map from node to containing block. 278 BasicBlockVector rpo_order_; // Reverse-post-order block list. 279 BasicBlock* start_; 280 BasicBlock* end_; 281 282 DISALLOW_COPY_AND_ASSIGN(Schedule); 283 }; 284 285 std::ostream& operator<<(std::ostream&, const Schedule&); 286 287 } // namespace compiler 288 } // namespace internal 289 } // namespace v8 290 291 #endif // V8_COMPILER_SCHEDULE_H_ 292
