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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/connode.hpp"
29 #include "opto/divnode.hpp"
30 #include "opto/loopnode.hpp"
31 #include "opto/matcher.hpp"
32 #include "opto/mulnode.hpp"
33 #include "opto/movenode.hpp"
34 #include "opto/opaquenode.hpp"
35 #include "opto/rootnode.hpp"
36 #include "opto/subnode.hpp"
37
38 //=============================================================================
39 //------------------------------split_thru_phi---------------------------------
40 // Split Node 'n' through merge point if there is enough win.
41 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
42 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
43 // ConvI2L may have type information on it which is unsafe to push up
44 // so disable this for now
45 return NULL;
46 }
47
48 int wins = 0;
49 assert(!n->is_CFG(), "");
50 assert(region->is_Region(), "");
51
52 const Type* type = n->bottom_type();
53 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
54 Node *phi;
55 if (t_oop != NULL && t_oop->is_known_instance_field()) {
56 int iid = t_oop->instance_id();
57 int index = C->get_alias_index(t_oop);
58 int offset = t_oop->offset();
59 phi = new PhiNode(region, type, NULL, iid, index, offset);
60 } else {
61 phi = PhiNode::make_blank(region, n);
62 }
63 uint old_unique = C->unique();
64 for (uint i = 1; i < region->req(); i++) {
65 Node *x;
66 Node* the_clone = NULL;
67 if (region->in(i) == C->top()) {
68 x = C->top(); // Dead path? Use a dead data op
69 } else {
70 x = n->clone(); // Else clone up the data op
71 the_clone = x; // Remember for possible deletion.
72 // Alter data node to use pre-phi inputs
73 if (n->in(0) == region)
74 x->set_req( 0, region->in(i) );
75 for (uint j = 1; j < n->req(); j++) {
76 Node *in = n->in(j);
77 if (in->is_Phi() && in->in(0) == region)
78 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
79 }
80 }
81 // Check for a 'win' on some paths
82 const Type *t = x->Value(&_igvn);
83
84 bool singleton = t->singleton();
85
86 // A TOP singleton indicates that there are no possible values incoming
87 // along a particular edge. In most cases, this is OK, and the Phi will
88 // be eliminated later in an Ideal call. However, we can't allow this to
89 // happen if the singleton occurs on loop entry, as the elimination of
94 // irreducible loop may not be indicated by an affirmative is_Loop());
95 // therefore, the only top we can split thru a phi is on a backedge of
96 // a loop.
97 singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
98 }
99
100 if (singleton) {
101 wins++;
102 x = ((PhaseGVN&)_igvn).makecon(t);
103 } else {
104 // We now call Identity to try to simplify the cloned node.
105 // Note that some Identity methods call phase->type(this).
106 // Make sure that the type array is big enough for
107 // our new node, even though we may throw the node away.
108 // (Note: This tweaking with igvn only works because x is a new node.)
109 _igvn.set_type(x, t);
110 // If x is a TypeNode, capture any more-precise type permanently into Node
111 // otherwise it will be not updated during igvn->transform since
112 // igvn->type(x) is set to x->Value() already.
113 x->raise_bottom_type(t);
114 Node *y = x->Identity(&_igvn);
115 if (y != x) {
116 wins++;
117 x = y;
118 } else {
119 y = _igvn.hash_find(x);
120 if (y) {
121 wins++;
122 x = y;
123 } else {
124 // Else x is a new node we are keeping
125 // We do not need register_new_node_with_optimizer
126 // because set_type has already been called.
127 _igvn._worklist.push(x);
128 }
129 }
130 }
131 if (x != the_clone && the_clone != NULL)
132 _igvn.remove_dead_node(the_clone);
133 phi->set_req( i, x );
134 }
135 // Too few wins?
136 if (wins <= policy) {
137 _igvn.remove_dead_node(phi);
138 return NULL;
139 }
140
141 // Record Phi
142 register_new_node( phi, region );
143
144 for (uint i2 = 1; i2 < phi->req(); i2++) {
145 Node *x = phi->in(i2);
146 // If we commoned up the cloned 'x' with another existing Node,
147 // the existing Node picks up a new use. We need to make the
148 // existing Node occur higher up so it dominates its uses.
149 Node *old_ctrl;
177 (old_loop == NULL || !new_loop->is_member(old_loop))) {
178 // Take early control, later control will be recalculated
179 // during next iteration of loop optimizations.
180 new_ctrl = get_early_ctrl(x);
181 new_loop = get_loop(new_ctrl);
182 }
183 // Set new location
184 set_ctrl(x, new_ctrl);
185 // If changing loop bodies, see if we need to collect into new body
186 if (old_loop != new_loop) {
187 if (old_loop && !old_loop->_child)
188 old_loop->_body.yank(x);
189 if (!new_loop->_child)
190 new_loop->_body.push(x); // Collect body info
191 }
192 }
193
194 return phi;
195 }
196
197 //------------------------------dominated_by------------------------------------
198 // Replace the dominated test with an obvious true or false. Place it on the
199 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the
200 // live path up to the dominating control.
201 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
202 #ifndef PRODUCT
203 if (VerifyLoopOptimizations && PrintOpto) tty->print_cr("dominating test");
204 #endif
205
206
207 // prevdom is the dominating projection of the dominating test.
208 assert( iff->is_If(), "" );
209 assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
210 int pop = prevdom->Opcode();
211 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
212 if (flip) {
213 if (pop == Op_IfTrue)
214 pop = Op_IfFalse;
215 else
216 pop = Op_IfTrue;
917 int policy = n_blk->req() >> 2;
918
919 // If the loop is a candidate for range check elimination,
920 // delay splitting through it's phi until a later loop optimization
921 if (n_blk->is_CountedLoop()) {
922 IdealLoopTree *lp = get_loop(n_blk);
923 if (lp && lp->_rce_candidate) {
924 return n;
925 }
926 }
927
928 // Use same limit as split_if_with_blocks_post
929 if( C->live_nodes() > 35000 ) return n; // Method too big
930
931 // Split 'n' through the merge point if it is profitable
932 Node *phi = split_thru_phi( n, n_blk, policy );
933 if (!phi) return n;
934
935 // Found a Phi to split thru!
936 // Replace 'n' with the new phi
937 _igvn.replace_node( n, phi );
938 // Moved a load around the loop, 'en-registering' something.
939 if (n_blk->is_Loop() && n->is_Load() &&
940 !phi->in(LoopNode::LoopBackControl)->is_Load())
941 C->set_major_progress();
942
943 return phi;
944 }
945
946 static bool merge_point_too_heavy(Compile* C, Node* region) {
947 // Bail out if the region and its phis have too many users.
948 int weight = 0;
949 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
950 weight += region->fast_out(i)->outcnt();
951 }
952 int nodes_left = C->max_node_limit() - C->live_nodes();
953 if (weight * 8 > nodes_left) {
954 #ifndef PRODUCT
955 if (PrintOpto)
956 tty->print_cr("*** Split-if bails out: %d nodes, region weight %d", C->unique(), weight);
957 #endif
958 return true;
959 } else {
960 return false;
961 }
962 }
1065 // for any input path not being in the same loop as n_ctrl. For
1066 // irreducible loops we cannot check for 'n_ctrl->is_Loop()'
1067 // because the alternative loop entry points won't be converted
1068 // into LoopNodes.
1069 IdealLoopTree *n_loop = get_loop(n_ctrl);
1070 for( uint j = 1; j < n_ctrl->req(); j++ )
1071 if( get_loop(n_ctrl->in(j)) != n_loop )
1072 return;
1073
1074 // Check for safety of the merge point.
1075 if( !merge_point_safe(n_ctrl) ) {
1076 return;
1077 }
1078
1079 // Split compare 'n' through the merge point if it is profitable
1080 Node *phi = split_thru_phi( n, n_ctrl, policy );
1081 if( !phi ) return;
1082
1083 // Found a Phi to split thru!
1084 // Replace 'n' with the new phi
1085 _igvn.replace_node( n, phi );
1086
1087 // Now split the bool up thru the phi
1088 Node *bolphi = split_thru_phi( bol, n_ctrl, -1 );
1089 guarantee(bolphi != NULL, "null boolean phi node");
1090
1091 _igvn.replace_node( bol, bolphi );
1092 assert( iff->in(1) == bolphi, "" );
1093
1094 if( bolphi->Value(&_igvn)->singleton() )
1095 return;
1096
1097 // Conditional-move? Must split up now
1098 if( !iff->is_If() ) {
1099 Node *cmovphi = split_thru_phi( iff, n_ctrl, -1 );
1100 _igvn.replace_node( iff, cmovphi );
1101 return;
1102 }
1103
1104 // Now split the IF
1105 do_split_if( iff );
1106 return;
1107 }
1108
1109 // Check for an IF ready to split; one that has its
1110 // condition codes input coming from a Phi at the block start.
1111 int n_op = n->Opcode();
1112
1113 // Check for an IF being dominated by another IF same test
1114 if (n_op == Op_If) {
1115 Node *bol = n->in(1);
1116 uint max = bol->outcnt();
1117 // Check for same test used more than once?
1118 if (max > 1 && bol->is_Bool()) {
1212 // Don't allow the control input to be a CFG splitting node.
1213 // Such nodes should only have ProjNodes as outs, e.g. IfNode
1214 // should only have IfTrueNode and IfFalseNode (4985384).
1215 x_ctrl = find_non_split_ctrl(x_ctrl);
1216 assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1217
1218 x->set_req(0, x_ctrl);
1219 }
1220 register_new_node(x, x_ctrl);
1221
1222 // Some institutional knowledge is needed here: 'x' is
1223 // yanked because if the optimizer runs GVN on it all the
1224 // cloned x's will common up and undo this optimization and
1225 // be forced back in the loop. This is annoying because it
1226 // makes +VerifyOpto report false-positives on progress. I
1227 // tried setting control edges on the x's to force them to
1228 // not combine, but the matching gets worried when it tries
1229 // to fold a StoreP and an AddP together (as part of an
1230 // address expression) and the AddP and StoreP have
1231 // different controls.
1232 if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1233 }
1234 _igvn.remove_dead_node(n);
1235 }
1236 }
1237 }
1238 }
1239
1240 try_move_store_after_loop(n);
1241
1242 // Check for Opaque2's who's loop has disappeared - who's input is in the
1243 // same loop nest as their output. Remove 'em, they are no longer useful.
1244 if( n_op == Op_Opaque2 &&
1245 n->in(1) != NULL &&
1246 get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1247 _igvn.replace_node( n, n->in(1) );
1248 }
1249 }
1250
1251 //------------------------------split_if_with_blocks---------------------------
1252 // Check for aggressive application of 'split-if' optimization,
1485 }
1486 }
1487 #endif
1488
1489 CloneMap& cm = C->clone_map();
1490 Dict* dict = cm.dict();
1491 if (C->do_vector_loop()) {
1492 cm.set_clone_idx(cm.max_gen()+1);
1493 #ifndef PRODUCT
1494 if (PrintOpto) {
1495 tty->print_cr("PhaseIdealLoop::clone_loop: _clone_idx %d", cm.clone_idx());
1496 loop->dump_head();
1497 }
1498 #endif
1499 }
1500
1501 // Step 1: Clone the loop body. Make the old->new mapping.
1502 uint i;
1503 for( i = 0; i < loop->_body.size(); i++ ) {
1504 Node *old = loop->_body.at(i);
1505 Node *nnn = old->clone();
1506 old_new.map( old->_idx, nnn );
1507 if (C->do_vector_loop()) {
1508 cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
1509 }
1510 _igvn.register_new_node_with_optimizer(nnn);
1511 }
1512
1513
1514 // Step 2: Fix the edges in the new body. If the old input is outside the
1515 // loop use it. If the old input is INside the loop, use the corresponding
1516 // new node instead.
1517 for( i = 0; i < loop->_body.size(); i++ ) {
1518 Node *old = loop->_body.at(i);
1519 Node *nnn = old_new[old->_idx];
1520 // Fix CFG/Loop controlling the new node
1521 if (has_ctrl(old)) {
1522 set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
1523 } else {
1524 set_loop(nnn, loop->_parent);
1675 : idom(prev);
1676 if( use->is_Phi() ) // Phi use is in prior block
1677 cfg = prev->in(idx); // NOT in block of Phi itself
1678 if (cfg->is_top()) { // Use is dead?
1679 _igvn.replace_input_of(use, idx, C->top());
1680 continue;
1681 }
1682
1683 while( !loop->is_member( get_loop( cfg ) ) ) {
1684 prev = cfg;
1685 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1686 }
1687 // If the use occurs after merging several exits from the loop, then
1688 // old value must have dominated all those exits. Since the same old
1689 // value was used on all those exits we did not need a Phi at this
1690 // merge point. NOW we do need a Phi here. Each loop exit value
1691 // is now merged with the peeled body exit; each exit gets its own
1692 // private Phi and those Phis need to be merged here.
1693 Node *phi;
1694 if( prev->is_Region() ) {
1695 if( idx == 0 ) { // Updating control edge?
1696 phi = prev; // Just use existing control
1697 } else { // Else need a new Phi
1698 phi = PhiNode::make( prev, old );
1699 // Now recursively fix up the new uses of old!
1700 for( uint i = 1; i < prev->req(); i++ ) {
1701 worklist.push(phi); // Onto worklist once for each 'old' input
1702 }
1703 }
1704 } else {
1705 // Get new RegionNode merging old and new loop exits
1706 prev = old_new[prev->_idx];
1707 assert( prev, "just made this in step 7" );
1708 if( idx == 0 ) { // Updating control edge?
1709 phi = prev; // Just use existing control
1710 } else { // Else need a new Phi
1711 // Make a new Phi merging data values properly
1712 phi = PhiNode::make( prev, old );
1713 phi->set_req( 1, nnn );
1714 }
1715 }
1716 // If inserting a new Phi, check for prior hits
1717 if( idx != 0 ) {
1718 Node *hit = _igvn.hash_find_insert(phi);
1719 if( hit == NULL ) {
1720 _igvn.register_new_node_with_optimizer(phi); // Register new phi
1721 } else { // or
1722 // Remove the new phi from the graph and use the hit
1723 _igvn.remove_dead_node(phi);
1724 phi = hit; // Use existing phi
1725 }
1726 set_ctrl(phi, prev);
1727 }
1728 // Make 'use' use the Phi instead of the old loop body exit value
2171
2172 //------------------------------ has_use_internal_to_set -------------------------------------
2173 // Has use internal to the vector set (ie. not in a phi at the loop head)
2174 bool PhaseIdealLoop::has_use_internal_to_set( Node* n, VectorSet& vset, IdealLoopTree *loop ) {
2175 Node* head = loop->_head;
2176 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2177 Node* use = n->fast_out(j);
2178 if (vset.test(use->_idx) && !(use->is_Phi() && use->in(0) == head)) {
2179 return true;
2180 }
2181 }
2182 return false;
2183 }
2184
2185
2186 //------------------------------ clone_for_use_outside_loop -------------------------------------
2187 // clone "n" for uses that are outside of loop
2188 int PhaseIdealLoop::clone_for_use_outside_loop( IdealLoopTree *loop, Node* n, Node_List& worklist ) {
2189 int cloned = 0;
2190 assert(worklist.size() == 0, "should be empty");
2191 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2192 Node* use = n->fast_out(j);
2193 if( !loop->is_member(get_loop(has_ctrl(use) ? get_ctrl(use) : use)) ) {
2194 worklist.push(use);
2195 }
2196 }
2197 while( worklist.size() ) {
2198 Node *use = worklist.pop();
2199 if (!has_node(use) || use->in(0) == C->top()) continue;
2200 uint j;
2201 for (j = 0; j < use->req(); j++) {
2202 if (use->in(j) == n) break;
2203 }
2204 assert(j < use->req(), "must be there");
2205
2206 // clone "n" and insert it between the inputs of "n" and the use outside the loop
2207 Node* n_clone = n->clone();
2208 _igvn.replace_input_of(use, j, n_clone);
2209 cloned++;
2210 Node* use_c;
2211 if (!use->is_Phi()) {
2212 use_c = has_ctrl(use) ? get_ctrl(use) : use->in(0);
2213 } else {
2214 // Use in a phi is considered a use in the associated predecessor block
2215 use_c = use->in(0)->in(j);
2216 }
2217 set_ctrl(n_clone, use_c);
2218 assert(!loop->is_member(get_loop(use_c)), "should be outside loop");
2219 get_loop(use_c)->_body.push(n_clone);
2220 _igvn.register_new_node_with_optimizer(n_clone);
2221 #if !defined(PRODUCT)
2222 if (TracePartialPeeling) {
2223 tty->print_cr("loop exit cloning old: %d new: %d newbb: %d", n->_idx, n_clone->_idx, get_ctrl(n_clone)->_idx);
2224 }
2225 #endif
2226 }
2233 // If these def-uses occur in separate blocks, the code generator
2234 // marks the method as not compilable. For example, if a "BoolNode"
2235 // is in a different basic block than the "IfNode" that uses it, then
2236 // the compilation is aborted in the code generator.
2237 void PhaseIdealLoop::clone_for_special_use_inside_loop( IdealLoopTree *loop, Node* n,
2238 VectorSet& not_peel, Node_List& sink_list, Node_List& worklist ) {
2239 if (n->is_Phi() || n->is_Load()) {
2240 return;
2241 }
2242 assert(worklist.size() == 0, "should be empty");
2243 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2244 Node* use = n->fast_out(j);
2245 if ( not_peel.test(use->_idx) &&
2246 (use->is_If() || use->is_CMove() || use->is_Bool()) &&
2247 use->in(1) == n) {
2248 worklist.push(use);
2249 }
2250 }
2251 if (worklist.size() > 0) {
2252 // clone "n" and insert it between inputs of "n" and the use
2253 Node* n_clone = n->clone();
2254 loop->_body.push(n_clone);
2255 _igvn.register_new_node_with_optimizer(n_clone);
2256 set_ctrl(n_clone, get_ctrl(n));
2257 sink_list.push(n_clone);
2258 not_peel <<= n_clone->_idx; // add n_clone to not_peel set.
2259 #if !defined(PRODUCT)
2260 if (TracePartialPeeling) {
2261 tty->print_cr("special not_peeled cloning old: %d new: %d", n->_idx, n_clone->_idx);
2262 }
2263 #endif
2264 while( worklist.size() ) {
2265 Node *use = worklist.pop();
2266 _igvn.rehash_node_delayed(use);
2267 for (uint j = 1; j < use->req(); j++) {
2268 if (use->in(j) == n) {
2269 use->set_req(j, n_clone);
2270 }
2271 }
2272 }
|
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 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/connode.hpp"
29 #include "opto/divnode.hpp"
30 #include "opto/loopnode.hpp"
31 #include "opto/matcher.hpp"
32 #include "opto/mulnode.hpp"
33 #include "opto/movenode.hpp"
34 #include "opto/opaquenode.hpp"
35 #include "opto/rootnode.hpp"
36 #include "opto/shenandoahSupport.hpp"
37 #include "opto/subnode.hpp"
38
39 //=============================================================================
40 //------------------------------split_thru_phi---------------------------------
41 // Split Node 'n' through merge point if there is enough win.
42 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
43 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
44 // ConvI2L may have type information on it which is unsafe to push up
45 // so disable this for now
46 return NULL;
47 }
48
49 int wins = 0;
50 assert(!n->is_CFG(), "");
51 assert(region->is_Region(), "");
52
53 const Type* type = n->bottom_type();
54 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
55 Node *phi;
56 if (t_oop != NULL && t_oop->is_known_instance_field()) {
57 int iid = t_oop->instance_id();
58 int index = C->get_alias_index(t_oop);
59 int offset = t_oop->offset();
60 phi = new PhiNode(region, type, NULL, iid, index, offset);
61 } else {
62 phi = PhiNode::make_blank(region, n);
63 }
64 uint old_unique = C->unique();
65 for (uint i = 1; i < region->req(); i++) {
66 Node *x;
67 Node* the_clone = NULL;
68 if (region->in(i) == C->top()) {
69 x = C->top(); // Dead path? Use a dead data op
70 } else {
71 #ifdef ASSERT
72 if (n->is_ShenandoahBarrier()) { n->as_ShenandoahBarrier()->check_invariants(); }
73 #endif
74 x = n->clone(); // Else clone up the data op
75 the_clone = x; // Remember for possible deletion.
76 // Alter data node to use pre-phi inputs
77 if (n->in(0) == region)
78 x->set_req( 0, region->in(i) );
79 for (uint j = 1; j < n->req(); j++) {
80 Node *in = n->in(j);
81 if (in->is_Phi() && in->in(0) == region)
82 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
83 }
84 }
85 // Check for a 'win' on some paths
86 const Type *t = x->Value(&_igvn);
87
88 bool singleton = t->singleton();
89
90 // A TOP singleton indicates that there are no possible values incoming
91 // along a particular edge. In most cases, this is OK, and the Phi will
92 // be eliminated later in an Ideal call. However, we can't allow this to
93 // happen if the singleton occurs on loop entry, as the elimination of
98 // irreducible loop may not be indicated by an affirmative is_Loop());
99 // therefore, the only top we can split thru a phi is on a backedge of
100 // a loop.
101 singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
102 }
103
104 if (singleton) {
105 wins++;
106 x = ((PhaseGVN&)_igvn).makecon(t);
107 } else {
108 // We now call Identity to try to simplify the cloned node.
109 // Note that some Identity methods call phase->type(this).
110 // Make sure that the type array is big enough for
111 // our new node, even though we may throw the node away.
112 // (Note: This tweaking with igvn only works because x is a new node.)
113 _igvn.set_type(x, t);
114 // If x is a TypeNode, capture any more-precise type permanently into Node
115 // otherwise it will be not updated during igvn->transform since
116 // igvn->type(x) is set to x->Value() already.
117 x->raise_bottom_type(t);
118 if (x->Opcode() != Op_ShenandoahWriteBarrier) {
119 Node *y = x->Identity(&_igvn);
120 if (y != x) {
121 wins++;
122 x = y;
123 } else {
124 y = _igvn.hash_find(x);
125 if (y) {
126 wins++;
127 x = y;
128 } else {
129 // Else x is a new node we are keeping
130 // We do not need register_new_node_with_optimizer
131 // because set_type has already been called.
132 _igvn._worklist.push(x);
133 }
134 }
135 } else {
136 // wins++;
137 _igvn._worklist.push(x);
138 }
139 }
140 if (x != the_clone && the_clone != NULL)
141 _igvn.remove_dead_node(the_clone);
142 phi->set_req( i, x );
143 }
144 // Too few wins?
145 if (wins <= policy) {
146 _igvn.remove_dead_node(phi);
147 return NULL;
148 }
149
150 // Record Phi
151 register_new_node( phi, region );
152
153 for (uint i2 = 1; i2 < phi->req(); i2++) {
154 Node *x = phi->in(i2);
155 // If we commoned up the cloned 'x' with another existing Node,
156 // the existing Node picks up a new use. We need to make the
157 // existing Node occur higher up so it dominates its uses.
158 Node *old_ctrl;
186 (old_loop == NULL || !new_loop->is_member(old_loop))) {
187 // Take early control, later control will be recalculated
188 // during next iteration of loop optimizations.
189 new_ctrl = get_early_ctrl(x);
190 new_loop = get_loop(new_ctrl);
191 }
192 // Set new location
193 set_ctrl(x, new_ctrl);
194 // If changing loop bodies, see if we need to collect into new body
195 if (old_loop != new_loop) {
196 if (old_loop && !old_loop->_child)
197 old_loop->_body.yank(x);
198 if (!new_loop->_child)
199 new_loop->_body.push(x); // Collect body info
200 }
201 }
202
203 return phi;
204 }
205
206 void PhaseIdealLoop::split_mem_thru_phi(Node* n, Node* r, Node* phi) {
207 if (n->Opcode() == Op_ShenandoahWriteBarrier) {
208 #ifdef ASSERT
209 n->as_ShenandoahBarrier()->check_invariants();
210 #endif
211 if (n->has_out_with(Op_ShenandoahWBMemProj)) {
212 Node* old_mem_phi = n->in(ShenandoahBarrierNode::Memory);
213 assert(r->is_Region(), "need region to control phi");
214 assert(phi->is_Phi(), "expect phi");
215 Node* memphi = PhiNode::make(r, old_mem_phi, Type::MEMORY, C->alias_type(n->adr_type())->adr_type());
216 for (uint i = 1; i < r->req(); i++) {
217 Node* wb = phi->in(i);
218 if (wb->Opcode() == Op_ShenandoahWriteBarrier) {
219 assert(! wb->has_out_with(Op_ShenandoahWBMemProj), "new clone does not have mem proj");
220 Node* new_proj = new ShenandoahWBMemProjNode(wb);
221 register_new_node(new_proj, r->in(i));
222 memphi->set_req(i, new_proj);
223 } else {
224 if (old_mem_phi->is_Phi() && old_mem_phi->in(0) == r) {
225 memphi->set_req(i, old_mem_phi->in(i));
226 }
227 }
228 }
229 register_new_node(memphi, r);
230 Node* old_mem_out = n->find_out_with(Op_ShenandoahWBMemProj);
231 assert(old_mem_out != NULL, "expect memory projection");
232 _igvn.replace_node(old_mem_out, memphi);
233 }
234 assert(! n->has_out_with(Op_ShenandoahWBMemProj), "no more memory outs");
235 }
236 }
237
238 //------------------------------dominated_by------------------------------------
239 // Replace the dominated test with an obvious true or false. Place it on the
240 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the
241 // live path up to the dominating control.
242 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
243 #ifndef PRODUCT
244 if (VerifyLoopOptimizations && PrintOpto) tty->print_cr("dominating test");
245 #endif
246
247
248 // prevdom is the dominating projection of the dominating test.
249 assert( iff->is_If(), "" );
250 assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
251 int pop = prevdom->Opcode();
252 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
253 if (flip) {
254 if (pop == Op_IfTrue)
255 pop = Op_IfFalse;
256 else
257 pop = Op_IfTrue;
958 int policy = n_blk->req() >> 2;
959
960 // If the loop is a candidate for range check elimination,
961 // delay splitting through it's phi until a later loop optimization
962 if (n_blk->is_CountedLoop()) {
963 IdealLoopTree *lp = get_loop(n_blk);
964 if (lp && lp->_rce_candidate) {
965 return n;
966 }
967 }
968
969 // Use same limit as split_if_with_blocks_post
970 if( C->live_nodes() > 35000 ) return n; // Method too big
971
972 // Split 'n' through the merge point if it is profitable
973 Node *phi = split_thru_phi( n, n_blk, policy );
974 if (!phi) return n;
975
976 // Found a Phi to split thru!
977 // Replace 'n' with the new phi
978 split_mem_thru_phi(n, n_blk, phi);
979 _igvn.replace_node( n, phi );
980 // Moved a load around the loop, 'en-registering' something.
981 if (n_blk->is_Loop() && n->is_Load() &&
982 !phi->in(LoopNode::LoopBackControl)->is_Load())
983 C->set_major_progress();
984
985 // Moved a barrier around the loop, 'en-registering' something.
986 if (n_blk->is_Loop() && n->is_ShenandoahBarrier() &&
987 !phi->in(LoopNode::LoopBackControl)->is_ShenandoahBarrier())
988 C->set_major_progress();
989
990 return phi;
991 }
992
993 static bool merge_point_too_heavy(Compile* C, Node* region) {
994 // Bail out if the region and its phis have too many users.
995 int weight = 0;
996 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
997 weight += region->fast_out(i)->outcnt();
998 }
999 int nodes_left = C->max_node_limit() - C->live_nodes();
1000 if (weight * 8 > nodes_left) {
1001 #ifndef PRODUCT
1002 if (PrintOpto)
1003 tty->print_cr("*** Split-if bails out: %d nodes, region weight %d", C->unique(), weight);
1004 #endif
1005 return true;
1006 } else {
1007 return false;
1008 }
1009 }
1112 // for any input path not being in the same loop as n_ctrl. For
1113 // irreducible loops we cannot check for 'n_ctrl->is_Loop()'
1114 // because the alternative loop entry points won't be converted
1115 // into LoopNodes.
1116 IdealLoopTree *n_loop = get_loop(n_ctrl);
1117 for( uint j = 1; j < n_ctrl->req(); j++ )
1118 if( get_loop(n_ctrl->in(j)) != n_loop )
1119 return;
1120
1121 // Check for safety of the merge point.
1122 if( !merge_point_safe(n_ctrl) ) {
1123 return;
1124 }
1125
1126 // Split compare 'n' through the merge point if it is profitable
1127 Node *phi = split_thru_phi( n, n_ctrl, policy );
1128 if( !phi ) return;
1129
1130 // Found a Phi to split thru!
1131 // Replace 'n' with the new phi
1132 assert(n->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers yet");
1133 _igvn.replace_node( n, phi );
1134
1135 // Now split the bool up thru the phi
1136 assert(bol->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers yet");
1137 Node *bolphi = split_thru_phi( bol, n_ctrl, -1 );
1138 guarantee(bolphi != NULL, "null boolean phi node");
1139
1140 _igvn.replace_node( bol, bolphi );
1141 assert( iff->in(1) == bolphi, "" );
1142
1143 if( bolphi->Value(&_igvn)->singleton() )
1144 return;
1145
1146 // Conditional-move? Must split up now
1147 if( !iff->is_If() ) {
1148 assert(iff->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers yet");
1149 Node *cmovphi = split_thru_phi( iff, n_ctrl, -1 );
1150 _igvn.replace_node( iff, cmovphi );
1151 return;
1152 }
1153
1154 // Now split the IF
1155 do_split_if( iff );
1156 return;
1157 }
1158
1159 // Check for an IF ready to split; one that has its
1160 // condition codes input coming from a Phi at the block start.
1161 int n_op = n->Opcode();
1162
1163 // Check for an IF being dominated by another IF same test
1164 if (n_op == Op_If) {
1165 Node *bol = n->in(1);
1166 uint max = bol->outcnt();
1167 // Check for same test used more than once?
1168 if (max > 1 && bol->is_Bool()) {
1262 // Don't allow the control input to be a CFG splitting node.
1263 // Such nodes should only have ProjNodes as outs, e.g. IfNode
1264 // should only have IfTrueNode and IfFalseNode (4985384).
1265 x_ctrl = find_non_split_ctrl(x_ctrl);
1266 assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1267
1268 x->set_req(0, x_ctrl);
1269 }
1270 register_new_node(x, x_ctrl);
1271
1272 // Some institutional knowledge is needed here: 'x' is
1273 // yanked because if the optimizer runs GVN on it all the
1274 // cloned x's will common up and undo this optimization and
1275 // be forced back in the loop. This is annoying because it
1276 // makes +VerifyOpto report false-positives on progress. I
1277 // tried setting control edges on the x's to force them to
1278 // not combine, but the matching gets worried when it tries
1279 // to fold a StoreP and an AddP together (as part of an
1280 // address expression) and the AddP and StoreP have
1281 // different controls.
1282 if (!x->is_Load() && !x->is_DecodeNarrowPtr() && !x->is_ShenandoahBarrier()) _igvn._worklist.yank(x);
1283 }
1284 _igvn.remove_dead_node(n);
1285 }
1286 }
1287 }
1288 }
1289
1290 try_move_store_after_loop(n);
1291
1292 // Check for Opaque2's who's loop has disappeared - who's input is in the
1293 // same loop nest as their output. Remove 'em, they are no longer useful.
1294 if( n_op == Op_Opaque2 &&
1295 n->in(1) != NULL &&
1296 get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1297 _igvn.replace_node( n, n->in(1) );
1298 }
1299 }
1300
1301 //------------------------------split_if_with_blocks---------------------------
1302 // Check for aggressive application of 'split-if' optimization,
1535 }
1536 }
1537 #endif
1538
1539 CloneMap& cm = C->clone_map();
1540 Dict* dict = cm.dict();
1541 if (C->do_vector_loop()) {
1542 cm.set_clone_idx(cm.max_gen()+1);
1543 #ifndef PRODUCT
1544 if (PrintOpto) {
1545 tty->print_cr("PhaseIdealLoop::clone_loop: _clone_idx %d", cm.clone_idx());
1546 loop->dump_head();
1547 }
1548 #endif
1549 }
1550
1551 // Step 1: Clone the loop body. Make the old->new mapping.
1552 uint i;
1553 for( i = 0; i < loop->_body.size(); i++ ) {
1554 Node *old = loop->_body.at(i);
1555 #ifdef ASSERT
1556 if (old->Opcode() == Op_ShenandoahWriteBarrier) {
1557 Node* memproj = old->find_out_with(Op_ShenandoahWBMemProj);
1558 assert(memproj == NULL || (loop->is_member(get_loop(has_ctrl(memproj) ? get_ctrl(memproj) : memproj))), "WB's mem-proj must be in loop too");
1559 }
1560 if (old->Opcode() == Op_ShenandoahWBMemProj) {
1561 Node* wb = old->in(0);
1562 assert(loop->is_member(get_loop(has_ctrl(wb) ? get_ctrl(wb) : wb)), "WB must be in loop too");
1563 }
1564 #endif
1565 Node *nnn = old->clone();
1566 old_new.map( old->_idx, nnn );
1567 if (C->do_vector_loop()) {
1568 cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
1569 }
1570 _igvn.register_new_node_with_optimizer(nnn);
1571 }
1572
1573
1574 // Step 2: Fix the edges in the new body. If the old input is outside the
1575 // loop use it. If the old input is INside the loop, use the corresponding
1576 // new node instead.
1577 for( i = 0; i < loop->_body.size(); i++ ) {
1578 Node *old = loop->_body.at(i);
1579 Node *nnn = old_new[old->_idx];
1580 // Fix CFG/Loop controlling the new node
1581 if (has_ctrl(old)) {
1582 set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
1583 } else {
1584 set_loop(nnn, loop->_parent);
1735 : idom(prev);
1736 if( use->is_Phi() ) // Phi use is in prior block
1737 cfg = prev->in(idx); // NOT in block of Phi itself
1738 if (cfg->is_top()) { // Use is dead?
1739 _igvn.replace_input_of(use, idx, C->top());
1740 continue;
1741 }
1742
1743 while( !loop->is_member( get_loop( cfg ) ) ) {
1744 prev = cfg;
1745 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1746 }
1747 // If the use occurs after merging several exits from the loop, then
1748 // old value must have dominated all those exits. Since the same old
1749 // value was used on all those exits we did not need a Phi at this
1750 // merge point. NOW we do need a Phi here. Each loop exit value
1751 // is now merged with the peeled body exit; each exit gets its own
1752 // private Phi and those Phis need to be merged here.
1753 Node *phi;
1754 if( prev->is_Region() ) {
1755 if( idx == 0 && use->Opcode() != Op_ShenandoahWBMemProj) { // Updating control edge?
1756 phi = prev; // Just use existing control
1757 } else { // Else need a new Phi
1758 phi = PhiNode::make( prev, old );
1759 // Now recursively fix up the new uses of old!
1760 uint first = use->Opcode() != Op_ShenandoahWBMemProj ? 1 : 0;
1761 for( uint i = first; i < prev->req(); i++ ) {
1762 worklist.push(phi); // Onto worklist once for each 'old' input
1763 }
1764 }
1765 } else {
1766 // Get new RegionNode merging old and new loop exits
1767 prev = old_new[prev->_idx];
1768 assert( prev, "just made this in step 7" );
1769 if( idx == 0 && use->Opcode() != Op_ShenandoahWBMemProj) { // Updating control edge?
1770 phi = prev; // Just use existing control
1771 } else { // Else need a new Phi
1772 // Make a new Phi merging data values properly
1773 phi = PhiNode::make( prev, old );
1774 phi->set_req( 1, nnn );
1775 }
1776 }
1777 // If inserting a new Phi, check for prior hits
1778 if( idx != 0 ) {
1779 Node *hit = _igvn.hash_find_insert(phi);
1780 if( hit == NULL ) {
1781 _igvn.register_new_node_with_optimizer(phi); // Register new phi
1782 } else { // or
1783 // Remove the new phi from the graph and use the hit
1784 _igvn.remove_dead_node(phi);
1785 phi = hit; // Use existing phi
1786 }
1787 set_ctrl(phi, prev);
1788 }
1789 // Make 'use' use the Phi instead of the old loop body exit value
2232
2233 //------------------------------ has_use_internal_to_set -------------------------------------
2234 // Has use internal to the vector set (ie. not in a phi at the loop head)
2235 bool PhaseIdealLoop::has_use_internal_to_set( Node* n, VectorSet& vset, IdealLoopTree *loop ) {
2236 Node* head = loop->_head;
2237 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2238 Node* use = n->fast_out(j);
2239 if (vset.test(use->_idx) && !(use->is_Phi() && use->in(0) == head)) {
2240 return true;
2241 }
2242 }
2243 return false;
2244 }
2245
2246
2247 //------------------------------ clone_for_use_outside_loop -------------------------------------
2248 // clone "n" for uses that are outside of loop
2249 int PhaseIdealLoop::clone_for_use_outside_loop( IdealLoopTree *loop, Node* n, Node_List& worklist ) {
2250 int cloned = 0;
2251 assert(worklist.size() == 0, "should be empty");
2252 assert(n->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers yet");
2253 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2254 Node* use = n->fast_out(j);
2255 if( !loop->is_member(get_loop(has_ctrl(use) ? get_ctrl(use) : use)) ) {
2256 worklist.push(use);
2257 }
2258 }
2259 while( worklist.size() ) {
2260 Node *use = worklist.pop();
2261 if (!has_node(use) || use->in(0) == C->top()) continue;
2262 uint j;
2263 for (j = 0; j < use->req(); j++) {
2264 if (use->in(j) == n) break;
2265 }
2266 assert(j < use->req(), "must be there");
2267
2268 // clone "n" and insert it between the inputs of "n" and the use outside the loop
2269 assert(n->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers");
2270 Node* n_clone = n->clone();
2271 _igvn.replace_input_of(use, j, n_clone);
2272 cloned++;
2273 Node* use_c;
2274 if (!use->is_Phi()) {
2275 use_c = has_ctrl(use) ? get_ctrl(use) : use->in(0);
2276 } else {
2277 // Use in a phi is considered a use in the associated predecessor block
2278 use_c = use->in(0)->in(j);
2279 }
2280 set_ctrl(n_clone, use_c);
2281 assert(!loop->is_member(get_loop(use_c)), "should be outside loop");
2282 get_loop(use_c)->_body.push(n_clone);
2283 _igvn.register_new_node_with_optimizer(n_clone);
2284 #if !defined(PRODUCT)
2285 if (TracePartialPeeling) {
2286 tty->print_cr("loop exit cloning old: %d new: %d newbb: %d", n->_idx, n_clone->_idx, get_ctrl(n_clone)->_idx);
2287 }
2288 #endif
2289 }
2296 // If these def-uses occur in separate blocks, the code generator
2297 // marks the method as not compilable. For example, if a "BoolNode"
2298 // is in a different basic block than the "IfNode" that uses it, then
2299 // the compilation is aborted in the code generator.
2300 void PhaseIdealLoop::clone_for_special_use_inside_loop( IdealLoopTree *loop, Node* n,
2301 VectorSet& not_peel, Node_List& sink_list, Node_List& worklist ) {
2302 if (n->is_Phi() || n->is_Load()) {
2303 return;
2304 }
2305 assert(worklist.size() == 0, "should be empty");
2306 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2307 Node* use = n->fast_out(j);
2308 if ( not_peel.test(use->_idx) &&
2309 (use->is_If() || use->is_CMove() || use->is_Bool()) &&
2310 use->in(1) == n) {
2311 worklist.push(use);
2312 }
2313 }
2314 if (worklist.size() > 0) {
2315 // clone "n" and insert it between inputs of "n" and the use
2316 assert(n->Opcode() != Op_ShenandoahWriteBarrier, "not with write barriers");
2317 Node* n_clone = n->clone();
2318 loop->_body.push(n_clone);
2319 _igvn.register_new_node_with_optimizer(n_clone);
2320 set_ctrl(n_clone, get_ctrl(n));
2321 sink_list.push(n_clone);
2322 not_peel <<= n_clone->_idx; // add n_clone to not_peel set.
2323 #if !defined(PRODUCT)
2324 if (TracePartialPeeling) {
2325 tty->print_cr("special not_peeled cloning old: %d new: %d", n->_idx, n_clone->_idx);
2326 }
2327 #endif
2328 while( worklist.size() ) {
2329 Node *use = worklist.pop();
2330 _igvn.rehash_node_delayed(use);
2331 for (uint j = 1; j < use->req(); j++) {
2332 if (use->in(j) == n) {
2333 use->set_req(j, n_clone);
2334 }
2335 }
2336 }
|