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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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