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, kTempSchedule = 1u << 2 }; 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* temp_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) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed 53 // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled 54 // 55 // We maintain the invariant that all nodes that are not reachable 56 // from the end have kUnknown placement. After the PrepareUses phase runs, 57 // also the opposite is true - all nodes with kUnknown placement are not 58 // reachable from the end. 59 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled }; 60 61 // Per-node data tracked during scheduling. 62 struct SchedulerData { 63 BasicBlock* minimum_block_; // Minimum legal RPO placement. 64 int unscheduled_count_; // Number of unscheduled uses of this node. 65 Placement placement_; // Whether the node is fixed, schedulable, 66 // coupled to another node, or not yet known. 67 }; 68 69 Zone* zone_; 70 Graph* graph_; 71 Schedule* schedule_; 72 Flags flags_; 73 ZoneVector<NodeVector*> 74 scheduled_nodes_; // Per-block list of nodes in reverse. 75 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. 76 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. 77 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. 78 CFGBuilder* control_flow_builder_; // Builds basic blocks for controls. 79 SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks. 80 ControlEquivalence* equivalence_; // Control dependence equivalence. 81 82 Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags, 83 size_t node_count_hint_); 84 85 inline SchedulerData DefaultSchedulerData(); 86 inline SchedulerData* GetData(Node* node); 87 88 Placement GetPlacement(Node* node); 89 Placement InitializePlacement(Node* node); 90 void UpdatePlacement(Node* node, Placement placement); 91 bool IsLive(Node* node); 92 93 inline bool IsCoupledControlEdge(Node* node, int index); 94 void IncrementUnscheduledUseCount(Node* node, int index, Node* from); 95 void DecrementUnscheduledUseCount(Node* node, int index, Node* from); 96 97 void PropagateImmediateDominators(BasicBlock* block); 98 99 // Phase 1: Build control-flow graph. 100 friend class CFGBuilder; 101 void BuildCFG(); 102 103 // Phase 2: Compute special RPO and dominator tree. 104 friend class SpecialRPONumberer; 105 void ComputeSpecialRPONumbering(); 106 void GenerateImmediateDominatorTree(); 107 108 // Phase 3: Prepare use counts for nodes. 109 friend class PrepareUsesVisitor; 110 void PrepareUses(); 111 112 // Phase 4: Schedule nodes early. 113 friend class ScheduleEarlyNodeVisitor; 114 void ScheduleEarly(); 115 116 // Phase 5: Schedule nodes late. 117 friend class ScheduleLateNodeVisitor; 118 void ScheduleLate(); 119 120 // Phase 6: Seal the final schedule. 121 void SealFinalSchedule(); 122 123 void FuseFloatingControl(BasicBlock* block, Node* node); 124 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); 125 }; 126 127 128 DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags) 129 130 } // namespace compiler 131 } // namespace internal 132 } // namespace v8 133 134 #endif // V8_COMPILER_SCHEDULER_H_ 135