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_SCHEDULER_H_ 6 #define V8_COMPILER_SCHEDULER_H_ 7 8 #include "src/v8.h" 9 10 #include "src/compiler/opcodes.h" 11 #include "src/compiler/schedule.h" 12 #include "src/zone-containers.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 // Computes a schedule from a graph, placing nodes into basic blocks and 19 // ordering the basic blocks in the special RPO order. 20 class Scheduler { 21 public: 22 // The complete scheduling algorithm. 23 // Create a new schedule and place all nodes from the graph into it. 24 static Schedule* ComputeSchedule(Graph* graph); 25 26 // Compute the RPO of blocks in an existing schedule. 27 static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule); 28 29 // (Exposed for testing only) 30 // Build and connect the CFG for a node graph, but don't schedule nodes. 31 static void ComputeCFG(Graph* graph, Schedule* schedule); 32 33 private: 34 enum Placement { kUnknown, kSchedulable, kFixed }; 35 36 // Per-node data tracked during scheduling. 37 struct SchedulerData { 38 int unscheduled_count_; // Number of unscheduled uses of this node. 39 int minimum_rpo_; // Minimum legal RPO placement. 40 bool is_connected_control_; // {true} if control-connected to the end node. 41 bool is_floating_control_; // {true} if control, but not control-connected 42 // to the end node. 43 Placement placement_ : 3; // Whether the node is fixed, schedulable, 44 // or not yet known. 45 }; 46 47 Zone* zone_; 48 Graph* graph_; 49 Schedule* schedule_; 50 NodeVectorVector scheduled_nodes_; 51 NodeVector schedule_root_nodes_; 52 ZoneVector<SchedulerData> node_data_; 53 bool has_floating_control_; 54 55 Scheduler(Zone* zone, Graph* graph, Schedule* schedule); 56 57 SchedulerData DefaultSchedulerData(); 58 GetData(Node * node)59 SchedulerData* GetData(Node* node) { 60 DCHECK(node->id() < static_cast<int>(node_data_.size())); 61 return &node_data_[node->id()]; 62 } 63 64 void BuildCFG(); 65 66 Placement GetPlacement(Node* node); 67 GetRPONumber(BasicBlock * block)68 int GetRPONumber(BasicBlock* block) { 69 DCHECK(block->rpo_number_ >= 0 && 70 block->rpo_number_ < static_cast<int>(schedule_->rpo_order_.size())); 71 DCHECK(schedule_->rpo_order_[block->rpo_number_] == block); 72 return block->rpo_number_; 73 } 74 75 void GenerateImmediateDominatorTree(); 76 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); 77 78 friend class CFGBuilder; 79 80 friend class ScheduleEarlyNodeVisitor; 81 void ScheduleEarly(); 82 83 friend class PrepareUsesVisitor; 84 void PrepareUses(); 85 86 friend class ScheduleLateNodeVisitor; 87 void ScheduleLate(); 88 89 bool ConnectFloatingControl(); 90 91 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); 92 }; 93 } 94 } 95 } // namespace v8::internal::compiler 96 97 #endif // V8_COMPILER_SCHEDULER_H_ 98