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