< prev index next >

src/hotspot/share/opto/loopnode.hpp

Print this page




 845     // Re-use the side array slot for this node to provide the
 846     // forwarding pointer.
 847     _nodes.map(old_node->_idx, (Node*)((intptr_t)new_node + 1));
 848   }
 849   void lazy_replace(Node *old_node, Node *new_node) {
 850     _igvn.replace_node(old_node, new_node);
 851     lazy_update(old_node, new_node);
 852   }
 853 
 854 private:
 855 
 856   // Place 'n' in some loop nest, where 'n' is a CFG node
 857   void build_loop_tree();
 858   int build_loop_tree_impl( Node *n, int pre_order );
 859   // Insert loop into the existing loop tree.  'innermost' is a leaf of the
 860   // loop tree, not the root.
 861   IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost );
 862 
 863   // Place Data nodes in some loop nest
 864   void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
 865   void build_loop_late ( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
 866   void build_loop_late_post ( Node* n );
 867   void verify_strip_mined_scheduling(Node *n, Node* least);
 868 
 869   // Array of immediate dominance info for each CFG node indexed by node idx
 870 private:
 871   uint _idom_size;
 872   Node **_idom;                  // Array of immediate dominators
 873   uint *_dom_depth;              // Used for fast LCA test
 874   GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
 875 
 876 public:
 877   Node* idom_no_update(Node* d) const {
 878     return idom_no_update(d->_idx);
 879   }
 880 
 881   Node* idom_no_update(uint didx) const {
 882     assert(didx < _idom_size, "oob");
 883     Node* n = _idom[didx];
 884     assert(n != NULL,"Bad immediate dominator info.");
 885     while (n->in(0) == NULL) { // Skip dead CFG nodes
 886       n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);


 906   }
 907   void set_idom(Node* d, Node* n, uint dom_depth);
 908   // Locally compute IDOM using dom_lca call
 909   Node *compute_idom( Node *region ) const;
 910   // Recompute dom_depth
 911   void recompute_dom_depth();
 912 
 913   // Is safept not required by an outer loop?
 914   bool is_deleteable_safept(Node* sfpt);
 915 
 916   // Replace parallel induction variable (parallel to trip counter)
 917   void replace_parallel_iv(IdealLoopTree *loop);
 918 
 919   // Perform verification that the graph is valid.
 920   PhaseIdealLoop( PhaseIterGVN &igvn) :
 921     PhaseTransform(Ideal_Loop),
 922     _igvn(igvn),
 923     _dom_lca_tags(arena()), // Thread::resource_area
 924     _verify_me(NULL),
 925     _verify_only(true) {
 926     build_and_optimize(false, false);
 927   }
 928 
 929   // build the loop tree and perform any requested optimizations
 930   void build_and_optimize(bool do_split_if, bool skip_loop_opts, bool last_round = false);
 931 
 932   // Dominators for the sea of nodes
 933   void Dominators();
 934   Node *dom_lca( Node *n1, Node *n2 ) const {
 935     return find_non_split_ctrl(dom_lca_internal(n1, n2));
 936   }
 937   Node *dom_lca_internal( Node *n1, Node *n2 ) const;
 938 
 939   // Compute the Ideal Node to Loop mapping
 940   PhaseIdealLoop( PhaseIterGVN &igvn, bool do_split_ifs, bool skip_loop_opts = false, bool last_round = false) :
 941     PhaseTransform(Ideal_Loop),
 942     _igvn(igvn),
 943     _dom_lca_tags(arena()), // Thread::resource_area
 944     _verify_me(NULL),
 945     _verify_only(false) {
 946     build_and_optimize(do_split_ifs, skip_loop_opts, last_round);
 947   }
 948 
 949   // Verify that verify_me made the same decisions as a fresh run.
 950   PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me) :
 951     PhaseTransform(Ideal_Loop),
 952     _igvn(igvn),
 953     _dom_lca_tags(arena()), // Thread::resource_area
 954     _verify_me(verify_me),
 955     _verify_only(false) {
 956     build_and_optimize(false, false);
 957   }
 958 
 959   // Build and verify the loop tree without modifying the graph.  This
 960   // is useful to verify that all inputs properly dominate their uses.
 961   static void verify(PhaseIterGVN& igvn) {
 962 #ifdef ASSERT
 963     PhaseIdealLoop v(igvn);
 964 #endif
 965   }
 966 
 967   // True if the method has at least 1 irreducible loop
 968   bool _has_irreducible_loops;
 969 
 970   // Per-Node transform
 971   virtual Node *transform( Node *a_node ) { return 0; }
 972 
 973   bool is_counted_loop(Node* x, IdealLoopTree*& loop);
 974   IdealLoopTree* create_outer_strip_mined_loop(BoolNode *test, Node *cmp, Node *init_control,
 975                                                IdealLoopTree* loop, float cl_prob, float le_fcnt,
 976                                                Node*& entry_control, Node*& iffalse);


