1 /*
2 * Copyright (c) 1997, 2020, 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 "memory/allocation.inline.hpp"
27 #include "opto/addnode.hpp"
28 #include "opto/connode.hpp"
29 #include "opto/convertnode.hpp"
30 #include "opto/memnode.hpp"
31 #include "opto/mulnode.hpp"
32 #include "opto/phaseX.hpp"
33 #include "opto/subnode.hpp"
34 #include "utilities/powerOfTwo.hpp"
35
36 // Portions of code courtesy of Clifford Click
37
38
39 //=============================================================================
40 //------------------------------hash-------------------------------------------
41 // Hash function over MulNodes. Needs to be commutative; i.e., I swap
42 // (commute) inputs to MulNodes willy-nilly so the hash function must return
43 // the same value in the presence of edge swapping.
hash() const44 uint MulNode::hash() const {
45 return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode();
46 }
47
48 //------------------------------Identity---------------------------------------
49 // Multiplying a one preserves the other argument
Identity(PhaseGVN * phase)50 Node* MulNode::Identity(PhaseGVN* phase) {
51 const Type *one = mul_id(); // The multiplicative identity
52 if( phase->type( in(1) )->higher_equal( one ) ) return in(2);
53 if( phase->type( in(2) )->higher_equal( one ) ) return in(1);
54
55 return this;
56 }
57
58 //------------------------------Ideal------------------------------------------
59 // We also canonicalize the Node, moving constants to the right input,
60 // and flatten expressions (so that 1+x+2 becomes x+3).
Ideal(PhaseGVN * phase,bool can_reshape)61 Node *MulNode::Ideal(PhaseGVN *phase, bool can_reshape) {
62 const Type *t1 = phase->type( in(1) );
63 const Type *t2 = phase->type( in(2) );
64 Node *progress = NULL; // Progress flag
65 // We are OK if right is a constant, or right is a load and
66 // left is a non-constant.
67 if( !(t2->singleton() ||
68 (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) {
69 if( t1->singleton() || // Left input is a constant?
70 // Otherwise, sort inputs (commutativity) to help value numbering.
71 (in(1)->_idx > in(2)->_idx) ) {
72 swap_edges(1, 2);
73 const Type *t = t1;
74 t1 = t2;
75 t2 = t;
76 progress = this; // Made progress
77 }
78 }
79
80 // If the right input is a constant, and the left input is a product of a
81 // constant, flatten the expression tree.
82 uint op = Opcode();
83 if( t2->singleton() && // Right input is a constant?
84 op != Op_MulF && // Float & double cannot reassociate
85 op != Op_MulD ) {
86 if( t2 == Type::TOP ) return NULL;
87 Node *mul1 = in(1);
88 #ifdef ASSERT
89 // Check for dead loop
90 int op1 = mul1->Opcode();
91 if( phase->eqv( mul1, this ) || phase->eqv( in(2), this ) ||
92 ( ( op1 == mul_opcode() || op1 == add_opcode() ) &&
93 ( phase->eqv( mul1->in(1), this ) || phase->eqv( mul1->in(2), this ) ||
94 phase->eqv( mul1->in(1), mul1 ) || phase->eqv( mul1->in(2), mul1 ) ) ) )
95 assert(false, "dead loop in MulNode::Ideal");
96 #endif
97
98 if( mul1->Opcode() == mul_opcode() ) { // Left input is a multiply?
99 // Mul of a constant?
100 const Type *t12 = phase->type( mul1->in(2) );
101 if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant?
102 // Compute new constant; check for overflow
103 const Type *tcon01 = ((MulNode*)mul1)->mul_ring(t2,t12);
104 if( tcon01->singleton() ) {
105 // The Mul of the flattened expression
106 set_req(1, mul1->in(1));
107 set_req(2, phase->makecon( tcon01 ));
108 t2 = tcon01;
109 progress = this; // Made progress
110 }
111 }
112 }
113 // If the right input is a constant, and the left input is an add of a
114 // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0
115 const Node *add1 = in(1);
116 if( add1->Opcode() == add_opcode() ) { // Left input is an add?
117 // Add of a constant?
118 const Type *t12 = phase->type( add1->in(2) );
119 if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant?
120 assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" );
121 // Compute new constant; check for overflow
122 const Type *tcon01 = mul_ring(t2,t12);
123 if( tcon01->singleton() ) {
124
125 // Convert (X+con1)*con0 into X*con0
126 Node *mul = clone(); // mul = ()*con0
127 mul->set_req(1,add1->in(1)); // mul = X*con0
128 mul = phase->transform(mul);
129
130 Node *add2 = add1->clone();
131 add2->set_req(1, mul); // X*con0 + con0*con1
132 add2->set_req(2, phase->makecon(tcon01) );
133 progress = add2;
134 }
135 }
136 } // End of is left input an add
137 } // End of is right input a Mul
138
139 return progress;
140 }
141
142 //------------------------------Value-----------------------------------------
Value(PhaseGVN * phase) const143 const Type* MulNode::Value(PhaseGVN* phase) const {
144 const Type *t1 = phase->type( in(1) );
145 const Type *t2 = phase->type( in(2) );
146 // Either input is TOP ==> the result is TOP
147 if( t1 == Type::TOP ) return Type::TOP;
148 if( t2 == Type::TOP ) return Type::TOP;
149
150 // Either input is ZERO ==> the result is ZERO.
151 // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0
152 int op = Opcode();
153 if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) {
154 const Type *zero = add_id(); // The multiplicative zero
155 if( t1->higher_equal( zero ) ) return zero;
156 if( t2->higher_equal( zero ) ) return zero;
157 }
158
159 // Either input is BOTTOM ==> the result is the local BOTTOM
160 if( t1 == Type::BOTTOM || t2 == Type::BOTTOM )
161 return bottom_type();
162
163 #if defined(IA32)
164 // Can't trust native compilers to properly fold strict double
165 // multiplication with round-to-zero on this platform.
166 if (op == Op_MulD && phase->C->method()->is_strict()) {
167 return TypeD::DOUBLE;
168 }
169 #endif
170
171 return mul_ring(t1,t2); // Local flavor of type multiplication
172 }
173
174 //=============================================================================
175 //------------------------------Ideal------------------------------------------
176 // Check for power-of-2 multiply, then try the regular MulNode::Ideal
Ideal(PhaseGVN * phase,bool can_reshape)177 Node *MulINode::Ideal(PhaseGVN *phase, bool can_reshape) {
178 // Swap constant to right
179 jint con;
180 if ((con = in(1)->find_int_con(0)) != 0) {
181 swap_edges(1, 2);
182 // Finish rest of method to use info in 'con'
183 } else if ((con = in(2)->find_int_con(0)) == 0) {
184 return MulNode::Ideal(phase, can_reshape);
185 }
186
187 // Now we have a constant Node on the right and the constant in con
188 if (con == 0) return NULL; // By zero is handled by Value call
189 if (con == 1) return NULL; // By one is handled by Identity call
190
191 // Check for negative constant; if so negate the final result
192 bool sign_flip = false;
193
194 unsigned int abs_con = uabs(con);
195 if (abs_con != (unsigned int)con) {
196 sign_flip = true;
197 }
198
199 // Get low bit; check for being the only bit
200 Node *res = NULL;
201 unsigned int bit1 = abs_con & (0-abs_con); // Extract low bit
202 if (bit1 == abs_con) { // Found a power of 2?
203 res = new LShiftINode(in(1), phase->intcon(log2_uint(bit1)));
204 } else {
205
206 // Check for constant with 2 bits set
207 unsigned int bit2 = abs_con-bit1;
208 bit2 = bit2 & (0-bit2); // Extract 2nd bit
209 if (bit2 + bit1 == abs_con) { // Found all bits in con?
210 Node *n1 = phase->transform( new LShiftINode(in(1), phase->intcon(log2_uint(bit1))));
211 Node *n2 = phase->transform( new LShiftINode(in(1), phase->intcon(log2_uint(bit2))));
212 res = new AddINode(n2, n1);
213
214 } else if (is_power_of_2(abs_con+1)) {
215 // Sleezy: power-of-2 -1. Next time be generic.
216 unsigned int temp = abs_con + 1;
217 Node *n1 = phase->transform(new LShiftINode(in(1), phase->intcon(log2_uint(temp))));
218 res = new SubINode(n1, in(1));
219 } else {
220 return MulNode::Ideal(phase, can_reshape);
221 }
222 }
223
224 if (sign_flip) { // Need to negate result?
225 res = phase->transform(res);// Transform, before making the zero con
226 res = new SubINode(phase->intcon(0),res);
227 }
228
229 return res; // Return final result
230 }
231
232 //------------------------------mul_ring---------------------------------------
233 // Compute the product type of two integer ranges into this node.
mul_ring(const Type * t0,const Type * t1) const234 const Type *MulINode::mul_ring(const Type *t0, const Type *t1) const {
235 const TypeInt *r0 = t0->is_int(); // Handy access
236 const TypeInt *r1 = t1->is_int();
237
238 // Fetch endpoints of all ranges
239 jint lo0 = r0->_lo;
240 double a = (double)lo0;
241 jint hi0 = r0->_hi;
242 double b = (double)hi0;
243 jint lo1 = r1->_lo;
244 double c = (double)lo1;
245 jint hi1 = r1->_hi;
246 double d = (double)hi1;
247
248 // Compute all endpoints & check for overflow
249 int32_t A = java_multiply(lo0, lo1);
250 if( (double)A != a*c ) return TypeInt::INT; // Overflow?
251 int32_t B = java_multiply(lo0, hi1);
252 if( (double)B != a*d ) return TypeInt::INT; // Overflow?
253 int32_t C = java_multiply(hi0, lo1);
254 if( (double)C != b*c ) return TypeInt::INT; // Overflow?
255 int32_t D = java_multiply(hi0, hi1);
256 if( (double)D != b*d ) return TypeInt::INT; // Overflow?
257
258 if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
259 else { lo0 = B; hi0 = A; }
260 if( C < D ) {
261 if( C < lo0 ) lo0 = C;
262 if( D > hi0 ) hi0 = D;
263 } else {
264 if( D < lo0 ) lo0 = D;
265 if( C > hi0 ) hi0 = C;
266 }
267 return TypeInt::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
268 }
269
270
271 //=============================================================================
272 //------------------------------Ideal------------------------------------------
273 // Check for power-of-2 multiply, then try the regular MulNode::Ideal
Ideal(PhaseGVN * phase,bool can_reshape)274 Node *MulLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
275 // Swap constant to right
276 jlong con;
277 if ((con = in(1)->find_long_con(0)) != 0) {
278 swap_edges(1, 2);
279 // Finish rest of method to use info in 'con'
280 } else if ((con = in(2)->find_long_con(0)) == 0) {
281 return MulNode::Ideal(phase, can_reshape);
282 }
283
284 // Now we have a constant Node on the right and the constant in con
285 if (con == CONST64(0)) return NULL; // By zero is handled by Value call
286 if (con == CONST64(1)) return NULL; // By one is handled by Identity call
287
288 // Check for negative constant; if so negate the final result
289 bool sign_flip = false;
290 julong abs_con = uabs(con);
291 if (abs_con != (julong)con) {
292 sign_flip = true;
293 }
294
295 // Get low bit; check for being the only bit
296 Node *res = NULL;
297 julong bit1 = abs_con & (0-abs_con); // Extract low bit
298 if (bit1 == abs_con) { // Found a power of 2?
299 res = new LShiftLNode(in(1), phase->intcon(log2_long(bit1)));
300 } else {
301
302 // Check for constant with 2 bits set
303 julong bit2 = abs_con-bit1;
304 bit2 = bit2 & (0-bit2); // Extract 2nd bit
305 if (bit2 + bit1 == abs_con) { // Found all bits in con?
306 Node *n1 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2_long(bit1))));
307 Node *n2 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2_long(bit2))));
308 res = new AddLNode(n2, n1);
309
310 } else if (is_power_of_2(abs_con+1)) {
311 // Sleezy: power-of-2 -1. Next time be generic.
312 julong temp = abs_con + 1;
313 Node *n1 = phase->transform( new LShiftLNode(in(1), phase->intcon(log2_long(temp))));
314 res = new SubLNode(n1, in(1));
315 } else {
316 return MulNode::Ideal(phase, can_reshape);
317 }
318 }
319
320 if (sign_flip) { // Need to negate result?
321 res = phase->transform(res);// Transform, before making the zero con
322 res = new SubLNode(phase->longcon(0),res);
323 }
324
325 return res; // Return final result
326 }
327
328 //------------------------------mul_ring---------------------------------------
329 // Compute the product type of two integer ranges into this node.
mul_ring(const Type * t0,const Type * t1) const330 const Type *MulLNode::mul_ring(const Type *t0, const Type *t1) const {
331 const TypeLong *r0 = t0->is_long(); // Handy access
332 const TypeLong *r1 = t1->is_long();
333
334 // Fetch endpoints of all ranges
335 jlong lo0 = r0->_lo;
336 double a = (double)lo0;
337 jlong hi0 = r0->_hi;
338 double b = (double)hi0;
339 jlong lo1 = r1->_lo;
340 double c = (double)lo1;
341 jlong hi1 = r1->_hi;
342 double d = (double)hi1;
343
344 // Compute all endpoints & check for overflow
345 jlong A = java_multiply(lo0, lo1);
346 if( (double)A != a*c ) return TypeLong::LONG; // Overflow?
347 jlong B = java_multiply(lo0, hi1);
348 if( (double)B != a*d ) return TypeLong::LONG; // Overflow?
349 jlong C = java_multiply(hi0, lo1);
350 if( (double)C != b*c ) return TypeLong::LONG; // Overflow?
351 jlong D = java_multiply(hi0, hi1);
352 if( (double)D != b*d ) return TypeLong::LONG; // Overflow?
353
354 if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
355 else { lo0 = B; hi0 = A; }
356 if( C < D ) {
357 if( C < lo0 ) lo0 = C;
358 if( D > hi0 ) hi0 = D;
359 } else {
360 if( D < lo0 ) lo0 = D;
361 if( C > hi0 ) hi0 = C;
362 }
363 return TypeLong::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
364 }
365
366 //=============================================================================
367 //------------------------------mul_ring---------------------------------------
368 // Compute the product type of two double ranges into this node.
mul_ring(const Type * t0,const Type * t1) const369 const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const {
370 if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT;
371 return TypeF::make( t0->getf() * t1->getf() );
372 }
373
374 //=============================================================================
375 //------------------------------mul_ring---------------------------------------
376 // Compute the product type of two double ranges into this node.
mul_ring(const Type * t0,const Type * t1) const377 const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const {
378 if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE;
379 // We must be multiplying 2 double constants.
380 return TypeD::make( t0->getd() * t1->getd() );
381 }
382
383 //=============================================================================
384 //------------------------------Value------------------------------------------
Value(PhaseGVN * phase) const385 const Type* MulHiLNode::Value(PhaseGVN* phase) const {
386 // Either input is TOP ==> the result is TOP
387 const Type *t1 = phase->type( in(1) );
388 const Type *t2 = phase->type( in(2) );
389 if( t1 == Type::TOP ) return Type::TOP;
390 if( t2 == Type::TOP ) return Type::TOP;
391
392 // Either input is BOTTOM ==> the result is the local BOTTOM
393 const Type *bot = bottom_type();
394 if( (t1 == bot) || (t2 == bot) ||
395 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
396 return bot;
397
398 // It is not worth trying to constant fold this stuff!
399 return TypeLong::LONG;
400 }
401
402 //=============================================================================
403 //------------------------------mul_ring---------------------------------------
404 // Supplied function returns the product of the inputs IN THE CURRENT RING.
405 // For the logical operations the ring's MUL is really a logical AND function.
406 // This also type-checks the inputs for sanity. Guaranteed never to
407 // be passed a TOP or BOTTOM type, these are filtered out by pre-check.
mul_ring(const Type * t0,const Type * t1) const408 const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const {
409 const TypeInt *r0 = t0->is_int(); // Handy access
410 const TypeInt *r1 = t1->is_int();
411 int widen = MAX2(r0->_widen,r1->_widen);
412
413 // If either input is a constant, might be able to trim cases
414 if( !r0->is_con() && !r1->is_con() )
415 return TypeInt::INT; // No constants to be had
416
417 // Both constants? Return bits
418 if( r0->is_con() && r1->is_con() )
419 return TypeInt::make( r0->get_con() & r1->get_con() );
420
421 if( r0->is_con() && r0->get_con() > 0 )
422 return TypeInt::make(0, r0->get_con(), widen);
423
424 if( r1->is_con() && r1->get_con() > 0 )
425 return TypeInt::make(0, r1->get_con(), widen);
426
427 if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) {
428 return TypeInt::BOOL;
429 }
430
431 return TypeInt::INT; // No constants to be had
432 }
433
434 //------------------------------Identity---------------------------------------
435 // Masking off the high bits of an unsigned load is not required
Identity(PhaseGVN * phase)436 Node* AndINode::Identity(PhaseGVN* phase) {
437
438 // x & x => x
439 if (phase->eqv(in(1), in(2))) return in(1);
440
441 Node* in1 = in(1);
442 uint op = in1->Opcode();
443 const TypeInt* t2 = phase->type(in(2))->isa_int();
444 if (t2 && t2->is_con()) {
445 int con = t2->get_con();
446 // Masking off high bits which are always zero is useless.
447 const TypeInt* t1 = phase->type( in(1) )->isa_int();
448 if (t1 != NULL && t1->_lo >= 0) {
449 jint t1_support = right_n_bits(1 + log2_jint(t1->_hi));
450 if ((t1_support & con) == t1_support)
451 return in1;
452 }
453 // Masking off the high bits of a unsigned-shift-right is not
454 // needed either.
455 if (op == Op_URShiftI) {
456 const TypeInt* t12 = phase->type(in1->in(2))->isa_int();
457 if (t12 && t12->is_con()) { // Shift is by a constant
458 int shift = t12->get_con();
459 shift &= BitsPerJavaInteger - 1; // semantics of Java shifts
460 int mask = max_juint >> shift;
461 if ((mask & con) == mask) // If AND is useless, skip it
462 return in1;
463 }
464 }
465 }
466 return MulNode::Identity(phase);
467 }
468
469 //------------------------------Ideal------------------------------------------
Ideal(PhaseGVN * phase,bool can_reshape)470 Node *AndINode::Ideal(PhaseGVN *phase, bool can_reshape) {
471 // Special case constant AND mask
472 const TypeInt *t2 = phase->type( in(2) )->isa_int();
473 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
474 const int mask = t2->get_con();
475 Node *load = in(1);
476 uint lop = load->Opcode();
477
478 // Masking bits off of a Character? Hi bits are already zero.
479 if( lop == Op_LoadUS &&
480 (mask & 0xFFFF0000) ) // Can we make a smaller mask?
481 return new AndINode(load,phase->intcon(mask&0xFFFF));
482
483 // Masking bits off of a Short? Loading a Character does some masking
484 if (can_reshape &&
485 load->outcnt() == 1 && load->unique_out() == this) {
486 if (lop == Op_LoadS && (mask & 0xFFFF0000) == 0 ) {
487 Node* ldus = load->as_Load()->convert_to_unsigned_load(*phase);
488 ldus = phase->transform(ldus);
489 return new AndINode(ldus, phase->intcon(mask & 0xFFFF));
490 }
491
492 // Masking sign bits off of a Byte? Do an unsigned byte load plus
493 // an and.
494 if (lop == Op_LoadB && (mask & 0xFFFFFF00) == 0) {
495 Node* ldub = load->as_Load()->convert_to_unsigned_load(*phase);
496 ldub = phase->transform(ldub);
497 return new AndINode(ldub, phase->intcon(mask));
498 }
499 }
500
501 // Masking off sign bits? Dont make them!
502 if( lop == Op_RShiftI ) {
503 const TypeInt *t12 = phase->type(load->in(2))->isa_int();
504 if( t12 && t12->is_con() ) { // Shift is by a constant
505 int shift = t12->get_con();
506 shift &= BitsPerJavaInteger-1; // semantics of Java shifts
507 const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift);
508 // If the AND'ing of the 2 masks has no bits, then only original shifted
509 // bits survive. NO sign-extension bits survive the maskings.
510 if( (sign_bits_mask & mask) == 0 ) {
511 // Use zero-fill shift instead
512 Node *zshift = phase->transform(new URShiftINode(load->in(1),load->in(2)));
513 return new AndINode( zshift, in(2) );
514 }
515 }
516 }
517
518 // Check for 'negate/and-1', a pattern emitted when someone asks for
519 // 'mod 2'. Negate leaves the low order bit unchanged (think: complement
520 // plus 1) and the mask is of the low order bit. Skip the negate.
521 if( lop == Op_SubI && mask == 1 && load->in(1) &&
522 phase->type(load->in(1)) == TypeInt::ZERO )
523 return new AndINode( load->in(2), in(2) );
524
525 return MulNode::Ideal(phase, can_reshape);
526 }
527
528 //=============================================================================
529 //------------------------------mul_ring---------------------------------------
530 // Supplied function returns the product of the inputs IN THE CURRENT RING.
531 // For the logical operations the ring's MUL is really a logical AND function.
532 // This also type-checks the inputs for sanity. Guaranteed never to
533 // be passed a TOP or BOTTOM type, these are filtered out by pre-check.
mul_ring(const Type * t0,const Type * t1) const534 const Type *AndLNode::mul_ring( const Type *t0, const Type *t1 ) const {
535 const TypeLong *r0 = t0->is_long(); // Handy access
536 const TypeLong *r1 = t1->is_long();
537 int widen = MAX2(r0->_widen,r1->_widen);
538
539 // If either input is a constant, might be able to trim cases
540 if( !r0->is_con() && !r1->is_con() )
541 return TypeLong::LONG; // No constants to be had
542
543 // Both constants? Return bits
544 if( r0->is_con() && r1->is_con() )
545 return TypeLong::make( r0->get_con() & r1->get_con() );
546
547 if( r0->is_con() && r0->get_con() > 0 )
548 return TypeLong::make(CONST64(0), r0->get_con(), widen);
549
550 if( r1->is_con() && r1->get_con() > 0 )
551 return TypeLong::make(CONST64(0), r1->get_con(), widen);
552
553 return TypeLong::LONG; // No constants to be had
554 }
555
556 //------------------------------Identity---------------------------------------
557 // Masking off the high bits of an unsigned load is not required
Identity(PhaseGVN * phase)558 Node* AndLNode::Identity(PhaseGVN* phase) {
559
560 // x & x => x
561 if (phase->eqv(in(1), in(2))) return in(1);
562
563 Node *usr = in(1);
564 const TypeLong *t2 = phase->type( in(2) )->isa_long();
565 if( t2 && t2->is_con() ) {
566 jlong con = t2->get_con();
567 // Masking off high bits which are always zero is useless.
568 const TypeLong* t1 = phase->type( in(1) )->isa_long();
569 if (t1 != NULL && t1->_lo >= 0) {
570 int bit_count = log2_long(t1->_hi) + 1;
571 jlong t1_support = jlong(max_julong >> (BitsPerJavaLong - bit_count));
572 if ((t1_support & con) == t1_support)
573 return usr;
574 }
575 uint lop = usr->Opcode();
576 // Masking off the high bits of a unsigned-shift-right is not
577 // needed either.
578 if( lop == Op_URShiftL ) {
579 const TypeInt *t12 = phase->type( usr->in(2) )->isa_int();
580 if( t12 && t12->is_con() ) { // Shift is by a constant
581 int shift = t12->get_con();
582 shift &= BitsPerJavaLong - 1; // semantics of Java shifts
583 jlong mask = max_julong >> shift;
584 if( (mask&con) == mask ) // If AND is useless, skip it
585 return usr;
586 }
587 }
588 }
589 return MulNode::Identity(phase);
590 }
591
592 //------------------------------Ideal------------------------------------------
Ideal(PhaseGVN * phase,bool can_reshape)593 Node *AndLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
594 // Special case constant AND mask
595 const TypeLong *t2 = phase->type( in(2) )->isa_long();
596 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
597 const jlong mask = t2->get_con();
598
599 Node* in1 = in(1);
600 uint op = in1->Opcode();
601
602 // Are we masking a long that was converted from an int with a mask
603 // that fits in 32-bits? Commute them and use an AndINode. Don't
604 // convert masks which would cause a sign extension of the integer
605 // value. This check includes UI2L masks (0x00000000FFFFFFFF) which
606 // would be optimized away later in Identity.
607 if (op == Op_ConvI2L && (mask & UCONST64(0xFFFFFFFF80000000)) == 0) {
608 Node* andi = new AndINode(in1->in(1), phase->intcon(mask));
609 andi = phase->transform(andi);
610 return new ConvI2LNode(andi);
611 }
612
613 // Masking off sign bits? Dont make them!
614 if (op == Op_RShiftL) {
615 const TypeInt* t12 = phase->type(in1->in(2))->isa_int();
616 if( t12 && t12->is_con() ) { // Shift is by a constant
617 int shift = t12->get_con();
618 shift &= BitsPerJavaLong - 1; // semantics of Java shifts
619 const jlong sign_bits_mask = ~(((jlong)CONST64(1) << (jlong)(BitsPerJavaLong - shift)) -1);
620 // If the AND'ing of the 2 masks has no bits, then only original shifted
621 // bits survive. NO sign-extension bits survive the maskings.
622 if( (sign_bits_mask & mask) == 0 ) {
623 // Use zero-fill shift instead
624 Node *zshift = phase->transform(new URShiftLNode(in1->in(1), in1->in(2)));
625 return new AndLNode(zshift, in(2));
626 }
627 }
628 }
629
630 return MulNode::Ideal(phase, can_reshape);
631 }
632
633 //=============================================================================
634
getShiftCon(PhaseGVN * phase,Node * shiftNode,int retVal)635 static int getShiftCon(PhaseGVN *phase, Node *shiftNode, int retVal) {
636 const Type *t = phase->type(shiftNode->in(2));
637 if (t == Type::TOP) return retVal; // Right input is dead.
638 const TypeInt *t2 = t->isa_int();
639 if (!t2 || !t2->is_con()) return retVal; // Right input is a constant.
640
641 return t2->get_con();
642 }
643
maskShiftAmount(PhaseGVN * phase,Node * shiftNode,int nBits)644 static int maskShiftAmount(PhaseGVN *phase, Node *shiftNode, int nBits) {
645 int shift = getShiftCon(phase, shiftNode, 0);
646 int maskedShift = shift & (nBits - 1);
647
648 if (maskedShift == 0) return 0; // Let Identity() handle 0 shift count.
649
650 if (shift != maskedShift) {
651 shiftNode->set_req(2, phase->intcon(maskedShift)); // Replace shift count with masked value.
652 phase->igvn_rehash_node_delayed(shiftNode);
653 }
654
655 return maskedShift;
656 }
657
658 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)659 Node* LShiftINode::Identity(PhaseGVN* phase) {
660 return ((getShiftCon(phase, this, -1) & (BitsPerJavaInteger - 1)) == 0) ? in(1) : this;
661 }
662
663 //------------------------------Ideal------------------------------------------
664 // If the right input is a constant, and the left input is an add of a
665 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
Ideal(PhaseGVN * phase,bool can_reshape)666 Node *LShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
667 int con = maskShiftAmount(phase, this, BitsPerJavaInteger);
668 if (con == 0) {
669 return NULL;
670 }
671
672 // Left input is an add of a constant?
673 Node *add1 = in(1);
674 int add1_op = add1->Opcode();
675 if( add1_op == Op_AddI ) { // Left input is an add?
676 assert( add1 != add1->in(1), "dead loop in LShiftINode::Ideal" );
677 const TypeInt *t12 = phase->type(add1->in(2))->isa_int();
678 if( t12 && t12->is_con() ){ // Left input is an add of a con?
679 // Transform is legal, but check for profit. Avoid breaking 'i2s'
680 // and 'i2b' patterns which typically fold into 'StoreC/StoreB'.
681 if( con < 16 ) {
682 // Compute X << con0
683 Node *lsh = phase->transform( new LShiftINode( add1->in(1), in(2) ) );
684 // Compute X<<con0 + (con1<<con0)
685 return new AddINode( lsh, phase->intcon(t12->get_con() << con));
686 }
687 }
688 }
689
690 // Check for "(x>>c0)<<c0" which just masks off low bits
691 if( (add1_op == Op_RShiftI || add1_op == Op_URShiftI ) &&
692 add1->in(2) == in(2) )
693 // Convert to "(x & -(1<<c0))"
694 return new AndINode(add1->in(1),phase->intcon( -(1<<con)));
695
696 // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
697 if( add1_op == Op_AndI ) {
698 Node *add2 = add1->in(1);
699 int add2_op = add2->Opcode();
700 if( (add2_op == Op_RShiftI || add2_op == Op_URShiftI ) &&
701 add2->in(2) == in(2) ) {
702 // Convert to "(x & (Y<<c0))"
703 Node *y_sh = phase->transform( new LShiftINode( add1->in(2), in(2) ) );
704 return new AndINode( add2->in(1), y_sh );
705 }
706 }
707
708 // Check for ((x & ((1<<(32-c0))-1)) << c0) which ANDs off high bits
709 // before shifting them away.
710 const jint bits_mask = right_n_bits(BitsPerJavaInteger-con);
711 if( add1_op == Op_AndI &&
712 phase->type(add1->in(2)) == TypeInt::make( bits_mask ) )
713 return new LShiftINode( add1->in(1), in(2) );
714
715 return NULL;
716 }
717
718 //------------------------------Value------------------------------------------
719 // A LShiftINode shifts its input2 left by input1 amount.
Value(PhaseGVN * phase) const720 const Type* LShiftINode::Value(PhaseGVN* phase) const {
721 const Type *t1 = phase->type( in(1) );
722 const Type *t2 = phase->type( in(2) );
723 // Either input is TOP ==> the result is TOP
724 if( t1 == Type::TOP ) return Type::TOP;
725 if( t2 == Type::TOP ) return Type::TOP;
726
727 // Left input is ZERO ==> the result is ZERO.
728 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
729 // Shift by zero does nothing
730 if( t2 == TypeInt::ZERO ) return t1;
731
732 // Either input is BOTTOM ==> the result is BOTTOM
733 if( (t1 == TypeInt::INT) || (t2 == TypeInt::INT) ||
734 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
735 return TypeInt::INT;
736
737 const TypeInt *r1 = t1->is_int(); // Handy access
738 const TypeInt *r2 = t2->is_int(); // Handy access
739
740 if (!r2->is_con())
741 return TypeInt::INT;
742
743 uint shift = r2->get_con();
744 shift &= BitsPerJavaInteger-1; // semantics of Java shifts
745 // Shift by a multiple of 32 does nothing:
746 if (shift == 0) return t1;
747
748 // If the shift is a constant, shift the bounds of the type,
749 // unless this could lead to an overflow.
750 if (!r1->is_con()) {
751 jint lo = r1->_lo, hi = r1->_hi;
752 if (((lo << shift) >> shift) == lo &&
753 ((hi << shift) >> shift) == hi) {
754 // No overflow. The range shifts up cleanly.
755 return TypeInt::make((jint)lo << (jint)shift,
756 (jint)hi << (jint)shift,
757 MAX2(r1->_widen,r2->_widen));
758 }
759 return TypeInt::INT;
760 }
761
762 return TypeInt::make( (jint)r1->get_con() << (jint)shift );
763 }
764
765 //=============================================================================
766 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)767 Node* LShiftLNode::Identity(PhaseGVN* phase) {
768 return ((getShiftCon(phase, this, -1) & (BitsPerJavaLong - 1)) == 0) ? in(1) : this;
769 }
770
771 //------------------------------Ideal------------------------------------------
772 // If the right input is a constant, and the left input is an add of a
773 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
Ideal(PhaseGVN * phase,bool can_reshape)774 Node *LShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
775 int con = maskShiftAmount(phase, this, BitsPerJavaLong);
776 if (con == 0) {
777 return NULL;
778 }
779
780 // Left input is an add of a constant?
781 Node *add1 = in(1);
782 int add1_op = add1->Opcode();
783 if( add1_op == Op_AddL ) { // Left input is an add?
784 // Avoid dead data cycles from dead loops
785 assert( add1 != add1->in(1), "dead loop in LShiftLNode::Ideal" );
786 const TypeLong *t12 = phase->type(add1->in(2))->isa_long();
787 if( t12 && t12->is_con() ){ // Left input is an add of a con?
788 // Compute X << con0
789 Node *lsh = phase->transform( new LShiftLNode( add1->in(1), in(2) ) );
790 // Compute X<<con0 + (con1<<con0)
791 return new AddLNode( lsh, phase->longcon(t12->get_con() << con));
792 }
793 }
794
795 // Check for "(x>>c0)<<c0" which just masks off low bits
796 if( (add1_op == Op_RShiftL || add1_op == Op_URShiftL ) &&
797 add1->in(2) == in(2) )
798 // Convert to "(x & -(1<<c0))"
799 return new AndLNode(add1->in(1),phase->longcon( -(CONST64(1)<<con)));
800
801 // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
802 if( add1_op == Op_AndL ) {
803 Node *add2 = add1->in(1);
804 int add2_op = add2->Opcode();
805 if( (add2_op == Op_RShiftL || add2_op == Op_URShiftL ) &&
806 add2->in(2) == in(2) ) {
807 // Convert to "(x & (Y<<c0))"
808 Node *y_sh = phase->transform( new LShiftLNode( add1->in(2), in(2) ) );
809 return new AndLNode( add2->in(1), y_sh );
810 }
811 }
812
813 // Check for ((x & ((CONST64(1)<<(64-c0))-1)) << c0) which ANDs off high bits
814 // before shifting them away.
815 const jlong bits_mask = jlong(max_julong >> con);
816 if( add1_op == Op_AndL &&
817 phase->type(add1->in(2)) == TypeLong::make( bits_mask ) )
818 return new LShiftLNode( add1->in(1), in(2) );
819
820 return NULL;
821 }
822
823 //------------------------------Value------------------------------------------
824 // A LShiftLNode shifts its input2 left by input1 amount.
Value(PhaseGVN * phase) const825 const Type* LShiftLNode::Value(PhaseGVN* phase) const {
826 const Type *t1 = phase->type( in(1) );
827 const Type *t2 = phase->type( in(2) );
828 // Either input is TOP ==> the result is TOP
829 if( t1 == Type::TOP ) return Type::TOP;
830 if( t2 == Type::TOP ) return Type::TOP;
831
832 // Left input is ZERO ==> the result is ZERO.
833 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
834 // Shift by zero does nothing
835 if( t2 == TypeInt::ZERO ) return t1;
836
837 // Either input is BOTTOM ==> the result is BOTTOM
838 if( (t1 == TypeLong::LONG) || (t2 == TypeInt::INT) ||
839 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
840 return TypeLong::LONG;
841
842 const TypeLong *r1 = t1->is_long(); // Handy access
843 const TypeInt *r2 = t2->is_int(); // Handy access
844
845 if (!r2->is_con())
846 return TypeLong::LONG;
847
848 uint shift = r2->get_con();
849 shift &= BitsPerJavaLong - 1; // semantics of Java shifts
850 // Shift by a multiple of 64 does nothing:
851 if (shift == 0) return t1;
852
853 // If the shift is a constant, shift the bounds of the type,
854 // unless this could lead to an overflow.
855 if (!r1->is_con()) {
856 jlong lo = r1->_lo, hi = r1->_hi;
857 if (((lo << shift) >> shift) == lo &&
858 ((hi << shift) >> shift) == hi) {
859 // No overflow. The range shifts up cleanly.
860 return TypeLong::make((jlong)lo << (jint)shift,
861 (jlong)hi << (jint)shift,
862 MAX2(r1->_widen,r2->_widen));
863 }
864 return TypeLong::LONG;
865 }
866
867 return TypeLong::make( (jlong)r1->get_con() << (jint)shift );
868 }
869
870 //=============================================================================
871 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)872 Node* RShiftINode::Identity(PhaseGVN* phase) {
873 int shift = getShiftCon(phase, this, -1);
874 if (shift == -1) return this;
875 if ((shift & (BitsPerJavaInteger - 1)) == 0) return in(1);
876
877 // Check for useless sign-masking
878 if (in(1)->Opcode() == Op_LShiftI &&
879 in(1)->req() == 3 &&
880 in(1)->in(2) == in(2)) {
881 shift &= BitsPerJavaInteger-1; // semantics of Java shifts
882 // Compute masks for which this shifting doesn't change
883 int lo = (-1 << (BitsPerJavaInteger - ((uint)shift)-1)); // FFFF8000
884 int hi = ~lo; // 00007FFF
885 const TypeInt *t11 = phase->type(in(1)->in(1))->isa_int();
886 if (!t11) return this;
887 // Does actual value fit inside of mask?
888 if (lo <= t11->_lo && t11->_hi <= hi) {
889 return in(1)->in(1); // Then shifting is a nop
890 }
891 }
892
893 return this;
894 }
895
896 //------------------------------Ideal------------------------------------------
Ideal(PhaseGVN * phase,bool can_reshape)897 Node *RShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
898 // Inputs may be TOP if they are dead.
899 const TypeInt *t1 = phase->type(in(1))->isa_int();
900 if (!t1) return NULL; // Left input is an integer
901 const TypeInt *t3; // type of in(1).in(2)
902 int shift = maskShiftAmount(phase, this, BitsPerJavaInteger);
903 if (shift == 0) {
904 return NULL;
905 }
906
907 // Check for (x & 0xFF000000) >> 24, whose mask can be made smaller.
908 // Such expressions arise normally from shift chains like (byte)(x >> 24).
909 const Node *mask = in(1);
910 if( mask->Opcode() == Op_AndI &&
911 (t3 = phase->type(mask->in(2))->isa_int()) &&
912 t3->is_con() ) {
913 Node *x = mask->in(1);
914 jint maskbits = t3->get_con();
915 // Convert to "(x >> shift) & (mask >> shift)"
916 Node *shr_nomask = phase->transform( new RShiftINode(mask->in(1), in(2)) );
917 return new AndINode(shr_nomask, phase->intcon( maskbits >> shift));
918 }
919
920 // Check for "(short[i] <<16)>>16" which simply sign-extends
921 const Node *shl = in(1);
922 if( shl->Opcode() != Op_LShiftI ) return NULL;
923
924 if( shift == 16 &&
925 (t3 = phase->type(shl->in(2))->isa_int()) &&
926 t3->is_con(16) ) {
927 Node *ld = shl->in(1);
928 if( ld->Opcode() == Op_LoadS ) {
929 // Sign extension is just useless here. Return a RShiftI of zero instead
930 // returning 'ld' directly. We cannot return an old Node directly as
931 // that is the job of 'Identity' calls and Identity calls only work on
932 // direct inputs ('ld' is an extra Node removed from 'this'). The
933 // combined optimization requires Identity only return direct inputs.
934 set_req(1, ld);
935 set_req(2, phase->intcon(0));
936 return this;
937 }
938 else if( can_reshape &&
939 ld->Opcode() == Op_LoadUS &&
940 ld->outcnt() == 1 && ld->unique_out() == shl)
941 // Replace zero-extension-load with sign-extension-load
942 return ld->as_Load()->convert_to_signed_load(*phase);
943 }
944
945 // Check for "(byte[i] <<24)>>24" which simply sign-extends
946 if( shift == 24 &&
947 (t3 = phase->type(shl->in(2))->isa_int()) &&
948 t3->is_con(24) ) {
949 Node *ld = shl->in(1);
950 if( ld->Opcode() == Op_LoadB ) {
951 // Sign extension is just useless here
952 set_req(1, ld);
953 set_req(2, phase->intcon(0));
954 return this;
955 }
956 }
957
958 return NULL;
959 }
960
961 //------------------------------Value------------------------------------------
962 // A RShiftINode shifts its input2 right by input1 amount.
Value(PhaseGVN * phase) const963 const Type* RShiftINode::Value(PhaseGVN* phase) const {
964 const Type *t1 = phase->type( in(1) );
965 const Type *t2 = phase->type( in(2) );
966 // Either input is TOP ==> the result is TOP
967 if( t1 == Type::TOP ) return Type::TOP;
968 if( t2 == Type::TOP ) return Type::TOP;
969
970 // Left input is ZERO ==> the result is ZERO.
971 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
972 // Shift by zero does nothing
973 if( t2 == TypeInt::ZERO ) return t1;
974
975 // Either input is BOTTOM ==> the result is BOTTOM
976 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
977 return TypeInt::INT;
978
979 if (t2 == TypeInt::INT)
980 return TypeInt::INT;
981
982 const TypeInt *r1 = t1->is_int(); // Handy access
983 const TypeInt *r2 = t2->is_int(); // Handy access
984
985 // If the shift is a constant, just shift the bounds of the type.
986 // For example, if the shift is 31, we just propagate sign bits.
987 if (r2->is_con()) {
988 uint shift = r2->get_con();
989 shift &= BitsPerJavaInteger-1; // semantics of Java shifts
990 // Shift by a multiple of 32 does nothing:
991 if (shift == 0) return t1;
992 // Calculate reasonably aggressive bounds for the result.
993 // This is necessary if we are to correctly type things
994 // like (x<<24>>24) == ((byte)x).
995 jint lo = (jint)r1->_lo >> (jint)shift;
996 jint hi = (jint)r1->_hi >> (jint)shift;
997 assert(lo <= hi, "must have valid bounds");
998 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
999 #ifdef ASSERT
1000 // Make sure we get the sign-capture idiom correct.
1001 if (shift == BitsPerJavaInteger-1) {
1002 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>31 of + is 0");
1003 if (r1->_hi < 0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1");
1004 }
1005 #endif
1006 return ti;
1007 }
1008
1009 if( !r1->is_con() || !r2->is_con() )
1010 return TypeInt::INT;
1011
1012 // Signed shift right
1013 return TypeInt::make( r1->get_con() >> (r2->get_con()&31) );
1014 }
1015
1016 //=============================================================================
1017 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)1018 Node* RShiftLNode::Identity(PhaseGVN* phase) {
1019 const TypeInt *ti = phase->type(in(2))->isa_int(); // Shift count is an int.
1020 return (ti && ti->is_con() && (ti->get_con() & (BitsPerJavaLong - 1)) == 0) ? in(1) : this;
1021 }
1022
1023 //------------------------------Value------------------------------------------
1024 // A RShiftLNode shifts its input2 right by input1 amount.
Value(PhaseGVN * phase) const1025 const Type* RShiftLNode::Value(PhaseGVN* phase) const {
1026 const Type *t1 = phase->type( in(1) );
1027 const Type *t2 = phase->type( in(2) );
1028 // Either input is TOP ==> the result is TOP
1029 if( t1 == Type::TOP ) return Type::TOP;
1030 if( t2 == Type::TOP ) return Type::TOP;
1031
1032 // Left input is ZERO ==> the result is ZERO.
1033 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1034 // Shift by zero does nothing
1035 if( t2 == TypeInt::ZERO ) return t1;
1036
1037 // Either input is BOTTOM ==> the result is BOTTOM
1038 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1039 return TypeLong::LONG;
1040
1041 if (t2 == TypeInt::INT)
1042 return TypeLong::LONG;
1043
1044 const TypeLong *r1 = t1->is_long(); // Handy access
1045 const TypeInt *r2 = t2->is_int (); // Handy access
1046
1047 // If the shift is a constant, just shift the bounds of the type.
1048 // For example, if the shift is 63, we just propagate sign bits.
1049 if (r2->is_con()) {
1050 uint shift = r2->get_con();
1051 shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts
1052 // Shift by a multiple of 64 does nothing:
1053 if (shift == 0) return t1;
1054 // Calculate reasonably aggressive bounds for the result.
1055 // This is necessary if we are to correctly type things
1056 // like (x<<24>>24) == ((byte)x).
1057 jlong lo = (jlong)r1->_lo >> (jlong)shift;
1058 jlong hi = (jlong)r1->_hi >> (jlong)shift;
1059 assert(lo <= hi, "must have valid bounds");
1060 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1061 #ifdef ASSERT
1062 // Make sure we get the sign-capture idiom correct.
1063 if (shift == (2*BitsPerJavaInteger)-1) {
1064 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>63 of + is 0");
1065 if (r1->_hi < 0) assert(tl == TypeLong::MINUS_1, ">>63 of - is -1");
1066 }
1067 #endif
1068 return tl;
1069 }
1070
1071 return TypeLong::LONG; // Give up
1072 }
1073
1074 //=============================================================================
1075 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)1076 Node* URShiftINode::Identity(PhaseGVN* phase) {
1077 int shift = getShiftCon(phase, this, -1);
1078 if ((shift & (BitsPerJavaInteger - 1)) == 0) return in(1);
1079
1080 // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x".
1081 // Happens during new-array length computation.
1082 // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)]
1083 Node *add = in(1);
1084 if (add->Opcode() == Op_AddI) {
1085 const TypeInt *t2 = phase->type(add->in(2))->isa_int();
1086 if (t2 && t2->is_con(wordSize - 1) &&
1087 add->in(1)->Opcode() == Op_LShiftI) {
1088 // Check that shift_counts are LogBytesPerWord.
1089 Node *lshift_count = add->in(1)->in(2);
1090 const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int();
1091 if (t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) &&
1092 t_lshift_count == phase->type(in(2))) {
1093 Node *x = add->in(1)->in(1);
1094 const TypeInt *t_x = phase->type(x)->isa_int();
1095 if (t_x != NULL && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord)) {
1096 return x;
1097 }
1098 }
1099 }
1100 }
1101
1102 return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this;
1103 }
1104
1105 //------------------------------Ideal------------------------------------------
Ideal(PhaseGVN * phase,bool can_reshape)1106 Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1107 int con = maskShiftAmount(phase, this, BitsPerJavaInteger);
1108 if (con == 0) {
1109 return NULL;
1110 }
1111
1112 // We'll be wanting the right-shift amount as a mask of that many bits
1113 const int mask = right_n_bits(BitsPerJavaInteger - con);
1114
1115 int in1_op = in(1)->Opcode();
1116
1117 // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32
1118 if( in1_op == Op_URShiftI ) {
1119 const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int();
1120 if( t12 && t12->is_con() ) { // Right input is a constant
1121 assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" );
1122 const int con2 = t12->get_con() & 31; // Shift count is always masked
1123 const int con3 = con+con2;
1124 if( con3 < 32 ) // Only merge shifts if total is < 32
1125 return new URShiftINode( in(1)->in(1), phase->intcon(con3) );
1126 }
1127 }
1128
1129 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z
1130 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1131 // If Q is "X << z" the rounding is useless. Look for patterns like
1132 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask.
1133 Node *add = in(1);
1134 const TypeInt *t2 = phase->type(in(2))->isa_int();
1135 if (in1_op == Op_AddI) {
1136 Node *lshl = add->in(1);
1137 if( lshl->Opcode() == Op_LShiftI &&
1138 phase->type(lshl->in(2)) == t2 ) {
1139 Node *y_z = phase->transform( new URShiftINode(add->in(2),in(2)) );
1140 Node *sum = phase->transform( new AddINode( lshl->in(1), y_z ) );
1141 return new AndINode( sum, phase->intcon(mask) );
1142 }
1143 }
1144
1145 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z)
1146 // This shortens the mask. Also, if we are extracting a high byte and
1147 // storing it to a buffer, the mask will be removed completely.
1148 Node *andi = in(1);
1149 if( in1_op == Op_AndI ) {
1150 const TypeInt *t3 = phase->type( andi->in(2) )->isa_int();
1151 if( t3 && t3->is_con() ) { // Right input is a constant
1152 jint mask2 = t3->get_con();
1153 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help)
1154 Node *newshr = phase->transform( new URShiftINode(andi->in(1), in(2)) );
1155 return new AndINode(newshr, phase->intcon(mask2));
1156 // The negative values are easier to materialize than positive ones.
1157 // A typical case from address arithmetic is ((x & ~15) >> 4).
1158 // It's better to change that to ((x >> 4) & ~0) versus
1159 // ((x >> 4) & 0x0FFFFFFF). The difference is greatest in LP64.
1160 }
1161 }
1162
1163 // Check for "(X << z ) >>> z" which simply zero-extends
1164 Node *shl = in(1);
1165 if( in1_op == Op_LShiftI &&
1166 phase->type(shl->in(2)) == t2 )
1167 return new AndINode( shl->in(1), phase->intcon(mask) );
1168
1169 // Check for (x >> n) >>> 31. Replace with (x >>> 31)
1170 Node *shr = in(1);
1171 if ( in1_op == Op_RShiftI ) {
1172 Node *in11 = shr->in(1);
1173 Node *in12 = shr->in(2);
1174 const TypeInt *t11 = phase->type(in11)->isa_int();
1175 const TypeInt *t12 = phase->type(in12)->isa_int();
1176 if ( t11 && t2 && t2->is_con(31) && t12 && t12->is_con() ) {
1177 return new URShiftINode(in11, phase->intcon(31));
1178 }
1179 }
1180
1181 return NULL;
1182 }
1183
1184 //------------------------------Value------------------------------------------
1185 // A URShiftINode shifts its input2 right by input1 amount.
Value(PhaseGVN * phase) const1186 const Type* URShiftINode::Value(PhaseGVN* phase) const {
1187 // (This is a near clone of RShiftINode::Value.)
1188 const Type *t1 = phase->type( in(1) );
1189 const Type *t2 = phase->type( in(2) );
1190 // Either input is TOP ==> the result is TOP
1191 if( t1 == Type::TOP ) return Type::TOP;
1192 if( t2 == Type::TOP ) return Type::TOP;
1193
1194 // Left input is ZERO ==> the result is ZERO.
1195 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1196 // Shift by zero does nothing
1197 if( t2 == TypeInt::ZERO ) return t1;
1198
1199 // Either input is BOTTOM ==> the result is BOTTOM
1200 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1201 return TypeInt::INT;
1202
1203 if (t2 == TypeInt::INT)
1204 return TypeInt::INT;
1205
1206 const TypeInt *r1 = t1->is_int(); // Handy access
1207 const TypeInt *r2 = t2->is_int(); // Handy access
1208
1209 if (r2->is_con()) {
1210 uint shift = r2->get_con();
1211 shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1212 // Shift by a multiple of 32 does nothing:
1213 if (shift == 0) return t1;
1214 // Calculate reasonably aggressive bounds for the result.
1215 jint lo = (juint)r1->_lo >> (juint)shift;
1216 jint hi = (juint)r1->_hi >> (juint)shift;
1217 if (r1->_hi >= 0 && r1->_lo < 0) {
1218 // If the type has both negative and positive values,
1219 // there are two separate sub-domains to worry about:
1220 // The positive half and the negative half.
1221 jint neg_lo = lo;
1222 jint neg_hi = (juint)-1 >> (juint)shift;
1223 jint pos_lo = (juint) 0 >> (juint)shift;
1224 jint pos_hi = hi;
1225 lo = MIN2(neg_lo, pos_lo); // == 0
1226 hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift;
1227 }
1228 assert(lo <= hi, "must have valid bounds");
1229 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1230 #ifdef ASSERT
1231 // Make sure we get the sign-capture idiom correct.
1232 if (shift == BitsPerJavaInteger-1) {
1233 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0");
1234 if (r1->_hi < 0) assert(ti == TypeInt::ONE, ">>>31 of - is +1");
1235 }
1236 #endif
1237 return ti;
1238 }
1239
1240 //
1241 // Do not support shifted oops in info for GC
1242 //
1243 // else if( t1->base() == Type::InstPtr ) {
1244 //
1245 // const TypeInstPtr *o = t1->is_instptr();
1246 // if( t1->singleton() )
1247 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift );
1248 // }
1249 // else if( t1->base() == Type::KlassPtr ) {
1250 // const TypeKlassPtr *o = t1->is_klassptr();
1251 // if( t1->singleton() )
1252 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift );
1253 // }
1254
1255 return TypeInt::INT;
1256 }
1257
1258 //=============================================================================
1259 //------------------------------Identity---------------------------------------
Identity(PhaseGVN * phase)1260 Node* URShiftLNode::Identity(PhaseGVN* phase) {
1261 return ((getShiftCon(phase, this, -1) & (BitsPerJavaLong - 1)) == 0) ? in(1) : this;
1262 }
1263
1264 //------------------------------Ideal------------------------------------------
Ideal(PhaseGVN * phase,bool can_reshape)1265 Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1266 int con = maskShiftAmount(phase, this, BitsPerJavaLong);
1267 if (con == 0) {
1268 return NULL;
1269 }
1270
1271 // We'll be wanting the right-shift amount as a mask of that many bits
1272 const jlong mask = jlong(max_julong >> con);
1273
1274 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z
1275 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1276 // If Q is "X << z" the rounding is useless. Look for patterns like
1277 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask.
1278 Node *add = in(1);
1279 const TypeInt *t2 = phase->type(in(2))->isa_int();
1280 if (add->Opcode() == Op_AddL) {
1281 Node *lshl = add->in(1);
1282 if( lshl->Opcode() == Op_LShiftL &&
1283 phase->type(lshl->in(2)) == t2 ) {
1284 Node *y_z = phase->transform( new URShiftLNode(add->in(2),in(2)) );
1285 Node *sum = phase->transform( new AddLNode( lshl->in(1), y_z ) );
1286 return new AndLNode( sum, phase->longcon(mask) );
1287 }
1288 }
1289
1290 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z)
1291 // This shortens the mask. Also, if we are extracting a high byte and
1292 // storing it to a buffer, the mask will be removed completely.
1293 Node *andi = in(1);
1294 if( andi->Opcode() == Op_AndL ) {
1295 const TypeLong *t3 = phase->type( andi->in(2) )->isa_long();
1296 if( t3 && t3->is_con() ) { // Right input is a constant
1297 jlong mask2 = t3->get_con();
1298 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help)
1299 Node *newshr = phase->transform( new URShiftLNode(andi->in(1), in(2)) );
1300 return new AndLNode(newshr, phase->longcon(mask2));
1301 }
1302 }
1303
1304 // Check for "(X << z ) >>> z" which simply zero-extends
1305 Node *shl = in(1);
1306 if( shl->Opcode() == Op_LShiftL &&
1307 phase->type(shl->in(2)) == t2 )
1308 return new AndLNode( shl->in(1), phase->longcon(mask) );
1309
1310 // Check for (x >> n) >>> 63. Replace with (x >>> 63)
1311 Node *shr = in(1);
1312 if ( shr->Opcode() == Op_RShiftL ) {
1313 Node *in11 = shr->in(1);
1314 Node *in12 = shr->in(2);
1315 const TypeLong *t11 = phase->type(in11)->isa_long();
1316 const TypeInt *t12 = phase->type(in12)->isa_int();
1317 if ( t11 && t2 && t2->is_con(63) && t12 && t12->is_con() ) {
1318 return new URShiftLNode(in11, phase->intcon(63));
1319 }
1320 }
1321 return NULL;
1322 }
1323
1324 //------------------------------Value------------------------------------------
1325 // A URShiftINode shifts its input2 right by input1 amount.
Value(PhaseGVN * phase) const1326 const Type* URShiftLNode::Value(PhaseGVN* phase) const {
1327 // (This is a near clone of RShiftLNode::Value.)
1328 const Type *t1 = phase->type( in(1) );
1329 const Type *t2 = phase->type( in(2) );
1330 // Either input is TOP ==> the result is TOP
1331 if( t1 == Type::TOP ) return Type::TOP;
1332 if( t2 == Type::TOP ) return Type::TOP;
1333
1334 // Left input is ZERO ==> the result is ZERO.
1335 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1336 // Shift by zero does nothing
1337 if( t2 == TypeInt::ZERO ) return t1;
1338
1339 // Either input is BOTTOM ==> the result is BOTTOM
1340 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1341 return TypeLong::LONG;
1342
1343 if (t2 == TypeInt::INT)
1344 return TypeLong::LONG;
1345
1346 const TypeLong *r1 = t1->is_long(); // Handy access
1347 const TypeInt *r2 = t2->is_int (); // Handy access
1348
1349 if (r2->is_con()) {
1350 uint shift = r2->get_con();
1351 shift &= BitsPerJavaLong - 1; // semantics of Java shifts
1352 // Shift by a multiple of 64 does nothing:
1353 if (shift == 0) return t1;
1354 // Calculate reasonably aggressive bounds for the result.
1355 jlong lo = (julong)r1->_lo >> (juint)shift;
1356 jlong hi = (julong)r1->_hi >> (juint)shift;
1357 if (r1->_hi >= 0 && r1->_lo < 0) {
1358 // If the type has both negative and positive values,
1359 // there are two separate sub-domains to worry about:
1360 // The positive half and the negative half.
1361 jlong neg_lo = lo;
1362 jlong neg_hi = (julong)-1 >> (juint)shift;
1363 jlong pos_lo = (julong) 0 >> (juint)shift;
1364 jlong pos_hi = hi;
1365 //lo = MIN2(neg_lo, pos_lo); // == 0
1366 lo = neg_lo < pos_lo ? neg_lo : pos_lo;
1367 //hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift;
1368 hi = neg_hi > pos_hi ? neg_hi : pos_hi;
1369 }
1370 assert(lo <= hi, "must have valid bounds");
1371 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1372 #ifdef ASSERT
1373 // Make sure we get the sign-capture idiom correct.
1374 if (shift == BitsPerJavaLong - 1) {
1375 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0");
1376 if (r1->_hi < 0) assert(tl == TypeLong::ONE, ">>>63 of - is +1");
1377 }
1378 #endif
1379 return tl;
1380 }
1381
1382 return TypeLong::LONG; // Give up
1383 }
1384
1385 //=============================================================================
1386 //------------------------------Value------------------------------------------
Value(PhaseGVN * phase) const1387 const Type* FmaDNode::Value(PhaseGVN* phase) const {
1388 const Type *t1 = phase->type(in(1));
1389 if (t1 == Type::TOP) return Type::TOP;
1390 if (t1->base() != Type::DoubleCon) return Type::DOUBLE;
1391 const Type *t2 = phase->type(in(2));
1392 if (t2 == Type::TOP) return Type::TOP;
1393 if (t2->base() != Type::DoubleCon) return Type::DOUBLE;
1394 const Type *t3 = phase->type(in(3));
1395 if (t3 == Type::TOP) return Type::TOP;
1396 if (t3->base() != Type::DoubleCon) return Type::DOUBLE;
1397 #ifndef __STDC_IEC_559__
1398 return Type::DOUBLE;
1399 #else
1400 double d1 = t1->getd();
1401 double d2 = t2->getd();
1402 double d3 = t3->getd();
1403 return TypeD::make(fma(d1, d2, d3));
1404 #endif
1405 }
1406
1407 //=============================================================================
1408 //------------------------------Value------------------------------------------
Value(PhaseGVN * phase) const1409 const Type* FmaFNode::Value(PhaseGVN* phase) const {
1410 const Type *t1 = phase->type(in(1));
1411 if (t1 == Type::TOP) return Type::TOP;
1412 if (t1->base() != Type::FloatCon) return Type::FLOAT;
1413 const Type *t2 = phase->type(in(2));
1414 if (t2 == Type::TOP) return Type::TOP;
1415 if (t2->base() != Type::FloatCon) return Type::FLOAT;
1416 const Type *t3 = phase->type(in(3));
1417 if (t3 == Type::TOP) return Type::TOP;
1418 if (t3->base() != Type::FloatCon) return Type::FLOAT;
1419 #ifndef __STDC_IEC_559__
1420 return Type::FLOAT;
1421 #else
1422 float f1 = t1->getf();
1423 float f2 = t2->getf();
1424 float f3 = t3->getf();
1425 return TypeF::make(fma(f1, f2, f3));
1426 #endif
1427 }
1428
1429 //=============================================================================
1430 //------------------------------hash-------------------------------------------
1431 // Hash function for MulAddS2INode. Operation is commutative with commutative pairs.
1432 // The hash function must return the same value when edge swapping is performed.
hash() const1433 uint MulAddS2INode::hash() const {
1434 return (uintptr_t)in(1) + (uintptr_t)in(2) + (uintptr_t)in(3) + (uintptr_t)in(4) + Opcode();
1435 }
1436