< prev index next >

src/share/vm/opto/loopnode.hpp

Print this page




 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


 730   void build_loop_late_post ( Node* n );
 731 
 732   // Array of immediate dominance info for each CFG node indexed by node idx
 733 private:
 734   uint _idom_size;
 735   Node **_idom;                 // Array of immediate dominators
 736   uint *_dom_depth;           // Used for fast LCA test
 737   GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
 738 
 739   Node* idom_no_update(Node* d) const {
 740     assert(d->_idx < _idom_size, "oob");
 741     Node* n = _idom[d->_idx];
 742     assert(n != NULL,"Bad immediate dominator info.");
 743     while (n->in(0) == NULL) {  // Skip dead CFG nodes
 744       //n = n->in(1);
 745       n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
 746       assert(n != NULL,"Bad immediate dominator info.");
 747     }
 748     return n;
 749   }

 750   Node *idom(Node* d) const {
 751     uint didx = d->_idx;
 752     Node *n = idom_no_update(d);
 753     _idom[didx] = n;            // Lazily remove dead CFG nodes from table.
 754     return n;
 755   }
 756   uint dom_depth(Node* d) const {
 757     guarantee(d != NULL, "Null dominator info.");
 758     guarantee(d->_idx < _idom_size, "");
 759     return _dom_depth[d->_idx];
 760   }
 761   void set_idom(Node* d, Node* n, uint dom_depth);


 762   // Locally compute IDOM using dom_lca call
 763   Node *compute_idom( Node *region ) const;
 764   // Recompute dom_depth
 765   void recompute_dom_depth();
 766 
 767   // Is safept not required by an outer loop?
 768   bool is_deleteable_safept(Node* sfpt);
 769 
 770   // Replace parallel induction variable (parallel to trip counter)
 771   void replace_parallel_iv(IdealLoopTree *loop);
 772 
 773   // Perform verification that the graph is valid.
 774   PhaseIdealLoop( PhaseIterGVN &igvn) :
 775     PhaseTransform(Ideal_Loop),
 776     _igvn(igvn),
 777     _dom_lca_tags(arena()), // Thread::resource_area
 778     _verify_me(NULL),
 779     _verify_only(true) {
 780     build_and_optimize(false, false);
 781   }


1025   // Reorganize offset computations to lower register pressure.
1026   // Mostly prevent loop-fallout uses of the pre-incremented trip counter
1027   // (which are then alive with the post-incremented trip counter
1028   // forcing an extra register move)
1029   void reorg_offsets( IdealLoopTree *loop );
1030 
1031   // Check for aggressive application of 'split-if' optimization,
1032   // using basic block level info.
1033   void  split_if_with_blocks     ( VectorSet &visited, Node_Stack &nstack );
1034   Node *split_if_with_blocks_pre ( Node *n );
1035   void  split_if_with_blocks_post( Node *n );
1036   Node *has_local_phi_input( Node *n );
1037   // Mark an IfNode as being dominated by a prior test,
1038   // without actually altering the CFG (and hence IDOM info).
1039   void dominated_by( Node *prevdom, Node *iff, bool flip = false, bool exclude_loop_predicate = false );
1040 
1041   // Split Node 'n' through merge point
1042   Node *split_thru_region( Node *n, Node *region );
1043   // Split Node 'n' through merge point if there is enough win.
1044   Node *split_thru_phi( Node *n, Node *region, int policy );

1045   // Found an If getting its condition-code input from a Phi in the
1046   // same block.  Split thru the Region.
1047   void do_split_if( Node *iff );
1048 
1049   // Conversion of fill/copy patterns into intrisic versions
1050   bool do_intrinsify_fill();
1051   bool intrinsify_fill(IdealLoopTree* lpt);
1052   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1053                        Node*& shift, Node*& offset);
1054 
1055 private:
1056   // Return a type based on condition control flow
1057   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1058   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1059  // Helpers for filtered type
1060   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1061 
1062   // Helper functions
1063   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1064   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1065   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 );
1066   bool split_up( Node *n, Node *blk1, Node *blk2 );
1067   void sink_use( Node *use, Node *post_loop );
1068   Node *place_near_use( Node *useblock ) const;
1069 
1070   bool _created_loop_node;
1071 public:
1072   void set_created_loop_node() { _created_loop_node = true; }
1073   bool created_loop_node()     { return _created_loop_node; }
1074   void register_new_node( Node *n, Node *blk );
1075 
1076 #ifdef ASSERT
1077   void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1078 #endif

1079 
1080 #ifndef PRODUCT
1081   void dump( ) const;
1082   void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1083   void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1084   void verify() const;          // Major slow  :-)
1085   void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1086   IdealLoopTree *get_loop_idx(Node* n) const {
1087     // Dead nodes have no loop, so return the top level loop instead
1088     return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1089   }
1090   // Print some stats
1091   static void print_statistics();
1092   static int _loop_invokes;     // Count of PhaseIdealLoop invokes
1093   static int _loop_work;        // Sum of PhaseIdealLoop x _unique
1094 #endif



