Line data    Source code

       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/base/flags.h"
       9             : #include "src/compiler/node.h"
      10             : #include "src/compiler/opcodes.h"
      11             : #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             : namespace v8 {
      17             : namespace internal {
      18             : namespace compiler {
      19             : 
      20             : // Forward declarations.
      21             : class CFGBuilder;
      22             : class ControlEquivalence;
      23             : class Graph;
      24             : class SpecialRPONumberer;
      25             : 
      26             : 
      27             : // Computes a schedule from a graph, placing nodes into basic blocks and
      28             : // ordering the basic blocks in the special RPO order.
      29     2868320 : 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             :   // The complete scheduling algorithm. Creates a new schedule and places all
      36             :   // 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             :   // Placement of a node changes during scheduling. The placement state
      44             :   // transitions over time while the scheduler is choosing a position:
      45             :   //
      46             :   //                   +---------------------+-----+----> kFixed
      47             :   //                  /                     /     /
      48             :   //    kUnknown ----+------> kCoupled ----+     /
      49             :   //                  \                         /
      50             :   //                   +----> kSchedulable ----+--------> kScheduled
      51             :   //
      52             :   // 1) InitializePlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
      53             :   // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
      54             :   //
      55             :   // We maintain the invariant that all nodes that are not reachable
      56             :   // from the end have kUnknown placement. After the PrepareUses phase runs,
      57             :   // also the opposite is true - all nodes with kUnknown placement are not
      58             :   // reachable from the end.
      59             :   enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
      60             : 
      61             :   // Per-node data tracked during scheduling.
      62             :   struct SchedulerData {
      63             :     BasicBlock* minimum_block_;  // Minimum legal RPO placement.
      64             :     int unscheduled_count_;      // Number of unscheduled uses of this node.
      65             :     Placement placement_;        // Whether the node is fixed, schedulable,
      66             :                                  // coupled to another node, or not yet known.
      67             :   };
      68             : 
      69             :   Zone* zone_;
      70             :   Graph* graph_;
      71             :   Schedule* schedule_;
      72             :   Flags flags_;
      73             :   ZoneVector<NodeVector*>
      74             :       scheduled_nodes_;                  // Per-block list of nodes in reverse.
      75             :   NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
      76             :   ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
      77             :   ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
      78             :   CFGBuilder* control_flow_builder_;     // Builds basic blocks for controls.
      79             :   SpecialRPONumberer* special_rpo_;      // Special RPO numbering of blocks.
      80             :   ControlEquivalence* equivalence_;      // Control dependence equivalence.
      81             : 
      82             :   Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags,
      83             :             size_t node_count_hint_);
      84             : 
      85             :   inline SchedulerData DefaultSchedulerData();
      86             :   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             :   inline bool IsCoupledControlEdge(Node* node, int index);
      94             :   void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
      95             :   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             :   // Phase 2: Compute special RPO and dominator tree.
     104             :   friend class SpecialRPONumberer;
     105             :   void ComputeSpecialRPONumbering();
     106             :   void GenerateImmediateDominatorTree();
     107             : 
     108             :   // Phase 3: Prepare use counts for nodes.
     109             :   friend class PrepareUsesVisitor;
     110             :   void PrepareUses();
     111             : 
     112             :   // Phase 4: Schedule nodes early.
     113             :   friend class ScheduleEarlyNodeVisitor;
     114             :   void ScheduleEarly();
     115             : 
     116             :   // Phase 5: Schedule nodes late.
     117             :   friend class ScheduleLateNodeVisitor;
     118             :   void ScheduleLate();
     119             : 
     120             :   // Phase 6: Seal the final schedule.
     121             :   void SealFinalSchedule();
     122             : 
     123             :   void FuseFloatingControl(BasicBlock* block, Node* node);
     124             :   void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
     125             : };
     126             : 
     127             : 
     128             : DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)
     129             : 
     130             : }  // namespace compiler
     131             : }  // namespace internal
     132             : }  // namespace v8
     133             : 
     134             : #endif  // V8_COMPILER_SCHEDULER_H_