scheduler.h 4.65 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_SCHEDULER_H_
#define V8_COMPILER_SCHEDULER_H_

8
#include "src/base/flags.h"
9
#include "src/compiler/node.h"
10 11
#include "src/compiler/opcodes.h"
#include "src/compiler/schedule.h"
12
#include "src/compiler/zone-stats.h"
13
#include "src/globals.h"
14
#include "src/zone/zone-containers.h"
15 16 17 18 19

namespace v8 {
namespace internal {
namespace compiler {

20
// Forward declarations.
21
class CFGBuilder;
22
class ControlEquivalence;
23
class Graph;
24 25
class SpecialRPONumberer;

26

27 28
// Computes a schedule from a graph, placing nodes into basic blocks and
// ordering the basic blocks in the special RPO order.
29
class V8_EXPORT_PRIVATE Scheduler {
30
 public:
31
  // Flags that control the mode of operation.
32
  enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1, kTempSchedule = 1u << 2 };
33 34
  typedef base::Flags<Flag> Flags;

35 36
  // The complete scheduling algorithm. Creates a new schedule and places all
  // nodes from the graph into it.
37
  static Schedule* ComputeSchedule(Zone* temp_zone, Graph* graph, Flags flags);
38

39
  // Compute the RPO of blocks in an existing schedule.
40
  static BasicBlockVector* ComputeSpecialRPO(Zone* zone, Schedule* schedule);
41 42

 private:
43 44 45 46 47 48 49 50 51
  // Placement of a node changes during scheduling. The placement state
  // transitions over time while the scheduler is choosing a position:
  //
  //                   +---------------------+-----+----> kFixed
  //                  /                     /     /
  //    kUnknown ----+------> kCoupled ----+     /
  //                  \                         /
  //                   +----> kSchedulable ----+--------> kScheduled
  //
52
  // 1) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
53
  // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
54 55 56 57 58
  //
  // We maintain the invariant that all nodes that are not reachable
  // from the end have kUnknown placement. After the PrepareUses phase runs,
  // also the opposite is true - all nodes with kUnknown placement are not
  // reachable from the end.
59
  enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
60 61 62

  // Per-node data tracked during scheduling.
  struct SchedulerData {
63
    BasicBlock* minimum_block_;  // Minimum legal RPO placement.
64
    int unscheduled_count_;      // Number of unscheduled uses of this node.
65 66
    Placement placement_;        // Whether the node is fixed, schedulable,
                                 // coupled to another node, or not yet known.
67 68
  };

69
  Zone* zone_;
70 71
  Graph* graph_;
  Schedule* schedule_;
72
  Flags flags_;
73
  ZoneVector<NodeVector*>
74 75 76 77 78 79 80
      scheduled_nodes_;                  // Per-block list of nodes in reverse.
  NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
  ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
  ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
  CFGBuilder* control_flow_builder_;     // Builds basic blocks for controls.
  SpecialRPONumberer* special_rpo_;      // Special RPO numbering of blocks.
  ControlEquivalence* equivalence_;      // Control dependence equivalence.
81

82 83
  Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
            size_t node_count_hint_);
84

85 86
  inline SchedulerData DefaultSchedulerData();
  inline SchedulerData* GetData(Node* node);
87 88

  Placement GetPlacement(Node* node);
89
  Placement InitializePlacement(Node* node);
90
  void UpdatePlacement(Node* node, Placement placement);
91
  bool IsLive(Node* node);
92

93 94 95
  inline bool IsCoupledControlEdge(Node* node, int index);
  void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
  void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
96

97
  void PropagateImmediateDominators(BasicBlock* block);
98

99
  // Phase 1: Build control-flow graph.
100
  friend class CFGBuilder;
101
  void BuildCFG();
102 103 104 105

  // Phase 2: Compute special RPO and dominator tree.
  friend class SpecialRPONumberer;
  void ComputeSpecialRPONumbering();
106
  void GenerateImmediateDominatorTree();
107

108
  // Phase 3: Prepare use counts for nodes.
109 110 111
  friend class PrepareUsesVisitor;
  void PrepareUses();

112
  // Phase 4: Schedule nodes early.
113 114 115
  friend class ScheduleEarlyNodeVisitor;
  void ScheduleEarly();

116
  // Phase 5: Schedule nodes late.
117 118
  friend class ScheduleLateNodeVisitor;
  void ScheduleLate();
119

120 121 122
  // Phase 6: Seal the final schedule.
  void SealFinalSchedule();

123 124
  void FuseFloatingControl(BasicBlock* block, Node* node);
  void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
125
};
126

127 128 129

DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)

130 131 132
}  // namespace compiler
}  // namespace internal
}  // namespace v8
133 134

#endif  // V8_COMPILER_SCHEDULER_H_