1065   void mark_reductions( IdealLoopTree *loop );
1066 
1067   // Return true if exp is a constant times an induction var
1068   bool is_scaled_iv(Node* exp, Node* iv, int* p_scale);
1069 
1070   // Return true if exp is a scaled induction var plus (or minus) constant
1071   bool is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth = 0);
1072 
1073   // Create a new if above the uncommon_trap_if_pattern for the predicate to be promoted
1074   ProjNode* create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
1075                                         Deoptimization::DeoptReason reason,
1076                                         int opcode);
1077   void register_control(Node* n, IdealLoopTree *loop, Node* pred);
1078 
1079   // Clone loop predicates to cloned loops (peeled, unswitched)
1080   static ProjNode* clone_predicate(ProjNode* predicate_proj, Node* new_entry,
1081                                    Deoptimization::DeoptReason reason,
1082                                    PhaseIdealLoop* loop_phase,
1083                                    PhaseIterGVN* igvn);
1084 




1085   static Node* clone_loop_predicates(Node* old_entry, Node* new_entry,
1086                                          bool clone_limit_check,
1087                                          PhaseIdealLoop* loop_phase,
1088                                          PhaseIterGVN* igvn);
1089   Node* clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check);
1090 
1091   static Node* skip_all_loop_predicates(Node* entry);
1092   static Node* skip_loop_predicates(Node* entry);
1093 
1094   // Find a good location to insert a predicate
1095   static ProjNode* find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason);
1096   // Find a predicate
1097   static Node* find_predicate(Node* entry);
1098   // Construct a range check for a predicate if
1099   BoolNode* rc_predicate(IdealLoopTree *loop, Node* ctrl,
1100                          int scale, Node* offset,
1101                          Node* init, Node* limit, jint stride,
1102                          Node* range, bool upper, bool &overflow);
1103 
1104   // Implementation of the loop predication to promote checks outside the loop


1272   bool intrinsify_fill(IdealLoopTree* lpt);
1273   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1274                        Node*& shift, Node*& offset);
1275 
1276 private:
1277   // Return a type based on condition control flow
1278   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1279   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1280  // Helpers for filtered type
1281   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1282 
1283   // Helper functions
1284   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1285   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1286   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 );
1287   bool split_up( Node *n, Node *blk1, Node *blk2 );
1288   void sink_use( Node *use, Node *post_loop );
1289   Node *place_near_use( Node *useblock ) const;
1290   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1291   void try_move_store_after_loop(Node* n);

1292   bool identical_backtoback_ifs(Node *n);
1293   bool can_split_if(Node *n_ctrl);

1294 
1295   bool _created_loop_node;
1296 public:
1297   void set_created_loop_node() { _created_loop_node = true; }
1298   bool created_loop_node()     { return _created_loop_node; }
1299   void register_new_node( Node *n, Node *blk );
1300 
1301 #ifdef ASSERT
1302   void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1303 #endif
1304 
1305 #ifndef PRODUCT
1306   void dump( ) const;
1307   void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;
1308   void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1309   void verify() const;          // Major slow  :-)
1310   void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1311   IdealLoopTree *get_loop_idx(Node* n) const {
1312     // Dead nodes have no loop, so return the top level loop instead
1313     return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1314   }
1315   // Print some stats
1316   static void print_statistics();
1317   static int _loop_invokes;     // Count of PhaseIdealLoop invokes
1318   static int _loop_work;        // Sum of PhaseIdealLoop x _unique
1319 #endif



