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