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
20namespace v8 {
21namespace internal {
22namespace compiler {
23
24class BasicBlock;
25class Graph;
26class ConstructScheduleData;
27class CodeGenerator;  // Because of a namespace bug in clang.
28
29class 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
90OStream& 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.
95class 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
145typedef GenericGraphVisit::NullNodeVisitor<BasicBlockData, BasicBlock>
146    NullBasicBlockVisitor;
147
148typedef ZoneVector<BasicBlock*> BasicBlockVector;
149typedef BasicBlockVector::iterator BasicBlockVectorIter;
150typedef 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.
156class 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
301OStream& operator<<(OStream& os, const Schedule& s);
302}
303}
304}  // namespace v8::internal::compiler
305
306#endif  // V8_COMPILER_SCHEDULE_H_
307