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 467 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
478 | 478 |
479 Node* entry_; | 479 Node* entry_; |
480 Node* exit_; | 480 Node* exit_; |
481 }; | 481 }; |
482 | 482 |
483 | 483 |
484 // Construct a flow graph from a function literal. Build pre- and postorder | 484 // Construct a flow graph from a function literal. Build pre- and postorder |
485 // traversal orders as a byproduct. | 485 // traversal orders as a byproduct. |
486 class FlowGraphBuilder: public AstVisitor { | 486 class FlowGraphBuilder: public AstVisitor { |
487 public: | 487 public: |
488 FlowGraphBuilder() | 488 explicit FlowGraphBuilder(int variable_count) |
489 : graph_(FlowGraph::Empty()), | 489 : graph_(FlowGraph::Empty()), |
490 global_exit_(NULL), | 490 global_exit_(NULL), |
491 preorder_(4), | 491 preorder_(4), |
492 postorder_(4), | 492 postorder_(4), |
493 definitions_(4) { | 493 variable_count_(variable_count), |
| 494 body_definitions_(4) { |
494 } | 495 } |
495 | 496 |
496 void Build(FunctionLiteral* lit); | 497 void Build(FunctionLiteral* lit); |
497 | 498 |
498 FlowGraph* graph() { return &graph_; } | 499 FlowGraph* graph() { return &graph_; } |
499 ZoneList<Node*>* postorder() { return &postorder_; } | 500 ZoneList<Node*>* postorder() { return &postorder_; } |
500 ZoneList<Expression*>* definitions() { return &definitions_; } | 501 ZoneList<Expression*>* body_definitions() { return &body_definitions_; } |
501 | 502 |
502 private: | 503 private: |
503 ExitNode* global_exit() { return global_exit_; } | 504 ExitNode* global_exit() { return global_exit_; } |
504 | 505 |
505 // AST node visit functions. | 506 // AST node visit functions. |
506 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); | 507 #define DECLARE_VISIT(type) virtual void Visit##type(type* node); |
507 AST_NODE_LIST(DECLARE_VISIT) | 508 AST_NODE_LIST(DECLARE_VISIT) |
508 #undef DECLARE_VISIT | 509 #undef DECLARE_VISIT |
509 | 510 |
510 FlowGraph graph_; | 511 FlowGraph graph_; |
511 ExitNode* global_exit_; | 512 ExitNode* global_exit_; |
512 ZoneList<Node*> preorder_; | 513 ZoneList<Node*> preorder_; |
513 ZoneList<Node*> postorder_; | 514 ZoneList<Node*> postorder_; |
514 | 515 |
515 // The flow graph builder collects a list of definitions (assignments and | 516 // The flow graph builder collects a list of explicit definitions |
516 // count operations) to stack-allocated variables to use for reaching | 517 // (assignments and count operations) to stack-allocated variables to use |
517 // definitions analysis. AST node numbers in the AST are used to refer | 518 // for reaching definitions analysis. It does not count the implicit |
518 // into this list. | 519 // definition at function entry. AST node numbers in the AST are used to |
519 ZoneList<Expression*> definitions_; | 520 // refer into this list. |
| 521 int variable_count_; |
| 522 ZoneList<Expression*> body_definitions_; |
520 | 523 |
521 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); | 524 DISALLOW_COPY_AND_ASSIGN(FlowGraphBuilder); |
522 }; | 525 }; |
523 | 526 |
524 | 527 |
525 // This class is used to number all expressions in the AST according to | 528 // This class is used to number all expressions in the AST according to |
526 // their evaluation order (post-order left-to-right traversal). | 529 // their evaluation order (post-order left-to-right traversal). |
527 class AstLabeler: public AstVisitor { | 530 class AstLabeler: public AstVisitor { |
528 public: | 531 public: |
529 AstLabeler() : next_number_(0) {} | 532 AstLabeler() : next_number_(0) {} |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
582 // Accumulator for assigned variables set. | 585 // Accumulator for assigned variables set. |
583 BitVector av_; | 586 BitVector av_; |
584 | 587 |
585 DISALLOW_COPY_AND_ASSIGN(AssignedVariablesAnalyzer); | 588 DISALLOW_COPY_AND_ASSIGN(AssignedVariablesAnalyzer); |
586 }; | 589 }; |
587 | 590 |
588 | 591 |
589 class ReachingDefinitions BASE_EMBEDDED { | 592 class ReachingDefinitions BASE_EMBEDDED { |
590 public: | 593 public: |
591 ReachingDefinitions(ZoneList<Node*>* postorder, | 594 ReachingDefinitions(ZoneList<Node*>* postorder, |
592 ZoneList<Expression*>* definitions, | 595 ZoneList<Expression*>* body_definitions, |
593 int variable_count) | 596 int variable_count) |
594 : postorder_(postorder), | 597 : postorder_(postorder), |
595 definitions_(definitions), | 598 body_definitions_(body_definitions), |
596 variables_(variable_count) { | 599 variable_count_(variable_count) { |
597 int definition_count = definitions->length(); | |
598 for (int i = 0; i < variable_count; i++) { | |
599 variables_.Add(new BitVector(definition_count)); | |
600 } | |
601 } | 600 } |
602 | 601 |
603 static int IndexFor(Variable* var, int variable_count); | 602 static int IndexFor(Variable* var, int variable_count); |
604 | 603 |
605 void Compute(); | 604 void Compute(); |
606 | 605 |
607 private: | 606 private: |
608 // A (postorder) list of flow-graph nodes in the body. | 607 // A (postorder) list of flow-graph nodes in the body. |
609 ZoneList<Node*>* postorder_; | 608 ZoneList<Node*>* postorder_; |
610 | 609 |
611 // A list of all the definitions in the body. | 610 // A list of all the definitions in the body. |
612 ZoneList<Expression*>* definitions_; | 611 ZoneList<Expression*>* body_definitions_; |
613 | 612 |
614 // For each variable, the set of all its definitions. | 613 int variable_count_; |
615 List<BitVector*> variables_; | |
616 | 614 |
617 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); | 615 DISALLOW_COPY_AND_ASSIGN(ReachingDefinitions); |
618 }; | 616 }; |
619 | 617 |
620 | 618 |
621 } } // namespace v8::internal | 619 } } // namespace v8::internal |
622 | 620 |
623 | 621 |
624 #endif // V8_DATAFLOW_H_ | 622 #endif // V8_DATAFLOW_H_ |
OLD | NEW |