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