src/v8/src/compiler/scheduler.h

   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/compiler/zone-pool.h"
  13 #include "src/zone-containers.h"
  14
  15 namespace v8 {
  16 namespace internal {
  17 namespace compiler {
  18
  19 // Computes a schedule from a graph, placing nodes into basic blocks and
  20 // ordering the basic blocks in the special RPO order.
  21 class Scheduler {
  22  public:
  23   // The complete scheduling algorithm. Creates a new schedule and places all
  24   // nodes from the graph into it.
  25   static Schedule* ComputeSchedule(ZonePool* zone_pool, Graph* graph);
  26
  27   // Compute the RPO of blocks in an existing schedule.
  28   static BasicBlockVector* ComputeSpecialRPO(ZonePool* zone_pool,
  29                                              Schedule* schedule);
  30
  31  private:
  32   // Placement of a node changes during scheduling. The placement state
  33   // transitions over time while the scheduler is choosing a position:
  34   //
  35   //                   +---------------------+-----+----> kFixed
  36   //                  /                     /     /
  37   //    kUnknown ----+------> kCoupled ----+     /
  38   //                  \                         /
  39   //                   +----> kSchedulable ----+--------> kScheduled
  40   //
  41   // 1) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
  42   // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
  43   enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
  44
  45   // Per-node data tracked during scheduling.
  46   struct SchedulerData {
  47     BasicBlock* minimum_block_;  // Minimum legal RPO placement.
  48     int unscheduled_count_;      // Number of unscheduled uses of this node.
  49     bool is_connected_control_;  // {true} if control-connected to the end node.
  50     bool is_floating_control_;   // {true} if control, but not control-connected
  51                                  // to the end node.
  52     Placement placement_;        // Whether the node is fixed, schedulable,
  53                                  // coupled to another node, or not yet known.
  54   };
  55
  56   Zone* zone_;
  57   Graph* graph_;
  58   Schedule* schedule_;
  59   NodeVectorVector scheduled_nodes_;     // Per-block list of nodes in reverse.
  60   NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
  61   ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
  62   ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
  63
  64   Scheduler(Zone* zone, Graph* graph, Schedule* schedule);
  65
  66   inline SchedulerData DefaultSchedulerData();
  67   inline SchedulerData* GetData(Node* node);
  68
  69   Placement GetPlacement(Node* node);
  70   void UpdatePlacement(Node* node, Placement placement);
  71
  72   inline bool IsCoupledControlEdge(Node* node, int index);
  73   void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
  74   void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
  75
  76   inline int GetRPONumber(BasicBlock* block);
  77   BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
  78
  79   // Phase 1: Build control-flow graph.
  80   friend class CFGBuilder;
  81   void BuildCFG();
  82
  83   // Phase 2: Compute special RPO and dominator tree.
  84   friend class SpecialRPONumberer;
  85   void ComputeSpecialRPONumbering();
  86   void GenerateImmediateDominatorTree();
  87
  88   // Phase 3: Prepare use counts for nodes.
  89   friend class PrepareUsesVisitor;
  90   void PrepareUses();
  91
  92   // Phase 4: Schedule nodes early.
  93   friend class ScheduleEarlyNodeVisitor;
  94   void ScheduleEarly();
  95
  96   // Phase 5: Schedule nodes late.
  97   friend class ScheduleLateNodeVisitor;
  98   void ScheduleLate();
  99
 100   void FuseFloatingControl(BasicBlock* block, Node* node);
 101   void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
 102 };
 103
 104 }  // namespace compiler
 105 }  // namespace internal
 106 }  // namespace v8
 107
 108 #endif  // V8_COMPILER_SCHEDULER_H_