Branch data Line data Source code
1 : : /* Operations with long integers.
2 : : Copyright (C) 2006-2024 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 : 2206664 : 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 : 2206664 : unsigned HOST_WIDE_INT signmask;
294 : :
295 : 2206664 : 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 : 2206664 : else if (count >= HOST_BITS_PER_WIDE_INT)
303 : : {
304 : 275833 : *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
305 : 275833 : *lv = 0;
306 : : }
307 : : else
308 : : {
309 : 1930831 : *hv = (((unsigned HOST_WIDE_INT) h1 << count)
310 : 1930831 : | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
311 : 1930831 : *lv = l1 << count;
312 : : }
313 : :
314 : : /* Sign extend all bits that are beyond the precision. */
315 : :
316 : 2206664 : signmask = -((prec > HOST_BITS_PER_WIDE_INT
317 : 2206664 : ? ((unsigned HOST_WIDE_INT) *hv
318 : 2206664 : >> (prec - HOST_BITS_PER_WIDE_INT - 1))
319 : 2206664 : : (*lv >> (prec - 1))) & 1);
320 : :
321 : 2206664 : 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 : 2206664 : }
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 : 2 : 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 : 181 : double_int::from_buffer (const unsigned char *buffer, int len)
622 : : {
623 : 181 : double_int result = double_int_zero;
624 : 181 : int words = len / UNITS_PER_WORD;
625 : :
626 : 181 : gcc_assert (len * BITS_PER_UNIT <= HOST_BITS_PER_DOUBLE_INT);
627 : :
628 : 482 : for (int byte = 0; byte < len; byte++)
629 : : {
630 : 301 : int offset;
631 : 301 : int bitpos = byte * BITS_PER_UNIT;
632 : 301 : unsigned HOST_WIDE_INT value;
633 : :
634 : 301 : 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 : 301 : value = (unsigned HOST_WIDE_INT) buffer[offset];
652 : :
653 : 301 : if (bitpos < HOST_BITS_PER_WIDE_INT)
654 : 301 : result.low |= value << bitpos;
655 : : else
656 : 0 : result.high |= value << (bitpos - HOST_BITS_PER_WIDE_INT);
657 : : }
658 : :
659 : 181 : return result;
660 : : }
661 : :
662 : :
663 : : /* Returns mask for PREC bits. */
664 : :
665 : : double_int
666 : 7283781 : double_int::mask (unsigned prec)
667 : : {
668 : 7283781 : unsigned HOST_WIDE_INT m;
669 : 7283781 : double_int mask;
670 : :
671 : 7283781 : 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 : 7283781 : mask.high = 0;
681 : 7283781 : mask.low = prec ? (HOST_WIDE_INT_UC (2) << (prec - 1)) - 1 : 0;
682 : : }
683 : :
684 : 7283781 : 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 : 7283765 : double_int::ext (unsigned prec, bool uns) const
716 : : {
717 : 7283765 : if (uns)
718 : 3638979 : return this->zext (prec);
719 : : else
720 : 3644786 : return this->sext (prec);
721 : : }
722 : :
723 : : /* The same as double_int::ext with UNS = true. */
724 : :
725 : : double_int
726 : 3638995 : double_int::zext (unsigned prec) const
727 : : {
728 : 3638995 : const double_int &cst = *this;
729 : 3638995 : double_int mask = double_int::mask (prec);
730 : 3638995 : double_int r;
731 : :
732 : 3638995 : r.low = cst.low & mask.low;
733 : 3638995 : r.high = cst.high & mask.high;
734 : :
735 : 3638995 : return r;
736 : : }
737 : :
738 : : /* The same as double_int::ext with UNS = false. */
739 : :
740 : : double_int
741 : 3644786 : double_int::sext (unsigned prec) const
742 : : {
743 : 3644786 : const double_int &cst = *this;
744 : 3644786 : double_int mask = double_int::mask (prec);
745 : 3644786 : double_int r;
746 : 3644786 : unsigned HOST_WIDE_INT snum;
747 : :
748 : 3644786 : if (prec <= HOST_BITS_PER_WIDE_INT)
749 : 3644786 : 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 : 3644786 : 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 : 3643256 : r.low = cst.low & mask.low;
763 : 3643256 : r.high = cst.high & mask.high;
764 : : }
765 : :
766 : 3644786 : 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 : 2206664 : double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1151 : : {
1152 : 2206664 : double_int ret;
1153 : 2206664 : if (count > 0)
1154 : 2206664 : 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 : 2206664 : 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 : 7283724 : mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1525 : : {
1526 : 7283724 : unsigned HOST_WIDE_INT *vp;
1527 : 7283724 : size_t count, numb;
1528 : 7283724 : double_int res;
1529 : :
1530 : 7283724 : 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 : 7283724 : numb = 8 * sizeof (HOST_WIDE_INT);
1552 : 7283724 : count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1553 : 7283724 : if (count < 2)
1554 : 7283724 : count = 2;
1555 : 7283724 : vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof (HOST_WIDE_INT));
1556 : :
1557 : 7283724 : vp[0] = 0;
1558 : 7283724 : vp[1] = 0;
1559 : 7283724 : mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1560 : :
1561 : 7283724 : gcc_assert (wrap || count <= 2);
1562 : :
1563 : 7283724 : res.low = vp[0];
1564 : 7283724 : res.high = (HOST_WIDE_INT) vp[1];
1565 : :
1566 : 7283724 : res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1567 : 7283724 : if (mpz_sgn (val) < 0)
1568 : 64452 : res = -res;
1569 : :
1570 : 7283724 : return res;
1571 : : }
|
