OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_COMPILER_SCHEDULE_H_ | 5 #ifndef V8_COMPILER_SCHEDULE_H_ |
6 #define V8_COMPILER_SCHEDULE_H_ | 6 #define V8_COMPILER_SCHEDULE_H_ |
7 | 7 |
8 #include <vector> | 8 #include <vector> |
9 | 9 |
10 #include "src/v8.h" | 10 #include "src/v8.h" |
(...skipping 22 matching lines...) Expand all Loading... |
33 kNone, // Control not initialized yet. | 33 kNone, // Control not initialized yet. |
34 kGoto, // Goto a single successor block. | 34 kGoto, // Goto a single successor block. |
35 kBranch, // Branch if true to first successor, otherwise second. | 35 kBranch, // Branch if true to first successor, otherwise second. |
36 kReturn, // Return a value from this method. | 36 kReturn, // Return a value from this method. |
37 kThrow, // Throw an exception. | 37 kThrow, // Throw an exception. |
38 kCall, // Call to a possibly deoptimizing or throwing function. | 38 kCall, // Call to a possibly deoptimizing or throwing function. |
39 kDeoptimize // Deoptimize. | 39 kDeoptimize // Deoptimize. |
40 }; | 40 }; |
41 | 41 |
42 int32_t rpo_number_; // special RPO number of the block. | 42 int32_t rpo_number_; // special RPO number of the block. |
| 43 BasicBlock* dominator_; // Immediate dominator of the block. |
43 BasicBlock* loop_header_; // Pointer to dominating loop header basic block, | 44 BasicBlock* loop_header_; // Pointer to dominating loop header basic block, |
44 // NULL if none. For loop headers, this points to | 45 // NULL if none. For loop headers, this points to |
45 // enclosing loop header. | 46 // enclosing loop header. |
46 int32_t loop_depth_; // loop nesting, 0 is top-level | 47 int32_t loop_depth_; // loop nesting, 0 is top-level |
47 int32_t loop_end_; // end of the loop, if this block is a loop header. | 48 int32_t loop_end_; // end of the loop, if this block is a loop header. |
48 int32_t code_start_; // start index of arch-specific code. | 49 int32_t code_start_; // start index of arch-specific code. |
49 int32_t code_end_; // end index of arch-specific code. | 50 int32_t code_end_; // end index of arch-specific code. |
50 bool deferred_; // {true} if this block is considered the slow | 51 bool deferred_; // {true} if this block is considered the slow |
51 // path. | 52 // path. |
52 Control control_; // Control at the end of the block. | 53 Control control_; // Control at the end of the block. |
53 Node* control_input_; // Input value for control. | 54 Node* control_input_; // Input value for control. |
54 NodeVector nodes_; // nodes of this block in forward order. | 55 NodeVector nodes_; // nodes of this block in forward order. |
55 | 56 |
56 explicit BasicBlockData(Zone* zone) | 57 explicit BasicBlockData(Zone* zone) |
57 : rpo_number_(-1), | 58 : rpo_number_(-1), |
| 59 dominator_(NULL), |
58 loop_header_(NULL), | 60 loop_header_(NULL), |
59 loop_depth_(0), | 61 loop_depth_(0), |
60 loop_end_(-1), | 62 loop_end_(-1), |
61 code_start_(-1), | 63 code_start_(-1), |
62 code_end_(-1), | 64 code_end_(-1), |
63 deferred_(false), | 65 deferred_(false), |
64 control_(kNone), | 66 control_(kNone), |
65 control_input_(NULL), | 67 control_input_(NULL), |
66 nodes_(zone) {} | 68 nodes_(zone) {} |
67 | 69 |
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
153 // and ordering them within basic blocks. Prior to computing a schedule, | 155 // 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 | 156 // 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. | 157 // by the graph's dependencies. A schedule is required to generate code. |
156 class Schedule : public GenericGraph<BasicBlock> { | 158 class Schedule : public GenericGraph<BasicBlock> { |
157 public: | 159 public: |
158 explicit Schedule(Zone* zone) | 160 explicit Schedule(Zone* zone) |
159 : GenericGraph<BasicBlock>(zone), | 161 : GenericGraph<BasicBlock>(zone), |
160 zone_(zone), | 162 zone_(zone), |
161 all_blocks_(zone), | 163 all_blocks_(zone), |
162 nodeid_to_block_(zone), | 164 nodeid_to_block_(zone), |
163 rpo_order_(zone), | 165 rpo_order_(zone) { |
164 immediate_dominator_(zone) { | |
165 SetStart(NewBasicBlock()); // entry. | 166 SetStart(NewBasicBlock()); // entry. |
166 SetEnd(NewBasicBlock()); // exit. | 167 SetEnd(NewBasicBlock()); // exit. |
167 } | 168 } |
168 | 169 |
169 // Return the block which contains {node}, if any. | 170 // Return the block which contains {node}, if any. |
170 BasicBlock* block(Node* node) const { | 171 BasicBlock* block(Node* node) const { |
171 if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { | 172 if (node->id() < static_cast<NodeId>(nodeid_to_block_.size())) { |
172 return nodeid_to_block_[node->id()]; | 173 return nodeid_to_block_[node->id()]; |
173 } | 174 } |
174 return NULL; | 175 return NULL; |
175 } | 176 } |
176 | 177 |
177 BasicBlock* dominator(BasicBlock* block) { | |
178 return immediate_dominator_[block->id()]; | |
179 } | |
180 | |
181 bool IsScheduled(Node* node) { | 178 bool IsScheduled(Node* node) { |
182 int length = static_cast<int>(nodeid_to_block_.size()); | 179 int length = static_cast<int>(nodeid_to_block_.size()); |
183 if (node->id() >= length) return false; | 180 if (node->id() >= length) return false; |
184 return nodeid_to_block_[node->id()] != NULL; | 181 return nodeid_to_block_[node->id()] != NULL; |
185 } | 182 } |
186 | 183 |
187 BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; } | 184 BasicBlock* GetBlockById(int block_id) { return all_blocks_[block_id]; } |
188 | 185 |
189 int BasicBlockCount() const { return NodeCount(); } | 186 int BasicBlockCount() const { return NodeCount(); } |
190 int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); } | 187 int RpoBlockCount() const { return static_cast<int>(rpo_order_.size()); } |
(...skipping 14 matching lines...) Expand all Loading... |
205 BasicBlock* block = | 202 BasicBlock* block = |
206 BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL)); | 203 BasicBlock::New(this, 0, static_cast<BasicBlock**>(NULL)); |
207 all_blocks_.push_back(block); | 204 all_blocks_.push_back(block); |
208 return block; | 205 return block; |
209 } | 206 } |
210 | 207 |
211 // BasicBlock building: records that a node will later be added to a block but | 208 // BasicBlock building: records that a node will later be added to a block but |
212 // doesn't actually add the node to the block. | 209 // doesn't actually add the node to the block. |
213 inline void PlanNode(BasicBlock* block, Node* node) { | 210 inline void PlanNode(BasicBlock* block, Node* node) { |
214 if (FLAG_trace_turbo_scheduler) { | 211 if (FLAG_trace_turbo_scheduler) { |
215 PrintF("Planning node %d for future add to block %d\n", node->id(), | 212 PrintF("Planning #%d:%s for future add to B%d\n", node->id(), |
216 block->id()); | 213 node->op()->mnemonic(), block->id()); |
217 } | 214 } |
218 DCHECK(this->block(node) == NULL); | 215 DCHECK(this->block(node) == NULL); |
219 SetBlockForNode(block, node); | 216 SetBlockForNode(block, node); |
220 } | 217 } |
221 | 218 |
222 // BasicBlock building: add a node to the end of the block. | 219 // BasicBlock building: add a node to the end of the block. |
223 inline void AddNode(BasicBlock* block, Node* node) { | 220 inline void AddNode(BasicBlock* block, Node* node) { |
224 if (FLAG_trace_turbo_scheduler) { | 221 if (FLAG_trace_turbo_scheduler) { |
225 PrintF("Adding node %d to block %d\n", node->id(), block->id()); | 222 PrintF("Adding #%d:%s to B%d\n", node->id(), node->op()->mnemonic(), |
| 223 block->id()); |
226 } | 224 } |
227 DCHECK(this->block(node) == NULL || this->block(node) == block); | 225 DCHECK(this->block(node) == NULL || this->block(node) == block); |
228 block->nodes_.push_back(node); | 226 block->nodes_.push_back(node); |
229 SetBlockForNode(block, node); | 227 SetBlockForNode(block, node); |
230 } | 228 } |
231 | 229 |
232 // BasicBlock building: add a goto to the end of {block}. | 230 // BasicBlock building: add a goto to the end of {block}. |
233 void AddGoto(BasicBlock* block, BasicBlock* succ) { | 231 void AddGoto(BasicBlock* block, BasicBlock* succ) { |
234 DCHECK(block->control_ == BasicBlock::kNone); | 232 DCHECK(block->control_ == BasicBlock::kNone); |
235 block->control_ = BasicBlock::kGoto; | 233 block->control_ = BasicBlock::kGoto; |
236 AddSuccessor(block, succ); | 234 AddSuccessor(block, succ); |
237 } | 235 } |
238 | 236 |
239 // BasicBlock building: add a (branching) call at the end of {block}. | 237 // BasicBlock building: add a (branching) call at the end of {block}. |
240 void AddCall(BasicBlock* block, Node* call, BasicBlock* cont_block, | 238 void AddCall(BasicBlock* block, Node* call, BasicBlock* cont_block, |
241 BasicBlock* deopt_block) { | 239 BasicBlock* deopt_block) { |
242 DCHECK(block->control_ == BasicBlock::kNone); | 240 DCHECK(block->control_ == BasicBlock::kNone); |
243 DCHECK(call->opcode() == IrOpcode::kCall); | 241 DCHECK(call->opcode() == IrOpcode::kCall); |
244 block->control_ = BasicBlock::kCall; | 242 block->control_ = BasicBlock::kCall; |
245 // Insert the deopt block first so that the RPO order builder picks | 243 // Insert the deopt block first so that the RPO order builder picks |
246 // it first (and thus it ends up late in the RPO order). | 244 // it first (and thus it ends up late in the RPO order). |
247 AddSuccessor(block, deopt_block); | 245 AddSuccessor(block, deopt_block); |
248 AddSuccessor(block, cont_block); | 246 AddSuccessor(block, cont_block); |
249 SetControlInput(block, call); | 247 SetControlInput(block, call); |
| 248 SetBlockForNode(block, call); |
250 } | 249 } |
251 | 250 |
252 // BasicBlock building: add a branch at the end of {block}. | 251 // BasicBlock building: add a branch at the end of {block}. |
253 void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, | 252 void AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock, |
254 BasicBlock* fblock) { | 253 BasicBlock* fblock) { |
255 DCHECK(block->control_ == BasicBlock::kNone); | 254 DCHECK(block->control_ == BasicBlock::kNone); |
256 DCHECK(branch->opcode() == IrOpcode::kBranch); | 255 DCHECK(branch->opcode() == IrOpcode::kBranch); |
257 block->control_ = BasicBlock::kBranch; | 256 block->control_ = BasicBlock::kBranch; |
258 AddSuccessor(block, tblock); | 257 AddSuccessor(block, tblock); |
259 AddSuccessor(block, fblock); | 258 AddSuccessor(block, fblock); |
260 SetControlInput(block, branch); | 259 SetControlInput(block, branch); |
| 260 if (branch->opcode() == IrOpcode::kBranch) { |
| 261 // TODO(titzer): require a Branch node here. (sloppy tests). |
| 262 SetBlockForNode(block, branch); |
| 263 } |
261 } | 264 } |
262 | 265 |
263 // BasicBlock building: add a return at the end of {block}. | 266 // BasicBlock building: add a return at the end of {block}. |
264 void AddReturn(BasicBlock* block, Node* input) { | 267 void AddReturn(BasicBlock* block, Node* input) { |
265 // TODO(titzer): require a Return node here. | |
266 DCHECK(block->control_ == BasicBlock::kNone); | 268 DCHECK(block->control_ == BasicBlock::kNone); |
267 block->control_ = BasicBlock::kReturn; | 269 block->control_ = BasicBlock::kReturn; |
268 SetControlInput(block, input); | 270 SetControlInput(block, input); |
269 if (block != end()) AddSuccessor(block, end()); | 271 if (block != end()) AddSuccessor(block, end()); |
| 272 if (input->opcode() == IrOpcode::kReturn) { |
| 273 // TODO(titzer): require a Return node here. (sloppy tests). |
| 274 SetBlockForNode(block, input); |
| 275 } |
270 } | 276 } |
271 | 277 |
272 // BasicBlock building: add a throw at the end of {block}. | 278 // BasicBlock building: add a throw at the end of {block}. |
273 void AddThrow(BasicBlock* block, Node* input) { | 279 void AddThrow(BasicBlock* block, Node* input) { |
274 DCHECK(block->control_ == BasicBlock::kNone); | 280 DCHECK(block->control_ == BasicBlock::kNone); |
275 block->control_ = BasicBlock::kThrow; | 281 block->control_ = BasicBlock::kThrow; |
276 SetControlInput(block, input); | 282 SetControlInput(block, input); |
277 if (block != end()) AddSuccessor(block, end()); | 283 if (block != end()) AddSuccessor(block, end()); |
278 } | 284 } |
279 | 285 |
(...skipping 28 matching lines...) Expand all Loading... |
308 if (node->id() >= length) { | 314 if (node->id() >= length) { |
309 nodeid_to_block_.resize(node->id() + 1); | 315 nodeid_to_block_.resize(node->id() + 1); |
310 } | 316 } |
311 nodeid_to_block_[node->id()] = block; | 317 nodeid_to_block_[node->id()] = block; |
312 } | 318 } |
313 | 319 |
314 Zone* zone_; | 320 Zone* zone_; |
315 BasicBlockVector all_blocks_; // All basic blocks in the schedule. | 321 BasicBlockVector all_blocks_; // All basic blocks in the schedule. |
316 BasicBlockVector nodeid_to_block_; // Map from node to containing block. | 322 BasicBlockVector nodeid_to_block_; // Map from node to containing block. |
317 BasicBlockVector rpo_order_; // Reverse-post-order block list. | 323 BasicBlockVector rpo_order_; // Reverse-post-order block list. |
318 BasicBlockVector immediate_dominator_; // Maps to a block's immediate | |
319 // dominator, indexed by block | |
320 // id. | |
321 }; | 324 }; |
322 | 325 |
323 OStream& operator<<(OStream& os, const Schedule& s); | 326 OStream& operator<<(OStream& os, const Schedule& s); |
324 } | 327 } |
325 } | 328 } |
326 } // namespace v8::internal::compiler | 329 } // namespace v8::internal::compiler |
327 | 330 |
328 #endif // V8_COMPILER_SCHEDULE_H_ | 331 #endif // V8_COMPILER_SCHEDULE_H_ |
OLD | NEW |