|
0
|
1 /* Operations with long integers.
|
|
|
2 Copyright (C) 2006, 2007 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"
|
|
|
24 #include "tree.h"
|
|
|
25
|
|
|
26 /* Returns mask for PREC bits. */
|
|
|
27
|
|
|
28 double_int
|
|
|
29 double_int_mask (unsigned prec)
|
|
|
30 {
|
|
|
31 unsigned HOST_WIDE_INT m;
|
|
|
32 double_int mask;
|
|
|
33
|
|
|
34 if (prec > HOST_BITS_PER_WIDE_INT)
|
|
|
35 {
|
|
|
36 prec -= HOST_BITS_PER_WIDE_INT;
|
|
|
37 m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
|
|
|
38 mask.high = (HOST_WIDE_INT) m;
|
|
|
39 mask.low = ALL_ONES;
|
|
|
40 }
|
|
|
41 else
|
|
|
42 {
|
|
|
43 mask.high = 0;
|
|
|
44 mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
|
|
|
45 }
|
|
|
46
|
|
|
47 return mask;
|
|
|
48 }
|
|
|
49
|
|
|
50 /* Clears the bits of CST over the precision PREC. If UNS is false, the bits
|
|
|
51 outside of the precision are set to the sign bit (i.e., the PREC-th one),
|
|
|
52 otherwise they are set to zero.
|
|
|
53
|
|
|
54 This corresponds to returning the value represented by PREC lowermost bits
|
|
|
55 of CST, with the given signedness. */
|
|
|
56
|
|
|
57 double_int
|
|
|
58 double_int_ext (double_int cst, unsigned prec, bool uns)
|
|
|
59 {
|
|
|
60 if (uns)
|
|
|
61 return double_int_zext (cst, prec);
|
|
|
62 else
|
|
|
63 return double_int_sext (cst, prec);
|
|
|
64 }
|
|
|
65
|
|
|
66 /* The same as double_int_ext with UNS = true. */
|
|
|
67
|
|
|
68 double_int
|
|
|
69 double_int_zext (double_int cst, unsigned prec)
|
|
|
70 {
|
|
|
71 double_int mask = double_int_mask (prec);
|
|
|
72 double_int r;
|
|
|
73
|
|
|
74 r.low = cst.low & mask.low;
|
|
|
75 r.high = cst.high & mask.high;
|
|
|
76
|
|
|
77 return r;
|
|
|
78 }
|
|
|
79
|
|
|
80 /* The same as double_int_ext with UNS = false. */
|
|
|
81
|
|
|
82 double_int
|
|
|
83 double_int_sext (double_int cst, unsigned prec)
|
|
|
84 {
|
|
|
85 double_int mask = double_int_mask (prec);
|
|
|
86 double_int r;
|
|
|
87 unsigned HOST_WIDE_INT snum;
|
|
|
88
|
|
|
89 if (prec <= HOST_BITS_PER_WIDE_INT)
|
|
|
90 snum = cst.low;
|
|
|
91 else
|
|
|
92 {
|
|
|
93 prec -= HOST_BITS_PER_WIDE_INT;
|
|
|
94 snum = (unsigned HOST_WIDE_INT) cst.high;
|
|
|
95 }
|
|
|
96 if (((snum >> (prec - 1)) & 1) == 1)
|
|
|
97 {
|
|
|
98 r.low = cst.low | ~mask.low;
|
|
|
99 r.high = cst.high | ~mask.high;
|
|
|
100 }
|
|
|
101 else
|
|
|
102 {
|
|
|
103 r.low = cst.low & mask.low;
|
|
|
104 r.high = cst.high & mask.high;
|
|
|
105 }
|
|
|
106
|
|
|
107 return r;
|
|
|
108 }
|
|
|
109
|
|
|
110 /* Constructs long integer from tree CST. The extra bits over the precision of
|
|
|
111 the number are filled with sign bit if CST is signed, and with zeros if it
|
|
|
112 is unsigned. */
|
|
|
113
|
|
|
114 double_int
|
|
|
115 tree_to_double_int (const_tree cst)
|
|
|
116 {
|
|
|
117 /* We do not need to call double_int_restrict here to ensure the semantics as
|
|
|
118 described, as this is the default one for trees. */
|
|
|
119 return TREE_INT_CST (cst);
|
|
|
120 }
|
|
|
121
|
|
|
122 /* Returns true if CST fits in unsigned HOST_WIDE_INT. */
|
|
|
123
|
|
|
124 bool
|
|
|
125 double_int_fits_in_uhwi_p (double_int cst)
|
|
|
126 {
|
|
|
127 return cst.high == 0;
|
|
|
128 }
|
|
|
129
|
|
|
130 /* Returns true if CST fits in signed HOST_WIDE_INT. */
|
|
|
131
|
|
|
132 bool
|
|
|
133 double_int_fits_in_shwi_p (double_int cst)
|
|
|
134 {
|
|
|
135 if (cst.high == 0)
|
|
|
136 return (HOST_WIDE_INT) cst.low >= 0;
|
|
|
137 else if (cst.high == -1)
|
|
|
138 return (HOST_WIDE_INT) cst.low < 0;
|
|
|
139 else
|
|
|
140 return false;
|
|
|
141 }
|
|
|
142
|
|
|
143 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
|
|
|
144 unsigned HOST_WIDE_INT if UNS is true. */
|
|
|
145
|
|
|
146 bool
|
|
|
147 double_int_fits_in_hwi_p (double_int cst, bool uns)
|
|
|
148 {
|
|
|
149 if (uns)
|
|
|
150 return double_int_fits_in_uhwi_p (cst);
|
|
|
151 else
|
|
|
152 return double_int_fits_in_shwi_p (cst);
|
|
|
153 }
|
|
|
154
|
|
|
155 /* Returns value of CST as a signed number. CST must satisfy
|
|
|
156 double_int_fits_in_shwi_p. */
|
|
|
157
|
|
|
158 HOST_WIDE_INT
|
|
|
159 double_int_to_shwi (double_int cst)
|
|
|
160 {
|
|
|
161 return (HOST_WIDE_INT) cst.low;
|
|
|
162 }
|
|
|
163
|
|
|
164 /* Returns value of CST as an unsigned number. CST must satisfy
|
|
|
165 double_int_fits_in_uhwi_p. */
|
|
|
166
|
|
|
167 unsigned HOST_WIDE_INT
|
|
|
168 double_int_to_uhwi (double_int cst)
|
|
|
169 {
|
|
|
170 return cst.low;
|
|
|
171 }
|
|
|
172
|
|
|
173 /* Returns A * B. */
|
|
|
174
|
|
|
175 double_int
|
|
|
176 double_int_mul (double_int a, double_int b)
|
|
|
177 {
|
|
|
178 double_int ret;
|
|
|
179 mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
|
|
|
180 return ret;
|
|
|
181 }
|
|
|
182
|
|
|
183 /* Returns A + B. */
|
|
|
184
|
|
|
185 double_int
|
|
|
186 double_int_add (double_int a, double_int b)
|
|
|
187 {
|
|
|
188 double_int ret;
|
|
|
189 add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
|
|
|
190 return ret;
|
|
|
191 }
|
|
|
192
|
|
|
193 /* Returns -A. */
|
|
|
194
|
|
|
195 double_int
|
|
|
196 double_int_neg (double_int a)
|
|
|
197 {
|
|
|
198 double_int ret;
|
|
|
199 neg_double (a.low, a.high, &ret.low, &ret.high);
|
|
|
200 return ret;
|
|
|
201 }
|
|
|
202
|
|
|
203 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
|
|
|
204 specified by CODE). CODE is enum tree_code in fact, but double_int.h
|
|
|
205 must be included before tree.h. The remainder after the division is
|
|
|
206 stored to MOD. */
|
|
|
207
|
|
|
208 double_int
|
|
|
209 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
|
|
|
210 double_int *mod)
|
|
|
211 {
|
|
|
212 double_int ret;
|
|
|
213
|
|
|
214 div_and_round_double (code, uns, a.low, a.high, b.low, b.high,
|
|
|
215 &ret.low, &ret.high, &mod->low, &mod->high);
|
|
|
216 return ret;
|
|
|
217 }
|
|
|
218
|
|
|
219 /* The same as double_int_divmod with UNS = false. */
|
|
|
220
|
|
|
221 double_int
|
|
|
222 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
|
|
|
223 {
|
|
|
224 return double_int_divmod (a, b, false, code, mod);
|
|
|
225 }
|
|
|
226
|
|
|
227 /* The same as double_int_divmod with UNS = true. */
|
|
|
228
|
|
|
229 double_int
|
|
|
230 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
|
|
|
231 {
|
|
|
232 return double_int_divmod (a, b, true, code, mod);
|
|
|
233 }
|
|
|
234
|
|
|
235 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
|
|
|
236 specified by CODE). CODE is enum tree_code in fact, but double_int.h
|
|
|
237 must be included before tree.h. */
|
|
|
238
|
|
|
239 double_int
|
|
|
240 double_int_div (double_int a, double_int b, bool uns, unsigned code)
|
|
|
241 {
|
|
|
242 double_int mod;
|
|
|
243
|
|
|
244 return double_int_divmod (a, b, uns, code, &mod);
|
|
|
245 }
|
|
|
246
|
|
|
247 /* The same as double_int_div with UNS = false. */
|
|
|
248
|
|
|
249 double_int
|
|
|
250 double_int_sdiv (double_int a, double_int b, unsigned code)
|
|
|
251 {
|
|
|
252 return double_int_div (a, b, false, code);
|
|
|
253 }
|
|
|
254
|
|
|
255 /* The same as double_int_div with UNS = true. */
|
|
|
256
|
|
|
257 double_int
|
|
|
258 double_int_udiv (double_int a, double_int b, unsigned code)
|
|
|
259 {
|
|
|
260 return double_int_div (a, b, true, code);
|
|
|
261 }
|
|
|
262
|
|
|
263 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
|
|
|
264 specified by CODE). CODE is enum tree_code in fact, but double_int.h
|
|
|
265 must be included before tree.h. */
|
|
|
266
|
|
|
267 double_int
|
|
|
268 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
|
|
|
269 {
|
|
|
270 double_int mod;
|
|
|
271
|
|
|
272 double_int_divmod (a, b, uns, code, &mod);
|
|
|
273 return mod;
|
|
|
274 }
|
|
|
275
|
|
|
276 /* The same as double_int_mod with UNS = false. */
|
|
|
277
|
|
|
278 double_int
|
|
|
279 double_int_smod (double_int a, double_int b, unsigned code)
|
|
|
280 {
|
|
|
281 return double_int_mod (a, b, false, code);
|
|
|
282 }
|
|
|
283
|
|
|
284 /* The same as double_int_mod with UNS = true. */
|
|
|
285
|
|
|
286 double_int
|
|
|
287 double_int_umod (double_int a, double_int b, unsigned code)
|
|
|
288 {
|
|
|
289 return double_int_mod (a, b, true, code);
|
|
|
290 }
|
|
|
291
|
|
|
292 /* Constructs tree in type TYPE from with value given by CST. Signedness of CST
|
|
|
293 is assumed to be the same as the signedness of TYPE. */
|
|
|
294
|
|
|
295 tree
|
|
|
296 double_int_to_tree (tree type, double_int cst)
|
|
|
297 {
|
|
|
298 cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
|
|
|
299
|
|
|
300 return build_int_cst_wide (type, cst.low, cst.high);
|
|
|
301 }
|
|
|
302
|
|
|
303 /* Returns true if CST fits into range of TYPE. Signedness of CST is assumed
|
|
|
304 to be the same as the signedness of TYPE. */
|
|
|
305
|
|
|
306 bool
|
|
|
307 double_int_fits_to_tree_p (const_tree type, double_int cst)
|
|
|
308 {
|
|
|
309 double_int ext = double_int_ext (cst,
|
|
|
310 TYPE_PRECISION (type),
|
|
|
311 TYPE_UNSIGNED (type));
|
|
|
312
|
|
|
313 return double_int_equal_p (cst, ext);
|
|
|
314 }
|
|
|
315
|
|
|
316 /* Returns true if CST is negative. Of course, CST is considered to
|
|
|
317 be signed. */
|
|
|
318
|
|
|
319 bool
|
|
|
320 double_int_negative_p (double_int cst)
|
|
|
321 {
|
|
|
322 return cst.high < 0;
|
|
|
323 }
|
|
|
324
|
|
|
325 /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the
|
|
|
326 comparison is given by UNS. */
|
|
|
327
|
|
|
328 int
|
|
|
329 double_int_cmp (double_int a, double_int b, bool uns)
|
|
|
330 {
|
|
|
331 if (uns)
|
|
|
332 return double_int_ucmp (a, b);
|
|
|
333 else
|
|
|
334 return double_int_scmp (a, b);
|
|
|
335 }
|
|
|
336
|
|
|
337 /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B,
|
|
|
338 and 1 if A > B. */
|
|
|
339
|
|
|
340 int
|
|
|
341 double_int_ucmp (double_int a, double_int b)
|
|
|
342 {
|
|
|
343 if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
|
|
|
344 return -1;
|
|
|
345 if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
|
|
|
346 return 1;
|
|
|
347 if (a.low < b.low)
|
|
|
348 return -1;
|
|
|
349 if (a.low > b.low)
|
|
|
350 return 1;
|
|
|
351
|
|
|
352 return 0;
|
|
|
353 }
|
|
|
354
|
|
|
355 /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B,
|
|
|
356 and 1 if A > B. */
|
|
|
357
|
|
|
358 int
|
|
|
359 double_int_scmp (double_int a, double_int b)
|
|
|
360 {
|
|
|
361 if (a.high < b.high)
|
|
|
362 return -1;
|
|
|
363 if (a.high > b.high)
|
|
|
364 return 1;
|
|
|
365 if (a.low < b.low)
|
|
|
366 return -1;
|
|
|
367 if (a.low > b.low)
|
|
|
368 return 1;
|
|
|
369
|
|
|
370 return 0;
|
|
|
371 }
|
|
|
372
|
|
|
373 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */
|
|
|
374
|
|
|
375 static unsigned
|
|
|
376 double_int_split_digit (double_int *cst, unsigned base)
|
|
|
377 {
|
|
|
378 unsigned HOST_WIDE_INT resl, reml;
|
|
|
379 HOST_WIDE_INT resh, remh;
|
|
|
380
|
|
|
381 div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
|
|
|
382 &resl, &resh, &reml, &remh);
|
|
|
383 cst->high = resh;
|
|
|
384 cst->low = resl;
|
|
|
385
|
|
|
386 return reml;
|
|
|
387 }
|
|
|
388
|
|
|
389 /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned,
|
|
|
390 otherwise it is signed. */
|
|
|
391
|
|
|
392 void
|
|
|
393 dump_double_int (FILE *file, double_int cst, bool uns)
|
|
|
394 {
|
|
|
395 unsigned digits[100], n;
|
|
|
396 int i;
|
|
|
397
|
|
|
398 if (double_int_zero_p (cst))
|
|
|
399 {
|
|
|
400 fprintf (file, "0");
|
|
|
401 return;
|
|
|
402 }
|
|
|
403
|
|
|
404 if (!uns && double_int_negative_p (cst))
|
|
|
405 {
|
|
|
406 fprintf (file, "-");
|
|
|
407 cst = double_int_neg (cst);
|
|
|
408 }
|
|
|
409
|
|
|
410 for (n = 0; !double_int_zero_p (cst); n++)
|
|
|
411 digits[n] = double_int_split_digit (&cst, 10);
|
|
|
412 for (i = n - 1; i >= 0; i--)
|
|
|
413 fprintf (file, "%u", digits[i]);
|
|
|
414 }
|
|
|
415
|
|
|
416
|
|
|
417 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
|
|
|
418 otherwise. */
|
|
|
419
|
|
|
420 void
|
|
|
421 mpz_set_double_int (mpz_t result, double_int val, bool uns)
|
|
|
422 {
|
|
|
423 bool negate = false;
|
|
|
424 unsigned HOST_WIDE_INT vp[2];
|
|
|
425
|
|
|
426 if (!uns && double_int_negative_p (val))
|
|
|
427 {
|
|
|
428 negate = true;
|
|
|
429 val = double_int_neg (val);
|
|
|
430 }
|
|
|
431
|
|
|
432 vp[0] = val.low;
|
|
|
433 vp[1] = (unsigned HOST_WIDE_INT) val.high;
|
|
|
434 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
|
|
|
435
|
|
|
436 if (negate)
|
|
|
437 mpz_neg (result, result);
|
|
|
438 }
|
|
|
439
|
|
|
440 /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range
|
|
|
441 values of VAL will be wrapped; otherwise, they will be set to the
|
|
|
442 appropriate minimum or maximum TYPE bound. */
|
|
|
443
|
|
|
444 double_int
|
|
|
445 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
|
|
|
446 {
|
|
|
447 unsigned HOST_WIDE_INT *vp;
|
|
|
448 size_t count, numb;
|
|
|
449 double_int res;
|
|
|
450
|
|
|
451 if (!wrap)
|
|
|
452 {
|
|
|
453 mpz_t min, max;
|
|
|
454
|
|
|
455 mpz_init (min);
|
|
|
456 mpz_init (max);
|
|
|
457 get_type_static_bounds (type, min, max);
|
|
|
458
|
|
|
459 if (mpz_cmp (val, min) < 0)
|
|
|
460 mpz_set (val, min);
|
|
|
461 else if (mpz_cmp (val, max) > 0)
|
|
|
462 mpz_set (val, max);
|
|
|
463
|
|
|
464 mpz_clear (min);
|
|
|
465 mpz_clear (max);
|
|
|
466 }
|
|
|
467
|
|
|
468 /* Determine the number of unsigned HOST_WIDE_INT that are required
|
|
|
469 for representing the value. The code to calculate count is
|
|
|
470 extracted from the GMP manual, section "Integer Import and Export":
|
|
|
471 http://gmplib.org/manual/Integer-Import-and-Export.html */
|
|
|
472 numb = 8*sizeof(HOST_WIDE_INT);
|
|
|
473 count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
|
|
|
474 if (count < 2)
|
|
|
475 count = 2;
|
|
|
476 vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
|
|
|
477
|
|
|
478 vp[0] = 0;
|
|
|
479 vp[1] = 0;
|
|
|
480 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
|
|
|
481
|
|
|
482 gcc_assert (wrap || count <= 2);
|
|
|
483
|
|
|
484 res.low = vp[0];
|
|
|
485 res.high = (HOST_WIDE_INT) vp[1];
|
|
|
486
|
|
|
487 res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
|
|
|
488 if (mpz_sgn (val) < 0)
|
|
|
489 res = double_int_neg (res);
|
|
|
490
|
|
|
491 return res;
|
|
|
492 }
|
