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();
|