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.
5 #ifndef V8_COMPILER_SCHEDULE_H_
6 #define V8_COMPILER_SCHEDULE_H_
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"
26 class ConstructScheduleData;
27 class CodeGenerator; // Because of a namespace bug in clang.
29 class BasicBlockData {
31 // Possible control nodes that can end a block.
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.
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
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.
55 explicit BasicBlockData(Zone* zone)
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_;
76 int first_instruction_index() {
77 DCHECK(code_start_ >= 0);
78 DCHECK(code_end_ > 0);
79 DCHECK(code_end_ >= code_start_);
82 int last_instruction_index() {
83 DCHECK(code_start_ >= 0);
84 DCHECK(code_end_ > 0);
85 DCHECK(code_end_ >= code_start_);
90 OStream& operator<<(OStream& os, const BasicBlockData::Control& c);
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> {
97 BasicBlock(GenericGraphBase* graph, int input_count)
98 : GenericNode<BasicBlockData, BasicBlock>(graph, input_count) {}
100 typedef Uses Successors;
101 typedef Inputs Predecessors;
103 Successors successors() { return static_cast<Successors>(uses()); }
104 Predecessors predecessors() { return static_cast<Predecessors>(inputs()); }
106 int PredecessorCount() { return InputCount(); }
107 BasicBlock* PredecessorAt(int index) { return InputAt(index); }
109 int SuccessorCount() { return UseCount(); }
110 BasicBlock* SuccessorAt(int index) { return UseAt(index); }
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();
121 inline BasicBlock* loop_header() {
122 return static_cast<BasicBlock*>(loop_header_);
124 inline BasicBlock* ContainingLoop() {
125 if (IsLoopHeader()) return this;
126 return static_cast<BasicBlock*>(loop_header_);
129 typedef NodeVector::iterator iterator;
130 iterator begin() { return nodes_.begin(); }
131 iterator end() { return nodes_.end(); }
133 typedef NodeVector::const_iterator const_iterator;
134 const_iterator begin() const { return nodes_.begin(); }
135 const_iterator end() const { return nodes_.end(); }
137 typedef NodeVector::reverse_iterator reverse_iterator;
138 reverse_iterator rbegin() { return nodes_.rbegin(); }
139 reverse_iterator rend() { return nodes_.rend(); }
142 DISALLOW_COPY_AND_ASSIGN(BasicBlock);
145 typedef GenericGraphVisit::NullNodeVisitor<BasicBlockData, BasicBlock>
146 NullBasicBlockVisitor;
148 typedef ZoneVector<BasicBlock*> BasicBlockVector;
149 typedef BasicBlockVector::iterator BasicBlockVectorIter;
150 typedef BasicBlockVector::reverse_iterator BasicBlockVectorRIter;
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> {
158 explicit Schedule(Zone* zone)
159 : GenericGraph<BasicBlock>(zone),
162 nodeid_to_block_(zone),
164 SetStart(NewBasicBlock()); // entry.
165 SetEnd(NewBasicBlock()); // exit.
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()];
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;
182 BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; }
184 int BasicBlockCount() const { return NodeCount(); }
185 int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); }
187 typedef ContainerPointerWrapper<BasicBlockVector> BasicBlocks;
189 // Return a list of all the blocks in the schedule, in arbitrary order.
190 BasicBlocks all_blocks() { return BasicBlocks(&all_blocks_); }
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);
198 // BasicBlock building: create a new block.
199 inline BasicBlock* NewBasicBlock() {
201 BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL));
202 all_blocks_.push_back(block);
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());
213 DCHECK(this->block(node) == NULL);
214 SetBlockForNode(block, node);
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(),
223 DCHECK(this->block(node) == NULL || this->block(node) == block);
224 block->nodes_.push_back(node);
225 SetBlockForNode(block, node);
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);
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);
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);
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());
270 friend class Scheduler;
271 friend class CodeGenerator;
273 void AddSuccessor(BasicBlock* block, BasicBlock* succ) {
274 succ->AppendInput(zone_, block);
277 BasicBlockVector* rpo_order() { return &rpo_order_; }
280 friend class ScheduleVisualizer;
282 void SetControlInput(BasicBlock* block, Node* node) {
283 block->control_input_ = node;
284 SetBlockForNode(block, node);
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);
292 nodeid_to_block_[node->id()] = block;
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.
301 OStream& operator<<(OStream& os, const Schedule& s);
304 } // namespace v8::internal::compiler
306 #endif // V8_COMPILER_SCHEDULE_H_