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