23 */
24
25 #include "precompiled.hpp"
26 #include "ci/ciMethodData.hpp"
27 #include "compiler/compileLog.hpp"
28 #include "gc/shared/barrierSet.hpp"
29 #include "gc/shared/c2/barrierSetC2.hpp"
30 #include "libadt/vectset.hpp"
31 #include "memory/allocation.inline.hpp"
32 #include "memory/resourceArea.hpp"
33 #include "opto/addnode.hpp"
34 #include "opto/callnode.hpp"
35 #include "opto/connode.hpp"
36 #include "opto/convertnode.hpp"
37 #include "opto/divnode.hpp"
38 #include "opto/idealGraphPrinter.hpp"
39 #include "opto/loopnode.hpp"
40 #include "opto/mulnode.hpp"
41 #include "opto/rootnode.hpp"
42 #include "opto/superword.hpp"
43
44 //=============================================================================
45 //------------------------------is_loop_iv-------------------------------------
46 // Determine if a node is Counted loop induction variable.
47 // The method is declared in node.hpp.
48 const Node* Node::is_loop_iv() const {
49 if (this->is_Phi() && !this->as_Phi()->is_copy() &&
50 this->as_Phi()->region()->is_CountedLoop() &&
51 this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
52 return this;
53 } else {
54 return NULL;
55 }
56 }
57
58 //=============================================================================
59 //------------------------------dump_spec--------------------------------------
60 // Dump special per-node info
61 #ifndef PRODUCT
62 void LoopNode::dump_spec(outputStream *st) const {
2696 }
2697 if (n2->in(0) != c2) {
2698 _igvn.hash_delete(n2);
2699 n2->set_req(0, c2);
2700 _igvn.hash_insert(n2);
2701 _igvn._worklist.push(n2);
2702 progress = true;
2703 }
2704 }
2705 }
2706 }
2707
2708 return progress;
2709 }
2710
2711
2712 //=============================================================================
2713 //----------------------------build_and_optimize-------------------------------
2714 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
2715 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
2716 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool skip_loop_opts, bool last_round) {
2717 ResourceMark rm;
2718
2719 int old_progress = C->major_progress();
2720 uint orig_worklist_size = _igvn._worklist.size();
2721
2722 // Reset major-progress flag for the driver's heuristics
2723 C->clear_major_progress();
2724
2725 #ifndef PRODUCT
2726 // Capture for later assert
2727 uint unique = C->unique();
2728 _loop_invokes++;
2729 _loop_work += unique;
2730 #endif
2731
2732 // True if the method has at least 1 irreducible loop
2733 _has_irreducible_loops = false;
2734
2735 _created_loop_node = false;
2736
2760 build_loop_tree();
2761 // Check for bailout, and return
2762 if (C->failing()) {
2763 return;
2764 }
2765
2766 // No loops after all
2767 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2768
2769 // There should always be an outer loop containing the Root and Return nodes.
2770 // If not, we have a degenerate empty program. Bail out in this case.
2771 if (!has_node(C->root())) {
2772 if (!_verify_only) {
2773 C->clear_major_progress();
2774 C->record_method_not_compilable("empty program detected during loop optimization");
2775 }
2776 return;
2777 }
2778
2779 // Nothing to do, so get out
2780 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2781 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2782 if (stop_early && !do_expensive_nodes) {
2783 _igvn.optimize(); // Cleanup NeverBranches
2784 return;
2785 }
2786
2787 // Set loop nesting depth
2788 _ltree_root->set_nest( 0 );
2789
2790 // Split shared headers and insert loop landing pads.
2791 // Do not bother doing this on the Root loop of course.
2792 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2793 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2794 if( _ltree_root->_child->beautify_loops( this ) ) {
2795 // Re-build loop tree!
2796 _ltree_root->_child = NULL;
2797 _nodes.clear();
2798 reallocate_preorders();
2799 build_loop_tree();
2800 // Check for bailout, and return
2839
2840 // Walk the DATA nodes and place into loops. Find earliest control
2841 // node. For CFG nodes, the _nodes array starts out and remains
2842 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2843 // _nodes array holds the earliest legal controlling CFG node.
2844
2845 // Allocate stack with enough space to avoid frequent realloc
2846 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2847 Node_Stack nstack( a, stack_size );
2848
2849 visited.Clear();
2850 Node_List worklist(a);
2851 // Don't need C->root() on worklist since
2852 // it will be processed among C->top() inputs
2853 worklist.push( C->top() );
2854 visited.set( C->top()->_idx ); // Set C->top() as visited now
2855 build_loop_early( visited, worklist, nstack );
2856
2857 // Given early legal placement, try finding counted loops. This placement
2858 // is good enough to discover most loop invariants.
2859 if( !_verify_me && !_verify_only )
2860 _ltree_root->counted_loop( this );
2861
2862 // Find latest loop placement. Find ideal loop placement.
2863 visited.Clear();
2864 init_dom_lca_tags();
2865 // Need C->root() on worklist when processing outs
2866 worklist.push( C->root() );
2867 NOT_PRODUCT( C->verify_graph_edges(); )
2868 worklist.push( C->top() );
2869 build_loop_late( visited, worklist, nstack );
2870
2871 if (_verify_only) {
2872 // restore major progress flag
2873 for (int i = 0; i < old_progress; i++)
2874 C->set_major_progress();
2875 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2876 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2877 return;
2878 }
2879
2880 // clear out the dead code after build_loop_late
2911 if(TraceLoopOpts && C->has_loops()) {
2912 _ltree_root->dump();
2913 }
2914 #endif
2915
2916 if (skip_loop_opts) {
2917 // restore major progress flag
2918 for (int i = 0; i < old_progress; i++) {
2919 C->set_major_progress();
2920 }
2921
2922 // Cleanup any modified bits
2923 _igvn.optimize();
2924
2925 if (C->log() != NULL) {
2926 log_loop_tree(_ltree_root, _ltree_root, C->log());
2927 }
2928 return;
2929 }
2930
2931 if (ReassociateInvariants) {
2932 // Reassociate invariants and prep for split_thru_phi
2933 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2934 IdealLoopTree* lpt = iter.current();
2935 bool is_counted = lpt->is_counted();
2936 if (!is_counted || !lpt->is_inner()) continue;
2937
2938 // check for vectorized loops, any reassociation of invariants was already done
2939 if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2940
2941 lpt->reassociate_invariants(this);
2942
2943 // Because RCE opportunities can be masked by split_thru_phi,
2944 // look for RCE candidates and inhibit split_thru_phi
2945 // on just their loop-phi's for this pass of loop opts
2946 if (SplitIfBlocks && do_split_ifs) {
2947 if (lpt->policy_range_check(this)) {
2948 lpt->_rce_candidate = 1; // = true
2949 }
2950 }
2951 }
2952 }
2953
2954 // Check for aggressive application of split-if and other transforms
2955 // that require basic-block info (like cloning through Phi's)
2956 if( SplitIfBlocks && do_split_ifs ) {
2957 visited.Clear();
2958 split_if_with_blocks( visited, nstack, last_round );
2959 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2960 if (last_round) {
2961 C->set_major_progress();
2962 }
2963 }
2964
2965 if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2966 C->set_major_progress();
2967 }
2968
2969 // Perform loop predication before iteration splitting
2970 if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2971 _ltree_root->_child->loop_predication(this);
2972 }
2973
2974 if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2975 if (do_intrinsify_fill()) {
2976 C->set_major_progress();
2977 }
2978 }
2979
2980 // Perform iteration-splitting on inner loops. Split iterations to avoid
3941 compute_lca_of_uses(n, early, true);
3942 }
3943 #endif
3944
3945 // if this is a load, check for anti-dependent stores
3946 // We use a conservative algorithm to identify potential interfering
3947 // instructions and for rescheduling the load. The users of the memory
3948 // input of this load are examined. Any use which is not a load and is
3949 // dominated by early is considered a potentially interfering store.
3950 // This can produce false positives.
3951 if (n->is_Load() && LCA != early) {
3952 Node_List worklist;
3953
3954 Node *mem = n->in(MemNode::Memory);
3955 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3956 Node* s = mem->fast_out(i);
3957 worklist.push(s);
3958 }
3959 while(worklist.size() != 0 && LCA != early) {
3960 Node* s = worklist.pop();
3961 if (s->is_Load() || s->Opcode() == Op_SafePoint) {
3962 continue;
3963 } else if (s->is_MergeMem()) {
3964 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3965 Node* s1 = s->fast_out(i);
3966 worklist.push(s1);
3967 }
3968 } else {
3969 Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3970 assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3971 if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3972 LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3973 }
3974 }
3975 }
3976 }
3977
3978 assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3979 return LCA;
3980 }
3981
4129 }
4130 // Get saved parent node and next use's index. Visit the rest of uses.
4131 n = nstack.node();
4132 cnt = n->outcnt();
4133 i = nstack.index();
4134 nstack.pop();
4135 }
4136 }
4137 }
4138 }
4139
4140 // Verify that no data node is schedules in the outer loop of a strip
4141 // mined loop.
4142 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4143 #ifdef ASSERT
4144 if (get_loop(least)->_nest == 0) {
4145 return;
4146 }
4147 IdealLoopTree* loop = get_loop(least);
4148 Node* head = loop->_head;
4149 if (head->is_OuterStripMinedLoop()) {
4150 Node* sfpt = head->as_Loop()->outer_safepoint();
4151 ResourceMark rm;
4152 Unique_Node_List wq;
4153 wq.push(sfpt);
4154 for (uint i = 0; i < wq.size(); i++) {
4155 Node *m = wq.at(i);
4156 for (uint i = 1; i < m->req(); i++) {
4157 Node* nn = m->in(i);
4158 if (nn == n) {
4159 return;
4160 }
4161 if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4162 wq.push(nn);
4163 }
4164 }
4165 }
4166 ShouldNotReachHere();
4167 }
4168 #endif
4169 }
4209 case Op_LoadI:
4210 case Op_LoadKlass:
4211 case Op_LoadNKlass:
4212 case Op_LoadL:
4213 case Op_LoadS:
4214 case Op_LoadP:
4215 case Op_LoadBarrierSlowReg:
4216 case Op_LoadBarrierWeakSlowReg:
4217 case Op_LoadN:
4218 case Op_LoadRange:
4219 case Op_LoadD_unaligned:
4220 case Op_LoadL_unaligned:
4221 case Op_StrComp: // Does a bunch of load-like effects
4222 case Op_StrEquals:
4223 case Op_StrIndexOf:
4224 case Op_StrIndexOfChar:
4225 case Op_AryEq:
4226 case Op_HasNegatives:
4227 pinned = false;
4228 }
4229 if( pinned ) {
4230 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4231 if( !chosen_loop->_child ) // Inner loop?
4232 chosen_loop->_body.push(n); // Collect inner loops
4233 return;
4234 }
4235 } else { // No slot zero
4236 if( n->is_CFG() ) { // CFG with no slot 0 is dead
4237 _nodes.map(n->_idx,0); // No block setting, it's globally dead
4238 return;
4239 }
4240 assert(!n->is_CFG() || n->outcnt() == 0, "");
4241 }
4242
4243 // Do I have a "safe range" I can select over?
4244 Node *early = get_ctrl(n);// Early location already computed
4245
4246 // Compute latest point this Node can go
4247 Node *LCA = get_late_ctrl( n, early );
4248 // LCA is NULL due to uses being dead
4473 }
4474 // Dump nodes it controls
4475 for( uint k = 0; k < _nodes.Size(); k++ ) {
4476 // (k < C->unique() && get_ctrl(find(k)) == n)
4477 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4478 Node *m = C->root()->find(k);
4479 if( m && m->outcnt() > 0 ) {
4480 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4481 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4482 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4483 }
4484 for( uint j = 0; j < loop->_nest; j++ )
4485 tty->print(" ");
4486 tty->print(" ");
4487 m->dump();
4488 }
4489 }
4490 }
4491 }
4492 }
4493
4494 // Collect a R-P-O for the whole CFG.
4495 // Result list is in post-order (scan backwards for RPO)
4496 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4497 stk.push(start, 0);
4498 visited.set(start->_idx);
4499
4500 while (stk.is_nonempty()) {
4501 Node* m = stk.node();
4502 uint idx = stk.index();
4503 if (idx < m->outcnt()) {
4504 stk.set_index(idx + 1);
4505 Node* n = m->raw_out(idx);
4506 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4507 stk.push(n, 0);
4508 }
4509 } else {
4510 rpo_list.push(m);
4511 stk.pop();
4512 }
4513 }
4514 }
4515 #endif
4516
4517
4518 //=============================================================================
4519 //------------------------------LoopTreeIterator-----------------------------------
4520
4521 // Advance to next loop tree using a preorder, left-to-right traversal.
4522 void LoopTreeIterator::next() {
4523 assert(!done(), "must not be done.");
4524 if (_curnt->_child != NULL) {
4525 _curnt = _curnt->_child;
4526 } else if (_curnt->_next != NULL) {
4527 _curnt = _curnt->_next;
4528 } else {
4529 while (_curnt != _root && _curnt->_next == NULL) {
4530 _curnt = _curnt->_parent;
4531 }
4532 if (_curnt == _root) {
4533 _curnt = NULL;
4534 assert(done(), "must be done.");
4535 } else {
|
23 */
24
25 #include "precompiled.hpp"
26 #include "ci/ciMethodData.hpp"
27 #include "compiler/compileLog.hpp"
28 #include "gc/shared/barrierSet.hpp"
29 #include "gc/shared/c2/barrierSetC2.hpp"
30 #include "libadt/vectset.hpp"
31 #include "memory/allocation.inline.hpp"
32 #include "memory/resourceArea.hpp"
33 #include "opto/addnode.hpp"
34 #include "opto/callnode.hpp"
35 #include "opto/connode.hpp"
36 #include "opto/convertnode.hpp"
37 #include "opto/divnode.hpp"
38 #include "opto/idealGraphPrinter.hpp"
39 #include "opto/loopnode.hpp"
40 #include "opto/mulnode.hpp"
41 #include "opto/rootnode.hpp"
42 #include "opto/superword.hpp"
43 #include "utilities/macros.hpp"
44 #if INCLUDE_SHENANDOAHGC
45 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
46 #endif
47
48 //=============================================================================
49 //------------------------------is_loop_iv-------------------------------------
50 // Determine if a node is Counted loop induction variable.
51 // The method is declared in node.hpp.
52 const Node* Node::is_loop_iv() const {
53 if (this->is_Phi() && !this->as_Phi()->is_copy() &&
54 this->as_Phi()->region()->is_CountedLoop() &&
55 this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
56 return this;
57 } else {
58 return NULL;
59 }
60 }
61
62 //=============================================================================
63 //------------------------------dump_spec--------------------------------------
64 // Dump special per-node info
65 #ifndef PRODUCT
66 void LoopNode::dump_spec(outputStream *st) const {
2700 }
2701 if (n2->in(0) != c2) {
2702 _igvn.hash_delete(n2);
2703 n2->set_req(0, c2);
2704 _igvn.hash_insert(n2);
2705 _igvn._worklist.push(n2);
2706 progress = true;
2707 }
2708 }
2709 }
2710 }
2711
2712 return progress;
2713 }
2714
2715
2716 //=============================================================================
2717 //----------------------------build_and_optimize-------------------------------
2718 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
2719 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
2720 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2721 bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsZgcLastRound);
2722 bool skip_loop_opts = (mode == LoopOptsNone) ;
2723 bool shenandoah_opts = (mode == LoopOptsShenandoahExpand ||
2724 mode == LoopOptsShenandoahPostExpand);
2725
2726 ResourceMark rm;
2727
2728 int old_progress = C->major_progress();
2729 uint orig_worklist_size = _igvn._worklist.size();
2730
2731 // Reset major-progress flag for the driver's heuristics
2732 C->clear_major_progress();
2733
2734 #ifndef PRODUCT
2735 // Capture for later assert
2736 uint unique = C->unique();
2737 _loop_invokes++;
2738 _loop_work += unique;
2739 #endif
2740
2741 // True if the method has at least 1 irreducible loop
2742 _has_irreducible_loops = false;
2743
2744 _created_loop_node = false;
2745
2769 build_loop_tree();
2770 // Check for bailout, and return
2771 if (C->failing()) {
2772 return;
2773 }
2774
2775 // No loops after all
2776 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2777
2778 // There should always be an outer loop containing the Root and Return nodes.
2779 // If not, we have a degenerate empty program. Bail out in this case.
2780 if (!has_node(C->root())) {
2781 if (!_verify_only) {
2782 C->clear_major_progress();
2783 C->record_method_not_compilable("empty program detected during loop optimization");
2784 }
2785 return;
2786 }
2787
2788 // Nothing to do, so get out
2789 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only && !shenandoah_opts;
2790 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2791 if (stop_early && !do_expensive_nodes) {
2792 _igvn.optimize(); // Cleanup NeverBranches
2793 return;
2794 }
2795
2796 // Set loop nesting depth
2797 _ltree_root->set_nest( 0 );
2798
2799 // Split shared headers and insert loop landing pads.
2800 // Do not bother doing this on the Root loop of course.
2801 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2802 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2803 if( _ltree_root->_child->beautify_loops( this ) ) {
2804 // Re-build loop tree!
2805 _ltree_root->_child = NULL;
2806 _nodes.clear();
2807 reallocate_preorders();
2808 build_loop_tree();
2809 // Check for bailout, and return
2848
2849 // Walk the DATA nodes and place into loops. Find earliest control
2850 // node. For CFG nodes, the _nodes array starts out and remains
2851 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2852 // _nodes array holds the earliest legal controlling CFG node.
2853
2854 // Allocate stack with enough space to avoid frequent realloc
2855 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2856 Node_Stack nstack( a, stack_size );
2857
2858 visited.Clear();
2859 Node_List worklist(a);
2860 // Don't need C->root() on worklist since
2861 // it will be processed among C->top() inputs
2862 worklist.push( C->top() );
2863 visited.set( C->top()->_idx ); // Set C->top() as visited now
2864 build_loop_early( visited, worklist, nstack );
2865
2866 // Given early legal placement, try finding counted loops. This placement
2867 // is good enough to discover most loop invariants.
2868 if (!_verify_me && !_verify_only && !shenandoah_opts) {
2869 _ltree_root->counted_loop(this);
2870 }
2871
2872 // Find latest loop placement. Find ideal loop placement.
2873 visited.Clear();
2874 init_dom_lca_tags();
2875 // Need C->root() on worklist when processing outs
2876 worklist.push( C->root() );
2877 NOT_PRODUCT( C->verify_graph_edges(); )
2878 worklist.push( C->top() );
2879 build_loop_late( visited, worklist, nstack );
2880
2881 if (_verify_only) {
2882 // restore major progress flag
2883 for (int i = 0; i < old_progress; i++)
2884 C->set_major_progress();
2885 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2886 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2887 return;
2888 }
2889
2890 // clear out the dead code after build_loop_late
2921 if(TraceLoopOpts && C->has_loops()) {
2922 _ltree_root->dump();
2923 }
2924 #endif
2925
2926 if (skip_loop_opts) {
2927 // restore major progress flag
2928 for (int i = 0; i < old_progress; i++) {
2929 C->set_major_progress();
2930 }
2931
2932 // Cleanup any modified bits
2933 _igvn.optimize();
2934
2935 if (C->log() != NULL) {
2936 log_loop_tree(_ltree_root, _ltree_root, C->log());
2937 }
2938 return;
2939 }
2940
2941 #if INCLUDE_SHENANDOAHGC
2942 if (UseShenandoahGC && ((ShenandoahBarrierSetC2*) BarrierSet::barrier_set()->barrier_set_c2())->optimize_loops(this, mode, visited, nstack, worklist)) {
2943 _igvn.optimize();
2944 if (C->log() != NULL) {
2945 log_loop_tree(_ltree_root, _ltree_root, C->log());
2946 }
2947 return;
2948 }
2949 #endif
2950
2951 if (ReassociateInvariants) {
2952 // Reassociate invariants and prep for split_thru_phi
2953 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2954 IdealLoopTree* lpt = iter.current();
2955 bool is_counted = lpt->is_counted();
2956 if (!is_counted || !lpt->is_inner()) continue;
2957
2958 // check for vectorized loops, any reassociation of invariants was already done
2959 if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2960
2961 lpt->reassociate_invariants(this);
2962
2963 // Because RCE opportunities can be masked by split_thru_phi,
2964 // look for RCE candidates and inhibit split_thru_phi
2965 // on just their loop-phi's for this pass of loop opts
2966 if (SplitIfBlocks && do_split_ifs) {
2967 if (lpt->policy_range_check(this)) {
2968 lpt->_rce_candidate = 1; // = true
2969 }
2970 }
2971 }
2972 }
2973
2974 // Check for aggressive application of split-if and other transforms
2975 // that require basic-block info (like cloning through Phi's)
2976 if( SplitIfBlocks && do_split_ifs ) {
2977 visited.Clear();
2978 split_if_with_blocks( visited, nstack, mode == LoopOptsZgcLastRound );
2979 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2980 if (mode == LoopOptsZgcLastRound) {
2981 C->set_major_progress();
2982 }
2983 }
2984
2985 if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2986 C->set_major_progress();
2987 }
2988
2989 // Perform loop predication before iteration splitting
2990 if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2991 _ltree_root->_child->loop_predication(this);
2992 }
2993
2994 if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2995 if (do_intrinsify_fill()) {
2996 C->set_major_progress();
2997 }
2998 }
2999
3000 // Perform iteration-splitting on inner loops. Split iterations to avoid
3961 compute_lca_of_uses(n, early, true);
3962 }
3963 #endif
3964
3965 // if this is a load, check for anti-dependent stores
3966 // We use a conservative algorithm to identify potential interfering
3967 // instructions and for rescheduling the load. The users of the memory
3968 // input of this load are examined. Any use which is not a load and is
3969 // dominated by early is considered a potentially interfering store.
3970 // This can produce false positives.
3971 if (n->is_Load() && LCA != early) {
3972 Node_List worklist;
3973
3974 Node *mem = n->in(MemNode::Memory);
3975 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3976 Node* s = mem->fast_out(i);
3977 worklist.push(s);
3978 }
3979 while(worklist.size() != 0 && LCA != early) {
3980 Node* s = worklist.pop();
3981 if (s->is_Load() || s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
3982 (UseShenandoahGC && s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
3983 continue;
3984 } else if (s->is_MergeMem()) {
3985 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3986 Node* s1 = s->fast_out(i);
3987 worklist.push(s1);
3988 }
3989 } else {
3990 Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3991 assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3992 if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3993 LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3994 }
3995 }
3996 }
3997 }
3998
3999 assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
4000 return LCA;
4001 }
4002
4150 }
4151 // Get saved parent node and next use's index. Visit the rest of uses.
4152 n = nstack.node();
4153 cnt = n->outcnt();
4154 i = nstack.index();
4155 nstack.pop();
4156 }
4157 }
4158 }
4159 }
4160
4161 // Verify that no data node is schedules in the outer loop of a strip
4162 // mined loop.
4163 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4164 #ifdef ASSERT
4165 if (get_loop(least)->_nest == 0) {
4166 return;
4167 }
4168 IdealLoopTree* loop = get_loop(least);
4169 Node* head = loop->_head;
4170 if (head->is_OuterStripMinedLoop() &&
4171 // Verification can't be applied to fully built strip mined loops
4172 head->as_Loop()->outer_loop_end()->in(1)->find_int_con(-1) == 0) {
4173 Node* sfpt = head->as_Loop()->outer_safepoint();
4174 ResourceMark rm;
4175 Unique_Node_List wq;
4176 wq.push(sfpt);
4177 for (uint i = 0; i < wq.size(); i++) {
4178 Node *m = wq.at(i);
4179 for (uint i = 1; i < m->req(); i++) {
4180 Node* nn = m->in(i);
4181 if (nn == n) {
4182 return;
4183 }
4184 if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4185 wq.push(nn);
4186 }
4187 }
4188 }
4189 ShouldNotReachHere();
4190 }
4191 #endif
4192 }
4232 case Op_LoadI:
4233 case Op_LoadKlass:
4234 case Op_LoadNKlass:
4235 case Op_LoadL:
4236 case Op_LoadS:
4237 case Op_LoadP:
4238 case Op_LoadBarrierSlowReg:
4239 case Op_LoadBarrierWeakSlowReg:
4240 case Op_LoadN:
4241 case Op_LoadRange:
4242 case Op_LoadD_unaligned:
4243 case Op_LoadL_unaligned:
4244 case Op_StrComp: // Does a bunch of load-like effects
4245 case Op_StrEquals:
4246 case Op_StrIndexOf:
4247 case Op_StrIndexOfChar:
4248 case Op_AryEq:
4249 case Op_HasNegatives:
4250 pinned = false;
4251 }
4252 if (UseShenandoahGC && n->is_CMove()) {
4253 pinned = false;
4254 }
4255 if( pinned ) {
4256 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4257 if( !chosen_loop->_child ) // Inner loop?
4258 chosen_loop->_body.push(n); // Collect inner loops
4259 return;
4260 }
4261 } else { // No slot zero
4262 if( n->is_CFG() ) { // CFG with no slot 0 is dead
4263 _nodes.map(n->_idx,0); // No block setting, it's globally dead
4264 return;
4265 }
4266 assert(!n->is_CFG() || n->outcnt() == 0, "");
4267 }
4268
4269 // Do I have a "safe range" I can select over?
4270 Node *early = get_ctrl(n);// Early location already computed
4271
4272 // Compute latest point this Node can go
4273 Node *LCA = get_late_ctrl( n, early );
4274 // LCA is NULL due to uses being dead
4499 }
4500 // Dump nodes it controls
4501 for( uint k = 0; k < _nodes.Size(); k++ ) {
4502 // (k < C->unique() && get_ctrl(find(k)) == n)
4503 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4504 Node *m = C->root()->find(k);
4505 if( m && m->outcnt() > 0 ) {
4506 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4507 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4508 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4509 }
4510 for( uint j = 0; j < loop->_nest; j++ )
4511 tty->print(" ");
4512 tty->print(" ");
4513 m->dump();
4514 }
4515 }
4516 }
4517 }
4518 }
4519 #endif
4520
4521 // Collect a R-P-O for the whole CFG.
4522 // Result list is in post-order (scan backwards for RPO)
4523 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4524 stk.push(start, 0);
4525 visited.set(start->_idx);
4526
4527 while (stk.is_nonempty()) {
4528 Node* m = stk.node();
4529 uint idx = stk.index();
4530 if (idx < m->outcnt()) {
4531 stk.set_index(idx + 1);
4532 Node* n = m->raw_out(idx);
4533 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4534 stk.push(n, 0);
4535 }
4536 } else {
4537 rpo_list.push(m);
4538 stk.pop();
4539 }
4540 }
4541 }
4542
4543
4544 //=============================================================================
4545 //------------------------------LoopTreeIterator-----------------------------------
4546
4547 // Advance to next loop tree using a preorder, left-to-right traversal.
4548 void LoopTreeIterator::next() {
4549 assert(!done(), "must not be done.");
4550 if (_curnt->_child != NULL) {
4551 _curnt = _curnt->_child;
4552 } else if (_curnt->_next != NULL) {
4553 _curnt = _curnt->_next;
4554 } else {
4555 while (_curnt != _root && _curnt->_next == NULL) {
4556 _curnt = _curnt->_parent;
4557 }
4558 if (_curnt == _root) {
4559 _curnt = NULL;
4560 assert(done(), "must be done.");
4561 } else {
|