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-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 class V8_EXPORT_PRIVATE Scheduler {
     30  public:
     31   // Flags that control the mode of operation.
     32   enum Flag { kNoFlags = 0u, kSplitNodes = 1u << 1 };
     33   typedef base::Flags<Flag> Flags;
     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* 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) GetPlacement(): kUnknown -> kCoupled|kSchedulable|kFixed
     53   // 2) UpdatePlacement(): kCoupled|kSchedulable -> kFixed|kScheduled
     54   enum Placement { kUnknown, kSchedulable, kFixed, kCoupled, kScheduled };
     55 
     56   // Per-node data tracked during scheduling.
     57   struct SchedulerData {
     58     BasicBlock* minimum_block_;  // Minimum legal RPO placement.
     59     int unscheduled_count_;      // Number of unscheduled uses of this node.
     60     Placement placement_;        // Whether the node is fixed, schedulable,
     61                                  // coupled to another node, or not yet known.
     62   };
     63 
     64   Zone* zone_;
     65   Graph* graph_;
     66   Schedule* schedule_;
     67   Flags flags_;
     68   NodeVectorVector scheduled_nodes_;     // Per-block list of nodes in reverse.
     69   NodeVector schedule_root_nodes_;       // Fixed root nodes seed the worklist.
     70   ZoneQueue<Node*> schedule_queue_;      // Worklist of schedulable nodes.
     71   ZoneVector<SchedulerData> node_data_;  // Per-node data for all nodes.
     72   CFGBuilder* control_flow_builder_;     // Builds basic blocks for controls.
     73   SpecialRPONumberer* special_rpo_;      // Special RPO numbering of blocks.
     74   ControlEquivalence* equivalence_;      // Control dependence equivalence.
     75 
     76   Scheduler(Zone* zone, Graph* graph, Schedule* schedule, Flags flags);
     77 
     78   inline SchedulerData DefaultSchedulerData();
     79   inline SchedulerData* GetData(Node* node);
     80 
     81   Placement GetPlacement(Node* node);
     82   void UpdatePlacement(Node* node, Placement placement);
     83 
     84   inline bool IsCoupledControlEdge(Node* node, int index);
     85   void IncrementUnscheduledUseCount(Node* node, int index, Node* from);
     86   void DecrementUnscheduledUseCount(Node* node, int index, Node* from);
     87 
     88   void PropagateImmediateDominators(BasicBlock* block);
     89 
     90   // Phase 1: Build control-flow graph.
     91   friend class CFGBuilder;
     92   void BuildCFG();
     93 
     94   // Phase 2: Compute special RPO and dominator tree.
     95   friend class SpecialRPONumberer;
     96   void ComputeSpecialRPONumbering();
     97   void GenerateImmediateDominatorTree();
     98 
     99   // Phase 3: Prepare use counts for nodes.
    100   friend class PrepareUsesVisitor;
    101   void PrepareUses();
    102 
    103   // Phase 4: Schedule nodes early.
    104   friend class ScheduleEarlyNodeVisitor;
    105   void ScheduleEarly();
    106 
    107   // Phase 5: Schedule nodes late.
    108   friend class ScheduleLateNodeVisitor;
    109   void ScheduleLate();
    110 
    111   // Phase 6: Seal the final schedule.
    112   void SealFinalSchedule();
    113 
    114   void FuseFloatingControl(BasicBlock* block, Node* node);
    115   void MovePlannedNodes(BasicBlock* from, BasicBlock* to);
    116 };
    117 
    118 
    119 DEFINE_OPERATORS_FOR_FLAGS(Scheduler::Flags)
    120 
    121 }  // namespace compiler
    122 }  // namespace internal
    123 }  // namespace v8
    124 
    125 #endif  // V8_COMPILER_SCHEDULER_H_
    126