gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006-2013 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
 645 /* Construct from a buffer of length LEN.  BUFFER will be read according
 646    to byte endianess and word endianess.  Only the lower LEN bytes
 647    of the result are set; the remaining high bytes are cleared.  */
 648
 649 double_int
 650 double_int::from_buffer (const unsigned char *buffer, int len)
 651 {
 652   double_int result = double_int_zero;
 653   int words = len / UNITS_PER_WORD;
 654
 655   gcc_assert (len * BITS_PER_UNIT <= HOST_BITS_PER_DOUBLE_INT);
 656
 657   for (int byte = 0; byte < len; byte++)
 658     {
 659       int offset;
 660       int bitpos = byte * BITS_PER_UNIT;
 661       unsigned HOST_WIDE_INT value;
 662
 663       if (len > UNITS_PER_WORD)
 664         {
 665           int word = byte / UNITS_PER_WORD;
 666
 667           if (WORDS_BIG_ENDIAN)
 668             word = (words - 1) - word;
 669
 670           offset = word * UNITS_PER_WORD;
 671
 672           if (BYTES_BIG_ENDIAN)
 673             offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD);
 674           else
 675             offset += byte % UNITS_PER_WORD;
 676         }
 677       else
 678         offset = BYTES_BIG_ENDIAN ? (len - 1) - byte : byte;
 679
 680       value = (unsigned HOST_WIDE_INT) buffer[offset];
 681
 682       if (bitpos < HOST_BITS_PER_WIDE_INT)
 683         result.low |= value << bitpos;
 684       else
 685         result.high |= value << (bitpos - HOST_BITS_PER_WIDE_INT);
 686     }
 687
 688   return result;
 689 }
 690
 691
 692 /* Returns mask for PREC bits.  */
 693
 694 double_int
 695 double_int::mask (unsigned prec)
 696 {
 697   unsigned HOST_WIDE_INT m;
 698   double_int mask;
 699
 700   if (prec > HOST_BITS_PER_WIDE_INT)
 701     {
 702       prec -= HOST_BITS_PER_WIDE_INT;
 703       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 704       mask.high = (HOST_WIDE_INT) m;
 705       mask.low = ALL_ONES;
 706     }
 707   else
 708     {
 709       mask.high = 0;
 710       mask.low = prec ? ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1 : 0;
 711     }
 712
 713   return mask;
 714 }
 715
 716 /* Returns a maximum value for signed or unsigned integer
 717    of precision PREC.  */
 718
 719 double_int
 720 double_int::max_value (unsigned int prec, bool uns)
 721 {
 722   return double_int::mask (prec - (uns ? 0 : 1));
 723 }
 724
 725 /* Returns a minimum value for signed or unsigned integer
 726    of precision PREC.  */
 727
 728 double_int
 729 double_int::min_value (unsigned int prec, bool uns)
 730 {
 731   if (uns)
 732     return double_int_zero;
 733   return double_int_one.lshift (prec - 1, prec, false);
 734 }
 735
 736 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
 737    outside of the precision are set to the sign bit (i.e., the PREC-th one),
 738    otherwise they are set to zero.
 739
 740    This corresponds to returning the value represented by PREC lowermost bits
 741    of CST, with the given signedness.  */
 742
 743 double_int
 744 double_int::ext (unsigned prec, bool uns) const
 745 {
 746   if (uns)
 747     return this->zext (prec);
 748   else
 749     return this->sext (prec);
 750 }
 751
 752 /* The same as double_int::ext with UNS = true.  */
 753
 754 double_int
 755 double_int::zext (unsigned prec) const
 756 {
 757   const double_int &cst = *this;
 758   double_int mask = double_int::mask (prec);
 759   double_int r;
 760
 761   r.low = cst.low & mask.low;
 762   r.high = cst.high & mask.high;
 763
 764   return r;
 765 }
 766
 767 /* The same as double_int::ext with UNS = false.  */
 768
 769 double_int
 770 double_int::sext (unsigned prec) const
 771 {
 772   const double_int &cst = *this;
 773   double_int mask = double_int::mask (prec);
 774   double_int r;
 775   unsigned HOST_WIDE_INT snum;
 776
 777   if (prec <= HOST_BITS_PER_WIDE_INT)
 778     snum = cst.low;
 779   else
 780     {
 781       prec -= HOST_BITS_PER_WIDE_INT;
 782       snum = (unsigned HOST_WIDE_INT) cst.high;
 783     }
 784   if (((snum >> (prec - 1)) & 1) == 1)
 785     {
 786       r.low = cst.low | ~mask.low;
 787       r.high = cst.high | ~mask.high;
 788     }
 789   else
 790     {
 791       r.low = cst.low & mask.low;
 792       r.high = cst.high & mask.high;
 793     }
 794
 795   return r;
 796 }
 797
 798 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 799
 800 bool
 801 double_int::fits_shwi () const
 802 {
 803   const double_int &cst = *this;
 804   if (cst.high == 0)
 805     return (HOST_WIDE_INT) cst.low >= 0;
 806   else if (cst.high == -1)
 807     return (HOST_WIDE_INT) cst.low < 0;
 808   else
 809     return false;
 810 }
 811
 812 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 813    unsigned HOST_WIDE_INT if UNS is true.  */
 814
 815 bool
 816 double_int::fits_hwi (bool uns) const
 817 {
 818   if (uns)
 819     return this->fits_uhwi ();
 820   else
 821     return this->fits_shwi ();
 822 }
 823
 824 /* Returns A * B.  */
 825
 826 double_int
 827 double_int::operator * (double_int b) const
 828 {
 829   const double_int &a = *this;
 830   double_int ret;
 831   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 832   return ret;
 833 }
 834
 835 /* Returns A * B. If the operation overflows according to UNSIGNED_P,
 836    *OVERFLOW is set to nonzero.  */
 837
 838 double_int
 839 double_int::mul_with_sign (double_int b, bool unsigned_p, bool *overflow) const
 840 {
 841   const double_int &a = *this;
 842   double_int ret;
 843   *overflow = mul_double_with_sign (a.low, a.high, b.low, b.high,
 844                                     &ret.low, &ret.high, unsigned_p);
 845   return ret;
 846 }
 847
 848 double_int
 849 double_int::wide_mul_with_sign (double_int b, bool unsigned_p,
 850                                 double_int *higher, bool *overflow) const
 851
 852 {
 853   double_int lower;
 854   *overflow = mul_double_wide_with_sign (low, high, b.low, b.high,
 855                                          &lower.low, &lower.high,
 856                                          &higher->low, &higher->high,
 857                                          unsigned_p);
 858   return lower;
 859 }
 860
 861 /* Returns A + B.  */
 862
 863 double_int
 864 double_int::operator + (double_int b) const
 865 {
 866   const double_int &a = *this;
 867   double_int ret;
 868   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 869   return ret;
 870 }
 871
 872 /* Returns A + B. If the operation overflows according to UNSIGNED_P,
 873    *OVERFLOW is set to nonzero.  */
 874
 875 double_int
 876 double_int::add_with_sign (double_int b, bool unsigned_p, bool *overflow) const
 877 {
 878   const double_int &a = *this;
 879   double_int ret;
 880   *overflow = add_double_with_sign (a.low, a.high, b.low, b.high,
 881                                     &ret.low, &ret.high, unsigned_p);
 882   return ret;
 883 }
 884
 885 /* Returns A - B.  */
 886
 887 double_int
 888 double_int::operator - (double_int b) const
 889 {
 890   const double_int &a = *this;
 891   double_int ret;
 892   neg_double (b.low, b.high, &b.low, &b.high);
 893   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 894   return ret;
 895 }
 896
 897 /* Returns A - B. If the operation overflows via inconsistent sign bits,
 898    *OVERFLOW is set to nonzero.  */
 899
 900 double_int
 901 double_int::sub_with_overflow (double_int b, bool *overflow) const
 902 {
 903   double_int ret;
 904   neg_double (b.low, b.high, &ret.low, &ret.high);
 905   add_double (low, high, ret.low, ret.high, &ret.low, &ret.high);
 906   *overflow = OVERFLOW_SUM_SIGN (ret.high, b.high, high);
 907   return ret;
 908 }
 909
 910 /* Returns -A.  */
 911
 912 double_int
 913 double_int::operator - () const
 914 {
 915   const double_int &a = *this;
 916   double_int ret;
 917   neg_double (a.low, a.high, &ret.low, &ret.high);
 918   return ret;
 919 }
 920
 921 double_int
 922 double_int::neg_with_overflow (bool *overflow) const
 923 {
 924   double_int ret;
 925   *overflow = neg_double (low, high, &ret.low, &ret.high);
 926   return ret;
 927 }
 928
 929 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 930    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 931    must be included before tree.h.  The remainder after the division is
 932    stored to MOD.  */
 933
 934 double_int
 935 double_int::divmod_with_overflow (double_int b, bool uns, unsigned code,
 936                                   double_int *mod, bool *overflow) const
 937 {
 938   const double_int &a = *this;
 939   double_int ret;
 940
 941   *overflow = div_and_round_double (code, uns, a.low, a.high,
 942                                     b.low, b.high, &ret.low, &ret.high,
 943                                     &mod->low, &mod->high);
 944   return ret;
 945 }
 946
 947 double_int
 948 double_int::divmod (double_int b, bool uns, unsigned code,
 949                     double_int *mod) const
 950 {
 951   const double_int &a = *this;
 952   double_int ret;
 953
 954   div_and_round_double (code, uns, a.low, a.high,
 955                         b.low, b.high, &ret.low, &ret.high,
 956                         &mod->low, &mod->high);
 957   return ret;
 958 }
 959
 960 /* The same as double_int::divmod with UNS = false.  */
 961
 962 double_int
 963 double_int::sdivmod (double_int b, unsigned code, double_int *mod) const
 964 {
 965   return this->divmod (b, false, code, mod);
 966 }
 967
 968 /* The same as double_int::divmod with UNS = true.  */
 969
 970 double_int
 971 double_int::udivmod (double_int b, unsigned code, double_int *mod) const
 972 {
 973   return this->divmod (b, true, code, mod);
 974 }
 975
 976 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 977    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 978    must be included before tree.h.  */
 979
 980 double_int
 981 double_int::div (double_int b, bool uns, unsigned code) const
 982 {
 983   double_int mod;
 984
 985   return this->divmod (b, uns, code, &mod);
 986 }
 987
 988 /* The same as double_int::div with UNS = false.  */
 989
 990 double_int
 991 double_int::sdiv (double_int b, unsigned code) const
 992 {
 993   return this->div (b, false, code);
 994 }
 995
 996 /* The same as double_int::div with UNS = true.  */
 997
 998 double_int
 999 double_int::udiv (double_int b, unsigned code) const
