1 /* Operations with long integers.
2 Copyright (C) 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
23 #include "tm.h" /* For SHIFT_COUNT_TRUNCATED. */
27 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
28 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
29 and SUM1. Then this yields nonzero if overflow occurred during the
32 Overflow occurs if A and B have the same sign, but A and SUM differ in
33 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
35 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
37 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
38 We do that by representing the two-word integer in 4 words, with only
39 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
40 number. The value of the word is LOWPART + HIGHPART * BASE. */
43 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
45 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
46 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
48 /* Unpack a two-word integer into 4 words.
49 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
50 WORDS points to the array of HOST_WIDE_INTs. */
53 encode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT low
, HOST_WIDE_INT hi
)
55 words
[0] = LOWPART (low
);
56 words
[1] = HIGHPART (low
);
57 words
[2] = LOWPART (hi
);
58 words
[3] = HIGHPART (hi
);
61 /* Pack an array of 4 words into a two-word integer.
62 WORDS points to the array of words.
63 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
66 decode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT
*low
,
69 *low
= words
[0] + words
[1] * BASE
;
70 *hi
= words
[2] + words
[3] * BASE
;
73 /* Add two doubleword integers with doubleword result.
74 Return nonzero if the operation overflows according to UNSIGNED_P.
75 Each argument is given as two `HOST_WIDE_INT' pieces.
76 One argument is L1 and H1; the other, L2 and H2.
77 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
80 add_double_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
81 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
82 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
85 unsigned HOST_WIDE_INT l
;
89 h
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) h1
90 + (unsigned HOST_WIDE_INT
) h2
97 return ((unsigned HOST_WIDE_INT
) h
< (unsigned HOST_WIDE_INT
) h1
101 return OVERFLOW_SUM_SIGN (h1
, h2
, h
);
104 /* Negate a doubleword integer with doubleword result.
105 Return nonzero if the operation overflows, assuming it's signed.
106 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
107 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
110 neg_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
111 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
)
117 return (*hv
& h1
) < 0;
127 /* Multiply two doubleword integers with doubleword result.
128 Return nonzero if the operation overflows according to UNSIGNED_P.
129 Each argument is given as two `HOST_WIDE_INT' pieces.
130 One argument is L1 and H1; the other, L2 and H2.
131 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
134 mul_double_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
135 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
136 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
139 HOST_WIDE_INT arg1
[4];
140 HOST_WIDE_INT arg2
[4];
141 HOST_WIDE_INT prod
[4 * 2];
142 unsigned HOST_WIDE_INT carry
;
144 unsigned HOST_WIDE_INT toplow
, neglow
;
145 HOST_WIDE_INT tophigh
, neghigh
;
147 encode (arg1
, l1
, h1
);
148 encode (arg2
, l2
, h2
);
150 memset (prod
, 0, sizeof prod
);
152 for (i
= 0; i
< 4; i
++)
155 for (j
= 0; j
< 4; j
++)
158 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
159 carry
+= arg1
[i
] * arg2
[j
];
160 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
162 prod
[k
] = LOWPART (carry
);
163 carry
= HIGHPART (carry
);
168 decode (prod
, lv
, hv
);
169 decode (prod
+ 4, &toplow
, &tophigh
);
171 /* Unsigned overflow is immediate. */
173 return (toplow
| tophigh
) != 0;
175 /* Check for signed overflow by calculating the signed representation of the
176 top half of the result; it should agree with the low half's sign bit. */
179 neg_double (l2
, h2
, &neglow
, &neghigh
);
180 add_double (neglow
, neghigh
, toplow
, tophigh
, &toplow
, &tophigh
);
184 neg_double (l1
, h1
, &neglow
, &neghigh
);
185 add_double (neglow
, neghigh
, toplow
, tophigh
, &toplow
, &tophigh
);
187 return (*hv
< 0 ? ~(toplow
& tophigh
) : toplow
| tophigh
) != 0;
190 /* Shift the doubleword integer in L1, H1 left by COUNT places
191 keeping only PREC bits of result.
192 Shift right if COUNT is negative.
193 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
194 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
197 lshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
198 HOST_WIDE_INT count
, unsigned int prec
,
199 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
, bool arith
)
201 unsigned HOST_WIDE_INT signmask
;
205 rshift_double (l1
, h1
, -count
, prec
, lv
, hv
, arith
);
209 if (SHIFT_COUNT_TRUNCATED
)
212 if (count
>= 2 * HOST_BITS_PER_WIDE_INT
)
214 /* Shifting by the host word size is undefined according to the
215 ANSI standard, so we must handle this as a special case. */
219 else if (count
>= HOST_BITS_PER_WIDE_INT
)
221 *hv
= l1
<< (count
- HOST_BITS_PER_WIDE_INT
);
226 *hv
= (((unsigned HOST_WIDE_INT
) h1
<< count
)
227 | (l1
>> (HOST_BITS_PER_WIDE_INT
- count
- 1) >> 1));
231 /* Sign extend all bits that are beyond the precision. */
233 signmask
= -((prec
> HOST_BITS_PER_WIDE_INT
234 ? ((unsigned HOST_WIDE_INT
) *hv
235 >> (prec
- HOST_BITS_PER_WIDE_INT
- 1))
236 : (*lv
>> (prec
- 1))) & 1);
238 if (prec
>= 2 * HOST_BITS_PER_WIDE_INT
)
240 else if (prec
>= HOST_BITS_PER_WIDE_INT
)
242 *hv
&= ~((HOST_WIDE_INT
) (-1) << (prec
- HOST_BITS_PER_WIDE_INT
));
243 *hv
|= signmask
<< (prec
- HOST_BITS_PER_WIDE_INT
);
248 *lv
&= ~((unsigned HOST_WIDE_INT
) (-1) << prec
);
249 *lv
|= signmask
<< prec
;
253 /* Shift the doubleword integer in L1, H1 right by COUNT places
254 keeping only PREC bits of result. Shift left if COUNT is negative.
255 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
256 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
259 rshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
260 HOST_WIDE_INT count
, unsigned int prec
,
261 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
264 unsigned HOST_WIDE_INT signmask
;
268 lshift_double (l1
, h1
, -count
, prec
, lv
, hv
, arith
);
273 ? -((unsigned HOST_WIDE_INT
) h1
>> (HOST_BITS_PER_WIDE_INT
- 1))
276 if (SHIFT_COUNT_TRUNCATED
)
279 if (count
>= 2 * HOST_BITS_PER_WIDE_INT
)
281 /* Shifting by the host word size is undefined according to the
282 ANSI standard, so we must handle this as a special case. */
286 else if (count
>= HOST_BITS_PER_WIDE_INT
)
289 *lv
= (unsigned HOST_WIDE_INT
) h1
>> (count
- HOST_BITS_PER_WIDE_INT
);
293 *hv
= (unsigned HOST_WIDE_INT
) h1
>> count
;
295 | ((unsigned HOST_WIDE_INT
) h1
296 << (HOST_BITS_PER_WIDE_INT
- count
- 1) << 1));
299 /* Zero / sign extend all bits that are beyond the precision. */
301 if (count
>= (HOST_WIDE_INT
)prec
)
306 else if ((prec
- count
) >= 2 * HOST_BITS_PER_WIDE_INT
)
308 else if ((prec
- count
) >= HOST_BITS_PER_WIDE_INT
)
310 *hv
&= ~((HOST_WIDE_INT
) (-1) << (prec
- count
- HOST_BITS_PER_WIDE_INT
));
311 *hv
|= signmask
<< (prec
- count
- HOST_BITS_PER_WIDE_INT
);
316 *lv
&= ~((unsigned HOST_WIDE_INT
) (-1) << (prec
- count
));
317 *lv
|= signmask
<< (prec
- count
);
321 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
322 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
323 CODE is a tree code for a kind of division, one of
324 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
326 It controls how the quotient is rounded to an integer.
327 Return nonzero if the operation overflows.
328 UNS nonzero says do unsigned division. */
331 div_and_round_double (unsigned code
, int uns
,
332 /* num == numerator == dividend */
333 unsigned HOST_WIDE_INT lnum_orig
,
334 HOST_WIDE_INT hnum_orig
,
335 /* den == denominator == divisor */
336 unsigned HOST_WIDE_INT lden_orig
,
337 HOST_WIDE_INT hden_orig
,
338 unsigned HOST_WIDE_INT
*lquo
,
339 HOST_WIDE_INT
*hquo
, unsigned HOST_WIDE_INT
*lrem
,
343 HOST_WIDE_INT num
[4 + 1]; /* extra element for scaling. */
344 HOST_WIDE_INT den
[4], quo
[4];
346 unsigned HOST_WIDE_INT work
;
347 unsigned HOST_WIDE_INT carry
= 0;
348 unsigned HOST_WIDE_INT lnum
= lnum_orig
;
349 HOST_WIDE_INT hnum
= hnum_orig
;
350 unsigned HOST_WIDE_INT lden
= lden_orig
;
351 HOST_WIDE_INT hden
= hden_orig
;
354 if (hden
== 0 && lden
== 0)
355 overflow
= 1, lden
= 1;
357 /* Calculate quotient sign and convert operands to unsigned. */
363 /* (minimum integer) / (-1) is the only overflow case. */
364 if (neg_double (lnum
, hnum
, &lnum
, &hnum
)
365 && ((HOST_WIDE_INT
) lden
& hden
) == -1)
371 neg_double (lden
, hden
, &lden
, &hden
);
375 if (hnum
== 0 && hden
== 0)
376 { /* single precision */
378 /* This unsigned division rounds toward zero. */
384 { /* trivial case: dividend < divisor */
385 /* hden != 0 already checked. */
392 memset (quo
, 0, sizeof quo
);
394 memset (num
, 0, sizeof num
); /* to zero 9th element */
395 memset (den
, 0, sizeof den
);
397 encode (num
, lnum
, hnum
);
398 encode (den
, lden
, hden
);
400 /* Special code for when the divisor < BASE. */
401 if (hden
== 0 && lden
< (unsigned HOST_WIDE_INT
) BASE
)
403 /* hnum != 0 already checked. */
404 for (i
= 4 - 1; i
>= 0; i
--)
406 work
= num
[i
] + carry
* BASE
;
407 quo
[i
] = work
/ lden
;
413 /* Full double precision division,
414 with thanks to Don Knuth's "Seminumerical Algorithms". */
415 int num_hi_sig
, den_hi_sig
;
416 unsigned HOST_WIDE_INT quo_est
, scale
;
418 /* Find the highest nonzero divisor digit. */
419 for (i
= 4 - 1;; i
--)
426 /* Insure that the first digit of the divisor is at least BASE/2.
427 This is required by the quotient digit estimation algorithm. */
429 scale
= BASE
/ (den
[den_hi_sig
] + 1);
431 { /* scale divisor and dividend */
433 for (i
= 0; i
<= 4 - 1; i
++)
435 work
= (num
[i
] * scale
) + carry
;
436 num
[i
] = LOWPART (work
);
437 carry
= HIGHPART (work
);
442 for (i
= 0; i
<= 4 - 1; i
++)
444 work
= (den
[i
] * scale
) + carry
;
445 den
[i
] = LOWPART (work
);
446 carry
= HIGHPART (work
);
447 if (den
[i
] != 0) den_hi_sig
= i
;
454 for (i
= num_hi_sig
- den_hi_sig
- 1; i
>= 0; i
--)
456 /* Guess the next quotient digit, quo_est, by dividing the first
457 two remaining dividend digits by the high order quotient digit.
458 quo_est is never low and is at most 2 high. */
459 unsigned HOST_WIDE_INT tmp
;
461 num_hi_sig
= i
+ den_hi_sig
+ 1;
462 work
= num
[num_hi_sig
] * BASE
+ num
[num_hi_sig
- 1];
463 if (num
[num_hi_sig
] != den
[den_hi_sig
])
464 quo_est
= work
/ den
[den_hi_sig
];
468 /* Refine quo_est so it's usually correct, and at most one high. */
469 tmp
= work
- quo_est
* den
[den_hi_sig
];
471 && (den
[den_hi_sig
- 1] * quo_est
472 > (tmp
* BASE
+ num
[num_hi_sig
- 2])))
475 /* Try QUO_EST as the quotient digit, by multiplying the
476 divisor by QUO_EST and subtracting from the remaining dividend.
477 Keep in mind that QUO_EST is the I - 1st digit. */
480 for (j
= 0; j
<= den_hi_sig
; j
++)
482 work
= quo_est
* den
[j
] + carry
;
483 carry
= HIGHPART (work
);
484 work
= num
[i
+ j
] - LOWPART (work
);
485 num
[i
+ j
] = LOWPART (work
);
486 carry
+= HIGHPART (work
) != 0;
489 /* If quo_est was high by one, then num[i] went negative and
490 we need to correct things. */
491 if (num
[num_hi_sig
] < (HOST_WIDE_INT
) carry
)
494 carry
= 0; /* add divisor back in */
495 for (j
= 0; j
<= den_hi_sig
; j
++)
497 work
= num
[i
+ j
] + den
[j
] + carry
;
498 carry
= HIGHPART (work
);
499 num
[i
+ j
] = LOWPART (work
);
502 num
[num_hi_sig
] += carry
;
505 /* Store the quotient digit. */
510 decode (quo
, lquo
, hquo
);
513 /* If result is negative, make it so. */
515 neg_double (*lquo
, *hquo
, lquo
, hquo
);
517 /* Compute trial remainder: rem = num - (quo * den) */
518 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
519 neg_double (*lrem
, *hrem
, lrem
, hrem
);
520 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
525 case TRUNC_MOD_EXPR
: /* round toward zero */
526 case EXACT_DIV_EXPR
: /* for this one, it shouldn't matter */
530 case FLOOR_MOD_EXPR
: /* round toward negative infinity */
531 if (quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio < 0 && rem != 0 */
534 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) -1, (HOST_WIDE_INT
) -1,
542 case CEIL_MOD_EXPR
: /* round toward positive infinity */
543 if (!quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio > 0 && rem != 0 */
545 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) 1, (HOST_WIDE_INT
) 0,
553 case ROUND_MOD_EXPR
: /* round to closest integer */
555 unsigned HOST_WIDE_INT labs_rem
= *lrem
;
556 HOST_WIDE_INT habs_rem
= *hrem
;
557 unsigned HOST_WIDE_INT labs_den
= lden
, ltwice
;
558 HOST_WIDE_INT habs_den
= hden
, htwice
;
560 /* Get absolute values. */
562 neg_double (*lrem
, *hrem
, &labs_rem
, &habs_rem
);
564 neg_double (lden
, hden
, &labs_den
, &habs_den
);
566 /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient. */
567 mul_double ((HOST_WIDE_INT
) 2, (HOST_WIDE_INT
) 0,
568 labs_rem
, habs_rem
, <wice
, &htwice
);
570 if (((unsigned HOST_WIDE_INT
) habs_den
571 < (unsigned HOST_WIDE_INT
) htwice
)
572 || (((unsigned HOST_WIDE_INT
) habs_den
573 == (unsigned HOST_WIDE_INT
) htwice
)
574 && (labs_den
<= ltwice
)))
578 add_double (*lquo
, *hquo
,
579 (HOST_WIDE_INT
) -1, (HOST_WIDE_INT
) -1, lquo
, hquo
);
582 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) 1, (HOST_WIDE_INT
) 0,
594 /* Compute true remainder: rem = num - (quo * den) */
595 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
596 neg_double (*lrem
, *hrem
, lrem
, hrem
);
597 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
602 /* Returns mask for PREC bits. */
605 double_int_mask (unsigned prec
)
607 unsigned HOST_WIDE_INT m
;
610 if (prec
> HOST_BITS_PER_WIDE_INT
)
612 prec
-= HOST_BITS_PER_WIDE_INT
;
613 m
= ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1;
614 mask
.high
= (HOST_WIDE_INT
) m
;
620 mask
.low
= ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1;
626 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
627 outside of the precision are set to the sign bit (i.e., the PREC-th one),
628 otherwise they are set to zero.
630 This corresponds to returning the value represented by PREC lowermost bits
631 of CST, with the given signedness. */
634 double_int_ext (double_int cst
, unsigned prec
, bool uns
)
637 return double_int_zext (cst
, prec
);
639 return double_int_sext (cst
, prec
);
642 /* The same as double_int_ext with UNS = true. */
645 double_int_zext (double_int cst
, unsigned prec
)
647 double_int mask
= double_int_mask (prec
);
650 r
.low
= cst
.low
& mask
.low
;
651 r
.high
= cst
.high
& mask
.high
;
656 /* The same as double_int_ext with UNS = false. */
659 double_int_sext (double_int cst
, unsigned prec
)
661 double_int mask
= double_int_mask (prec
);
663 unsigned HOST_WIDE_INT snum
;
665 if (prec
<= HOST_BITS_PER_WIDE_INT
)
669 prec
-= HOST_BITS_PER_WIDE_INT
;
670 snum
= (unsigned HOST_WIDE_INT
) cst
.high
;
672 if (((snum
>> (prec
- 1)) & 1) == 1)
674 r
.low
= cst
.low
| ~mask
.low
;
675 r
.high
= cst
.high
| ~mask
.high
;
679 r
.low
= cst
.low
& mask
.low
;
680 r
.high
= cst
.high
& mask
.high
;
686 /* Returns true if CST fits in signed HOST_WIDE_INT. */
689 double_int_fits_in_shwi_p (double_int cst
)
692 return (HOST_WIDE_INT
) cst
.low
>= 0;
693 else if (cst
.high
== -1)
694 return (HOST_WIDE_INT
) cst
.low
< 0;
699 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
700 unsigned HOST_WIDE_INT if UNS is true. */
703 double_int_fits_in_hwi_p (double_int cst
, bool uns
)
706 return double_int_fits_in_uhwi_p (cst
);
708 return double_int_fits_in_shwi_p (cst
);
714 double_int_mul (double_int a
, double_int b
)
717 mul_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
721 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
722 *OVERFLOW is set to nonzero. */
725 double_int_mul_with_sign (double_int a
, double_int b
,
726 bool unsigned_p
, int *overflow
)
729 *overflow
= mul_double_with_sign (a
.low
, a
.high
, b
.low
, b
.high
,
730 &ret
.low
, &ret
.high
, unsigned_p
);
737 double_int_add (double_int a
, double_int b
)
740 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
747 double_int_sub (double_int a
, double_int b
)
750 neg_double (b
.low
, b
.high
, &b
.low
, &b
.high
);
751 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
758 double_int_neg (double_int a
)
761 neg_double (a
.low
, a
.high
, &ret
.low
, &ret
.high
);
765 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
766 specified by CODE). CODE is enum tree_code in fact, but double_int.h
767 must be included before tree.h. The remainder after the division is
771 double_int_divmod (double_int a
, double_int b
, bool uns
, unsigned code
,
776 div_and_round_double (code
, uns
, a
.low
, a
.high
,
777 b
.low
, b
.high
, &ret
.low
, &ret
.high
,
778 &mod
->low
, &mod
->high
);
782 /* The same as double_int_divmod with UNS = false. */
785 double_int_sdivmod (double_int a
, double_int b
, unsigned code
, double_int
*mod
)
787 return double_int_divmod (a
, b
, false, code
, mod
);
790 /* The same as double_int_divmod with UNS = true. */
793 double_int_udivmod (double_int a
, double_int b
, unsigned code
, double_int
*mod
)
795 return double_int_divmod (a
, b
, true, code
, mod
);
798 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
799 specified by CODE). CODE is enum tree_code in fact, but double_int.h
800 must be included before tree.h. */
803 double_int_div (double_int a
, double_int b
, bool uns
, unsigned code
)
807 return double_int_divmod (a
, b
, uns
, code
, &mod
);
810 /* The same as double_int_div with UNS = false. */
813 double_int_sdiv (double_int a
, double_int b
, unsigned code
)
815 return double_int_div (a
, b
, false, code
);
818 /* The same as double_int_div with UNS = true. */
821 double_int_udiv (double_int a
, double_int b
, unsigned code
)
823 return double_int_div (a
, b
, true, code
);
826 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
827 specified by CODE). CODE is enum tree_code in fact, but double_int.h
828 must be included before tree.h. */
831 double_int_mod (double_int a
, double_int b
, bool uns
, unsigned code
)
835 double_int_divmod (a
, b
, uns
, code
, &mod
);
839 /* The same as double_int_mod with UNS = false. */
842 double_int_smod (double_int a
, double_int b
, unsigned code
)
844 return double_int_mod (a
, b
, false, code
);
847 /* The same as double_int_mod with UNS = true. */
850 double_int_umod (double_int a
, double_int b
, unsigned code
)
852 return double_int_mod (a
, b
, true, code
);
855 /* Set BITPOS bit in A. */
857 double_int_setbit (double_int a
, unsigned bitpos
)
859 if (bitpos
< HOST_BITS_PER_WIDE_INT
)
860 a
.low
|= (unsigned HOST_WIDE_INT
) 1 << bitpos
;
862 a
.high
|= (HOST_WIDE_INT
) 1 << (bitpos
- HOST_BITS_PER_WIDE_INT
);
867 /* Count trailing zeros in A. */
869 double_int_ctz (double_int a
)
871 unsigned HOST_WIDE_INT w
= a
.low
? a
.low
: (unsigned HOST_WIDE_INT
) a
.high
;
872 unsigned bits
= a
.low
? 0 : HOST_BITS_PER_WIDE_INT
;
874 return HOST_BITS_PER_DOUBLE_INT
;
879 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
880 right if COUNT is negative. ARITH true specifies arithmetic shifting;
881 otherwise use logical shift. */
884 double_int_lshift (double_int a
, HOST_WIDE_INT count
, unsigned int prec
, bool arith
)
887 lshift_double (a
.low
, a
.high
, count
, prec
, &ret
.low
, &ret
.high
, arith
);
891 /* Shift A rigth by COUNT places keeping only PREC bits of result. Shift
892 left if COUNT is negative. ARITH true specifies arithmetic shifting;
893 otherwise use logical shift. */
896 double_int_rshift (double_int a
, HOST_WIDE_INT count
, unsigned int prec
, bool arith
)
899 rshift_double (a
.low
, a
.high
, count
, prec
, &ret
.low
, &ret
.high
, arith
);
903 /* Rotate A left by COUNT places keeping only PREC bits of result.
904 Rotate right if COUNT is negative. */
907 double_int_lrotate (double_int a
, HOST_WIDE_INT count
, unsigned int prec
)
915 t1
= double_int_lshift (a
, count
, prec
, false);
916 t2
= double_int_rshift (a
, prec
- count
, prec
, false);
918 return double_int_ior (t1
, t2
);
921 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
922 Rotate right if COUNT is negative. */
925 double_int_rrotate (double_int a
, HOST_WIDE_INT count
, unsigned int prec
)
933 t1
= double_int_rshift (a
, count
, prec
, false);
934 t2
= double_int_lshift (a
, prec
- count
, prec
, false);
936 return double_int_ior (t1
, t2
);
939 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
940 comparison is given by UNS. */
943 double_int_cmp (double_int a
, double_int b
, bool uns
)
946 return double_int_ucmp (a
, b
);
948 return double_int_scmp (a
, b
);
951 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
955 double_int_ucmp (double_int a
, double_int b
)
957 if ((unsigned HOST_WIDE_INT
) a
.high
< (unsigned HOST_WIDE_INT
) b
.high
)
959 if ((unsigned HOST_WIDE_INT
) a
.high
> (unsigned HOST_WIDE_INT
) b
.high
)
969 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
973 double_int_scmp (double_int a
, double_int b
)
987 /* Compares two values A and B. Returns max value. Signedness of the
988 comparison is given by UNS. */
991 double_int_max (double_int a
, double_int b
, bool uns
)
993 return (double_int_cmp (a
, b
, uns
) == 1) ? a
: b
;
996 /* Compares two signed values A and B. Returns max value. */
998 double_int
double_int_smax (double_int a
, double_int b
)
1000 return (double_int_scmp (a
, b
) == 1) ? a
: b
;
1003 /* Compares two unsigned values A and B. Returns max value. */
1005 double_int
double_int_umax (double_int a
, double_int b
)
1007 return (double_int_ucmp (a
, b
) == 1) ? a
: b
;
1010 /* Compares two values A and B. Returns mix value. Signedness of the
1011 comparison is given by UNS. */
1013 double_int
double_int_min (double_int a
, double_int b
, bool uns
)
1015 return (double_int_cmp (a
, b
, uns
) == -1) ? a
: b
;
1018 /* Compares two signed values A and B. Returns min value. */
1020 double_int
double_int_smin (double_int a
, double_int b
)
1022 return (double_int_scmp (a
, b
) == -1) ? a
: b
;
1025 /* Compares two unsigned values A and B. Returns min value. */
1027 double_int
double_int_umin (double_int a
, double_int b
)
1029 return (double_int_ucmp (a
, b
) == -1) ? a
: b
;
1032 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1035 double_int_split_digit (double_int
*cst
, unsigned base
)
1037 unsigned HOST_WIDE_INT resl
, reml
;
1038 HOST_WIDE_INT resh
, remh
;
1040 div_and_round_double (FLOOR_DIV_EXPR
, true, cst
->low
, cst
->high
, base
, 0,
1041 &resl
, &resh
, &reml
, &remh
);
1048 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1049 otherwise it is signed. */
1052 dump_double_int (FILE *file
, double_int cst
, bool uns
)
1054 unsigned digits
[100], n
;
1057 if (double_int_zero_p (cst
))
1059 fprintf (file
, "0");
1063 if (!uns
&& double_int_negative_p (cst
))
1065 fprintf (file
, "-");
1066 cst
= double_int_neg (cst
);
1069 for (n
= 0; !double_int_zero_p (cst
); n
++)
1070 digits
[n
] = double_int_split_digit (&cst
, 10);
1071 for (i
= n
- 1; i
>= 0; i
--)
1072 fprintf (file
, "%u", digits
[i
]);
1076 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1080 mpz_set_double_int (mpz_t result
, double_int val
, bool uns
)
1082 bool negate
= false;
1083 unsigned HOST_WIDE_INT vp
[2];
1085 if (!uns
&& double_int_negative_p (val
))
1088 val
= double_int_neg (val
);
1092 vp
[1] = (unsigned HOST_WIDE_INT
) val
.high
;
1093 mpz_import (result
, 2, -1, sizeof (HOST_WIDE_INT
), 0, 0, vp
);
1096 mpz_neg (result
, result
);
1099 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
1100 values of VAL will be wrapped; otherwise, they will be set to the
1101 appropriate minimum or maximum TYPE bound. */
1104 mpz_get_double_int (const_tree type
, mpz_t val
, bool wrap
)
1106 unsigned HOST_WIDE_INT
*vp
;
1116 get_type_static_bounds (type
, min
, max
);
1118 if (mpz_cmp (val
, min
) < 0)
1120 else if (mpz_cmp (val
, max
) > 0)
1127 /* Determine the number of unsigned HOST_WIDE_INT that are required
1128 for representing the value. The code to calculate count is
1129 extracted from the GMP manual, section "Integer Import and Export":
1130 http://gmplib.org/manual/Integer-Import-and-Export.html */
1131 numb
= 8*sizeof(HOST_WIDE_INT
);
1132 count
= (mpz_sizeinbase (val
, 2) + numb
-1) / numb
;
1135 vp
= (unsigned HOST_WIDE_INT
*) alloca (count
* sizeof(HOST_WIDE_INT
));
1139 mpz_export (vp
, &count
, -1, sizeof (HOST_WIDE_INT
), 0, 0, val
);
1141 gcc_assert (wrap
|| count
<= 2);
1144 res
.high
= (HOST_WIDE_INT
) vp
[1];
1146 res
= double_int_ext (res
, TYPE_PRECISION (type
), TYPE_UNSIGNED (type
));
1147 if (mpz_sgn (val
) < 0)
1148 res
= double_int_neg (res
);