1320 };
1321 
1322 // This kit may be used for making of a reserved copy of a loop before this loop
1323 //  goes under non-reversible changes.
1324 //
1325 // Function create_reserve() creates a reserved copy (clone) of the loop.
1326 // The reserved copy is created by calling
1327 // PhaseIdealLoop::create_reserve_version_of_loop - see there how
1328 // the original and reserved loops are connected in the outer graph.
1329 // If create_reserve succeeded, it returns 'true' and _has_reserved is set to 'true'.
1330 //
1331 // By default the reserved copy (clone) of the loop is created as dead code - it is
1332 // dominated in the outer loop by this node chain:
1333 //   intcon(1)->If->IfFalse->reserved_copy.
1334 // The original loop is dominated by the the same node chain but IfTrue projection:
1335 //   intcon(0)->If->IfTrue->original_loop.
1336 //
1337 // In this implementation of CountedLoopReserveKit the ctor includes create_reserve()
1338 // and the dtor, checks _use_new value.
1339 // If _use_new == false, it "switches" control to reserved copy of the loop




 845     // Re-use the side array slot for this node to provide the
 846     // forwarding pointer.
 847     _nodes.map(old_node->_idx, (Node*)((intptr_t)new_node + 1));
 848   }
 849   void lazy_replace(Node *old_node, Node *new_node) {
 850     _igvn.replace_node(old_node, new_node);
 851     lazy_update(old_node, new_node);
 852   }
 853 
 854 private:
 855 
 856   // Place 'n' in some loop nest, where 'n' is a CFG node
 857   void build_loop_tree();
 858   int build_loop_tree_impl( Node *n, int pre_order );
 859   // Insert loop into the existing loop tree.  'innermost' is a leaf of the
 860   // loop tree, not the root.
 861   IdealLoopTree *sort( IdealLoopTree *loop, IdealLoopTree *innermost );
 862 
 863   // Place Data nodes in some loop nest
 864   void build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack );
 865   void build_loop_late(VectorSet &visited, Node_List &worklist, Node_Stack &nstack, bool verify_strip_mined);
 866   void build_loop_late_post(Node* n, bool verify_strip_mined);
 867   void verify_strip_mined_scheduling(Node *n, Node* least);
 868 
 869   // Array of immediate dominance info for each CFG node indexed by node idx
 870 private:
 871   uint _idom_size;
 872   Node **_idom;                  // Array of immediate dominators
 873   uint *_dom_depth;              // Used for fast LCA test
 874   GrowableArray<uint>* _dom_stk; // For recomputation of dom depth
 875 
 876 public:
 877   Node* idom_no_update(Node* d) const {
 878     return idom_no_update(d->_idx);
 879   }
 880 
 881   Node* idom_no_update(uint didx) const {
 882     assert(didx < _idom_size, "oob");
 883     Node* n = _idom[didx];
 884     assert(n != NULL,"Bad immediate dominator info.");
 885     while (n->in(0) == NULL) { // Skip dead CFG nodes
 886       n = (Node*)(((intptr_t)_nodes[n->_idx]) & ~1);


 906   }
 907   void set_idom(Node* d, Node* n, uint dom_depth);
 908   // Locally compute IDOM using dom_lca call
 909   Node *compute_idom( Node *region ) const;
 910   // Recompute dom_depth
 911   void recompute_dom_depth();
 912 
 913   // Is safept not required by an outer loop?
 914   bool is_deleteable_safept(Node* sfpt);
 915 
 916   // Replace parallel induction variable (parallel to trip counter)
 917   void replace_parallel_iv(IdealLoopTree *loop);
 918 
 919   // Perform verification that the graph is valid.
 920   PhaseIdealLoop( PhaseIterGVN &igvn) :
 921     PhaseTransform(Ideal_Loop),
 922     _igvn(igvn),
 923     _dom_lca_tags(arena()), // Thread::resource_area
 924     _verify_me(NULL),
 925     _verify_only(true) {
 926     build_and_optimize(LoopOptsVerify);
 927   }
 928 
 929   // build the loop tree and perform any requested optimizations
 930   void build_and_optimize(LoopOptsMode mode);
 931 
 932   // Dominators for the sea of nodes
 933   void Dominators();
 934   Node *dom_lca( Node *n1, Node *n2 ) const {
 935     return find_non_split_ctrl(dom_lca_internal(n1, n2));
 936   }
 937   Node *dom_lca_internal( Node *n1, Node *n2 ) const;
 938 
 939   // Compute the Ideal Node to Loop mapping
 940   PhaseIdealLoop( PhaseIterGVN &igvn, LoopOptsMode mode) :
 941     PhaseTransform(Ideal_Loop),
 942     _igvn(igvn),
 943     _dom_lca_tags(arena()), // Thread::resource_area
 944     _verify_me(NULL),
 945     _verify_only(false) {
 946       build_and_optimize(mode);
 947   }
 948 
 949   // Verify that verify_me made the same decisions as a fresh run.
 950   PhaseIdealLoop( PhaseIterGVN &igvn, const PhaseIdealLoop *verify_me) :
 951     PhaseTransform(Ideal_Loop),
 952     _igvn(igvn),
 953     _dom_lca_tags(arena()), // Thread::resource_area
 954     _verify_me(verify_me),
 955     _verify_only(false) {
 956     build_and_optimize(LoopOptsVerify);
 957   }
 958 
 959   // Build and verify the loop tree without modifying the graph.  This
 960   // is useful to verify that all inputs properly dominate their uses.
 961   static void verify(PhaseIterGVN& igvn) {
 962 #ifdef ASSERT
 963     PhaseIdealLoop v(igvn);
 964 #endif
 965   }
 966 
 967   // True if the method has at least 1 irreducible loop
 968   bool _has_irreducible_loops;
 969 
 970   // Per-Node transform
 971   virtual Node *transform( Node *a_node ) { return 0; }
 972 
 973   bool is_counted_loop(Node* x, IdealLoopTree*& loop);
 974   IdealLoopTree* create_outer_strip_mined_loop(BoolNode *test, Node *cmp, Node *init_control,
 975                                                IdealLoopTree* loop, float cl_prob, float le_fcnt,
 976                                                Node*& entry_control, Node*& iffalse);


1065   void mark_reductions( IdealLoopTree *loop );
1066 
1067   // Return true if exp is a constant times an induction var
1068   bool is_scaled_iv(Node* exp, Node* iv, int* p_scale);
1069 
1070   // Return true if exp is a scaled induction var plus (or minus) constant
1071   bool is_scaled_iv_plus_offset(Node* exp, Node* iv, int* p_scale, Node** p_offset, int depth = 0);
1072 
1073   // Create a new if above the uncommon_trap_if_pattern for the predicate to be promoted
1074   ProjNode* create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry,
1075                                         Deoptimization::DeoptReason reason,
1076                                         int opcode);
1077   void register_control(Node* n, IdealLoopTree *loop, Node* pred);
1078 
1079   // Clone loop predicates to cloned loops (peeled, unswitched)
1080   static ProjNode* clone_predicate(ProjNode* predicate_proj, Node* new_entry,
1081                                    Deoptimization::DeoptReason reason,
1082                                    PhaseIdealLoop* loop_phase,
1083                                    PhaseIterGVN* igvn);
1084 
1085   static void clone_loop_predicates_fix_mem(ProjNode* dom_proj , ProjNode* proj,
1086                                             PhaseIdealLoop* loop_phase,
1087                                             PhaseIterGVN* igvn );
1088 
1089   static Node* clone_loop_predicates(Node* old_entry, Node* new_entry,
1090                                          bool clone_limit_check,
1091                                          PhaseIdealLoop* loop_phase,
1092                                          PhaseIterGVN* igvn);
1093   Node* clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check);
1094 
1095   static Node* skip_all_loop_predicates(Node* entry);
1096   static Node* skip_loop_predicates(Node* entry);
1097 
1098   // Find a good location to insert a predicate
1099   static ProjNode* find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason);
1100   // Find a predicate
1101   static Node* find_predicate(Node* entry);
1102   // Construct a range check for a predicate if
1103   BoolNode* rc_predicate(IdealLoopTree *loop, Node* ctrl,
1104                          int scale, Node* offset,
1105                          Node* init, Node* limit, jint stride,
1106                          Node* range, bool upper, bool &overflow);
1107 
1108   // Implementation of the loop predication to promote checks outside the loop


