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/v8.h"
9 
10 #include "src/compiler/opcodes.h"
11 #include "src/compiler/schedule.h"
12 #include "src/zone-containers.h"
13 
14 namespace v8 {
15 namespace internal {
16 namespace compiler {
17 
18 // Computes a schedule from a graph, placing nodes into basic blocks and
19 // ordering the basic blocks in the special RPO order.
20 class Scheduler {
21  public:
22   // The complete scheduling algorithm.
23   // Create a new schedule and place all nodes from the graph into it.
24   static Schedule* ComputeSchedule(Graph* graph);
25 
26   // Compute the RPO of blocks in an existing schedule.
27   static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule);
28 
29   // (Exposed for testing only)
30   // Build and connect the CFG for a node graph, but don't schedule nodes.
31   static void ComputeCFG(Graph* graph, Schedule* schedule);
32 
33  private:
34   enum Placement { kUnknown, kSchedulable, kFixed };
35 
36   // Per-node data tracked during scheduling.
37   struct SchedulerData {
38     int unscheduled_count_;      // Number of unscheduled uses of this node.
39     int minimum_rpo_;            // Minimum legal RPO placement.
40     bool is_connected_control_;  // {true} if control-connected to the end node.
41     bool is_floating_control_;   // {true} if control, but not control-connected
42                                  // to the end node.
43     Placement placement_ : 3;    // Whether the node is fixed, schedulable,
44                                  // or not yet known.
45   };
46 
47   Zone* zone_;
48   Graph* graph_;
49   Schedule* schedule_;
50   NodeVectorVector scheduled_nodes_;
51   NodeVector schedule_root_nodes_;
52   ZoneVector<SchedulerData> node_data_;
53   bool has_floating_control_;
54 
55   Scheduler(Zone* zone, Graph* graph, Schedule* schedule);
56 
57   SchedulerData DefaultSchedulerData();
58 
GetData(Node * node)59   SchedulerData* GetData(Node* node) {
60     DCHECK(node->id() < static_cast<int>(node_data_.size()));
61     return &node_data_[node->id()];
62   }
63 
64   void BuildCFG();
65 
66   Placement GetPlacement(Node* node);
67 
GetRPONumber(BasicBlock * block)68   int GetRPONumber(BasicBlock* block) {
69     DCHECK(block->rpo_number_ >= 0 &&
70            block->rpo_number_ < static_cast<int>(schedule_->rpo_order_.size()));
71     DCHECK(schedule_->rpo_order_[block->rpo_number_] == block);
72     return block->rpo_number_;
73   }
74 
75   void GenerateImmediateDominatorTree();
76   BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
77 
78   friend class CFGBuilder;
79 
80   friend class ScheduleEarlyNodeVisitor;
81   void ScheduleEarly();
82 
83   friend class PrepareUsesVisitor;
84   void PrepareUses();
85 
86   friend class ScheduleLateNodeVisitor;
87   void ScheduleLate();
88 
89   bool ConnectFloatingControl();
90 
91   void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node);
92 };
93 }
94 }
95 }  // namespace v8::internal::compiler
96 
97 #endif  // V8_COMPILER_SCHEDULER_H_
98