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