OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 19 matching lines...) Expand all Loading... |
30 | 30 |
31 #include "v8.h" | 31 #include "v8.h" |
32 | 32 |
33 #include "ast.h" | 33 #include "ast.h" |
34 #include "compiler.h" | 34 #include "compiler.h" |
35 #include "zone-inl.h" | 35 #include "zone-inl.h" |
36 | 36 |
37 namespace v8 { | 37 namespace v8 { |
38 namespace internal { | 38 namespace internal { |
39 | 39 |
| 40 // Forward declarations. |
| 41 class Node; |
| 42 |
40 class BitVector: public ZoneObject { | 43 class BitVector: public ZoneObject { |
41 public: | 44 public: |
42 explicit BitVector(int length) | 45 explicit BitVector(int length) |
43 : length_(length), | 46 : length_(length), |
44 data_length_(SizeFor(length)), | 47 data_length_(SizeFor(length)), |
45 data_(Zone::NewArray<uint32_t>(data_length_)) { | 48 data_(Zone::NewArray<uint32_t>(data_length_)) { |
46 ASSERT(length > 0); | 49 ASSERT(length > 0); |
47 Clear(); | 50 Clear(); |
48 } | 51 } |
49 | 52 |
(...skipping 148 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
198 BitVector* kill() { return kill_; } | 201 BitVector* kill() { return kill_; } |
199 BitVector* gen() { return gen_; } | 202 BitVector* gen() { return gen_; } |
200 | 203 |
201 private: | 204 private: |
202 BitVector* rd_in_; | 205 BitVector* rd_in_; |
203 BitVector* kill_; | 206 BitVector* kill_; |
204 BitVector* gen_; | 207 BitVector* gen_; |
205 }; | 208 }; |
206 | 209 |
207 | 210 |
208 // Flow-graph nodes. | |
209 class Node: public ZoneObject { | |
210 public: | |
211 Node() : number_(-1), mark_(false) {} | |
212 | |
213 virtual ~Node() {} | |
214 | |
215 virtual bool IsExitNode() { return false; } | |
216 virtual bool IsBlockNode() { return false; } | |
217 virtual bool IsBranchNode() { return false; } | |
218 virtual bool IsJoinNode() { return false; } | |
219 | |
220 virtual void AddPredecessor(Node* predecessor) = 0; | |
221 virtual void AddSuccessor(Node* successor) = 0; | |
222 | |
223 bool IsMarkedWith(bool mark) { return mark_ == mark; } | |
224 void MarkWith(bool mark) { mark_ = mark; } | |
225 | |
226 // Perform a depth first search and record preorder and postorder | |
227 // traversal orders. | |
228 virtual void Traverse(bool mark, | |
229 ZoneList<Node*>* preorder, | |
230 ZoneList<Node*>* postorder) = 0; | |
231 | |
232 int number() { return number_; } | |
233 void set_number(int number) { number_ = number; } | |
234 | |
235 // Functions used by data-flow analyses. | |
236 virtual void InitializeReachingDefinitions(int definition_count, | |
237 List<BitVector*>* variables, | |
238 WorkList<Node>* worklist, | |
239 bool mark); | |
240 virtual void ComputeRDOut(BitVector* result) = 0; | |
241 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark) = 0; | |
242 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); | |
243 | |
244 // Functions used by dead-code elimination. | |
245 virtual void MarkCriticalInstructions( | |
246 List<AstNode*>* stack, | |
247 ZoneList<Expression*>* body_definitions, | |
248 int variable_count); | |
249 | |
250 #ifdef DEBUG | |
251 void AssignNodeNumber(); | |
252 void PrintReachingDefinitions(); | |
253 virtual void PrintText() = 0; | |
254 #endif | |
255 | |
256 protected: | |
257 ReachingDefinitionsData rd_; | |
258 | |
259 private: | |
260 int number_; | |
261 bool mark_; | |
262 | |
263 DISALLOW_COPY_AND_ASSIGN(Node); | |
264 }; | |
265 | |
266 | |
267 // An exit node has a arbitrarily many predecessors and no successors. | |
268 class ExitNode: public Node { | |
269 public: | |
270 ExitNode() : predecessors_(4) {} | |
271 | |
272 virtual bool IsExitNode() { return true; } | |
273 | |
274 virtual void AddPredecessor(Node* predecessor) { | |
275 ASSERT(predecessor != NULL); | |
276 predecessors_.Add(predecessor); | |
277 } | |
278 | |
279 virtual void AddSuccessor(Node* successor) { UNREACHABLE(); } | |
280 | |
281 virtual void Traverse(bool mark, | |
282 ZoneList<Node*>* preorder, | |
283 ZoneList<Node*>* postorder); | |
284 | |
285 virtual void ComputeRDOut(BitVector* result); | |
286 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); | |
287 | |
288 #ifdef DEBUG | |
289 virtual void PrintText(); | |
290 #endif | |
291 | |
292 private: | |
293 ZoneList<Node*> predecessors_; | |
294 | |
295 DISALLOW_COPY_AND_ASSIGN(ExitNode); | |
296 }; | |
297 | |
298 | |
299 // Block nodes have a single successor and predecessor and a list of | |
300 // instructions. | |
301 class BlockNode: public Node { | |
302 public: | |
303 BlockNode() : predecessor_(NULL), successor_(NULL), instructions_(4) {} | |
304 | |
305 static BlockNode* cast(Node* node) { | |
306 ASSERT(node->IsBlockNode()); | |
307 return reinterpret_cast<BlockNode*>(node); | |
308 } | |
309 | |
310 virtual bool IsBlockNode() { return true; } | |
311 | |
312 bool is_empty() { return instructions_.is_empty(); } | |
313 | |
314 ZoneList<AstNode*>* instructions() { return &instructions_; } | |
315 | |
316 virtual void AddPredecessor(Node* predecessor) { | |
317 ASSERT(predecessor_ == NULL && predecessor != NULL); | |
318 predecessor_ = predecessor; | |
319 } | |
320 | |
321 virtual void AddSuccessor(Node* successor) { | |
322 ASSERT(successor_ == NULL && successor != NULL); | |
323 successor_ = successor; | |
324 } | |
325 | |
326 void AddInstruction(AstNode* instruction) { | |
327 instructions_.Add(instruction); | |
328 } | |
329 | |
330 virtual void Traverse(bool mark, | |
331 ZoneList<Node*>* preorder, | |
332 ZoneList<Node*>* postorder); | |
333 | |
334 virtual void InitializeReachingDefinitions(int definition_count, | |
335 List<BitVector*>* variables, | |
336 WorkList<Node>* worklist, | |
337 bool mark); | |
338 virtual void ComputeRDOut(BitVector* result); | |
339 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); | |
340 virtual void PropagateReachingDefinitions(List<BitVector*>* variables); | |
341 | |
342 virtual void MarkCriticalInstructions( | |
343 List<AstNode*>* stack, | |
344 ZoneList<Expression*>* body_definitions, | |
345 int variable_count); | |
346 | |
347 #ifdef DEBUG | |
348 virtual void PrintText(); | |
349 #endif | |
350 | |
351 private: | |
352 Node* predecessor_; | |
353 Node* successor_; | |
354 ZoneList<AstNode*> instructions_; | |
355 | |
356 DISALLOW_COPY_AND_ASSIGN(BlockNode); | |
357 }; | |
358 | |
359 | |
360 // Branch nodes have a single predecessor and a pair of successors. | |
361 class BranchNode: public Node { | |
362 public: | |
363 BranchNode() : predecessor_(NULL), successor0_(NULL), successor1_(NULL) {} | |
364 | |
365 virtual bool IsBranchNode() { return true; } | |
366 | |
367 virtual void AddPredecessor(Node* predecessor) { | |
368 ASSERT(predecessor_ == NULL && predecessor != NULL); | |
369 predecessor_ = predecessor; | |
370 } | |
371 | |
372 virtual void AddSuccessor(Node* successor) { | |
373 ASSERT(successor1_ == NULL && successor != NULL); | |
374 if (successor0_ == NULL) { | |
375 successor0_ = successor; | |
376 } else { | |
377 successor1_ = successor; | |
378 } | |
379 } | |
380 | |
381 virtual void Traverse(bool mark, | |
382 ZoneList<Node*>* preorder, | |
383 ZoneList<Node*>* postorder); | |
384 | |
385 virtual void ComputeRDOut(BitVector* result); | |
386 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); | |
387 | |
388 #ifdef DEBUG | |
389 virtual void PrintText(); | |
390 #endif | |
391 | |
392 private: | |
393 Node* predecessor_; | |
394 Node* successor0_; | |
395 Node* successor1_; | |
396 | |
397 DISALLOW_COPY_AND_ASSIGN(BranchNode); | |
398 }; | |
399 | |
400 | |
401 // Join nodes have arbitrarily many predecessors and a single successor. | |
402 class JoinNode: public Node { | |
403 public: | |
404 JoinNode() : predecessors_(2), successor_(NULL) {} | |
405 | |
406 static JoinNode* cast(Node* node) { | |
407 ASSERT(node->IsJoinNode()); | |
408 return reinterpret_cast<JoinNode*>(node); | |
409 } | |
410 | |
411 virtual bool IsJoinNode() { return true; } | |
412 | |
413 virtual void AddPredecessor(Node* predecessor) { | |
414 ASSERT(predecessor != NULL); | |
415 predecessors_.Add(predecessor); | |
416 } | |
417 | |
418 virtual void AddSuccessor(Node* successor) { | |
419 ASSERT(successor_ == NULL && successor != NULL); | |
420 successor_ = successor; | |
421 } | |
422 | |
423 virtual void Traverse(bool mark, | |
424 ZoneList<Node*>* preorder, | |
425 ZoneList<Node*>* postorder); | |
426 | |
427 virtual void ComputeRDOut(BitVector* result); | |
428 virtual void UpdateRDIn(WorkList<Node>* worklist, bool mark); | |
429 | |
430 #ifdef DEBUG | |
431 virtual void PrintText(); | |
432 #endif | |
433 | |
434 private: | |
435 ZoneList<Node*> predecessors_; | |
436 Node* successor_; | |
437 | |
438 DISALLOW_COPY_AND_ASSIGN(JoinNode); | |
439 }; | |
440 | |
441 | |
442 // Flow graphs have a single entry and single exit. The empty flowgraph is | |
443 // represented by both entry and exit being NULL. | |
444 class FlowGraph BASE_EMBEDDED { | |
445 public: | |
446 static FlowGraph Empty() { | |
447 FlowGraph graph; | |
448 graph.entry_ = new BlockNode(); | |
449 graph.exit_ = graph.entry_; | |
450 return graph; | |
451 } | |
452 | |
453 bool is_empty() const { | |
454 return entry_ == exit_ && BlockNode::cast(entry_)->is_empty(); | |
455 } | |
456 Node* entry() const { return entry_; } | |
457 Node* exit() const { return exit_; } | |
458 | |
459 // Add a single instruction to the end of this flowgraph. | |
460 void AppendInstruction(AstNode* instruction); | |
461 | |
462 // Add a single node to the end of this flow graph. | |
463 void AppendNode(Node* node); | |
464 | |
465 // Add a flow graph fragment to the end of this one. | |
466 void AppendGraph(FlowGraph* graph); | |
467 | |
468 // Concatenate an if-then-else flow-graph to this one. Control is split | |
469 // and merged, so the graph remains single-entry, single-exit. | |
470 void Split(BranchNode* branch, | |
471 FlowGraph* left, | |
472 FlowGraph* right, | |
473 JoinNode* merge); | |
474 | |
475 // Concatenate a forward loop (e.g., while or for loop) flow-graph to this | |
476 // one. Control is split by the condition and merged back from the back | |
477 // edge at end of the body to the beginning of the condition. The single | |
478 // (free) exit of the result graph is the right (false) arm of the branch | |
479 // node. | |
480 void Loop(JoinNode* merge, | |
481 FlowGraph* condition, | |
482 BranchNode* branch, | |
483 FlowGraph* body); | |
484 | |
485 #ifdef DEBUG | |
486 void PrintText(FunctionLiteral* fun, ZoneList<Node*>* postorder); | |
487 #endif | |
488 | |
489 private: | |
490 FlowGraph() : entry_(NULL), exit_(NULL) {} | |
491 | |
492 Node* entry_; | |
493 Node* exit_; | |
494 }; | |
495 | |
496 | |
497 // Construct a flow graph from a function literal. Build pre- and postorder | |
498 // traversal orders as a byproduct. | |
499 class FlowGraphBuilder: public AstVisitor { | |
500 public: | |
501 explicit FlowGraphBuilder(int variable_count) | |
502 : graph_(FlowGraph::Empty()), | |
503 global_exit_(NULL), | |
504 preorder_(4), | |
505 postorder_(4), | |
506 variable_count_(variable_count), | |
507 body_definitions_(4) { | |
508 } | |
509 | |
510 void Build(FunctionLiteral* lit); | |
511 | |
512 FlowGraph* graph() { return &graph_; } | |
513 ZoneList<Node*>* preorder() { return &preorder_; } | |
514 ZoneList<Node*>* postorder() { return &postorder_; } | |
515 ZoneList<Expression*>* body_definitions() { return &body_definitions_; } | |
516 | |
517 private: | |
518 ExitNode* global_exit() { return global_exit_; } | |
519 | |
520 // Helpers to allow tranforming the ast during flow graph construction. | |
521 void VisitStatements(ZoneList<Statement*>* stmts); | |
522 Statement* ProcessStatement(Statement* stmt); | |
523 | |
524 // AST node visit functions. | |
525 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); | |
526 AST_NODE_LIST(DECLARE_VISIT) | |
527 #undef DECLARE_VISIT | |
528 | |
529 FlowGraph graph_; | |
530 ExitNode* global_exit_; | |
531 ZoneList<Node*> preorder_; | |
532 ZoneList<Node*> postorder_; | |
533 | |
534 // The flow graph builder collects a list of explicit definitions | |
535 // (assignments and count operations) to stack-allocated variables to use | |
536 // for reaching definitions analysis. It does not count the implicit | |
537 // definition at function entry. AST node numbers in the AST are used to | |
538 // refer into this list. | |
539 int variable_count_; | |
540 ZoneList<Expression*> body_definitions_; | |
541 | |
542 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); | |
543 }; | |
544 | |
545 | |
546 // This class is used to number all expressions in the AST according to | 211 // This class is used to number all expressions in the AST according to |
547 // their evaluation order (post-order left-to-right traversal). | 212 // their evaluation order (post-order left-to-right traversal). |
548 class AstLabeler: public AstVisitor { | 213 class AstLabeler: public AstVisitor { |
549 public: | 214 public: |
550 AstLabeler() : next_number_(0) {} | 215 AstLabeler() : next_number_(0) {} |
551 | 216 |
552 void Label(CompilationInfo* info); | 217 void Label(CompilationInfo* info); |
553 | 218 |
554 private: | 219 private: |
555 CompilationInfo* info() { return info_; } | 220 CompilationInfo* info() { return info_; } |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
663 | 328 |
664 void MarkLiveCode(ZoneList<Node*>* nodes, | 329 void MarkLiveCode(ZoneList<Node*>* nodes, |
665 ZoneList<Expression*>* body_definitions, | 330 ZoneList<Expression*>* body_definitions, |
666 int variable_count); | 331 int variable_count); |
667 | 332 |
668 | 333 |
669 } } // namespace v8::internal | 334 } } // namespace v8::internal |
670 | 335 |
671 | 336 |
672 #endif // V8_DATAFLOW_H_ | 337 #endif // V8_DATAFLOW_H_ |
OLD | NEW |