gcc/fixed-value.c

   1 /* Fixed-point arithmetic support.
   2    Copyright (C) 2006, 2007, 2008, 2009 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 #include "toplev.h"
  26
  27 /* Compare two fixed objects for bitwise identity.  */
  28
  29 bool
  30 fixed_identical (const FIXED_VALUE_TYPE *a, const FIXED_VALUE_TYPE *b)
  31 {
  32   return (a->mode == b->mode
  33           && a->data.high == b->data.high
  34           && a->data.low == b->data.low);
  35 }
  36
  37 /* Calculate a hash value.  */
  38
  39 unsigned int
  40 fixed_hash (const FIXED_VALUE_TYPE *f)
  41 {
  42   return (unsigned int) (f->data.low ^ f->data.high);
  43 }
  44
  45 /* Define the enum code for the range of the fixed-point value.  */
  46 enum fixed_value_range_code {
  47   FIXED_OK,             /* The value is within the range.  */
  48   FIXED_UNDERFLOW,      /* The value is less than the minimum.  */
  49   FIXED_GT_MAX_EPS,     /* The value is greater than the maximum, but not equal
  50                            to the maximum plus the epsilon.  */
  51   FIXED_MAX_EPS         /* The value equals the maximum plus the epsilon.  */
  52 };
  53
  54 /* Check REAL_VALUE against the range of the fixed-point mode.
  55    Return FIXED_OK, if it is within the range.
  56           FIXED_UNDERFLOW, if it is less than the minimum.
  57           FIXED_GT_MAX_EPS, if it is greater than the maximum, but not equal to
  58             the maximum plus the epsilon.
  59           FIXED_MAX_EPS, if it is equal to the maximum plus the epsilon.  */
  60
  61 static enum fixed_value_range_code
  62 check_real_for_fixed_mode (REAL_VALUE_TYPE *real_value, enum machine_mode mode)
  63 {
  64   REAL_VALUE_TYPE max_value, min_value, epsilon_value;
  65
  66   real_2expN (&max_value, GET_MODE_IBIT (mode), mode);
  67   real_2expN (&epsilon_value, -GET_MODE_FBIT (mode), mode);
  68
  69   if (SIGNED_FIXED_POINT_MODE_P (mode))
  70     min_value = real_value_negate (&max_value);
  71   else
  72     real_from_string (&min_value, "0.0");
  73
  74   if (real_compare (LT_EXPR, real_value, &min_value))
  75     return FIXED_UNDERFLOW;
  76   if (real_compare (EQ_EXPR, real_value, &max_value))
  77     return FIXED_MAX_EPS;
  78   real_arithmetic (&max_value, MINUS_EXPR, &max_value, &epsilon_value);
  79   if (real_compare (GT_EXPR, real_value, &max_value))
  80     return FIXED_GT_MAX_EPS;
  81   return FIXED_OK;
  82 }
  83
  84 /* Initialize from a decimal or hexadecimal string.  */
  85
  86 void
  87 fixed_from_string (FIXED_VALUE_TYPE *f, const char *str, enum machine_mode mode)
  88 {
  89   REAL_VALUE_TYPE real_value, fixed_value, base_value;
  90   unsigned int fbit;
  91   enum fixed_value_range_code temp;
  92
  93   f->mode = mode;
  94   fbit = GET_MODE_FBIT (mode);
  95
  96   real_from_string (&real_value, str);
  97   temp = check_real_for_fixed_mode (&real_value, f->mode);
  98   /* We don't want to warn the case when the _Fract value is 1.0.  */
  99   if (temp == FIXED_UNDERFLOW
 100       || temp == FIXED_GT_MAX_EPS
 101       || (temp == FIXED_MAX_EPS && ALL_ACCUM_MODE_P (f->mode)))
 102     warning (OPT_Woverflow,
 103              "large fixed-point constant implicitly truncated to fixed-point type");
 104   real_2expN (&base_value, fbit, mode);
 105   real_arithmetic (&fixed_value, MULT_EXPR, &real_value, &base_value);
 106   real_to_integer2 ((HOST_WIDE_INT *)&f->data.low, &f->data.high,
 107                     &fixed_value);
 108
 109   if (temp == FIXED_MAX_EPS && ALL_FRACT_MODE_P (f->mode))
 110     {
 111       /* From the spec, we need to evaluate 1 to the maximal value.  */
 112       f->data.low = -1;
 113       f->data.high = -1;
 114       f->data = double_int_ext (f->data,
 115                                 GET_MODE_FBIT (f->mode)
 116                                 + GET_MODE_IBIT (f->mode), 1);
 117     }
 118   else
 119     f->data = double_int_ext (f->data,
 120                               SIGNED_FIXED_POINT_MODE_P (f->mode)
 121                               + GET_MODE_FBIT (f->mode)
 122                               + GET_MODE_IBIT (f->mode),
 123                               UNSIGNED_FIXED_POINT_MODE_P (f->mode));
 124 }
 125
 126 /* Render F as a decimal floating point constant.  */
 127
 128 void
 129 fixed_to_decimal (char *str, const FIXED_VALUE_TYPE *f_orig,
 130                   size_t buf_size)
 131 {
 132   REAL_VALUE_TYPE real_value, base_value, fixed_value;
 133
 134   real_2expN (&base_value, GET_MODE_FBIT (f_orig->mode), f_orig->mode);
 135   real_from_integer (&real_value, VOIDmode, f_orig->data.low, f_orig->data.high,
 136                      UNSIGNED_FIXED_POINT_MODE_P (f_orig->mode));
 137   real_arithmetic (&fixed_value, RDIV_EXPR, &real_value, &base_value);
 138   real_to_decimal (str, &fixed_value, buf_size, 0, 1);
 139 }
 140
 141 /* If SAT_P, saturate A to the maximum or the minimum, and save to *F based on
 142    the machine mode MODE.
 143    Do not modify *F otherwise.
 144    This function assumes the width of double_int is greater than the width
 145    of the fixed-point value (the sum of a possible sign bit, possible ibits,
 146    and fbits).
 147    Return true, if !SAT_P and overflow.  */
 148
 149 static bool
 150 fixed_saturate1 (enum machine_mode mode, double_int a, double_int *f,
 151                  bool sat_p)
 152 {
 153   bool overflow_p = false;
 154   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (mode);
 155   int i_f_bits = GET_MODE_IBIT (mode) + GET_MODE_FBIT (mode);
 156
 157   if (unsigned_p) /* Unsigned type.  */
 158     {
 159       double_int max;
 160       max.low = -1;
 161       max.high = -1;
 162       max = double_int_ext (max, i_f_bits, 1);
 163       if (double_int_cmp (a, max, 1) == 1)
 164         {
 165           if (sat_p)
 166             *f = max;
 167           else
 168             overflow_p = true;
 169         }
 170     }
 171   else /* Signed type.  */
 172     {
 173       double_int max, min;
 174       max.high = -1;
 175       max.low = -1;
 176       max = double_int_ext (max, i_f_bits, 1);
 177       min.high = 0;
 178       min.low = 1;
 179       lshift_double (min.low, min.high, i_f_bits,
 180                      2 * HOST_BITS_PER_WIDE_INT,
 181                      &min.low, &min.high, 1);
 182       min = double_int_ext (min, 1 + i_f_bits, 0);
 183       if (double_int_cmp (a, max, 0) == 1)
 184         {
 185           if (sat_p)
 186             *f = max;
 187           else
 188             overflow_p = true;
 189         }
 190       else if (double_int_cmp (a, min, 0) == -1)
 191         {
 192           if (sat_p)
 193             *f = min;
 194           else
 195             overflow_p = true;
 196         }
 197     }
 198   return overflow_p;
 199 }
 200
 201 /* If SAT_P, saturate {A_HIGH, A_LOW} to the maximum or the minimum, and
 202    save to *F based on the machine mode MODE.
 203    Do not modify *F otherwise.
 204    This function assumes the width of two double_int is greater than the width
 205    of the fixed-point value (the sum of a possible sign bit, possible ibits,
 206    and fbits).
 207    Return true, if !SAT_P and overflow.  */
 208
 209 static bool
 210 fixed_saturate2 (enum machine_mode mode, double_int a_high, double_int a_low,
 211                  double_int *f, bool sat_p)
 212 {
 213   bool overflow_p = false;
 214   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (mode);
 215   int i_f_bits = GET_MODE_IBIT (mode) + GET_MODE_FBIT (mode);
 216
 217   if (unsigned_p) /* Unsigned type.  */
 218     {
 219       double_int max_r, max_s;
 220       max_r.high = 0;
 221       max_r.low = 0;
 222       max_s.high = -1;
 223       max_s.low = -1;
 224       max_s = double_int_ext (max_s, i_f_bits, 1);
 225       if (double_int_cmp (a_high, max_r, 1) == 1
 226           || (double_int_equal_p (a_high, max_r) &&
 227               double_int_cmp (a_low, max_s, 1) == 1))
 228         {
 229           if (sat_p)
 230             *f = max_s;
 231           else
 232             overflow_p = true;
 233         }
 234     }
 235   else /* Signed type.  */
 236     {
 237       double_int max_r, max_s, min_r, min_s;
 238       max_r.high = 0;
 239       max_r.low = 0;
 240       max_s.high = -1;
 241       max_s.low = -1;
 242       max_s = double_int_ext (max_s, i_f_bits, 1);
 243       min_r.high = -1;
 244       min_r.low = -1;
 245       min_s.high = 0;
 246       min_s.low = 1;
 247       lshift_double (min_s.low, min_s.high, i_f_bits,
 248                      2 * HOST_BITS_PER_WIDE_INT,
 249                      &min_s.low, &min_s.high, 1);
 250       min_s = double_int_ext (min_s, 1 + i_f_bits, 0);
 251       if (double_int_cmp (a_high, max_r, 0) == 1
 252           || (double_int_equal_p (a_high, max_r) &&
 253               double_int_cmp (a_low, max_s, 1) == 1))
 254         {
 255           if (sat_p)
 256             *f = max_s;
 257           else
 258             overflow_p = true;
 259         }
 260       else if (double_int_cmp (a_high, min_r, 0) == -1
 261                || (double_int_equal_p (a_high, min_r) &&
 262                    double_int_cmp (a_low, min_s, 1) == -1))
 263         {
 264           if (sat_p)
 265             *f = min_s;
 266           else
 267             overflow_p = true;
 268         }
 269     }
 270   return overflow_p;
 271 }
 272
 273 /* Return the sign bit based on I_F_BITS.  */
 274
 275 static inline int
 276 get_fixed_sign_bit (double_int a, int i_f_bits)
 277 {
 278   if (i_f_bits < HOST_BITS_PER_WIDE_INT)
 279     return (a.low >> i_f_bits) & 1;
 280   else
 281     return (a.high >> (i_f_bits - HOST_BITS_PER_WIDE_INT)) & 1;
 282 }
 283
 284 /* Calculate F = A + (SUBTRACT_P ? -B : B).
 285    If SAT_P, saturate the result to the max or the min.
 286    Return true, if !SAT_P and overflow.  */
 287
 288 static bool
 289 do_fixed_add (FIXED_VALUE_TYPE *f, const FIXED_VALUE_TYPE *a,
 290               const FIXED_VALUE_TYPE *b, bool subtract_p, bool sat_p)
 291 {
 292   bool overflow_p = false;
 293   bool unsigned_p;
 294   double_int temp;
 295   int i_f_bits;
 296
 297   /* This was a conditional expression but it triggered a bug in
 298      Sun C 5.5.  */
 299   if (subtract_p)
 300     temp = double_int_neg (b->data);
 301   else
 302     temp = b->data;
 303
 304   unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (a->mode);
 305   i_f_bits = GET_MODE_IBIT (a->mode) + GET_MODE_FBIT (a->mode);
 306   f->mode = a->mode;
 307   f->data = double_int_add (a->data, temp);
 308   if (unsigned_p) /* Unsigned type.  */
 309     {
 310       if (subtract_p) /* Unsigned subtraction.  */
 311         {
 312           if (double_int_cmp (a->data, b->data, 1) == -1)
 313             {
 314               if (sat_p)
 315                 {
 316                   f->data.high = 0;
 317                   f->data.low = 0;
 318                  }
 319               else
 320                 overflow_p = true;
 321             }
 322         }
 323       else /* Unsigned addition.  */
 324         {
 325           f->data = double_int_ext (f->data, i_f_bits, 1);
 326           if (double_int_cmp (f->data, a->data, 1) == -1
 327               || double_int_cmp (f->data, b->data, 1) == -1)
 328             {
 329               if (sat_p)
 330                 {
 331                   f->data.high = -1;
 332                   f->data.low = -1;
 333                 }
 334               else
 335                 overflow_p = true;
 336             }
 337         }
 338     }
 339   else /* Signed type.  */
 340     {
 341       if ((!subtract_p
 342            && (get_fixed_sign_bit (a->data, i_f_bits)
 343                == get_fixed_sign_bit (b->data, i_f_bits))
 344            && (get_fixed_sign_bit (a->data, i_f_bits)
 345                != get_fixed_sign_bit (f->data, i_f_bits)))
 346           || (subtract_p
 347               && (get_fixed_sign_bit (a->data, i_f_bits)
 348                   != get_fixed_sign_bit (b->data, i_f_bits))
 349               && (get_fixed_sign_bit (a->data, i_f_bits)
 350                   != get_fixed_sign_bit (f->data, i_f_bits))))
 351         {
 352           if (sat_p)
 353             {
 354               f->data.low = 1;
 355               f->data.high = 0;
 356               lshift_double (f->data.low, f->data.high, i_f_bits,
 357                              2 * HOST_BITS_PER_WIDE_INT,
 358                              &f->data.low, &f->data.high, 1);
 359               if (get_fixed_sign_bit (a->data, i_f_bits) == 0)
 360                 {
 361                   double_int one;
 362                   one.low = 1;
 363                   one.high = 0;
 364                   f->data = double_int_add (f->data, double_int_neg (one));
 365                 }
 366             }
 367           else
 368             overflow_p = true;
 369         }
 370     }
 371   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
 372   return overflow_p;
 373 }
 374
 375 /* Calculate F = A * B.
 376    If SAT_P, saturate the result to the max or the min.
 377    Return true, if !SAT_P and overflow.  */
 378
 379 static bool
 380 do_fixed_multiply (FIXED_VALUE_TYPE *f, const FIXED_VALUE_TYPE *a,
 381                    const FIXED_VALUE_TYPE *b, bool sat_p)
 382 {
 383   bool overflow_p = false;
 384   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (a->mode);
 385   int i_f_bits = GET_MODE_IBIT (a->mode) + GET_MODE_FBIT (a->mode);
 386   f->mode = a->mode;
 387   if (GET_MODE_PRECISION (f->mode) <= HOST_BITS_PER_WIDE_INT)
 388     {
 389       f->data = double_int_mul (a->data, b->data);
 390       lshift_double (f->data.low, f->data.high,
 391                      (-GET_MODE_FBIT (f->mode)),
 392                      2 * HOST_BITS_PER_WIDE_INT,
 393                      &f->data.low, &f->data.high, !unsigned_p);
 394       overflow_p = fixed_saturate1 (f->mode, f->data, &f->data, sat_p);
 395     }
 396   else
 397     {
 398       /* The result of multiplication expands to two double_int.  */
 399       double_int a_high, a_low, b_high, b_low;
 400       double_int high_high, high_low, low_high, low_low;
 401       double_int r, s, temp1, temp2;
 402       int carry = 0;
 403
 404       /* Decompose a and b to four double_int.  */
 405       a_high.low = a->data.high;
 406       a_high.high = 0;
 407       a_low.low = a->data.low;
 408       a_low.high = 0;
 409       b_high.low = b->data.high;
 410       b_high.high = 0;
 411       b_low.low = b->data.low;
 412       b_low.high = 0;
 413
 414       /* Perform four multiplications.  */
 415       low_low = double_int_mul (a_low, b_low);
 416       low_high = double_int_mul (a_low, b_high);
 417       high_low = double_int_mul (a_high, b_low);
 418       high_high = double_int_mul (a_high, b_high);
 419
 420       /* Accumulate four results to {r, s}.  */
 421       temp1.high = high_low.low;
 422       temp1.low = 0;
 423       s = double_int_add (low_low, temp1);
 424       if (double_int_cmp (s, low_low, 1) == -1
 425           || double_int_cmp (s, temp1, 1) == -1)
 426         carry ++; /* Carry */
 427       temp1.high = s.high;
 428       temp1.low = s.low;
 429       temp2.high = low_high.low;
 430       temp2.low = 0;
 431       s = double_int_add (temp1, temp2);
 432       if (double_int_cmp (s, temp1, 1) == -1
 433           || double_int_cmp (s, temp2, 1) == -1)
 434         carry ++; /* Carry */
 435
 436       temp1.low = high_low.high;
 437       temp1.high = 0;
 438       r = double_int_add (high_high, temp1);
 439       temp1.low = low_high.high;
 440       temp1.high = 0;
 441       r = double_int_add (r, temp1);
 442       temp1.low = carry;
 443       temp1.high = 0;
 444       r = double_int_add (r, temp1);
 445
 446       /* We need to add neg(b) to r, if a < 0.  */
 447       if (!unsigned_p && a->data.high < 0)
 448         r = double_int_add (r, double_int_neg (b->data));
 449       /* We need to add neg(a) to r, if b < 0.  */
 450       if (!unsigned_p && b->data.high < 0)
 451         r = double_int_add (r, double_int_neg (a->data));
 452
 453       /* Shift right the result by FBIT.  */
 454       if (GET_MODE_FBIT (f->mode) == 2 * HOST_BITS_PER_WIDE_INT)
 455         {
 456           s.low = r.low;
 457           s.high = r.high;
 458           if (unsigned_p)
 459             {
 460               r.low = 0;
 461               r.high = 0;
 462             }
 463           else
 464             {
 465               r.low = -1;
 466               r.high = -1;
 467             }
 468           f->data.low = s.low;
 469           f->data.high = s.high;
 470         }
 471       else
 472         {
 473           lshift_double (s.low, s.high,
 474                          (-GET_MODE_FBIT (f->mode)),
 475                          2 * HOST_BITS_PER_WIDE_INT,
 476                          &s.low, &s.high, 0);
 477           lshift_double (r.low, r.high,
 478                          (2 * HOST_BITS_PER_WIDE_INT
 479                           - GET_MODE_FBIT (f->mode)),
 480                          2 * HOST_BITS_PER_WIDE_INT,
 481                          &f->data.low, &f->data.high, 0);
 482           f->data.low = f->data.low | s.low;
 483           f->data.high = f->data.high | s.high;
 484           s.low = f->data.low;
 485           s.high = f->data.high;
 486           lshift_double (r.low, r.high,
 487                          (-GET_MODE_FBIT (f->mode)),
 488                          2 * HOST_BITS_PER_WIDE_INT,
 489                          &r.low, &r.high, !unsigned_p);
 490         }
 491
 492       overflow_p = fixed_saturate2 (f->mode, r, s, &f->data, sat_p);
 493     }
 494
 495   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
 496   return overflow_p;
 497 }
 498
 499 /* Calculate F = A / B.
 500    If SAT_P, saturate the result to the max or the min.
 501    Return true, if !SAT_P and overflow.  */
 502
 503 static bool
 504 do_fixed_divide (FIXED_VALUE_TYPE *f, const FIXED_VALUE_TYPE *a,
 505                  const FIXED_VALUE_TYPE *b, bool sat_p)
 506 {
 507   bool overflow_p = false;
 508   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (a->mode);
 509   int i_f_bits = GET_MODE_IBIT (a->mode) + GET_MODE_FBIT (a->mode);
 510   f->mode = a->mode;
 511   if (GET_MODE_PRECISION (f->mode) <= HOST_BITS_PER_WIDE_INT)
 512     {
 513       lshift_double (a->data.low, a->data.high,
 514                      GET_MODE_FBIT (f->mode),
 515                      2 * HOST_BITS_PER_WIDE_INT,
 516                      &f->data.low, &f->data.high, !unsigned_p);
 517       f->data = double_int_div (f->data, b->data, unsigned_p, TRUNC_DIV_EXPR);
 518       overflow_p = fixed_saturate1 (f->mode, f->data, &f->data, sat_p);
 519     }
 520   else
 521     {
 522       double_int pos_a, pos_b, r, s;
 523       double_int quo_r, quo_s, mod, temp;
 524       int num_of_neg = 0;
 525       int i;
 526
 527       /* If a < 0, negate a.  */
 528       if (!unsigned_p && a->data.high < 0)
 529         {
 530           pos_a = double_int_neg (a->data);
 531           num_of_neg ++;
 532         }
 533       else
 534         pos_a = a->data;
 535
 536       /* If b < 0, negate b.  */
 537       if (!unsigned_p && b->data.high < 0)
 538         {
 539           pos_b = double_int_neg (b->data);
 540           num_of_neg ++;
 541         }
 542       else
 543         pos_b = b->data;
 544
 545       /* Left shift pos_a to {r, s} by FBIT.  */
 546       if (GET_MODE_FBIT (f->mode) == 2 * HOST_BITS_PER_WIDE_INT)
 547         {
 548           r = pos_a;
 549           s.high = 0;
 550           s.low = 0;
 551         }
 552       else
 553         {
 554           lshift_double (pos_a.low, pos_a.high,
 555                          GET_MODE_FBIT (f->mode),
 556                          2 * HOST_BITS_PER_WIDE_INT,
 557                          &s.low, &s.high, 0);
 558           lshift_double (pos_a.low, pos_a.high,
 559                          - (2 * HOST_BITS_PER_WIDE_INT
 560                             - GET_MODE_FBIT (f->mode)),
 561                          2 * HOST_BITS_PER_WIDE_INT,
 562                          &r.low, &r.high, 0);
 563         }
 564
 565       /* Divide r by pos_b to quo_r.  The remainder is in mod.  */
 566       div_and_round_double (TRUNC_DIV_EXPR, 1, r.low, r.high, pos_b.low,
 567                             pos_b.high, &quo_r.low, &quo_r.high, &mod.low,
 568                             &mod.high);
 569
 570       quo_s.high = 0;
 571       quo_s.low = 0;
 572
 573       for (i = 0; i < 2 * HOST_BITS_PER_WIDE_INT; i++)
 574         {
 575           /* Record the leftmost bit of mod.  */
 576           int leftmost_mod = (mod.high < 0);
 577
 578           /* Shift left mod by 1 bit.  */
 579           lshift_double (mod.low, mod.high, 1, 2 * HOST_BITS_PER_WIDE_INT,
 580                          &mod.low, &mod.high, 0);
 581
 582           /* Test the leftmost bit of s to add to mod.  */
 583           if (s.high < 0)
 584             mod.low += 1;
 585
 586           /* Shift left quo_s by 1 bit.  */
 587           lshift_double (quo_s.low, quo_s.high, 1, 2 * HOST_BITS_PER_WIDE_INT,
 588                          &quo_s.low, &quo_s.high, 0);
 589
 590           /* Try to calculate (mod - pos_b).  */
 591           temp = double_int_add (mod, double_int_neg (pos_b));
 592
 593           if (leftmost_mod == 1 || double_int_cmp (mod, pos_b, 1) != -1)
 594             {
 595               quo_s.low += 1;
 596               mod = temp;
 597             }
 598
 599           /* Shift left s by 1 bit.  */
 600           lshift_double (s.low, s.high, 1, 2 * HOST_BITS_PER_WIDE_INT,
 601                          &s.low, &s.high, 0);
 602
 603         }
 604
 605       if (num_of_neg == 1)
 606         {
 607           quo_s = double_int_neg (quo_s);
 608           if (quo_s.high == 0 && quo_s.low == 0)
 609             quo_r = double_int_neg (quo_r);
 610           else
 611             {
 612               quo_r.low = ~quo_r.low;
 613               quo_r.high = ~quo_r.high;
 614             }
 615         }
 616
 617       f->data = quo_s;
 618       overflow_p = fixed_saturate2 (f->mode, quo_r, quo_s, &f->data, sat_p);
 619     }
 620
 621   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
 622   return overflow_p;
 623 }
 624
 625 /* Calculate F = A << B if LEFT_P.  Otherwise, F = A >> B.
 626    If SAT_P, saturate the result to the max or the min.
 627    Return true, if !SAT_P and overflow.  */
 628
 629 static bool
 630 do_fixed_shift (FIXED_VALUE_TYPE *f, const FIXED_VALUE_TYPE *a,
 631               const FIXED_VALUE_TYPE *b, bool left_p, bool sat_p)
 632 {
 633   bool overflow_p = false;
 634   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (a->mode);
 635   int i_f_bits = GET_MODE_IBIT (a->mode) + GET_MODE_FBIT (a->mode);
 636   f->mode = a->mode;
 637
 638   if (b->data.low == 0)
 639     {
 640       f->data = a->data;
 641       return overflow_p;
 642     }
 643
 644   if (GET_MODE_PRECISION (f->mode) <= HOST_BITS_PER_WIDE_INT || (!left_p))
 645     {
 646       lshift_double (a->data.low, a->data.high,
 647                      left_p ? b->data.low : (-b->data.low),
 648                      2 * HOST_BITS_PER_WIDE_INT,
 649                      &f->data.low, &f->data.high, !unsigned_p);
 650       if (left_p) /* Only left shift saturates.  */
 651         overflow_p = fixed_saturate1 (f->mode, f->data, &f->data, sat_p);
 652     }
 653   else /* We need two double_int to store the left-shift result.  */
 654     {
 655       double_int temp_high, temp_low;
 656       if (b->data.low == 2 * HOST_BITS_PER_WIDE_INT)
 657         {
 658           temp_high = a->data;
 659           temp_low.high = 0;
 660           temp_low.low = 0;
 661         }
 662       else
 663         {
 664           lshift_double (a->data.low, a->data.high,
 665                          b->data.low,
 666                          2 * HOST_BITS_PER_WIDE_INT,
 667                          &temp_low.low, &temp_low.high, !unsigned_p);
 668           /* Logical shift right to temp_high.  */
 669           lshift_double (a->data.low, a->data.high,
 670                          b->data.low - 2 * HOST_BITS_PER_WIDE_INT,
 671                          2 * HOST_BITS_PER_WIDE_INT,
 672                          &temp_high.low, &temp_high.high, 0);
 673         }
 674       if (!unsigned_p && a->data.high < 0) /* Signed-extend temp_high.  */
 675         temp_high = double_int_ext (temp_high, b->data.low, unsigned_p);
 676       f->data = temp_low;
 677       overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low, &f->data,
 678                                     sat_p);
 679     }
 680   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
 681   return overflow_p;
 682 }
 683
 684 /* Calculate F = -A.
 685    If SAT_P, saturate the result to the max or the min.
 686    Return true, if !SAT_P and overflow.  */
 687
 688 static bool
 689 do_fixed_neg (FIXED_VALUE_TYPE *f, const FIXED_VALUE_TYPE *a, bool sat_p)
 690 {
 691   bool overflow_p = false;
 692   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (a->mode);
 693   int i_f_bits = GET_MODE_IBIT (a->mode) + GET_MODE_FBIT (a->mode);
 694   f->mode = a->mode;
 695   f->data = double_int_neg (a->data);
 696   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
 697
 698   if (unsigned_p) /* Unsigned type.  */
 699     {
 700       if (f->data.low != 0 || f->data.high != 0)
 701         {
 702           if (sat_p)
 703             {
 704               f->data.low = 0;
 705               f->data.high = 0;
 706             }
 707           else
 708             overflow_p = true;
 709         }
 710     }
 711   else /* Signed type.  */
 712     {
 713       if (!(f->data.high == 0 && f->data.low == 0)
 714           && f->data.high == a->data.high && f->data.low == a->data.low )
 715         {
 716           if (sat_p)
 717             {
 718               /* Saturate to the maximum by subtracting f->data by one.  */
 719               f->data.low = -1;
 720               f->data.high = -1;
 721               f->data = double_int_ext (f->data, i_f_bits, 1);
 722             }
 723           else
 724             overflow_p = true;
 725         }
 726     }
 727   return overflow_p;
 728 }
 729
 730 /* Perform the binary or unary operation described by CODE.
 731    Note that OP0 and OP1 must have the same mode for binary operators.
 732    For a unary operation, leave OP1 NULL.
 733    Return true, if !SAT_P and overflow.  */
 734
 735 bool
 736 fixed_arithmetic (FIXED_VALUE_TYPE *f, int icode, const FIXED_VALUE_TYPE *op0,
 737                   const FIXED_VALUE_TYPE *op1, bool sat_p)
 738 {
 739   switch (icode)
 740     {
 741     case NEGATE_EXPR:
 742       return do_fixed_neg (f, op0, sat_p);
 743       break;
 744
 745     case PLUS_EXPR:
 746       gcc_assert (op0->mode == op1->mode);
 747       return do_fixed_add (f, op0, op1, false, sat_p);
 748       break;
 749
 750     case MINUS_EXPR:
 751       gcc_assert (op0->mode == op1->mode);
 752       return do_fixed_add (f, op0, op1, true, sat_p);
 753       break;
 754
 755     case MULT_EXPR:
 756       gcc_assert (op0->mode == op1->mode);
 757       return do_fixed_multiply (f, op0, op1, sat_p);
 758       break;
 759
 760     case TRUNC_DIV_EXPR:
 761       gcc_assert (op0->mode == op1->mode);
 762       return do_fixed_divide (f, op0, op1, sat_p);
 763       break;
 764
 765     case LSHIFT_EXPR:
 766       return do_fixed_shift (f, op0, op1, true, sat_p);
 767       break;
 768
 769     case RSHIFT_EXPR:
 770       return do_fixed_shift (f, op0, op1, false, sat_p);
 771       break;
 772
 773     default:
 774       gcc_unreachable ();
 775     }
 776   return false;
 777 }
 778
 779 /* Compare fixed-point values by tree_code.
 780    Note that OP0 and OP1 must have the same mode.  */
 781
 782 bool
 783 fixed_compare (int icode, const FIXED_VALUE_TYPE *op0,
 784                const FIXED_VALUE_TYPE *op1)
 785 {
 786   enum tree_code code = (enum tree_code) icode;
 787   gcc_assert (op0->mode == op1->mode);
 788
 789   switch (code)
 790     {
 791     case NE_EXPR:
 792       return !double_int_equal_p (op0->data, op1->data);
 793
 794     case EQ_EXPR:
 795       return double_int_equal_p (op0->data, op1->data);
 796
 797     case LT_EXPR:
 798       return double_int_cmp (op0->data, op1->data,
 799                              UNSIGNED_FIXED_POINT_MODE_P (op0->mode)) == -1;
 800
 801     case LE_EXPR:
 802       return double_int_cmp (op0->data, op1->data,
 803                              UNSIGNED_FIXED_POINT_MODE_P (op0->mode)) != 1;
 804
 805     case GT_EXPR:
 806       return double_int_cmp (op0->data, op1->data,
 807                              UNSIGNED_FIXED_POINT_MODE_P (op0->mode)) == 1;
 808
 809     case GE_EXPR:
 810       return double_int_cmp (op0->data, op1->data,
 811                              UNSIGNED_FIXED_POINT_MODE_P (op0->mode)) != -1;
 812
 813     default:
 814       gcc_unreachable ();
 815     }
 816 }
 817
 818 /* Extend or truncate to a new mode.
 819    If SAT_P, saturate the result to the max or the min.
 820    Return true, if !SAT_P and overflow.  */
 821
 822 bool
 823 fixed_convert (FIXED_VALUE_TYPE *f, enum machine_mode mode,
 824                const FIXED_VALUE_TYPE *a, bool sat_p)
 825 {
 826   bool overflow_p = false;
 827   if (mode == a->mode)
 828     {
 829       *f = *a;
 830       return overflow_p;
 831     }
 832
 833   if (GET_MODE_FBIT (mode) > GET_MODE_FBIT (a->mode))
 834     {
 835       /* Left shift a to temp_high, temp_low based on a->mode.  */
 836       double_int temp_high, temp_low;
 837       int amount = GET_MODE_FBIT (mode) - GET_MODE_FBIT (a->mode);
 838       lshift_double (a->data.low, a->data.high,
 839                      amount,
 840                      2 * HOST_BITS_PER_WIDE_INT,
 841                      &temp_low.low, &temp_low.high,
 842                      SIGNED_FIXED_POINT_MODE_P (a->mode));
 843       /* Logical shift right to temp_high.  */
 844       lshift_double (a->data.low, a->data.high,
 845                      amount - 2 * HOST_BITS_PER_WIDE_INT,
 846                      2 * HOST_BITS_PER_WIDE_INT,
 847                      &temp_high.low, &temp_high.high, 0);
 848       if (SIGNED_FIXED_POINT_MODE_P (a->mode)
 849           && a->data.high < 0) /* Signed-extend temp_high.  */
 850         temp_high = double_int_ext (temp_high, amount, 0);
 851       f->mode = mode;
 852       f->data = temp_low;
 853       if (SIGNED_FIXED_POINT_MODE_P (a->mode) ==
 854           SIGNED_FIXED_POINT_MODE_P (f->mode))
 855         overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low, &f->data,
 856                                       sat_p);
 857       else
 858         {
 859           /* Take care of the cases when converting between signed and
 860              unsigned.  */
 861           if (SIGNED_FIXED_POINT_MODE_P (a->mode))
 862             {
 863               /* Signed -> Unsigned.  */
 864               if (a->data.high < 0)
 865                 {
 866                   if (sat_p)
 867                     {
 868                       f->data.low = 0;  /* Set to zero.  */
 869                       f->data.high = 0;  /* Set to zero.  */
 870                     }
 871                   else
 872                     overflow_p = true;
 873                 }
 874               else
 875                 overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low,
 876                                               &f->data, sat_p);
 877             }
 878           else
 879             {
 880               /* Unsigned -> Signed.  */
 881               if (temp_high.high < 0)
 882                 {
 883                   if (sat_p)
 884                     {
 885                       /* Set to maximum.  */
 886                       f->data.low = -1;  /* Set to all ones.  */
 887                       f->data.high = -1;  /* Set to all ones.  */
 888                       f->data = double_int_ext (f->data,
 889                                                 GET_MODE_FBIT (f->mode)
 890                                                 + GET_MODE_IBIT (f->mode),
 891                                                 1); /* Clear the sign.  */
 892                     }
 893                   else
 894                     overflow_p = true;
 895                 }
 896               else
 897                 overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low,
 898                                               &f->data, sat_p);
 899             }
 900         }
 901     }
 902   else
 903     {
 904       /* Right shift a to temp based on a->mode.  */
 905       double_int temp;
 906       lshift_double (a->data.low, a->data.high,
 907                      GET_MODE_FBIT (mode) - GET_MODE_FBIT (a->mode),
 908                      2 * HOST_BITS_PER_WIDE_INT,
 909                      &temp.low, &temp.high,
 910                      SIGNED_FIXED_POINT_MODE_P (a->mode));
 911       f->mode = mode;
 912       f->data = temp;
 913       if (SIGNED_FIXED_POINT_MODE_P (a->mode) ==
 914           SIGNED_FIXED_POINT_MODE_P (f->mode))
 915         overflow_p = fixed_saturate1 (f->mode, f->data, &f->data, sat_p);
 916       else
 917         {
 918           /* Take care of the cases when converting between signed and
 919              unsigned.  */
 920           if (SIGNED_FIXED_POINT_MODE_P (a->mode))
 921             {
 922               /* Signed -> Unsigned.  */
 923               if (a->data.high < 0)
 924                 {
 925                   if (sat_p)
 926                     {
 927                       f->data.low = 0;  /* Set to zero.  */
 928                       f->data.high = 0;  /* Set to zero.  */
 929                     }
 930                   else
 931                     overflow_p = true;
 932                 }
 933               else
 934                 overflow_p = fixed_saturate1 (f->mode, f->data, &f->data,
 935                                               sat_p);
 936             }
 937           else
 938             {
 939               /* Unsigned -> Signed.  */
 940               if (temp.high < 0)
 941                 {
 942                   if (sat_p)
 943                     {
 944                       /* Set to maximum.  */
 945                       f->data.low = -1;  /* Set to all ones.  */
 946                       f->data.high = -1;  /* Set to all ones.  */
 947                       f->data = double_int_ext (f->data,
 948                                                 GET_MODE_FBIT (f->mode)
 949                                                 + GET_MODE_IBIT (f->mode),
 950                                                 1); /* Clear the sign.  */
 951                     }
 952                   else
 953                     overflow_p = true;
 954                 }
 955               else
 956                 overflow_p = fixed_saturate1 (f->mode, f->data, &f->data,
 957                                               sat_p);
 958             }
 959         }
 960     }
 961
 962   f->data = double_int_ext (f->data,
 963                             SIGNED_FIXED_POINT_MODE_P (f->mode)
 964                             + GET_MODE_FBIT (f->mode)
 965                             + GET_MODE_IBIT (f->mode),
 966                             UNSIGNED_FIXED_POINT_MODE_P (f->mode));
 967   return overflow_p;
 968 }
 969
 970 /* Convert to a new fixed-point mode from an integer.
 971    If UNSIGNED_P, this integer is unsigned.
 972    If SAT_P, saturate the result to the max or the min.
 973    Return true, if !SAT_P and overflow.  */
 974
 975 bool
 976 fixed_convert_from_int (FIXED_VALUE_TYPE *f, enum machine_mode mode,
 977                         double_int a, bool unsigned_p, bool sat_p)
 978 {
 979   bool overflow_p = false;
 980   /* Left shift a to temp_high, temp_low.  */
 981   double_int temp_high, temp_low;
 982   int amount = GET_MODE_FBIT (mode);
 983   if (amount == 2 * HOST_BITS_PER_WIDE_INT)
 984     {
 985        temp_high = a;
 986        temp_low.low = 0;
 987        temp_low.high = 0;
 988     }
 989   else
 990     {
 991       lshift_double (a.low, a.high,
 992                      amount,
 993                      2 * HOST_BITS_PER_WIDE_INT,
 994                      &temp_low.low, &temp_low.high, 0);
 995
 996       /* Logical shift right to temp_high.  */
 997       lshift_double (a.low, a.high,
 998                      amount - 2 * HOST_BITS_PER_WIDE_INT,
 999                      2 * HOST_BITS_PER_WIDE_INT,
1000                      &temp_high.low, &temp_high.high, 0);
1001     }
1002   if (!unsigned_p && a.high < 0) /* Signed-extend temp_high.  */
1003     temp_high = double_int_ext (temp_high, amount, 0);
1004
1005   f->mode = mode;
1006   f->data = temp_low;
1007
1008   if (unsigned_p == UNSIGNED_FIXED_POINT_MODE_P (f->mode))
1009     overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low, &f->data,
1010                                   sat_p);
1011   else
1012     {
1013       /* Take care of the cases when converting between signed and unsigned.  */
1014       if (!unsigned_p)
1015         {
1016           /* Signed -> Unsigned.  */
1017           if (a.high < 0)
1018             {
1019               if (sat_p)
1020                 {
1021                   f->data.low = 0;  /* Set to zero.  */
1022                   f->data.high = 0;  /* Set to zero.  */
1023                 }
1024               else
1025                 overflow_p = true;
1026             }
1027           else
1028             overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low,
1029                                           &f->data, sat_p);
1030         }
1031       else
1032         {
1033           /* Unsigned -> Signed.  */
1034           if (temp_high.high < 0)
1035             {
1036               if (sat_p)
1037                 {
1038                   /* Set to maximum.  */
1039                   f->data.low = -1;  /* Set to all ones.  */
1040                   f->data.high = -1;  /* Set to all ones.  */
1041                   f->data = double_int_ext (f->data,
1042                                             GET_MODE_FBIT (f->mode)
1043                                             + GET_MODE_IBIT (f->mode),
1044                                             1); /* Clear the sign.  */
1045                 }
1046               else
1047                 overflow_p = true;
1048             }
1049           else
1050             overflow_p = fixed_saturate2 (f->mode, temp_high, temp_low,
1051                                           &f->data, sat_p);
1052         }
1053     }
1054   f->data = double_int_ext (f->data,
1055                             SIGNED_FIXED_POINT_MODE_P (f->mode)
1056                             + GET_MODE_FBIT (f->mode)
1057                             + GET_MODE_IBIT (f->mode),
1058                             UNSIGNED_FIXED_POINT_MODE_P (f->mode));
1059   return overflow_p;
1060 }
1061
1062 /* Convert to a new fixed-point mode from a real.
1063    If SAT_P, saturate the result to the max or the min.
1064    Return true, if !SAT_P and overflow.  */
1065
1066 bool
1067 fixed_convert_from_real (FIXED_VALUE_TYPE *f, enum machine_mode mode,
1068                          const REAL_VALUE_TYPE *a, bool sat_p)
1069 {
1070   bool overflow_p = false;
1071   REAL_VALUE_TYPE real_value, fixed_value, base_value;
1072   bool unsigned_p = UNSIGNED_FIXED_POINT_MODE_P (mode);
1073   int i_f_bits = GET_MODE_IBIT (mode) + GET_MODE_FBIT (mode);
1074   unsigned int fbit = GET_MODE_FBIT (mode);
1075   enum fixed_value_range_code temp;
1076
1077   real_value = *a;
1078   f->mode = mode;
1079   real_2expN (&base_value, fbit, mode);
1080   real_arithmetic (&fixed_value, MULT_EXPR, &real_value, &base_value);
1081   real_to_integer2 ((HOST_WIDE_INT *)&f->data.low, &f->data.high, &fixed_value);
1082   temp = check_real_for_fixed_mode (&real_value, mode);
1083   if (temp == FIXED_UNDERFLOW) /* Minimum.  */
1084     {
1085       if (sat_p)
1086         {
1087           if (unsigned_p)
1088             {
1089               f->data.low = 0;
1090               f->data.high = 0;
1091             }
1092           else
1093             {
1094               f->data.low = 1;
1095               f->data.high = 0;
1096               lshift_double (f->data.low, f->data.high, i_f_bits,
1097                              2 * HOST_BITS_PER_WIDE_INT,
1098                              &f->data.low, &f->data.high, 1);
1099               f->data = double_int_ext (f->data, 1 + i_f_bits, 0);
1100             }
1101         }
1102       else
1103         overflow_p = true;
1104     }
1105   else if (temp == FIXED_GT_MAX_EPS || temp == FIXED_MAX_EPS) /* Maximum.  */
1106     {
1107       if (sat_p)
1108         {
1109           f->data.low = -1;
1110           f->data.high = -1;
1111           f->data = double_int_ext (f->data, i_f_bits, 1);
1112         }
1113       else
1114         overflow_p = true;
1115     }
1116   f->data = double_int_ext (f->data, (!unsigned_p) + i_f_bits, unsigned_p);
1117   return overflow_p;
1118 }
1119
1120 /* Convert to a new real mode from a fixed-point.  */
1121
1122 void
1123 real_convert_from_fixed (REAL_VALUE_TYPE *r, enum machine_mode mode,
1124                          const FIXED_VALUE_TYPE *f)
1125 {
1126   REAL_VALUE_TYPE base_value, fixed_value, real_value;
1127
1128   real_2expN (&base_value, GET_MODE_FBIT (f->mode), f->mode);
1129   real_from_integer (&fixed_value, VOIDmode, f->data.low, f->data.high,
1130                      UNSIGNED_FIXED_POINT_MODE_P (f->mode));
1131   real_arithmetic (&real_value, RDIV_EXPR, &fixed_value, &base_value);
1132   real_convert (r, mode, &real_value);
1133 }
1134
1135 /* Determine whether a fixed-point value F is negative.  */
1136
1137 bool
1138 fixed_isneg (const FIXED_VALUE_TYPE *f)
1139 {
1140   if (SIGNED_FIXED_POINT_MODE_P (f->mode))
1141     {
1142       int i_f_bits = GET_MODE_IBIT (f->mode) + GET_MODE_FBIT (f->mode);
1143       int sign_bit = get_fixed_sign_bit (f->data, i_f_bits);
1144       if (sign_bit == 1)
1145         return true;
1146     }
1147
1148   return false;
1149 }