< prev index next >

src/hotspot/share/opto/loopnode.cpp

Print this page


   1 /*
   2  * Copyright (c) 1998, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   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
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


2422     // Remove safepoints
2423     bool keep_one_sfpt = !(_has_call || _has_sfpt);
2424     remove_safepoints(phase, keep_one_sfpt);
2425 
2426     // Look for induction variables
2427     phase->replace_parallel_iv(this);
2428 
2429   } else if (_parent != NULL && !_irreducible) {
2430     // Not a counted loop. Keep one safepoint.
2431     bool keep_one_sfpt = true;
2432     remove_safepoints(phase, keep_one_sfpt);
2433   }
2434 
2435   // Recursively
2436   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2437   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2438   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2439   if (loop->_next)  loop->_next ->counted_loop(phase);
2440 }
2441 


















































2442 #ifndef PRODUCT
2443 //------------------------------dump_head--------------------------------------
2444 // Dump 1 liner for loop header info
2445 void IdealLoopTree::dump_head( ) const {
2446   for (uint i=0; i<_nest; i++)
2447     tty->print("  ");

2448   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2449   if (_irreducible) tty->print(" IRREDUCIBLE");
2450   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2451   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2452   if (predicate != NULL ) {
2453     tty->print(" limit_check");
2454     entry = PhaseIdealLoop::skip_loop_predicates(entry);
2455   }
2456   if (UseLoopPredicate) {
2457     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2458     if (entry != NULL) {
2459       tty->print(" predicated");
2460       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2461     }
2462   }
2463   if (UseProfiledLoopPredicate) {
2464     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2465     if (entry != NULL) {
2466       tty->print(" profile_predicated");
2467     }


2496   if (_has_call) tty->print(" has_call");
2497   if (_has_sfpt) tty->print(" has_sfpt");
2498   if (_rce_candidate) tty->print(" rce");
2499   if (_safepts != NULL && _safepts->size() > 0) {
2500     tty->print(" sfpts={"); _safepts->dump_simple(); tty->print(" }");
2501   }
2502   if (_required_safept != NULL && _required_safept->size() > 0) {
2503     tty->print(" req={"); _required_safept->dump_simple(); tty->print(" }");
2504   }
2505   if (Verbose) {
2506     tty->print(" body={"); _body.dump_simple(); tty->print(" }");
2507   }
2508   if (_head->is_Loop() && _head->as_Loop()->is_strip_mined()) {
2509     tty->print(" strip_mined");
2510   }
2511   tty->cr();
2512 }
2513 
2514 //------------------------------dump-------------------------------------------
2515 // Dump loops by loop tree
2516 void IdealLoopTree::dump( ) const {
2517   dump_head();
2518   if (_child) _child->dump();
2519   if (_next)  _next ->dump();
2520 }
2521 
2522 #endif
2523 
2524 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) {
2525   if (loop == root) {
2526     if (loop->_child != NULL) {
2527       log->begin_head("loop_tree");
2528       log->end_head();
2529       if( loop->_child ) log_loop_tree(root, loop->_child, log);
2530       log->tail("loop_tree");
2531       assert(loop->_next == NULL, "what?");
2532     }
2533   } else {
2534     Node* head = loop->_head;
2535     log->begin_head("loop");
2536     log->print(" idx='%d' ", head->_idx);


2891       // make some more progress: we need to try processing expensive
2892       // nodes again.
2893       C->set_major_progress();
2894     }
2895     _igvn.optimize();
2896     return;
2897   }
2898 
2899   // Some parser-inserted loop predicates could never be used by loop
2900   // predication or they were moved away from loop during some optimizations.
2901   // For example, peeling. Eliminate them before next loop optimizations.
2902   eliminate_useless_predicates();
2903 
2904 #ifndef PRODUCT
2905   C->verify_graph_edges();
2906   if (_verify_me) {             // Nested verify pass?
2907     // Check to see if the verify mode is broken
2908     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2909     return;
2910   }
2911   if(VerifyLoopOptimizations) verify();
2912   if(TraceLoopOpts && C->has_loops()) {
2913     _ltree_root->dump();
2914   }
2915 #endif
2916 
2917   if (skip_loop_opts) {
2918     // restore major progress flag
2919     for (int i = 0; i < old_progress; i++) {
2920       C->set_major_progress();
2921     }
2922 
2923     // Cleanup any modified bits
2924     _igvn.optimize();
2925 
2926     if (C->log() != NULL) {
2927       log_loop_tree(_ltree_root, _ltree_root, C->log());
2928     }
2929     return;
2930   }
2931 
2932   if (bs->optimize_loops(this, mode, visited, nstack, worklist)) {
2933     _igvn.optimize();
2934     if (C->log() != NULL) {
2935       log_loop_tree(_ltree_root, _ltree_root, C->log());
2936     }
2937     return;
2938   }
2939 
2940   if (ReassociateInvariants) {
2941     AutoNodeBudget node_budget(this, AutoNodeBudget::NO_BUDGET_CHECK);
2942     // Reassociate invariants and prep for split_thru_phi
2943     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2944       IdealLoopTree* lpt = iter.current();
2945       bool is_counted = lpt->is_counted();
2946       if (!is_counted || !lpt->is_innermost()) continue;
2947 
2948       // check for vectorized loops, any reassociation of invariants was already done
2949       if (is_counted && lpt->_head->as_CountedLoop()->is_unroll_only()) continue;
2950 


2951       lpt->reassociate_invariants(this);
2952 
2953       // Because RCE opportunities can be masked by split_thru_phi,
2954       // look for RCE candidates and inhibit split_thru_phi
2955       // on just their loop-phi's for this pass of loop opts
2956       if (SplitIfBlocks && do_split_ifs) {

2957         if (lpt->policy_range_check(this)) {
2958           lpt->_rce_candidate = 1; // = true
2959         }
2960       }
2961     }
2962   }
2963 
2964   // Check for aggressive application of split-if and other transforms
2965   // that require basic-block info (like cloning through Phi's)
2966   if( SplitIfBlocks && do_split_ifs ) {
2967     visited.Clear();
2968     split_if_with_blocks( visited, nstack, mode == LoopOptsLastRound );
2969     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2970     if (mode == LoopOptsLastRound) {
2971       C->set_major_progress();
2972     }
2973   }
2974 
2975   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2976     C->set_major_progress();


   1 /*
   2  * Copyright (c) 1998, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   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
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


2422     // Remove safepoints
2423     bool keep_one_sfpt = !(_has_call || _has_sfpt);
2424     remove_safepoints(phase, keep_one_sfpt);
2425 
2426     // Look for induction variables
2427     phase->replace_parallel_iv(this);
2428 
2429   } else if (_parent != NULL && !_irreducible) {
2430     // Not a counted loop. Keep one safepoint.
2431     bool keep_one_sfpt = true;
2432     remove_safepoints(phase, keep_one_sfpt);
2433   }
2434 
2435   // Recursively
2436   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2437   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2438   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2439   if (loop->_next)  loop->_next ->counted_loop(phase);
2440 }
2441 
2442 
2443 // The Estimated Loop Clone Size:
2444 //   CloneFactor * (~112% * BodySize + BC) + CC + FanOutTerm,
2445 // where  BC and  CC are  totally ad-hoc/magic  "body" and "clone" constants,
2446 // respectively, used to ensure that the node usage estimates made are on the
2447 // safe side, for the most part. The FanOutTerm is an attempt to estimate the
2448 // possible additional/excessive nodes generated due to data and control flow
2449 // merging, for edges reaching outside the loop.
2450 uint IdealLoopTree::est_loop_clone_sz(uint factor) const {
2451 
2452   precond(0 < factor && factor < 16);
2453 
2454   uint const bc = 13;
2455   uint const cc = 17;
2456   uint const sz = _body.size() + (_body.size() + 7) / 8;
2457   uint estimate = factor * (sz + bc) + cc;
2458 
2459   assert((estimate - cc) / factor == sz + bc, "overflow");
2460 
2461   uint ctrl_edge_out_cnt = 0;
2462   uint data_edge_out_cnt = 0;
2463 
2464   for (uint i = 0; i < _body.size(); i++) {
2465     Node* node = _body.at(i);
2466     uint outcnt = node->outcnt();
2467 
2468     for (uint k = 0; k < outcnt; k++) {
2469       Node* out = node->raw_out(k);
2470 
2471       if (out->is_CFG()) {
2472         if (!is_member(_phase->get_loop(out))) {
2473           ctrl_edge_out_cnt++;
2474         }
2475       } else {
2476         Node* ctrl = _phase->get_ctrl(out);
2477         assert(ctrl->is_CFG(), "must be");
2478         if (!is_member(_phase->get_loop(ctrl))) {
2479           data_edge_out_cnt++;
2480         }
2481       }
2482     }
2483   }
2484   // Add data (x1.5) and control (x1.0) count to estimate iff both are > 0.
2485   if (ctrl_edge_out_cnt > 0 && data_edge_out_cnt > 0) {
2486     estimate += ctrl_edge_out_cnt + data_edge_out_cnt + data_edge_out_cnt / 2;
2487   }
2488 
2489   return estimate;
2490 }
2491 
2492 #ifndef PRODUCT
2493 //------------------------------dump_head--------------------------------------
2494 // Dump 1 liner for loop header info
2495 void IdealLoopTree::dump_head() const {
2496   for (uint i = 0; i < _nest; i++) {
2497     tty->print("  ");
2498   }
2499   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2500   if (_irreducible) tty->print(" IRREDUCIBLE");
2501   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2502   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2503   if (predicate != NULL ) {
2504     tty->print(" limit_check");
2505     entry = PhaseIdealLoop::skip_loop_predicates(entry);
2506   }
2507   if (UseLoopPredicate) {
2508     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2509     if (entry != NULL) {
2510       tty->print(" predicated");
2511       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2512     }
2513   }
2514   if (UseProfiledLoopPredicate) {
2515     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2516     if (entry != NULL) {
2517       tty->print(" profile_predicated");
2518     }


2547   if (_has_call) tty->print(" has_call");
2548   if (_has_sfpt) tty->print(" has_sfpt");
2549   if (_rce_candidate) tty->print(" rce");
2550   if (_safepts != NULL && _safepts->size() > 0) {
2551     tty->print(" sfpts={"); _safepts->dump_simple(); tty->print(" }");
2552   }
2553   if (_required_safept != NULL && _required_safept->size() > 0) {
2554     tty->print(" req={"); _required_safept->dump_simple(); tty->print(" }");
2555   }
2556   if (Verbose) {
2557     tty->print(" body={"); _body.dump_simple(); tty->print(" }");
2558   }
2559   if (_head->is_Loop() && _head->as_Loop()->is_strip_mined()) {
2560     tty->print(" strip_mined");
2561   }
2562   tty->cr();
2563 }
2564 
2565 //------------------------------dump-------------------------------------------
2566 // Dump loops by loop tree
2567 void IdealLoopTree::dump() const {
2568   dump_head();
2569   if (_child) _child->dump();
2570   if (_next)  _next ->dump();
2571 }
2572 
2573 #endif
2574 
2575 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) {
2576   if (loop == root) {
2577     if (loop->_child != NULL) {
2578       log->begin_head("loop_tree");
2579       log->end_head();
2580       if( loop->_child ) log_loop_tree(root, loop->_child, log);
2581       log->tail("loop_tree");
2582       assert(loop->_next == NULL, "what?");
2583     }
2584   } else {
2585     Node* head = loop->_head;
2586     log->begin_head("loop");
2587     log->print(" idx='%d' ", head->_idx);


2942       // make some more progress: we need to try processing expensive
2943       // nodes again.
2944       C->set_major_progress();
2945     }
2946     _igvn.optimize();
2947     return;
2948   }
2949 
2950   // Some parser-inserted loop predicates could never be used by loop
2951   // predication or they were moved away from loop during some optimizations.
2952   // For example, peeling. Eliminate them before next loop optimizations.
2953   eliminate_useless_predicates();
2954 
2955 #ifndef PRODUCT
2956   C->verify_graph_edges();
2957   if (_verify_me) {             // Nested verify pass?
2958     // Check to see if the verify mode is broken
2959     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2960     return;
2961   }
2962   if (VerifyLoopOptimizations) verify();
2963   if (TraceLoopOpts && C->has_loops()) {
2964     _ltree_root->dump();
2965   }
2966 #endif
2967 
2968   if (skip_loop_opts) {
2969     // restore major progress flag
2970     for (int i = 0; i < old_progress; i++) {
2971       C->set_major_progress();
2972     }
2973 
2974     // Cleanup any modified bits
2975     _igvn.optimize();
2976 
2977     if (C->log() != NULL) {
2978       log_loop_tree(_ltree_root, _ltree_root, C->log());
2979     }
2980     return;
2981   }
2982 
2983   if (bs->optimize_loops(this, mode, visited, nstack, worklist)) {
2984     _igvn.optimize();
2985     if (C->log() != NULL) {
2986       log_loop_tree(_ltree_root, _ltree_root, C->log());
2987     }
2988     return;
2989   }
2990 
2991   if (ReassociateInvariants) {

2992     // Reassociate invariants and prep for split_thru_phi
2993     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2994       IdealLoopTree* lpt = iter.current();
2995       bool is_counted = lpt->is_counted();
2996       if (!is_counted || !lpt->is_innermost()) continue;
2997 
2998       // check for vectorized loops, any reassociation of invariants was already done
2999       if (is_counted && lpt->_head->as_CountedLoop()->is_unroll_only()) {
3000         continue;
3001       } else {
3002         AutoNodeBudget node_budget(this);
3003         lpt->reassociate_invariants(this);
3004       }
3005       // Because RCE opportunities can be masked by split_thru_phi,
3006       // look for RCE candidates and inhibit split_thru_phi
3007       // on just their loop-phi's for this pass of loop opts
3008       if (SplitIfBlocks && do_split_ifs) {
3009         AutoNodeBudget node_budget(this, AutoNodeBudget::NO_BUDGET_CHECK);
3010         if (lpt->policy_range_check(this)) {
3011           lpt->_rce_candidate = 1; // = true
3012         }
3013       }
3014     }
3015   }
3016 
3017   // Check for aggressive application of split-if and other transforms
3018   // that require basic-block info (like cloning through Phi's)
3019   if( SplitIfBlocks && do_split_ifs ) {
3020     visited.Clear();
3021     split_if_with_blocks( visited, nstack, mode == LoopOptsLastRound );
3022     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
3023     if (mode == LoopOptsLastRound) {
3024       C->set_major_progress();
3025     }
3026   }
3027 
3028   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
3029     C->set_major_progress();


< prev index next >