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 // Implements a two-dimensional map: (int, int) -> BasicBlock*. 72 using CommonDominatorCache = ZoneMap<int, ZoneMap<int, BasicBlock*>*>; 73 74 // Per-node data tracked during scheduling. 75 struct SchedulerData { 76 BasicBlock* minimum_block_; // Minimum legal RPO placement. 77 int unscheduled_count_; // Number of unscheduled uses of this node. 78 Placement placement_; // Whether the node is fixed, schedulable, 79 // coupled to another node, or not yet known. 80 }; 81 82 Zone* zone_; 83 Graph* graph_; 84 Schedule* schedule_; 85 Flags flags_; 86 ZoneVector<NodeVector*> 87 scheduled_nodes_; // Per-block list of nodes in reverse. 88 NodeVector schedule_root_nodes_; // Fixed root nodes seed the worklist. 89 ZoneQueue<Node*> schedule_queue_; // Worklist of schedulable nodes. 90 ZoneVector<SchedulerData> node_data_; // Per-node data for all nodes. 91 CFGBuilder* control_flow_builder_; // Builds basic blocks for controls. 92 SpecialRPONumberer* special_rpo_; // Special RPO numbering of blocks. 93 ControlEquivalence* equivalence_; // Control dependence equivalence. 94 TickCounter* const tick_counter_; 95 const ProfileDataFromFile* profile_data_; 96 CommonDominatorCache common_dominator_cache_; 97 98 Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags, 99 size_t node_count_hint_, TickCounter* tick_counter, 100 const ProfileDataFromFile* profile_data); 101 102 inline SchedulerData DefaultSchedulerData(); 103 inline SchedulerData* GetData(Node* node); 104 105 Placement GetPlacement(Node* node); 106 Placement InitializePlacement(Node* node); 107 void UpdatePlacement(Node* node, Placement placement); 108 bool IsLive(Node* node); 109 110 // If the node is coupled, returns the coupled control edge index. 111 inline base::Optional<int> GetCoupledControlEdge(Node* node); 112 void IncrementUnscheduledUseCount(Node* node, Node* from); 113 void DecrementUnscheduledUseCount(Node* node, Node* from); 114 115 static void PropagateImmediateDominators(BasicBlock* block); 116 117 // Uses {common_dominator_cache_} to speed up repeated calls. 118 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); 119 // Returns the common dominator of {b1} and {b2} if it can be found in 120 // {common_dominator_cache_}, or nullptr otherwise. 121 // Not meant to be called directly, only from {GetCommonDominator}. 122 BasicBlock* GetCommonDominatorIfCached(BasicBlock* b1, BasicBlock* b2); 123 124 // Phase 1: Build control-flow graph. 125 friend class CFGBuilder; 126 void BuildCFG(); 127 128 // Phase 2: Compute special RPO and dominator tree. 129 friend class SpecialRPONumberer; 130 void ComputeSpecialRPONumbering(); 131 void GenerateDominatorTree(); 132 133 // Phase 3: Prepare use counts for nodes. 134 friend class PrepareUsesVisitor; 135 void PrepareUses(); 136 137 // Phase 4: Schedule nodes early. 138 friend class ScheduleEarlyNodeVisitor; 139 void ScheduleEarly(); 140 141 // Phase 5: Schedule nodes late. 142 friend class ScheduleLateNodeVisitor; 143 void ScheduleLate(); 144 145 // Phase 6: Seal the final schedule. 146 void SealFinalSchedule(); 147 148 void FuseFloatingControl(BasicBlock* block, Node* node); 149 void MovePlannedNodes(BasicBlock* from, BasicBlock* to); 150 }; 151 152 153 DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags) 154 155 } // namespace compiler 156 } // namespace internal 157 } // namespace v8 158 159 #endif // V8_COMPILER_SCHEDULER_H_ 160