gcc/double-int.c

   1 /* Operations with long integers.
   2    Copyright (C) 2006, 2007, 2009, 2010 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"
  24 #include "tree.h"
  25
  26 /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring
  27    overflow.  Suppose A, B and SUM have the same respective signs as A1, B1,
  28    and SUM1.  Then this yields nonzero if overflow occurred during the
  29    addition.
  30
  31    Overflow occurs if A and B have the same sign, but A and SUM differ in
  32    sign.  Use `^' to test whether signs differ, and `< 0' to isolate the
  33    sign.  */
  34 #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)
  35
  36 /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
  37    We do that by representing the two-word integer in 4 words, with only
  38    HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive
  39    number.  The value of the word is LOWPART + HIGHPART * BASE.  */
  40
  41 #define LOWPART(x) \
  42   ((x) & (((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT / 2)) - 1))
  43 #define HIGHPART(x) \
  44   ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2)
  45 #define BASE ((unsigned HOST_WIDE_INT) 1 << HOST_BITS_PER_WIDE_INT / 2)
  46
  47 /* Unpack a two-word integer into 4 words.
  48    LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
  49    WORDS points to the array of HOST_WIDE_INTs.  */
  50
  51 static void
  52 encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
  53 {
  54   words[0] = LOWPART (low);
  55   words[1] = HIGHPART (low);
  56   words[2] = LOWPART (hi);
  57   words[3] = HIGHPART (hi);
  58 }
  59
  60 /* Pack an array of 4 words into a two-word integer.
  61    WORDS points to the array of words.
  62    The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */
  63
  64 static void
  65 decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low,
  66         HOST_WIDE_INT *hi)
  67 {
  68   *low = words[0] + words[1] * BASE;
  69   *hi = words[2] + words[3] * BASE;
  70 }
  71
  72 /* Force the double-word integer L1, H1 to be within the range of the
  73    integer type TYPE.  Stores the properly truncated and sign-extended
  74    double-word integer in *LV, *HV.  Returns true if the operation
  75    overflows, that is, argument and result are different.  */
  76
  77 int
  78 fit_double_type (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
  79                  unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, const_tree type)
  80 {
  81   unsigned HOST_WIDE_INT low0 = l1;
  82   HOST_WIDE_INT high0 = h1;
  83   unsigned int prec = TYPE_PRECISION (type);
  84   int sign_extended_type;
  85
  86   /* Size types *are* sign extended.  */
  87   sign_extended_type = (!TYPE_UNSIGNED (type)
  88                         || (TREE_CODE (type) == INTEGER_TYPE
  89                             && TYPE_IS_SIZETYPE (type)));
  90
  91   /* First clear all bits that are beyond the type's precision.  */
  92   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
  93     ;
  94   else if (prec > HOST_BITS_PER_WIDE_INT)
  95     h1 &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
  96   else
  97     {
  98       h1 = 0;
  99       if (prec < HOST_BITS_PER_WIDE_INT)
 100         l1 &= ~((HOST_WIDE_INT) (-1) << prec);
 101     }
 102
 103   /* Then do sign extension if necessary.  */
 104   if (!sign_extended_type)
 105     /* No sign extension */;
 106   else if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 107     /* Correct width already.  */;
 108   else if (prec > HOST_BITS_PER_WIDE_INT)
 109     {
 110       /* Sign extend top half? */
 111       if (h1 & ((unsigned HOST_WIDE_INT)1
 112                 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
 113         h1 |= (HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT);
 114     }
 115   else if (prec == HOST_BITS_PER_WIDE_INT)
 116     {
 117       if ((HOST_WIDE_INT)l1 < 0)
 118         h1 = -1;
 119     }
 120   else
 121     {
 122       /* Sign extend bottom half? */
 123       if (l1 & ((unsigned HOST_WIDE_INT)1 << (prec - 1)))
 124         {
 125           h1 = -1;
 126           l1 |= (HOST_WIDE_INT)(-1) << prec;
 127         }
 128     }
 129
 130   *lv = l1;
 131   *hv = h1;
 132
 133   /* If the value didn't fit, signal overflow.  */
 134   return l1 != low0 || h1 != high0;
 135 }
 136
 137 /* We force the double-int HIGH:LOW to the range of the type TYPE by
 138    sign or zero extending it.
 139    OVERFLOWABLE indicates if we are interested
 140    in overflow of the value, when >0 we are only interested in signed
 141    overflow, for <0 we are interested in any overflow.  OVERFLOWED
 142    indicates whether overflow has already occurred.  CONST_OVERFLOWED
 143    indicates whether constant overflow has already occurred.  We force
 144    T's value to be within range of T's type (by setting to 0 or 1 all
 145    the bits outside the type's range).  We set TREE_OVERFLOWED if,
 146         OVERFLOWED is nonzero,
 147         or OVERFLOWABLE is >0 and signed overflow occurs
 148         or OVERFLOWABLE is <0 and any overflow occurs
 149    We return a new tree node for the extended double-int.  The node
 150    is shared if no overflow flags are set.  */
 151
 152 tree
 153 force_fit_type_double (tree type, unsigned HOST_WIDE_INT low,
 154                        HOST_WIDE_INT high, int overflowable,
 155                        bool overflowed)
 156 {
 157   int sign_extended_type;
 158   bool overflow;
 159
 160   /* Size types *are* sign extended.  */
 161   sign_extended_type = (!TYPE_UNSIGNED (type)
 162                         || (TREE_CODE (type) == INTEGER_TYPE
 163                             && TYPE_IS_SIZETYPE (type)));
 164
 165   overflow = fit_double_type (low, high, &low, &high, type);
 166
 167   /* If we need to set overflow flags, return a new unshared node.  */
 168   if (overflowed || overflow)
 169     {
 170       if (overflowed
 171           || overflowable < 0
 172           || (overflowable > 0 && sign_extended_type))
 173         {
 174           tree t = make_node (INTEGER_CST);
 175           TREE_INT_CST_LOW (t) = low;
 176           TREE_INT_CST_HIGH (t) = high;
 177           TREE_TYPE (t) = type;
 178           TREE_OVERFLOW (t) = 1;
 179           return t;
 180         }
 181     }
 182
 183   /* Else build a shared node.  */
 184   return build_int_cst_wide (type, low, high);
 185 }
 186
 187 /* Add two doubleword integers with doubleword result.
 188    Return nonzero if the operation overflows according to UNSIGNED_P.
 189    Each argument is given as two `HOST_WIDE_INT' pieces.
 190    One argument is L1 and H1; the other, L2 and H2.
 191    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 192
 193 int
 194 add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 195                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 196                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 197                       bool unsigned_p)
 198 {
 199   unsigned HOST_WIDE_INT l;
 200   HOST_WIDE_INT h;
 201
 202   l = l1 + l2;
 203   h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1
 204                        + (unsigned HOST_WIDE_INT) h2
 205                        + (l < l1));
 206
 207   *lv = l;
 208   *hv = h;
 209
 210   if (unsigned_p)
 211     return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1
 212             || (h == h1
 213                 && l < l1));
 214   else
 215     return OVERFLOW_SUM_SIGN (h1, h2, h);
 216 }
 217
 218 /* Negate a doubleword integer with doubleword result.
 219    Return nonzero if the operation overflows, assuming it's signed.
 220    The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
 221    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 222
 223 int
 224 neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 225             unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv)
 226 {
 227   if (l1 == 0)
 228     {
 229       *lv = 0;
 230       *hv = - h1;
 231       return (*hv & h1) < 0;
 232     }
 233   else
 234     {
 235       *lv = -l1;
 236       *hv = ~h1;
 237       return 0;
 238     }
 239 }
 240
 241 /* Multiply two doubleword integers with doubleword result.
 242    Return nonzero if the operation overflows according to UNSIGNED_P.
 243    Each argument is given as two `HOST_WIDE_INT' pieces.
 244    One argument is L1 and H1; the other, L2 and H2.
 245    The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 246
 247 int
 248 mul_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 249                       unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2,
 250                       unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 251                       bool unsigned_p)
 252 {
 253   HOST_WIDE_INT arg1[4];
 254   HOST_WIDE_INT arg2[4];
 255   HOST_WIDE_INT prod[4 * 2];
 256   unsigned HOST_WIDE_INT carry;
 257   int i, j, k;
 258   unsigned HOST_WIDE_INT toplow, neglow;
 259   HOST_WIDE_INT tophigh, neghigh;
 260
 261   encode (arg1, l1, h1);
 262   encode (arg2, l2, h2);
 263
 264   memset (prod, 0, sizeof prod);
 265
 266   for (i = 0; i < 4; i++)
 267     {
 268       carry = 0;
 269       for (j = 0; j < 4; j++)
 270         {
 271           k = i + j;
 272           /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000.  */
 273           carry += arg1[i] * arg2[j];
 274           /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF.  */
 275           carry += prod[k];
 276           prod[k] = LOWPART (carry);
 277           carry = HIGHPART (carry);
 278         }
 279       prod[i + 4] = carry;
 280     }
 281
 282   decode (prod, lv, hv);
 283   decode (prod + 4, &toplow, &tophigh);
 284
 285   /* Unsigned overflow is immediate.  */
 286   if (unsigned_p)
 287     return (toplow | tophigh) != 0;
 288
 289   /* Check for signed overflow by calculating the signed representation of the
 290      top half of the result; it should agree with the low half's sign bit.  */
 291   if (h1 < 0)
 292     {
 293       neg_double (l2, h2, &neglow, &neghigh);
 294       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 295     }
 296   if (h2 < 0)
 297     {
 298       neg_double (l1, h1, &neglow, &neghigh);
 299       add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
 300     }
 301   return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
 302 }
 303
 304 /* Shift the doubleword integer in L1, H1 left by COUNT places
 305    keeping only PREC bits of result.
 306    Shift right if COUNT is negative.
 307    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 308    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 309
 310 void
 311 lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 312                HOST_WIDE_INT count, unsigned int prec,
 313                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, bool arith)
 314 {
 315   unsigned HOST_WIDE_INT signmask;
 316
 317   if (count < 0)
 318     {
 319       rshift_double (l1, h1, -count, prec, lv, hv, arith);
 320       return;
 321     }
 322
 323   if (SHIFT_COUNT_TRUNCATED)
 324     count %= prec;
 325
 326   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 327     {
 328       /* Shifting by the host word size is undefined according to the
 329          ANSI standard, so we must handle this as a special case.  */
 330       *hv = 0;
 331       *lv = 0;
 332     }
 333   else if (count >= HOST_BITS_PER_WIDE_INT)
 334     {
 335       *hv = l1 << (count - HOST_BITS_PER_WIDE_INT);
 336       *lv = 0;
 337     }
 338   else
 339     {
 340       *hv = (((unsigned HOST_WIDE_INT) h1 << count)
 341              | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1));
 342       *lv = l1 << count;
 343     }
 344
 345   /* Sign extend all bits that are beyond the precision.  */
 346
 347   signmask = -((prec > HOST_BITS_PER_WIDE_INT
 348                 ? ((unsigned HOST_WIDE_INT) *hv
 349                    >> (prec - HOST_BITS_PER_WIDE_INT - 1))
 350                 : (*lv >> (prec - 1))) & 1);
 351
 352   if (prec >= 2 * HOST_BITS_PER_WIDE_INT)
 353     ;
 354   else if (prec >= HOST_BITS_PER_WIDE_INT)
 355     {
 356       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 357       *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT);
 358     }
 359   else
 360     {
 361       *hv = signmask;
 362       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << prec);
 363       *lv |= signmask << prec;
 364     }
 365 }
 366
 367 /* Shift the doubleword integer in L1, H1 right by COUNT places
 368    keeping only PREC bits of result.  Shift left if COUNT is negative.
 369    ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
 370    Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */
 371
 372 void
 373 rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1,
 374                HOST_WIDE_INT count, unsigned int prec,
 375                unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv,
 376                bool arith)
 377 {
 378   unsigned HOST_WIDE_INT signmask;
 379
 380   if (count < 0)
 381     {
 382       lshift_double (l1, h1, -count, prec, lv, hv, arith);
 383       return;
 384     }
 385
 386   signmask = (arith
 387               ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1))
 388               : 0);
 389
 390   if (SHIFT_COUNT_TRUNCATED)
 391     count %= prec;
 392
 393   if (count >= 2 * HOST_BITS_PER_WIDE_INT)
 394     {
 395       /* Shifting by the host word size is undefined according to the
 396          ANSI standard, so we must handle this as a special case.  */
 397       *hv = 0;
 398       *lv = 0;
 399     }
 400   else if (count >= HOST_BITS_PER_WIDE_INT)
 401     {
 402       *hv = 0;
 403       *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT);
 404     }
 405   else
 406     {
 407       *hv = (unsigned HOST_WIDE_INT) h1 >> count;
 408       *lv = ((l1 >> count)
 409              | ((unsigned HOST_WIDE_INT) h1
 410                 << (HOST_BITS_PER_WIDE_INT - count - 1) << 1));
 411     }
 412
 413   /* Zero / sign extend all bits that are beyond the precision.  */
 414
 415   if (count >= (HOST_WIDE_INT)prec)
 416     {
 417       *hv = signmask;
 418       *lv = signmask;
 419     }
 420   else if ((prec - count) >= 2 * HOST_BITS_PER_WIDE_INT)
 421     ;
 422   else if ((prec - count) >= HOST_BITS_PER_WIDE_INT)
 423     {
 424       *hv &= ~((HOST_WIDE_INT) (-1) << (prec - count - HOST_BITS_PER_WIDE_INT));
 425       *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT);
 426     }
 427   else
 428     {
 429       *hv = signmask;
 430       *lv &= ~((unsigned HOST_WIDE_INT) (-1) << (prec - count));
 431       *lv |= signmask << (prec - count);
 432     }
 433 }
 434
 435 /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN
 436    for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
 437    CODE is a tree code for a kind of division, one of
 438    TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR
 439    or EXACT_DIV_EXPR
 440    It controls how the quotient is rounded to an integer.
 441    Return nonzero if the operation overflows.
 442    UNS nonzero says do unsigned division.  */
 443
 444 int
 445 div_and_round_double (unsigned code, int uns,
 446                       /* num == numerator == dividend */
 447                       unsigned HOST_WIDE_INT lnum_orig,
 448                       HOST_WIDE_INT hnum_orig,
 449                       /* den == denominator == divisor */
 450                       unsigned HOST_WIDE_INT lden_orig,
 451                       HOST_WIDE_INT hden_orig,
 452                       unsigned HOST_WIDE_INT *lquo,
 453                       HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem,
 454                       HOST_WIDE_INT *hrem)
 455 {
 456   int quo_neg = 0;
 457   HOST_WIDE_INT num[4 + 1];     /* extra element for scaling.  */
 458   HOST_WIDE_INT den[4], quo[4];
 459   int i, j;
 460   unsigned HOST_WIDE_INT work;
 461   unsigned HOST_WIDE_INT carry = 0;
 462   unsigned HOST_WIDE_INT lnum = lnum_orig;
 463   HOST_WIDE_INT hnum = hnum_orig;
 464   unsigned HOST_WIDE_INT lden = lden_orig;
 465   HOST_WIDE_INT hden = hden_orig;
 466   int overflow = 0;
 467
 468   if (hden == 0 && lden == 0)
 469     overflow = 1, lden = 1;
 470
 471   /* Calculate quotient sign and convert operands to unsigned.  */
 472   if (!uns)
 473     {
 474       if (hnum < 0)
 475         {
 476           quo_neg = ~ quo_neg;
 477           /* (minimum integer) / (-1) is the only overflow case.  */
 478           if (neg_double (lnum, hnum, &lnum, &hnum)
 479               && ((HOST_WIDE_INT) lden & hden) == -1)
 480             overflow = 1;
 481         }
 482       if (hden < 0)
 483         {
 484           quo_neg = ~ quo_neg;
 485           neg_double (lden, hden, &lden, &hden);
 486         }
 487     }
 488
 489   if (hnum == 0 && hden == 0)
 490     {                           /* single precision */
 491       *hquo = *hrem = 0;
 492       /* This unsigned division rounds toward zero.  */
 493       *lquo = lnum / lden;
 494       goto finish_up;
 495     }
 496
 497   if (hnum == 0)
 498     {                           /* trivial case: dividend < divisor */
 499       /* hden != 0 already checked.  */
 500       *hquo = *lquo = 0;
 501       *hrem = hnum;
 502       *lrem = lnum;
 503       goto finish_up;
 504     }
 505
 506   memset (quo, 0, sizeof quo);
 507
 508   memset (num, 0, sizeof num);  /* to zero 9th element */
 509   memset (den, 0, sizeof den);
 510
 511   encode (num, lnum, hnum);
 512   encode (den, lden, hden);
 513
 514   /* Special code for when the divisor < BASE.  */
 515   if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE)
 516     {
 517       /* hnum != 0 already checked.  */
 518       for (i = 4 - 1; i >= 0; i--)
 519         {
 520           work = num[i] + carry * BASE;
 521           quo[i] = work / lden;
 522           carry = work % lden;
 523         }
 524     }
 525   else
 526     {
 527       /* Full double precision division,
 528          with thanks to Don Knuth's "Seminumerical Algorithms".  */
 529       int num_hi_sig, den_hi_sig;
 530       unsigned HOST_WIDE_INT quo_est, scale;
 531
 532       /* Find the highest nonzero divisor digit.  */
 533       for (i = 4 - 1;; i--)
 534         if (den[i] != 0)
 535           {
 536             den_hi_sig = i;
 537             break;
 538           }
 539
 540       /* Insure that the first digit of the divisor is at least BASE/2.
 541          This is required by the quotient digit estimation algorithm.  */
 542
 543       scale = BASE / (den[den_hi_sig] + 1);
 544       if (scale > 1)
 545         {               /* scale divisor and dividend */
 546           carry = 0;
 547           for (i = 0; i <= 4 - 1; i++)
 548             {
 549               work = (num[i] * scale) + carry;
 550               num[i] = LOWPART (work);
 551               carry = HIGHPART (work);
 552             }
 553
 554           num[4] = carry;
 555           carry = 0;
 556           for (i = 0; i <= 4 - 1; i++)
 557             {
 558               work = (den[i] * scale) + carry;
 559               den[i] = LOWPART (work);
 560               carry = HIGHPART (work);
 561               if (den[i] != 0) den_hi_sig = i;
 562             }
 563         }
 564
 565       num_hi_sig = 4;
 566
 567       /* Main loop */
 568       for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--)
 569         {
 570           /* Guess the next quotient digit, quo_est, by dividing the first
 571              two remaining dividend digits by the high order quotient digit.
 572              quo_est is never low and is at most 2 high.  */
 573           unsigned HOST_WIDE_INT tmp;
 574
 575           num_hi_sig = i + den_hi_sig + 1;
 576           work = num[num_hi_sig] * BASE + num[num_hi_sig - 1];
 577           if (num[num_hi_sig] != den[den_hi_sig])
 578             quo_est = work / den[den_hi_sig];
 579           else
 580             quo_est = BASE - 1;
 581
 582           /* Refine quo_est so it's usually correct, and at most one high.  */
 583           tmp = work - quo_est * den[den_hi_sig];
 584           if (tmp < BASE
 585               && (den[den_hi_sig - 1] * quo_est
 586                   > (tmp * BASE + num[num_hi_sig - 2])))
 587             quo_est--;
 588
 589           /* Try QUO_EST as the quotient digit, by multiplying the
 590              divisor by QUO_EST and subtracting from the remaining dividend.
 591              Keep in mind that QUO_EST is the I - 1st digit.  */
 592
 593           carry = 0;
 594           for (j = 0; j <= den_hi_sig; j++)
 595             {
 596               work = quo_est * den[j] + carry;
 597               carry = HIGHPART (work);
 598               work = num[i + j] - LOWPART (work);
 599               num[i + j] = LOWPART (work);
 600               carry += HIGHPART (work) != 0;
 601             }
 602
 603           /* If quo_est was high by one, then num[i] went negative and
 604              we need to correct things.  */
 605           if (num[num_hi_sig] < (HOST_WIDE_INT) carry)
 606             {
 607               quo_est--;
 608               carry = 0;                /* add divisor back in */
 609               for (j = 0; j <= den_hi_sig; j++)
 610                 {
 611                   work = num[i + j] + den[j] + carry;
 612                   carry = HIGHPART (work);
 613                   num[i + j] = LOWPART (work);
 614                 }
 615
 616               num [num_hi_sig] += carry;
 617             }
 618
 619           /* Store the quotient digit.  */
 620           quo[i] = quo_est;
 621         }
 622     }
 623
 624   decode (quo, lquo, hquo);
 625
 626  finish_up:
 627   /* If result is negative, make it so.  */
 628   if (quo_neg)
 629     neg_double (*lquo, *hquo, lquo, hquo);
 630
 631   /* Compute trial remainder:  rem = num - (quo * den)  */
 632   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 633   neg_double (*lrem, *hrem, lrem, hrem);
 634   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 635
 636   switch (code)
 637     {
 638     case TRUNC_DIV_EXPR:
 639     case TRUNC_MOD_EXPR:        /* round toward zero */
 640     case EXACT_DIV_EXPR:        /* for this one, it shouldn't matter */
 641       return overflow;
 642
 643     case FLOOR_DIV_EXPR:
 644     case FLOOR_MOD_EXPR:        /* round toward negative infinity */
 645       if (quo_neg && (*lrem != 0 || *hrem != 0))   /* ratio < 0 && rem != 0 */
 646         {
 647           /* quo = quo - 1;  */
 648           add_double (*lquo, *hquo, (HOST_WIDE_INT) -1, (HOST_WIDE_INT)  -1,
 649                       lquo, hquo);
 650         }
 651       else
 652         return overflow;
 653       break;
 654
 655     case CEIL_DIV_EXPR:
 656     case CEIL_MOD_EXPR:         /* round toward positive infinity */
 657       if (!quo_neg && (*lrem != 0 || *hrem != 0))  /* ratio > 0 && rem != 0 */
 658         {
 659           add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 660                       lquo, hquo);
 661         }
 662       else
 663         return overflow;
 664       break;
 665
 666     case ROUND_DIV_EXPR:
 667     case ROUND_MOD_EXPR:        /* round to closest integer */
 668       {
 669         unsigned HOST_WIDE_INT labs_rem = *lrem;
 670         HOST_WIDE_INT habs_rem = *hrem;
 671         unsigned HOST_WIDE_INT labs_den = lden, ltwice;
 672         HOST_WIDE_INT habs_den = hden, htwice;
 673
 674         /* Get absolute values.  */
 675         if (*hrem < 0)
 676           neg_double (*lrem, *hrem, &labs_rem, &habs_rem);
 677         if (hden < 0)
 678           neg_double (lden, hden, &labs_den, &habs_den);
 679
 680         /* If (2 * abs (lrem) >= abs (lden)), adjust the quotient.  */
 681         mul_double ((HOST_WIDE_INT) 2, (HOST_WIDE_INT) 0,
 682                     labs_rem, habs_rem, &ltwice, &htwice);
 683
 684         if (((unsigned HOST_WIDE_INT) habs_den
 685              < (unsigned HOST_WIDE_INT) htwice)
 686             || (((unsigned HOST_WIDE_INT) habs_den
 687                  == (unsigned HOST_WIDE_INT) htwice)
 688                 && (labs_den <= ltwice)))
 689           {
 690             if (*hquo < 0)
 691               /* quo = quo - 1;  */
 692               add_double (*lquo, *hquo,
 693                           (HOST_WIDE_INT) -1, (HOST_WIDE_INT) -1, lquo, hquo);
 694             else
 695               /* quo = quo + 1; */
 696               add_double (*lquo, *hquo, (HOST_WIDE_INT) 1, (HOST_WIDE_INT) 0,
 697                           lquo, hquo);
 698           }
 699         else
 700           return overflow;
 701       }
 702       break;
 703
 704     default:
 705       gcc_unreachable ();
 706     }
 707
 708   /* Compute true remainder:  rem = num - (quo * den)  */
 709   mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem);
 710   neg_double (*lrem, *hrem, lrem, hrem);
 711   add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem);
 712   return overflow;
 713 }
 714
 715
 716 /* Returns mask for PREC bits.  */
 717
 718 double_int
 719 double_int_mask (unsigned prec)
 720 {
 721   unsigned HOST_WIDE_INT m;
 722   double_int mask;
 723
 724   if (prec > HOST_BITS_PER_WIDE_INT)
 725     {
 726       prec -= HOST_BITS_PER_WIDE_INT;
 727       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 728       mask.high = (HOST_WIDE_INT) m;
 729       mask.low = ALL_ONES;
 730     }
 731   else
 732     {
 733       mask.high = 0;
 734       mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
 735     }
 736
 737   return mask;
 738 }
 739
 740 /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
 741    outside of the precision are set to the sign bit (i.e., the PREC-th one),
 742    otherwise they are set to zero.
 743
 744    This corresponds to returning the value represented by PREC lowermost bits
 745    of CST, with the given signedness.  */
 746
 747 double_int
 748 double_int_ext (double_int cst, unsigned prec, bool uns)
 749 {
 750   if (uns)
 751     return double_int_zext (cst, prec);
 752   else
 753     return double_int_sext (cst, prec);
 754 }
 755
 756 /* The same as double_int_ext with UNS = true.  */
 757
 758 double_int
 759 double_int_zext (double_int cst, unsigned prec)
 760 {
 761   double_int mask = double_int_mask (prec);
 762   double_int r;
 763
 764   r.low = cst.low & mask.low;
 765   r.high = cst.high & mask.high;
 766
 767   return r;
 768 }
 769
 770 /* The same as double_int_ext with UNS = false.  */
 771
 772 double_int
 773 double_int_sext (double_int cst, unsigned prec)
 774 {
 775   double_int mask = double_int_mask (prec);
 776   double_int r;
 777   unsigned HOST_WIDE_INT snum;
 778
 779   if (prec <= HOST_BITS_PER_WIDE_INT)
 780     snum = cst.low;
 781   else
 782     {
 783       prec -= HOST_BITS_PER_WIDE_INT;
 784       snum = (unsigned HOST_WIDE_INT) cst.high;
 785     }
 786   if (((snum >> (prec - 1)) & 1) == 1)
 787     {
 788       r.low = cst.low | ~mask.low;
 789       r.high = cst.high | ~mask.high;
 790     }
 791   else
 792     {
 793       r.low = cst.low & mask.low;
 794       r.high = cst.high & mask.high;
 795     }
 796
 797   return r;
 798 }
 799
 800 /* Returns true if CST fits in signed HOST_WIDE_INT.  */
 801
 802 bool
 803 double_int_fits_in_shwi_p (double_int cst)
 804 {
 805   if (cst.high == 0)
 806     return (HOST_WIDE_INT) cst.low >= 0;
 807   else if (cst.high == -1)
 808     return (HOST_WIDE_INT) cst.low < 0;
 809   else
 810     return false;
 811 }
 812
 813 /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
 814    unsigned HOST_WIDE_INT if UNS is true.  */
 815
 816 bool
 817 double_int_fits_in_hwi_p (double_int cst, bool uns)
 818 {
 819   if (uns)
 820     return double_int_fits_in_uhwi_p (cst);
 821   else
 822     return double_int_fits_in_shwi_p (cst);
 823 }
 824
 825 /* Returns A * B.  */
 826
 827 double_int
 828 double_int_mul (double_int a, double_int b)
 829 {
 830   double_int ret;
 831   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 832   return ret;
 833 }
 834
 835 /* Returns A + B.  */
 836
 837 double_int
 838 double_int_add (double_int a, double_int b)
 839 {
 840   double_int ret;
 841   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
 842   return ret;
 843 }
 844
 845 /* Returns -A.  */
 846
 847 double_int
 848 double_int_neg (double_int a)
 849 {
 850   double_int ret;
 851   neg_double (a.low, a.high, &ret.low, &ret.high);
 852   return ret;
 853 }
 854
 855 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 856    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 857    must be included before tree.h.  The remainder after the division is
 858    stored to MOD.  */
 859
 860 double_int
 861 double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
 862                    double_int *mod)
 863 {
 864   double_int ret;
 865
 866   div_and_round_double (code, uns, a.low, a.high,
 867                         b.low, b.high, &ret.low, &ret.high,
 868                         &mod->low, &mod->high);
 869   return ret;
 870 }
 871
 872 /* The same as double_int_divmod with UNS = false.  */
 873
 874 double_int
 875 double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
 876 {
 877   return double_int_divmod (a, b, false, code, mod);
 878 }
 879
 880 /* The same as double_int_divmod with UNS = true.  */
 881
 882 double_int
 883 double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
 884 {
 885   return double_int_divmod (a, b, true, code, mod);
 886 }
 887
 888 /* Returns A / B (computed as unsigned depending on UNS, and rounded as
 889    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 890    must be included before tree.h.  */
 891
 892 double_int
 893 double_int_div (double_int a, double_int b, bool uns, unsigned code)
 894 {
 895   double_int mod;
 896
 897   return double_int_divmod (a, b, uns, code, &mod);
 898 }
 899
 900 /* The same as double_int_div with UNS = false.  */
 901
 902 double_int
 903 double_int_sdiv (double_int a, double_int b, unsigned code)
 904 {
 905   return double_int_div (a, b, false, code);
 906 }
 907
 908 /* The same as double_int_div with UNS = true.  */
 909
 910 double_int
 911 double_int_udiv (double_int a, double_int b, unsigned code)
 912 {
 913   return double_int_div (a, b, true, code);
 914 }
 915
 916 /* Returns A % B (computed as unsigned depending on UNS, and rounded as
 917    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
 918    must be included before tree.h.  */
 919
 920 double_int
 921 double_int_mod (double_int a, double_int b, bool uns, unsigned code)
 922 {
 923   double_int mod;
 924
 925   double_int_divmod (a, b, uns, code, &mod);
 926   return mod;
 927 }
 928
 929 /* The same as double_int_mod with UNS = false.  */
 930
 931 double_int
 932 double_int_smod (double_int a, double_int b, unsigned code)
 933 {
 934   return double_int_mod (a, b, false, code);
 935 }
 936
 937 /* The same as double_int_mod with UNS = true.  */
 938
 939 double_int
 940 double_int_umod (double_int a, double_int b, unsigned code)
 941 {
 942   return double_int_mod (a, b, true, code);
 943 }
 944
 945 /* Set BITPOS bit in A.  */
 946 double_int
 947 double_int_setbit (double_int a, unsigned bitpos)
 948 {
 949   if (bitpos < HOST_BITS_PER_WIDE_INT)
 950     a.low |= (unsigned HOST_WIDE_INT) 1 << bitpos;
 951   else
 952     a.high |= (HOST_WIDE_INT) 1 <<  (bitpos - HOST_BITS_PER_WIDE_INT);
 953
 954   return a;
 955 }
 956
 957 /* Shift A left by COUNT places keeping only PREC bits of result.  Shift
 958    right if COUNT is negative.  ARITH true specifies arithmetic shifting;
 959    otherwise use logical shift.  */
 960
 961 double_int
 962 double_int_lshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 963 {
 964   double_int ret;
 965   lshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 966   return ret;
 967 }
 968
 969 /* Shift A rigth by COUNT places keeping only PREC bits of result.  Shift
 970    left if COUNT is negative.  ARITH true specifies arithmetic shifting;
 971    otherwise use logical shift.  */
 972
 973 double_int
 974 double_int_rshift (double_int a, HOST_WIDE_INT count, unsigned int prec, bool arith)
 975 {
 976   double_int ret;
 977   rshift_double (a.low, a.high, count, prec, &ret.low, &ret.high, arith);
 978   return ret;
 979 }
 980
 981 /* Rotate  A left by COUNT places keeping only PREC bits of result.
 982    Rotate right if COUNT is negative.  */
 983
 984 double_int
 985 double_int_lrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
 986 {
 987   double_int t1, t2;
 988
 989   count %= prec;
 990   if (count < 0)
 991     count += prec;
 992
 993   t1 = double_int_lshift (a, count, prec, false);
 994   t2 = double_int_rshift (a, prec - count, prec, false);
 995
 996   return double_int_ior (t1, t2);
 997 }
 998
 999 /* Rotate A rigth by COUNT places keeping only PREC bits of result.
1000    Rotate right if COUNT is negative.  */
1001
1002 double_int
1003 double_int_rrotate (double_int a, HOST_WIDE_INT count, unsigned int prec)
1004 {
1005   double_int t1, t2;
1006
1007   count %= prec;
1008   if (count < 0)
1009     count += prec;
1010
1011   t1 = double_int_rshift (a, count, prec, false);
1012   t2 = double_int_lshift (a, prec - count, prec, false);
1013
1014   return double_int_ior (t1, t2);
1015 }
1016
1017 /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
1018    comparison is given by UNS.  */
1019
1020 int
1021 double_int_cmp (double_int a, double_int b, bool uns)
1022 {
1023   if (uns)
1024     return double_int_ucmp (a, b);
1025   else
1026     return double_int_scmp (a, b);
1027 }
1028
1029 /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
1030    and 1 if A > B.  */
1031
1032 int
1033 double_int_ucmp (double_int a, double_int b)
1034 {
1035   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
1036     return -1;
1037   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
1038     return 1;
1039   if (a.low < b.low)
1040     return -1;
1041   if (a.low > b.low)
1042     return 1;
1043
1044   return 0;
1045 }
1046
1047 /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
1048    and 1 if A > B.  */
1049
1050 int
1051 double_int_scmp (double_int a, double_int b)
1052 {
1053   if (a.high < b.high)
1054     return -1;
1055   if (a.high > b.high)
1056     return 1;
1057   if (a.low < b.low)
1058     return -1;
1059   if (a.low > b.low)
1060     return 1;
1061
1062   return 0;
1063 }
1064
1065 /* Compares two values A and B.  Returns max value.  Signedness of the
1066    comparison is given by UNS.  */
1067
1068 double_int
1069 double_int_max (double_int a, double_int b, bool uns)
1070 {
1071   return (double_int_cmp (a, b, uns) == 1) ? a : b;
1072 }
1073
1074 /* Compares two signed values A and B.  Returns max value.  */
1075
1076 double_int double_int_smax (double_int a, double_int b)
1077 {
1078   return (double_int_scmp (a, b) == 1) ? a : b;
1079 }
1080
1081 /* Compares two unsigned values A and B.  Returns max value.  */
1082
1083 double_int double_int_umax (double_int a, double_int b)
1084 {
1085   return (double_int_ucmp (a, b) == 1) ? a : b;
1086 }
1087
1088 /* Compares two values A and B.  Returns mix value.  Signedness of the
1089    comparison is given by UNS.  */
1090
1091 double_int double_int_min (double_int a, double_int b, bool uns)
1092 {
1093   return (double_int_cmp (a, b, uns) == -1) ? a : b;
1094 }
1095
1096 /* Compares two signed values A and B.  Returns min value.  */
1097
1098 double_int double_int_smin (double_int a, double_int b)
1099 {
1100   return (double_int_scmp (a, b) == -1) ? a : b;
1101 }
1102
1103 /* Compares two unsigned values A and B.  Returns min value.  */
1104
1105 double_int double_int_umin (double_int a, double_int b)
1106 {
1107   return (double_int_ucmp (a, b) == -1) ? a : b;
1108 }
1109
1110 /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
1111
1112 static unsigned
1113 double_int_split_digit (double_int *cst, unsigned base)
1114 {
1115   unsigned HOST_WIDE_INT resl, reml;
1116   HOST_WIDE_INT resh, remh;
1117
1118   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
1119                         &resl, &resh, &reml, &remh);
1120   cst->high = resh;
1121   cst->low = resl;
1122
1123   return reml;
1124 }
1125
1126 /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
1127    otherwise it is signed.  */
1128
1129 void
1130 dump_double_int (FILE *file, double_int cst, bool uns)
1131 {
1132   unsigned digits[100], n;
1133   int i;
1134
1135   if (double_int_zero_p (cst))
1136     {
1137       fprintf (file, "0");
1138       return;
1139     }
1140
1141   if (!uns && double_int_negative_p (cst))
1142     {
1143       fprintf (file, "-");
1144       cst = double_int_neg (cst);
1145     }
1146
1147   for (n = 0; !double_int_zero_p (cst); n++)
1148     digits[n] = double_int_split_digit (&cst, 10);
1149   for (i = n - 1; i >= 0; i--)
1150     fprintf (file, "%u", digits[i]);
1151 }
1152
1153
1154 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
1155    otherwise.  */
1156
1157 void
1158 mpz_set_double_int (mpz_t result, double_int val, bool uns)
1159 {
1160   bool negate = false;
1161   unsigned HOST_WIDE_INT vp[2];
1162
1163   if (!uns && double_int_negative_p (val))
1164     {
1165       negate = true;
1166       val = double_int_neg (val);
1167     }
1168
1169   vp[0] = val.low;
1170   vp[1] = (unsigned HOST_WIDE_INT) val.high;
1171   mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
1172
1173   if (negate)
1174     mpz_neg (result, result);
1175 }
1176
1177 /* Returns VAL converted to TYPE.  If WRAP is true, then out-of-range
1178    values of VAL will be wrapped; otherwise, they will be set to the
1179    appropriate minimum or maximum TYPE bound.  */
1180
1181 double_int
1182 mpz_get_double_int (const_tree type, mpz_t val, bool wrap)
1183 {
1184   unsigned HOST_WIDE_INT *vp;
1185   size_t count, numb;
1186   double_int res;
1187
1188   if (!wrap)
1189     {
1190       mpz_t min, max;
1191
1192       mpz_init (min);
1193       mpz_init (max);
1194       get_type_static_bounds (type, min, max);
1195
1196       if (mpz_cmp (val, min) < 0)
1197         mpz_set (val, min);
1198       else if (mpz_cmp (val, max) > 0)
1199         mpz_set (val, max);
1200
1201       mpz_clear (min);
1202       mpz_clear (max);
1203     }
1204
1205   /* Determine the number of unsigned HOST_WIDE_INT that are required
1206      for representing the value.  The code to calculate count is
1207      extracted from the GMP manual, section "Integer Import and Export":
1208      http://gmplib.org/manual/Integer-Import-and-Export.html  */
1209   numb = 8*sizeof(HOST_WIDE_INT);
1210   count = (mpz_sizeinbase (val, 2) + numb-1) / numb;
1211   if (count < 2)
1212     count = 2;
1213   vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof(HOST_WIDE_INT));
1214
1215   vp[0] = 0;
1216   vp[1] = 0;
1217   mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
1218
1219   gcc_assert (wrap || count <= 2);
1220
1221   res.low = vp[0];
1222   res.high = (HOST_WIDE_INT) vp[1];
1223
1224   res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
1225   if (mpz_sgn (val) < 0)
1226     res = double_int_neg (res);
1227
1228   return res;
1229 }