1 #ifdef USE_PRAGMA_IDENT_SRC
2 #pragma ident "@(#)divnode.cpp 1.88 07/05/05 17:06:13 JVM"
3 #endif
4 /*
5 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
26 */
27
28 // Portions of code courtesy of Clifford Click
29
30 // Optimization - Graph Style
31
32 #include "incls/_precompiled.incl"
33 #include "incls/_divnode.cpp.incl"
34 #include <math.h>
35
36 // Implement the integer constant divide -> long multiply transform found in
37 // "Division by Invariant Integers using Multiplication"
38 // by Granlund and Montgomery
39 static Node *transform_int_divide_to_long_multiply( PhaseGVN *phase, Node *dividend, int divisor ) {
40
41 // Check for invalid divisors
42 assert( divisor != 0 && divisor != min_jint && divisor != 1,
43 "bad divisor for transforming to long multiply" );
44
45 // Compute l = ceiling(log2(d))
46 // presumes d is more likely small
47 bool d_pos = divisor >= 0;
48 int d = d_pos ? divisor : -divisor;
49 unsigned ud = (unsigned)d;
50 const int N = 32;
51 int l = log2_intptr(d-1)+1;
52 int sh_post = l;
53
54 const uint64_t U1 = (uint64_t)1;
55
56 // Cliff pointed out how to prevent overflow (from the paper)
57 uint64_t m_low = (((U1 << l) - ud) << N) / ud + (U1 << N);
58 uint64_t m_high = ((((U1 << l) - ud) << N) + (U1 << (l+1))) / ud + (U1 << N);
59
60 // Reduce to lowest terms
61 for ( ; sh_post > 0; sh_post-- ) {
62 uint64_t m_low_1 = m_low >> 1;
63 uint64_t m_high_1 = m_high >> 1;
64 if ( m_low_1 >= m_high_1 )
65 break;
66 m_low = m_low_1;
67 m_high = m_high_1;
68 }
69
70 // Result
71 Node *q;
72
73 // division by +/- 1
74 if (d == 1) {
75 // Filtered out as identity above
76 if (d_pos)
77 return NULL;
78
79 // Just negate the value
80 else {
81 q = new (phase->C, 3) SubINode(phase->intcon(0), dividend);
82 }
83 }
84
85 // division by +/- a power of 2
86 else if ( is_power_of_2(d) ) {
87
88 // See if we can simply do a shift without rounding
89 bool needs_rounding = true;
90 const Type *dt = phase->type(dividend);
91 const TypeInt *dti = dt->isa_int();
92
93 // we don't need to round a positive dividend
94 if (dti && dti->_lo >= 0)
95 needs_rounding = false;
96
97 // An AND mask of sufficient size clears the low bits and
98 // I can avoid rounding.
99 else if( dividend->Opcode() == Op_AndI ) {
100 const TypeInt *andconi = phase->type( dividend->in(2) )->isa_int();
101 if( andconi && andconi->is_con(-d) ) {
102 dividend = dividend->in(1);
103 needs_rounding = false;
104 }
105 }
106
107 // Add rounding to the shift to handle the sign bit
108 if( needs_rounding ) {
109 Node *t1 = phase->transform(new (phase->C, 3) RShiftINode(dividend, phase->intcon(l - 1)));
110 Node *t2 = phase->transform(new (phase->C, 3) URShiftINode(t1, phase->intcon(N - l)));
111 dividend = phase->transform(new (phase->C, 3) AddINode(dividend, t2));
112 }
113
114 q = new (phase->C, 3) RShiftINode(dividend, phase->intcon(l));
115
116 if (!d_pos)
117 q = new (phase->C, 3) SubINode(phase->intcon(0), phase->transform(q));
118 }
119
120 // division by something else
121 else if (m_high < (U1 << (N-1))) {
122 Node *t1 = phase->transform(new (phase->C, 2) ConvI2LNode(dividend));
123 Node *t2 = phase->transform(new (phase->C, 3) MulLNode(t1, phase->longcon(m_high)));
124 Node *t3 = phase->transform(new (phase->C, 3) RShiftLNode(t2, phase->intcon(sh_post+N)));
125 Node *t4 = phase->transform(new (phase->C, 2) ConvL2INode(t3));
126 Node *t5 = phase->transform(new (phase->C, 3) RShiftINode(dividend, phase->intcon(N-1)));
127
128 q = new (phase->C, 3) SubINode(d_pos ? t4 : t5, d_pos ? t5 : t4);
129 }
130
131 // This handles that case where m_high is >= 2**(N-1). In that case,
132 // we subtract out 2**N from the multiply and add it in later as
133 // "dividend" in the equation (t5). This case computes the same result
134 // as the immediately preceeding case, save that rounding and overflow
135 // are accounted for.
136 else {
137 Node *t1 = phase->transform(new (phase->C, 2) ConvI2LNode(dividend));
138 Node *t2 = phase->transform(new (phase->C, 3) MulLNode(t1, phase->longcon(m_high - (U1 << N))));
139 Node *t3 = phase->transform(new (phase->C, 3) RShiftLNode(t2, phase->intcon(N)));
140 Node *t4 = phase->transform(new (phase->C, 2) ConvL2INode(t3));
141 Node *t5 = phase->transform(new (phase->C, 3) AddINode(dividend, t4));
142 Node *t6 = phase->transform(new (phase->C, 3) RShiftINode(t5, phase->intcon(sh_post)));
143 Node *t7 = phase->transform(new (phase->C, 3) RShiftINode(dividend, phase->intcon(N-1)));
144
145 q = new (phase->C, 3) SubINode(d_pos ? t6 : t7, d_pos ? t7 : t6);
146 }
147
148 return (q);
149 }
150
151 //=============================================================================
152 //------------------------------Identity---------------------------------------
153 // If the divisor is 1, we are an identity on the dividend.
154 Node *DivINode::Identity( PhaseTransform *phase ) {
155 return (phase->type( in(2) )->higher_equal(TypeInt::ONE)) ? in(1) : this;
156 }
157
158 //------------------------------Idealize---------------------------------------
159 // Divides can be changed to multiplies and/or shifts
160 Node *DivINode::Ideal(PhaseGVN *phase, bool can_reshape) {
161 if (in(0) && remove_dead_region(phase, can_reshape)) return this;
162
163 const Type *t = phase->type( in(2) );
164 if( t == TypeInt::ONE ) // Identity?
165 return NULL; // Skip it
166
167 const TypeInt *ti = t->isa_int();
168 if( !ti ) return NULL;
169 if( !ti->is_con() ) return NULL;
170 int i = ti->get_con(); // Get divisor
171
172 if (i == 0) return NULL; // Dividing by zero constant does not idealize
173
174 set_req(0,NULL); // Dividing by a not-zero constant; no faulting
175
176 // Dividing by MININT does not optimize as a power-of-2 shift.
177 if( i == min_jint ) return NULL;
178
179 return transform_int_divide_to_long_multiply( phase, in(1), i );
180 }
181
182 //------------------------------Value------------------------------------------
183 // A DivINode divides its inputs. The third input is a Control input, used to
184 // prevent hoisting the divide above an unsafe test.
185 const Type *DivINode::Value( PhaseTransform *phase ) const {
186 // Either input is TOP ==> the result is TOP
187 const Type *t1 = phase->type( in(1) );
188 const Type *t2 = phase->type( in(2) );
189 if( t1 == Type::TOP ) return Type::TOP;
190 if( t2 == Type::TOP ) return Type::TOP;
191
192 // x/x == 1 since we always generate the dynamic divisor check for 0.
193 if( phase->eqv( in(1), in(2) ) )
194 return TypeInt::ONE;
195
196 // Either input is BOTTOM ==> the result is the local BOTTOM
197 const Type *bot = bottom_type();
198 if( (t1 == bot) || (t2 == bot) ||
199 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
200 return bot;
201
202 // Divide the two numbers. We approximate.
203 // If divisor is a constant and not zero
204 const TypeInt *i1 = t1->is_int();
205 const TypeInt *i2 = t2->is_int();
206 int widen = MAX2(i1->_widen, i2->_widen);
207
208 if( i2->is_con() && i2->get_con() != 0 ) {
209 int32 d = i2->get_con(); // Divisor
210 jint lo, hi;
211 if( d >= 0 ) {
212 lo = i1->_lo/d;
213 hi = i1->_hi/d;
214 } else {
215 if( d == -1 && i1->_lo == min_jint ) {
216 // 'min_jint/-1' throws arithmetic exception during compilation
217 lo = min_jint;
218 // do not support holes, 'hi' must go to either min_jint or max_jint:
219 // [min_jint, -10]/[-1,-1] ==> [min_jint] UNION [10,max_jint]
220 hi = i1->_hi == min_jint ? min_jint : max_jint;
221 } else {
222 lo = i1->_hi/d;
223 hi = i1->_lo/d;
224 }
225 }
226 return TypeInt::make(lo, hi, widen);
227 }
228
229 // If the dividend is a constant
230 if( i1->is_con() ) {
231 int32 d = i1->get_con();
232 if( d < 0 ) {
233 if( d == min_jint ) {
234 // (-min_jint) == min_jint == (min_jint / -1)
235 return TypeInt::make(min_jint, max_jint/2 + 1, widen);
236 } else {
237 return TypeInt::make(d, -d, widen);
238 }
239 }
240 return TypeInt::make(-d, d, widen);
241 }
242
243 // Otherwise we give up all hope
244 return TypeInt::INT;
245 }
246
247
248 //=============================================================================
249 //------------------------------Identity---------------------------------------
250 // If the divisor is 1, we are an identity on the dividend.
251 Node *DivLNode::Identity( PhaseTransform *phase ) {
252 return (phase->type( in(2) )->higher_equal(TypeLong::ONE)) ? in(1) : this;
253 }
254
255 //------------------------------Idealize---------------------------------------
256 // Dividing by a power of 2 is a shift.
257 Node *DivLNode::Ideal( PhaseGVN *phase, bool can_reshape) {
258 if (in(0) && remove_dead_region(phase, can_reshape)) return this;
259
260 const Type *t = phase->type( in(2) );
261 if( t == TypeLong::ONE ) // Identity?
262 return NULL; // Skip it
263
264 const TypeLong *ti = t->isa_long();
265 if( !ti ) return NULL;
266 if( !ti->is_con() ) return NULL;
267 jlong i = ti->get_con(); // Get divisor
268 if( i ) set_req(0, NULL); // Dividing by a not-zero constant; no faulting
269
270 // Dividing by MININT does not optimize as a power-of-2 shift.
271 if( i == min_jlong ) return NULL;
272
273 // Check for negative power of 2 divisor, if so, negate it and set a flag
274 // to indicate result needs to be negated. Note that negating the dividend
275 // here does not work when it has the value MININT
276 Node *dividend = in(1);
277 bool negate_res = false;
278 if (is_power_of_2_long(-i)) {
279 i = -i; // Flip divisor
280 negate_res = true;
281 }
282
283 // Check for power of 2
284 if (!is_power_of_2_long(i)) // Is divisor a power of 2?
285 return NULL; // Not a power of 2
286
287 // Compute number of bits to shift
288 int log_i = log2_long(i);
289
290 // See if we can simply do a shift without rounding
291 bool needs_rounding = true;
292 const Type *dt = phase->type(dividend);
293 const TypeLong *dtl = dt->isa_long();
294
295 if (dtl && dtl->_lo > 0) {
296 // we don't need to round a positive dividend
297 needs_rounding = false;
298 } else if( dividend->Opcode() == Op_AndL ) {
299 // An AND mask of sufficient size clears the low bits and
300 // I can avoid rounding.
301 const TypeLong *andconi = phase->type( dividend->in(2) )->isa_long();
302 if( andconi &&
303 andconi->is_con() &&
304 andconi->get_con() == -i ) {
305 dividend = dividend->in(1);
306 needs_rounding = false;
307 }
308 }
309
310 if (!needs_rounding) {
311 Node *result = new (phase->C, 3) RShiftLNode(dividend, phase->intcon(log_i));
312 if (negate_res) {
313 result = phase->transform(result);
314 result = new (phase->C, 3) SubLNode(phase->longcon(0), result);
315 }
316 return result;
317 }
318
319 // Divide-by-power-of-2 can be made into a shift, but you have to do
320 // more math for the rounding. You need to add 0 for positive
321 // numbers, and "i-1" for negative numbers. Example: i=4, so the
322 // shift is by 2. You need to add 3 to negative dividends and 0 to
323 // positive ones. So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1,
324 // (-2+3)>>2 becomes 0, etc.
325
326 // Compute 0 or -1, based on sign bit
327 Node *sign = phase->transform(new (phase->C, 3) RShiftLNode(dividend,phase->intcon(63)));
328 // Mask sign bit to the low sign bits
329 Node *round = phase->transform(new (phase->C, 3) AndLNode(sign,phase->longcon(i-1)));
330 // Round up before shifting
331 Node *sum = phase->transform(new (phase->C, 3) AddLNode(dividend,round));
332 // Shift for division
333 Node *result = new (phase->C, 3) RShiftLNode(sum, phase->intcon(log_i));
334 if (negate_res) {
335 result = phase->transform(result);
336 result = new (phase->C, 3) SubLNode(phase->longcon(0), result);
337 }
338
339 return result;
340 }
341
342 //------------------------------Value------------------------------------------
343 // A DivLNode divides its inputs. The third input is a Control input, used to
344 // prevent hoisting the divide above an unsafe test.
345 const Type *DivLNode::Value( PhaseTransform *phase ) const {
346 // Either input is TOP ==> the result is TOP
347 const Type *t1 = phase->type( in(1) );
348 const Type *t2 = phase->type( in(2) );
349 if( t1 == Type::TOP ) return Type::TOP;
350 if( t2 == Type::TOP ) return Type::TOP;
351
352 // x/x == 1 since we always generate the dynamic divisor check for 0.
353 if( phase->eqv( in(1), in(2) ) )
354 return TypeLong::ONE;
355
356 // Either input is BOTTOM ==> the result is the local BOTTOM
357 const Type *bot = bottom_type();
358 if( (t1 == bot) || (t2 == bot) ||
359 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
360 return bot;
361
362 // Divide the two numbers. We approximate.
363 // If divisor is a constant and not zero
364 const TypeLong *i1 = t1->is_long();
365 const TypeLong *i2 = t2->is_long();
366 int widen = MAX2(i1->_widen, i2->_widen);
367
368 if( i2->is_con() && i2->get_con() != 0 ) {
369 jlong d = i2->get_con(); // Divisor
370 jlong lo, hi;
371 if( d >= 0 ) {
372 lo = i1->_lo/d;
373 hi = i1->_hi/d;
374 } else {
375 if( d == CONST64(-1) && i1->_lo == min_jlong ) {
376 // 'min_jlong/-1' throws arithmetic exception during compilation
377 lo = min_jlong;
378 // do not support holes, 'hi' must go to either min_jlong or max_jlong:
379 // [min_jlong, -10]/[-1,-1] ==> [min_jlong] UNION [10,max_jlong]
380 hi = i1->_hi == min_jlong ? min_jlong : max_jlong;
381 } else {
382 lo = i1->_hi/d;
383 hi = i1->_lo/d;
384 }
385 }
386 return TypeLong::make(lo, hi, widen);
387 }
388
389 // If the dividend is a constant
390 if( i1->is_con() ) {
391 jlong d = i1->get_con();
392 if( d < 0 ) {
393 if( d == min_jlong ) {
394 // (-min_jlong) == min_jlong == (min_jlong / -1)
395 return TypeLong::make(min_jlong, max_jlong/2 + 1, widen);
396 } else {
397 return TypeLong::make(d, -d, widen);
398 }
399 }
400 return TypeLong::make(-d, d, widen);
401 }
402
403 // Otherwise we give up all hope
404 return TypeLong::LONG;
405 }
406
407
408 //=============================================================================
409 //------------------------------Value------------------------------------------
410 // An DivFNode divides its inputs. The third input is a Control input, used to
411 // prevent hoisting the divide above an unsafe test.
412 const Type *DivFNode::Value( PhaseTransform *phase ) const {
413 // Either input is TOP ==> the result is TOP
414 const Type *t1 = phase->type( in(1) );
415 const Type *t2 = phase->type( in(2) );
416 if( t1 == Type::TOP ) return Type::TOP;
417 if( t2 == Type::TOP ) return Type::TOP;
418
419 // Either input is BOTTOM ==> the result is the local BOTTOM
420 const Type *bot = bottom_type();
421 if( (t1 == bot) || (t2 == bot) ||
422 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
423 return bot;
424
425 // x/x == 1, we ignore 0/0.
426 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
427 // does not work for variables because of NaN's
428 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::FloatCon)
429 if (!g_isnan(t1->getf()) && g_isfinite(t1->getf()) && t1->getf() != 0.0) // could be negative ZERO or NaN
430 return TypeF::ONE;
431
432 if( t2 == TypeF::ONE )
433 return t1;
434
435 // If divisor is a constant and not zero, divide them numbers
436 if( t1->base() == Type::FloatCon &&
437 t2->base() == Type::FloatCon &&
438 t2->getf() != 0.0 ) // could be negative zero
439 return TypeF::make( t1->getf()/t2->getf() );
440
441 // If the dividend is a constant zero
442 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
443 // Test TypeF::ZERO is not sufficient as it could be negative zero
444
445 if( t1 == TypeF::ZERO && !g_isnan(t2->getf()) && t2->getf() != 0.0 )
446 return TypeF::ZERO;
447
448 // Otherwise we give up all hope
449 return Type::FLOAT;
450 }
451
452 //------------------------------isA_Copy---------------------------------------
453 // Dividing by self is 1.
454 // If the divisor is 1, we are an identity on the dividend.
455 Node *DivFNode::Identity( PhaseTransform *phase ) {
456 return (phase->type( in(2) ) == TypeF::ONE) ? in(1) : this;
457 }
458
459
460 //------------------------------Idealize---------------------------------------
461 Node *DivFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
462 if (in(0) && remove_dead_region(phase, can_reshape)) return this;
463
464 const Type *t2 = phase->type( in(2) );
465 if( t2 == TypeF::ONE ) // Identity?
466 return NULL; // Skip it
467
468 const TypeF *tf = t2->isa_float_constant();
469 if( !tf ) return NULL;
470 if( tf->base() != Type::FloatCon ) return NULL;
471
472 // Check for out of range values
473 if( tf->is_nan() || !tf->is_finite() ) return NULL;
474
475 // Get the value
476 float f = tf->getf();
477 int exp;
478
479 // Only for special case of dividing by a power of 2
480 if( frexp((double)f, &exp) != 0.5 ) return NULL;
481
482 // Limit the range of acceptable exponents
483 if( exp < -126 || exp > 126 ) return NULL;
484
485 // Compute the reciprocal
486 float reciprocal = ((float)1.0) / f;
487
488 assert( frexp((double)reciprocal, &exp) == 0.5, "reciprocal should be power of 2" );
489
490 // return multiplication by the reciprocal
491 return (new (phase->C, 3) MulFNode(in(1), phase->makecon(TypeF::make(reciprocal))));
492 }
493
494 //=============================================================================
495 //------------------------------Value------------------------------------------
496 // An DivDNode divides its inputs. The third input is a Control input, used to
497 // prvent hoisting the divide above an unsafe test.
498 const Type *DivDNode::Value( PhaseTransform *phase ) const {
499 // Either input is TOP ==> the result is TOP
500 const Type *t1 = phase->type( in(1) );
501 const Type *t2 = phase->type( in(2) );
502 if( t1 == Type::TOP ) return Type::TOP;
503 if( t2 == Type::TOP ) return Type::TOP;
504
505 // Either input is BOTTOM ==> the result is the local BOTTOM
506 const Type *bot = bottom_type();
507 if( (t1 == bot) || (t2 == bot) ||
508 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
509 return bot;
510
511 // x/x == 1, we ignore 0/0.
512 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
513 // Does not work for variables because of NaN's
514 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::DoubleCon)
515 if (!g_isnan(t1->getd()) && g_isfinite(t1->getd()) && t1->getd() != 0.0) // could be negative ZERO or NaN
516 return TypeD::ONE;
517
518 if( t2 == TypeD::ONE )
519 return t1;
520
521 // If divisor is a constant and not zero, divide them numbers
522 if( t1->base() == Type::DoubleCon &&
523 t2->base() == Type::DoubleCon &&
524 t2->getd() != 0.0 ) // could be negative zero
525 return TypeD::make( t1->getd()/t2->getd() );
526
527 // If the dividend is a constant zero
528 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
529 // Test TypeF::ZERO is not sufficient as it could be negative zero
530 if( t1 == TypeD::ZERO && !g_isnan(t2->getd()) && t2->getd() != 0.0 )
531 return TypeD::ZERO;
532
533 // Otherwise we give up all hope
534 return Type::DOUBLE;
535 }
536
537
538 //------------------------------isA_Copy---------------------------------------
539 // Dividing by self is 1.
540 // If the divisor is 1, we are an identity on the dividend.
541 Node *DivDNode::Identity( PhaseTransform *phase ) {
542 return (phase->type( in(2) ) == TypeD::ONE) ? in(1) : this;
543 }
544
545 //------------------------------Idealize---------------------------------------
546 Node *DivDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
547 if (in(0) && remove_dead_region(phase, can_reshape)) return this;
548
549 const Type *t2 = phase->type( in(2) );
550 if( t2 == TypeD::ONE ) // Identity?
551 return NULL; // Skip it
552
553 const TypeD *td = t2->isa_double_constant();
554 if( !td ) return NULL;
555 if( td->base() != Type::DoubleCon ) return NULL;
556
557 // Check for out of range values
558 if( td->is_nan() || !td->is_finite() ) return NULL;
559
560 // Get the value
561 double d = td->getd();
562 int exp;
563
564 // Only for special case of dividing by a power of 2
565 if( frexp(d, &exp) != 0.5 ) return NULL;
566
567 // Limit the range of acceptable exponents
568 if( exp < -1021 || exp > 1022 ) return NULL;
569
570 // Compute the reciprocal
571 double reciprocal = 1.0 / d;
572
573 assert( frexp(reciprocal, &exp) == 0.5, "reciprocal should be power of 2" );
574
575 // return multiplication by the reciprocal
576 return (new (phase->C, 3) MulDNode(in(1), phase->makecon(TypeD::make(reciprocal))));
577 }
578
579 //=============================================================================
580 //------------------------------Idealize---------------------------------------
581 Node *ModINode::Ideal(PhaseGVN *phase, bool can_reshape) {
582 // Check for dead control input
583 if( remove_dead_region(phase, can_reshape) ) return this;
584
585 // Get the modulus
586 const Type *t = phase->type( in(2) );
587 if( t == Type::TOP ) return NULL;
588 const TypeInt *ti = t->is_int();
589
590 // Check for useless control input
591 // Check for excluding mod-zero case
592 if( in(0) && (ti->_hi < 0 || ti->_lo > 0) ) {
593 set_req(0, NULL); // Yank control input
594 return this;
595 }
596
597 // See if we are MOD'ing by 2^k or 2^k-1.
598 if( !ti->is_con() ) return NULL;
599 jint con = ti->get_con();
600
601 Node *hook = new (phase->C, 1) Node(1);
602
603 // First, special check for modulo 2^k-1
604 if( con >= 0 && con < max_jint && is_power_of_2(con+1) ) {
605 uint k = exact_log2(con+1); // Extract k
606
607 // Basic algorithm by David Detlefs. See fastmod_int.java for gory details.
608 static int unroll_factor[] = { 999, 999, 29, 14, 9, 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/};
609 int trip_count = 1;
610 if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k];
611
612 // If the unroll factor is not too large, and if conditional moves are
613 // ok, then use this case
614 if( trip_count <= 5 && ConditionalMoveLimit != 0 ) {
615 Node *x = in(1); // Value being mod'd
616 Node *divisor = in(2); // Also is mask
617
618 hook->init_req(0, x); // Add a use to x to prevent him from dying
619 // Generate code to reduce X rapidly to nearly 2^k-1.
620 for( int i = 0; i < trip_count; i++ ) {
621 Node *xl = phase->transform( new (phase->C, 3) AndINode(x,divisor) );
622 Node *xh = phase->transform( new (phase->C, 3) RShiftINode(x,phase->intcon(k)) ); // Must be signed
623 x = phase->transform( new (phase->C, 3) AddINode(xh,xl) );
624 hook->set_req(0, x);
625 }
626
627 // Generate sign-fixup code. Was original value positive?
628 // int hack_res = (i >= 0) ? divisor : 1;
629 Node *cmp1 = phase->transform( new (phase->C, 3) CmpINode( in(1), phase->intcon(0) ) );
630 Node *bol1 = phase->transform( new (phase->C, 2) BoolNode( cmp1, BoolTest::ge ) );
631 Node *cmov1= phase->transform( new (phase->C, 4) CMoveINode(bol1, phase->intcon(1), divisor, TypeInt::POS) );
632 // if( x >= hack_res ) x -= divisor;
633 Node *sub = phase->transform( new (phase->C, 3) SubINode( x, divisor ) );
634 Node *cmp2 = phase->transform( new (phase->C, 3) CmpINode( x, cmov1 ) );
635 Node *bol2 = phase->transform( new (phase->C, 2) BoolNode( cmp2, BoolTest::ge ) );
636 // Convention is to not transform the return value of an Ideal
637 // since Ideal is expected to return a modified 'this' or a new node.
638 Node *cmov2= new (phase->C, 4) CMoveINode(bol2, x, sub, TypeInt::INT);
639 // cmov2 is now the mod
640
641 // Now remove the bogus extra edges used to keep things alive
642 if (can_reshape) {
643 phase->is_IterGVN()->remove_dead_node(hook);
644 } else {
645 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
646 }
647 return cmov2;
648 }
649 }
650
651 // Fell thru, the unroll case is not appropriate. Transform the modulo
652 // into a long multiply/int multiply/subtract case
653
654 // Cannot handle mod 0, and min_jint isn't handled by the transform
655 if( con == 0 || con == min_jint ) return NULL;
656
657 // Get the absolute value of the constant; at this point, we can use this
658 jint pos_con = (con >= 0) ? con : -con;
659
660 // integer Mod 1 is always 0
661 if( pos_con == 1 ) return new (phase->C, 1) ConINode(TypeInt::ZERO);
662
663 int log2_con = -1;
664
665 // If this is a power of two, they maybe we can mask it
666 if( is_power_of_2(pos_con) ) {
667 log2_con = log2_intptr((intptr_t)pos_con);
668
669 const Type *dt = phase->type(in(1));
670 const TypeInt *dti = dt->isa_int();
671
672 // See if this can be masked, if the dividend is non-negative
673 if( dti && dti->_lo >= 0 )
674 return ( new (phase->C, 3) AndINode( in(1), phase->intcon( pos_con-1 ) ) );
675 }
676
677 // Save in(1) so that it cannot be changed or deleted
678 hook->init_req(0, in(1));
679
680 // Divide using the transform from DivI to MulL
681 Node *divide = phase->transform( transform_int_divide_to_long_multiply( phase, in(1), pos_con ) );
682
683 // Re-multiply, using a shift if this is a power of two
684 Node *mult = NULL;
685
686 if( log2_con >= 0 )
687 mult = phase->transform( new (phase->C, 3) LShiftINode( divide, phase->intcon( log2_con ) ) );
688 else
689 mult = phase->transform( new (phase->C, 3) MulINode( divide, phase->intcon( pos_con ) ) );
690
691 // Finally, subtract the multiplied divided value from the original
692 Node *result = new (phase->C, 3) SubINode( in(1), mult );
693
694 // Now remove the bogus extra edges used to keep things alive
695 if (can_reshape) {
696 phase->is_IterGVN()->remove_dead_node(hook);
697 } else {
698 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
699 }
700
701 // return the value
702 return result;
703 }
704
705 //------------------------------Value------------------------------------------
706 const Type *ModINode::Value( PhaseTransform *phase ) const {
707 // Either input is TOP ==> the result is TOP
708 const Type *t1 = phase->type( in(1) );
709 const Type *t2 = phase->type( in(2) );
710 if( t1 == Type::TOP ) return Type::TOP;
711 if( t2 == Type::TOP ) return Type::TOP;
712
713 // We always generate the dynamic check for 0.
714 // 0 MOD X is 0
715 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
716 // X MOD X is 0
717 if( phase->eqv( in(1), in(2) ) ) return TypeInt::ZERO;
718
719 // Either input is BOTTOM ==> the result is the local BOTTOM
720 const Type *bot = bottom_type();
721 if( (t1 == bot) || (t2 == bot) ||
722 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
723 return bot;
724
725 const TypeInt *i1 = t1->is_int();
726 const TypeInt *i2 = t2->is_int();
727 if( !i1->is_con() || !i2->is_con() ) {
728 if( i1->_lo >= 0 && i2->_lo >= 0 )
729 return TypeInt::POS;
730 // If both numbers are not constants, we know little.
731 return TypeInt::INT;
732 }
733 // Mod by zero? Throw exception at runtime!
734 if( !i2->get_con() ) return TypeInt::POS;
735
736 // We must be modulo'ing 2 float constants.
737 // Check for min_jint % '-1', result is defined to be '0'.
738 if( i1->get_con() == min_jint && i2->get_con() == -1 )
739 return TypeInt::ZERO;
740
741 return TypeInt::make( i1->get_con() % i2->get_con() );
742 }
743
744
745 //=============================================================================
746 //------------------------------Idealize---------------------------------------
747 Node *ModLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
748 // Check for dead control input
749 if( remove_dead_region(phase, can_reshape) ) return this;
750
751 // Get the modulus
752 const Type *t = phase->type( in(2) );
753 if( t == Type::TOP ) return NULL;
754 const TypeLong *ti = t->is_long();
755
756 // Check for useless control input
757 // Check for excluding mod-zero case
758 if( in(0) && (ti->_hi < 0 || ti->_lo > 0) ) {
759 set_req(0, NULL); // Yank control input
760 return this;
761 }
762
763 // See if we are MOD'ing by 2^k or 2^k-1.
764 if( !ti->is_con() ) return NULL;
765 jlong con = ti->get_con();
766 bool m1 = false;
767 if( !is_power_of_2_long(con) ) { // Not 2^k
768 if( !is_power_of_2_long(con+1) ) // Not 2^k-1?
769 return NULL; // No interesting mod hacks
770 m1 = true; // Found 2^k-1
771 con++; // Convert to 2^k form
772 }
773 uint k = log2_long(con); // Extract k
774
775 // Expand mod
776 if( !m1 ) { // Case 2^k
777 } else { // Case 2^k-1
778 // Basic algorithm by David Detlefs. See fastmod_long.java for gory details.
779 // Used to help a popular random number generator which does a long-mod
780 // of 2^31-1 and shows up in SpecJBB and SciMark.
781 static int unroll_factor[] = { 999, 999, 61, 30, 20, 15, 12, 10, 8, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/};
782 int trip_count = 1;
783 if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k];
784 if( trip_count > 4 ) return NULL; // Too much unrolling
785 if (ConditionalMoveLimit == 0) return NULL; // cmov is required
786
787 Node *x = in(1); // Value being mod'd
788 Node *divisor = in(2); // Also is mask
789
790 Node *hook = new (phase->C, 1) Node(x);
791 // Generate code to reduce X rapidly to nearly 2^k-1.
792 for( int i = 0; i < trip_count; i++ ) {
793 Node *xl = phase->transform( new (phase->C, 3) AndLNode(x,divisor) );
794 Node *xh = phase->transform( new (phase->C, 3) RShiftLNode(x,phase->intcon(k)) ); // Must be signed
795 x = phase->transform( new (phase->C, 3) AddLNode(xh,xl) );
796 hook->set_req(0, x); // Add a use to x to prevent him from dying
797 }
798 // Generate sign-fixup code. Was original value positive?
799 // long hack_res = (i >= 0) ? divisor : CONST64(1);
800 Node *cmp1 = phase->transform( new (phase->C, 3) CmpLNode( in(1), phase->longcon(0) ) );
801 Node *bol1 = phase->transform( new (phase->C, 2) BoolNode( cmp1, BoolTest::ge ) );
802 Node *cmov1= phase->transform( new (phase->C, 4) CMoveLNode(bol1, phase->longcon(1), divisor, TypeLong::LONG) );
803 // if( x >= hack_res ) x -= divisor;
804 Node *sub = phase->transform( new (phase->C, 3) SubLNode( x, divisor ) );
805 Node *cmp2 = phase->transform( new (phase->C, 3) CmpLNode( x, cmov1 ) );
806 Node *bol2 = phase->transform( new (phase->C, 2) BoolNode( cmp2, BoolTest::ge ) );
807 // Convention is to not transform the return value of an Ideal
808 // since Ideal is expected to return a modified 'this' or a new node.
809 Node *cmov2= new (phase->C, 4) CMoveLNode(bol2, x, sub, TypeLong::LONG);
810 // cmov2 is now the mod
811
812 // Now remove the bogus extra edges used to keep things alive
813 if (can_reshape) {
814 phase->is_IterGVN()->remove_dead_node(hook);
815 } else {
816 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
817 }
818 return cmov2;
819 }
820 return NULL;
821 }
822
823 //------------------------------Value------------------------------------------
824 const Type *ModLNode::Value( PhaseTransform *phase ) const {
825 // Either input is TOP ==> the result is TOP
826 const Type *t1 = phase->type( in(1) );
827 const Type *t2 = phase->type( in(2) );
828 if( t1 == Type::TOP ) return Type::TOP;
829 if( t2 == Type::TOP ) return Type::TOP;
830
831 // We always generate the dynamic check for 0.
832 // 0 MOD X is 0
833 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
834 // X MOD X is 0
835 if( phase->eqv( in(1), in(2) ) ) return TypeLong::ZERO;
836
837 // Either input is BOTTOM ==> the result is the local BOTTOM
838 const Type *bot = bottom_type();
839 if( (t1 == bot) || (t2 == bot) ||
840 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
841 return bot;
842
843 const TypeLong *i1 = t1->is_long();
844 const TypeLong *i2 = t2->is_long();
845 if( !i1->is_con() || !i2->is_con() ) {
846 if( i1->_lo >= CONST64(0) && i2->_lo >= CONST64(0) )
847 return TypeLong::POS;
848 // If both numbers are not constants, we know little.
849 return TypeLong::LONG;
850 }
851 // Mod by zero? Throw exception at runtime!
852 if( !i2->get_con() ) return TypeLong::POS;
853
854 // We must be modulo'ing 2 float constants.
855 // Check for min_jint % '-1', result is defined to be '0'.
856 if( i1->get_con() == min_jlong && i2->get_con() == -1 )
857 return TypeLong::ZERO;
858
859 return TypeLong::make( i1->get_con() % i2->get_con() );
860 }
861
862
863 //=============================================================================
864 //------------------------------Value------------------------------------------
865 const Type *ModFNode::Value( PhaseTransform *phase ) const {
866 // Either input is TOP ==> the result is TOP
867 const Type *t1 = phase->type( in(1) );
868 const Type *t2 = phase->type( in(2) );
869 if( t1 == Type::TOP ) return Type::TOP;
870 if( t2 == Type::TOP ) return Type::TOP;
871
872 // Either input is BOTTOM ==> the result is the local BOTTOM
873 const Type *bot = bottom_type();
874 if( (t1 == bot) || (t2 == bot) ||
875 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
876 return bot;
877
878 // If either is a NaN, return an input NaN
879 if( g_isnan(t1->getf()) ) return t1;
880 if( g_isnan(t2->getf()) ) return t2;
881
882 // It is not worth trying to constant fold this stuff!
883 return Type::FLOAT;
884
885 /*
886 // If dividend is infinity or divisor is zero, or both, the result is NaN
887 if( !g_isfinite(t1->getf()) || ((t2->getf() == 0.0) || (jint_cast(t2->getf()) == 0x80000000)) )
888
889 // X MOD infinity = X
890 if( !g_isfinite(t2->getf()) && !g_isnan(t2->getf()) ) return t1;
891 // 0 MOD finite = dividend (positive or negative zero)
892 // Not valid for: NaN MOD any; any MOD nan; 0 MOD 0; or for 0 MOD NaN
893 // NaNs are handled previously.
894 if( !(t2->getf() == 0.0) && !((int)t2->getf() == 0x80000000)) {
895 if (((t1->getf() == 0.0) || ((int)t1->getf() == 0x80000000)) && g_isfinite(t2->getf()) ) {
896 return t1;
897 }
898 }
899 // X MOD X is 0
900 // Does not work for variables because of NaN's
901 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::FloatCon)
902 if (!g_isnan(t1->getf()) && (t1->getf() != 0.0) && ((int)t1->getf() != 0x80000000)) {
903 if(t1->getf() < 0.0) {
904 float result = jfloat_cast(0x80000000);
905 return TypeF::make( result );
906 }
907 else
908 return TypeF::ZERO;
909 }
910
911 // If both numbers are not constants, we know nothing.
912 if( (t1->base() != Type::FloatCon) || (t2->base() != Type::FloatCon) )
913 return Type::FLOAT;
914
915 // We must be modulo'ing 2 float constants.
916 // Make sure that the sign of the fmod is equal to the sign of the dividend
917 float result = (float)fmod( t1->getf(), t2->getf() );
918 float dividend = t1->getf();
919 if( (dividend < 0.0) || ((int)dividend == 0x80000000) ) {
920 if( result > 0.0 )
921 result = 0.0 - result;
922 else if( result == 0.0 ) {
923 result = jfloat_cast(0x80000000);
924 }
925 }
926 return TypeF::make( result );
927 */
928 }
929
930
931 //=============================================================================
932 //------------------------------Value------------------------------------------
933 const Type *ModDNode::Value( PhaseTransform *phase ) const {
934 // Either input is TOP ==> the result is TOP
935 const Type *t1 = phase->type( in(1) );
936 const Type *t2 = phase->type( in(2) );
937 if( t1 == Type::TOP ) return Type::TOP;
938 if( t2 == Type::TOP ) return Type::TOP;
939
940 // Either input is BOTTOM ==> the result is the local BOTTOM
941 const Type *bot = bottom_type();
942 if( (t1 == bot) || (t2 == bot) ||
943 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
944 return bot;
945
946 // If either is a NaN, return an input NaN
947 if( g_isnan(t1->getd()) ) return t1;
948 if( g_isnan(t2->getd()) ) return t2;
949 // X MOD infinity = X
950 if( !g_isfinite(t2->getd())) return t1;
951 // 0 MOD finite = dividend (positive or negative zero)
952 // Not valid for: NaN MOD any; any MOD nan; 0 MOD 0; or for 0 MOD NaN
953 // NaNs are handled previously.
954 if( !(t2->getd() == 0.0) ) {
955 if( t1->getd() == 0.0 && g_isfinite(t2->getd()) ) {
956 return t1;
957 }
958 }
959
960 // X MOD X is 0
961 // does not work for variables because of NaN's
962 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::DoubleCon )
963 if (!g_isnan(t1->getd()) && t1->getd() != 0.0)
964 return TypeD::ZERO;
965
966
967 // If both numbers are not constants, we know nothing.
968 if( (t1->base() != Type::DoubleCon) || (t2->base() != Type::DoubleCon) )
969 return Type::DOUBLE;
970
971 // We must be modulo'ing 2 double constants.
972 return TypeD::make( fmod( t1->getd(), t2->getd() ) );
973 }
974
975 //=============================================================================
976
977 DivModNode::DivModNode( Node *c, Node *dividend, Node *divisor ) : MultiNode(3) {
978 init_req(0, c);
979 init_req(1, dividend);
980 init_req(2, divisor);
981 }
982
983 //------------------------------make------------------------------------------
984 DivModINode* DivModINode::make(Compile* C, Node* div_or_mod) {
985 Node* n = div_or_mod;
986 assert(n->Opcode() == Op_DivI || n->Opcode() == Op_ModI,
987 "only div or mod input pattern accepted");
988
989 DivModINode* divmod = new (C, 3) DivModINode(n->in(0), n->in(1), n->in(2));
990 Node* dproj = new (C, 1) ProjNode(divmod, DivModNode::div_proj_num);
991 Node* mproj = new (C, 1) ProjNode(divmod, DivModNode::mod_proj_num);
992 return divmod;
993 }
994
995 //------------------------------make------------------------------------------
996 DivModLNode* DivModLNode::make(Compile* C, Node* div_or_mod) {
997 Node* n = div_or_mod;
998 assert(n->Opcode() == Op_DivL || n->Opcode() == Op_ModL,
999 "only div or mod input pattern accepted");
1000
1001 DivModLNode* divmod = new (C, 3) DivModLNode(n->in(0), n->in(1), n->in(2));
1002 Node* dproj = new (C, 1) ProjNode(divmod, DivModNode::div_proj_num);
1003 Node* mproj = new (C, 1) ProjNode(divmod, DivModNode::mod_proj_num);
1004 return divmod;
1005 }
1006
1007 //------------------------------match------------------------------------------
1008 // return result(s) along with their RegMask info
1009 Node *DivModINode::match( const ProjNode *proj, const Matcher *match ) {
1010 uint ideal_reg = proj->ideal_reg();
1011 RegMask rm;
1012 if (proj->_con == div_proj_num) {
1013 rm = match->divI_proj_mask();
1014 } else {
1015 assert(proj->_con == mod_proj_num, "must be div or mod projection");
1016 rm = match->modI_proj_mask();
1017 }
1018 return new (match->C, 1)MachProjNode(this, proj->_con, rm, ideal_reg);
1019 }
1020
1021
1022 //------------------------------match------------------------------------------
1023 // return result(s) along with their RegMask info
1024 Node *DivModLNode::match( const ProjNode *proj, const Matcher *match ) {
1025 uint ideal_reg = proj->ideal_reg();
1026 RegMask rm;
1027 if (proj->_con == div_proj_num) {
1028 rm = match->divL_proj_mask();
1029 } else {
1030 assert(proj->_con == mod_proj_num, "must be div or mod projection");
1031 rm = match->modL_proj_mask();
1032 }
1033 return new (match->C, 1)MachProjNode(this, proj->_con, rm, ideal_reg);
1034 }