554 _max_preorder = newsize;
555 }
556 }
557 // Check for pre-visited. Zero for NOT visited; non-zero for visited.
558 int is_visited( Node *n ) const { return _preorders[n->_idx]; }
559 // Pre-order numbers are written to the Nodes array as low-bit-set values.
560 void set_preorder_visited( Node *n, int pre_order ) {
561 assert( !is_visited( n ), "already set" );
562 _preorders[n->_idx] = (pre_order<<1);
563 };
564 // Return pre-order number.
565 int get_preorder( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]>>1; }
566
567 // Check for being post-visited.
568 // Should be previsited already (checked with assert(is_visited(n))).
569 int is_postvisited( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]&1; }
570
571 // Mark as post visited
572 void set_postvisited( Node *n ) { assert( !is_postvisited( n ), "" ); _preorders[n->_idx] |= 1; }
573
574 // Set/get control node out. Set lower bit to distinguish from IdealLoopTree
575 // Returns true if "n" is a data node, false if it's a control node.
576 bool has_ctrl( Node *n ) const { return ((intptr_t)_nodes[n->_idx]) & 1; }
577
578 // clear out dead code after build_loop_late
579 Node_List _deadlist;
580
581 // Support for faster execution of get_late_ctrl()/dom_lca()
582 // when a node has many uses and dominator depth is deep.
583 Node_Array _dom_lca_tags;
584 void init_dom_lca_tags();
585 void clear_dom_lca_tags();
586
587 // Helper for debugging bad dominance relationships
588 bool verify_dominance(Node* n, Node* use, Node* LCA, Node* early);
589
590 Node* compute_lca_of_uses(Node* n, Node* early, bool verify = false);
591
592 // Inline wrapper for frequent cases:
593 // 1) only one use
594 // 2) a use is the same as the current LCA passed as 'n1'
595 Node *dom_lca_for_get_late_ctrl( Node *lca, Node *n, Node *tag ) {
596 assert( n->is_CFG(), "" );
597 // Fast-path NULL lca
733 void build_loop_late_post ( Node* n );
734
735 // Array of immediate dominance info for each CFG node indexed by node idx
736 private:
737 uint _idom_size;
738 Node **_idom; // Array of immediate dominators
739 uint *_dom_depth; // Used for fast LCA test
740 GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
741
742 Node* idom_no_update(Node* d) const {
743 assert(d->_idx < _idom_size, "oob");
744 Node* n = _idom[d->_idx];
745 assert(n != NULL,"Bad immediate dominator info.");
746 while (n->in(0) == NULL) { // Skip dead CFG nodes
747 //n = n->in(1);
748 n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
749 assert(n != NULL,"Bad immediate dominator info.");
750 }
751 return n;
752 }
753 Node *idom(Node* d) const {
754 uint didx = d->_idx;
755 Node *n = idom_no_update(d);
756 _idom[didx] = n; // Lazily remove dead CFG nodes from table.
757 return n;
758 }
759 uint dom_depth(Node* d) const {
760 guarantee(d != NULL, "Null dominator info.");
761 guarantee(d->_idx < _idom_size, "");
762 return _dom_depth[d->_idx];
763 }
764 void set_idom(Node* d, Node* n, uint dom_depth);
765 // Locally compute IDOM using dom_lca call
766 Node *compute_idom( Node *region ) const;
767 // Recompute dom_depth
768 void recompute_dom_depth();
769
770 // Is safept not required by an outer loop?
771 bool is_deleteable_safept(Node* sfpt);
772
773 // Replace parallel induction variable (parallel to trip counter)
774 void replace_parallel_iv(IdealLoopTree *loop);
775
776 // Perform verification that the graph is valid.
777 PhaseIdealLoop( PhaseIterGVN &igvn) :
778 PhaseTransform(Ideal_Loop),
779 _igvn(igvn),
780 _dom_lca_tags(arena()), // Thread::resource_area
781 _verify_me(NULL),
782 _verify_only(true) {
783 build_and_optimize(false, false);
784 }
1028 // Reorganize offset computations to lower register pressure.
1029 // Mostly prevent loop-fallout uses of the pre-incremented trip counter
1030 // (which are then alive with the post-incremented trip counter
1031 // forcing an extra register move)
1032 void reorg_offsets( IdealLoopTree *loop );
1033
1034 // Check for aggressive application of 'split-if' optimization,
1035 // using basic block level info.
1036 void split_if_with_blocks ( VectorSet &visited, Node_Stack &nstack );
1037 Node *split_if_with_blocks_pre ( Node *n );
1038 void split_if_with_blocks_post( Node *n );
1039 Node *has_local_phi_input( Node *n );
1040 // Mark an IfNode as being dominated by a prior test,
1041 // without actually altering the CFG (and hence IDOM info).
1042 void dominated_by( Node *prevdom, Node *iff, bool flip = false, bool exclude_loop_predicate = false );
1043
1044 // Split Node 'n' through merge point
1045 Node *split_thru_region( Node *n, Node *region );
1046 // Split Node 'n' through merge point if there is enough win.
1047 Node *split_thru_phi( Node *n, Node *region, int policy );
1048 // Found an If getting its condition-code input from a Phi in the
1049 // same block. Split thru the Region.
1050 void do_split_if( Node *iff );
1051
1052 // Conversion of fill/copy patterns into intrisic versions
1053 bool do_intrinsify_fill();
1054 bool intrinsify_fill(IdealLoopTree* lpt);
1055 bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1056 Node*& shift, Node*& offset);
1057
1058 private:
1059 // Return a type based on condition control flow
1060 const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1061 const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1062 // Helpers for filtered type
1063 const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1064
1065 // Helper functions
1066 Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1067 Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1068 void handle_use( Node *use, Node *def, small_cache *cache, Node *region_dom, Node *new_false, Node *new_true, Node *old_false, Node *old_true );
1069 bool split_up( Node *n, Node *blk1, Node *blk2 );
1070 void sink_use( Node *use, Node *post_loop );
1071 Node *place_near_use( Node *useblock ) const;
1072
1073 bool _created_loop_node;
1074 public:
1075 void set_created_loop_node() { _created_loop_node = true; }
1076 bool created_loop_node() { return _created_loop_node; }
1077 void register_new_node( Node *n, Node *blk );
1078
1079 #ifdef ASSERT
1080 void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1081 #endif
1082
1083 #ifndef PRODUCT
1084 void dump( ) const;
1085 void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1086 void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1087 void verify() const; // Major slow :-)
1088 void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1089 IdealLoopTree *get_loop_idx(Node* n) const {
1090 // Dead nodes have no loop, so return the top level loop instead
1091 return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1092 }
1093 // Print some stats
1094 static void print_statistics();
1095 static int _loop_invokes; // Count of PhaseIdealLoop invokes
1096 static int _loop_work; // Sum of PhaseIdealLoop x _unique
1097 #endif
1098 };
1099
1100 inline Node* IdealLoopTree::tail() {
1101 // Handle lazy update of _tail field
1102 Node *n = _tail;
1103 //while( !n->in(0) ) // Skip dead CFG nodes
1104 //n = n->in(1);
1105 if (n->in(0) == NULL)
1106 n = _phase->get_ctrl(n);
1107 _tail = n;
1108 return n;
1109 }
1110
1111
1112 // Iterate over the loop tree using a preorder, left-to-right traversal.
1113 //
1114 // Example that visits all counted loops from within PhaseIdealLoop
1115 //
1116 // for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1117 // IdealLoopTree* lpt = iter.current();
|
554 _max_preorder = newsize;
555 }
556 }
557 // Check for pre-visited. Zero for NOT visited; non-zero for visited.
558 int is_visited( Node *n ) const { return _preorders[n->_idx]; }
559 // Pre-order numbers are written to the Nodes array as low-bit-set values.
560 void set_preorder_visited( Node *n, int pre_order ) {
561 assert( !is_visited( n ), "already set" );
562 _preorders[n->_idx] = (pre_order<<1);
563 };
564 // Return pre-order number.
565 int get_preorder( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]>>1; }
566
567 // Check for being post-visited.
568 // Should be previsited already (checked with assert(is_visited(n))).
569 int is_postvisited( Node *n ) const { assert( is_visited(n), "" ); return _preorders[n->_idx]&1; }
570
571 // Mark as post visited
572 void set_postvisited( Node *n ) { assert( !is_postvisited( n ), "" ); _preorders[n->_idx] |= 1; }
573
574 public:
575 // Set/get control node out. Set lower bit to distinguish from IdealLoopTree
576 // Returns true if "n" is a data node, false if it's a control node.
577 bool has_ctrl( Node *n ) const { return ((intptr_t)_nodes[n->_idx]) & 1; }
578
579 private:
580 // clear out dead code after build_loop_late
581 Node_List _deadlist;
582
583 // Support for faster execution of get_late_ctrl()/dom_lca()
584 // when a node has many uses and dominator depth is deep.
585 Node_Array _dom_lca_tags;
586 void init_dom_lca_tags();
587 void clear_dom_lca_tags();
588
589 // Helper for debugging bad dominance relationships
590 bool verify_dominance(Node* n, Node* use, Node* LCA, Node* early);
591
592 Node* compute_lca_of_uses(Node* n, Node* early, bool verify = false);
593
594 // Inline wrapper for frequent cases:
595 // 1) only one use
596 // 2) a use is the same as the current LCA passed as 'n1'
597 Node *dom_lca_for_get_late_ctrl( Node *lca, Node *n, Node *tag ) {
598 assert( n->is_CFG(), "" );
599 // Fast-path NULL lca
735 void build_loop_late_post ( Node* n );
736
737 // Array of immediate dominance info for each CFG node indexed by node idx
738 private:
739 uint _idom_size;
740 Node **_idom; // Array of immediate dominators
741 uint *_dom_depth; // Used for fast LCA test
742 GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
743
744 Node* idom_no_update(Node* d) const {
745 assert(d->_idx < _idom_size, "oob");
746 Node* n = _idom[d->_idx];
747 assert(n != NULL,"Bad immediate dominator info.");
748 while (n->in(0) == NULL) { // Skip dead CFG nodes
749 //n = n->in(1);
750 n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
751 assert(n != NULL,"Bad immediate dominator info.");
752 }
753 return n;
754 }
755 public:
756 Node *idom(Node* d) const {
757 uint didx = d->_idx;
758 Node *n = idom_no_update(d);
759 _idom[didx] = n; // Lazily remove dead CFG nodes from table.
760 return n;
761 }
762 uint dom_depth(Node* d) const {
763 guarantee(d != NULL, "Null dominator info.");
764 guarantee(d->_idx < _idom_size, "");
765 return _dom_depth[d->_idx];
766 }
767 void set_idom(Node* d, Node* n, uint dom_depth);
768
769 private:
770 // Locally compute IDOM using dom_lca call
771 Node *compute_idom( Node *region ) const;
772 // Recompute dom_depth
773 void recompute_dom_depth();
774
775 // Is safept not required by an outer loop?
776 bool is_deleteable_safept(Node* sfpt);
777
778 // Replace parallel induction variable (parallel to trip counter)
779 void replace_parallel_iv(IdealLoopTree *loop);
780
781 // Perform verification that the graph is valid.
782 PhaseIdealLoop( PhaseIterGVN &igvn) :
783 PhaseTransform(Ideal_Loop),
784 _igvn(igvn),
785 _dom_lca_tags(arena()), // Thread::resource_area
786 _verify_me(NULL),
787 _verify_only(true) {
788 build_and_optimize(false, false);
789 }
1033 // Reorganize offset computations to lower register pressure.
1034 // Mostly prevent loop-fallout uses of the pre-incremented trip counter
1035 // (which are then alive with the post-incremented trip counter
1036 // forcing an extra register move)
1037 void reorg_offsets( IdealLoopTree *loop );
1038
1039 // Check for aggressive application of 'split-if' optimization,
1040 // using basic block level info.
1041 void split_if_with_blocks ( VectorSet &visited, Node_Stack &nstack );
1042 Node *split_if_with_blocks_pre ( Node *n );
1043 void split_if_with_blocks_post( Node *n );
1044 Node *has_local_phi_input( Node *n );
1045 // Mark an IfNode as being dominated by a prior test,
1046 // without actually altering the CFG (and hence IDOM info).
1047 void dominated_by( Node *prevdom, Node *iff, bool flip = false, bool exclude_loop_predicate = false );
1048
1049 // Split Node 'n' through merge point
1050 Node *split_thru_region( Node *n, Node *region );
1051 // Split Node 'n' through merge point if there is enough win.
1052 Node *split_thru_phi( Node *n, Node *region, int policy );
1053
1054 // Found an If getting its condition-code input from a Phi in the
1055 // same block. Split thru the Region.
1056 void do_split_if( Node *iff );
1057
1058 // Conversion of fill/copy patterns into intrisic versions
1059 bool do_intrinsify_fill();
1060 bool intrinsify_fill(IdealLoopTree* lpt);
1061 bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1062 Node*& shift, Node*& offset);
1063
1064 private:
1065 // Return a type based on condition control flow
1066 const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1067 const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1068 // Helpers for filtered type
1069 const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1070
1071 // Helper functions
1072 Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1073 Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1074 void handle_use( Node *use, Node *def, small_cache *cache, Node *region_dom, Node *new_false, Node *new_true, Node *old_false, Node *old_true );
1075 bool split_up( Node *n, Node *blk1, Node *blk2 );
1076 void sink_use( Node *use, Node *post_loop );
1077 Node *place_near_use( Node *useblock ) const;
1078
1079 bool _created_loop_node;
1080 public:
1081 void set_created_loop_node() { _created_loop_node = true; }
1082 bool created_loop_node() { return _created_loop_node; }
1083 void register_new_node( Node *n, Node *blk );
1084
1085 #ifdef ASSERT
1086 void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1087 #endif
1088 void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1089
1090 #ifndef PRODUCT
1091 void dump( ) const;
1092 void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1093 void verify() const; // Major slow :-)
1094 void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1095 IdealLoopTree *get_loop_idx(Node* n) const {
1096 // Dead nodes have no loop, so return the top level loop instead
1097 return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1098 }
1099 // Print some stats
1100 static void print_statistics();
1101 static int _loop_invokes; // Count of PhaseIdealLoop invokes
1102 static int _loop_work; // Sum of PhaseIdealLoop x _unique
1103 #endif
1104
1105 PhaseIterGVN& igvn() { return _igvn; }
1106 IdealLoopTree* ltree_root() const { return _ltree_root; }
1107 };
1108
1109 inline Node* IdealLoopTree::tail() {
1110 // Handle lazy update of _tail field
1111 Node *n = _tail;
1112 //while( !n->in(0) ) // Skip dead CFG nodes
1113 //n = n->in(1);
1114 if (n->in(0) == NULL)
1115 n = _phase->get_ctrl(n);
1116 _tail = n;
1117 return n;
1118 }
1119
1120
1121 // Iterate over the loop tree using a preorder, left-to-right traversal.
1122 //
1123 // Example that visits all counted loops from within PhaseIdealLoop
1124 //
1125 // for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1126 // IdealLoopTree* lpt = iter.current();
|