1000 {
1001   return this->div (b, true, code);
1002 }
1003
1004 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
1005    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
1006    must be included before tree.h.  */
1007
1008 double_int
1009 double_int::mod (double_int b, bool uns, unsigned code) const
1010 {
1011   double_int mod;
1012
1013   this->divmod (b, uns, code, &mod);
1014   return mod;
1015 }
1016
1017 /* The same as double_int::mod with UNS = false.  */
1018
1019 double_int
1020 double_int::smod (double_int b, unsigned code) const
1021 {
1022   return this->mod (b, false, code);
1023 }
1024
1025 /* The same as double_int::mod with UNS = true.  */
1026
1027 double_int
1028 double_int::umod (double_int b, unsigned code) const
1029 {
1030   return this->mod (b, true, code);
1031 }
1032
1033 /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return
1034    the multiple in *MULTIPLE.  Otherwise return FALSE and leave *MULTIPLE
1035    unchanged.  */
1036
1037 bool
1038 double_int::multiple_of (double_int factor,
1039                          bool unsigned_p, double_int *multiple) const
1040 {
1041   double_int remainder;
1042   double_int quotient = this->divmod (factor, unsigned_p,
1043                                            TRUNC_DIV_EXPR, &remainder);
1044   if (remainder.is_zero ())
1045     {
1046       *multiple = quotient;
1047       return true;
1048     }
1049
1050   return false;
1051 }
1052
1053 /* Set BITPOS bit in A.  */
1054 double_int
1055 double_int::set_bit (unsigned bitpos) const
1056 {
1057   double_int a = *this;
1058   if (bitpos < HOST_BITS_PER_WIDE_INT)
1059     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
1060   else
1061     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
1062
1063   return a;
1064 }
1065
1066 /* Count trailing zeros in A.  */
1067 int
1068 double_int::trailing_zeros () const
1069 {
1070   const double_int &a = *this;
1071   unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high;
1072   unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT;
1073   if (!w)
1074     return HOST_BITS_PER_DOUBLE_INT;
1075   bits += ctz_hwi (w);
1076   return bits;
1077 }
1078
1079 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
1080    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
1081    otherwise use logical shift.  */
1082
1083 double_int
1084 double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1085 {
1086   const double_int &a = *this;
1087   double_int ret;
1088   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
1089   return ret;
1090 }
1091
1092 /* Shift A right by COUNT places keeping only PREC bits of result.  Shift
1093    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
1094    otherwise use logical shift.  */
1095
1096 double_int
1097 double_int::rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const
1098 {
1099   const double_int &a = *this;
1100   double_int ret;
1101   lshift_double (a.low, a.high, -count, prec, &ret.low, &ret.high, arith);
1102   return ret;
1103 }
1104
1105 /* Arithmetic shift A left by COUNT places keeping only PREC bits of result.
1106    Shift right if COUNT is negative.  */
1107
1108 double_int
1109 double_int::alshift (HOST_WIDE_INT count, unsigned int prec) const
1110 {
1111   double_int r;
1112   lshift_double (low, high, count, prec, &r.low, &r.high, true);
1113   return r;
1114 }
1115
1116 /* Arithmetic shift A right by COUNT places keeping only PREC bits of result.
1117    Shift left if COUNT is negative.  */
1118
1119 double_int
1120 double_int::arshift (HOST_WIDE_INT count, unsigned int prec) const
1121 {
1122   double_int r;
1123   lshift_double (low, high, -count, prec, &r.low, &r.high, true);
1124   return r;
1125 }
1126
1127 /* Logical shift A left by COUNT places keeping only PREC bits of result.
1128    Shift right if COUNT is negative.  */
1129
1130 double_int
1131 double_int::llshift (HOST_WIDE_INT count, unsigned int prec) const
1132 {
1133   double_int r;
1134   lshift_double (low, high, count, prec, &r.low, &r.high, false);
1135   return r;
1136 }
1137
1138 /* Logical shift A right by COUNT places keeping only PREC bits of result.
1139    Shift left if COUNT is negative.  */
1140
1141 double_int
1142 double_int::lrshift (HOST_WIDE_INT count, unsigned int prec) const
1143 {
1144   double_int r;
1145   lshift_double (low, high, -count, prec, &r.low, &r.high, false);
1146   return r;
1147 }
1148
1149 /* Rotate  A left by COUNT places keeping only PREC bits of result.
1150    Rotate right if COUNT is negative.  */
1151
1152 double_int
1153 double_int::lrotate (HOST_WIDE_INT count, unsigned int prec) const
1154 {
1155   double_int t1, t2;
1156
1157   count %= prec;
1158   if (count < 0)
1159     count += prec;
1160
1161   t1 = this->lshift (count, prec, false);
1162   t2 = this->rshift (prec - count, prec, false);
1163
1164   return t1 | t2;
1165 }
1166
1167 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1168    Rotate right if COUNT is negative.  */
1169
1170 double_int
1171 double_int::rrotate (HOST_WIDE_INT count, unsigned int prec) const
1172 {
1173   double_int t1, t2;
1174
1175   count %= prec;
1176   if (count < 0)
1177     count += prec;
1178
1179   t1 = this->rshift (count, prec, false);
1180   t2 = this->lshift (prec - count, prec, false);
1181
1182   return t1 | t2;
1183 }
1184
1185 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
1186    comparison is given by UNS.  */
1187
1188 int
1189 double_int::cmp (double_int b, bool uns) const
1190 {
1191   if (uns)
1192     return this->ucmp (b);
1193   else
1194     return this->scmp (b);
1195 }
1196
1197 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
1198    and 1 if A > B.  */
1199
1200 int
1201 double_int::ucmp (double_int b) const
1202 {
1203   const double_int &a = *this;
1204   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
1205     return -1;
1206   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
1207     return 1;
1208   if (a.low < b.low)
1209     return -1;
1210   if (a.low > b.low)
1211     return 1;
1212
1213   return 0;
1214 }
1215
1216 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
1217    and 1 if A > B.  */
1218
1219 int
1220 double_int::scmp (double_int b) const
1221 {
1222   const double_int &a = *this;
1223   if (a.high < b.high)
1224     return -1;
1225   if (a.high > b.high)
1226     return 1;
1227   if (a.low < b.low)
1228     return -1;
1229   if (a.low > b.low)
1230     return 1;
1231
1232   return 0;
1233 }
1234
1235 /* Compares two unsigned values A and B for less-than.  */
1236
1237 bool
1238 double_int::ult (double_int b) const
1239 {
1240   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1241     return true;
1242   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1243     return false;
1244   if (low < b.low)
1245     return true;
1246   return false;
1247 }
1248
1249 /* Compares two unsigned values A and B for less-than or equal-to.  */
1250
1251 bool
1252 double_int::ule (double_int b) const
1253 {
1254   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1255     return true;
1256   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1257     return false;
1258   if (low <= b.low)
1259     return true;
1260   return false;
1261 }
1262
1263 /* Compares two unsigned values A and B for greater-than.  */
1264
1265 bool
1266 double_int::ugt (double_int b) const
1267 {
1268   if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high)
1269     return true;
1270   if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high)
1271     return false;
1272   if (low > b.low)
1273     return true;
1274   return false;
1275 }
1276
1277 /* Compares two signed values A and B for less-than.  */
1278
1279 bool
1280 double_int::slt (double_int b) const
1281 {
1282   if (high < b.high)
1283     return true;
1284   if (high > b.high)
1285     return false;
1286   if (low < b.low)
1287     return true;
1288   return false;
1289 }
1290
1291 /* Compares two signed values A and B for less-than or equal-to.  */
1292
1293 bool
1294 double_int::sle (double_int b) const
1295 {
1296   if (high < b.high)
1297     return true;
1298   if (high > b.high)
1299     return false;
1300   if (low <= b.low)
1301     return true;
1302   return false;
1303 }
1304
1305 /* Compares two signed values A and B for greater-than.  */
1306
1307 bool
1308 double_int::sgt (double_int b) const
1309 {
1310   if (high > b.high)
1311     return true;
1312   if (high < b.high)
1313     return false;
1314   if (low > b.low)
1315     return true;
1316   return false;
1317 }
1318
1319
1320 /* Compares two values A and B.  Returns max value.  Signedness of the
1321    comparison is given by UNS.  */
1322
1323 double_int
1324 double_int::max (double_int b, bool uns)
1325 {
1326   return (this->cmp (b, uns) == 1) ? *this : b;
1327 }
1328
1329 /* Compares two signed values A and B.  Returns max value.  */
1330
1331 double_int
1332 double_int::smax (double_int b)
1333 {
1334   return (this->scmp (b) == 1) ? *this : b;
1335 }
1336
1337 /* Compares two unsigned values A and B.  Returns max value.  */
1338
1339 double_int
1340 double_int::umax (double_int b)
1341 {
1342   return (this->ucmp (b) == 1) ? *this : b;
1343 }
1344
1345 /* Compares two values A and B.  Returns mix value.  Signedness of the
1346    comparison is given by UNS.  */
1347
1348 double_int
1349 double_int::min (double_int b, bool uns)
1350 {
1351   return (this->cmp (b, uns) == -1) ? *this : b;
1352 }
1353
1354 /* Compares two signed values A and B.  Returns min value.  */
1355
1356 double_int
1357 double_int::smin (double_int b)
1358 {
1359   return (this->scmp (b) == -1) ? *this : b;
1360 }
1361
1362 /* Compares two unsigned values A and B.  Returns min value.  */
1363
1364 double_int
1365 double_int::umin (double_int b)
1366 {
1367   return (this->ucmp (b) == -1) ? *this : b;
1368 }
1369
1370 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1371
1372 static unsigned
1373 double_int_split_digit (double_int *cst, unsigned base)
1374 {
1375   unsigned HOST_WIDE_INT resl, reml;
1376   HOST_WIDE_INT resh, remh;
1377
1378   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1379                         &resl, &resh, &reml, &remh);
1380   cst->high = resh;
1381   cst->low = resl;
1382
1383   return reml;
1384 }
1385
1386 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1387    otherwise it is signed.  */
1388
1389 void
1390 dump_double_int (FILE *file, double_int cst, bool uns)
1391 {
1392   unsigned digits[100], n;
1393   int i;
1394
1395   if (cst.is_zero ())
1396     {
1397       fprintf (file, "0");
1398       return;
1399     }
1400
1401   if (!uns && cst.is_negative ())
1402     {
1403       fprintf (file, "-");
1404       cst = -cst;
1405     }
1406
1407   for (n = 0; !cst.is_zero (); n++)
1408     digits[n] = double_int_split_digit (&cst, 10);
1409   for (i = n - 1; i >= 0; i--)
1410     fprintf (file, "%u", digits[i]);
1411 }
1412
1413
1414 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1415    otherwise.  */
1416
1417 void
1418 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1419 {
1420   bool negate = false;
1421   unsigned HOST_WIDE_INT vp[2];
1422
1423   if (!uns && val.is_negative ())
1424     {
1425       negate = true;
1426       val = -val;
1427     }
1428
1429   vp[0] = val.low;
1430   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1431   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1432
1433   if (negate)
1434     mpz_neg (result, result);
1435 }
1436
1437 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1438    values of VAL will be wrapped; otherwise, they will be set to the
1439    appropriate minimum or maximum TYPE bound.  */
1440
1441 double_int
1442 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1443 {
1444   unsigned HOST_WIDE_INT *vp;
1445   size_t count, numb;
1446   double_int res;
1447
1448   if (!wrap)
1449     {
1450       mpz_t min, max;
1451
1452       mpz_init (min);
1453       mpz_init (max);
1454       get_type_static_bounds (type, min, max);
1455
1456       if (mpz_cmp (val, min) < 0)
1457         mpz_set (val, min);
1458       else if (mpz_cmp (val, max) > 0)
1459         mpz_set (val, max);
1460
1461       mpz_clear (min);
1462       mpz_clear (max);
1463     }
1464
1465   /* Determine the number of unsigned HOST_WIDE_INT that are required
1466      for representing the value.  The code to calculate count is
1467      extracted from the GMP manual, section "Integer Import and Export":
1468      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1469   numb = 8*sizeof(HOST_WIDE_INT);
1470   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1471   if (count < 2)
1472     count = 2;
1473   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1474
1475   vp[0] = 0;
1476   vp[1] = 0;
1477   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1478
1479   gcc_assert (wrap || count <= 2);
1480
1481   res.low = vp[0];
1482   res.high = (HOST_WIDE_INT) vp[1];
1483
1484   res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1485   if (mpz_sgn (val) < 0)
1486     res = -res;
1487
1488   return res;
1489 }