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/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_
     98