1276   bool intrinsify_fill(IdealLoopTree* lpt);
1277   bool match_fill_loop(IdealLoopTree* lpt, Node*& store, Node*& store_value,
1278                        Node*& shift, Node*& offset);
1279 
1280 private:
1281   // Return a type based on condition control flow
1282   const TypeInt* filtered_type( Node *n, Node* n_ctrl);
1283   const TypeInt* filtered_type( Node *n ) { return filtered_type(n, NULL); }
1284  // Helpers for filtered type
1285   const TypeInt* filtered_type_from_dominators( Node* val, Node *val_ctrl);
1286 
1287   // Helper functions
1288   Node *spinup( Node *iff, Node *new_false, Node *new_true, Node *region, Node *phi, small_cache *cache );
1289   Node *find_use_block( Node *use, Node *def, Node *old_false, Node *new_false, Node *old_true, Node *new_true );
1290   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 );
1291   bool split_up( Node *n, Node *blk1, Node *blk2 );
1292   void sink_use( Node *use, Node *post_loop );
1293   Node *place_near_use( Node *useblock ) const;
1294   Node* try_move_store_before_loop(Node* n, Node *n_ctrl);
1295   void try_move_store_after_loop(Node* n);
1296 public:
1297   bool identical_backtoback_ifs(Node *n);
1298   bool can_split_if(Node *n_ctrl);
1299 private:
1300 
1301   bool _created_loop_node;
1302 public:
1303   void set_created_loop_node() { _created_loop_node = true; }
1304   bool created_loop_node()     { return _created_loop_node; }
1305   void register_new_node( Node *n, Node *blk );
1306 
1307 #ifdef ASSERT
1308   void dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA);
1309 #endif
1310 
1311 #ifndef PRODUCT
1312   void dump( ) const;
1313   void dump( IdealLoopTree *loop, uint rpo_idx, Node_List &rpo_list ) const;

