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.
77Node *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
99Node *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.
124Node* 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
152const Type* CMoveNode::Value(PhaseGVN* phase) const {
153 if( phase->type(in(Condition)) == Type::TOP )
154 return Type::TOP;
155 return phase->type(in(IfFalse))->meet_speculative(phase->type(in(IfTrue)));
156}
157
158//------------------------------make-------------------------------------------
159// Make a correctly-flavored CMove. Since _type is directly determined
160// from the inputs we do not need to specify it here.
161CMoveNode *CMoveNode::make(Node *c, Node *bol, Node *left, Node *right, const Type *t) {
162 switch( t->basic_type() ) {
163 case T_INT: return new CMoveINode( bol, left, right, t->is_int() );
164 case T_FLOAT: return new CMoveFNode( bol, left, right, t );
165 case T_DOUBLE: return new CMoveDNode( bol, left, right, t );
166 case T_LONG: return new CMoveLNode( bol, left, right, t->is_long() );
167 case T_OBJECT: return new CMovePNode( c, bol, left, right, t->is_oopptr() );
168 case T_ADDRESS: return new CMovePNode( c, bol, left, right, t->is_ptr() );
169 case T_NARROWOOP: return new CMoveNNode( c, bol, left, right, t );
170 default:
171 ShouldNotReachHere();
172 return NULL;
173 }
174}
175
176//=============================================================================
177//------------------------------Ideal------------------------------------------
178// Return a node which is more "ideal" than the current node.
179// Check for conversions to boolean
180Node *CMoveINode::Ideal(PhaseGVN *phase, bool can_reshape) {
181 // Try generic ideal's first
182 Node *x = CMoveNode::Ideal(phase, can_reshape);
183 if( x ) return x;
184
185 // If zero is on the left (false-case, no-move-case) it must mean another
186 // constant is on the right (otherwise the shared CMove::Ideal code would
187 // have moved the constant to the right). This situation is bad for Intel
188 // and a don't-care for Sparc. It's bad for Intel because the zero has to
189 // be manifested in a register with a XOR which kills flags, which are live
190 // on input to the CMoveI, leading to a situation which causes excessive
191 // spilling on Intel. For Sparc, if the zero in on the left the Sparc will
192 // zero a register via G0 and conditionally-move the other constant. If the
193 // zero is on the right, the Sparc will load the first constant with a
194 // 13-bit set-lo and conditionally move G0. See bug 4677505.
195 if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {
196 if( in(Condition)->is_Bool() ) {
197 BoolNode* b = in(Condition)->as_Bool();
198 BoolNode* b2 = b->negate(phase);
199 return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);
200 }
201 }
202
203 // Now check for booleans
204 int flip = 0;
205
206 // Check for picking from zero/one
207 if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {
208 flip = 1 - flip;
209 } else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {
210 } else return NULL;
211
212 // Check for eq/ne test
213 if( !in(1)->is_Bool() ) return NULL;
214 BoolNode *bol = in(1)->as_Bool();
215 if( bol->_test._test == BoolTest::eq ) {
216 } else if( bol->_test._test == BoolTest::ne ) {
217 flip = 1-flip;
218 } else return NULL;
219
220 // Check for vs 0 or 1
221 if( !bol->in(1)->is_Cmp() ) return NULL;
222 const CmpNode *cmp = bol->in(1)->as_Cmp();
223 if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {
224 } else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {
225 // Allow cmp-vs-1 if the other input is bounded by 0-1
226 if( phase->type(cmp->in(1)) != TypeInt::BOOL )
227 return NULL;
228 flip = 1 - flip;
229 } else return NULL;
230
231 // Convert to a bool (flipped)
232 // Build int->bool conversion
233 if (PrintOpto) { tty->print_cr("CMOV to I2B"); }
234 Node *n = new Conv2BNode( cmp->in(1) );
235 if( flip )
236 n = new XorINode( phase->transform(n), phase->intcon(1) );
237
238 return n;
239}
240
241//=============================================================================
242//------------------------------Ideal------------------------------------------
243// Return a node which is more "ideal" than the current node.
244// Check for absolute value
245Node *CMoveFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
246 // Try generic ideal's first
247 Node *x = CMoveNode::Ideal(phase, can_reshape);
248 if( x ) return x;
249
250 int cmp_zero_idx = 0; // Index of compare input where to look for zero
251 int phi_x_idx = 0; // Index of phi input where to find naked x
252
253 // Find the Bool
254 if( !in(1)->is_Bool() ) return NULL;
255 BoolNode *bol = in(1)->as_Bool();
256 // Check bool sense
257 switch( bol->_test._test ) {
258 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;
259 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
260 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;
261 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
262 default: return NULL; break;
263 }
264
265 // Find zero input of CmpF; the other input is being abs'd
266 Node *cmpf = bol->in(1);
267 if( cmpf->Opcode() != Op_CmpF ) return NULL;
268 Node *X = NULL;
269 bool flip = false;
270 if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {
271 X = cmpf->in(3 - cmp_zero_idx);
272 } else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {
273 // The test is inverted, we should invert the result...
274 X = cmpf->in(cmp_zero_idx);
275 flip = true;
276 } else {
277 return NULL;
278 }
279
280 // If X is found on the appropriate phi input, find the subtract on the other
281 if( X != in(phi_x_idx) ) return NULL;
282 int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
283 Node *sub = in(phi_sub_idx);
284
285 // Allow only SubF(0,X) and fail out for all others; NegF is not OK
286 if( sub->Opcode() != Op_SubF ||
287 sub->in(2) != X ||
288 phase->type(sub->in(1)) != TypeF::ZERO ) return NULL;
289
290 Node *abs = new AbsFNode( X );
291 if( flip )
292 abs = new SubFNode(sub->in(1), phase->transform(abs));
293
294 return abs;
295}
296
297//=============================================================================
298//------------------------------Ideal------------------------------------------
299// Return a node which is more "ideal" than the current node.
300// Check for absolute value
301Node *CMoveDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
302 // Try generic ideal's first
303 Node *x = CMoveNode::Ideal(phase, can_reshape);
304 if( x ) return x;
305
306 int cmp_zero_idx = 0; // Index of compare input where to look for zero
307 int phi_x_idx = 0; // Index of phi input where to find naked x
308
309 // Find the Bool
310 if( !in(1)->is_Bool() ) return NULL;
311 BoolNode *bol = in(1)->as_Bool();
312 // Check bool sense
313 switch( bol->_test._test ) {
314 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;
315 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
316 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;
317 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
318 default: return NULL; break;
319 }
320
321 // Find zero input of CmpD; the other input is being abs'd
322 Node *cmpd = bol->in(1);
323 if( cmpd->Opcode() != Op_CmpD ) return NULL;
324 Node *X = NULL;
325 bool flip = false;
326 if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {
327 X = cmpd->in(3 - cmp_zero_idx);
328 } else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {
329 // The test is inverted, we should invert the result...
330 X = cmpd->in(cmp_zero_idx);
331 flip = true;
332 } else {
333 return NULL;
334 }
335
336 // If X is found on the appropriate phi input, find the subtract on the other
337 if( X != in(phi_x_idx) ) return NULL;
338 int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
339 Node *sub = in(phi_sub_idx);
340
341 // Allow only SubD(0,X) and fail out for all others; NegD is not OK
342 if( sub->Opcode() != Op_SubD ||
343 sub->in(2) != X ||
344 phase->type(sub->in(1)) != TypeD::ZERO ) return NULL;
345
346 Node *abs = new AbsDNode( X );
347 if( flip )
348 abs = new SubDNode(sub->in(1), phase->transform(abs));
349
350 return abs;
351}
352
353//------------------------------Value------------------------------------------
354const Type* MoveL2DNode::Value(PhaseGVN* phase) const {
355 const Type *t = phase->type( in(1) );
356 if( t == Type::TOP ) return Type::TOP;
357 const TypeLong *tl = t->is_long();
358 if( !tl->is_con() ) return bottom_type();
359 JavaValue v;
360 v.set_jlong(tl->get_con());
361 return TypeD::make( v.get_jdouble() );
362}
363
364//------------------------------Value------------------------------------------
365const Type* MoveI2FNode::Value(PhaseGVN* phase) const {
366 const Type *t = phase->type( in(1) );
367 if( t == Type::TOP ) return Type::TOP;
368 const TypeInt *ti = t->is_int();
369 if( !ti->is_con() ) return bottom_type();
370 JavaValue v;
371 v.set_jint(ti->get_con());
372 return TypeF::make( v.get_jfloat() );
373}
374
375//------------------------------Value------------------------------------------
376const Type* MoveF2INode::Value(PhaseGVN* phase) const {
377 const Type *t = phase->type( in(1) );
378 if( t == Type::TOP ) return Type::TOP;
379 if( t == Type::FLOAT ) return TypeInt::INT;
380 const TypeF *tf = t->is_float_constant();
381 JavaValue v;
382 v.set_jfloat(tf->getf());
383 return TypeInt::make( v.get_jint() );
384}
385
386//------------------------------Value------------------------------------------
387const Type* MoveD2LNode::Value(PhaseGVN* phase) const {
388 const Type *t = phase->type( in(1) );
389 if( t == Type::TOP ) return Type::TOP;
390 if( t == Type::DOUBLE ) return TypeLong::LONG;
391 const TypeD *td = t->is_double_constant();
392 JavaValue v;
393 v.set_jdouble(td->getd());
394 return TypeLong::make( v.get_jlong() );
395}
396
397#ifndef PRODUCT
398//----------------------------BinaryNode---------------------------------------
399// The set of related nodes for a BinaryNode is all data inputs and all outputs
400// till level 2 (i.e., one beyond the associated CMoveNode). In compact mode,
401// it's the inputs till level 1 and the outputs till level 2.
402void BinaryNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
403 if (compact) {
404 this->collect_nodes(in_rel, 1, false, true);
405 } else {
406 this->collect_nodes_in_all_data(in_rel, false);
407 }
408 this->collect_nodes(out_rel, -2, false, false);
409}
410#endif
411