scheduler.h 5.73 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
#include "src/compiler/schedule.h"
11
#include "src/zone/zone-containers.h"
12 13 14

namespace v8 {
namespace internal {
15

16
class ProfileDataFromFile;
17 18
class TickCounter;

19 20
namespace compiler {

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

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
  using Flags = base::Flags<Flag>;
34

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
                                   TickCounter* tick_counter,
                                   const ProfileDataFromFile* profile_data);
40

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

44 45 46
  // Computes the dominator tree on an existing schedule that has RPO computed.
  static void GenerateDominatorTree(Schedule* schedule);

47 48
  const ProfileDataFromFile* profile_data() const { return profile_data_; }

49
 private:
50 51 52 53 54 55 56 57 58
  // 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
  //
59
  // 1) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
60
  // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
61 62 63 64 65
  //
  // 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.
66
  enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
67

68 69 70
  // Implements a two-dimensional map: (int, int) -> BasicBlock*.
  using CommonDominatorCache = ZoneMap<int, ZoneMap<int, BasicBlock*>*>;

71 72
  // Per-node data tracked during scheduling.
  struct SchedulerData {
73
    BasicBlock* minimum_block_;  // Minimum legal RPO placement.
74
    int unscheduled_count_;      // Number of unscheduled uses of this node.
75 76
    Placement placement_;        // Whether the node is fixed, schedulable,
                                 // coupled to another node, or not yet known.
77 78
  };

79
  Zone* zone_;
80 81
  Graph* graph_;
  Schedule* schedule_;
82
  Flags flags_;
83
  ZoneVector<NodeVector*>
84 85 86 87 88 89 90
      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.
91
  TickCounter* const tick_counter_;
92
  const ProfileDataFromFile* profile_data_;
93
  CommonDominatorCache common_dominator_cache_;
94

95
  Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
96 97
            size_t node_count_hint_, TickCounter* tick_counter,
            const ProfileDataFromFile* profile_data);
98

99 100
  inline SchedulerData DefaultSchedulerData();
  inline SchedulerData* GetData(Node* node);
101 102

  Placement GetPlacement(Node* node);
103
  Placement InitializePlacement(Node* node);
104
  void UpdatePlacement(Node* node, Placement placement);
105
  bool IsLive(Node* node);
106

107 108 109 110
  // If the node is coupled, returns the coupled control edge index.
  inline base::Optional<int> GetCoupledControlEdge(Node* node);
  void IncrementUnscheduledUseCount(Node* node, Node* from);
  void DecrementUnscheduledUseCount(Node* node, Node* from);
111

112
  static void PropagateImmediateDominators(BasicBlock* block);
113

114 115 116 117 118 119 120
  // Uses {common_dominator_cache_} to speed up repeated calls.
  BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
  // Returns the common dominator of {b1} and {b2} if it can be found in
  // {common_dominator_cache_}, or nullptr otherwise.
  // Not meant to be called directly, only from {GetCommonDominator}.
  BasicBlock* GetCommonDominatorIfCached(BasicBlock* b1, BasicBlock* b2);

121
  // Phase 1: Build control-flow graph.
122
  friend class CFGBuilder;
123
  void BuildCFG();
124 125 126 127

  // Phase 2: Compute special RPO and dominator tree.
  friend class SpecialRPONumberer;
  void ComputeSpecialRPONumbering();
128
  void GenerateDominatorTree();
129

130
  // Phase 3: Prepare use counts for nodes.
131 132 133
  friend class PrepareUsesVisitor;
  void PrepareUses();

134
  // Phase 4: Schedule nodes early.
135 136 137
  friend class ScheduleEarlyNodeVisitor;
  void ScheduleEarly();

138
  // Phase 5: Schedule nodes late.
139 140
  friend class ScheduleLateNodeVisitor;
  void ScheduleLate();
141

142 143 144
  // Phase 6: Seal the final schedule.
  void SealFinalSchedule();

145 146
  void FuseFloatingControl(BasicBlock* block, Node* node);
  void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
147
};
148

149 150 151

DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)

152 153 154
}  // namespace compiler
}  // namespace internal
}  // namespace v8
155 156

#endif  // V8_COMPILER_SCHEDULER_H_