deps/v8/src/compiler/schedule.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_SCHEDULE_H_
   6 #define V8_COMPILER_SCHEDULE_H_
   7
   8 #include <iosfwd>
   9
  10 #include "src/zone-containers.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14 namespace compiler {
  15
  16 // Forward declarations.
  17 class BasicBlock;
  18 class BasicBlockInstrumentor;
  19 class Node;
  20
  21
  22 typedef ZoneVector<BasicBlock*> BasicBlockVector;
  23 typedef ZoneVector<Node*> NodeVector;
  24
  25
  26 // A basic block contains an ordered list of nodes and ends with a control
  27 // node. Note that if a basic block has phis, then all phis must appear as the
  28 // first nodes in the block.
  29 class BasicBlock FINAL : public ZoneObject {
  30  public:
  31   // Possible control nodes that can end a block.
  32   enum Control {
  33     kNone,    // Control not initialized yet.
  34     kGoto,    // Goto a single successor block.
  35     kBranch,  // Branch if true to first successor, otherwise second.
  36     kSwitch,  // Table dispatch to one of the successor blocks.
  37     kReturn,  // Return a value from this method.
  38     kThrow    // Throw an exception.
  39   };
  40
  41   class Id {
  42    public:
  43     int ToInt() const { return static_cast<int>(index_); }
  44     size_t ToSize() const { return index_; }
  45     static Id FromSize(size_t index) { return Id(index); }
  46     static Id FromInt(int index) { return Id(static_cast<size_t>(index)); }
  47
  48    private:
  49     explicit Id(size_t index) : index_(index) {}
  50     size_t index_;
  51   };
  52
  53   static const int kInvalidRpoNumber = -1;
  54   class RpoNumber FINAL {
  55    public:
  56     int ToInt() const {
  57       DCHECK(IsValid());
  58       return index_;
  59     }
  60     size_t ToSize() const {
  61       DCHECK(IsValid());
  62       return static_cast<size_t>(index_);
  63     }
  64     bool IsValid() const { return index_ >= 0; }
  65     static RpoNumber FromInt(int index) { return RpoNumber(index); }
  66     static RpoNumber Invalid() { return RpoNumber(kInvalidRpoNumber); }
  67
  68     bool IsNext(const RpoNumber other) const {
  69       DCHECK(IsValid());
  70       return other.index_ == this->index_ + 1;
  71     }
  72
  73     bool operator==(RpoNumber other) const {
  74       return this->index_ == other.index_;
  75     }
  76
  77    private:
  78     explicit RpoNumber(int32_t index) : index_(index) {}
  79     int32_t index_;
  80   };
  81
  82   BasicBlock(Zone* zone, Id id);
  83
  84   Id id() const { return id_; }
  85
  86   // Predecessors.
  87   BasicBlockVector& predecessors() { return predecessors_; }
  88   const BasicBlockVector& predecessors() const { return predecessors_; }
  89   size_t PredecessorCount() const { return predecessors_.size(); }
  90   BasicBlock* PredecessorAt(size_t index) { return predecessors_[index]; }
  91   void ClearPredecessors() { predecessors_.clear(); }
  92   void AddPredecessor(BasicBlock* predecessor);
  93
  94   // Successors.
  95   BasicBlockVector& successors() { return successors_; }
  96   const BasicBlockVector& successors() const { return successors_; }
  97   size_t SuccessorCount() const { return successors_.size(); }
  98   BasicBlock* SuccessorAt(size_t index) { return successors_[index]; }
  99   void ClearSuccessors() { successors_.clear(); }
 100   void AddSuccessor(BasicBlock* successor);
 101
 102   // Nodes in the basic block.
 103   typedef Node* value_type;
 104   bool empty() const { return nodes_.empty(); }
 105   size_t size() const { return nodes_.size(); }
 106   Node* NodeAt(size_t index) { return nodes_[index]; }
 107   size_t NodeCount() const { return nodes_.size(); }
 108
 109   value_type& front() { return nodes_.front(); }
 110   value_type const& front() const { return nodes_.front(); }
 111
 112   typedef NodeVector::iterator iterator;
 113   iterator begin() { return nodes_.begin(); }
 114   iterator end() { return nodes_.end(); }
 115
 116   typedef NodeVector::const_iterator const_iterator;
 117   const_iterator begin() const { return nodes_.begin(); }
 118   const_iterator end() const { return nodes_.end(); }
 119
 120   typedef NodeVector::reverse_iterator reverse_iterator;
 121   reverse_iterator rbegin() { return nodes_.rbegin(); }
 122   reverse_iterator rend() { return nodes_.rend(); }
 123
 124   void AddNode(Node* node);
 125   template <class InputIterator>
 126   void InsertNodes(iterator insertion_point, InputIterator insertion_start,
 127                    InputIterator insertion_end) {
 128     nodes_.insert(insertion_point, insertion_start, insertion_end);
 129   }
 130
 131   // Accessors.
 132   Control control() const { return control_; }
 133   void set_control(Control control);
 134
 135   Node* control_input() const { return control_input_; }
 136   void set_control_input(Node* control_input);
 137
 138   bool deferred() const { return deferred_; }
 139   void set_deferred(bool deferred) { deferred_ = deferred; }
 140
 141   int32_t dominator_depth() const { return dominator_depth_; }
 142   void set_dominator_depth(int32_t depth) { dominator_depth_ = depth; }
 143
 144   BasicBlock* dominator() const { return dominator_; }
 145   void set_dominator(BasicBlock* dominator) { dominator_ = dominator; }
 146
 147   BasicBlock* rpo_next() const { return rpo_next_; }
 148   void set_rpo_next(BasicBlock* rpo_next) { rpo_next_ = rpo_next; }
 149
 150   BasicBlock* loop_header() const { return loop_header_; }
 151   void set_loop_header(BasicBlock* loop_header);
 152
 153   BasicBlock* loop_end() const { return loop_end_; }
 154   void set_loop_end(BasicBlock* loop_end);
 155
 156   int32_t loop_depth() const { return loop_depth_; }
 157   void set_loop_depth(int32_t loop_depth);
 158
 159   int32_t loop_number() const { return loop_number_; }
 160   void set_loop_number(int32_t loop_number) { loop_number_ = loop_number; }
 161
 162   RpoNumber GetRpoNumber() const { return RpoNumber::FromInt(rpo_number_); }
 163   int32_t rpo_number() const { return rpo_number_; }
 164   void set_rpo_number(int32_t rpo_number);
 165
 166   // Loop membership helpers.
 167   inline bool IsLoopHeader() const { return loop_end_ != NULL; }
 168   bool LoopContains(BasicBlock* block) const;
 169
 170   // Computes the immediate common dominator of {b1} and {b2}. The worst time
 171   // complexity is O(N) where N is the height of the dominator tree.
 172   static BasicBlock* GetCommonDominator(BasicBlock* b1, BasicBlock* b2);
 173
 174  private:
 175   int32_t loop_number_;      // loop number of the block.
 176   int32_t rpo_number_;       // special RPO number of the block.
 177   bool deferred_;            // true if the block contains deferred code.
 178   int32_t dominator_depth_;  // Depth within the dominator tree.
 179   BasicBlock* dominator_;    // Immediate dominator of the block.
 180   BasicBlock* rpo_next_;     // Link to next block in special RPO order.
 181   BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
 182                              // NULL if none. For loop headers, this points to
 183                              // enclosing loop header.
 184   BasicBlock* loop_end_;     // end of the loop, if this block is a loop header.
 185   int32_t loop_depth_;       // loop nesting, 0 is top-level
 186
 187   Control control_;          // Control at the end of the block.
 188   Node* control_input_;      // Input value for control.
 189   NodeVector nodes_;         // nodes of this block in forward order.
 190
 191   BasicBlockVector successors_;
 192   BasicBlockVector predecessors_;
 193   Id id_;
 194
 195   DISALLOW_COPY_AND_ASSIGN(BasicBlock);
 196 };
 197
 198 std::ostream& operator<<(std::ostream&, const BasicBlock::Control&);
 199 std::ostream& operator<<(std::ostream&, const BasicBlock::Id&);
 200 std::ostream& operator<<(std::ostream&, const BasicBlock::RpoNumber&);
 201
 202
 203 // A schedule represents the result of assigning nodes to basic blocks
 204 // and ordering them within basic blocks. Prior to computing a schedule,
 205 // a graph has no notion of control flow ordering other than that induced
 206 // by the graph's dependencies. A schedule is required to generate code.
 207 class Schedule FINAL : public ZoneObject {
 208  public:
 209   explicit Schedule(Zone* zone, size_t node_count_hint = 0);
 210
 211   // Return the block which contains {node}, if any.
 212   BasicBlock* block(Node* node) const;
 213
 214   bool IsScheduled(Node* node);
 215   BasicBlock* GetBlockById(BasicBlock::Id block_id);
 216
 217   size_t BasicBlockCount() const { return all_blocks_.size(); }
 218   size_t RpoBlockCount() const { return rpo_order_.size(); }
 219
 220   // Check if nodes {a} and {b} are in the same block.
 221   bool SameBasicBlock(Node* a, Node* b) const;
 222
 223   // BasicBlock building: create a new block.
 224   BasicBlock* NewBasicBlock();
 225
 226   // BasicBlock building: records that a node will later be added to a block but
 227   // doesn't actually add the node to the block.
 228   void PlanNode(BasicBlock* block, Node* node);
 229
 230   // BasicBlock building: add a node to the end of the block.
 231   void AddNode(BasicBlock* block, Node* node);
 232
 233   // BasicBlock building: add a goto to the end of {block}.
 234   void AddGoto(BasicBlock* block, BasicBlock* succ);
 235
 236   // BasicBlock building: add a branch at the end of {block}.
 237   void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
 238                  BasicBlock* fblock);
 239
 240   // BasicBlock building: add a switch at the end of {block}.
 241   void AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
 242                  size_t succ_count);
 243
 244   // BasicBlock building: add a return at the end of {block}.
 245   void AddReturn(BasicBlock* block, Node* input);
 246
 247   // BasicBlock building: add a throw at the end of {block}.
 248   void AddThrow(BasicBlock* block, Node* input);
 249
 250   // BasicBlock mutation: insert a branch into the end of {block}.
 251   void InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
 252                     BasicBlock* tblock, BasicBlock* fblock);
 253
 254   // BasicBlock mutation: insert a switch into the end of {block}.
 255   void InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
 256                     BasicBlock** succ_blocks, size_t succ_count);
 257
 258   // Exposed publicly for testing only.
 259   void AddSuccessorForTesting(BasicBlock* block, BasicBlock* succ) {
 260     return AddSuccessor(block, succ);
 261   }
 262
 263   BasicBlockVector* rpo_order() { return &rpo_order_; }
 264   const BasicBlockVector* rpo_order() const { return &rpo_order_; }
 265
 266   BasicBlock* start() { return start_; }
 267   BasicBlock* end() { return end_; }
 268
 269   Zone* zone() const { return zone_; }
 270
 271  private:
 272   friend class Scheduler;
 273   friend class BasicBlockInstrumentor;
 274
 275   void AddSuccessor(BasicBlock* block, BasicBlock* succ);
 276   void MoveSuccessors(BasicBlock* from, BasicBlock* to);
 277
 278   void SetControlInput(BasicBlock* block, Node* node);
 279   void SetBlockForNode(BasicBlock* block, Node* node);
 280
 281   Zone* zone_;
 282   BasicBlockVector all_blocks_;           // All basic blocks in the schedule.
 283   BasicBlockVector nodeid_to_block_;      // Map from node to containing block.
 284   BasicBlockVector rpo_order_;            // Reverse-post-order block list.
 285   BasicBlock* start_;
 286   BasicBlock* end_;
 287
 288   DISALLOW_COPY_AND_ASSIGN(Schedule);
 289 };
 290
 291 std::ostream& operator<<(std::ostream&, const Schedule&);
 292
 293 }  // namespace compiler
 294 }  // namespace internal
 295 }  // namespace v8
 296
 297 #endif  // V8_COMPILER_SCHEDULE_H_