1095 };
1096 
1097 inline Node* IdealLoopTree::tail() {
1098 // Handle lazy update of _tail field
1099   Node *n = _tail;
1100   //while( !n->in(0) )  // Skip dead CFG nodes
1101     //n = n->in(1);
1102   if (n->in(0) == NULL)
1103     n = _phase->get_ctrl(n);
1104   _tail = n;
1105   return n;
1106 }
1107 
1108 
1109 // Iterate over the loop tree using a preorder, left-to-right traversal.
1110 //
1111 // Example that visits all counted loops from within PhaseIdealLoop
1112 //
1113 //  for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1114 //   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


 732   void build_loop_late_post ( Node* n );
 733 
 734   // Array of immediate dominance info for each CFG node indexed by node idx
 735 private:
 736   uint _idom_size;
 737   Node **_idom;                 // Array of immediate dominators
 738   uint *_dom_depth;           // Used for fast LCA test
 739   GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
 740 
 741   Node* idom_no_update(Node* d) const {
 742     assert(d->_idx < _idom_size, "oob");
 743     Node* n = _idom[d->_idx];
 744     assert(n != NULL,"Bad immediate dominator info.");
 745     while (n->in(0) == NULL) {  // Skip dead CFG nodes
 746       //n = n->in(1);
 747       n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);
 748       assert(n != NULL,"Bad immediate dominator info.");
 749     }
 750     return n;
 751   }
 752 public:
 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 
 766 private:
 767   // Locally compute IDOM using dom_lca call
 768   Node *compute_idom( Node *region ) const;
 769   // Recompute dom_depth
 770   void recompute_dom_depth();
 771 
 772   // Is safept not required by an outer loop?
 773   bool is_deleteable_safept(Node* sfpt);
 774 
 775   // Replace parallel induction variable (parallel to trip counter)
 776   void replace_parallel_iv(IdealLoopTree *loop);
 777 
 778   // Perform verification that the graph is valid.
 779   PhaseIdealLoop( PhaseIterGVN &igvn) :
 780     PhaseTransform(Ideal_Loop),
 781     _igvn(igvn),
 782     _dom_lca_tags(arena()), // Thread::resource_area
 783     _verify_me(NULL),
 784     _verify_only(true) {
 785     build_and_optimize(false, false);
 786   }


1030   // Reorganize offset computations to lower register pressure.
1031   // Mostly prevent loop-fallout uses of the pre-incremented trip counter
1032   // (which are then alive with the post-incremented trip counter
1033   // forcing an extra register move)
1034   void reorg_offsets( IdealLoopTree *loop );
1035 
1036   // Check for aggressive application of 'split-if' optimization,
1037   // using basic block level info.
1038   void  split_if_with_blocks     ( VectorSet &visited, Node_Stack &nstack );
1039   Node *split_if_with_blocks_pre ( Node *n );
1040   void  split_if_with_blocks_post( Node *n );
1041   Node *has_local_phi_input( Node *n );
1042   // Mark an IfNode as being dominated by a prior test,
1043   // without actually altering the CFG (and hence IDOM info).
1044   void dominated_by( Node *prevdom, Node *iff, bool flip = false, bool exclude_loop_predicate = false );
1045 
1046   // Split Node 'n' through merge point
1047   Node *split_thru_region( Node *n, Node *region );
1048   // Split Node 'n' through merge point if there is enough win.
1049   Node *split_thru_phi( Node *n, Node *region, int policy );
1050 
1051   // Found an If getting its condition-code input from a Phi in the
1052   // same block.  Split thru the Region.
1053   void do_split_if( Node *iff );
1054 
1055   // Conversion of fill/copy patterns into intrisic versions
1056   bool do_intrinsify_fill();
1057   bool intrinsify_fill(IdealLoopTree* lpt);
1058   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1059                        Node*& shift, Node*& offset);
1060 
1061 private:
1062   // Return a type based on condition control flow
1063   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1064   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1065  // Helpers for filtered type
1066   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1067 
1068   // Helper functions
1069   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1070   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1071   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 );
1072   bool split_up( Node *n, Node *blk1, Node *blk2 );
1073   void sink_use( Node *use, Node *post_loop );
1074   Node *place_near_use( Node *useblock ) const;
1075 
1076   bool _created_loop_node;
1077 public:
1078   void set_created_loop_node() { _created_loop_node = true; }
1079   bool created_loop_node()     { return _created_loop_node; }
1080   void register_new_node( Node *n, Node *blk );
1081 
1082 #ifdef ASSERT
1083   void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1084 #endif
1085   void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1086 
1087 #ifndef PRODUCT
1088   void dump( ) const;
1089   void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;

1090   void verify() const;          // Major slow  :-)
1091   void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1092   IdealLoopTree *get_loop_idx(Node* n) const {
1093     // Dead nodes have no loop, so return the top level loop instead
1094     return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1095   }
1096   // Print some stats
1097   static void print_statistics();
1098   static int _loop_invokes;     // Count of PhaseIdealLoop invokes
1099   static int _loop_work;        // Sum of PhaseIdealLoop x _unique
1100 #endif
1101 
1102   PhaseIterGVN& igvn() { return _igvn; }
1103   IdealLoopTree* ltree_root() const { return _ltree_root; }
1104 };
1105 
1106 inline Node* IdealLoopTree::tail() {
1107 // Handle lazy update of _tail field
1108   Node *n = _tail;
1109   //while( !n->in(0) )  // Skip dead CFG nodes
1110     //n = n->in(1);
1111   if (n->in(0) == NULL)
1112     n = _phase->get_ctrl(n);
1113   _tail = n;
1114   return n;
1115 }
1116 
1117 
1118 // Iterate over the loop tree using a preorder, left-to-right traversal.
1119 //
1120 // Example that visits all counted loops from within PhaseIdealLoop
1121 //
1122 //  for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
1123 //   IdealLoopTree* lpt = iter.current();
< prev index next >