gcc/double-int.c

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