src/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 <vector>
   9
  10 #include "src/v8.h"
  11
  12 #include "src/compiler/generic-algorithm.h"
  13 #include "src/compiler/generic-graph.h"
  14 #include "src/compiler/generic-node.h"
  15 #include "src/compiler/generic-node-inl.h"
  16 #include "src/compiler/node.h"
  17 #include "src/compiler/opcodes.h"
  18 #include "src/zone.h"
  19
  20 namespace v8 {
  21 namespace internal {
  22 namespace compiler {
  23
  24 class BasicBlock;
  25 class Graph;
  26 class ConstructScheduleData;
  27 class CodeGenerator;  // Because of a namespace bug in clang.
  28
  29 class BasicBlockData {
  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     kReturn,  // Return a value from this method.
  37     kThrow    // Throw an exception.
  38   };
  39
  40   int32_t rpo_number_;       // special RPO number of the block.
  41   BasicBlock* dominator_;    // Immediate dominator of the block.
  42   BasicBlock* loop_header_;  // Pointer to dominating loop header basic block,
  43                              // NULL if none. For loop headers, this points to
  44                              // enclosing loop header.
  45   int32_t loop_depth_;       // loop nesting, 0 is top-level
  46   int32_t loop_end_;         // end of the loop, if this block is a loop header.
  47   int32_t code_start_;       // start index of arch-specific code.
  48   int32_t code_end_;         // end index of arch-specific code.
  49   bool deferred_;            // {true} if this block is considered the slow
  50                              // path.
  51   Control control_;          // Control at the end of the block.
  52   Node* control_input_;      // Input value for control.
  53   NodeVector nodes_;         // nodes of this block in forward order.
  54
  55   explicit BasicBlockData(Zone* zone)
  56       : rpo_number_(-1),
  57         dominator_(NULL),
  58         loop_header_(NULL),
  59         loop_depth_(0),
  60         loop_end_(-1),
  61         code_start_(-1),
  62         code_end_(-1),
  63         deferred_(false),
  64         control_(kNone),
  65         control_input_(NULL),
  66         nodes_(zone) {}
  67
  68   inline bool IsLoopHeader() const { return loop_end_ >= 0; }
  69   inline bool LoopContains(BasicBlockData* block) const {
  70     // RPO numbers must be initialized.
  71     DCHECK(rpo_number_ >= 0);
  72     DCHECK(block->rpo_number_ >= 0);
  73     if (loop_end_ < 0) return false;  // This is not a loop.
  74     return block->rpo_number_ >= rpo_number_ && block->rpo_number_ < loop_end_;
  75   }
  76   int first_instruction_index() {
  77     DCHECK(code_start_ >= 0);
  78     DCHECK(code_end_ > 0);
  79     DCHECK(code_end_ >= code_start_);
  80     return code_start_;
  81   }
  82   int last_instruction_index() {
  83     DCHECK(code_start_ >= 0);
  84     DCHECK(code_end_ > 0);
  85     DCHECK(code_end_ >= code_start_);
  86     return code_end_ - 1;
  87   }
  88 };
  89
  90 OStream& operator<<(OStream& os, const BasicBlockData::Control& c);
  91
  92 // A basic block contains an ordered list of nodes and ends with a control
  93 // node. Note that if a basic block has phis, then all phis must appear as the
  94 // first nodes in the block.
  95 class BasicBlock FINAL : public GenericNode<BasicBlockData, BasicBlock> {
  96  public:
  97   BasicBlock(GenericGraphBase* graph, int input_count)
  98       : GenericNode<BasicBlockData, BasicBlock>(graph, input_count) {}
  99
 100   typedef Uses Successors;
 101   typedef Inputs Predecessors;
 102
 103   Successors successors() { return static_cast<Successors>(uses()); }
 104   Predecessors predecessors() { return static_cast<Predecessors>(inputs()); }
 105
 106   int PredecessorCount() { return InputCount(); }
 107   BasicBlock* PredecessorAt(int index) { return InputAt(index); }
 108
 109   int SuccessorCount() { return UseCount(); }
 110   BasicBlock* SuccessorAt(int index) { return UseAt(index); }
 111
 112   int PredecessorIndexOf(BasicBlock* predecessor) {
 113     BasicBlock::Predecessors predecessors = this->predecessors();
 114     for (BasicBlock::Predecessors::iterator i = predecessors.begin();
 115          i != predecessors.end(); ++i) {
 116       if (*i == predecessor) return i.index();
 117     }
 118     return -1;
 119   }
 120
 121   inline BasicBlock* loop_header() {
 122     return static_cast<BasicBlock*>(loop_header_);
 123   }
 124   inline BasicBlock* ContainingLoop() {
 125     if (IsLoopHeader()) return this;
 126     return static_cast<BasicBlock*>(loop_header_);
 127   }
 128
 129   typedef NodeVector::iterator iterator;
 130   iterator begin() { return nodes_.begin(); }
 131   iterator end() { return nodes_.end(); }
 132
 133   typedef NodeVector::const_iterator const_iterator;
 134   const_iterator begin() const { return nodes_.begin(); }
 135   const_iterator end() const { return nodes_.end(); }
 136
 137   typedef NodeVector::reverse_iterator reverse_iterator;
 138   reverse_iterator rbegin() { return nodes_.rbegin(); }
 139   reverse_iterator rend() { return nodes_.rend(); }
 140
 141  private:
 142   DISALLOW_COPY_AND_ASSIGN(BasicBlock);
 143 };
 144
 145 typedef GenericGraphVisit::NullNodeVisitor<BasicBlockData, BasicBlock>
 146     NullBasicBlockVisitor;
 147
 148 typedef ZoneVector<BasicBlock*> BasicBlockVector;
 149 typedef BasicBlockVector::iterator BasicBlockVectorIter;
 150 typedef BasicBlockVector::reverse_iterator BasicBlockVectorRIter;
 151
 152 // A schedule represents the result of assigning nodes to basic blocks
 153 // and ordering them within basic blocks. Prior to computing a schedule,
 154 // a graph has no notion of control flow ordering other than that induced
 155 // by the graph's dependencies. A schedule is required to generate code.
 156 class Schedule : public GenericGraph<BasicBlock> {
 157  public:
 158   explicit Schedule(Zone* zone)
 159       : GenericGraph<BasicBlock>(zone),
 160         zone_(zone),
 161         all_blocks_(zone),
 162         nodeid_to_block_(zone),
 163         rpo_order_(zone) {
 164     SetStart(NewBasicBlock());  // entry.
 165     SetEnd(NewBasicBlock());    // exit.
 166   }
 167
 168   // Return the block which contains {node}, if any.
 169   BasicBlock* block(Node* node) const {
 170     if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) {
 171       return nodeid_to_block_[node->id()];
 172     }
 173     return NULL;
 174   }
 175
 176   bool IsScheduled(Node* node) {
 177     int length = static_cast<int>(nodeid_to_block_.size());
 178     if (node->id() >= length) return false;
 179     return nodeid_to_block_[node->id()] != NULL;
 180   }
 181
 182   BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; }
 183
 184   int BasicBlockCount() const { return NodeCount(); }
 185   int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); }
 186
 187   typedef ContainerPointerWrapper<BasicBlockVector> BasicBlocks;
 188
 189   // Return a list of all the blocks in the schedule, in arbitrary order.
 190   BasicBlocks all_blocks() { return BasicBlocks(&all_blocks_); }
 191
 192   // Check if nodes {a} and {b} are in the same block.
 193   inline bool SameBasicBlock(Node* a, Node* b) const {
 194     BasicBlock* block = this->block(a);
 195     return block != NULL && block == this->block(b);
 196   }
 197
 198   // BasicBlock building: create a new block.
 199   inline BasicBlock* NewBasicBlock() {
 200     BasicBlock* block =
 201         BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL));
 202     all_blocks_.push_back(block);
 203     return block;
 204   }
 205
 206   // BasicBlock building: records that a node will later be added to a block but
 207   // doesn't actually add the node to the block.
 208   inline void PlanNode(BasicBlock* block, Node* node) {
 209     if (FLAG_trace_turbo_scheduler) {
 210       PrintF("Planning #%d:%s for future add to B%d\n", node->id(),
 211              node->op()->mnemonic(), block->id());
 212     }
 213     DCHECK(this->block(node) == NULL);
 214     SetBlockForNode(block, node);
 215   }
 216
 217   // BasicBlock building: add a node to the end of the block.
 218   inline void AddNode(BasicBlock* block, Node* node) {
 219     if (FLAG_trace_turbo_scheduler) {
 220       PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(),
 221              block->id());
 222     }
 223     DCHECK(this->block(node) == NULL || this->block(node) == block);
 224     block->nodes_.push_back(node);
 225     SetBlockForNode(block, node);
 226   }
 227
 228   // BasicBlock building: add a goto to the end of {block}.
 229   void AddGoto(BasicBlock* block, BasicBlock* succ) {
 230     DCHECK(block->control_ == BasicBlock::kNone);
 231     block->control_ = BasicBlock::kGoto;
 232     AddSuccessor(block, succ);
 233   }
 234
 235   // BasicBlock building: add a branch at the end of {block}.
 236   void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
 237                  BasicBlock* fblock) {
 238     DCHECK(block->control_ == BasicBlock::kNone);
 239     DCHECK(branch->opcode() == IrOpcode::kBranch);
 240     block->control_ = BasicBlock::kBranch;
 241     AddSuccessor(block, tblock);
 242     AddSuccessor(block, fblock);
 243     SetControlInput(block, branch);
 244     if (branch->opcode() == IrOpcode::kBranch) {
 245       // TODO(titzer): require a Branch node here. (sloppy tests).
 246       SetBlockForNode(block, branch);
 247     }
 248   }
 249
 250   // BasicBlock building: add a return at the end of {block}.
 251   void AddReturn(BasicBlock* block, Node* input) {
 252     DCHECK(block->control_ == BasicBlock::kNone);
 253     block->control_ = BasicBlock::kReturn;
 254     SetControlInput(block, input);
 255     if (block != end()) AddSuccessor(block, end());
 256     if (input->opcode() == IrOpcode::kReturn) {
 257       // TODO(titzer): require a Return node here. (sloppy tests).
 258       SetBlockForNode(block, input);
 259     }
 260   }
 261
 262   // BasicBlock building: add a throw at the end of {block}.
 263   void AddThrow(BasicBlock* block, Node* input) {
 264     DCHECK(block->control_ == BasicBlock::kNone);
 265     block->control_ = BasicBlock::kThrow;
 266     SetControlInput(block, input);
 267     if (block != end()) AddSuccessor(block, end());
 268   }
 269
 270   friend class Scheduler;
 271   friend class CodeGenerator;
 272
 273   void AddSuccessor(BasicBlock* block, BasicBlock* succ) {
 274     succ->AppendInput(zone_, block);
 275   }
 276
 277   BasicBlockVector* rpo_order() { return &rpo_order_; }
 278
 279  private:
 280   friend class ScheduleVisualizer;
 281
 282   void SetControlInput(BasicBlock* block, Node* node) {
 283     block->control_input_ = node;
 284     SetBlockForNode(block, node);
 285   }
 286
 287   void SetBlockForNode(BasicBlock* block, Node* node) {
 288     int length = static_cast<int>(nodeid_to_block_.size());
 289     if (node->id() >= length) {
 290       nodeid_to_block_.resize(node->id() + 1);
 291     }
 292     nodeid_to_block_[node->id()] = block;
 293   }
 294
 295   Zone* zone_;
 296   BasicBlockVector all_blocks_;           // All basic blocks in the schedule.
 297   BasicBlockVector nodeid_to_block_;      // Map from node to containing block.
 298   BasicBlockVector rpo_order_;            // Reverse-post-order block list.
 299 };
 300
 301 OStream& operator<<(OStream& os, const Schedule& s);
 302 }
 303 }
 304 }  // namespace v8::internal::compiler
 305
 306 #endif  // V8_COMPILER_SCHEDULE_H_