1 /*
2 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "opto/addnode.hpp"
27 #include "opto/connode.hpp"
28 #include "opto/convertnode.hpp"
29 #include "opto/movenode.hpp"
30 #include "opto/phaseX.hpp"
31 #include "opto/subnode.hpp"
32
33 //=============================================================================
34 /*
35 The major change is for CMoveP and StrComp. They have related but slightly
36 different problems. They both take in TWO oops which are both null-checked
37 independently before the using Node. After CCP removes the CastPP's they need
38 to pick up the guarding test edge - in this case TWO control edges. I tried
39 various solutions, all have problems:
40
41 (1) Do nothing. This leads to a bug where we hoist a Load from a CMoveP or a
42 StrComp above a guarding null check. I've seen both cases in normal -Xcomp
43 testing.
44
45 (2) Plug the control edge from 1 of the 2 oops in. Apparent problem here is
46 to figure out which test post-dominates. The real problem is that it doesn't
47 matter which one you pick. After you pick up, the dominating-test elider in
48 IGVN can remove the test and allow you to hoist up to the dominating test on
49 the chosen oop bypassing the test on the not-chosen oop. Seen in testing.
50 Oops.
51
52 (3) Leave the CastPP's in. This makes the graph more accurate in some sense;
53 we get to keep around the knowledge that an oop is not-null after some test.
54 Alas, the CastPP's interfere with GVN (some values are the regular oop, some
55 are the CastPP of the oop, all merge at Phi's which cannot collapse, etc).
56 This cost us 10% on SpecJVM, even when I removed some of the more trivial
57 cases in the optimizer. Removing more useless Phi's started allowing Loads to
58 illegally float above null checks. I gave up on this approach.
59
60 (4) Add BOTH control edges to both tests. Alas, too much code knows that
61 control edges are in slot-zero ONLY. Many quick asserts fail; no way to do
62 this one. Note that I really want to allow the CMoveP to float and add both
63 control edges to the dependent Load op - meaning I can select early but I
64 cannot Load until I pass both tests.
65
66 (5) Do not hoist CMoveP and StrComp. To this end I added the v-call
67 depends_only_on_test(). No obvious performance loss on Spec, but we are
68 clearly conservative on CMoveP (also so on StrComp but that's unlikely to
69 matter ever).
70
71 */
72
73
74 //------------------------------Ideal------------------------------------------
75 // Return a node which is more "ideal" than the current node.
76 // Move constants to the right.
77 Node *CMoveNode::Ideal(PhaseGVN *phase, bool can_reshape) {
78 if( in(0) && remove_dead_region(phase, can_reshape) ) return this;
79 // Don't bother trying to transform a dead node
80 if( in(0) && in(0)->is_top() ) return NULL;
81 assert( !phase->eqv(in(Condition), this) &&
82 !phase->eqv(in(IfFalse), this) &&
83 !phase->eqv(in(IfTrue), this), "dead loop in CMoveNode::Ideal" );
84 if( phase->type(in(Condition)) == Type::TOP )
85 return NULL; // return NULL when Condition is dead
86
87 if( in(IfFalse)->is_Con() && !in(IfTrue)->is_Con() ) {
88 if( in(Condition)->is_Bool() ) {
89 BoolNode* b = in(Condition)->as_Bool();
90 BoolNode* b2 = b->negate(phase);
91 return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);
92 }
93 }
94 return NULL;
95 }
96
97 //------------------------------is_cmove_id------------------------------------
98 // Helper function to check for CMOVE identity. Shared with PhiNode::Identity
99 Node *CMoveNode::is_cmove_id( PhaseTransform *phase, Node *cmp, Node *t, Node *f, BoolNode *b ) {
100 // Check for Cmp'ing and CMove'ing same values
101 if( (phase->eqv(cmp->in(1),f) &&
102 phase->eqv(cmp->in(2),t)) ||
103 // Swapped Cmp is OK
104 (phase->eqv(cmp->in(2),f) &&
105 phase->eqv(cmp->in(1),t)) ) {
106 // Give up this identity check for floating points because it may choose incorrect
107 // value around 0.0 and -0.0
108 if ( cmp->Opcode()==Op_CmpF || cmp->Opcode()==Op_CmpD )
109 return NULL;
110 // Check for "(t==f)?t:f;" and replace with "f"
111 if( b->_test._test == BoolTest::eq )
112 return f;
113 // Allow the inverted case as well
114 // Check for "(t!=f)?t:f;" and replace with "t"
115 if( b->_test._test == BoolTest::ne )
116 return t;
117 }
118 return NULL;
119 }
120
121 //------------------------------Identity---------------------------------------
122 // Conditional-move is an identity if both inputs are the same, or the test
123 // true or false.
124 Node* CMoveNode::Identity(PhaseGVN* phase) {
125 if( phase->eqv(in(IfFalse),in(IfTrue)) ) // C-moving identical inputs?
126 return in(IfFalse); // Then it doesn't matter
127 if( phase->type(in(Condition)) == TypeInt::ZERO )
128 return in(IfFalse); // Always pick left(false) input
129 if( phase->type(in(Condition)) == TypeInt::ONE )
130 return in(IfTrue); // Always pick right(true) input
131
132 // Check for CMove'ing a constant after comparing against the constant.
133 // Happens all the time now, since if we compare equality vs a constant in
134 // the parser, we "know" the variable is constant on one path and we force
135 // it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
136 // conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more
137 // general in that we don't need constants.
138 if( in(Condition)->is_Bool() ) {
139 BoolNode *b = in(Condition)->as_Bool();
140 Node *cmp = b->in(1);
141 if( cmp->is_Cmp() ) {
142 Node *id = is_cmove_id( phase, cmp, in(IfTrue), in(IfFalse), b );
143 if( id ) return id;
144 }
145 }
146
147 return this;
148 }
149
150 //------------------------------Value------------------------------------------
151 // Result is the meet of inputs
152 const Type* CMoveNode::Value(PhaseGVN* phase) const {
153 if (phase->type(in(Condition)) == Type::TOP) {
154 return Type::TOP;
155 }
156 const Type* t = phase->type(in(IfFalse))->meet_speculative(phase->type(in(IfTrue)));
157 return t->filter(_type);
158 }
159
160 //------------------------------make-------------------------------------------
161 // Make a correctly-flavored CMove. Since _type is directly determined
162 // from the inputs we do not need to specify it here.
163 CMoveNode *CMoveNode::make(Node *c, Node *bol, Node *left, Node *right, const Type *t) {
164 switch( t->basic_type() ) {
165 case T_INT: return new CMoveINode( bol, left, right, t->is_int() );
166 case T_FLOAT: return new CMoveFNode( bol, left, right, t );
167 case T_DOUBLE: return new CMoveDNode( bol, left, right, t );
168 case T_LONG: return new CMoveLNode( bol, left, right, t->is_long() );
169 case T_OBJECT: return new CMovePNode( c, bol, left, right, t->is_oopptr() );
170 case T_ADDRESS: return new CMovePNode( c, bol, left, right, t->is_ptr() );
171 case T_NARROWOOP: return new CMoveNNode( c, bol, left, right, t );
172 default:
173 ShouldNotReachHere();
174 return NULL;
175 }
176 }
177
178 //=============================================================================
179 //------------------------------Ideal------------------------------------------
180 // Return a node which is more "ideal" than the current node.
181 // Check for conversions to boolean
182 Node *CMoveINode::Ideal(PhaseGVN *phase, bool can_reshape) {
183 // Try generic ideal's first
184 Node *x = CMoveNode::Ideal(phase, can_reshape);
185 if( x ) return x;
186
187 // If zero is on the left (false-case, no-move-case) it must mean another
188 // constant is on the right (otherwise the shared CMove::Ideal code would
189 // have moved the constant to the right). This situation is bad for Intel
190 // and a don't-care for Sparc. It's bad for Intel because the zero has to
191 // be manifested in a register with a XOR which kills flags, which are live
192 // on input to the CMoveI, leading to a situation which causes excessive
193 // spilling on Intel. For Sparc, if the zero in on the left the Sparc will
194 // zero a register via G0 and conditionally-move the other constant. If the
195 // zero is on the right, the Sparc will load the first constant with a
196 // 13-bit set-lo and conditionally move G0. See bug 4677505.
197 if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {
198 if( in(Condition)->is_Bool() ) {
199 BoolNode* b = in(Condition)->as_Bool();
200 BoolNode* b2 = b->negate(phase);
201 return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);
202 }
203 }
204
205 // Now check for booleans
206 int flip = 0;
207
208 // Check for picking from zero/one
209 if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {
210 flip = 1 - flip;
211 } else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {
212 } else return NULL;
213
214 // Check for eq/ne test
215 if( !in(1)->is_Bool() ) return NULL;
216 BoolNode *bol = in(1)->as_Bool();
217 if( bol->_test._test == BoolTest::eq ) {
218 } else if( bol->_test._test == BoolTest::ne ) {
219 flip = 1-flip;
220 } else return NULL;
221
222 // Check for vs 0 or 1
223 if( !bol->in(1)->is_Cmp() ) return NULL;
224 const CmpNode *cmp = bol->in(1)->as_Cmp();
225 if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {
226 } else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {
227 // Allow cmp-vs-1 if the other input is bounded by 0-1
228 if( phase->type(cmp->in(1)) != TypeInt::BOOL )
229 return NULL;
230 flip = 1 - flip;
231 } else return NULL;
232
233 // Convert to a bool (flipped)
234 // Build int->bool conversion
235 if (PrintOpto) { tty->print_cr("CMOV to I2B"); }
236 Node *n = new Conv2BNode( cmp->in(1) );
237 if( flip )
238 n = new XorINode( phase->transform(n), phase->intcon(1) );
239
240 return n;
241 }
242
243 //=============================================================================
244 //------------------------------Ideal------------------------------------------
245 // Return a node which is more "ideal" than the current node.
246 // Check for absolute value
247 Node *CMoveFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
248 // Try generic ideal's first
249 Node *x = CMoveNode::Ideal(phase, can_reshape);
250 if( x ) return x;
251
252 int cmp_zero_idx = 0; // Index of compare input where to look for zero
253 int phi_x_idx = 0; // Index of phi input where to find naked x
254
255 // Find the Bool
256 if( !in(1)->is_Bool() ) return NULL;
257 BoolNode *bol = in(1)->as_Bool();
258 // Check bool sense
259 switch( bol->_test._test ) {
260 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;
261 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
262 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;
263 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
264 default: return NULL; break;
265 }
266
267 // Find zero input of CmpF; the other input is being abs'd
268 Node *cmpf = bol->in(1);
269 if( cmpf->Opcode() != Op_CmpF ) return NULL;
270 Node *X = NULL;
271 bool flip = false;
272 if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {
273 X = cmpf->in(3 - cmp_zero_idx);
274 } else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {
275 // The test is inverted, we should invert the result...
276 X = cmpf->in(cmp_zero_idx);
277 flip = true;
278 } else {
279 return NULL;
280 }
281
282 // If X is found on the appropriate phi input, find the subtract on the other
283 if( X != in(phi_x_idx) ) return NULL;
284 int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
285 Node *sub = in(phi_sub_idx);
286
287 // Allow only SubF(0,X) and fail out for all others; NegF is not OK
288 if( sub->Opcode() != Op_SubF ||
289 sub->in(2) != X ||
290 phase->type(sub->in(1)) != TypeF::ZERO ) return NULL;
291
292 Node *abs = new AbsFNode( X );
293 if( flip )
294 abs = new SubFNode(sub->in(1), phase->transform(abs));
295
296 return abs;
297 }
298
299 //=============================================================================
300 //------------------------------Ideal------------------------------------------
301 // Return a node which is more "ideal" than the current node.
302 // Check for absolute value
303 Node *CMoveDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
304 // Try generic ideal's first
305 Node *x = CMoveNode::Ideal(phase, can_reshape);
306 if( x ) return x;
307
308 int cmp_zero_idx = 0; // Index of compare input where to look for zero
309 int phi_x_idx = 0; // Index of phi input where to find naked x
310
311 // Find the Bool
312 if( !in(1)->is_Bool() ) return NULL;
313 BoolNode *bol = in(1)->as_Bool();
314 // Check bool sense
315 switch( bol->_test._test ) {
316 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;
317 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
318 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;
319 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
320 default: return NULL; break;
321 }
322
323 // Find zero input of CmpD; the other input is being abs'd
324 Node *cmpd = bol->in(1);
325 if( cmpd->Opcode() != Op_CmpD ) return NULL;
326 Node *X = NULL;
327 bool flip = false;
328 if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {
329 X = cmpd->in(3 - cmp_zero_idx);
330 } else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {
331 // The test is inverted, we should invert the result...
332 X = cmpd->in(cmp_zero_idx);
333 flip = true;
334 } else {
335 return NULL;
336 }
337
338 // If X is found on the appropriate phi input, find the subtract on the other
339 if( X != in(phi_x_idx) ) return NULL;
340 int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
341 Node *sub = in(phi_sub_idx);
342
343 // Allow only SubD(0,X) and fail out for all others; NegD is not OK
344 if( sub->Opcode() != Op_SubD ||
345 sub->in(2) != X ||
346 phase->type(sub->in(1)) != TypeD::ZERO ) return NULL;
347
348 Node *abs = new AbsDNode( X );
349 if( flip )
350 abs = new SubDNode(sub->in(1), phase->transform(abs));
351
352 return abs;
353 }
354
355 //------------------------------Value------------------------------------------
356 const Type* MoveL2DNode::Value(PhaseGVN* phase) const {
357 const Type *t = phase->type( in(1) );
358 if( t == Type::TOP ) return Type::TOP;
359 const TypeLong *tl = t->is_long();
360 if( !tl->is_con() ) return bottom_type();
361 JavaValue v;
362 v.set_jlong(tl->get_con());
363 return TypeD::make( v.get_jdouble() );
364 }
365
366 //------------------------------Identity----------------------------------------
367 Node* MoveL2DNode::Identity(PhaseGVN* phase) {
368 if (in(1)->Opcode() == Op_MoveD2L) {
369 return in(1)->in(1);
370 }
371 return this;
372 }
373
374 //------------------------------Value------------------------------------------
375 const Type* MoveI2FNode::Value(PhaseGVN* phase) const {
376 const Type *t = phase->type( in(1) );
377 if( t == Type::TOP ) return Type::TOP;
378 const TypeInt *ti = t->is_int();
379 if( !ti->is_con() ) return bottom_type();
380 JavaValue v;
381 v.set_jint(ti->get_con());
382 return TypeF::make( v.get_jfloat() );
383 }
384
385 //------------------------------Identity----------------------------------------
386 Node* MoveI2FNode::Identity(PhaseGVN* phase) {
387 if (in(1)->Opcode() == Op_MoveF2I) {
388 return in(1)->in(1);
389 }
390 return this;
391 }
392
393 //------------------------------Value------------------------------------------
394 const Type* MoveF2INode::Value(PhaseGVN* phase) const {
395 const Type *t = phase->type( in(1) );
396 if( t == Type::TOP ) return Type::TOP;
397 if( t == Type::FLOAT ) return TypeInt::INT;
398 const TypeF *tf = t->is_float_constant();
399 JavaValue v;
400 v.set_jfloat(tf->getf());
401 return TypeInt::make( v.get_jint() );
402 }
403
404 //------------------------------Identity----------------------------------------
405 Node* MoveF2INode::Identity(PhaseGVN* phase) {
406 if (in(1)->Opcode() == Op_MoveI2F) {
407 return in(1)->in(1);
408 }
409 return this;
410 }
411
412 //------------------------------Value------------------------------------------
413 const Type* MoveD2LNode::Value(PhaseGVN* phase) const {
414 const Type *t = phase->type( in(1) );
415 if( t == Type::TOP ) return Type::TOP;
416 if( t == Type::DOUBLE ) return TypeLong::LONG;
417 const TypeD *td = t->is_double_constant();
418 JavaValue v;
419 v.set_jdouble(td->getd());
420 return TypeLong::make( v.get_jlong() );
421 }
422
423 //------------------------------Identity----------------------------------------
424 Node* MoveD2LNode::Identity(PhaseGVN* phase) {
425 if (in(1)->Opcode() == Op_MoveL2D) {
426 return in(1)->in(1);
427 }
428 return this;
429 }
430
431 #ifndef PRODUCT
432 //----------------------------BinaryNode---------------------------------------
433 // The set of related nodes for a BinaryNode is all data inputs and all outputs
434 // till level 2 (i.e., one beyond the associated CMoveNode). In compact mode,
435 // it's the inputs till level 1 and the outputs till level 2.
436 void BinaryNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
437 if (compact) {
438 this->collect_nodes(in_rel, 1, false, true);
439 } else {
440 this->collect_nodes_in_all_data(in_rel, false);
441 }
442 this->collect_nodes(out_rel, -2, false, false);
443 }
444 #endif