Line data Source code
1 : /* Operations with long integers.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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
9 : later version.
10 :
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
14 : for more details.
15 :
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/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "tm.h" /* For BITS_PER_UNIT and *_BIG_ENDIAN. */
24 : #include "tree.h"
25 :
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 *,
29 : bool);
30 :
31 : #define add_double(l1,h1,l2,h2,lv,hv) \
32 : add_double_with_sign (l1, h1, l2, h2, lv, hv, false)
33 :
34 : static int neg_double (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
35 : unsigned HOST_WIDE_INT *, HOST_WIDE_INT *);
36 :
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 *,
41 : bool);
42 :
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)
45 :
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 *,
50 : HOST_WIDE_INT *);
51 :
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
55 : addition.
56 :
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
59 : sign. */
60 : #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
61 :
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. */
66 :
67 : #define LOWPART(x) \
68 : ((x) & ((HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
69 : #define HIGHPART(x) \
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)
72 :
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. */
76 :
77 : static void
78 5 : encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
79 : {
80 5 : words[0] = LOWPART (low);
81 5 : words[1] = HIGHPART (low);
82 5 : words[2] = LOWPART (hi);
83 5 : words[3] = HIGHPART (hi);
84 0 : }
85 :
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. */
89 :
90 : static void
91 5 : decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
92 : HOST_WIDE_INT *hi)
93 : {
94 5 : *low = words[0] + words[1] * BASE;
95 5 : *hi = words[2] + words[3] * BASE;
96 2 : }
97 :
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. */
103 :
104 : static int
105 6 : 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,
108 : bool unsigned_p)
109 : {
110 6 : unsigned HOST_WIDE_INT l;
111 6 : HOST_WIDE_INT h;
112 :
113 6 : l = l1 + l2;
114 6 : h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
115 5 : + (unsigned HOST_WIDE_INT) h2
116 6 : + (l < l1));
117 :
118 6 : *lv = l;
119 6 : *hv = h;
120 :
121 0 : if (unsigned_p)
122 0 : return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
123 0 : || (h == h1
124 0 : && l < l1));
125 : else
126 0 : return OVERFLOW_SUM_SIGN (h1, h2, h);
127 : }
128 :
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. */
133 :
134 : static int
135 64457 : neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
136 : unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
137 : {
138 0 : if (l1 == 0)
139 : {
140 3 : *lv = 0;
141 3 : *hv = - (unsigned HOST_WIDE_INT) h1;
142 3 : return (*hv & h1) < 0;
143 : }
144 : else
145 : {
146 64454 : *lv = -l1;
147 64454 : *hv = ~h1;
148 64454 : return 0;
149 : }
150 : }
151 :
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,
157 : *LW and *HW.
158 : If lw is NULL then only the low part and no overflow is computed. */
159 :
160 : static int
161 3 : 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,
165 : bool unsigned_p)
166 : {
167 3 : HOST_WIDE_INT arg1[4];
168 3 : HOST_WIDE_INT arg2[4];
169 3 : HOST_WIDE_INT prod[4 * 2];
170 3 : unsigned HOST_WIDE_INT carry;
171 3 : int i, j, k;
172 3 : unsigned HOST_WIDE_INT neglow;
173 3 : HOST_WIDE_INT neghigh;
174 :
175 3 : encode (arg1, l1, h1);
176 3 : encode (arg2, l2, h2);
177 :
178 3 : memset (prod, 0, sizeof prod);
179 :
180 15 : for (i = 0; i < 4; i++)
181 : {
182 : carry = 0;
183 60 : for (j = 0; j < 4; j++)
184 : {
185 48 : k = i + j;
186 : /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
187 48 : carry += (unsigned HOST_WIDE_INT) arg1[i] * arg2[j];
188 : /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
189 48 : carry += prod[k];
190 48 : prod[k] = LOWPART (carry);
191 48 : carry = HIGHPART (carry);
192 : }
193 12 : prod[i + 4] = carry;
194 : }
195 :
196 3 : decode (prod, lv, hv);
197 :
198 : /* We are not interested in the wide part nor in overflow. */
199 3 : if (lw == NULL)
200 : return 0;
201 :
202 0 : decode (prod + 4, lw, hw);
203 :
204 : /* Unsigned overflow is immediate. */
205 0 : if (unsigned_p)
206 0 : return (*lw | *hw) != 0;
207 :
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. */
210 0 : if (h1 < 0)
211 : {
212 0 : neg_double (l2, h2, &neglow, &neghigh);
213 0 : add_double (neglow, neghigh, *lw, *hw, lw, hw);
214 : }
215 0 : if (h2 < 0)
216 : {
217 0 : neg_double (l1, h1, &neglow, &neghigh);
218 0 : add_double (neglow, neghigh, *lw, *hw, lw, hw);
219 : }
220 0 : return (*hv < 0 ? ~(*lw & *hw) : *lw | *hw) != 0;
221 : }
222 :
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. */
227 :
228 : static void
229 0 : 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,
232 : bool arith)
233 : {
234 0 : unsigned HOST_WIDE_INT signmask;
235 :
236 0 : signmask = (arith
237 0 : ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
238 : : 0);
239 :
240 0 : if (count >= HOST_BITS_PER_DOUBLE_INT)
241 : {
242 : /* Shifting by the host word size is undefined according to the
243 : ANSI standard, so we must handle this as a special case. */
244 0 : *hv = 0;
245 0 : *lv = 0;
246 : }
247 0 : else if (count >= HOST_BITS_PER_WIDE_INT)
248 : {
249 0 : *hv = 0;
250 0 : *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
251 : }
252 : else
253 : {
254 0 : *hv = (unsigned HOST_WIDE_INT) h1 >> count;
255 0 : *lv = ((l1 >> count)
256 0 : | ((unsigned HOST_WIDE_INT) h1
257 0 : << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
258 : }
259 :
260 : /* Zero / sign extend all bits that are beyond the precision. */
261 :
262 0 : if (count >= prec)
263 : {
264 0 : *hv = signmask;
265 0 : *lv = signmask;
266 : }
267 0 : else if ((prec - count) >= HOST_BITS_PER_DOUBLE_INT)
268 : ;
269 0 : else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
270 : {
271 0 : *hv &= ~(HOST_WIDE_INT_M1U << (prec - count - HOST_BITS_PER_WIDE_INT));
272 0 : *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
273 : }
274 : else
275 : {
276 0 : *hv = signmask;
277 0 : *lv &= ~(HOST_WIDE_INT_M1U << (prec - count));
278 0 : *lv |= signmask << (prec - count);
279 : }
280 0 : }
281 :
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. */
287 :
288 : static void
289 2229128 : 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)
292 : {
293 2229128 : unsigned HOST_WIDE_INT signmask;
294 :
295 2229128 : if (count >= HOST_BITS_PER_DOUBLE_INT)
296 : {
297 : /* Shifting by the host word size is undefined according to the
298 : ANSI standard, so we must handle this as a special case. */
299 0 : *hv = 0;
300 0 : *lv = 0;
301 : }
302 2229128 : else if (count >= HOST_BITS_PER_WIDE_INT)
303 : {
304 278641 : *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
305 278641 : *lv = 0;
306 : }
307 : else
308 : {
309 1950487 : *hv = (((unsigned HOST_WIDE_INT) h1 << count)
310 1950487 : | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
311 1950487 : *lv = l1 << count;
312 : }
313 :
314 : /* Sign extend all bits that are beyond the precision. */
315 :
316 2229128 : signmask = -((prec > HOST_BITS_PER_WIDE_INT
317 2229128 : ? ((unsigned HOST_WIDE_INT) *hv
318 2229128 : >> (prec - HOST_BITS_PER_WIDE_INT - 1))
319 2229128 : : (*lv >> (prec - 1))) & 1);
320 :
321 2229128 : if (prec >= HOST_BITS_PER_DOUBLE_INT)
322 : ;
323 0 : else if (prec >= HOST_BITS_PER_WIDE_INT)
324 : {
325 0 : *hv &= ~(HOST_WIDE_INT_M1U << (prec - HOST_BITS_PER_WIDE_INT));
326 0 : *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
327 : }
328 : else
329 : {
330 0 : *hv = signmask;
331 0 : *lv &= ~(HOST_WIDE_INT_M1U << prec);
332 0 : *lv |= signmask << prec;
333 : }
334 2229128 : }
335 :
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
340 : or EXACT_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. */
344 :
345 : static int
346 2 : 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,
355 : HOST_WIDE_INT *hrem)
356 : {
357 2 : int quo_neg = 0;
358 2 : HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
359 2 : HOST_WIDE_INT den[4], quo[4];
360 2 : int i, j;
361 2 : unsigned HOST_WIDE_INT work;
362 2 : unsigned HOST_WIDE_INT carry = 0;
363 2 : unsigned HOST_WIDE_INT lnum = lnum_orig;
364 2 : HOST_WIDE_INT hnum = hnum_orig;
365 2 : unsigned HOST_WIDE_INT lden = lden_orig;
366 2 : HOST_WIDE_INT hden = hden_orig;
367 2 : int overflow = 0;
368 :
369 2 : if (hden == 0 && lden == 0)
370 2 : overflow = 1, lden = 1;
371 :
372 : /* Calculate quotient sign and convert operands to unsigned. */
373 2 : if (!uns)
374 : {
375 0 : if (hnum < 0)
376 : {
377 0 : quo_neg = ~ quo_neg;
378 : /* (minimum integer) / (-1) is the only overflow case. */
379 0 : if (neg_double (lnum, hnum, &lnum, &hnum)
380 0 : && ((HOST_WIDE_INT) lden & hden) == -1)
381 : overflow = 1;
382 : }
383 0 : if (hden < 0)
384 : {
385 0 : quo_neg = ~ quo_neg;
386 0 : neg_double (lden, hden, &lden, &hden);
387 : }
388 : }
389 :
390 2 : if (hnum == 0 && hden == 0)
391 : { /* single precision */
392 0 : *hquo = *hrem = 0;
393 : /* This unsigned division rounds toward zero. */
394 0 : *lquo = lnum / lden;
395 0 : goto finish_up;
396 : }
397 :
398 0 : if (hnum == 0)
399 : { /* trivial case: dividend < divisor */
400 : /* hden != 0 already checked. */
401 0 : *hquo = *lquo = 0;
402 0 : *hrem = hnum;
403 0 : *lrem = lnum;
404 0 : goto finish_up;
405 : }
406 :
407 2 : memset (quo, 0, sizeof quo);
408 :
409 2 : memset (num, 0, sizeof num); /* to zero 9th element */
410 2 : memset (den, 0, sizeof den);
411 :
412 2 : encode (num, lnum, hnum);
413 2 : encode (den, lden, hden);
414 :
415 : /* Special code for when the divisor < BASE. */
416 2 : if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
417 : {
418 : /* hnum != 0 already checked. */
419 0 : for (i = 4 - 1; i >= 0; i--)
420 : {
421 0 : work = num[i] + carry * BASE;
422 0 : quo[i] = work / lden;
423 0 : carry = work % lden;
424 : }
425 : }
426 : else
427 : {
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;
432 :
433 : /* Find the highest nonzero divisor digit. */
434 0 : for (i = 4 - 1;; i--)
435 2 : if (den[i] != 0)
436 : {
437 2 : den_hi_sig = i;
438 2 : break;
439 : }
440 :
441 : /* Insure that the first digit of the divisor is at least BASE/2.
442 : This is required by the quotient digit estimation algorithm. */
443 :
444 2 : scale = BASE / (den[den_hi_sig] + 1);
445 2 : if (scale > 1)
446 : { /* scale divisor and dividend */
447 : carry = 0;
448 0 : for (i = 0; i <= 4 - 1; i++)
449 : {
450 0 : work = (num[i] * scale) + carry;
451 0 : num[i] = LOWPART (work);
452 0 : carry = HIGHPART (work);
453 : }
454 :
455 0 : num[4] = carry;
456 0 : carry = 0;
457 0 : for (i = 0; i <= 4 - 1; i++)
458 : {
459 0 : work = (den[i] * scale) + carry;
460 0 : den[i] = LOWPART (work);
461 0 : carry = HIGHPART (work);
462 0 : if (den[i] != 0) den_hi_sig = i;
463 : }
464 : }
465 :
466 2 : num_hi_sig = 4;
467 :
468 : /* Main loop */
469 4 : for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
470 : {
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 2 : unsigned HOST_WIDE_INT tmp;
475 :
476 2 : num_hi_sig = i + den_hi_sig + 1;
477 2 : work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
478 2 : if (num[num_hi_sig] != den[den_hi_sig])
479 2 : quo_est = work / den[den_hi_sig];
480 : else
481 : quo_est = BASE - 1;
482 :
483 : /* Refine quo_est so it's usually correct, and at most one high. */
484 2 : tmp = work - quo_est * den[den_hi_sig];
485 2 : if (tmp < BASE
486 2 : && (den[den_hi_sig - 1] * quo_est
487 2 : > (tmp * BASE + num[num_hi_sig - 2])))
488 0 : quo_est--;
489 :
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. */
493 :
494 2 : carry = 0;
495 10 : for (j = 0; j <= den_hi_sig; j++)
496 : {
497 8 : work = quo_est * den[j] + carry;
498 8 : carry = HIGHPART (work);
499 8 : work = num[i + j] - LOWPART (work);
500 8 : num[i + j] = LOWPART (work);
501 8 : carry += HIGHPART (work) != 0;
502 : }
503 :
504 : /* If quo_est was high by one, then num[i] went negative and
505 : we need to correct things. */
506 2 : if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
507 : {
508 0 : quo_est--;
509 0 : carry = 0; /* add divisor back in */
510 0 : for (j = 0; j <= den_hi_sig; j++)
511 : {
512 0 : work = num[i + j] + den[j] + carry;
513 0 : carry = HIGHPART (work);
514 0 : num[i + j] = LOWPART (work);
515 : }
516 :
517 0 : num [num_hi_sig] += carry;
518 : }
519 :
520 : /* Store the quotient digit. */
521 2 : quo[i] = quo_est;
522 : }
523 : }
524 :
525 2 : decode (quo, lquo, hquo);
526 :
527 2 : finish_up:
528 : /* If result is negative, make it so. */
529 2 : if (quo_neg)
530 0 : neg_double (*lquo, *hquo, lquo, hquo);
531 :
532 : /* Compute trial remainder: rem = num - (quo * den) */
533 2 : mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
534 2 : neg_double (*lrem, *hrem, lrem, hrem);
535 2 : add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
536 :
537 2 : switch (code)
538 : {
539 : case TRUNC_DIV_EXPR:
540 : case TRUNC_MOD_EXPR: /* round toward zero */
541 : case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
542 : return overflow;
543 :
544 0 : case FLOOR_DIV_EXPR:
545 0 : case FLOOR_MOD_EXPR: /* round toward negative infinity */
546 0 : if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
547 : {
548 : /* quo = quo - 1; */
549 0 : add_double (*lquo, *hquo, HOST_WIDE_INT_M1, HOST_WIDE_INT_M1,
550 : lquo, hquo);
551 : }
552 : else
553 : return overflow;
554 0 : break;
555 :
556 0 : case CEIL_DIV_EXPR:
557 0 : case CEIL_MOD_EXPR: /* round toward positive infinity */
558 0 : if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
559 : {
560 0 : add_double (*lquo, *hquo, HOST_WIDE_INT_1, HOST_WIDE_INT_0,
561 : lquo, hquo);
562 : }
563 : else
564 : return overflow;
565 0 : break;
566 :
567 2 : case ROUND_DIV_EXPR:
568 2 : case ROUND_MOD_EXPR: /* round to closest integer */
569 2 : {
570 2 : unsigned HOST_WIDE_INT labs_rem = *lrem;
571 2 : HOST_WIDE_INT habs_rem = *hrem;
572 2 : unsigned HOST_WIDE_INT labs_den = lden, lnegabs_rem, ldiff;
573 2 : HOST_WIDE_INT habs_den = hden, hnegabs_rem, hdiff;
574 :
575 : /* Get absolute values. */
576 2 : if (!uns && *hrem < 0)
577 0 : neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
578 0 : if (!uns && hden < 0)
579 0 : neg_double (lden, hden, &labs_den, &habs_den);
580 :
581 : /* If abs(rem) >= abs(den) - abs(rem), adjust the quotient. */
582 2 : neg_double (labs_rem, habs_rem, &lnegabs_rem, &hnegabs_rem);
583 2 : add_double (labs_den, habs_den, lnegabs_rem, hnegabs_rem,
584 : &ldiff, &hdiff);
585 :
586 2 : if (((unsigned HOST_WIDE_INT) habs_rem
587 : > (unsigned HOST_WIDE_INT) hdiff)
588 1 : || (habs_rem == hdiff && labs_rem >= ldiff))
589 : {
590 1 : if (quo_neg)
591 : /* quo = quo - 1; */
592 0 : add_double (*lquo, *hquo,
593 : HOST_WIDE_INT_M1, HOST_WIDE_INT_M1, lquo, hquo);
594 : else
595 : /* quo = quo + 1; */
596 1 : add_double (*lquo, *hquo, HOST_WIDE_INT_1, HOST_WIDE_INT_0,
597 : lquo, hquo);
598 : }
599 : else
600 2 : return overflow;
601 : }
602 : break;
603 :
604 0 : default:
605 0 : gcc_unreachable ();
606 : }
607 :
608 : /* Compute true remainder: rem = num - (quo * den) */
609 1 : mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
610 1 : neg_double (*lrem, *hrem, lrem, hrem);
611 1 : add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
612 1 : return overflow;
613 : }
614 :
615 :
616 : /* Construct from a buffer of length LEN. BUFFER will be read according
617 : to byte endianness and word endianness. Only the lower LEN bytes
618 : of the result are set; the remaining high bytes are cleared. */
619 :
620 : double_int
621 192 : double_int::from_buffer (const unsigned char *buffer, int len)
622 : {
623 192 : double_int result = double_int_zero;
624 192 : int words = len / UNITS_PER_WORD;
625 :
626 192 : gcc_assert (len * BITS_PER_UNIT <= HOST_BITS_PER_DOUBLE_INT);
627 :
628 504 : for (int byte = 0; byte < len; byte++)
629 : {
630 312 : int offset;
631 312 : int bitpos = byte * BITS_PER_UNIT;
632 312 : unsigned HOST_WIDE_INT value;
633 :
634 312 : if (len > UNITS_PER_WORD)
635 : {
636 : int word = byte / UNITS_PER_WORD;
637 :
638 : if (WORDS_BIG_ENDIAN)
639 : word = (words - 1) - word;
640 :
641 : offset = word * UNITS_PER_WORD;
642 :
643 : if (BYTES_BIG_ENDIAN)
644 : offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
645 : else
646 : offset += byte % UNITS_PER_WORD;
647 : }
648 : else
649 : offset = BYTES_BIG_ENDIAN ? (len - 1) - byte : byte;
650 :
651 312 : value = (unsigned HOST_WIDE_INT) buffer[offset];
652 :
653 312 : if (bitpos < HOST_BITS_PER_WIDE_INT)
654 312 : result.low |= value << bitpos;
655 : else
656 0 : result.high |= value << (bitpos - HOST_BITS_PER_WIDE_INT);
657 : }
658 :
659 192 : return result;
660 : }
661 :
662 :
663 : /* Returns mask for PREC bits. */
664 :
665 : double_int
666 7287624 : double_int::mask (unsigned prec)
667 : {
668 7287624 : unsigned HOST_WIDE_INT m;
669 7287624 : double_int mask;
670 :
671 7287624 : if (prec > HOST_BITS_PER_WIDE_INT)
672 : {
673 0 : prec -= HOST_BITS_PER_WIDE_INT;
674 0 : m = (HOST_WIDE_INT_UC (2) << (prec - 1)) - 1;
675 0 : mask.high = (HOST_WIDE_INT) m;
676 0 : mask.low = ALL_ONES;
677 : }
678 : else
679 : {
680 7287624 : mask.high = 0;
681 7287624 : mask.low = prec ? (HOST_WIDE_INT_UC (2) << (prec - 1)) - 1 : 0;
682 : }
683 :
684 7287624 : return mask;
685 : }
686 :
687 : /* Returns a maximum value for signed or unsigned integer
688 : of precision PREC. */
689 :
690 : double_int
691 0 : double_int::max_value (unsigned int prec, bool uns)
692 : {
693 0 : return double_int::mask (prec - (uns ? 0 : 1));
694 : }
695 :
696 : /* Returns a minimum value for signed or unsigned integer
697 : of precision PREC. */
698 :
699 : double_int
700 0 : double_int::min_value (unsigned int prec, bool uns)
701 : {
702 0 : if (uns)
703 0 : return double_int_zero;
704 0 : return double_int_one.lshift (prec - 1, prec, false);
705 : }
706 :
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.
710 :
711 : This corresponds to returning the value represented by PREC lowermost bits
712 : of CST, with the given signedness. */
713 :
714 : double_int
715 7287609 : double_int::ext (unsigned prec, bool uns) const
716 : {
717 7287609 : if (uns)
718 3641456 : return this->zext (prec);
719 : else
720 3646153 : return this->sext (prec);
721 : }
722 :
723 : /* The same as double_int::ext with UNS = true. */
724 :
725 : double_int
726 3641471 : double_int::zext (unsigned prec) const
727 : {
728 3641471 : const double_int &cst = *this;
729 3641471 : double_int mask = double_int::mask (prec);
730 3641471 : double_int r;
731 :
732 3641471 : r.low = cst.low & mask.low;
733 3641471 : r.high = cst.high & mask.high;
734 :
735 3641471 : return r;
736 : }
737 :
738 : /* The same as double_int::ext with UNS = false. */
739 :
740 : double_int
741 3646153 : double_int::sext (unsigned prec) const
742 : {
743 3646153 : const double_int &cst = *this;
744 3646153 : double_int mask = double_int::mask (prec);
745 3646153 : double_int r;
746 3646153 : unsigned HOST_WIDE_INT snum;
747 :
748 3646153 : if (prec <= HOST_BITS_PER_WIDE_INT)
749 3646153 : snum = cst.low;
750 : else
751 : {
752 0 : prec -= HOST_BITS_PER_WIDE_INT;
753 0 : snum = (unsigned HOST_WIDE_INT) cst.high;
754 : }
755 3646153 : if (((snum >> (prec - 1)) & 1) == 1)
756 : {
757 1530 : r.low = cst.low | ~mask.low;
758 1530 : r.high = cst.high | ~mask.high;
759 : }
760 : else
761 : {
762 3644623 : r.low = cst.low & mask.low;
763 3644623 : r.high = cst.high & mask.high;
764 : }
765 :
766 3646153 : return r;
767 : }
768 :
769 : /* Returns true if CST fits in signed HOST_WIDE_INT. */
770 :
771 : bool
772 0 : double_int::fits_shwi () const
773 : {
774 0 : const double_int &cst = *this;
775 0 : if (cst.high == 0)
776 0 : return (HOST_WIDE_INT) cst.low >= 0;
777 0 : else if (cst.high == -1)
778 0 : return (HOST_WIDE_INT) cst.low < 0;
779 : else
780 : return false;
781 : }
782 :
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. */
785 :
786 : bool
787 0 : double_int::fits_hwi (bool uns) const
788 : {
789 0 : if (uns)
790 0 : return this->fits_uhwi ();
791 : else
792 0 : return this->fits_shwi ();
793 : }
794 :
795 : /* Returns A * B. */
796 :
797 : double_int
798 0 : double_int::operator * (double_int b) const
799 : {
800 0 : const double_int &a = *this;
801 0 : double_int ret;
802 0 : mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
803 0 : return ret;
804 : }
805 :
806 : /* Multiplies *this with B and returns a reference to *this. */
807 :
808 : double_int &
809 0 : double_int::operator *= (double_int b)
810 : {
811 0 : mul_double (low, high, b.low, b.high, &low, &high);
812 0 : return *this;
813 : }
814 :
815 : /* Returns A * B. If the operation overflows according to UNSIGNED_P,
816 : *OVERFLOW is set to nonzero. */
817 :
818 : double_int
819 0 : double_int::mul_with_sign (double_int b, bool unsigned_p, bool *overflow) const
820 : {
821 0 : const double_int &a = *this;
822 0 : double_int ret, tem;
823 0 : *overflow = mul_double_wide_with_sign (a.low, a.high, b.low, b.high,
824 : &ret.low, &ret.high,
825 : &tem.low, &tem.high, unsigned_p);
826 0 : return ret;
827 : }
828 :
829 : double_int
830 0 : double_int::wide_mul_with_sign (double_int b, bool unsigned_p,
831 : double_int *higher, bool *overflow) const
832 :
833 : {
834 0 : double_int lower;
835 0 : *overflow = mul_double_wide_with_sign (low, high, b.low, b.high,
836 : &lower.low, &lower.high,
837 : &higher->low, &higher->high,
838 : unsigned_p);
839 0 : return lower;
840 : }
841 :
842 : /* Returns A + B. */
843 :
844 : double_int
845 0 : double_int::operator + (double_int b) const
846 : {
847 0 : const double_int &a = *this;
848 0 : double_int ret;
849 0 : add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
850 0 : return ret;
851 : }
852 :
853 : /* Adds B to *this and returns a reference to *this. */
854 :
855 : double_int &
856 0 : double_int::operator += (double_int b)
857 : {
858 0 : add_double (low, high, b.low, b.high, &low, &high);
859 0 : return *this;
860 : }
861 :
862 :
863 : /* Returns A + B. If the operation overflows according to UNSIGNED_P,
864 : *OVERFLOW is set to nonzero. */
865 :
866 : double_int
867 0 : double_int::add_with_sign (double_int b, bool unsigned_p, bool *overflow) const
868 : {
869 0 : const double_int &a = *this;
870 0 : double_int ret;
871 0 : *overflow = add_double_with_sign (a.low, a.high, b.low, b.high,
872 : &ret.low, &ret.high, unsigned_p);
873 0 : return ret;
874 : }
875 :
876 : /* Returns A - B. */
877 :
878 : double_int
879 0 : double_int::operator - (double_int b) const
880 : {
881 0 : const double_int &a = *this;
882 0 : double_int ret;
883 0 : neg_double (b.low, b.high, &b.low, &b.high);
884 0 : add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
885 0 : return ret;
886 : }
887 :
888 : /* Subtracts B from *this and returns a reference to *this. */
889 :
890 : double_int &
891 0 : double_int::operator -= (double_int b)
892 : {
893 0 : neg_double (b.low, b.high, &b.low, &b.high);
894 0 : add_double (low, high, b.low, b.high, &low, &high);
895 0 : return *this;
896 : }
897 :
898 :
899 : /* Returns A - B. If the operation overflows via inconsistent sign bits,
900 : *OVERFLOW is set to nonzero. */
901 :
902 : double_int
903 0 : double_int::sub_with_overflow (double_int b, bool *overflow) const
904 : {
905 0 : double_int ret;
906 0 : neg_double (b.low, b.high, &ret.low, &ret.high);
907 0 : add_double (low, high, ret.low, ret.high, &ret.low, &ret.high);
908 0 : *overflow = OVERFLOW_SUM_SIGN (ret.high, b.high, high);
909 0 : return ret;
910 : }
911 :
912 : /* Returns -A. */
913 :
914 : double_int
915 64452 : double_int::operator - () const
916 : {
917 64452 : const double_int &a = *this;
918 64452 : double_int ret;
919 64452 : neg_double (a.low, a.high, &ret.low, &ret.high);
920 64452 : return ret;
921 : }
922 :
923 : double_int
924 0 : double_int::neg_with_overflow (bool *overflow) const
925 : {
926 0 : double_int ret;
927 0 : *overflow = neg_double (low, high, &ret.low, &ret.high);
928 0 : return ret;
929 : }
930 :
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
934 : stored to MOD. */
935 :
936 : double_int
937 0 : double_int::divmod_with_overflow (double_int b, bool uns, unsigned code,
938 : double_int *mod, bool *overflow) const
939 : {
940 0 : const double_int &a = *this;
941 0 : double_int ret;
942 :
943 0 : *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);
946 0 : return ret;
947 : }
948 :
949 : double_int
950 2 : double_int::divmod (double_int b, bool uns, unsigned code,
951 : double_int *mod) const
952 : {
953 2 : const double_int &a = *this;
954 2 : double_int ret;
955 :
956 2 : div_and_round_double (code, uns, a.low, a.high,
957 : b.low, b.high, &ret.low, &ret.high,
958 : &mod->low, &mod->high);
959 2 : return ret;
960 : }
961 :
962 : /* The same as double_int::divmod with UNS = false. */
963 :
964 : double_int
965 0 : double_int::sdivmod (double_int b, unsigned code, double_int *mod) const
966 : {
967 0 : return this->divmod (b, false, code, mod);
968 : }
969 :
970 : /* The same as double_int::divmod with UNS = true. */
971 :
972 : double_int
973 2 : double_int::udivmod (double_int b, unsigned code, double_int *mod) const
974 : {
975 2 : return this->divmod (b, true, code, mod);
976 : }
977 :
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. */
981 :
982 : double_int
983 0 : double_int::div (double_int b, bool uns, unsigned code) const
984 : {
985 0 : double_int mod;
986 :
987 0 : return this->divmod (b, uns, code, &mod);
988 : }
989 :
990 : /* The same as double_int::div with UNS = false. */
991 :
992 : double_int
993 0 : double_int::sdiv (double_int b, unsigned code) const
994 : {
995 0 : return this->div (b, false, code);
996 : }
997 :
998 : /* The same as double_int::div with UNS = true. */
999 :
1000 : double_int
1001 0 : double_int::udiv (double_int b, unsigned code) const
1002 : {
1003 0 : return this->div (b, true, code);
1004 : }
1005 :
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. */
1009 :
1010 : double_int
1011 0 : double_int::mod (double_int b, bool uns, unsigned code) const
1012 : {
1013 0 : double_int mod;
1014 :
1015 0 : this->divmod (b, uns, code, &mod);
1016 0 : return mod;
1017 : }
1018 :
1019 : /* The same as double_int::mod with UNS = false. */
1020 :
1021 : double_int
1022 0 : double_int::smod (double_int b, unsigned code) const
1023 : {
1024 0 : return this->mod (b, false, code);
1025 : }
1026 :
1027 : /* The same as double_int::mod with UNS = true. */
1028 :
1029 : double_int
1030 0 : double_int::umod (double_int b, unsigned code) const
1031 : {
1032 0 : return this->mod (b, true, code);
1033 : }
1034 :
1035 : /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
1036 : the multiple in *MULTIPLE. Otherwise return FALSE and leave *MULTIPLE
1037 : unchanged. */
1038 :
1039 : bool
1040 0 : double_int::multiple_of (double_int factor,
1041 : bool unsigned_p, double_int *multiple) const
1042 : {
1043 0 : double_int remainder;
1044 0 : double_int quotient = this->divmod (factor, unsigned_p,
1045 : TRUNC_DIV_EXPR, &remainder);
1046 0 : if (remainder.is_zero ())
1047 : {
1048 0 : *multiple = quotient;
1049 0 : return true;
1050 : }
1051 :
1052 : return false;
1053 : }
1054 :
1055 : /* Set BITPOS bit in A. */
1056 : double_int
1057 0 : double_int::set_bit (unsigned bitpos) const
1058 : {
1059 0 : double_int a = *this;
1060 0 : if (bitpos < HOST_BITS_PER_WIDE_INT)
1061 0 : a.low |= HOST_WIDE_INT_1U << bitpos;
1062 : else
1063 0 : a.high |= HOST_WIDE_INT_1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1064 :
1065 0 : return a;
1066 : }
1067 :
1068 : /* Count trailing zeros in A. */
1069 : int
1070 0 : double_int::trailing_zeros () const
1071 : {
1072 0 : const double_int &a = *this;
1073 0 : unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
1074 0 : unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
1075 0 : if (!w)
1076 : return HOST_BITS_PER_DOUBLE_INT;
1077 0 : bits += ctz_hwi (w);
1078 0 : return bits;
1079 : }
1080 :
1081 : /* Shift A left by COUNT places. */
1082 :
1083 : double_int
1084 0 : double_int::lshift (HOST_WIDE_INT count) const
1085 : {
1086 0 : double_int ret;
1087 :
1088 0 : gcc_checking_assert (count >= 0);
1089 :
1090 0 : if (count >= HOST_BITS_PER_DOUBLE_INT)
1091 : {
1092 : /* Shifting by the host word size is undefined according to the
1093 : ANSI standard, so we must handle this as a special case. */
1094 : ret.high = 0;
1095 : ret.low = 0;
1096 : }
1097 0 : else if (count >= HOST_BITS_PER_WIDE_INT)
1098 : {
1099 0 : ret.high = low << (count - HOST_BITS_PER_WIDE_INT);
1100 0 : ret.low = 0;
1101 : }
1102 : else
1103 : {
1104 0 : ret.high = (((unsigned HOST_WIDE_INT) high << count)
1105 0 : | (low >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
1106 0 : ret.low = low << count;
1107 : }
1108 :
1109 0 : return ret;
1110 : }
1111 :
1112 : /* Shift A right by COUNT places. */
1113 :
1114 : double_int
1115 0 : double_int::rshift (HOST_WIDE_INT count) const
1116 : {
1117 0 : double_int ret;
1118 :
1119 0 : gcc_checking_assert (count >= 0);
1120 :
1121 0 : if (count >= HOST_BITS_PER_DOUBLE_INT)
1122 : {
1123 : /* Shifting by the host word size is undefined according to the
1124 : ANSI standard, so we must handle this as a special case. */
1125 : ret.high = 0;
1126 : ret.low = 0;
1127 : }
1128 0 : else if (count >= HOST_BITS_PER_WIDE_INT)
1129 : {
1130 0 : ret.high = 0;
1131 0 : ret.low
1132 0 : = (unsigned HOST_WIDE_INT) (high >> (count - HOST_BITS_PER_WIDE_INT));
1133 : }
1134 : else
1135 : {
1136 0 : ret.high = high >> count;
1137 0 : ret.low = ((low >> count)
1138 0 : | ((unsigned HOST_WIDE_INT) high
1139 0 : << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
1140 : }
1141 :
1142 0 : return ret;
1143 : }
1144 :
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. */
1148 :
1149 : double_int
1150 2229128 : double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1151 : {
1152 2229128 : double_int ret;
1153 2229128 : if (count > 0)
1154 2229128 : lshift_double (low, high, count, prec, &ret.low, &ret.high);
1155 : else
1156 0 : rshift_double (low, high, absu_hwi (count), prec, &ret.low, &ret.high, arith);
1157 2229128 : return ret;
1158 : }
1159 :
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. */
1163 :
1164 : double_int
1165 0 : double_int::rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1166 : {
1167 0 : double_int ret;
1168 0 : if (count > 0)
1169 0 : rshift_double (low, high, count, prec, &ret.low, &ret.high, arith);
1170 : else
1171 0 : lshift_double (low, high, absu_hwi (count), prec, &ret.low, &ret.high);
1172 0 : return ret;
1173 : }
1174 :
1175 : /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
1176 : Shift right if COUNT is negative. */
1177 :
1178 : double_int
1179 0 : double_int::alshift (HOST_WIDE_INT count, unsigned int prec) const
1180 : {
1181 0 : double_int r;
1182 0 : if (count > 0)
1183 0 : lshift_double (low, high, count, prec, &r.low, &r.high);
1184 : else
1185 0 : rshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high, true);
1186 0 : return r;
1187 : }
1188 :
1189 : /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
1190 : Shift left if COUNT is negative. */
1191 :
1192 : double_int
1193 0 : double_int::arshift (HOST_WIDE_INT count, unsigned int prec) const
1194 : {
1195 0 : double_int r;
1196 0 : if (count > 0)
1197 0 : rshift_double (low, high, count, prec, &r.low, &r.high, true);
1198 : else
1199 0 : lshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high);
1200 0 : return r;
1201 : }
1202 :
1203 : /* Logical shift A left by COUNT places keeping only PREC bits of result.
1204 : Shift right if COUNT is negative. */
1205 :
1206 : double_int
1207 0 : double_int::llshift (HOST_WIDE_INT count, unsigned int prec) const
1208 : {
1209 0 : double_int r;
1210 0 : if (count > 0)
1211 0 : lshift_double (low, high, count, prec, &r.low, &r.high);
1212 : else
1213 0 : rshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high, false);
1214 0 : return r;
1215 : }
1216 :
1217 : /* Logical shift A right by COUNT places keeping only PREC bits of result.
1218 : Shift left if COUNT is negative. */
1219 :
1220 : double_int
1221 0 : double_int::lrshift (HOST_WIDE_INT count, unsigned int prec) const
1222 : {
1223 0 : double_int r;
1224 0 : if (count > 0)
1225 0 : rshift_double (low, high, count, prec, &r.low, &r.high, false);
1226 : else
1227 0 : lshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high);
1228 0 : return r;
1229 : }
1230 :
1231 : /* Rotate A left by COUNT places keeping only PREC bits of result.
1232 : Rotate right if COUNT is negative. */
1233 :
1234 : double_int
1235 0 : double_int::lrotate (HOST_WIDE_INT count, unsigned int prec) const
1236 : {
1237 0 : double_int t1, t2;
1238 :
1239 0 : count %= prec;
1240 0 : if (count < 0)
1241 0 : count += prec;
1242 :
1243 0 : t1 = this->llshift (count, prec);
1244 0 : t2 = this->lrshift (prec - count, prec);
1245 :
1246 0 : return t1 | t2;
1247 : }
1248 :
1249 : /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1250 : Rotate right if COUNT is negative. */
1251 :
1252 : double_int
1253 0 : double_int::rrotate (HOST_WIDE_INT count, unsigned int prec) const
1254 : {
1255 0 : double_int t1, t2;
1256 :
1257 0 : count %= prec;
1258 0 : if (count < 0)
1259 0 : count += prec;
1260 :
1261 0 : t1 = this->lrshift (count, prec);
1262 0 : t2 = this->llshift (prec - count, prec);
1263 :
1264 0 : return t1 | t2;
1265 : }
1266 :
1267 : /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
1268 : comparison is given by UNS. */
1269 :
1270 : int
1271 0 : double_int::cmp (double_int b, bool uns) const
1272 : {
1273 0 : if (uns)
1274 0 : return this->ucmp (b);
1275 : else
1276 0 : return this->scmp (b);
1277 : }
1278 :
1279 : /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
1280 : and 1 if A > B. */
1281 :
1282 : int
1283 0 : double_int::ucmp (double_int b) const
1284 : {
1285 0 : const double_int &a = *this;
1286 0 : if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
1287 : return -1;
1288 0 : if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
1289 : return 1;
1290 0 : if (a.low < b.low)
1291 : return -1;
1292 0 : if (a.low > b.low)
1293 0 : return 1;
1294 :
1295 : return 0;
1296 : }
1297 :
1298 : /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
1299 : and 1 if A > B. */
1300 :
1301 : int
1302 0 : double_int::scmp (double_int b) const
1303 : {
1304 0 : const double_int &a = *this;
1305 0 : if (a.high < b.high)
1306 : return -1;
1307 0 : if (a.high > b.high)
1308 : return 1;
1309 0 : if (a.low < b.low)
1310 : return -1;
1311 0 : if (a.low > b.low)
1312 0 : return 1;
1313 :
1314 : return 0;
1315 : }
1316 :
1317 : /* Compares two unsigned values A and B for less-than. */
1318 :
1319 : bool
1320 0 : double_int::ult (double_int b) const
1321 : {
1322 0 : if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1323 : return true;
1324 0 : if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1325 : return false;
1326 0 : if (low < b.low)
1327 0 : return true;
1328 : return false;
1329 : }
1330 :
1331 : /* Compares two unsigned values A and B for less-than or equal-to. */
1332 :
1333 : bool
1334 0 : double_int::ule (double_int b) const
1335 : {
1336 0 : if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1337 : return true;
1338 0 : if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1339 : return false;
1340 0 : if (low <= b.low)
1341 0 : return true;
1342 : return false;
1343 : }
1344 :
1345 : /* Compares two unsigned values A and B for greater-than. */
1346 :
1347 : bool
1348 0 : double_int::ugt (double_int b) const
1349 : {
1350 0 : if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1351 : return true;
1352 0 : if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1353 : return false;
1354 0 : if (low > b.low)
1355 0 : return true;
1356 : return false;
1357 : }
1358 :
1359 : /* Compares two signed values A and B for less-than. */
1360 :
1361 : bool
1362 0 : double_int::slt (double_int b) const
1363 : {
1364 0 : if (high < b.high)
1365 : return true;
1366 0 : if (high > b.high)
1367 : return false;
1368 0 : if (low < b.low)
1369 0 : return true;
1370 : return false;
1371 : }
1372 :
1373 : /* Compares two signed values A and B for less-than or equal-to. */
1374 :
1375 : bool
1376 0 : double_int::sle (double_int b) const
1377 : {
1378 0 : if (high < b.high)
1379 : return true;
1380 0 : if (high > b.high)
1381 : return false;
1382 0 : if (low <= b.low)
1383 0 : return true;
1384 : return false;
1385 : }
1386 :
1387 : /* Compares two signed values A and B for greater-than. */
1388 :
1389 : bool
1390 0 : double_int::sgt (double_int b) const
1391 : {
1392 0 : if (high > b.high)
1393 : return true;
1394 0 : if (high < b.high)
1395 : return false;
1396 0 : if (low > b.low)
1397 0 : return true;
1398 : return false;
1399 : }
1400 :
1401 :
1402 : /* Compares two values A and B. Returns max value. Signedness of the
1403 : comparison is given by UNS. */
1404 :
1405 : double_int
1406 0 : double_int::max (double_int b, bool uns)
1407 : {
1408 0 : return (this->cmp (b, uns) == 1) ? *this : b;
1409 : }
1410 :
1411 : /* Compares two signed values A and B. Returns max value. */
1412 :
1413 : double_int
1414 0 : double_int::smax (double_int b)
1415 : {
1416 0 : return (this->scmp (b) == 1) ? *this : b;
1417 : }
1418 :
1419 : /* Compares two unsigned values A and B. Returns max value. */
1420 :
1421 : double_int
1422 0 : double_int::umax (double_int b)
1423 : {
1424 0 : return (this->ucmp (b) == 1) ? *this : b;
1425 : }
1426 :
1427 : /* Compares two values A and B. Returns mix value. Signedness of the
1428 : comparison is given by UNS. */
1429 :
1430 : double_int
1431 0 : double_int::min (double_int b, bool uns)
1432 : {
1433 0 : return (this->cmp (b, uns) == -1) ? *this : b;
1434 : }
1435 :
1436 : /* Compares two signed values A and B. Returns min value. */
1437 :
1438 : double_int
1439 0 : double_int::smin (double_int b)
1440 : {
1441 0 : return (this->scmp (b) == -1) ? *this : b;
1442 : }
1443 :
1444 : /* Compares two unsigned values A and B. Returns min value. */
1445 :
1446 : double_int
1447 0 : double_int::umin (double_int b)
1448 : {
1449 0 : return (this->ucmp (b) == -1) ? *this : b;
1450 : }
1451 :
1452 : /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1453 :
1454 : static unsigned
1455 0 : double_int_split_digit (double_int *cst, unsigned base)
1456 : {
1457 0 : unsigned HOST_WIDE_INT resl, reml;
1458 0 : HOST_WIDE_INT resh, remh;
1459 :
1460 0 : div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1461 : &resl, &resh, &reml, &remh);
1462 0 : cst->high = resh;
1463 0 : cst->low = resl;
1464 :
1465 0 : return reml;
1466 : }
1467 :
1468 : /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1469 : otherwise it is signed. */
1470 :
1471 : void
1472 0 : dump_double_int (FILE *file, double_int cst, bool uns)
1473 : {
1474 0 : unsigned digits[100], n;
1475 0 : int i;
1476 :
1477 0 : if (cst.is_zero ())
1478 : {
1479 0 : fprintf (file, "0");
1480 0 : return;
1481 : }
1482 :
1483 0 : if (!uns && cst.is_negative ())
1484 : {
1485 0 : fprintf (file, "-");
1486 0 : cst = -cst;
1487 : }
1488 :
1489 0 : for (n = 0; !cst.is_zero (); n++)
1490 0 : digits[n] = double_int_split_digit (&cst, 10);
1491 0 : for (i = n - 1; i >= 0; i--)
1492 0 : fprintf (file, "%u", digits[i]);
1493 : }
1494 :
1495 :
1496 : /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1497 : otherwise. */
1498 :
1499 : void
1500 0 : mpz_set_double_int (mpz_t result, double_int val, bool uns)
1501 : {
1502 0 : bool negate = false;
1503 0 : unsigned HOST_WIDE_INT vp[2];
1504 :
1505 0 : if (!uns && val.is_negative ())
1506 : {
1507 0 : negate = true;
1508 0 : val = -val;
1509 : }
1510 :
1511 0 : vp[0] = val.low;
1512 0 : vp[1] = (unsigned HOST_WIDE_INT) val.high;
1513 0 : mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1514 :
1515 0 : if (negate)
1516 0 : mpz_neg (result, result);
1517 0 : }
1518 :
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. */
1522 :
1523 : double_int
1524 7287570 : mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1525 : {
1526 7287570 : unsigned HOST_WIDE_INT *vp;
1527 7287570 : size_t count, numb;
1528 7287570 : double_int res;
1529 :
1530 7287570 : if (!wrap)
1531 : {
1532 0 : mpz_t min, max;
1533 :
1534 0 : mpz_init (min);
1535 0 : mpz_init (max);
1536 0 : get_type_static_bounds (type, min, max);
1537 :
1538 0 : if (mpz_cmp (val, min) < 0)
1539 0 : mpz_set (val, min);
1540 0 : else if (mpz_cmp (val, max) > 0)
1541 0 : mpz_set (val, max);
1542 :
1543 0 : mpz_clear (min);
1544 0 : mpz_clear (max);
1545 : }
1546 :
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 7287570 : numb = 8 * sizeof (HOST_WIDE_INT);
1552 7287570 : count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1553 7287570 : if (count < 2)
1554 7287570 : count = 2;
1555 7287570 : vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof (HOST_WIDE_INT));
1556 :
1557 7287570 : vp[0] = 0;
1558 7287570 : vp[1] = 0;
1559 7287570 : mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1560 :
1561 7287570 : gcc_assert (wrap || count <= 2);
1562 :
1563 7287570 : res.low = vp[0];
1564 7287570 : res.high = (HOST_WIDE_INT) vp[1];
1565 :
1566 7287570 : res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1567 7287570 : if (mpz_sgn (val) < 0)
1568 64452 : res = -res;
1569 :
1570 7287570 : return res;
1571 : }
|
