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
14namespace v8 {
15namespace internal {
16namespace 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.
20class 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
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
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