gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2009, 2010, 2012 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 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_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                                  bool);
  41
  42 static int mul_double_wide_with_sign (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
  43                                       unsigned HOST_WIDE_INT, HOST_WIDE_INT,
  44                                       unsigned HOST_WIDE_INT *, HOST_WIDE_INT *,
  45                                       unsigned HOST_WIDE_INT *, HOST_WIDE_INT *,
  46                                       bool);
  47
  48 #define mul_double(l1,h1,l2,h2,lv,hv) \
  49   mul_double_with_sign (l1, h1, l2, h2, lv, hv, false)
  50
  51 static void lshift_double (unsigned HOST_WIDE_INT, HOST_WIDE_INT,
  52                            HOST_WIDE_INT, unsigned int,
  53                            unsigned HOST_WIDE_INT *, HOST_WIDE_INT *, bool);
  54
  55 static int div_and_round_double (unsigned, int, unsigned HOST_WIDE_INT,
  56                                  HOST_WIDE_INT, unsigned HOST_WIDE_INT,
  57                                  HOST_WIDE_INT, unsigned HOST_WIDE_INT *,
  58                                  HOST_WIDE_INT *, unsigned HOST_WIDE_INT *,
  59                                  HOST_WIDE_INT *);
  60
  61 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
  62    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
  63    and SUM1.  Then this yields nonzero if overflow occurred during the
  64    addition.
  65
  66    Overflow occurs if A and B have the same sign, but A and SUM differ in
  67    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
  68    sign.  */
  69 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
  70
  71 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
  72    We do that by representing the two-word integer in 4 words, with only
  73    HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
  74    number.  The value of the word is LOWPART + HIGHPART * BASE.  */
  75
  76 #define LOWPART(x) \
  77   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
  78 #define HIGHPART(x) \
  79   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
  80 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
  81
  82 /* Unpack a two-word integer into 4 words.
  83    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
  84    WORDS points to the array of HOST_WIDE_INTs.  */
  85
  86 static void
  87 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
  88 {
  89   words[0] = LOWPART (low);
  90   words[1] = HIGHPART (low);
  91   words[2] = LOWPART (hi);
  92   words[3] = HIGHPART (hi);
  93 }
  94
  95 /* Pack an array of 4 words into a two-word integer.
  96    WORDS points to the array of words.
  97    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
  98
  99 static void
 100 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
 101         HOST_WIDE_INT *hi)
 102 {
 103   *low = words[0] + words[1] * BASE;
 104   *hi = words[2] + words[3] * BASE;
 105 }
 106
 107 /* Add two doubleword integers with doubleword result.
 108    Return nonzero if the operation overflows according to UNSIGNED_P.
 109    Each argument is given as two `HOST_WIDE_INT' pieces.
 110    One argument is L1 and H1; the other, L2 and H2.
 111    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 112
 113 static int
 114 add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 115                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 116                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 117                       bool unsigned_p)
 118 {
 119   unsigned HOST_WIDE_INT l;
 120   HOST_WIDE_INT h;
 121
 122   l = l1 + l2;
 123   h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
 124                        + (unsigned HOST_WIDE_INT) h2
 125                        + (l < l1));
 126
 127   *lv = l;
 128   *hv = h;
 129
 130   if (unsigned_p)
 131     return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
 132             || (h == h1
 133                 && l < l1));
 134   else
 135     return OVERFLOW_SUM_SIGN (h1, h2, h);
 136 }
 137
 138 /* Negate a doubleword integer with doubleword result.
 139    Return nonzero if the operation overflows, assuming it's signed.
 140    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 141    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 142
 143 static int
 144 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 145             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 146 {
 147   if (l1 == 0)
 148     {
 149       *lv = 0;
 150       *hv = - h1;
 151       return (*hv & h1) < 0;
 152     }
 153   else
 154     {
 155       *lv = -l1;
 156       *hv = ~h1;
 157       return 0;
 158     }
 159 }
 160
 161 /* Multiply two doubleword integers with doubleword result.
 162    Return nonzero if the operation overflows according to UNSIGNED_P.
 163    Each argument is given as two `HOST_WIDE_INT' pieces.
 164    One argument is L1 and H1; the other, L2 and H2.
 165    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 166
 167 static int
 168 mul_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 169                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 170                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 171                       bool unsigned_p)
 172 {
 173   unsigned HOST_WIDE_INT toplow;
 174   HOST_WIDE_INT tophigh;
 175
 176   return mul_double_wide_with_sign (l1, h1, l2, h2,
 177                                     lv, hv, &toplow, &tophigh,
 178                                     unsigned_p);
 179 }
 180
 181 static int
 182 mul_double_wide_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 183                            unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 184                            unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 185                            unsigned HOST_WIDE_INT *lw, HOST_WIDE_INT *hw,
 186                            bool unsigned_p)
 187 {
 188   HOST_WIDE_INT arg1[4];
 189   HOST_WIDE_INT arg2[4];
 190   HOST_WIDE_INT prod[4 * 2];
 191   unsigned HOST_WIDE_INT carry;
 192   int i, j, k;
 193   unsigned HOST_WIDE_INT neglow;
 194   HOST_WIDE_INT neghigh;
 195
 196   encode (arg1, l1, h1);
 197   encode (arg2, l2, h2);
 198
 199   memset (prod, 0, sizeof prod);
 200
 201   for (i = 0; i < 4; i++)
 202     {
 203       carry = 0;
 204       for (j = 0; j < 4; j++)
 205         {
 206           k = i + j;
 207           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 208           carry += (unsigned HOST_WIDE_INT) arg1[i] * arg2[j];
 209           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 210           carry += prod[k];
 211           prod[k] = LOWPART (carry);
 212           carry = HIGHPART (carry);
 213         }
 214       prod[i + 4] = carry;
 215     }
 216
 217   decode (prod, lv, hv);
 218   decode (prod + 4, lw, hw);
 219
 220   /* Unsigned overflow is immediate.  */
 221   if (unsigned_p)
 222     return (*lw | *hw) != 0;
 223
 224   /* Check for signed overflow by calculating the signed representation of the
 225      top half of the result; it should agree with the low half's sign bit.  */
 226   if (h1 < 0)
 227     {
 228       neg_double (l2, h2, &neglow, &neghigh);
 229       add_double (neglow, neghigh, *lw, *hw, lw, hw);
 230     }
 231   if (h2 < 0)
 232     {
 233       neg_double (l1, h1, &neglow, &neghigh);
 234       add_double (neglow, neghigh, *lw, *hw, lw, hw);
 235     }
 236   return (*hv < 0 ? ~(*lw & *hw) : *lw | *hw) != 0;
 237 }
 238
 239 /* Shift the doubleword integer in L1, H1 right by COUNT places
 240    keeping only PREC bits of result.  ARITH nonzero specifies
 241    arithmetic shifting; otherwise use logical shift.
 242    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 243
 244 static void
 245 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 246                unsigned HOST_WIDE_INT count, unsigned int prec,
 247                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 248                bool arith)
 249 {
 250   unsigned HOST_WIDE_INT signmask;
 251
 252   signmask = (arith
 253               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 254               : 0);
 255
 256   if (SHIFT_COUNT_TRUNCATED)
 257     count %= prec;
 258
 259   if (count >= HOST_BITS_PER_DOUBLE_INT)
 260     {
 261       /* Shifting by the host word size is undefined according to the
 262          ANSI standard, so we must handle this as a special case.  */
 263       *hv = 0;
 264       *lv = 0;
 265     }
 266   else if (count >= HOST_BITS_PER_WIDE_INT)
 267     {
 268       *hv = 0;
 269       *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
 270     }
 271   else
 272     {
 273       *hv = (unsigned HOST_WIDE_INT) h1 >> count;
 274       *lv = ((l1 >> count)
 275              | ((unsigned HOST_WIDE_INT) h1
 276                 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 277     }
 278
 279   /* Zero / sign extend all bits that are beyond the precision.  */
 280
 281   if (count >= prec)
 282     {
 283       *hv = signmask;
 284       *lv = signmask;
 285     }
 286   else if ((prec - count) >= HOST_BITS_PER_DOUBLE_INT)
 287     ;
 288   else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
 289     {
 290       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
 291       *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
 292     }
 293   else
 294     {
 295       *hv = signmask;
 296       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
 297       *lv |= signmask << (prec - count);
 298     }
 299 }
 300
 301 /* Shift the doubleword integer in L1, H1 left by COUNT places
 302    keeping only PREC bits of result.
 303    Shift right if COUNT is negative.
 304    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 305    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 306
 307 static void
 308 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 309                HOST_WIDE_INT count, unsigned int prec,
 310                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, bool arith)
 311 {
 312   unsigned HOST_WIDE_INT signmask;
 313
 314   if (count < 0)
 315     {
 316       rshift_double (l1, h1, absu_hwi (count), prec, lv, hv, arith);
 317       return;
 318     }
 319
 320   if (SHIFT_COUNT_TRUNCATED)
 321     count %= prec;
 322
 323   if (count >= HOST_BITS_PER_DOUBLE_INT)
 324     {
 325       /* Shifting by the host word size is undefined according to the
 326          ANSI standard, so we must handle this as a special case.  */
 327       *hv = 0;
 328       *lv = 0;
 329     }
 330   else if (count >= HOST_BITS_PER_WIDE_INT)
 331     {
 332       *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
 333       *lv = 0;
 334     }
 335   else
 336     {
 337       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 338              | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 339       *lv = l1 << count;
 340     }
 341
 342   /* Sign extend all bits that are beyond the precision.  */
 343
 344   signmask = -((prec > HOST_BITS_PER_WIDE_INT
 345                 ? ((unsigned HOST_WIDE_INT) *hv
 346                    >> (prec - HOST_BITS_PER_WIDE_INT - 1))
 347                 : (*lv >> (prec - 1))) & 1);
 348
 349   if (prec >= HOST_BITS_PER_DOUBLE_INT)
 350     ;
 351   else if (prec >= HOST_BITS_PER_WIDE_INT)
 352     {
 353       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 354       *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
 355     }
 356   else
 357     {
 358       *hv = signmask;
 359       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
 360       *lv |= signmask << prec;
 361     }
 362 }
 363
 364 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 365    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 366    CODE is a tree code for a kind of division, one of
 367    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 368    or EXACT_DIV_EXPR
 369    It controls how the quotient is rounded to an integer.
 370    Return nonzero if the operation overflows.
 371    UNS nonzero says do unsigned division.  */
 372
 373 static int
 374 div_and_round_double (unsigned code, int uns,
 375                       /* num == numerator == dividend */
 376                       unsigned HOST_WIDE_INT lnum_orig,
 377                       HOST_WIDE_INT hnum_orig,
 378                       /* den == denominator == divisor */
 379                       unsigned HOST_WIDE_INT lden_orig,
 380                       HOST_WIDE_INT hden_orig,
 381                       unsigned HOST_WIDE_INT *lquo,
 382                       HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
 383                       HOST_WIDE_INT *hrem)
 384 {
 385   int quo_neg = 0;
 386   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 387   HOST_WIDE_INT den[4], quo[4];
 388   int i, j;
 389   unsigned HOST_WIDE_INT work;
 390   unsigned HOST_WIDE_INT carry = 0;
 391   unsigned HOST_WIDE_INT lnum = lnum_orig;
 392   HOST_WIDE_INT hnum = hnum_orig;
 393   unsigned HOST_WIDE_INT lden = lden_orig;
 394   HOST_WIDE_INT hden = hden_orig;
 395   int overflow = 0;
 396
 397   if (hden == 0 && lden == 0)
 398     overflow = 1, lden = 1;
 399
 400   /* Calculate quotient sign and convert operands to unsigned.  */
 401   if (!uns)
 402     {
 403       if (hnum < 0)
 404         {
 405           quo_neg = ~ quo_neg;
 406           /* (minimum integer) / (-1) is the only overflow case.  */
 407           if (neg_double (lnum, hnum, &lnum, &hnum)
 408               && ((HOST_WIDE_INT) lden & hden) == -1)
 409             overflow = 1;
 410         }
 411       if (hden < 0)
 412         {
 413           quo_neg = ~ quo_neg;
 414           neg_double (lden, hden, &lden, &hden);
 415         }
 416     }
 417
 418   if (hnum == 0 && hden == 0)
 419     {                           /* single precision */
 420       *hquo = *hrem = 0;
 421       /* This unsigned division rounds toward zero.  */
 422       *lquo = lnum / lden;
 423       goto finish_up;
 424     }
 425
 426   if (hnum == 0)
 427     {                           /* trivial case: dividend < divisor */
 428       /* hden != 0 already checked.  */
 429       *hquo = *lquo = 0;
 430       *hrem = hnum;
 431       *lrem = lnum;
 432       goto finish_up;
 433     }
 434
 435   memset (quo, 0, sizeof quo);
 436
 437   memset (num, 0, sizeof num);  /* to zero 9th element */
 438   memset (den, 0, sizeof den);
 439
 440   encode (num, lnum, hnum);
 441   encode (den, lden, hden);
 442
 443   /* Special code for when the divisor < BASE.  */
 444   if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
 445     {
 446       /* hnum != 0 already checked.  */
 447       for (i = 4 - 1; i >= 0; i--)
 448         {
 449           work = num[i] + carry * BASE;
 450           quo[i] = work / lden;
 451           carry = work % lden;
 452         }
 453     }
 454   else
 455     {
 456       /* Full double precision division,
 457          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 458       int num_hi_sig, den_hi_sig;
 459       unsigned HOST_WIDE_INT quo_est, scale;
 460
 461       /* Find the highest nonzero divisor digit.  */
 462       for (i = 4 - 1;; i--)
 463         if (den[i] != 0)
 464           {
 465             den_hi_sig = i;
 466             break;
 467           }
 468
 469       /* Insure that the first digit of the divisor is at least BASE/2.
 470          This is required by the quotient digit estimation algorithm.  */
 471
 472       scale = BASE / (den[den_hi_sig] + 1);
 473       if (scale > 1)
 474         {               /* scale divisor and dividend */
 475           carry = 0;
 476           for (i = 0; i <= 4 - 1; i++)
 477             {
 478               work = (num[i] * scale) + carry;
 479               num[i] = LOWPART (work);
 480               carry = HIGHPART (work);
 481             }
 482
 483           num[4] = carry;
 484           carry = 0;
 485           for (i = 0; i <= 4 - 1; i++)
 486             {
 487               work = (den[i] * scale) + carry;
 488               den[i] = LOWPART (work);
 489               carry = HIGHPART (work);
 490               if (den[i] != 0) den_hi_sig = i;
 491             }
 492         }
 493
 494       num_hi_sig = 4;
 495
 496       /* Main loop */
 497       for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
 498         {
 499           /* Guess the next quotient digit, quo_est, by dividing the first
 500              two remaining dividend digits by the high order quotient digit.
 501              quo_est is never low and is at most 2 high.  */
 502           unsigned HOST_WIDE_INT tmp;
 503
 504           num_hi_sig = i + den_hi_sig + 1;
 505           work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 506           if (num[num_hi_sig] != den[den_hi_sig])
 507             quo_est = work / den[den_hi_sig];
 508           else
 509             quo_est = BASE - 1;
 510
 511           /* Refine quo_est so it's usually correct, and at most one high.  */
 512           tmp = work - quo_est * den[den_hi_sig];
 513           if (tmp < BASE
 514               && (den[den_hi_sig - 1] * quo_est
 515                   > (tmp * BASE + num[num_hi_sig - 2])))
 516             quo_est--;
 517
 518           /* Try QUO_EST as the quotient digit, by multiplying the
 519              divisor by QUO_EST and subtracting from the remaining dividend.
 520              Keep in mind that QUO_EST is the I - 1st digit.  */
 521
 522           carry = 0;
 523           for (j = 0; j <= den_hi_sig; j++)
 524             {
 525               work = quo_est * den[j] + carry;
 526               carry = HIGHPART (work);
 527               work = num[i + j] - LOWPART (work);
 528               num[i + j] = LOWPART (work);
 529               carry += HIGHPART (work) != 0;
 530             }
 531
 532           /* If quo_est was high by one, then num[i] went negative and
 533              we need to correct things.  */
 534           if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
 535             {
 536               quo_est--;
 537               carry = 0;                /* add divisor back in */
 538               for (j = 0; j <= den_hi_sig; j++)
 539                 {
 540                   work = num[i + j] + den[j] + carry;
 541                   carry = HIGHPART (work);
 542                   num[i + j] = LOWPART (work);
 543                 }
 544
 545               num [num_hi_sig] += carry;
 546             }
 547
 548           /* Store the quotient digit.  */
 549           quo[i] = quo_est;
 550         }
 551     }
 552
 553   decode (quo, lquo, hquo);
 554
 555  finish_up:
 556   /* If result is negative, make it so.  */
 557   if (quo_neg)
 558     neg_double (*lquo, *hquo, lquo, hquo);
 559
 560   /* Compute trial remainder:  rem = num - (quo * den)  */
 561   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 562   neg_double (*lrem, *hrem, lrem, hrem);
 563   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 564
 565   switch (code)
 566     {
 567     case TRUNC_DIV_EXPR:
 568     case TRUNC_MOD_EXPR:        /* round toward zero */
 569     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 570       return overflow;
 571
 572     case FLOOR_DIV_EXPR:
 573     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 574       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 575         {
 576           /* quo = quo - 1;  */
 577           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 578                       lquo, hquo);
 579         }
 580       else
 581         return overflow;
 582       break;
 583
 584     case CEIL_DIV_EXPR:
 585     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 586       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 587         {
 588           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 589                       lquo, hquo);
 590         }
 591       else
 592         return overflow;
 593       break;
 594
 595     case ROUND_DIV_EXPR:
 596     case ROUND_MOD_EXPR:        /* round to closest integer */
 597       {
 598         unsigned HOST_WIDE_INT labs_rem = *lrem;
 599         HOST_WIDE_INT habs_rem = *hrem;
 600         unsigned HOST_WIDE_INT labs_den = lden, ltwice;
 601         HOST_WIDE_INT habs_den = hden, htwice;
 602
 603         /* Get absolute values.  */
 604         if (*hrem < 0)
 605           neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 606         if (hden < 0)
 607           neg_double (lden, hden, &labs_den, &habs_den);
 608
 609         /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient.  */
 610         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 611                     labs_rem, habs_rem, &ltwice, &htwice);
 612
 613         if (((unsigned HOST_WIDE_INT) habs_den
 614              < (unsigned HOST_WIDE_INT) htwice)
 615             || (((unsigned HOST_WIDE_INT) habs_den
 616                  == (unsigned HOST_WIDE_INT) htwice)
 617                 && (labs_den <= ltwice)))
 618           {
 619             if (*hquo < 0)
 620               /* quo = quo - 1;  */
 621               add_double (*lquo, *hquo,
 622                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 623             else
 624               /* quo = quo + 1; */
 625               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 626                           lquo, hquo);
 627           }
 628         else
 629           return overflow;
 630       }
 631       break;
 632
 633     default:
 634       gcc_unreachable ();
 635     }
 636
 637   /* Compute true remainder:  rem = num - (quo * den)  */
 638   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 639   neg_double (*lrem, *hrem, lrem, hrem);
 640   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 641   return overflow;
 642 }
 643
 644 /* Returns mask for PREC bits.  */
 645
 646 double_int
 647 double_int::mask (unsigned prec)
 648 {
 649   unsigned HOST_WIDE_INT m;
 650   double_int mask;
 651
 652   if (prec > HOST_BITS_PER_WIDE_INT)
 653     {
 654       prec -= HOST_BITS_PER_WIDE_INT;
 655       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 656       mask.high = (HOST_WIDE_INT) m;
 657       mask.low = ALL_ONES;
 658     }
 659   else
 660     {
 661       mask.high = 0;
 662       mask.low = prec ? ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1 : 0;
 663     }
 664
 665   return mask;
 666 }
 667
 668 /* Returns a maximum value for signed or unsigned integer
 669    of precision PREC.  */
 670
 671 double_int
 672 double_int::max_value (unsigned int prec, bool uns)
 673 {
 674   return double_int::mask (prec - (uns ? 0 : 1));
 675 }
 676
 677 /* Returns a minimum value for signed or unsigned integer
 678    of precision PREC.  */
 679
 680 double_int
 681 double_int::min_value (unsigned int prec, bool uns)
 682 {
 683   if (uns)
 684     return double_int_zero;
 685   return double_int_one.lshift (prec - 1, prec, false);
 686 }
 687
 688 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
 689    outside of the precision are set to the sign bit (i.e., the PREC-th one),
 690    otherwise they are set to zero.
 691
 692    This corresponds to returning the value represented by PREC lowermost bits
 693    of CST, with the given signedness.  */
 694
 695 double_int
 696 double_int::ext (unsigned prec, bool uns) const
 697 {
 698   if (uns)
 699     return this->zext (prec);
 700   else
 701     return this->sext (prec);
 702 }
 703
 704 /* The same as double_int::ext with UNS = true.  */
 705
 706 double_int
 707 double_int::zext (unsigned prec) const
 708 {
 709   const double_int &cst = *this;
 710   double_int mask = double_int::mask (prec);
 711   double_int r;
 712
 713   r.low = cst.low & mask.low;
 714   r.high = cst.high & mask.high;
 715
 716   return r;
 717 }
 718
 719 /* The same as double_int::ext with UNS = false.  */
 720
 721 double_int
 722 double_int::sext (unsigned prec) const
 723 {
 724   const double_int &cst = *this;
 725   double_int mask = double_int::mask (prec);
 726   double_int r;
 727   unsigned HOST_WIDE_INT snum;
 728
 729   if (prec <= HOST_BITS_PER_WIDE_INT)
 730     snum = cst.low;
 731   else
 732     {
 733       prec -= HOST_BITS_PER_WIDE_INT;
 734       snum = (unsigned HOST_WIDE_INT) cst.high;
 735     }
 736   if (((snum >> (prec - 1)) & 1) == 1)
 737     {
 738       r.low = cst.low | ~mask.low;
 739       r.high = cst.high | ~mask.high;
 740     }
 741   else
 742     {
 743       r.low = cst.low & mask.low;
 744       r.high = cst.high & mask.high;
 745     }
 746
 747   return r;
 748 }
 749
 750 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 751
 752 bool
 753 double_int::fits_shwi () const
 754 {
 755   const double_int &cst = *this;
 756   if (cst.high == 0)
 757     return (HOST_WIDE_INT) cst.low >= 0;
 758   else if (cst.high == -1)
 759     return (HOST_WIDE_INT) cst.low < 0;
 760   else
 761     return false;
 762 }
 763
 764 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 765    unsigned HOST_WIDE_INT if UNS is true.  */
 766
 767 bool
 768 double_int::fits_hwi (bool uns) const
 769 {
 770   if (uns)
 771     return this->fits_uhwi ();
 772   else
 773     return this->fits_shwi ();
 774 }
 775
 776 /* Returns A * B.  */
 777
 778 double_int
 779 double_int::operator * (double_int b) const
 780 {
 781   const double_int &a = *this;
 782   double_int ret;
 783   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 784   return ret;
 785 }
 786
 787 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
 788    *OVERFLOW is set to nonzero.  */
 789
 790 double_int
 791 double_int::mul_with_sign (double_int b, bool unsigned_p, bool *overflow) const
 792 {
 793   const double_int &a = *this;
 794   double_int ret;
 795   *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
 796                                     &ret.low, &ret.high, unsigned_p);
 797   return ret;
 798 }
 799
 800 double_int
 801 double_int::wide_mul_with_sign (double_int b, bool unsigned_p,
 802                                 double_int *higher, bool *overflow) const
 803
 804 {
 805   double_int lower;
 806   *overflow = mul_double_wide_with_sign (low, high, b.low, b.high,
 807                                          &lower.low, &lower.high,
 808                                          &higher->low, &higher->high,
 809                                          unsigned_p);
 810   return lower;
 811 }
 812
 813 /* Returns A + B.  */
 814
 815 double_int
 816 double_int::operator + (double_int b) const
 817 {
 818   const double_int &a = *this;
 819   double_int ret;
 820   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 821   return ret;
 822 }
 823
 824 /* Returns A + B. If the operation overflows according to UNSIGNED_P,
 825    *OVERFLOW is set to nonzero.  */
 826
 827 double_int
 828 double_int::add_with_sign (double_int b, bool unsigned_p, bool *overflow) const
 829 {
 830   const double_int &a = *this;
 831   double_int ret;
 832   *overflow = add_double_with_sign (a.low, a.high, b.low, b.high,
 833                                     &ret.low, &ret.high, unsigned_p);
 834   return ret;
 835 }
 836
 837 /* Returns A - B.  */
 838
 839 double_int
 840 double_int::operator - (double_int b) const
 841 {
 842   const double_int &a = *this;
 843   double_int ret;
 844   neg_double (b.low, b.high, &b.low, &b.high);
 845   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 846   return ret;
 847 }
 848
 849 /* Returns A - B. If the operation overflows via inconsistent sign bits,
 850    *OVERFLOW is set to nonzero.  */
 851
 852 double_int
 853 double_int::sub_with_overflow (double_int b, bool *overflow) const
 854 {
 855   double_int ret;
 856   neg_double (b.low, b.high, &ret.low, &ret.high);
 857   add_double (low, high, ret.low, ret.high, &ret.low, &ret.high);
 858   *overflow = OVERFLOW_SUM_SIGN (ret.high, b.high, high);
 859   return ret;
 860 }
 861
 862 /* Returns -A.  */
 863
 864 double_int
 865 double_int::operator - () const
 866 {
 867   const double_int &a = *this;
 868   double_int ret;
 869   neg_double (a.low, a.high, &ret.low, &ret.high);
 870   return ret;
 871 }
 872
 873 double_int
 874 double_int::neg_with_overflow (bool *overflow) const
 875 {
 876   double_int ret;
 877   *overflow = neg_double (low, high, &ret.low, &ret.high);
 878   return ret;
 879 }
 880
 881 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 882    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 883    must be included before tree.h.  The remainder after the division is
 884    stored to MOD.  */
 885
 886 double_int
 887 double_int::divmod_with_overflow (double_int b, bool uns, unsigned code,
 888                                   double_int *mod, bool *overflow) const
 889 {
 890   const double_int &a = *this;
 891   double_int ret;
 892
 893   *overflow = div_and_round_double (code, uns, a.low, a.high,
 894                                     b.low, b.high, &ret.low, &ret.high,
 895                                     &mod->low, &mod->high);
 896   return ret;
 897 }
 898
 899 double_int
 900 double_int::divmod (double_int b, bool uns, unsigned code,
 901                     double_int *mod) const
 902 {
 903   const double_int &a = *this;
 904   double_int ret;
 905
 906   div_and_round_double (code, uns, a.low, a.high,
 907                         b.low, b.high, &ret.low, &ret.high,
 908                         &mod->low, &mod->high);
 909   return ret;
 910 }
 911
 912 /* The same as double_int::divmod with UNS = false.  */
 913
 914 double_int
 915 double_int::sdivmod (double_int b, unsigned code, double_int *mod) const
 916 {
 917   return this->divmod (b, false, code, mod);
 918 }
 919
 920 /* The same as double_int::divmod with UNS = true.  */
 921
 922 double_int
 923 double_int::udivmod (double_int b, unsigned code, double_int *mod) const
 924 {
 925   return this->divmod (b, true, code, mod);
 926 }
 927
 928 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 929    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 930    must be included before tree.h.  */
 931
 932 double_int
 933 double_int::div (double_int b, bool uns, unsigned code) const
 934 {
 935   double_int mod;
 936
 937   return this->divmod (b, uns, code, &mod);
 938 }
 939
 940 /* The same as double_int::div with UNS = false.  */
 941
 942 double_int
 943 double_int::sdiv (double_int b, unsigned code) const
 944 {
 945   return this->div (b, false, code);
 946 }
 947
 948 /* The same as double_int::div with UNS = true.  */
 949
 950 double_int
 951 double_int::udiv (double_int b, unsigned code) const
 952 {
 953   return this->div (b, true, code);
 954 }
 955
 956 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 957    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 958    must be included before tree.h.  */
 959
 960 double_int
 961 double_int::mod (double_int b, bool uns, unsigned code) const
 962 {
 963   double_int mod;
 964
 965   this->divmod (b, uns, code, &mod);
 966   return mod;
 967 }
 968
 969 /* The same as double_int::mod with UNS = false.  */
 970
 971 double_int
 972 double_int::smod (double_int b, unsigned code) const
 973 {
 974   return this->mod (b, false, code);
 975 }
 976
 977 /* The same as double_int::mod with UNS = true.  */
 978
 979 double_int
 980 double_int::umod (double_int b, unsigned code) const
 981 {
 982   return this->mod (b, true, code);
 983 }
 984
 985 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
 986    the multiple in *MULTIPLE.  Otherwise return FALSE and leave *MULTIPLE
 987    unchanged.  */
 988
 989 bool
 990 double_int::multiple_of (double_int factor,
 991                          bool unsigned_p, double_int *multiple) const
 992 {
 993   double_int remainder;
 994   double_int quotient = this->divmod (factor, unsigned_p,
 995                                            TRUNC_DIV_EXPR, &remainder);
 996   if (remainder.is_zero ())
 997     {
 998       *multiple = quotient;
 999       return true;
1000     }
1001
1002   return false;
1003 }
1004
1005 /* Set BITPOS bit in A.  */
1006 double_int
1007 double_int::set_bit (unsigned bitpos) const
1008 {
1009   double_int a = *this;
1010   if (bitpos < HOST_BITS_PER_WIDE_INT)
1011     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
1012   else
1013     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
1014
1015   return a;
1016 }
1017
1018 /* Count trailing zeros in A.  */
1019 int
1020 double_int::trailing_zeros () const
1021 {
1022   const double_int &a = *this;
1023   unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
1024   unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
1025   if (!w)
1026     return HOST_BITS_PER_DOUBLE_INT;
1027   bits += ctz_hwi (w);
1028   return bits;
1029 }
1030
1031 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
1032    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
1033    otherwise use logical shift.  */
1034
1035 double_int
1036 double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1037 {
1038   const double_int &a = *this;
1039   double_int ret;
1040   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
1041   return ret;
1042 }
1043
1044 /* Shift A right by COUNT places keeping only PREC bits of result.  Shift
1045    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
1046    otherwise use logical shift.  */
1047
1048 double_int
1049 double_int::rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1050 {
1051   const double_int &a = *this;
1052   double_int ret;
1053   lshift_double (a.low, a.high, -count, prec, &ret.low, &ret.high, arith);
1054   return ret;
1055 }
1056
1057 /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
1058    Shift right if COUNT is negative.  */
1059
1060 double_int
1061 double_int::alshift (HOST_WIDE_INT count, unsigned int prec) const
1062 {
1063   double_int r;
1064   lshift_double (low, high, count, prec, &r.low, &r.high, true);
1065   return r;
1066 }
1067
1068 /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
1069    Shift left if COUNT is negative.  */
1070
1071 double_int
1072 double_int::arshift (HOST_WIDE_INT count, unsigned int prec) const
1073 {
1074   double_int r;
1075   lshift_double (low, high, -count, prec, &r.low, &r.high, true);
1076   return r;
1077 }
1078
1079 /* Logical shift A left by COUNT places keeping only PREC bits of result.
1080    Shift right if COUNT is negative.  */
1081
1082 double_int
1083 double_int::llshift (HOST_WIDE_INT count, unsigned int prec) const
1084 {
1085   double_int r;
1086   lshift_double (low, high, count, prec, &r.low, &r.high, false);
1087   return r;
1088 }
1089
1090 /* Logical shift A right by COUNT places keeping only PREC bits of result.
1091    Shift left if COUNT is negative.  */
1092
1093 double_int
1094 double_int::lrshift (HOST_WIDE_INT count, unsigned int prec) const
1095 {
1096   double_int r;
1097   lshift_double (low, high, -count, prec, &r.low, &r.high, false);
1098   return r;
1099 }
1100
1101 /* Rotate  A left by COUNT places keeping only PREC bits of result.
1102    Rotate right if COUNT is negative.  */
1103
1104 double_int
1105 double_int::lrotate (HOST_WIDE_INT count, unsigned int prec) const
1106 {
1107   double_int t1, t2;
1108
1109   count %= prec;
1110   if (count < 0)
1111     count += prec;
1112
1113   t1 = this->lshift (count, prec, false);
1114   t2 = this->rshift (prec - count, prec, false);
1115
1116   return t1 | t2;
1117 }
1118
1119 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1120    Rotate right if COUNT is negative.  */
1121
1122 double_int
1123 double_int::rrotate (HOST_WIDE_INT count, unsigned int prec) const
1124 {
1125   double_int t1, t2;
1126
1127   count %= prec;
1128   if (count < 0)
1129     count += prec;
1130
1131   t1 = this->rshift (count, prec, false);
1132   t2 = this->lshift (prec - count, prec, false);
1133
1134   return t1 | t2;
1135 }
1136
1137 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
1138    comparison is given by UNS.  */
1139
1140 int
1141 double_int::cmp (double_int b, bool uns) const
1142 {
1143   if (uns)
1144     return this->ucmp (b);
1145   else
1146     return this->scmp (b);
1147 }
1148
1149 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
1150    and 1 if A > B.  */
1151
1152 int
1153 double_int::ucmp (double_int b) const
1154 {
1155   const double_int &a = *this;
1156   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
1157     return -1;
1158   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
1159     return 1;
1160   if (a.low < b.low)
1161     return -1;
1162   if (a.low > b.low)
1163     return 1;
1164
1165   return 0;
1166 }
1167
1168 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
1169    and 1 if A > B.  */
1170
1171 int
1172 double_int::scmp (double_int b) const
1173 {
1174   const double_int &a = *this;
1175   if (a.high < b.high)
1176     return -1;
1177   if (a.high > b.high)
1178     return 1;
1179   if (a.low < b.low)
1180     return -1;
1181   if (a.low > b.low)
1182     return 1;
1183
1184   return 0;
1185 }
1186
1187 /* Compares two unsigned values A and B for less-than.  */
1188
1189 bool
1190 double_int::ult (double_int b) const
1191 {
1192   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1193     return true;
1194   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1195     return false;
1196   if (low < b.low)
1197     return true;
1198   return false;
1199 }
1200
1201 /* Compares two unsigned values A and B for less-than or equal-to.  */
1202
1203 bool
1204 double_int::ule (double_int b) const
1205 {
1206   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1207     return true;
1208   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1209     return false;
1210   if (low <= b.low)
1211     return true;
1212   return false;
1213 }
1214
1215 /* Compares two unsigned values A and B for greater-than.  */
1216
1217 bool
1218 double_int::ugt (double_int b) const
1219 {
1220   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1221     return true;
1222   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1223     return false;
1224   if (low > b.low)
1225     return true;
1226   return false;
1227 }
1228
1229 /* Compares two signed values A and B for less-than.  */
1230
1231 bool
1232 double_int::slt (double_int b) const
1233 {
1234   if (high < b.high)
1235     return true;
1236   if (high > b.high)
1237     return false;
1238   if (low < b.low)
1239     return true;
1240   return false;
1241 }
1242
1243 /* Compares two signed values A and B for less-than or equal-to.  */
1244
1245 bool
1246 double_int::sle (double_int b) const
1247 {
1248   if (high < b.high)
1249     return true;
1250   if (high > b.high)
1251     return false;
1252   if (low <= b.low)
1253     return true;
1254   return false;
1255 }
1256
1257 /* Compares two signed values A and B for greater-than.  */
1258
1259 bool
1260 double_int::sgt (double_int b) const
1261 {
1262   if (high > b.high)
1263     return true;
1264   if (high < b.high)
1265     return false;
1266   if (low > b.low)
1267     return true;
1268   return false;
1269 }
1270
1271
1272 /* Compares two values A and B.  Returns max value.  Signedness of the
1273    comparison is given by UNS.  */
1274
1275 double_int
1276 double_int::max (double_int b, bool uns)
1277 {
1278   return (this->cmp (b, uns) == 1) ? *this : b;
1279 }
1280
1281 /* Compares two signed values A and B.  Returns max value.  */
1282
1283 double_int
1284 double_int::smax (double_int b)
1285 {
1286   return (this->scmp (b) == 1) ? *this : b;
1287 }
1288
1289 /* Compares two unsigned values A and B.  Returns max value.  */
1290
1291 double_int
1292 double_int::umax (double_int b)
1293 {
1294   return (this->ucmp (b) == 1) ? *this : b;
1295 }
1296
1297 /* Compares two values A and B.  Returns mix value.  Signedness of the
1298    comparison is given by UNS.  */
1299
1300 double_int
1301 double_int::min (double_int b, bool uns)
1302 {
1303   return (this->cmp (b, uns) == -1) ? *this : b;
1304 }
1305
1306 /* Compares two signed values A and B.  Returns min value.  */
1307
1308 double_int
1309 double_int::smin (double_int b)
1310 {
1311   return (this->scmp (b) == -1) ? *this : b;
1312 }
1313
1314 /* Compares two unsigned values A and B.  Returns min value.  */
1315
1316 double_int
1317 double_int::umin (double_int b)
1318 {
1319   return (this->ucmp (b) == -1) ? *this : b;
1320 }
1321
1322 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1323
1324 static unsigned
1325 double_int_split_digit (double_int *cst, unsigned base)
1326 {
1327   unsigned HOST_WIDE_INT resl, reml;
1328   HOST_WIDE_INT resh, remh;
1329
1330   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1331                         &resl, &resh, &reml, &remh);
1332   cst->high = resh;
1333   cst->low = resl;
1334
1335   return reml;
1336 }
1337
1338 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1339    otherwise it is signed.  */
1340
1341 void
1342 dump_double_int (FILE *file, double_int cst, bool uns)
1343 {
1344   unsigned digits[100], n;
1345   int i;
1346
1347   if (cst.is_zero ())
1348     {
1349       fprintf (file, "0");
1350       return;
1351     }
1352
1353   if (!uns && cst.is_negative ())
1354     {
1355       fprintf (file, "-");
1356       cst = -cst;
1357     }
1358
1359   for (n = 0; !cst.is_zero (); n++)
1360     digits[n] = double_int_split_digit (&cst, 10);
1361   for (i = n - 1; i >= 0; i--)
1362     fprintf (file, "%u", digits[i]);
1363 }
1364
1365
1366 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1367    otherwise.  */
1368
1369 void
1370 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1371 {
1372   bool negate = false;
1373   unsigned HOST_WIDE_INT vp[2];
1374
1375   if (!uns && val.is_negative ())
1376     {
1377       negate = true;
1378       val = -val;
1379     }
1380
1381   vp[0] = val.low;
1382   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1383   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1384
1385   if (negate)
1386     mpz_neg (result, result);
1387 }
1388
1389 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1390    values of VAL will be wrapped; otherwise, they will be set to the
1391    appropriate minimum or maximum TYPE bound.  */
1392
1393 double_int
1394 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1395 {
1396   unsigned HOST_WIDE_INT *vp;
1397   size_t count, numb;
1398   double_int res;
1399
1400   if (!wrap)
1401     {
1402       mpz_t min, max;
1403
1404       mpz_init (min);
1405       mpz_init (max);
1406       get_type_static_bounds (type, min, max);
1407
1408       if (mpz_cmp (val, min) < 0)
1409         mpz_set (val, min);
1410       else if (mpz_cmp (val, max) > 0)
1411         mpz_set (val, max);
1412
1413       mpz_clear (min);
1414       mpz_clear (max);
1415     }
1416
1417   /* Determine the number of unsigned HOST_WIDE_INT that are required
1418      for representing the value.  The code to calculate count is
1419      extracted from the GMP manual, section "Integer Import and Export":
1420      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1421   numb = 8*sizeof(HOST_WIDE_INT);
1422   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1423   if (count < 2)
1424     count = 2;
1425   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1426
1427   vp[0] = 0;
1428   vp[1] = 0;
1429   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1430
1431   gcc_assert (wrap || count <= 2);
1432
1433   res.low = vp[0];
1434   res.high = (HOST_WIDE_INT) vp[1];
1435
1436   res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1437   if (mpz_sgn (val) < 0)
1438     res = -res;
1439
1440   return res;
1441 }