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/zone-containers.h"
  13
  14 namespace v8 {
  15 namespace internal {
  16 namespace compiler {
  17
  18 // Computes a schedule from a graph, placing nodes into basic blocks and
  19 // ordering the basic blocks in the special RPO order.
  20 class Scheduler {
  21  public:
  22   // The complete scheduling algorithm.
  23   // Create a new schedule and place all nodes from the graph into it.
  24   static Schedule* ComputeSchedule(Graph* graph);
  25
  26   // Compute the RPO of blocks in an existing schedule.
  27   static BasicBlockVector* ComputeSpecialRPO(Schedule* schedule);
  28
  29   // (Exposed for testing only)
  30   // Build and connect the CFG for a node graph, but don't schedule nodes.
  31   static void ComputeCFG(Graph* graph, Schedule* schedule);
  32
  33  private:
  34   enum Placement { kUnknown, kSchedulable, kFixed };
  35
  36   // Per-node data tracked during scheduling.
  37   struct SchedulerData {
  38     int unscheduled_count_;      // Number of unscheduled uses of this node.
  39     int minimum_rpo_;            // Minimum legal RPO placement.
  40     bool is_connected_control_;  // {true} if control-connected to the end node.
  41     bool is_floating_control_;   // {true} if control, but not control-connected
  42                                  // to the end node.
  43     Placement placement_ : 3;    // Whether the node is fixed, schedulable,
  44                                  // or not yet known.
  45   };
  46
  47   Zone* zone_;
  48   Graph* graph_;
  49   Schedule* schedule_;
  50   NodeVectorVector scheduled_nodes_;
  51   NodeVector schedule_root_nodes_;
  52   ZoneVector<SchedulerData> node_data_;
  53   bool has_floating_control_;
  54
  55   Scheduler(Zone* zone, Graph* graph, Schedule* schedule);
  56
  57   SchedulerData DefaultSchedulerData();
  58
  59   SchedulerData* GetData(Node* node) {
  60     DCHECK(node->id() < static_cast<int>(node_data_.size()));
  61     return &node_data_[node->id()];
  62   }
  63
  64   void BuildCFG();
  65
  66   Placement GetPlacement(Node* node);
  67
  68   int GetRPONumber(BasicBlock* block) {
  69     DCHECK(block->rpo_number_ >= 0 &&
  70            block->rpo_number_ < static_cast<int>(schedule_->rpo_order_.size()));
  71     DCHECK(schedule_->rpo_order_[block->rpo_number_] == block);
  72     return block->rpo_number_;
  73   }
  74
  75   void GenerateImmediateDominatorTree();
  76   BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
  77
  78   friend class CFGBuilder;
  79
  80   friend class ScheduleEarlyNodeVisitor;
  81   void ScheduleEarly();
  82
  83   friend class PrepareUsesVisitor;
  84   void PrepareUses();
  85
  86   friend class ScheduleLateNodeVisitor;
  87   void ScheduleLate();
  88
  89   bool ConnectFloatingControl();
  90
  91   void ConnectFloatingControlSubgraph(BasicBlock* block, Node* node);
  92 };
  93 }
  94 }
  95 }  // namespace v8::internal::compiler
  96
  97 #endif  // V8_COMPILER_SCHEDULER_H_