contrib/gcc-8.0/gcc/double-int.c

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