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