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/base/flags.h" 9 #include "src/compiler/node.h" 10 #include "src/compiler/opcodes.h" 11 #include "src/compiler/schedule.h" 12 #include "src/compiler/zone-stats.h" 13 #include "src/globals.h" 14 #include "src/zone/zone-containers.h" 15 16 namespace v8 { 17 namespace internal { 18 namespace compiler { 19 20 // Forward declarations. 21 class CFGBuilder; 22 class ControlEquivalence; 23 class Graph; 24 class SpecialRPONumberer; 25 26 27 // Computes a schedule from a graph, placing nodes into basic blocks and 28 // ordering the basic blocks in the special RPO order. 29 class V8_EXPORT_PRIVATE Scheduler { 30 public: 31 // Flags that control the mode of operation. 32 enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1 }; 33 typedef base::Flags<Flag> Flags; 34 35 // The complete scheduling algorithm. Creates a new schedule and places all 36 // nodes from the graph into it. 37 static Schedule* ComputeSchedule(Zone* zone, Graph* graph, Flags flags); 38 39 // Compute the RPO of blocks in an existing schedule. 40 static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule); 41 42 private: 43 // Placement of a node changes during scheduling. The placement state 44 // transitions over time while the scheduler is choosing a position: 45 // 46 // +---------------------+-----+----> kFixed 47 // / / / 48 // kUnknown ----+------> kCoupled ----+ / 49 // \ / 50 // +----> kSchedulable ----+--------> kScheduled 51 // 52 // 1) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed 53 // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled 54 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled }; 55 56 // Per-node data tracked during scheduling. 57 struct SchedulerData { 58 BasicBlock* minimum_block_; // Minimum legal RPO placement. 59 int unscheduled_count_; // Number of unscheduled uses of this node. 60 Placement placement_; // Whether the node is fixed, schedulable, 61 // coupled to another node, or not yet known. 62 }; 63 64 Zone* zone_; 65 Graph* graph_; 66 Schedule* schedule_; 67 Flags flags_; 68 NodeVectorVector scheduled_nodes_; // Per-block list of nodes in reverse. 69 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. 70 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. 71 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. 72 CFGBuilder* control_flow_builder_; // Builds basic blocks for controls. 73 SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks. 74 ControlEquivalence* equivalence_; // Control dependence equivalence. 75 76 Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags); 77 78 inline SchedulerData DefaultSchedulerData(); 79 inline SchedulerData* GetData(Node* node); 80 81 Placement GetPlacement(Node* node); 82 void UpdatePlacement(Node* node, Placement placement); 83 84 inline bool IsCoupledControlEdge(Node* node, int index); 85 void IncrementUnscheduledUseCount(Node* node, int index, Node* from); 86 void DecrementUnscheduledUseCount(Node* node, int index, Node* from); 87 88 void PropagateImmediateDominators(BasicBlock* block); 89 90 // Phase 1: Build control-flow graph. 91 friend class CFGBuilder; 92 void BuildCFG(); 93 94 // Phase 2: Compute special RPO and dominator tree. 95 friend class SpecialRPONumberer; 96 void ComputeSpecialRPONumbering(); 97 void GenerateImmediateDominatorTree(); 98 99 // Phase 3: Prepare use counts for nodes. 100 friend class PrepareUsesVisitor; 101 void PrepareUses(); 102 103 // Phase 4: Schedule nodes early. 104 friend class ScheduleEarlyNodeVisitor; 105 void ScheduleEarly(); 106 107 // Phase 5: Schedule nodes late. 108 friend class ScheduleLateNodeVisitor; 109 void ScheduleLate(); 110 111 // Phase 6: Seal the final schedule. 112 void SealFinalSchedule(); 113 114 void FuseFloatingControl(BasicBlock* block, Node* node); 115 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); 116 }; 117 118 119 DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags) 120 121 } // namespace compiler 122 } // namespace internal 123 } // namespace v8 124 125 #endif // V8_COMPILER_SCHEDULER_H_ 126