Mercurial > hg > truffle

comparison src/share/vm/opto/loopnode.hpp @ 921:046932b72aa2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
6862956: PhaseIdealLoop should have a CFG verification mode Reviewed-by: kvn, twisti
author never
date Fri, 14 Aug 2009 00:02:12 -0700
parents 98cb887364d3
children b2b6a9bf6238
comparison
equal deleted inserted replaced
910:10d8c0d0d60e 921:046932b72aa2
1 /* 1 /*
2 * Copyright 1998-2008 Sun Microsystems, Inc. All Rights Reserved. 2 * Copyright 1998-2009 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 * 4 *
5 * This code is free software; you can redistribute it and/or modify it 5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as 6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. 7 * published by the Free Software Foundation.
440 // ZERO for not pre-visited. EVEN for pre-visited but not post-visited. 440 // ZERO for not pre-visited. EVEN for pre-visited but not post-visited.
441 // ODD for post-visited. Other bits are the pre-order number. 441 // ODD for post-visited. Other bits are the pre-order number.
442 uint *_preorders; 442 uint *_preorders;
443 uint _max_preorder; 443 uint _max_preorder;
444 444
445 const PhaseIdealLoop* _verify_me;
446 bool _verify_only;
447
445 // Allocate _preorders[] array 448 // Allocate _preorders[] array
446 void allocate_preorders() { 449 void allocate_preorders() {
447 _max_preorder = C->unique()+8; 450 _max_preorder = C->unique()+8;
448 _preorders = NEW_RESOURCE_ARRAY(uint, _max_preorder); 451 _preorders = NEW_RESOURCE_ARRAY(uint, _max_preorder);
449 memset(_preorders, 0, sizeof(uint) * _max_preorder); 452 memset(_preorders, 0, sizeof(uint) * _max_preorder);
495 // Support for faster execution of get_late_ctrl()/dom_lca() 498 // Support for faster execution of get_late_ctrl()/dom_lca()
496 // when a node has many uses and dominator depth is deep. 499 // when a node has many uses and dominator depth is deep.
497 Node_Array _dom_lca_tags; 500 Node_Array _dom_lca_tags;
498 void init_dom_lca_tags(); 501 void init_dom_lca_tags();
499 void clear_dom_lca_tags(); 502 void clear_dom_lca_tags();
503
504 // Helper for debugging bad dominance relationships
505 bool verify_dominance(Node* n, Node* use, Node* LCA, Node* early);
506
507 Node* compute_lca_of_uses(Node* n, Node* early, bool verify = false);
508
500 // Inline wrapper for frequent cases: 509 // Inline wrapper for frequent cases:
501 // 1) only one use 510 // 1) only one use
502 // 2) a use is the same as the current LCA passed as 'n1' 511 // 2) a use is the same as the current LCA passed as 'n1'
503 Node *dom_lca_for_get_late_ctrl( Node *lca, Node *n, Node *tag ) { 512 Node *dom_lca_for_get_late_ctrl( Node *lca, Node *n, Node *tag ) {
504 assert( n->is_CFG(), "" ); 513 assert( n->is_CFG(), "" );
509 n = dom_lca_for_get_late_ctrl_internal( lca, n, tag ); 518 n = dom_lca_for_get_late_ctrl_internal( lca, n, tag );
510 } 519 }
511 return find_non_split_ctrl(n); 520 return find_non_split_ctrl(n);
512 } 521 }
513 Node *dom_lca_for_get_late_ctrl_internal( Node *lca, Node *n, Node *tag ); 522 Node *dom_lca_for_get_late_ctrl_internal( Node *lca, Node *n, Node *tag );
523
514 // true if CFG node d dominates CFG node n 524 // true if CFG node d dominates CFG node n
515 bool is_dominator(Node *d, Node *n); 525 bool is_dominator(Node *d, Node *n);
516 526
517 // Helper function for directing control inputs away from CFG split 527 // Helper function for directing control inputs away from CFG split
518 // points. 528 // points.
619 // Insert loop into the existing loop tree. 'innermost' is a leaf of the 629 // Insert loop into the existing loop tree. 'innermost' is a leaf of the
620 // loop tree, not the root. 630 // loop tree, not the root.
621 IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost ); 631 IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost );
622 632
623 // Place Data nodes in some loop nest 633 // Place Data nodes in some loop nest
624 void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ); 634 void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
625 void build_loop_late ( VectorSet &visited, Node_List &worklist, Node_Stack &nstack, const PhaseIdealLoop *verify_me ); 635 void build_loop_late ( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
626 void build_loop_late_post ( Node* n, const PhaseIdealLoop *verify_me ); 636 void build_loop_late_post ( Node* n );
627 637
628 // Array of immediate dominance info for each CFG node indexed by node idx 638 // Array of immediate dominance info for each CFG node indexed by node idx
629 private: 639 private:
630 uint _idom_size; 640 uint _idom_size;
631 Node **_idom; // Array of immediate dominators 641 Node **_idom; // Array of immediate dominators
660 void recompute_dom_depth(); 670 void recompute_dom_depth();
661 671
662 // Is safept not required by an outer loop? 672 // Is safept not required by an outer loop?
663 bool is_deleteable_safept(Node* sfpt); 673 bool is_deleteable_safept(Node* sfpt);
664 674
675 // Perform verification that the graph is valid.
676 PhaseIdealLoop( PhaseIterGVN &igvn) :
677 PhaseTransform(Ideal_Loop),
678 _igvn(igvn),
679 _dom_lca_tags(C->comp_arena()),
680 _verify_me(NULL),
681 _verify_only(true) {
682 build_and_optimize(false);
683 }
684
685 // build the loop tree and perform any requested optimizations
686 void build_and_optimize(bool do_split_if);
687
665 public: 688 public:
666 // Dominators for the sea of nodes 689 // Dominators for the sea of nodes
667 void Dominators(); 690 void Dominators();
668 Node *dom_lca( Node *n1, Node *n2 ) const { 691 Node *dom_lca( Node *n1, Node *n2 ) const {
669 return find_non_split_ctrl(dom_lca_internal(n1, n2)); 692 return find_non_split_ctrl(dom_lca_internal(n1, n2));
670 } 693 }
671 Node *dom_lca_internal( Node *n1, Node *n2 ) const; 694 Node *dom_lca_internal( Node *n1, Node *n2 ) const;
672 695
673 // Compute the Ideal Node to Loop mapping 696 // Compute the Ideal Node to Loop mapping
674 PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me, bool do_split_ifs ); 697 PhaseIdealLoop( PhaseIterGVN &igvn, bool do_split_ifs) :
698 PhaseTransform(Ideal_Loop),
699 _igvn(igvn),
700 _dom_lca_tags(C->comp_arena()),
701 _verify_me(NULL),
702 _verify_only(false) {
703 build_and_optimize(do_split_ifs);
704 }
705
706 // Verify that verify_me made the same decisions as a fresh run.
707 PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me) :
708 PhaseTransform(Ideal_Loop),
709 _igvn(igvn),
710 _dom_lca_tags(C->comp_arena()),
711 _verify_me(verify_me),
712 _verify_only(false) {
713 build_and_optimize(false);
714 }
715
716 // Build and verify the loop tree without modifying the graph. This
717 // is useful to verify that all inputs properly dominate their uses.
718 static void verify(PhaseIterGVN& igvn) {
719 #ifdef ASSERT
720 PhaseIdealLoop v(igvn);
721 #endif
722 }
675 723
676 // True if the method has at least 1 irreducible loop 724 // True if the method has at least 1 irreducible loop
677 bool _has_irreducible_loops; 725 bool _has_irreducible_loops;
678 726
679 // Per-Node transform 727 // Per-Node transform