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