| 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/compiler/opcodes.h" | 10 #include "src/compiler/opcodes.h" |
| (...skipping 11 matching lines...) Expand all Loading... |
| 22 public: | 22 public: |
| 23 // The complete scheduling algorithm. Creates a new schedule and places all | 23 // The complete scheduling algorithm. Creates a new schedule and places all |
| 24 // nodes from the graph into it. | 24 // nodes from the graph into it. |
| 25 static Schedule* ComputeSchedule(ZonePool* zone_pool, Graph* graph); | 25 static Schedule* ComputeSchedule(ZonePool* zone_pool, Graph* graph); |
| 26 | 26 |
| 27 // Compute the RPO of blocks in an existing schedule. | 27 // Compute the RPO of blocks in an existing schedule. |
| 28 static BasicBlockVector* ComputeSpecialRPO(ZonePool* zone_pool, | 28 static BasicBlockVector* ComputeSpecialRPO(ZonePool* zone_pool, |
| 29 Schedule* schedule); | 29 Schedule* schedule); |
| 30 | 30 |
| 31 private: | 31 private: |
| 32 enum Placement { kUnknown, kSchedulable, kFixed, kCoupled }; | 32 enum Placement { kUnknown, kSchedulable, kFixed }; |
| 33 | 33 |
| 34 // Per-node data tracked during scheduling. | 34 // Per-node data tracked during scheduling. |
| 35 struct SchedulerData { | 35 struct SchedulerData { |
| 36 BasicBlock* minimum_block_; // Minimum legal RPO placement. | 36 BasicBlock* minimum_block_; // Minimum legal RPO placement. |
| 37 int unscheduled_count_; // Number of unscheduled uses of this node. | 37 int unscheduled_count_; // Number of unscheduled uses of this node. |
| 38 bool is_connected_control_; // {true} if control-connected to the end node. | 38 bool is_connected_control_; // {true} if control-connected to the end node. |
| 39 bool is_floating_control_; // {true} if control, but not control-connected | 39 bool is_floating_control_; // {true} if control, but not control-connected |
| 40 // to the end node. | 40 // to the end node. |
| 41 Placement placement_ : 2; // Whether the node is fixed, schedulable, | 41 Placement placement_ : 3; // Whether the node is fixed, schedulable, |
| 42 // coupled to another node, or not yet known. | 42 // or not yet known. |
| 43 }; | 43 }; |
| 44 | 44 |
| 45 ZonePool* zone_pool_; | 45 ZonePool* zone_pool_; |
| 46 Zone* zone_; | 46 Zone* zone_; |
| 47 Graph* graph_; | 47 Graph* graph_; |
| 48 Schedule* schedule_; | 48 Schedule* schedule_; |
| 49 NodeVectorVector scheduled_nodes_; | 49 NodeVectorVector scheduled_nodes_; |
| 50 NodeVector schedule_root_nodes_; | 50 NodeVector schedule_root_nodes_; |
| 51 ZoneVector<SchedulerData> node_data_; | 51 ZoneVector<SchedulerData> node_data_; |
| 52 bool has_floating_control_; | 52 bool has_floating_control_; |
| 53 | 53 |
| 54 Scheduler(ZonePool* zone_pool, Zone* zone, Graph* graph, Schedule* schedule); | 54 Scheduler(ZonePool* zone_pool, Zone* zone, Graph* graph, Schedule* schedule); |
| 55 | 55 |
| 56 inline SchedulerData DefaultSchedulerData(); | 56 SchedulerData DefaultSchedulerData(); |
| 57 inline SchedulerData* GetData(Node* node); | 57 |
| 58 SchedulerData* GetData(Node* node) { |
| 59 DCHECK(node->id() < static_cast<int>(node_data_.size())); |
| 60 return &node_data_[node->id()]; |
| 61 } |
| 58 | 62 |
| 59 Placement GetPlacement(Node* node); | 63 Placement GetPlacement(Node* node); |
| 60 | 64 |
| 61 void IncrementUnscheduledUseCount(Node* node, Node* from); | 65 int GetRPONumber(BasicBlock* block) { |
| 62 void DecrementUnscheduledUseCount(Node* node, Node* from); | 66 DCHECK(block->rpo_number() >= 0 && |
| 67 block->rpo_number() < |
| 68 static_cast<int>(schedule_->rpo_order_.size())); |
| 69 DCHECK(schedule_->rpo_order_[block->rpo_number()] == block); |
| 70 return block->rpo_number(); |
| 71 } |
| 63 | 72 |
| 64 inline int GetRPONumber(BasicBlock* block); | |
| 65 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); | 73 BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2); |
| 66 | 74 |
| 67 // Phase 1: Build control-flow graph and dominator tree. | 75 // Phase 1: Build control-flow graph and dominator tree. |
| 68 friend class CFGBuilder; | 76 friend class CFGBuilder; |
| 69 void BuildCFG(); | 77 void BuildCFG(); |
| 70 void GenerateImmediateDominatorTree(); | 78 void GenerateImmediateDominatorTree(); |
| 71 | 79 |
| 72 // Phase 2: Prepare use counts for nodes. | 80 // Phase 2: Prepare use counts for nodes. |
| 73 friend class PrepareUsesVisitor; | 81 friend class PrepareUsesVisitor; |
| 74 void PrepareUses(); | 82 void PrepareUses(); |
| 75 | 83 |
| 76 // Phase 3: Schedule nodes early. | 84 // Phase 3: Schedule nodes early. |
| 77 friend class ScheduleEarlyNodeVisitor; | 85 friend class ScheduleEarlyNodeVisitor; |
| 78 void ScheduleEarly(); | 86 void ScheduleEarly(); |
| 79 | 87 |
| 80 // Phase 4: Schedule nodes late. | 88 // Phase 4: Schedule nodes late. |
| 81 friend class ScheduleLateNodeVisitor; | 89 friend class ScheduleLateNodeVisitor; |
| 82 void ScheduleLate(); | 90 void ScheduleLate(); |
| 83 | 91 |
| 84 bool ConnectFloatingControl(); | 92 bool ConnectFloatingControl(); |
| 85 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); | 93 void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node); |
| 86 }; | 94 }; |
| 87 | 95 |
| 88 } // namespace compiler | 96 } // namespace compiler |
| 89 } // namespace internal | 97 } // namespace internal |
| 90 } // namespace v8 | 98 } // namespace v8 |
| 91 | 99 |
| 92 #endif // V8_COMPILER_SCHEDULER_H_ | 100 #endif // V8_COMPILER_SCHEDULER_H_ |
| OLD | NEW |