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