1314   void verify() const;          // Major slow  :-)
1315   void verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const;
1316   IdealLoopTree *get_loop_idx(Node* n) const {
1317     // Dead nodes have no loop, so return the top level loop instead
1318     return _nodes[n->_idx] ? (IdealLoopTree*)_nodes[n->_idx] : _ltree_root;
1319   }
1320   // Print some stats
1321   static void print_statistics();
1322   static int _loop_invokes;     // Count of PhaseIdealLoop invokes
1323   static int _loop_work;        // Sum of PhaseIdealLoop x _unique
1324 #endif
1325   void rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const;
1326 
1327   PhaseIterGVN& igvn() { return _igvn; }
1328 };
1329 
1330 // This kit may be used for making of a reserved copy of a loop before this loop
1331 //  goes under non-reversible changes.
1332 //
1333 // Function create_reserve() creates a reserved copy (clone) of the loop.
1334 // The reserved copy is created by calling
1335 // PhaseIdealLoop::create_reserve_version_of_loop - see there how
1336 // the original and reserved loops are connected in the outer graph.
1337 // If create_reserve succeeded, it returns 'true' and _has_reserved is set to 'true'.
1338 //
1339 // By default the reserved copy (clone) of the loop is created as dead code - it is
1340 // dominated in the outer loop by this node chain:
1341 //   intcon(1)->If->IfFalse->reserved_copy.
1342 // The original loop is dominated by the the same node chain but IfTrue projection:
1343 //   intcon(0)->If->IfTrue->original_loop.
1344 //
1345 // In this implementation of CountedLoopReserveKit the ctor includes create_reserve()
1346 // and the dtor, checks _use_new value.
1347 // If _use_new == false, it "switches" control to reserved copy of the loop


< prev index next >