1 /* Operations with long integers.
2 Copyright (C) 2006, 2007, 2009, 2010 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 SHIFT_COUNT_TRUNCATED. */
24 #include "tree.h"
25
26 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
27 overflow. Suppose A, B and SUM have the same respective signs as A1, B1,
28 and SUM1. Then this yields nonzero if overflow occurred during the
29 addition.
30
31 Overflow occurs if A and B have the same sign, but A and SUM differ in
32 sign. Use `^' to test whether signs differ, and `< 0' to isolate the
33 sign. */
34 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
35
36 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
37 We do that by representing the two-word integer in 4 words, with only
38 HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
39 number. The value of the word is LOWPART + HIGHPART * BASE. */
40
41 #define LOWPART(x) \
42 ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
43 #define HIGHPART(x) \
44 ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
45 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
46
47 /* Unpack a two-word integer into 4 words.
48 LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
49 WORDS points to the array of HOST_WIDE_INTs. */
50
51 static void
encode(HOST_WIDE_INT * words,unsigned HOST_WIDE_INT low,HOST_WIDE_INT hi)52 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
53 {
54 words[0] = LOWPART (low);
55 words[1] = HIGHPART (low);
56 words[2] = LOWPART (hi);
57 words[3] = HIGHPART (hi);
58 }
59
60 /* Pack an array of 4 words into a two-word integer.
61 WORDS points to the array of words.
62 The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */
63
64 static void
decode(HOST_WIDE_INT * words,unsigned HOST_WIDE_INT * low,HOST_WIDE_INT * hi)65 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
66 HOST_WIDE_INT *hi)
67 {
68 *low = words[0] + words[1] * BASE;
69 *hi = words[2] + words[3] * BASE;
70 }
71
72 /* Add two doubleword integers with doubleword result.
73 Return nonzero if the operation overflows according to UNSIGNED_P.
74 Each argument is given as two `HOST_WIDE_INT' pieces.
75 One argument is L1 and H1; the other, L2 and H2.
76 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
77
78 int
add_double_with_sign(unsigned HOST_WIDE_INT l1,HOST_WIDE_INT h1,unsigned HOST_WIDE_INT l2,HOST_WIDE_INT h2,unsigned HOST_WIDE_INT * lv,HOST_WIDE_INT * hv,bool unsigned_p)79 add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
80 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
81 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
82 bool unsigned_p)
83 {
84 unsigned HOST_WIDE_INT l;
85 HOST_WIDE_INT h;
86
87 l = l1 + l2;
88 h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
89 + (unsigned HOST_WIDE_INT) h2
90 + (l < l1));
91
92 *lv = l;
93 *hv = h;
94
95 if (unsigned_p)
96 return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
97 || (h == h1
98 && l < l1));
99 else
100 return OVERFLOW_SUM_SIGN (h1, h2, h);
101 }
102
103 /* Negate a doubleword integer with doubleword result.
104 Return nonzero if the operation overflows, assuming it's signed.
105 The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
106 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
107
108 int
neg_double(unsigned HOST_WIDE_INT l1,HOST_WIDE_INT h1,unsigned HOST_WIDE_INT * lv,HOST_WIDE_INT * hv)109 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
110 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
111 {
112 if (l1 == 0)
113 {
114 *lv = 0;
115 *hv = - h1;
116 return (*hv & h1) < 0;
117 }
118 else
119 {
120 *lv = -l1;
121 *hv = ~h1;
122 return 0;
123 }
124 }
125
126 /* Multiply two doubleword integers with doubleword result.
127 Return nonzero if the operation overflows according to UNSIGNED_P.
128 Each argument is given as two `HOST_WIDE_INT' pieces.
129 One argument is L1 and H1; the other, L2 and H2.
130 The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */
131
132 int
mul_double_with_sign(unsigned HOST_WIDE_INT l1,HOST_WIDE_INT h1,unsigned HOST_WIDE_INT l2,HOST_WIDE_INT h2,unsigned HOST_WIDE_INT * lv,HOST_WIDE_INT * hv,bool unsigned_p)133 mul_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
134 unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
135 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
136 bool unsigned_p)
137 {
138 HOST_WIDE_INT arg1[4];
139 HOST_WIDE_INT arg2[4];
140 HOST_WIDE_INT prod[4 * 2];
141 unsigned HOST_WIDE_INT carry;
142 int i, j, k;
143 unsigned HOST_WIDE_INT toplow, neglow;
144 HOST_WIDE_INT tophigh, neghigh;
145
146 encode (arg1, l1, h1);
147 encode (arg2, l2, h2);
148
149 memset (prod, 0, sizeof prod);
150
151 for (i = 0; i < 4; i++)
152 {
153 carry = 0;
154 for (j = 0; j < 4; j++)
155 {
156 k = i + j;
157 /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */
158 carry += arg1[i] * arg2[j];
159 /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */
160 carry += prod[k];
161 prod[k] = LOWPART (carry);
162 carry = HIGHPART (carry);
163 }
164 prod[i + 4] = carry;
165 }
166
167 decode (prod, lv, hv);
168 decode (prod + 4, &toplow, &tophigh);
169
170 /* Unsigned overflow is immediate. */
171 if (unsigned_p)
172 return (toplow | tophigh) != 0;
173
174 /* Check for signed overflow by calculating the signed representation of the
175 top half of the result; it should agree with the low half's sign bit. */
176 if (h1 < 0)
177 {
178 neg_double (l2, h2, &neglow, &neghigh);
179 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
180 }
181 if (h2 < 0)
182 {
183 neg_double (l1, h1, &neglow, &neghigh);
184 add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
185 }
186 return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
187 }
188
189 /* Shift the doubleword integer in L1, H1 right by COUNT places
190 keeping only PREC bits of result. ARITH nonzero specifies
191 arithmetic shifting; otherwise use logical shift.
192 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
193
194 static void
rshift_double(unsigned HOST_WIDE_INT l1,HOST_WIDE_INT h1,unsigned HOST_WIDE_INT count,unsigned int prec,unsigned HOST_WIDE_INT * lv,HOST_WIDE_INT * hv,bool arith)195 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
196 unsigned HOST_WIDE_INT count, unsigned int prec,
197 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
198 bool arith)
199 {
200 unsigned HOST_WIDE_INT signmask;
201
202 signmask = (arith
203 ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
204 : 0);
205
206 if (SHIFT_COUNT_TRUNCATED)
207 count %= prec;
208
209 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
210 {
211 /* Shifting by the host word size is undefined according to the
212 ANSI standard, so we must handle this as a special case. */
213 *hv = 0;
214 *lv = 0;
215 }
216 else if (count >= HOST_BITS_PER_WIDE_INT)
217 {
218 *hv = 0;
219 *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
220 }
221 else
222 {
223 *hv = (unsigned HOST_WIDE_INT) h1 >> count;
224 *lv = ((l1 >> count)
225 | ((unsigned HOST_WIDE_INT) h1
226 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
227 }
228
229 /* Zero / sign extend all bits that are beyond the precision. */
230
231 if (count >= prec)
232 {
233 *hv = signmask;
234 *lv = signmask;
235 }
236 else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
237 ;
238 else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
239 {
240 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
241 *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
242 }
243 else
244 {
245 *hv = signmask;
246 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
247 *lv |= signmask << (prec - count);
248 }
249 }
250
251 /* Shift the doubleword integer in L1, H1 left by COUNT places
252 keeping only PREC bits of result.
253 Shift right if COUNT is negative.
254 ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
255 Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */
256
257 void
lshift_double(unsigned HOST_WIDE_INT l1,HOST_WIDE_INT h1,HOST_WIDE_INT count,unsigned int prec,unsigned HOST_WIDE_INT * lv,HOST_WIDE_INT * hv,bool arith)258 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
259 HOST_WIDE_INT count, unsigned int prec,
260 unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, bool arith)
261 {
262 unsigned HOST_WIDE_INT signmask;
263
264 if (count < 0)
265 {
266 rshift_double (l1, h1, absu_hwi (count), prec, lv, hv, arith);
267 return;
268 }
269
270 if (SHIFT_COUNT_TRUNCATED)
271 count %= prec;
272
273 if (count >= 2 * HOST_BITS_PER_WIDE_INT)
274 {
275 /* Shifting by the host word size is undefined according to the
276 ANSI standard, so we must handle this as a special case. */
277 *hv = 0;
278 *lv = 0;
279 }
280 else if (count >= HOST_BITS_PER_WIDE_INT)
281 {
282 *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
283 *lv = 0;
284 }
285 else
286 {
287 *hv = (((unsigned HOST_WIDE_INT) h1 << count)
288 | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
289 *lv = l1 << count;
290 }
291
292 /* Sign extend all bits that are beyond the precision. */
293
294 signmask = -((prec > HOST_BITS_PER_WIDE_INT
295 ? ((unsigned HOST_WIDE_INT) *hv
296 >> (prec - HOST_BITS_PER_WIDE_INT - 1))
297 : (*lv >> (prec - 1))) & 1);
298
299 if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
300 ;
301 else if (prec >= HOST_BITS_PER_WIDE_INT)
302 {
303 *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
304 *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
305 }
306 else
307 {
308 *hv = signmask;
309 *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
310 *lv |= signmask << prec;
311 }
312 }
313
314 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
315 for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
316 CODE is a tree code for a kind of division, one of
317 TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
318 or EXACT_DIV_EXPR
319 It controls how the quotient is rounded to an integer.
320 Return nonzero if the operation overflows.
321 UNS nonzero says do unsigned division. */
322
323 int
div_and_round_double(unsigned code,int uns,unsigned HOST_WIDE_INT lnum_orig,HOST_WIDE_INT hnum_orig,unsigned HOST_WIDE_INT lden_orig,HOST_WIDE_INT hden_orig,unsigned HOST_WIDE_INT * lquo,HOST_WIDE_INT * hquo,unsigned HOST_WIDE_INT * lrem,HOST_WIDE_INT * hrem)324 div_and_round_double (unsigned code, int uns,
325 /* num == numerator == dividend */
326 unsigned HOST_WIDE_INT lnum_orig,
327 HOST_WIDE_INT hnum_orig,
328 /* den == denominator == divisor */
329 unsigned HOST_WIDE_INT lden_orig,
330 HOST_WIDE_INT hden_orig,
331 unsigned HOST_WIDE_INT *lquo,
332 HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
333 HOST_WIDE_INT *hrem)
334 {
335 int quo_neg = 0;
336 HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */
337 HOST_WIDE_INT den[4], quo[4];
338 int i, j;
339 unsigned HOST_WIDE_INT work;
340 unsigned HOST_WIDE_INT carry = 0;
341 unsigned HOST_WIDE_INT lnum = lnum_orig;
342 HOST_WIDE_INT hnum = hnum_orig;
343 unsigned HOST_WIDE_INT lden = lden_orig;
344 HOST_WIDE_INT hden = hden_orig;
345 int overflow = 0;
346
347 if (hden == 0 && lden == 0)
348 overflow = 1, lden = 1;
349
350 /* Calculate quotient sign and convert operands to unsigned. */
351 if (!uns)
352 {
353 if (hnum < 0)
354 {
355 quo_neg = ~ quo_neg;
356 /* (minimum integer) / (-1) is the only overflow case. */
357 if (neg_double (lnum, hnum, &lnum, &hnum)
358 && ((HOST_WIDE_INT) lden & hden) == -1)
359 overflow = 1;
360 }
361 if (hden < 0)
362 {
363 quo_neg = ~ quo_neg;
364 neg_double (lden, hden, &lden, &hden);
365 }
366 }
367
368 if (hnum == 0 && hden == 0)
369 { /* single precision */
370 *hquo = *hrem = 0;
371 /* This unsigned division rounds toward zero. */
372 *lquo = lnum / lden;
373 goto finish_up;
374 }
375
376 if (hnum == 0)
377 { /* trivial case: dividend < divisor */
378 /* hden != 0 already checked. */
379 *hquo = *lquo = 0;
380 *hrem = hnum;
381 *lrem = lnum;
382 goto finish_up;
383 }
384
385 memset (quo, 0, sizeof quo);
386
387 memset (num, 0, sizeof num); /* to zero 9th element */
388 memset (den, 0, sizeof den);
389
390 encode (num, lnum, hnum);
391 encode (den, lden, hden);
392
393 /* Special code for when the divisor < BASE. */
394 if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
395 {
396 /* hnum != 0 already checked. */
397 for (i = 4 - 1; i >= 0; i--)
398 {
399 work = num[i] + carry * BASE;
400 quo[i] = work / lden;
401 carry = work % lden;
402 }
403 }
404 else
405 {
406 /* Full double precision division,
407 with thanks to Don Knuth's "Seminumerical Algorithms". */
408 int num_hi_sig, den_hi_sig;
409 unsigned HOST_WIDE_INT quo_est, scale;
410
411 /* Find the highest nonzero divisor digit. */
412 for (i = 4 - 1;; i--)
413 if (den[i] != 0)
414 {
415 den_hi_sig = i;
416 break;
417 }
418
419 /* Insure that the first digit of the divisor is at least BASE/2.
420 This is required by the quotient digit estimation algorithm. */
421
422 scale = BASE / (den[den_hi_sig] + 1);
423 if (scale > 1)
424 { /* scale divisor and dividend */
425 carry = 0;
426 for (i = 0; i <= 4 - 1; i++)
427 {
428 work = (num[i] * scale) + carry;
429 num[i] = LOWPART (work);
430 carry = HIGHPART (work);
431 }
432
433 num[4] = carry;
434 carry = 0;
435 for (i = 0; i <= 4 - 1; i++)
436 {
437 work = (den[i] * scale) + carry;
438 den[i] = LOWPART (work);
439 carry = HIGHPART (work);
440 if (den[i] != 0) den_hi_sig = i;
441 }
442 }
443
444 num_hi_sig = 4;
445
446 /* Main loop */
447 for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
448 {
449 /* Guess the next quotient digit, quo_est, by dividing the first
450 two remaining dividend digits by the high order quotient digit.
451 quo_est is never low and is at most 2 high. */
452 unsigned HOST_WIDE_INT tmp;
453
454 num_hi_sig = i + den_hi_sig + 1;
455 work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
456 if (num[num_hi_sig] != den[den_hi_sig])
457 quo_est = work / den[den_hi_sig];
458 else
459 quo_est = BASE - 1;
460
461 /* Refine quo_est so it's usually correct, and at most one high. */
462 tmp = work - quo_est * den[den_hi_sig];
463 if (tmp < BASE
464 && (den[den_hi_sig - 1] * quo_est
465 > (tmp * BASE + num[num_hi_sig - 2])))
466 quo_est--;
467
468 /* Try QUO_EST as the quotient digit, by multiplying the
469 divisor by QUO_EST and subtracting from the remaining dividend.
470 Keep in mind that QUO_EST is the I - 1st digit. */
471
472 carry = 0;
473 for (j = 0; j <= den_hi_sig; j++)
474 {
475 work = quo_est * den[j] + carry;
476 carry = HIGHPART (work);
477 work = num[i + j] - LOWPART (work);
478 num[i + j] = LOWPART (work);
479 carry += HIGHPART (work) != 0;
480 }
481
482 /* If quo_est was high by one, then num[i] went negative and
483 we need to correct things. */
484 if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
485 {
486 quo_est--;
487 carry = 0; /* add divisor back in */
488 for (j = 0; j <= den_hi_sig; j++)
489 {
490 work = num[i + j] + den[j] + carry;
491 carry = HIGHPART (work);
492 num[i + j] = LOWPART (work);
493 }
494
495 num [num_hi_sig] += carry;
496 }
497
498 /* Store the quotient digit. */
499 quo[i] = quo_est;
500 }
501 }
502
503 decode (quo, lquo, hquo);
504
505 finish_up:
506 /* If result is negative, make it so. */
507 if (quo_neg)
508 neg_double (*lquo, *hquo, lquo, hquo);
509
510 /* Compute trial remainder: rem = num - (quo * den) */
511 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
512 neg_double (*lrem, *hrem, lrem, hrem);
513 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
514
515 switch (code)
516 {
517 case TRUNC_DIV_EXPR:
518 case TRUNC_MOD_EXPR: /* round toward zero */
519 case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */
520 return overflow;
521
522 case FLOOR_DIV_EXPR:
523 case FLOOR_MOD_EXPR: /* round toward negative infinity */
524 if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */
525 {
526 /* quo = quo - 1; */
527 add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1,
528 lquo, hquo);
529 }
530 else
531 return overflow;
532 break;
533
534 case CEIL_DIV_EXPR:
535 case CEIL_MOD_EXPR: /* round toward positive infinity */
536 if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */
537 {
538 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
539 lquo, hquo);
540 }
541 else
542 return overflow;
543 break;
544
545 case ROUND_DIV_EXPR:
546 case ROUND_MOD_EXPR: /* round to closest integer */
547 {
548 unsigned HOST_WIDE_INT labs_rem = *lrem;
549 HOST_WIDE_INT habs_rem = *hrem;
550 unsigned HOST_WIDE_INT labs_den = lden, ltwice;
551 HOST_WIDE_INT habs_den = hden, htwice;
552
553 /* Get absolute values. */
554 if (*hrem < 0)
555 neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
556 if (hden < 0)
557 neg_double (lden, hden, &labs_den, &habs_den);
558
559 /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient. */
560 mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
561 labs_rem, habs_rem, <wice, &htwice);
562
563 if (((unsigned HOST_WIDE_INT) habs_den
564 < (unsigned HOST_WIDE_INT) htwice)
565 || (((unsigned HOST_WIDE_INT) habs_den
566 == (unsigned HOST_WIDE_INT) htwice)
567 && (labs_den <= ltwice)))
568 {
569 if (*hquo < 0)
570 /* quo = quo - 1; */
571 add_double (*lquo, *hquo,
572 (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
573 else
574 /* quo = quo + 1; */
575 add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
576 lquo, hquo);
577 }
578 else
579 return overflow;
580 }
581 break;
582
583 default:
584 gcc_unreachable ();
585 }
586
587 /* Compute true remainder: rem = num - (quo * den) */
588 mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
589 neg_double (*lrem, *hrem, lrem, hrem);
590 add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
591 return overflow;
592 }
593
594
595 /* Returns mask for PREC bits. */
596
597 double_int
double_int_mask(unsigned prec)598 double_int_mask (unsigned prec)
599 {
600 unsigned HOST_WIDE_INT m;
601 double_int mask;
602
603 if (prec > HOST_BITS_PER_WIDE_INT)
604 {
605 prec -= HOST_BITS_PER_WIDE_INT;
606 m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
607 mask.high = (HOST_WIDE_INT) m;
608 mask.low = ALL_ONES;
609 }
610 else
611 {
612 mask.high = 0;
613 mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
614 }
615
616 return mask;
617 }
618
619 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
620 outside of the precision are set to the sign bit (i.e., the PREC-th one),
621 otherwise they are set to zero.
622
623 This corresponds to returning the value represented by PREC lowermost bits
624 of CST, with the given signedness. */
625
626 double_int
double_int_ext(double_int cst,unsigned prec,bool uns)627 double_int_ext (double_int cst, unsigned prec, bool uns)
628 {
629 if (uns)
630 return double_int_zext (cst, prec);
631 else
632 return double_int_sext (cst, prec);
633 }
634
635 /* The same as double_int_ext with UNS = true. */
636
637 double_int
double_int_zext(double_int cst,unsigned prec)638 double_int_zext (double_int cst, unsigned prec)
639 {
640 double_int mask = double_int_mask (prec);
641 double_int r;
642
643 r.low = cst.low & mask.low;
644 r.high = cst.high & mask.high;
645
646 return r;
647 }
648
649 /* The same as double_int_ext with UNS = false. */
650
651 double_int
double_int_sext(double_int cst,unsigned prec)652 double_int_sext (double_int cst, unsigned prec)
653 {
654 double_int mask = double_int_mask (prec);
655 double_int r;
656 unsigned HOST_WIDE_INT snum;
657
658 if (prec <= HOST_BITS_PER_WIDE_INT)
659 snum = cst.low;
660 else
661 {
662 prec -= HOST_BITS_PER_WIDE_INT;
663 snum = (unsigned HOST_WIDE_INT) cst.high;
664 }
665 if (((snum >> (prec - 1)) & 1) == 1)
666 {
667 r.low = cst.low | ~mask.low;
668 r.high = cst.high | ~mask.high;
669 }
670 else
671 {
672 r.low = cst.low & mask.low;
673 r.high = cst.high & mask.high;
674 }
675
676 return r;
677 }
678
679 /* Returns true if CST fits in signed HOST_WIDE_INT. */
680
681 bool
double_int_fits_in_shwi_p(double_int cst)682 double_int_fits_in_shwi_p (double_int cst)
683 {
684 if (cst.high == 0)
685 return (HOST_WIDE_INT) cst.low >= 0;
686 else if (cst.high == -1)
687 return (HOST_WIDE_INT) cst.low < 0;
688 else
689 return false;
690 }
691
692 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
693 unsigned HOST_WIDE_INT if UNS is true. */
694
695 bool
double_int_fits_in_hwi_p(double_int cst,bool uns)696 double_int_fits_in_hwi_p (double_int cst, bool uns)
697 {
698 if (uns)
699 return double_int_fits_in_uhwi_p (cst);
700 else
701 return double_int_fits_in_shwi_p (cst);
702 }
703
704 /* Returns A * B. */
705
706 double_int
double_int_mul(double_int a,double_int b)707 double_int_mul (double_int a, double_int b)
708 {
709 double_int ret;
710 mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
711 return ret;
712 }
713
714 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
715 *OVERFLOW is set to nonzero. */
716
717 double_int
double_int_mul_with_sign(double_int a,double_int b,bool unsigned_p,int * overflow)718 double_int_mul_with_sign (double_int a, double_int b,
719 bool unsigned_p, int *overflow)
720 {
721 double_int ret;
722 *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
723 &ret.low, &ret.high, unsigned_p);
724 return ret;
725 }
726
727 /* Returns A + B. */
728
729 double_int
double_int_add(double_int a,double_int b)730 double_int_add (double_int a, double_int b)
731 {
732 double_int ret;
733 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
734 return ret;
735 }
736
737 /* Returns A - B. */
738
739 double_int
double_int_sub(double_int a,double_int b)740 double_int_sub (double_int a, double_int b)
741 {
742 double_int ret;
743 neg_double (b.low, b.high, &b.low, &b.high);
744 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
745 return ret;
746 }
747
748 /* Returns -A. */
749
750 double_int
double_int_neg(double_int a)751 double_int_neg (double_int a)
752 {
753 double_int ret;
754 neg_double (a.low, a.high, &ret.low, &ret.high);
755 return ret;
756 }
757
758 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
759 specified by CODE). CODE is enum tree_code in fact, but double_int.h
760 must be included before tree.h. The remainder after the division is
761 stored to MOD. */
762
763 double_int
double_int_divmod(double_int a,double_int b,bool uns,unsigned code,double_int * mod)764 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
765 double_int *mod)
766 {
767 double_int ret;
768
769 div_and_round_double (code, uns, a.low, a.high,
770 b.low, b.high, &ret.low, &ret.high,
771 &mod->low, &mod->high);
772 return ret;
773 }
774
775 /* The same as double_int_divmod with UNS = false. */
776
777 double_int
double_int_sdivmod(double_int a,double_int b,unsigned code,double_int * mod)778 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
779 {
780 return double_int_divmod (a, b, false, code, mod);
781 }
782
783 /* The same as double_int_divmod with UNS = true. */
784
785 double_int
double_int_udivmod(double_int a,double_int b,unsigned code,double_int * mod)786 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
787 {
788 return double_int_divmod (a, b, true, code, mod);
789 }
790
791 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
792 specified by CODE). CODE is enum tree_code in fact, but double_int.h
793 must be included before tree.h. */
794
795 double_int
double_int_div(double_int a,double_int b,bool uns,unsigned code)796 double_int_div (double_int a, double_int b, bool uns, unsigned code)
797 {
798 double_int mod;
799
800 return double_int_divmod (a, b, uns, code, &mod);
801 }
802
803 /* The same as double_int_div with UNS = false. */
804
805 double_int
double_int_sdiv(double_int a,double_int b,unsigned code)806 double_int_sdiv (double_int a, double_int b, unsigned code)
807 {
808 return double_int_div (a, b, false, code);
809 }
810
811 /* The same as double_int_div with UNS = true. */
812
813 double_int
double_int_udiv(double_int a,double_int b,unsigned code)814 double_int_udiv (double_int a, double_int b, unsigned code)
815 {
816 return double_int_div (a, b, true, code);
817 }
818
819 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
820 specified by CODE). CODE is enum tree_code in fact, but double_int.h
821 must be included before tree.h. */
822
823 double_int
double_int_mod(double_int a,double_int b,bool uns,unsigned code)824 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
825 {
826 double_int mod;
827
828 double_int_divmod (a, b, uns, code, &mod);
829 return mod;
830 }
831
832 /* The same as double_int_mod with UNS = false. */
833
834 double_int
double_int_smod(double_int a,double_int b,unsigned code)835 double_int_smod (double_int a, double_int b, unsigned code)
836 {
837 return double_int_mod (a, b, false, code);
838 }
839
840 /* The same as double_int_mod with UNS = true. */
841
842 double_int
double_int_umod(double_int a,double_int b,unsigned code)843 double_int_umod (double_int a, double_int b, unsigned code)
844 {
845 return double_int_mod (a, b, true, code);
846 }
847
848 /* Set BITPOS bit in A. */
849 double_int
double_int_setbit(double_int a,unsigned bitpos)850 double_int_setbit (double_int a, unsigned bitpos)
851 {
852 if (bitpos < HOST_BITS_PER_WIDE_INT)
853 a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
854 else
855 a.high |= (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
856
857 return a;
858 }
859
860 /* Count trailing zeros in A. */
861 int
double_int_ctz(double_int a)862 double_int_ctz (double_int a)
863 {
864 unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
865 unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
866 if (!w)
867 return HOST_BITS_PER_DOUBLE_INT;
868 bits += ctz_hwi (w);
869 return bits;
870 }
871
872 /* Shift A left by COUNT places keeping only PREC bits of result. Shift
873 right if COUNT is negative. ARITH true specifies arithmetic shifting;
874 otherwise use logical shift. */
875
876 double_int
double_int_lshift(double_int a,HOST_WIDE_INT count,unsigned int prec,bool arith)877 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
878 {
879 double_int ret;
880 lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
881 return ret;
882 }
883
884 /* Shift A rigth by COUNT places keeping only PREC bits of result. Shift
885 left if COUNT is negative. ARITH true specifies arithmetic shifting;
886 otherwise use logical shift. */
887
888 double_int
double_int_rshift(double_int a,HOST_WIDE_INT count,unsigned int prec,bool arith)889 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
890 {
891 double_int ret;
892 lshift_double (a.low, a.high, -count, prec, &ret.low, &ret.high, arith);
893 return ret;
894 }
895
896 /* Rotate A left by COUNT places keeping only PREC bits of result.
897 Rotate right if COUNT is negative. */
898
899 double_int
double_int_lrotate(double_int a,HOST_WIDE_INT count,unsigned int prec)900 double_int_lrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
901 {
902 double_int t1, t2;
903
904 count %= prec;
905 if (count < 0)
906 count += prec;
907
908 t1 = double_int_lshift (a, count, prec, false);
909 t2 = double_int_rshift (a, prec - count, prec, false);
910
911 return double_int_ior (t1, t2);
912 }
913
914 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
915 Rotate right if COUNT is negative. */
916
917 double_int
double_int_rrotate(double_int a,HOST_WIDE_INT count,unsigned int prec)918 double_int_rrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
919 {
920 double_int t1, t2;
921
922 count %= prec;
923 if (count < 0)
924 count += prec;
925
926 t1 = double_int_rshift (a, count, prec, false);
927 t2 = double_int_lshift (a, prec - count, prec, false);
928
929 return double_int_ior (t1, t2);
930 }
931
932 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
933 comparison is given by UNS. */
934
935 int
double_int_cmp(double_int a,double_int b,bool uns)936 double_int_cmp (double_int a, double_int b, bool uns)
937 {
938 if (uns)
939 return double_int_ucmp (a, b);
940 else
941 return double_int_scmp (a, b);
942 }
943
944 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
945 and 1 if A > B. */
946
947 int
double_int_ucmp(double_int a,double_int b)948 double_int_ucmp (double_int a, double_int b)
949 {
950 if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
951 return -1;
952 if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
953 return 1;
954 if (a.low < b.low)
955 return -1;
956 if (a.low > b.low)
957 return 1;
958
959 return 0;
960 }
961
962 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
963 and 1 if A > B. */
964
965 int
double_int_scmp(double_int a,double_int b)966 double_int_scmp (double_int a, double_int b)
967 {
968 if (a.high < b.high)
969 return -1;
970 if (a.high > b.high)
971 return 1;
972 if (a.low < b.low)
973 return -1;
974 if (a.low > b.low)
975 return 1;
976
977 return 0;
978 }
979
980 /* Compares two values A and B. Returns max value. Signedness of the
981 comparison is given by UNS. */
982
983 double_int
double_int_max(double_int a,double_int b,bool uns)984 double_int_max (double_int a, double_int b, bool uns)
985 {
986 return (double_int_cmp (a, b, uns) == 1) ? a : b;
987 }
988
989 /* Compares two signed values A and B. Returns max value. */
990
double_int_smax(double_int a,double_int b)991 double_int double_int_smax (double_int a, double_int b)
992 {
993 return (double_int_scmp (a, b) == 1) ? a : b;
994 }
995
996 /* Compares two unsigned values A and B. Returns max value. */
997
double_int_umax(double_int a,double_int b)998 double_int double_int_umax (double_int a, double_int b)
999 {
1000 return (double_int_ucmp (a, b) == 1) ? a : b;
1001 }
1002
1003 /* Compares two values A and B. Returns mix value. Signedness of the
1004 comparison is given by UNS. */
1005
double_int_min(double_int a,double_int b,bool uns)1006 double_int double_int_min (double_int a, double_int b, bool uns)
1007 {
1008 return (double_int_cmp (a, b, uns) == -1) ? a : b;
1009 }
1010
1011 /* Compares two signed values A and B. Returns min value. */
1012
double_int_smin(double_int a,double_int b)1013 double_int double_int_smin (double_int a, double_int b)
1014 {
1015 return (double_int_scmp (a, b) == -1) ? a : b;
1016 }
1017
1018 /* Compares two unsigned values A and B. Returns min value. */
1019
double_int_umin(double_int a,double_int b)1020 double_int double_int_umin (double_int a, double_int b)
1021 {
1022 return (double_int_ucmp (a, b) == -1) ? a : b;
1023 }
1024
1025 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
1026
1027 static unsigned
double_int_split_digit(double_int * cst,unsigned base)1028 double_int_split_digit (double_int *cst, unsigned base)
1029 {
1030 unsigned HOST_WIDE_INT resl, reml;
1031 HOST_WIDE_INT resh, remh;
1032
1033 div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1034 &resl, &resh, &reml, &remh);
1035 cst->high = resh;
1036 cst->low = resl;
1037
1038 return reml;
1039 }
1040
1041 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
1042 otherwise it is signed. */
1043
1044 void
dump_double_int(FILE * file,double_int cst,bool uns)1045 dump_double_int (FILE *file, double_int cst, bool uns)
1046 {
1047 unsigned digits[100], n;
1048 int i;
1049
1050 if (double_int_zero_p (cst))
1051 {
1052 fprintf (file, "0");
1053 return;
1054 }
1055
1056 if (!uns && double_int_negative_p (cst))
1057 {
1058 fprintf (file, "-");
1059 cst = double_int_neg (cst);
1060 }
1061
1062 for (n = 0; !double_int_zero_p (cst); n++)
1063 digits[n] = double_int_split_digit (&cst, 10);
1064 for (i = n - 1; i >= 0; i--)
1065 fprintf (file, "%u", digits[i]);
1066 }
1067
1068
1069 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1070 otherwise. */
1071
1072 void
mpz_set_double_int(mpz_t result,double_int val,bool uns)1073 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1074 {
1075 bool negate = false;
1076 unsigned HOST_WIDE_INT vp[2];
1077
1078 if (!uns && double_int_negative_p (val))
1079 {
1080 negate = true;
1081 val = double_int_neg (val);
1082 }
1083
1084 vp[0] = val.low;
1085 vp[1] = (unsigned HOST_WIDE_INT) val.high;
1086 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1087
1088 if (negate)
1089 mpz_neg (result, result);
1090 }
1091
1092 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
1093 values of VAL will be wrapped; otherwise, they will be set to the
1094 appropriate minimum or maximum TYPE bound. */
1095
1096 double_int
mpz_get_double_int(const_tree type,mpz_t val,bool wrap)1097 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1098 {
1099 unsigned HOST_WIDE_INT *vp;
1100 size_t count, numb;
1101 double_int res;
1102
1103 if (!wrap)
1104 {
1105 mpz_t min, max;
1106
1107 mpz_init (min);
1108 mpz_init (max);
1109 get_type_static_bounds (type, min, max);
1110
1111 if (mpz_cmp (val, min) < 0)
1112 mpz_set (val, min);
1113 else if (mpz_cmp (val, max) > 0)
1114 mpz_set (val, max);
1115
1116 mpz_clear (min);
1117 mpz_clear (max);
1118 }
1119
1120 /* Determine the number of unsigned HOST_WIDE_INT that are required
1121 for representing the value. The code to calculate count is
1122 extracted from the GMP manual, section "Integer Import and Export":
1123 http://gmplib.org/manual/Integer-Import-and-Export.html */
1124 numb = 8*sizeof(HOST_WIDE_INT);
1125 count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1126 if (count < 2)
1127 count = 2;
1128 vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1129
1130 vp[0] = 0;
1131 vp[1] = 0;
1132 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1133
1134 gcc_assert (wrap || count <= 2);
1135
1136 res.low = vp[0];
1137 res.high = (HOST_WIDE_INT) vp[1];
1138
1139 res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1140 if (mpz_sgn (val) < 0)
1141 res = double_int_neg (res);
1142
1143 return res;
1144 }
1145