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