gcc/fixed-value.c

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