1 /* Operations with long integers.
2 Copyright (C) 2006-2017 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 BITS_PER_UNIT and *_BIG_ENDIAN. */
26 static int add_double_with_sign (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
27 unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
28 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
31 #define add_double(l1,h1,l2,h2,lv,hv) \
32 add_double_with_sign (l1, h1, l2, h2, lv, hv, false)
34 static int neg_double (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
35 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*);
37 static int mul_double_wide_with_sign (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
38 unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
39 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
40 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
43 #define mul_double(l1,h1,l2,h2,lv,hv) \
44 mul_double_wide_with_sign (l1, h1, l2, h2, lv, hv, NULL, NULL, false)
46 static int div_and_round_double (unsigned, int, unsigned HOST_WIDE_INT
,
47 HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
48 HOST_WIDE_INT
, unsigned HOST_WIDE_INT
*,
49 HOST_WIDE_INT
*, unsigned HOST_WIDE_INT
*,
52 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
53 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
54 and SUM1. Then this yields nonzero if overflow occurred during the
57 Overflow occurs if A and B have the same sign, but A and SUM differ in
58 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
60 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
62 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
63 We do that by representing the two-word integer in 4 words, with only
64 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
65 number. The value of the word is LOWPART + HIGHPART * BASE. */
68 ((x) & ((HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
70 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
71 #define BASE (HOST_WIDE_INT_1U << HOST_BITS_PER_WIDE_INT / 2)
73 /* Unpack a two-word integer into 4 words.
74 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
75 WORDS points to the array of HOST_WIDE_INTs. */
78 encode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT low
, HOST_WIDE_INT hi
)
80 words
[0] = LOWPART (low
);
81 words
[1] = HIGHPART (low
);
82 words
[2] = LOWPART (hi
);
83 words
[3] = HIGHPART (hi
);
86 /* Pack an array of 4 words into a two-word integer.
87 WORDS points to the array of words.
88 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
91 decode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT
*low
,
94 *low
= words
[0] + words
[1] * BASE
;
95 *hi
= words
[2] + words
[3] * BASE
;
98 /* Add two doubleword integers with doubleword result.
99 Return nonzero if the operation overflows according to UNSIGNED_P.
100 Each argument is given as two `HOST_WIDE_INT' pieces.
101 One argument is L1 and H1; the other, L2 and H2.
102 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
105 add_double_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
106 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
107 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
110 unsigned HOST_WIDE_INT l
;
114 h
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) h1
115 + (unsigned HOST_WIDE_INT
) h2
122 return ((unsigned HOST_WIDE_INT
) h
< (unsigned HOST_WIDE_INT
) h1
126 return OVERFLOW_SUM_SIGN (h1
, h2
, h
);
129 /* Negate a doubleword integer with doubleword result.
130 Return nonzero if the operation overflows, assuming it's signed.
131 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
132 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
135 neg_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
136 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
)
141 *hv
= - (unsigned HOST_WIDE_INT
) h1
;
142 return (*hv
& h1
) < 0;
152 /* Multiply two doubleword integers with quadword result.
153 Return nonzero if the operation overflows according to UNSIGNED_P.
154 Each argument is given as two `HOST_WIDE_INT' pieces.
155 One argument is L1 and H1; the other, L2 and H2.
156 The value is stored as four `HOST_WIDE_INT' pieces in *LV and *HV,
158 If lw is NULL then only the low part and no overflow is computed. */
161 mul_double_wide_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
162 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
163 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
164 unsigned HOST_WIDE_INT
*lw
, HOST_WIDE_INT
*hw
,
167 HOST_WIDE_INT arg1
[4];
168 HOST_WIDE_INT arg2
[4];
169 HOST_WIDE_INT prod
[4 * 2];
170 unsigned HOST_WIDE_INT carry
;
172 unsigned HOST_WIDE_INT neglow
;
173 HOST_WIDE_INT neghigh
;
175 encode (arg1
, l1
, h1
);
176 encode (arg2
, l2
, h2
);
178 memset (prod
, 0, sizeof prod
);
180 for (i
= 0; i
< 4; i
++)
183 for (j
= 0; j
< 4; j
++)
186 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
187 carry
+= (unsigned HOST_WIDE_INT
) arg1
[i
] * arg2
[j
];
188 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
190 prod
[k
] = LOWPART (carry
);
191 carry
= HIGHPART (carry
);
196 decode (prod
, lv
, hv
);
198 /* We are not interested in the wide part nor in overflow. */
202 decode (prod
+ 4, lw
, hw
);
204 /* Unsigned overflow is immediate. */
206 return (*lw
| *hw
) != 0;
208 /* Check for signed overflow by calculating the signed representation of the
209 top half of the result; it should agree with the low half's sign bit. */
212 neg_double (l2
, h2
, &neglow
, &neghigh
);
213 add_double (neglow
, neghigh
, *lw
, *hw
, lw
, hw
);
217 neg_double (l1
, h1
, &neglow
, &neghigh
);
218 add_double (neglow
, neghigh
, *lw
, *hw
, lw
, hw
);
220 return (*hv
< 0 ? ~(*lw
& *hw
) : *lw
| *hw
) != 0;
223 /* Shift the doubleword integer in L1, H1 right by COUNT places
224 keeping only PREC bits of result. ARITH nonzero specifies
225 arithmetic shifting; otherwise use logical shift.
226 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
229 rshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
230 unsigned HOST_WIDE_INT count
, unsigned int prec
,
231 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
234 unsigned HOST_WIDE_INT signmask
;
237 ? -((unsigned HOST_WIDE_INT
) h1
>> (HOST_BITS_PER_WIDE_INT
- 1))
240 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
242 /* Shifting by the host word size is undefined according to the
243 ANSI standard, so we must handle this as a special case. */
247 else if (count
>= HOST_BITS_PER_WIDE_INT
)
250 *lv
= (unsigned HOST_WIDE_INT
) h1
>> (count
- HOST_BITS_PER_WIDE_INT
);
254 *hv
= (unsigned HOST_WIDE_INT
) h1
>> count
;
256 | ((unsigned HOST_WIDE_INT
) h1
257 << (HOST_BITS_PER_WIDE_INT
- count
- 1) << 1));
260 /* Zero / sign extend all bits that are beyond the precision. */
267 else if ((prec
- count
) >= HOST_BITS_PER_DOUBLE_INT
)
269 else if ((prec
- count
) >= HOST_BITS_PER_WIDE_INT
)
271 *hv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- count
- HOST_BITS_PER_WIDE_INT
));
272 *hv
|= signmask
<< (prec
- count
- HOST_BITS_PER_WIDE_INT
);
277 *lv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- count
));
278 *lv
|= signmask
<< (prec
- count
);
282 /* Shift the doubleword integer in L1, H1 left by COUNT places
283 keeping only PREC bits of result.
284 Shift right if COUNT is negative.
285 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
286 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
289 lshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
290 unsigned HOST_WIDE_INT count
, unsigned int prec
,
291 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
)
293 unsigned HOST_WIDE_INT signmask
;
295 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
297 /* Shifting by the host word size is undefined according to the
298 ANSI standard, so we must handle this as a special case. */
302 else if (count
>= HOST_BITS_PER_WIDE_INT
)
304 *hv
= l1
<< (count
- HOST_BITS_PER_WIDE_INT
);
309 *hv
= (((unsigned HOST_WIDE_INT
) h1
<< count
)
310 | (l1
>> (HOST_BITS_PER_WIDE_INT
- count
- 1) >> 1));
314 /* Sign extend all bits that are beyond the precision. */
316 signmask
= -((prec
> HOST_BITS_PER_WIDE_INT
317 ? ((unsigned HOST_WIDE_INT
) *hv
318 >> (prec
- HOST_BITS_PER_WIDE_INT
- 1))
319 : (*lv
>> (prec
- 1))) & 1);
321 if (prec
>= HOST_BITS_PER_DOUBLE_INT
)
323 else if (prec
>= HOST_BITS_PER_WIDE_INT
)
325 *hv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- HOST_BITS_PER_WIDE_INT
));
326 *hv
|= signmask
<< (prec
- HOST_BITS_PER_WIDE_INT
);
331 *lv
&= ~(HOST_WIDE_INT_M1U
<< prec
);
332 *lv
|= signmask
<< prec
;
336 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
337 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
338 CODE is a tree code for a kind of division, one of
339 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
341 It controls how the quotient is rounded to an integer.
342 Return nonzero if the operation overflows.
343 UNS nonzero says do unsigned division. */
346 div_and_round_double (unsigned code
, int uns
,
347 /* num == numerator == dividend */
348 unsigned HOST_WIDE_INT lnum_orig
,
349 HOST_WIDE_INT hnum_orig
,
350 /* den == denominator == divisor */
351 unsigned HOST_WIDE_INT lden_orig
,
352 HOST_WIDE_INT hden_orig
,
353 unsigned HOST_WIDE_INT
*lquo
,
354 HOST_WIDE_INT
*hquo
, unsigned HOST_WIDE_INT
*lrem
,
358 HOST_WIDE_INT num
[4 + 1]; /* extra element for scaling. */
359 HOST_WIDE_INT den
[4], quo
[4];
361 unsigned HOST_WIDE_INT work
;
362 unsigned HOST_WIDE_INT carry
= 0;
363 unsigned HOST_WIDE_INT lnum
= lnum_orig
;
364 HOST_WIDE_INT hnum
= hnum_orig
;
365 unsigned HOST_WIDE_INT lden
= lden_orig
;
366 HOST_WIDE_INT hden
= hden_orig
;
369 if (hden
== 0 && lden
== 0)
370 overflow
= 1, lden
= 1;
372 /* Calculate quotient sign and convert operands to unsigned. */
378 /* (minimum integer) / (-1) is the only overflow case. */
379 if (neg_double (lnum
, hnum
, &lnum
, &hnum
)
380 && ((HOST_WIDE_INT
) lden
& hden
) == -1)
386 neg_double (lden
, hden
, &lden
, &hden
);
390 if (hnum
== 0 && hden
== 0)
391 { /* single precision */
393 /* This unsigned division rounds toward zero. */
399 { /* trivial case: dividend < divisor */
400 /* hden != 0 already checked. */
407 memset (quo
, 0, sizeof quo
);
409 memset (num
, 0, sizeof num
); /* to zero 9th element */
410 memset (den
, 0, sizeof den
);
412 encode (num
, lnum
, hnum
);
413 encode (den
, lden
, hden
);
415 /* Special code for when the divisor < BASE. */
416 if (hden
== 0 && lden
< (unsigned HOST_WIDE_INT
) BASE
)
418 /* hnum != 0 already checked. */
419 for (i
= 4 - 1; i
>= 0; i
--)
421 work
= num
[i
] + carry
* BASE
;
422 quo
[i
] = work
/ lden
;
428 /* Full double precision division,
429 with thanks to Don Knuth's "Seminumerical Algorithms". */
430 int num_hi_sig
, den_hi_sig
;
431 unsigned HOST_WIDE_INT quo_est
, scale
;
433 /* Find the highest nonzero divisor digit. */
434 for (i
= 4 - 1;; i
--)
441 /* Insure that the first digit of the divisor is at least BASE/2.
442 This is required by the quotient digit estimation algorithm. */
444 scale
= BASE
/ (den
[den_hi_sig
] + 1);
446 { /* scale divisor and dividend */
448 for (i
= 0; i
<= 4 - 1; i
++)
450 work
= (num
[i
] * scale
) + carry
;
451 num
[i
] = LOWPART (work
);
452 carry
= HIGHPART (work
);
457 for (i
= 0; i
<= 4 - 1; i
++)
459 work
= (den
[i
] * scale
) + carry
;
460 den
[i
] = LOWPART (work
);
461 carry
= HIGHPART (work
);
462 if (den
[i
] != 0) den_hi_sig
= i
;
469 for (i
= num_hi_sig
- den_hi_sig
- 1; i
>= 0; i
--)
471 /* Guess the next quotient digit, quo_est, by dividing the first
472 two remaining dividend digits by the high order quotient digit.
473 quo_est is never low and is at most 2 high. */
474 unsigned HOST_WIDE_INT tmp
;
476 num_hi_sig
= i
+ den_hi_sig
+ 1;
477 work
= num
[num_hi_sig
] * BASE
+ num
[num_hi_sig
- 1];
478 if (num
[num_hi_sig
] != den
[den_hi_sig
])
479 quo_est
= work
/ den
[den_hi_sig
];
483 /* Refine quo_est so it's usually correct, and at most one high. */
484 tmp
= work
- quo_est
* den
[den_hi_sig
];
486 && (den
[den_hi_sig
- 1] * quo_est
487 > (tmp
* BASE
+ num
[num_hi_sig
- 2])))
490 /* Try QUO_EST as the quotient digit, by multiplying the
491 divisor by QUO_EST and subtracting from the remaining dividend.
492 Keep in mind that QUO_EST is the I - 1st digit. */
495 for (j
= 0; j
<= den_hi_sig
; j
++)
497 work
= quo_est
* den
[j
] + carry
;
498 carry
= HIGHPART (work
);
499 work
= num
[i
+ j
] - LOWPART (work
);
500 num
[i
+ j
] = LOWPART (work
);
501 carry
+= HIGHPART (work
) != 0;
504 /* If quo_est was high by one, then num[i] went negative and
505 we need to correct things. */
506 if (num
[num_hi_sig
] < (HOST_WIDE_INT
) carry
)
509 carry
= 0; /* add divisor back in */
510 for (j
= 0; j
<= den_hi_sig
; j
++)
512 work
= num
[i
+ j
] + den
[j
] + carry
;
513 carry
= HIGHPART (work
);
514 num
[i
+ j
] = LOWPART (work
);
517 num
[num_hi_sig
] += carry
;
520 /* Store the quotient digit. */
525 decode (quo
, lquo
, hquo
);
528 /* If result is negative, make it so. */
530 neg_double (*lquo
, *hquo
, lquo
, hquo
);
532 /* Compute trial remainder: rem = num - (quo * den) */
533 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
534 neg_double (*lrem
, *hrem
, lrem
, hrem
);
535 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
540 case TRUNC_MOD_EXPR
: /* round toward zero */
541 case EXACT_DIV_EXPR
: /* for this one, it shouldn't matter */
545 case FLOOR_MOD_EXPR
: /* round toward negative infinity */
546 if (quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio < 0 && rem != 0 */
549 add_double (*lquo
, *hquo
, HOST_WIDE_INT_M1
, HOST_WIDE_INT_M1
,
557 case CEIL_MOD_EXPR
: /* round toward positive infinity */
558 if (!quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio > 0 && rem != 0 */
560 add_double (*lquo
, *hquo
, HOST_WIDE_INT_1
, HOST_WIDE_INT_0
,
568 case ROUND_MOD_EXPR
: /* round to closest integer */
570 unsigned HOST_WIDE_INT labs_rem
= *lrem
;
571 HOST_WIDE_INT habs_rem
= *hrem
;
572 unsigned HOST_WIDE_INT labs_den
= lden
, lnegabs_rem
, ldiff
;
573 HOST_WIDE_INT habs_den
= hden
, hnegabs_rem
, hdiff
;
575 /* Get absolute values. */
576 if (!uns
&& *hrem
< 0)
577 neg_double (*lrem
, *hrem
, &labs_rem
, &habs_rem
);
578 if (!uns
&& hden
< 0)
579 neg_double (lden
, hden
, &labs_den
, &habs_den
);
581 /* If abs(rem) >= abs(den) - abs(rem), adjust the quotient. */
582 neg_double (labs_rem
, habs_rem
, &lnegabs_rem
, &hnegabs_rem
);
583 add_double (labs_den
, habs_den
, lnegabs_rem
, hnegabs_rem
,
586 if (((unsigned HOST_WIDE_INT
) habs_rem
587 > (unsigned HOST_WIDE_INT
) hdiff
)
588 || (habs_rem
== hdiff
&& labs_rem
>= ldiff
))
592 add_double (*lquo
, *hquo
,
593 HOST_WIDE_INT_M1
, HOST_WIDE_INT_M1
, lquo
, hquo
);
596 add_double (*lquo
, *hquo
, HOST_WIDE_INT_1
, HOST_WIDE_INT_0
,
608 /* Compute true remainder: rem = num - (quo * den) */
609 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
610 neg_double (*lrem
, *hrem
, lrem
, hrem
);
611 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
616 /* Construct from a buffer of length LEN. BUFFER will be read according
617 to byte endianess and word endianess. Only the lower LEN bytes
618 of the result are set; the remaining high bytes are cleared. */
621 double_int::from_buffer (const unsigned char *buffer
, int len
)
623 double_int result
= double_int_zero
;
624 int words
= len
/ UNITS_PER_WORD
;
626 gcc_assert (len
* BITS_PER_UNIT
<= HOST_BITS_PER_DOUBLE_INT
);
628 for (int byte
= 0; byte
< len
; byte
++)
631 int bitpos
= byte
* BITS_PER_UNIT
;
632 unsigned HOST_WIDE_INT value
;
634 if (len
> UNITS_PER_WORD
)
636 int word
= byte
/ UNITS_PER_WORD
;
638 if (WORDS_BIG_ENDIAN
)
639 word
= (words
- 1) - word
;
641 offset
= word
* UNITS_PER_WORD
;
643 if (BYTES_BIG_ENDIAN
)
644 offset
+= (UNITS_PER_WORD
- 1) - (byte
% UNITS_PER_WORD
);
646 offset
+= byte
% UNITS_PER_WORD
;
649 offset
= BYTES_BIG_ENDIAN
? (len
- 1) - byte
: byte
;
651 value
= (unsigned HOST_WIDE_INT
) buffer
[offset
];
653 if (bitpos
< HOST_BITS_PER_WIDE_INT
)
654 result
.low
|= value
<< bitpos
;
656 result
.high
|= value
<< (bitpos
- HOST_BITS_PER_WIDE_INT
);
663 /* Returns mask for PREC bits. */
666 double_int::mask (unsigned prec
)
668 unsigned HOST_WIDE_INT m
;
671 if (prec
> HOST_BITS_PER_WIDE_INT
)
673 prec
-= HOST_BITS_PER_WIDE_INT
;
674 m
= ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1;
675 mask
.high
= (HOST_WIDE_INT
) m
;
681 mask
.low
= prec
? ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1 : 0;
687 /* Returns a maximum value for signed or unsigned integer
688 of precision PREC. */
691 double_int::max_value (unsigned int prec
, bool uns
)
693 return double_int::mask (prec
- (uns
? 0 : 1));
696 /* Returns a minimum value for signed or unsigned integer
697 of precision PREC. */
700 double_int::min_value (unsigned int prec
, bool uns
)
703 return double_int_zero
;
704 return double_int_one
.lshift (prec
- 1, prec
, false);
707 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
708 outside of the precision are set to the sign bit (i.e., the PREC-th one),
709 otherwise they are set to zero.
711 This corresponds to returning the value represented by PREC lowermost bits
712 of CST, with the given signedness. */
715 double_int::ext (unsigned prec
, bool uns
) const
718 return this->zext (prec
);
720 return this->sext (prec
);
723 /* The same as double_int::ext with UNS = true. */
726 double_int::zext (unsigned prec
) const
728 const double_int
&cst
= *this;
729 double_int mask
= double_int::mask (prec
);
732 r
.low
= cst
.low
& mask
.low
;
733 r
.high
= cst
.high
& mask
.high
;
738 /* The same as double_int::ext with UNS = false. */
741 double_int::sext (unsigned prec
) const
743 const double_int
&cst
= *this;
744 double_int mask
= double_int::mask (prec
);
746 unsigned HOST_WIDE_INT snum
;
748 if (prec
<= HOST_BITS_PER_WIDE_INT
)
752 prec
-= HOST_BITS_PER_WIDE_INT
;
753 snum
= (unsigned HOST_WIDE_INT
) cst
.high
;
755 if (((snum
>> (prec
- 1)) & 1) == 1)
757 r
.low
= cst
.low
| ~mask
.low
;
758 r
.high
= cst
.high
| ~mask
.high
;
762 r
.low
= cst
.low
& mask
.low
;
763 r
.high
= cst
.high
& mask
.high
;
769 /* Returns true if CST fits in signed HOST_WIDE_INT. */
772 double_int::fits_shwi () const
774 const double_int
&cst
= *this;
776 return (HOST_WIDE_INT
) cst
.low
>= 0;
777 else if (cst
.high
== -1)
778 return (HOST_WIDE_INT
) cst
.low
< 0;
783 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
784 unsigned HOST_WIDE_INT if UNS is true. */
787 double_int::fits_hwi (bool uns
) const
790 return this->fits_uhwi ();
792 return this->fits_shwi ();
798 double_int::operator * (double_int b
) const
800 const double_int
&a
= *this;
802 mul_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
806 /* Multiplies *this with B and returns a reference to *this. */
809 double_int::operator *= (double_int b
)
811 mul_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
815 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
816 *OVERFLOW is set to nonzero. */
819 double_int::mul_with_sign (double_int b
, bool unsigned_p
, bool *overflow
) const
821 const double_int
&a
= *this;
823 *overflow
= mul_double_wide_with_sign (a
.low
, a
.high
, b
.low
, b
.high
,
825 &tem
.low
, &tem
.high
, unsigned_p
);
830 double_int::wide_mul_with_sign (double_int b
, bool unsigned_p
,
831 double_int
*higher
, bool *overflow
) const
835 *overflow
= mul_double_wide_with_sign (low
, high
, b
.low
, b
.high
,
836 &lower
.low
, &lower
.high
,
837 &higher
->low
, &higher
->high
,
845 double_int::operator + (double_int b
) const
847 const double_int
&a
= *this;
849 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
853 /* Adds B to *this and returns a reference to *this. */
856 double_int::operator += (double_int b
)
858 add_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
863 /* Returns A + B. If the operation overflows according to UNSIGNED_P,
864 *OVERFLOW is set to nonzero. */
867 double_int::add_with_sign (double_int b
, bool unsigned_p
, bool *overflow
) const
869 const double_int
&a
= *this;
871 *overflow
= add_double_with_sign (a
.low
, a
.high
, b
.low
, b
.high
,
872 &ret
.low
, &ret
.high
, unsigned_p
);
879 double_int::operator - (double_int b
) const
881 const double_int
&a
= *this;
883 neg_double (b
.low
, b
.high
, &b
.low
, &b
.high
);
884 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
888 /* Subtracts B from *this and returns a reference to *this. */
891 double_int::operator -= (double_int b
)
893 neg_double (b
.low
, b
.high
, &b
.low
, &b
.high
);
894 add_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
899 /* Returns A - B. If the operation overflows via inconsistent sign bits,
900 *OVERFLOW is set to nonzero. */
903 double_int::sub_with_overflow (double_int b
, bool *overflow
) const
906 neg_double (b
.low
, b
.high
, &ret
.low
, &ret
.high
);
907 add_double (low
, high
, ret
.low
, ret
.high
, &ret
.low
, &ret
.high
);
908 *overflow
= OVERFLOW_SUM_SIGN (ret
.high
, b
.high
, high
);
915 double_int::operator - () const
917 const double_int
&a
= *this;
919 neg_double (a
.low
, a
.high
, &ret
.low
, &ret
.high
);
924 double_int::neg_with_overflow (bool *overflow
) const
927 *overflow
= neg_double (low
, high
, &ret
.low
, &ret
.high
);
931 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
932 specified by CODE). CODE is enum tree_code in fact, but double_int.h
933 must be included before tree.h. The remainder after the division is
937 double_int::divmod_with_overflow (double_int b
, bool uns
, unsigned code
,
938 double_int
*mod
, bool *overflow
) const
940 const double_int
&a
= *this;
943 *overflow
= div_and_round_double (code
, uns
, a
.low
, a
.high
,
944 b
.low
, b
.high
, &ret
.low
, &ret
.high
,
945 &mod
->low
, &mod
->high
);
950 double_int::divmod (double_int b
, bool uns
, unsigned code
,
951 double_int
*mod
) const
953 const double_int
&a
= *this;
956 div_and_round_double (code
, uns
, a
.low
, a
.high
,
957 b
.low
, b
.high
, &ret
.low
, &ret
.high
,
958 &mod
->low
, &mod
->high
);
962 /* The same as double_int::divmod with UNS = false. */
965 double_int::sdivmod (double_int b
, unsigned code
, double_int
*mod
) const
967 return this->divmod (b
, false, code
, mod
);
970 /* The same as double_int::divmod with UNS = true. */
973 double_int::udivmod (double_int b
, unsigned code
, double_int
*mod
) const
975 return this->divmod (b
, true, code
, mod
);
978 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
979 specified by CODE). CODE is enum tree_code in fact, but double_int.h
980 must be included before tree.h. */
983 double_int::div (double_int b
, bool uns
, unsigned code
) const
987 return this->divmod (b
, uns
, code
, &mod
);
990 /* The same as double_int::div with UNS = false. */
993 double_int::sdiv (double_int b
, unsigned code
) const
995 return this->div (b
, false, code
);
998 /* The same as double_int::div with UNS = true. */
1001 double_int::udiv (double_int b
, unsigned code
) const
1003 return this->div (b
, true, code
);
1006 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
1007 specified by CODE). CODE is enum tree_code in fact, but double_int.h
1008 must be included before tree.h. */
1011 double_int::mod (double_int b
, bool uns
, unsigned code
) const
1015 this->divmod (b
, uns
, code
, &mod
);
1019 /* The same as double_int::mod with UNS = false. */
1022 double_int::smod (double_int b
, unsigned code
) const
1024 return this->mod (b
, false, code
);
1027 /* The same as double_int::mod with UNS = true. */
1030 double_int::umod (double_int b
, unsigned code
) const
1032 return this->mod (b
, true, code
);
1035 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
1036 the multiple in *MULTIPLE. Otherwise return FALSE and leave *MULTIPLE
1040 double_int::multiple_of (double_int factor
,
1041 bool unsigned_p
, double_int
*multiple
) const
1043 double_int remainder
;
1044 double_int quotient
= this->divmod (factor
, unsigned_p
,
1045 TRUNC_DIV_EXPR
, &remainder
);
1046 if (remainder
.is_zero ())
1048 *multiple
= quotient
;
1055 /* Set BITPOS bit in A. */
1057 double_int::set_bit (unsigned bitpos
) const
1059 double_int a
= *this;
1060 if (bitpos
< HOST_BITS_PER_WIDE_INT
)
1061 a
.low
|= HOST_WIDE_INT_1U
<< bitpos
;
1063 a
.high
|= HOST_WIDE_INT_1
<< (bitpos
- HOST_BITS_PER_WIDE_INT
);
1068 /* Count trailing zeros in A. */
1070 double_int::trailing_zeros () const
1072 const double_int
&a
= *this;
1073 unsigned HOST_WIDE_INT w
= a
.low
? a
.low
: (unsigned HOST_WIDE_INT
) a
.high
;
1074 unsigned bits
= a
.low
? 0 : HOST_BITS_PER_WIDE_INT
;
1076 return HOST_BITS_PER_DOUBLE_INT
;
1077 bits
+= ctz_hwi (w
);
1081 /* Shift A left by COUNT places. */
1084 double_int::lshift (HOST_WIDE_INT count
) const
1088 gcc_checking_assert (count
>= 0);
1090 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
1092 /* Shifting by the host word size is undefined according to the
1093 ANSI standard, so we must handle this as a special case. */
1097 else if (count
>= HOST_BITS_PER_WIDE_INT
)
1099 ret
.high
= low
<< (count
- HOST_BITS_PER_WIDE_INT
);
1104 ret
.high
= (((unsigned HOST_WIDE_INT
) high
<< count
)
1105 | (low
>> (HOST_BITS_PER_WIDE_INT
- count
- 1) >> 1));
1106 ret
.low
= low
<< count
;
1112 /* Shift A right by COUNT places. */
1115 double_int::rshift (HOST_WIDE_INT count
) const
1119 gcc_checking_assert (count
>= 0);
1121 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
1123 /* Shifting by the host word size is undefined according to the
1124 ANSI standard, so we must handle this as a special case. */
1128 else if (count
>= HOST_BITS_PER_WIDE_INT
)
1132 = (unsigned HOST_WIDE_INT
) (high
>> (count
- HOST_BITS_PER_WIDE_INT
));
1136 ret
.high
= high
>> count
;
1137 ret
.low
= ((low
>> count
)
1138 | ((unsigned HOST_WIDE_INT
) high
1139 << (HOST_BITS_PER_WIDE_INT
- count
- 1) << 1));
1145 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
1146 right if COUNT is negative. ARITH true specifies arithmetic shifting;
1147 otherwise use logical shift. */
1150 double_int::lshift (HOST_WIDE_INT count
, unsigned int prec
, bool arith
) const
1154 lshift_double (low
, high
, count
, prec
, &ret
.low
, &ret
.high
);
1156 rshift_double (low
, high
, absu_hwi (count
), prec
, &ret
.low
, &ret
.high
, arith
);
1160 /* Shift A right by COUNT places keeping only PREC bits of result. Shift
1161 left if COUNT is negative. ARITH true specifies arithmetic shifting;
1162 otherwise use logical shift. */
1165 double_int::rshift (HOST_WIDE_INT count
, unsigned int prec
, bool arith
) const
1169 rshift_double (low
, high
, count
, prec
, &ret
.low
, &ret
.high
, arith
);
1171 lshift_double (low
, high
, absu_hwi (count
), prec
, &ret
.low
, &ret
.high
);
1175 /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
1176 Shift right if COUNT is negative. */
1179 double_int::alshift (HOST_WIDE_INT count
, unsigned int prec
) const
1183 lshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
);
1185 rshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
, true);
1189 /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
1190 Shift left if COUNT is negative. */
1193 double_int::arshift (HOST_WIDE_INT count
, unsigned int prec
) const
1197 rshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
, true);
1199 lshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
);
1203 /* Logical shift A left by COUNT places keeping only PREC bits of result.
1204 Shift right if COUNT is negative. */
1207 double_int::llshift (HOST_WIDE_INT count
, unsigned int prec
) const
1211 lshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
);
1213 rshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
, false);
1217 /* Logical shift A right by COUNT places keeping only PREC bits of result.
1218 Shift left if COUNT is negative. */
1221 double_int::lrshift (HOST_WIDE_INT count
, unsigned int prec
) const
1225 rshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
, false);
1227 lshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
);
1231 /* Rotate A left by COUNT places keeping only PREC bits of result.
1232 Rotate right if COUNT is negative. */
1235 double_int::lrotate (HOST_WIDE_INT count
, unsigned int prec
) const
1243 t1
= this->llshift (count
, prec
);
1244 t2
= this->lrshift (prec
- count
, prec
);
1249 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1250 Rotate right if COUNT is negative. */
1253 double_int::rrotate (HOST_WIDE_INT count
, unsigned int prec
) const
1261 t1
= this->lrshift (count
, prec
);
1262 t2
= this->llshift (prec
- count
, prec
);
1267 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
1268 comparison is given by UNS. */
1271 double_int::cmp (double_int b
, bool uns
) const
1274 return this->ucmp (b
);
1276 return this->scmp (b
);
1279 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
1283 double_int::ucmp (double_int b
) const
1285 const double_int
&a
= *this;
1286 if ((unsigned HOST_WIDE_INT
) a
.high
< (unsigned HOST_WIDE_INT
) b
.high
)
1288 if ((unsigned HOST_WIDE_INT
) a
.high
> (unsigned HOST_WIDE_INT
) b
.high
)
1298 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
1302 double_int::scmp (double_int b
) const
1304 const double_int
&a
= *this;
1305 if (a
.high
< b
.high
)
1307 if (a
.high
> b
.high
)
1317 /* Compares two unsigned values A and B for less-than. */
1320 double_int::ult (double_int b
) const
1322 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1324 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1331 /* Compares two unsigned values A and B for less-than or equal-to. */
1334 double_int::ule (double_int b
) const
1336 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1338 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1345 /* Compares two unsigned values A and B for greater-than. */
1348 double_int::ugt (double_int b
) const
1350 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1352 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1359 /* Compares two signed values A and B for less-than. */
1362 double_int::slt (double_int b
) const
1373 /* Compares two signed values A and B for less-than or equal-to. */
1376 double_int::sle (double_int b
) const
1387 /* Compares two signed values A and B for greater-than. */
1390 double_int::sgt (double_int b
) const
1402 /* Compares two values A and B. Returns max value. Signedness of the
1403 comparison is given by UNS. */
1406 double_int::max (double_int b
, bool uns
)
1408 return (this->cmp (b
, uns
) == 1) ? *this : b
;
1411 /* Compares two signed values A and B. Returns max value. */
1414 double_int::smax (double_int b
)
1416 return (this->scmp (b
) == 1) ? *this : b
;
1419 /* Compares two unsigned values A and B. Returns max value. */
1422 double_int::umax (double_int b
)
1424 return (this->ucmp (b
) == 1) ? *this : b
;
1427 /* Compares two values A and B. Returns mix value. Signedness of the
1428 comparison is given by UNS. */
1431 double_int::min (double_int b
, bool uns
)
1433 return (this->cmp (b
, uns
) == -1) ? *this : b
;
1436 /* Compares two signed values A and B. Returns min value. */
1439 double_int::smin (double_int b
)
1441 return (this->scmp (b
) == -1) ? *this : b
;
1444 /* Compares two unsigned values A and B. Returns min value. */
1447 double_int::umin (double_int b
)
1449 return (this->ucmp (b
) == -1) ? *this : b
;
1452 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1455 double_int_split_digit (double_int
*cst
, unsigned base
)
1457 unsigned HOST_WIDE_INT resl
, reml
;
1458 HOST_WIDE_INT resh
, remh
;
1460 div_and_round_double (FLOOR_DIV_EXPR
, true, cst
->low
, cst
->high
, base
, 0,
1461 &resl
, &resh
, &reml
, &remh
);
1468 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1469 otherwise it is signed. */
1472 dump_double_int (FILE *file
, double_int cst
, bool uns
)
1474 unsigned digits
[100], n
;
1479 fprintf (file
, "0");
1483 if (!uns
&& cst
.is_negative ())
1485 fprintf (file
, "-");
1489 for (n
= 0; !cst
.is_zero (); n
++)
1490 digits
[n
] = double_int_split_digit (&cst
, 10);
1491 for (i
= n
- 1; i
>= 0; i
--)
1492 fprintf (file
, "%u", digits
[i
]);
1496 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1500 mpz_set_double_int (mpz_t result
, double_int val
, bool uns
)
1502 bool negate
= false;
1503 unsigned HOST_WIDE_INT vp
[2];
1505 if (!uns
&& val
.is_negative ())
1512 vp
[1] = (unsigned HOST_WIDE_INT
) val
.high
;
1513 mpz_import (result
, 2, -1, sizeof (HOST_WIDE_INT
), 0, 0, vp
);
1516 mpz_neg (result
, result
);
1519 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
1520 values of VAL will be wrapped; otherwise, they will be set to the
1521 appropriate minimum or maximum TYPE bound. */
1524 mpz_get_double_int (const_tree type
, mpz_t val
, bool wrap
)
1526 unsigned HOST_WIDE_INT
*vp
;
1536 get_type_static_bounds (type
, min
, max
);
1538 if (mpz_cmp (val
, min
) < 0)
1540 else if (mpz_cmp (val
, max
) > 0)
1547 /* Determine the number of unsigned HOST_WIDE_INT that are required
1548 for representing the value. The code to calculate count is
1549 extracted from the GMP manual, section "Integer Import and Export":
1550 http://gmplib.org/manual/Integer-Import-and-Export.html */
1551 numb
= 8 * sizeof (HOST_WIDE_INT
);
1552 count
= (mpz_sizeinbase (val
, 2) + numb
-1) / numb
;
1555 vp
= (unsigned HOST_WIDE_INT
*) alloca (count
* sizeof (HOST_WIDE_INT
));
1559 mpz_export (vp
, &count
, -1, sizeof (HOST_WIDE_INT
), 0, 0, val
);
1561 gcc_assert (wrap
|| count
<= 2);
1564 res
.high
= (HOST_WIDE_INT
) vp
[1];
1566 res
= res
.ext (TYPE_PRECISION (type
), TYPE_UNSIGNED (type
));
1567 if (mpz_sgn (val
) < 0)