1 /* Operations with long integers.
2 Copyright (C) 2006-2015 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. */
32 static int add_double_with_sign (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
33 unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
34 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
37 #define add_double(l1,h1,l2,h2,lv,hv) \
38 add_double_with_sign (l1, h1, l2, h2, lv, hv, false)
40 static int neg_double (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
41 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*);
43 static int mul_double_wide_with_sign (unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
44 unsigned HOST_WIDE_INT
, HOST_WIDE_INT
,
45 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
46 unsigned HOST_WIDE_INT
*, HOST_WIDE_INT
*,
49 #define mul_double(l1,h1,l2,h2,lv,hv) \
50 mul_double_wide_with_sign (l1, h1, l2, h2, lv, hv, NULL, NULL, false)
52 static int div_and_round_double (unsigned, int, unsigned HOST_WIDE_INT
,
53 HOST_WIDE_INT
, unsigned HOST_WIDE_INT
,
54 HOST_WIDE_INT
, unsigned HOST_WIDE_INT
*,
55 HOST_WIDE_INT
*, unsigned HOST_WIDE_INT
*,
58 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
59 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
60 and SUM1. Then this yields nonzero if overflow occurred during the
63 Overflow occurs if A and B have the same sign, but A and SUM differ in
64 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
66 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
68 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
69 We do that by representing the two-word integer in 4 words, with only
70 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
71 number. The value of the word is LOWPART + HIGHPART * BASE. */
74 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
76 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
77 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
79 /* Unpack a two-word integer into 4 words.
80 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
81 WORDS points to the array of HOST_WIDE_INTs. */
84 encode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT low
, HOST_WIDE_INT hi
)
86 words
[0] = LOWPART (low
);
87 words
[1] = HIGHPART (low
);
88 words
[2] = LOWPART (hi
);
89 words
[3] = HIGHPART (hi
);
92 /* Pack an array of 4 words into a two-word integer.
93 WORDS points to the array of words.
94 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
97 decode (HOST_WIDE_INT
*words
, unsigned HOST_WIDE_INT
*low
,
100 *low
= words
[0] + words
[1] * BASE
;
101 *hi
= words
[2] + words
[3] * BASE
;
104 /* Add two doubleword integers with doubleword result.
105 Return nonzero if the operation overflows according to UNSIGNED_P.
106 Each argument is given as two `HOST_WIDE_INT' pieces.
107 One argument is L1 and H1; the other, L2 and H2.
108 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
111 add_double_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
112 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
113 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
116 unsigned HOST_WIDE_INT l
;
120 h
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) h1
121 + (unsigned HOST_WIDE_INT
) h2
128 return ((unsigned HOST_WIDE_INT
) h
< (unsigned HOST_WIDE_INT
) h1
132 return OVERFLOW_SUM_SIGN (h1
, h2
, h
);
135 /* Negate a doubleword integer with doubleword result.
136 Return nonzero if the operation overflows, assuming it's signed.
137 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
138 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
141 neg_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
142 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
)
147 *hv
= - (unsigned HOST_WIDE_INT
) h1
;
148 return (*hv
& h1
) < 0;
158 /* Multiply two doubleword integers with quadword result.
159 Return nonzero if the operation overflows according to UNSIGNED_P.
160 Each argument is given as two `HOST_WIDE_INT' pieces.
161 One argument is L1 and H1; the other, L2 and H2.
162 The value is stored as four `HOST_WIDE_INT' pieces in *LV and *HV,
164 If lw is NULL then only the low part and no overflow is computed. */
167 mul_double_wide_with_sign (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
168 unsigned HOST_WIDE_INT l2
, HOST_WIDE_INT h2
,
169 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
170 unsigned HOST_WIDE_INT
*lw
, HOST_WIDE_INT
*hw
,
173 HOST_WIDE_INT arg1
[4];
174 HOST_WIDE_INT arg2
[4];
175 HOST_WIDE_INT prod
[4 * 2];
176 unsigned HOST_WIDE_INT carry
;
178 unsigned HOST_WIDE_INT neglow
;
179 HOST_WIDE_INT neghigh
;
181 encode (arg1
, l1
, h1
);
182 encode (arg2
, l2
, h2
);
184 memset (prod
, 0, sizeof prod
);
186 for (i
= 0; i
< 4; i
++)
189 for (j
= 0; j
< 4; j
++)
192 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
193 carry
+= (unsigned HOST_WIDE_INT
) arg1
[i
] * arg2
[j
];
194 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
196 prod
[k
] = LOWPART (carry
);
197 carry
= HIGHPART (carry
);
202 decode (prod
, lv
, hv
);
204 /* We are not interested in the wide part nor in overflow. */
208 decode (prod
+ 4, lw
, hw
);
210 /* Unsigned overflow is immediate. */
212 return (*lw
| *hw
) != 0;
214 /* Check for signed overflow by calculating the signed representation of the
215 top half of the result; it should agree with the low half's sign bit. */
218 neg_double (l2
, h2
, &neglow
, &neghigh
);
219 add_double (neglow
, neghigh
, *lw
, *hw
, lw
, hw
);
223 neg_double (l1
, h1
, &neglow
, &neghigh
);
224 add_double (neglow
, neghigh
, *lw
, *hw
, lw
, hw
);
226 return (*hv
< 0 ? ~(*lw
& *hw
) : *lw
| *hw
) != 0;
229 /* Shift the doubleword integer in L1, H1 right by COUNT places
230 keeping only PREC bits of result. ARITH nonzero specifies
231 arithmetic shifting; otherwise use logical shift.
232 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
235 rshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
236 unsigned HOST_WIDE_INT count
, unsigned int prec
,
237 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
,
240 unsigned HOST_WIDE_INT signmask
;
243 ? -((unsigned HOST_WIDE_INT
) h1
>> (HOST_BITS_PER_WIDE_INT
- 1))
246 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
248 /* Shifting by the host word size is undefined according to the
249 ANSI standard, so we must handle this as a special case. */
253 else if (count
>= HOST_BITS_PER_WIDE_INT
)
256 *lv
= (unsigned HOST_WIDE_INT
) h1
>> (count
- HOST_BITS_PER_WIDE_INT
);
260 *hv
= (unsigned HOST_WIDE_INT
) h1
>> count
;
262 | ((unsigned HOST_WIDE_INT
) h1
263 << (HOST_BITS_PER_WIDE_INT
- count
- 1) << 1));
266 /* Zero / sign extend all bits that are beyond the precision. */
273 else if ((prec
- count
) >= HOST_BITS_PER_DOUBLE_INT
)
275 else if ((prec
- count
) >= HOST_BITS_PER_WIDE_INT
)
277 *hv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- count
- HOST_BITS_PER_WIDE_INT
));
278 *hv
|= signmask
<< (prec
- count
- HOST_BITS_PER_WIDE_INT
);
283 *lv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- count
));
284 *lv
|= signmask
<< (prec
- count
);
288 /* Shift the doubleword integer in L1, H1 left by COUNT places
289 keeping only PREC bits of result.
290 Shift right if COUNT is negative.
291 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
292 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
295 lshift_double (unsigned HOST_WIDE_INT l1
, HOST_WIDE_INT h1
,
296 unsigned HOST_WIDE_INT count
, unsigned int prec
,
297 unsigned HOST_WIDE_INT
*lv
, HOST_WIDE_INT
*hv
)
299 unsigned HOST_WIDE_INT signmask
;
301 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
303 /* Shifting by the host word size is undefined according to the
304 ANSI standard, so we must handle this as a special case. */
308 else if (count
>= HOST_BITS_PER_WIDE_INT
)
310 *hv
= l1
<< (count
- HOST_BITS_PER_WIDE_INT
);
315 *hv
= (((unsigned HOST_WIDE_INT
) h1
<< count
)
316 | (l1
>> (HOST_BITS_PER_WIDE_INT
- count
- 1) >> 1));
320 /* Sign extend all bits that are beyond the precision. */
322 signmask
= -((prec
> HOST_BITS_PER_WIDE_INT
323 ? ((unsigned HOST_WIDE_INT
) *hv
324 >> (prec
- HOST_BITS_PER_WIDE_INT
- 1))
325 : (*lv
>> (prec
- 1))) & 1);
327 if (prec
>= HOST_BITS_PER_DOUBLE_INT
)
329 else if (prec
>= HOST_BITS_PER_WIDE_INT
)
331 *hv
&= ~(HOST_WIDE_INT_M1U
<< (prec
- HOST_BITS_PER_WIDE_INT
));
332 *hv
|= signmask
<< (prec
- HOST_BITS_PER_WIDE_INT
);
337 *lv
&= ~(HOST_WIDE_INT_M1U
<< prec
);
338 *lv
|= signmask
<< prec
;
342 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
343 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
344 CODE is a tree code for a kind of division, one of
345 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
347 It controls how the quotient is rounded to an integer.
348 Return nonzero if the operation overflows.
349 UNS nonzero says do unsigned division. */
352 div_and_round_double (unsigned code
, int uns
,
353 /* num == numerator == dividend */
354 unsigned HOST_WIDE_INT lnum_orig
,
355 HOST_WIDE_INT hnum_orig
,
356 /* den == denominator == divisor */
357 unsigned HOST_WIDE_INT lden_orig
,
358 HOST_WIDE_INT hden_orig
,
359 unsigned HOST_WIDE_INT
*lquo
,
360 HOST_WIDE_INT
*hquo
, unsigned HOST_WIDE_INT
*lrem
,
364 HOST_WIDE_INT num
[4 + 1]; /* extra element for scaling. */
365 HOST_WIDE_INT den
[4], quo
[4];
367 unsigned HOST_WIDE_INT work
;
368 unsigned HOST_WIDE_INT carry
= 0;
369 unsigned HOST_WIDE_INT lnum
= lnum_orig
;
370 HOST_WIDE_INT hnum
= hnum_orig
;
371 unsigned HOST_WIDE_INT lden
= lden_orig
;
372 HOST_WIDE_INT hden
= hden_orig
;
375 if (hden
== 0 && lden
== 0)
376 overflow
= 1, lden
= 1;
378 /* Calculate quotient sign and convert operands to unsigned. */
384 /* (minimum integer) / (-1) is the only overflow case. */
385 if (neg_double (lnum
, hnum
, &lnum
, &hnum
)
386 && ((HOST_WIDE_INT
) lden
& hden
) == -1)
392 neg_double (lden
, hden
, &lden
, &hden
);
396 if (hnum
== 0 && hden
== 0)
397 { /* single precision */
399 /* This unsigned division rounds toward zero. */
405 { /* trivial case: dividend < divisor */
406 /* hden != 0 already checked. */
413 memset (quo
, 0, sizeof quo
);
415 memset (num
, 0, sizeof num
); /* to zero 9th element */
416 memset (den
, 0, sizeof den
);
418 encode (num
, lnum
, hnum
);
419 encode (den
, lden
, hden
);
421 /* Special code for when the divisor < BASE. */
422 if (hden
== 0 && lden
< (unsigned HOST_WIDE_INT
) BASE
)
424 /* hnum != 0 already checked. */
425 for (i
= 4 - 1; i
>= 0; i
--)
427 work
= num
[i
] + carry
* BASE
;
428 quo
[i
] = work
/ lden
;
434 /* Full double precision division,
435 with thanks to Don Knuth's "Seminumerical Algorithms". */
436 int num_hi_sig
, den_hi_sig
;
437 unsigned HOST_WIDE_INT quo_est
, scale
;
439 /* Find the highest nonzero divisor digit. */
440 for (i
= 4 - 1;; i
--)
447 /* Insure that the first digit of the divisor is at least BASE/2.
448 This is required by the quotient digit estimation algorithm. */
450 scale
= BASE
/ (den
[den_hi_sig
] + 1);
452 { /* scale divisor and dividend */
454 for (i
= 0; i
<= 4 - 1; i
++)
456 work
= (num
[i
] * scale
) + carry
;
457 num
[i
] = LOWPART (work
);
458 carry
= HIGHPART (work
);
463 for (i
= 0; i
<= 4 - 1; i
++)
465 work
= (den
[i
] * scale
) + carry
;
466 den
[i
] = LOWPART (work
);
467 carry
= HIGHPART (work
);
468 if (den
[i
] != 0) den_hi_sig
= i
;
475 for (i
= num_hi_sig
- den_hi_sig
- 1; i
>= 0; i
--)
477 /* Guess the next quotient digit, quo_est, by dividing the first
478 two remaining dividend digits by the high order quotient digit.
479 quo_est is never low and is at most 2 high. */
480 unsigned HOST_WIDE_INT tmp
;
482 num_hi_sig
= i
+ den_hi_sig
+ 1;
483 work
= num
[num_hi_sig
] * BASE
+ num
[num_hi_sig
- 1];
484 if (num
[num_hi_sig
] != den
[den_hi_sig
])
485 quo_est
= work
/ den
[den_hi_sig
];
489 /* Refine quo_est so it's usually correct, and at most one high. */
490 tmp
= work
- quo_est
* den
[den_hi_sig
];
492 && (den
[den_hi_sig
- 1] * quo_est
493 > (tmp
* BASE
+ num
[num_hi_sig
- 2])))
496 /* Try QUO_EST as the quotient digit, by multiplying the
497 divisor by QUO_EST and subtracting from the remaining dividend.
498 Keep in mind that QUO_EST is the I - 1st digit. */
501 for (j
= 0; j
<= den_hi_sig
; j
++)
503 work
= quo_est
* den
[j
] + carry
;
504 carry
= HIGHPART (work
);
505 work
= num
[i
+ j
] - LOWPART (work
);
506 num
[i
+ j
] = LOWPART (work
);
507 carry
+= HIGHPART (work
) != 0;
510 /* If quo_est was high by one, then num[i] went negative and
511 we need to correct things. */
512 if (num
[num_hi_sig
] < (HOST_WIDE_INT
) carry
)
515 carry
= 0; /* add divisor back in */
516 for (j
= 0; j
<= den_hi_sig
; j
++)
518 work
= num
[i
+ j
] + den
[j
] + carry
;
519 carry
= HIGHPART (work
);
520 num
[i
+ j
] = LOWPART (work
);
523 num
[num_hi_sig
] += carry
;
526 /* Store the quotient digit. */
531 decode (quo
, lquo
, hquo
);
534 /* If result is negative, make it so. */
536 neg_double (*lquo
, *hquo
, lquo
, hquo
);
538 /* Compute trial remainder: rem = num - (quo * den) */
539 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
540 neg_double (*lrem
, *hrem
, lrem
, hrem
);
541 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
546 case TRUNC_MOD_EXPR
: /* round toward zero */
547 case EXACT_DIV_EXPR
: /* for this one, it shouldn't matter */
551 case FLOOR_MOD_EXPR
: /* round toward negative infinity */
552 if (quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio < 0 && rem != 0 */
555 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) -1, (HOST_WIDE_INT
) -1,
563 case CEIL_MOD_EXPR
: /* round toward positive infinity */
564 if (!quo_neg
&& (*lrem
!= 0 || *hrem
!= 0)) /* ratio > 0 && rem != 0 */
566 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) 1, (HOST_WIDE_INT
) 0,
574 case ROUND_MOD_EXPR
: /* round to closest integer */
576 unsigned HOST_WIDE_INT labs_rem
= *lrem
;
577 HOST_WIDE_INT habs_rem
= *hrem
;
578 unsigned HOST_WIDE_INT labs_den
= lden
, lnegabs_rem
, ldiff
;
579 HOST_WIDE_INT habs_den
= hden
, hnegabs_rem
, hdiff
;
581 /* Get absolute values. */
582 if (!uns
&& *hrem
< 0)
583 neg_double (*lrem
, *hrem
, &labs_rem
, &habs_rem
);
584 if (!uns
&& hden
< 0)
585 neg_double (lden
, hden
, &labs_den
, &habs_den
);
587 /* If abs(rem) >= abs(den) - abs(rem), adjust the quotient. */
588 neg_double (labs_rem
, habs_rem
, &lnegabs_rem
, &hnegabs_rem
);
589 add_double (labs_den
, habs_den
, lnegabs_rem
, hnegabs_rem
,
592 if (((unsigned HOST_WIDE_INT
) habs_rem
593 > (unsigned HOST_WIDE_INT
) hdiff
)
594 || (habs_rem
== hdiff
&& labs_rem
>= ldiff
))
598 add_double (*lquo
, *hquo
,
599 (HOST_WIDE_INT
) -1, (HOST_WIDE_INT
) -1, lquo
, hquo
);
602 add_double (*lquo
, *hquo
, (HOST_WIDE_INT
) 1, (HOST_WIDE_INT
) 0,
614 /* Compute true remainder: rem = num - (quo * den) */
615 mul_double (*lquo
, *hquo
, lden_orig
, hden_orig
, lrem
, hrem
);
616 neg_double (*lrem
, *hrem
, lrem
, hrem
);
617 add_double (lnum_orig
, hnum_orig
, *lrem
, *hrem
, lrem
, hrem
);
622 /* Construct from a buffer of length LEN. BUFFER will be read according
623 to byte endianess and word endianess. Only the lower LEN bytes
624 of the result are set; the remaining high bytes are cleared. */
627 double_int::from_buffer (const unsigned char *buffer
, int len
)
629 double_int result
= double_int_zero
;
630 int words
= len
/ UNITS_PER_WORD
;
632 gcc_assert (len
* BITS_PER_UNIT
<= HOST_BITS_PER_DOUBLE_INT
);
634 for (int byte
= 0; byte
< len
; byte
++)
637 int bitpos
= byte
* BITS_PER_UNIT
;
638 unsigned HOST_WIDE_INT value
;
640 if (len
> UNITS_PER_WORD
)
642 int word
= byte
/ UNITS_PER_WORD
;
644 if (WORDS_BIG_ENDIAN
)
645 word
= (words
- 1) - word
;
647 offset
= word
* UNITS_PER_WORD
;
649 if (BYTES_BIG_ENDIAN
)
650 offset
+= (UNITS_PER_WORD
- 1) - (byte
% UNITS_PER_WORD
);
652 offset
+= byte
% UNITS_PER_WORD
;
655 offset
= BYTES_BIG_ENDIAN
? (len
- 1) - byte
: byte
;
657 value
= (unsigned HOST_WIDE_INT
) buffer
[offset
];
659 if (bitpos
< HOST_BITS_PER_WIDE_INT
)
660 result
.low
|= value
<< bitpos
;
662 result
.high
|= value
<< (bitpos
- HOST_BITS_PER_WIDE_INT
);
669 /* Returns mask for PREC bits. */
672 double_int::mask (unsigned prec
)
674 unsigned HOST_WIDE_INT m
;
677 if (prec
> HOST_BITS_PER_WIDE_INT
)
679 prec
-= HOST_BITS_PER_WIDE_INT
;
680 m
= ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1;
681 mask
.high
= (HOST_WIDE_INT
) m
;
687 mask
.low
= prec
? ((unsigned HOST_WIDE_INT
) 2 << (prec
- 1)) - 1 : 0;
693 /* Returns a maximum value for signed or unsigned integer
694 of precision PREC. */
697 double_int::max_value (unsigned int prec
, bool uns
)
699 return double_int::mask (prec
- (uns
? 0 : 1));
702 /* Returns a minimum value for signed or unsigned integer
703 of precision PREC. */
706 double_int::min_value (unsigned int prec
, bool uns
)
709 return double_int_zero
;
710 return double_int_one
.lshift (prec
- 1, prec
, false);
713 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
714 outside of the precision are set to the sign bit (i.e., the PREC-th one),
715 otherwise they are set to zero.
717 This corresponds to returning the value represented by PREC lowermost bits
718 of CST, with the given signedness. */
721 double_int::ext (unsigned prec
, bool uns
) const
724 return this->zext (prec
);
726 return this->sext (prec
);
729 /* The same as double_int::ext with UNS = true. */
732 double_int::zext (unsigned prec
) const
734 const double_int
&cst
= *this;
735 double_int mask
= double_int::mask (prec
);
738 r
.low
= cst
.low
& mask
.low
;
739 r
.high
= cst
.high
& mask
.high
;
744 /* The same as double_int::ext with UNS = false. */
747 double_int::sext (unsigned prec
) const
749 const double_int
&cst
= *this;
750 double_int mask
= double_int::mask (prec
);
752 unsigned HOST_WIDE_INT snum
;
754 if (prec
<= HOST_BITS_PER_WIDE_INT
)
758 prec
-= HOST_BITS_PER_WIDE_INT
;
759 snum
= (unsigned HOST_WIDE_INT
) cst
.high
;
761 if (((snum
>> (prec
- 1)) & 1) == 1)
763 r
.low
= cst
.low
| ~mask
.low
;
764 r
.high
= cst
.high
| ~mask
.high
;
768 r
.low
= cst
.low
& mask
.low
;
769 r
.high
= cst
.high
& mask
.high
;
775 /* Returns true if CST fits in signed HOST_WIDE_INT. */
778 double_int::fits_shwi () const
780 const double_int
&cst
= *this;
782 return (HOST_WIDE_INT
) cst
.low
>= 0;
783 else if (cst
.high
== -1)
784 return (HOST_WIDE_INT
) cst
.low
< 0;
789 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
790 unsigned HOST_WIDE_INT if UNS is true. */
793 double_int::fits_hwi (bool uns
) const
796 return this->fits_uhwi ();
798 return this->fits_shwi ();
804 double_int::operator * (double_int b
) const
806 const double_int
&a
= *this;
808 mul_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
812 /* Multiplies *this with B and returns a reference to *this. */
815 double_int::operator *= (double_int b
)
817 mul_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
821 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
822 *OVERFLOW is set to nonzero. */
825 double_int::mul_with_sign (double_int b
, bool unsigned_p
, bool *overflow
) const
827 const double_int
&a
= *this;
829 *overflow
= mul_double_wide_with_sign (a
.low
, a
.high
, b
.low
, b
.high
,
831 &tem
.low
, &tem
.high
, unsigned_p
);
836 double_int::wide_mul_with_sign (double_int b
, bool unsigned_p
,
837 double_int
*higher
, bool *overflow
) const
841 *overflow
= mul_double_wide_with_sign (low
, high
, b
.low
, b
.high
,
842 &lower
.low
, &lower
.high
,
843 &higher
->low
, &higher
->high
,
851 double_int::operator + (double_int b
) const
853 const double_int
&a
= *this;
855 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
859 /* Adds B to *this and returns a reference to *this. */
862 double_int::operator += (double_int b
)
864 add_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
869 /* Returns A + B. If the operation overflows according to UNSIGNED_P,
870 *OVERFLOW is set to nonzero. */
873 double_int::add_with_sign (double_int b
, bool unsigned_p
, bool *overflow
) const
875 const double_int
&a
= *this;
877 *overflow
= add_double_with_sign (a
.low
, a
.high
, b
.low
, b
.high
,
878 &ret
.low
, &ret
.high
, unsigned_p
);
885 double_int::operator - (double_int b
) const
887 const double_int
&a
= *this;
889 neg_double (b
.low
, b
.high
, &b
.low
, &b
.high
);
890 add_double (a
.low
, a
.high
, b
.low
, b
.high
, &ret
.low
, &ret
.high
);
894 /* Subtracts B from *this and returns a reference to *this. */
897 double_int::operator -= (double_int b
)
899 neg_double (b
.low
, b
.high
, &b
.low
, &b
.high
);
900 add_double (low
, high
, b
.low
, b
.high
, &low
, &high
);
905 /* Returns A - B. If the operation overflows via inconsistent sign bits,
906 *OVERFLOW is set to nonzero. */
909 double_int::sub_with_overflow (double_int b
, bool *overflow
) const
912 neg_double (b
.low
, b
.high
, &ret
.low
, &ret
.high
);
913 add_double (low
, high
, ret
.low
, ret
.high
, &ret
.low
, &ret
.high
);
914 *overflow
= OVERFLOW_SUM_SIGN (ret
.high
, b
.high
, high
);
921 double_int::operator - () const
923 const double_int
&a
= *this;
925 neg_double (a
.low
, a
.high
, &ret
.low
, &ret
.high
);
930 double_int::neg_with_overflow (bool *overflow
) const
933 *overflow
= neg_double (low
, high
, &ret
.low
, &ret
.high
);
937 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
938 specified by CODE). CODE is enum tree_code in fact, but double_int.h
939 must be included before tree.h. The remainder after the division is
943 double_int::divmod_with_overflow (double_int b
, bool uns
, unsigned code
,
944 double_int
*mod
, bool *overflow
) const
946 const double_int
&a
= *this;
949 *overflow
= div_and_round_double (code
, uns
, a
.low
, a
.high
,
950 b
.low
, b
.high
, &ret
.low
, &ret
.high
,
951 &mod
->low
, &mod
->high
);
956 double_int::divmod (double_int b
, bool uns
, unsigned code
,
957 double_int
*mod
) const
959 const double_int
&a
= *this;
962 div_and_round_double (code
, uns
, a
.low
, a
.high
,
963 b
.low
, b
.high
, &ret
.low
, &ret
.high
,
964 &mod
->low
, &mod
->high
);
968 /* The same as double_int::divmod with UNS = false. */
971 double_int::sdivmod (double_int b
, unsigned code
, double_int
*mod
) const
973 return this->divmod (b
, false, code
, mod
);
976 /* The same as double_int::divmod with UNS = true. */
979 double_int::udivmod (double_int b
, unsigned code
, double_int
*mod
) const
981 return this->divmod (b
, true, code
, mod
);
984 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
985 specified by CODE). CODE is enum tree_code in fact, but double_int.h
986 must be included before tree.h. */
989 double_int::div (double_int b
, bool uns
, unsigned code
) const
993 return this->divmod (b
, uns
, code
, &mod
);
996 /* The same as double_int::div with UNS = false. */
999 double_int::sdiv (double_int b
, unsigned code
) const
1001 return this->div (b
, false, code
);
1004 /* The same as double_int::div with UNS = true. */
1007 double_int::udiv (double_int b
, unsigned code
) const
1009 return this->div (b
, true, code
);
1012 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
1013 specified by CODE). CODE is enum tree_code in fact, but double_int.h
1014 must be included before tree.h. */
1017 double_int::mod (double_int b
, bool uns
, unsigned code
) const
1021 this->divmod (b
, uns
, code
, &mod
);
1025 /* The same as double_int::mod with UNS = false. */
1028 double_int::smod (double_int b
, unsigned code
) const
1030 return this->mod (b
, false, code
);
1033 /* The same as double_int::mod with UNS = true. */
1036 double_int::umod (double_int b
, unsigned code
) const
1038 return this->mod (b
, true, code
);
1041 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
1042 the multiple in *MULTIPLE. Otherwise return FALSE and leave *MULTIPLE
1046 double_int::multiple_of (double_int factor
,
1047 bool unsigned_p
, double_int
*multiple
) const
1049 double_int remainder
;
1050 double_int quotient
= this->divmod (factor
, unsigned_p
,
1051 TRUNC_DIV_EXPR
, &remainder
);
1052 if (remainder
.is_zero ())
1054 *multiple
= quotient
;
1061 /* Set BITPOS bit in A. */
1063 double_int::set_bit (unsigned bitpos
) const
1065 double_int a
= *this;
1066 if (bitpos
< HOST_BITS_PER_WIDE_INT
)
1067 a
.low
|= (unsigned HOST_WIDE_INT
) 1 << bitpos
;
1069 a
.high
|= (HOST_WIDE_INT
) 1 << (bitpos
- HOST_BITS_PER_WIDE_INT
);
1074 /* Count trailing zeros in A. */
1076 double_int::trailing_zeros () const
1078 const double_int
&a
= *this;
1079 unsigned HOST_WIDE_INT w
= a
.low
? a
.low
: (unsigned HOST_WIDE_INT
) a
.high
;
1080 unsigned bits
= a
.low
? 0 : HOST_BITS_PER_WIDE_INT
;
1082 return HOST_BITS_PER_DOUBLE_INT
;
1083 bits
+= ctz_hwi (w
);
1087 /* Shift A left by COUNT places. */
1090 double_int::lshift (HOST_WIDE_INT count
) const
1094 gcc_checking_assert (count
>= 0);
1096 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
1098 /* Shifting by the host word size is undefined according to the
1099 ANSI standard, so we must handle this as a special case. */
1103 else if (count
>= HOST_BITS_PER_WIDE_INT
)
1105 ret
.high
= low
<< (count
- HOST_BITS_PER_WIDE_INT
);
1110 ret
.high
= (((unsigned HOST_WIDE_INT
) high
<< count
)
1111 | (low
>> (HOST_BITS_PER_WIDE_INT
- count
- 1) >> 1));
1112 ret
.low
= low
<< count
;
1118 /* Shift A right by COUNT places. */
1121 double_int::rshift (HOST_WIDE_INT count
) const
1125 gcc_checking_assert (count
>= 0);
1127 if (count
>= HOST_BITS_PER_DOUBLE_INT
)
1129 /* Shifting by the host word size is undefined according to the
1130 ANSI standard, so we must handle this as a special case. */
1134 else if (count
>= HOST_BITS_PER_WIDE_INT
)
1138 = (unsigned HOST_WIDE_INT
) (high
>> (count
- HOST_BITS_PER_WIDE_INT
));
1142 ret
.high
= high
>> count
;
1143 ret
.low
= ((low
>> count
)
1144 | ((unsigned HOST_WIDE_INT
) high
1145 << (HOST_BITS_PER_WIDE_INT
- count
- 1) << 1));
1151 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
1152 right if COUNT is negative. ARITH true specifies arithmetic shifting;
1153 otherwise use logical shift. */
1156 double_int::lshift (HOST_WIDE_INT count
, unsigned int prec
, bool arith
) const
1160 lshift_double (low
, high
, count
, prec
, &ret
.low
, &ret
.high
);
1162 rshift_double (low
, high
, absu_hwi (count
), prec
, &ret
.low
, &ret
.high
, arith
);
1166 /* Shift A right by COUNT places keeping only PREC bits of result. Shift
1167 left if COUNT is negative. ARITH true specifies arithmetic shifting;
1168 otherwise use logical shift. */
1171 double_int::rshift (HOST_WIDE_INT count
, unsigned int prec
, bool arith
) const
1175 rshift_double (low
, high
, count
, prec
, &ret
.low
, &ret
.high
, arith
);
1177 lshift_double (low
, high
, absu_hwi (count
), prec
, &ret
.low
, &ret
.high
);
1181 /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
1182 Shift right if COUNT is negative. */
1185 double_int::alshift (HOST_WIDE_INT count
, unsigned int prec
) const
1189 lshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
);
1191 rshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
, true);
1195 /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
1196 Shift left if COUNT is negative. */
1199 double_int::arshift (HOST_WIDE_INT count
, unsigned int prec
) const
1203 rshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
, true);
1205 lshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
);
1209 /* Logical shift A left by COUNT places keeping only PREC bits of result.
1210 Shift right if COUNT is negative. */
1213 double_int::llshift (HOST_WIDE_INT count
, unsigned int prec
) const
1217 lshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
);
1219 rshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
, false);
1223 /* Logical shift A right by COUNT places keeping only PREC bits of result.
1224 Shift left if COUNT is negative. */
1227 double_int::lrshift (HOST_WIDE_INT count
, unsigned int prec
) const
1231 rshift_double (low
, high
, count
, prec
, &r
.low
, &r
.high
, false);
1233 lshift_double (low
, high
, absu_hwi (count
), prec
, &r
.low
, &r
.high
);
1237 /* Rotate A left by COUNT places keeping only PREC bits of result.
1238 Rotate right if COUNT is negative. */
1241 double_int::lrotate (HOST_WIDE_INT count
, unsigned int prec
) const
1249 t1
= this->llshift (count
, prec
);
1250 t2
= this->lrshift (prec
- count
, prec
);
1255 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1256 Rotate right if COUNT is negative. */
1259 double_int::rrotate (HOST_WIDE_INT count
, unsigned int prec
) const
1267 t1
= this->lrshift (count
, prec
);
1268 t2
= this->llshift (prec
- count
, prec
);
1273 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
1274 comparison is given by UNS. */
1277 double_int::cmp (double_int b
, bool uns
) const
1280 return this->ucmp (b
);
1282 return this->scmp (b
);
1285 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
1289 double_int::ucmp (double_int b
) const
1291 const double_int
&a
= *this;
1292 if ((unsigned HOST_WIDE_INT
) a
.high
< (unsigned HOST_WIDE_INT
) b
.high
)
1294 if ((unsigned HOST_WIDE_INT
) a
.high
> (unsigned HOST_WIDE_INT
) b
.high
)
1304 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
1308 double_int::scmp (double_int b
) const
1310 const double_int
&a
= *this;
1311 if (a
.high
< b
.high
)
1313 if (a
.high
> b
.high
)
1323 /* Compares two unsigned values A and B for less-than. */
1326 double_int::ult (double_int b
) const
1328 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1330 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1337 /* Compares two unsigned values A and B for less-than or equal-to. */
1340 double_int::ule (double_int b
) const
1342 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1344 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1351 /* Compares two unsigned values A and B for greater-than. */
1354 double_int::ugt (double_int b
) const
1356 if ((unsigned HOST_WIDE_INT
) high
> (unsigned HOST_WIDE_INT
) b
.high
)
1358 if ((unsigned HOST_WIDE_INT
) high
< (unsigned HOST_WIDE_INT
) b
.high
)
1365 /* Compares two signed values A and B for less-than. */
1368 double_int::slt (double_int b
) const
1379 /* Compares two signed values A and B for less-than or equal-to. */
1382 double_int::sle (double_int b
) const
1393 /* Compares two signed values A and B for greater-than. */
1396 double_int::sgt (double_int b
) const
1408 /* Compares two values A and B. Returns max value. Signedness of the
1409 comparison is given by UNS. */
1412 double_int::max (double_int b
, bool uns
)
1414 return (this->cmp (b
, uns
) == 1) ? *this : b
;
1417 /* Compares two signed values A and B. Returns max value. */
1420 double_int::smax (double_int b
)
1422 return (this->scmp (b
) == 1) ? *this : b
;
1425 /* Compares two unsigned values A and B. Returns max value. */
1428 double_int::umax (double_int b
)
1430 return (this->ucmp (b
) == 1) ? *this : b
;
1433 /* Compares two values A and B. Returns mix value. Signedness of the
1434 comparison is given by UNS. */
1437 double_int::min (double_int b
, bool uns
)
1439 return (this->cmp (b
, uns
) == -1) ? *this : b
;
1442 /* Compares two signed values A and B. Returns min value. */
1445 double_int::smin (double_int b
)
1447 return (this->scmp (b
) == -1) ? *this : b
;
1450 /* Compares two unsigned values A and B. Returns min value. */
1453 double_int::umin (double_int b
)
1455 return (this->ucmp (b
) == -1) ? *this : b
;
1458 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1461 double_int_split_digit (double_int
*cst
, unsigned base
)
1463 unsigned HOST_WIDE_INT resl
, reml
;
1464 HOST_WIDE_INT resh
, remh
;
1466 div_and_round_double (FLOOR_DIV_EXPR
, true, cst
->low
, cst
->high
, base
, 0,
1467 &resl
, &resh
, &reml
, &remh
);
1474 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1475 otherwise it is signed. */
1478 dump_double_int (FILE *file
, double_int cst
, bool uns
)
1480 unsigned digits
[100], n
;
1485 fprintf (file
, "0");
1489 if (!uns
&& cst
.is_negative ())
1491 fprintf (file
, "-");
1495 for (n
= 0; !cst
.is_zero (); n
++)
1496 digits
[n
] = double_int_split_digit (&cst
, 10);
1497 for (i
= n
- 1; i
>= 0; i
--)
1498 fprintf (file
, "%u", digits
[i
]);
1502 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1506 mpz_set_double_int (mpz_t result
, double_int val
, bool uns
)
1508 bool negate
= false;
1509 unsigned HOST_WIDE_INT vp
[2];
1511 if (!uns
&& val
.is_negative ())
1518 vp
[1] = (unsigned HOST_WIDE_INT
) val
.high
;
1519 mpz_import (result
, 2, -1, sizeof (HOST_WIDE_INT
), 0, 0, vp
);
1522 mpz_neg (result
, result
);
1525 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
1526 values of VAL will be wrapped; otherwise, they will be set to the
1527 appropriate minimum or maximum TYPE bound. */
1530 mpz_get_double_int (const_tree type
, mpz_t val
, bool wrap
)
1532 unsigned HOST_WIDE_INT
*vp
;
1542 get_type_static_bounds (type
, min
, max
);
1544 if (mpz_cmp (val
, min
) < 0)
1546 else if (mpz_cmp (val
, max
) > 0)
1553 /* Determine the number of unsigned HOST_WIDE_INT that are required
1554 for representing the value. The code to calculate count is
1555 extracted from the GMP manual, section "Integer Import and Export":
1556 http://gmplib.org/manual/Integer-Import-and-Export.html */
1557 numb
= 8 * sizeof (HOST_WIDE_INT
);
1558 count
= (mpz_sizeinbase (val
, 2) + numb
-1) / numb
;
1561 vp
= (unsigned HOST_WIDE_INT
*) alloca (count
* sizeof (HOST_WIDE_INT
));
1565 mpz_export (vp
, &count
, -1, sizeof (HOST_WIDE_INT
), 0, 0, val
);
1567 gcc_assert (wrap
|| count
<= 2);
1570 res
.high
= (HOST_WIDE_INT
) vp
[1];
1572 res
= res
.ext (TYPE_PRECISION (type
), TYPE_UNSIGNED (type
));
1573 if (mpz_sgn (val
) < 0)