gcc/expmed.c

   1 /* Medium-level subroutines: convert bit-field store and extract
   2    and shifts, multiplies and divides to rtl instructions.
   3    Copyright (C) 1987-2015 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "diagnostic-core.h"
  27 #include "rtl.h"
  28 #include "alias.h"
  29 #include "symtab.h"
  30 #include "tree.h"
  31 #include "fold-const.h"
  32 #include "stor-layout.h"
  33 #include "tm_p.h"
  34 #include "flags.h"
  35 #include "insn-config.h"
  36 #include "hard-reg-set.h"
  37 #include "function.h"
  38 #include "expmed.h"
  39 #include "dojump.h"
  40 #include "explow.h"
  41 #include "calls.h"
  42 #include "emit-rtl.h"
  43 #include "varasm.h"
  44 #include "stmt.h"
  45 #include "expr.h"
  46 #include "insn-codes.h"
  47 #include "optabs.h"
  48 #include "recog.h"
  49 #include "langhooks.h"
  50 #include "predict.h"
  51 #include "basic-block.h"
  52 #include "df.h"
  53 #include "target.h"
  54
  55 struct target_expmed default_target_expmed;
  56 #if SWITCHABLE_TARGET
  57 struct target_expmed *this_target_expmed = &default_target_expmed;
  58 #endif
  59
  60 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
  61                                    unsigned HOST_WIDE_INT,
  62                                    unsigned HOST_WIDE_INT,
  63                                    unsigned HOST_WIDE_INT,
  64                                    rtx);
  65 static void store_fixed_bit_field_1 (rtx, unsigned HOST_WIDE_INT,
  66                                      unsigned HOST_WIDE_INT,
  67                                      rtx);
  68 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
  69                                    unsigned HOST_WIDE_INT,
  70                                    unsigned HOST_WIDE_INT,
  71                                    unsigned HOST_WIDE_INT,
  72                                    rtx);
  73 static rtx extract_fixed_bit_field (machine_mode, rtx,
  74                                     unsigned HOST_WIDE_INT,
  75                                     unsigned HOST_WIDE_INT, rtx, int);
  76 static rtx extract_fixed_bit_field_1 (machine_mode, rtx,
  77                                       unsigned HOST_WIDE_INT,
  78                                       unsigned HOST_WIDE_INT, rtx, int);
  79 static rtx lshift_value (machine_mode, unsigned HOST_WIDE_INT, int);
  80 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
  81                                     unsigned HOST_WIDE_INT, int);
  82 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, machine_mode, rtx_code_label *);
  83 static rtx expand_smod_pow2 (machine_mode, rtx, HOST_WIDE_INT);
  84 static rtx expand_sdiv_pow2 (machine_mode, rtx, HOST_WIDE_INT);
  85
  86 /* Return a constant integer mask value of mode MODE with BITSIZE ones
  87    followed by BITPOS zeros, or the complement of that if COMPLEMENT.
  88    The mask is truncated if necessary to the width of mode MODE.  The
  89    mask is zero-extended if BITSIZE+BITPOS is too small for MODE.  */
  90
  91 static inline rtx
  92 mask_rtx (machine_mode mode, int bitpos, int bitsize, bool complement)
  93 {
  94   return immed_wide_int_const
  95     (wi::shifted_mask (bitpos, bitsize, complement,
  96                        GET_MODE_PRECISION (mode)), mode);
  97 }
  98
  99 /* Test whether a value is zero of a power of two.  */
 100 #define EXACT_POWER_OF_2_OR_ZERO_P(x) \
 101   (((x) & ((x) - (unsigned HOST_WIDE_INT) 1)) == 0)
 102
 103 struct init_expmed_rtl
 104 {
 105   rtx reg;
 106   rtx plus;
 107   rtx neg;
 108   rtx mult;
 109   rtx sdiv;
 110   rtx udiv;
 111   rtx sdiv_32;
 112   rtx smod_32;
 113   rtx wide_mult;
 114   rtx wide_lshr;
 115   rtx wide_trunc;
 116   rtx shift;
 117   rtx shift_mult;
 118   rtx shift_add;
 119   rtx shift_sub0;
 120   rtx shift_sub1;
 121   rtx zext;
 122   rtx trunc;
 123
 124   rtx pow2[MAX_BITS_PER_WORD];
 125   rtx cint[MAX_BITS_PER_WORD];
 126 };
 127
 128 static void
 129 init_expmed_one_conv (struct init_expmed_rtl *all, machine_mode to_mode,
 130                       machine_mode from_mode, bool speed)
 131 {
 132   int to_size, from_size;
 133   rtx which;
 134
 135   to_size = GET_MODE_PRECISION (to_mode);
 136   from_size = GET_MODE_PRECISION (from_mode);
 137
 138   /* Most partial integers have a precision less than the "full"
 139      integer it requires for storage.  In case one doesn't, for
 140      comparison purposes here, reduce the bit size by one in that
 141      case.  */
 142   if (GET_MODE_CLASS (to_mode) == MODE_PARTIAL_INT
 143       && exact_log2 (to_size) != -1)
 144     to_size --;
 145   if (GET_MODE_CLASS (from_mode) == MODE_PARTIAL_INT
 146       && exact_log2 (from_size) != -1)
 147     from_size --;
 148
 149   /* Assume cost of zero-extend and sign-extend is the same.  */
 150   which = (to_size < from_size ? all->trunc : all->zext);
 151
 152   PUT_MODE (all->reg, from_mode);
 153   set_convert_cost (to_mode, from_mode, speed, set_src_cost (which, speed));
 154 }
 155
 156 static void
 157 init_expmed_one_mode (struct init_expmed_rtl *all,
 158                       machine_mode mode, int speed)
 159 {
 160   int m, n, mode_bitsize;
 161   machine_mode mode_from;
 162
 163   mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
 164
 165   PUT_MODE (all->reg, mode);
 166   PUT_MODE (all->plus, mode);
 167   PUT_MODE (all->neg, mode);
 168   PUT_MODE (all->mult, mode);
 169   PUT_MODE (all->sdiv, mode);
 170   PUT_MODE (all->udiv, mode);
 171   PUT_MODE (all->sdiv_32, mode);
 172   PUT_MODE (all->smod_32, mode);
 173   PUT_MODE (all->wide_trunc, mode);
 174   PUT_MODE (all->shift, mode);
 175   PUT_MODE (all->shift_mult, mode);
 176   PUT_MODE (all->shift_add, mode);
 177   PUT_MODE (all->shift_sub0, mode);
 178   PUT_MODE (all->shift_sub1, mode);
 179   PUT_MODE (all->zext, mode);
 180   PUT_MODE (all->trunc, mode);
 181
 182   set_add_cost (speed, mode, set_src_cost (all->plus, speed));
 183   set_neg_cost (speed, mode, set_src_cost (all->neg, speed));
 184   set_mul_cost (speed, mode, set_src_cost (all->mult, speed));
 185   set_sdiv_cost (speed, mode, set_src_cost (all->sdiv, speed));
 186   set_udiv_cost (speed, mode, set_src_cost (all->udiv, speed));
 187
 188   set_sdiv_pow2_cheap (speed, mode, (set_src_cost (all->sdiv_32, speed)
 189                                      <= 2 * add_cost (speed, mode)));
 190   set_smod_pow2_cheap (speed, mode, (set_src_cost (all->smod_32, speed)
 191                                      <= 4 * add_cost (speed, mode)));
 192
 193   set_shift_cost (speed, mode, 0, 0);
 194   {
 195     int cost = add_cost (speed, mode);
 196     set_shiftadd_cost (speed, mode, 0, cost);
 197     set_shiftsub0_cost (speed, mode, 0, cost);
 198     set_shiftsub1_cost (speed, mode, 0, cost);
 199   }
 200
 201   n = MIN (MAX_BITS_PER_WORD, mode_bitsize);
 202   for (m = 1; m < n; m++)
 203     {
 204       XEXP (all->shift, 1) = all->cint[m];
 205       XEXP (all->shift_mult, 1) = all->pow2[m];
 206
 207       set_shift_cost (speed, mode, m, set_src_cost (all->shift, speed));
 208       set_shiftadd_cost (speed, mode, m, set_src_cost (all->shift_add, speed));
 209       set_shiftsub0_cost (speed, mode, m, set_src_cost (all->shift_sub0, speed));
 210       set_shiftsub1_cost (speed, mode, m, set_src_cost (all->shift_sub1, speed));
 211     }
 212
 213   if (SCALAR_INT_MODE_P (mode))
 214     {
 215       for (mode_from = MIN_MODE_INT; mode_from <= MAX_MODE_INT;
 216            mode_from = (machine_mode)(mode_from + 1))
 217         init_expmed_one_conv (all, mode, mode_from, speed);
 218     }
 219   if (GET_MODE_CLASS (mode) == MODE_INT)
 220     {
 221       machine_mode  wider_mode = GET_MODE_WIDER_MODE (mode);
 222       if (wider_mode != VOIDmode)
 223         {
 224           PUT_MODE (all->zext, wider_mode);
 225           PUT_MODE (all->wide_mult, wider_mode);
 226           PUT_MODE (all->wide_lshr, wider_mode);
 227           XEXP (all->wide_lshr, 1) = GEN_INT (mode_bitsize);
 228
 229           set_mul_widen_cost (speed, wider_mode,
 230                               set_src_cost (all->wide_mult, speed));
 231           set_mul_highpart_cost (speed, mode,
 232                                  set_src_cost (all->wide_trunc, speed));
 233         }
 234     }
 235 }
 236
 237 void
 238 init_expmed (void)
 239 {
 240   struct init_expmed_rtl all;
 241   machine_mode mode = QImode;
 242   int m, speed;
 243
 244   memset (&all, 0, sizeof all);
 245   for (m = 1; m < MAX_BITS_PER_WORD; m++)
 246     {
 247       all.pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
 248       all.cint[m] = GEN_INT (m);
 249     }
 250
 251   /* Avoid using hard regs in ways which may be unsupported.  */
 252   all.reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
 253   all.plus = gen_rtx_PLUS (mode, all.reg, all.reg);
 254   all.neg = gen_rtx_NEG (mode, all.reg);
 255   all.mult = gen_rtx_MULT (mode, all.reg, all.reg);
 256   all.sdiv = gen_rtx_DIV (mode, all.reg, all.reg);
 257   all.udiv = gen_rtx_UDIV (mode, all.reg, all.reg);
 258   all.sdiv_32 = gen_rtx_DIV (mode, all.reg, all.pow2[5]);
 259   all.smod_32 = gen_rtx_MOD (mode, all.reg, all.pow2[5]);
 260   all.zext = gen_rtx_ZERO_EXTEND (mode, all.reg);
 261   all.wide_mult = gen_rtx_MULT (mode, all.zext, all.zext);
 262   all.wide_lshr = gen_rtx_LSHIFTRT (mode, all.wide_mult, all.reg);
 263   all.wide_trunc = gen_rtx_TRUNCATE (mode, all.wide_lshr);
 264   all.shift = gen_rtx_ASHIFT (mode, all.reg, all.reg);
 265   all.shift_mult = gen_rtx_MULT (mode, all.reg, all.reg);
 266   all.shift_add = gen_rtx_PLUS (mode, all.shift_mult, all.reg);
 267   all.shift_sub0 = gen_rtx_MINUS (mode, all.shift_mult, all.reg);
 268   all.shift_sub1 = gen_rtx_MINUS (mode, all.reg, all.shift_mult);
 269   all.trunc = gen_rtx_TRUNCATE (mode, all.reg);
 270
 271   for (speed = 0; speed < 2; speed++)
 272     {
 273       crtl->maybe_hot_insn_p = speed;
 274       set_zero_cost (speed, set_src_cost (const0_rtx, speed));
 275
 276       for (mode = MIN_MODE_INT; mode <= MAX_MODE_INT;
 277            mode = (machine_mode)(mode + 1))
 278         init_expmed_one_mode (&all, mode, speed);
 279
 280       if (MIN_MODE_PARTIAL_INT != VOIDmode)
 281         for (mode = MIN_MODE_PARTIAL_INT; mode <= MAX_MODE_PARTIAL_INT;
 282              mode = (machine_mode)(mode + 1))
 283           init_expmed_one_mode (&all, mode, speed);
 284
 285       if (MIN_MODE_VECTOR_INT != VOIDmode)
 286         for (mode = MIN_MODE_VECTOR_INT; mode <= MAX_MODE_VECTOR_INT;
 287              mode = (machine_mode)(mode + 1))
 288           init_expmed_one_mode (&all, mode, speed);
 289     }
 290
 291   if (alg_hash_used_p ())
 292     {
 293       struct alg_hash_entry *p = alg_hash_entry_ptr (0);
 294       memset (p, 0, sizeof (*p) * NUM_ALG_HASH_ENTRIES);
 295     }
 296   else
 297     set_alg_hash_used_p (true);
 298   default_rtl_profile ();
 299
 300   ggc_free (all.trunc);
 301   ggc_free (all.shift_sub1);
 302   ggc_free (all.shift_sub0);
 303   ggc_free (all.shift_add);
 304   ggc_free (all.shift_mult);
 305   ggc_free (all.shift);
 306   ggc_free (all.wide_trunc);
 307   ggc_free (all.wide_lshr);
 308   ggc_free (all.wide_mult);
 309   ggc_free (all.zext);
 310   ggc_free (all.smod_32);
 311   ggc_free (all.sdiv_32);
 312   ggc_free (all.udiv);
 313   ggc_free (all.sdiv);
 314   ggc_free (all.mult);
 315   ggc_free (all.neg);
 316   ggc_free (all.plus);
 317   ggc_free (all.reg);
 318 }
 319
 320 /* Return an rtx representing minus the value of X.
 321    MODE is the intended mode of the result,
 322    useful if X is a CONST_INT.  */
 323
 324 rtx
 325 negate_rtx (machine_mode mode, rtx x)
 326 {
 327   rtx result = simplify_unary_operation (NEG, mode, x, mode);
 328
 329   if (result == 0)
 330     result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
 331
 332   return result;
 333 }
 334
 335 /* Adjust bitfield memory MEM so that it points to the first unit of mode
 336    MODE that contains a bitfield of size BITSIZE at bit position BITNUM.
 337    If MODE is BLKmode, return a reference to every byte in the bitfield.
 338    Set *NEW_BITNUM to the bit position of the field within the new memory.  */
 339
 340 static rtx
 341 narrow_bit_field_mem (rtx mem, machine_mode mode,
 342                       unsigned HOST_WIDE_INT bitsize,
 343                       unsigned HOST_WIDE_INT bitnum,
 344                       unsigned HOST_WIDE_INT *new_bitnum)
 345 {
 346   if (mode == BLKmode)
 347     {
 348       *new_bitnum = bitnum % BITS_PER_UNIT;
 349       HOST_WIDE_INT offset = bitnum / BITS_PER_UNIT;
 350       HOST_WIDE_INT size = ((*new_bitnum + bitsize + BITS_PER_UNIT - 1)
 351                             / BITS_PER_UNIT);
 352       return adjust_bitfield_address_size (mem, mode, offset, size);
 353     }
 354   else
 355     {
 356       unsigned int unit = GET_MODE_BITSIZE (mode);
 357       *new_bitnum = bitnum % unit;
 358       HOST_WIDE_INT offset = (bitnum - *new_bitnum) / BITS_PER_UNIT;
 359       return adjust_bitfield_address (mem, mode, offset);
 360     }
 361 }
 362
 363 /* The caller wants to perform insertion or extraction PATTERN on a
 364    bitfield of size BITSIZE at BITNUM bits into memory operand OP0.
 365    BITREGION_START and BITREGION_END are as for store_bit_field
 366    and FIELDMODE is the natural mode of the field.
 367
 368    Search for a mode that is compatible with the memory access
 369    restrictions and (where applicable) with a register insertion or
 370    extraction.  Return the new memory on success, storing the adjusted
 371    bit position in *NEW_BITNUM.  Return null otherwise.  */
 372
 373 static rtx
 374 adjust_bit_field_mem_for_reg (enum extraction_pattern pattern,
 375                               rtx op0, HOST_WIDE_INT bitsize,
 376                               HOST_WIDE_INT bitnum,
 377                               unsigned HOST_WIDE_INT bitregion_start,
 378                               unsigned HOST_WIDE_INT bitregion_end,
 379                               machine_mode fieldmode,
 380                               unsigned HOST_WIDE_INT *new_bitnum)
 381 {
 382   bit_field_mode_iterator iter (bitsize, bitnum, bitregion_start,
 383                                 bitregion_end, MEM_ALIGN (op0),
 384                                 MEM_VOLATILE_P (op0));
 385   machine_mode best_mode;
 386   if (iter.next_mode (&best_mode))
 387     {
 388       /* We can use a memory in BEST_MODE.  See whether this is true for
 389          any wider modes.  All other things being equal, we prefer to
 390          use the widest mode possible because it tends to expose more
 391          CSE opportunities.  */
 392       if (!iter.prefer_smaller_modes ())
 393         {
 394           /* Limit the search to the mode required by the corresponding
 395              register insertion or extraction instruction, if any.  */
 396           machine_mode limit_mode = word_mode;
 397           extraction_insn insn;
 398           if (get_best_reg_extraction_insn (&insn, pattern,
 399                                             GET_MODE_BITSIZE (best_mode),
 400                                             fieldmode))
 401             limit_mode = insn.field_mode;
 402
 403           machine_mode wider_mode;
 404           while (iter.next_mode (&wider_mode)
 405                  && GET_MODE_SIZE (wider_mode) <= GET_MODE_SIZE (limit_mode))
 406             best_mode = wider_mode;
 407         }
 408       return narrow_bit_field_mem (op0, best_mode, bitsize, bitnum,
 409                                    new_bitnum);
 410     }
 411   return NULL_RTX;
 412 }
 413
 414 /* Return true if a bitfield of size BITSIZE at bit number BITNUM within
 415    a structure of mode STRUCT_MODE represents a lowpart subreg.   The subreg
 416    offset is then BITNUM / BITS_PER_UNIT.  */
 417
 418 static bool
 419 lowpart_bit_field_p (unsigned HOST_WIDE_INT bitnum,
 420                      unsigned HOST_WIDE_INT bitsize,
 421                      machine_mode struct_mode)
 422 {
 423   if (BYTES_BIG_ENDIAN)
 424     return (bitnum % BITS_PER_UNIT == 0
 425             && (bitnum + bitsize == GET_MODE_BITSIZE (struct_mode)
 426                 || (bitnum + bitsize) % BITS_PER_WORD == 0));
 427   else
 428     return bitnum % BITS_PER_WORD == 0;
 429 }
 430
 431 /* Return true if -fstrict-volatile-bitfields applies to an access of OP0
 432    containing BITSIZE bits starting at BITNUM, with field mode FIELDMODE.
 433    Return false if the access would touch memory outside the range
 434    BITREGION_START to BITREGION_END for conformance to the C++ memory
 435    model.  */
 436
 437 static bool
 438 strict_volatile_bitfield_p (rtx op0, unsigned HOST_WIDE_INT bitsize,
 439                             unsigned HOST_WIDE_INT bitnum,
 440                             machine_mode fieldmode,
 441                             unsigned HOST_WIDE_INT bitregion_start,
 442                             unsigned HOST_WIDE_INT bitregion_end)
 443 {
 444   unsigned HOST_WIDE_INT modesize = GET_MODE_BITSIZE (fieldmode);
 445
 446   /* -fstrict-volatile-bitfields must be enabled and we must have a
 447      volatile MEM.  */
 448   if (!MEM_P (op0)
 449       || !MEM_VOLATILE_P (op0)
 450       || flag_strict_volatile_bitfields <= 0)
 451     return false;
 452
 453   /* Non-integral modes likely only happen with packed structures.
 454      Punt.  */
 455   if (!SCALAR_INT_MODE_P (fieldmode))
 456     return false;
 457
 458   /* The bit size must not be larger than the field mode, and
 459      the field mode must not be larger than a word.  */
 460   if (bitsize > modesize || modesize > BITS_PER_WORD)
 461     return false;
 462
 463   /* Check for cases of unaligned fields that must be split.  */
 464   if (bitnum % modesize + bitsize > modesize)
 465     return false;
 466
 467   /* The memory must be sufficiently aligned for a MODESIZE access.
 468      This condition guarantees, that the memory access will not
 469      touch anything after the end of the structure.  */
 470   if (MEM_ALIGN (op0) < modesize)
 471     return false;
 472
 473   /* Check for cases where the C++ memory model applies.  */
 474   if (bitregion_end != 0
 475       && (bitnum - bitnum % modesize < bitregion_start
 476           || bitnum - bitnum % modesize + modesize - 1 > bitregion_end))
 477     return false;
 478
 479   return true;
 480 }
 481
 482 /* Return true if OP is a memory and if a bitfield of size BITSIZE at
 483    bit number BITNUM can be treated as a simple value of mode MODE.  */
 484
 485 static bool
 486 simple_mem_bitfield_p (rtx op0, unsigned HOST_WIDE_INT bitsize,
 487                        unsigned HOST_WIDE_INT bitnum, machine_mode mode)
 488 {
 489   return (MEM_P (op0)
 490           && bitnum % BITS_PER_UNIT == 0
 491           && bitsize == GET_MODE_BITSIZE (mode)
 492           && (!SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
 493               || (bitnum % GET_MODE_ALIGNMENT (mode) == 0
 494                   && MEM_ALIGN (op0) >= GET_MODE_ALIGNMENT (mode))));
 495 }
 496 \f
 497 /* Try to use instruction INSV to store VALUE into a field of OP0.
 498    BITSIZE and BITNUM are as for store_bit_field.  */
 499
 500 static bool
 501 store_bit_field_using_insv (const extraction_insn *insv, rtx op0,
 502                             unsigned HOST_WIDE_INT bitsize,
 503                             unsigned HOST_WIDE_INT bitnum,
 504                             rtx value)
 505 {
 506   struct expand_operand ops[4];
 507   rtx value1;
 508   rtx xop0 = op0;
 509   rtx_insn *last = get_last_insn ();
 510   bool copy_back = false;
 511
 512   machine_mode op_mode = insv->field_mode;
 513   unsigned int unit = GET_MODE_BITSIZE (op_mode);
 514   if (bitsize == 0 || bitsize > unit)
 515     return false;
 516
 517   if (MEM_P (xop0))
 518     /* Get a reference to the first byte of the field.  */
 519     xop0 = narrow_bit_field_mem (xop0, insv->struct_mode, bitsize, bitnum,
 520                                  &bitnum);
 521   else
 522     {
 523       /* Convert from counting within OP0 to counting in OP_MODE.  */
 524       if (BYTES_BIG_ENDIAN)
 525         bitnum += unit - GET_MODE_BITSIZE (GET_MODE (op0));
 526
 527       /* If xop0 is a register, we need it in OP_MODE
 528          to make it acceptable to the format of insv.  */
 529       if (GET_CODE (xop0) == SUBREG)
 530         /* We can't just change the mode, because this might clobber op0,
 531            and we will need the original value of op0 if insv fails.  */
 532         xop0 = gen_rtx_SUBREG (op_mode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
 533       if (REG_P (xop0) && GET_MODE (xop0) != op_mode)
 534         xop0 = gen_lowpart_SUBREG (op_mode, xop0);
 535     }
 536
 537   /* If the destination is a paradoxical subreg such that we need a
 538      truncate to the inner mode, perform the insertion on a temporary and
 539      truncate the result to the original destination.  Note that we can't
 540      just truncate the paradoxical subreg as (truncate:N (subreg:W (reg:N
 541      X) 0)) is (reg:N X).  */
 542   if (GET_CODE (xop0) == SUBREG
 543       && REG_P (SUBREG_REG (xop0))
 544       && !TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (SUBREG_REG (xop0)),
 545                                          op_mode))
 546     {
 547       rtx tem = gen_reg_rtx (op_mode);
 548       emit_move_insn (tem, xop0);
 549       xop0 = tem;
 550       copy_back = true;
 551     }
 552
 553   /* There are similar overflow check at the start of store_bit_field_1,
 554      but that only check the situation where the field lies completely
 555      outside the register, while there do have situation where the field
 556      lies partialy in the register, we need to adjust bitsize for this
 557      partial overflow situation.  Without this fix, pr48335-2.c on big-endian
 558      will broken on those arch support bit insert instruction, like arm, aarch64
 559      etc.  */
 560   if (bitsize + bitnum > unit && bitnum < unit)
 561     {
 562       warning (OPT_Wextra, "write of %wu-bit data outside the bound of "
 563                "destination object, data truncated into %wu-bit",
 564                bitsize, unit - bitnum);
 565       bitsize = unit - bitnum;
 566     }
 567
 568   /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
 569      "backwards" from the size of the unit we are inserting into.
 570      Otherwise, we count bits from the most significant on a
 571      BYTES/BITS_BIG_ENDIAN machine.  */
 572
 573   if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
 574     bitnum = unit - bitsize - bitnum;
 575
 576   /* Convert VALUE to op_mode (which insv insn wants) in VALUE1.  */
 577   value1 = value;
 578   if (GET_MODE (value) != op_mode)
 579     {
 580       if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
 581         {
 582           /* Optimization: Don't bother really extending VALUE
 583              if it has all the bits we will actually use.  However,
 584              if we must narrow it, be sure we do it correctly.  */
 585
 586           if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (op_mode))
 587             {
 588               rtx tmp;
 589
 590               tmp = simplify_subreg (op_mode, value1, GET_MODE (value), 0);
 591               if (! tmp)
 592                 tmp = simplify_gen_subreg (op_mode,
 593                                            force_reg (GET_MODE (value),
 594                                                       value1),
 595                                            GET_MODE (value), 0);
 596               value1 = tmp;
 597             }
 598           else
 599             value1 = gen_lowpart (op_mode, value1);
 600         }
 601       else if (CONST_INT_P (value))
 602         value1 = gen_int_mode (INTVAL (value), op_mode);
 603       else
 604         /* Parse phase is supposed to make VALUE's data type
 605            match that of the component reference, which is a type
 606            at least as wide as the field; so VALUE should have
 607            a mode that corresponds to that type.  */
 608         gcc_assert (CONSTANT_P (value));
 609     }
 610
 611   create_fixed_operand (&ops[0], xop0);
 612   create_integer_operand (&ops[1], bitsize);
 613   create_integer_operand (&ops[2], bitnum);
 614   create_input_operand (&ops[3], value1, op_mode);
 615   if (maybe_expand_insn (insv->icode, 4, ops))
 616     {
 617       if (copy_back)
 618         convert_move (op0, xop0, true);
 619       return true;
 620     }
 621   delete_insns_since (last);
 622   return false;
 623 }
 624
 625 /* A subroutine of store_bit_field, with the same arguments.  Return true
 626    if the operation could be implemented.
 627
 628    If FALLBACK_P is true, fall back to store_fixed_bit_field if we have
 629    no other way of implementing the operation.  If FALLBACK_P is false,
 630    return false instead.  */
 631
 632 static bool
 633 store_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
 634                    unsigned HOST_WIDE_INT bitnum,
 635                    unsigned HOST_WIDE_INT bitregion_start,
 636                    unsigned HOST_WIDE_INT bitregion_end,
 637                    machine_mode fieldmode,
 638                    rtx value, bool fallback_p)
 639 {
 640   rtx op0 = str_rtx;
 641   rtx orig_value;
 642
 643   while (GET_CODE (op0) == SUBREG)
 644     {
 645       /* The following line once was done only if WORDS_BIG_ENDIAN,
 646          but I think that is a mistake.  WORDS_BIG_ENDIAN is
 647          meaningful at a much higher level; when structures are copied
 648          between memory and regs, the higher-numbered regs
 649          always get higher addresses.  */
 650       int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)));
 651       int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0));
 652       int byte_offset = 0;
 653
 654       /* Paradoxical subregs need special handling on big endian machines.  */
 655       if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size)
 656         {
 657           int difference = inner_mode_size - outer_mode_size;
 658
 659           if (WORDS_BIG_ENDIAN)
 660             byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
 661           if (BYTES_BIG_ENDIAN)
 662             byte_offset += difference % UNITS_PER_WORD;
 663         }
 664       else
 665         byte_offset = SUBREG_BYTE (op0);
 666
 667       bitnum += byte_offset * BITS_PER_UNIT;
 668       op0 = SUBREG_REG (op0);
 669     }
 670
 671   /* No action is needed if the target is a register and if the field
 672      lies completely outside that register.  This can occur if the source
 673      code contains an out-of-bounds access to a small array.  */
 674   if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
 675     return true;
 676
 677   /* Use vec_set patterns for inserting parts of vectors whenever
 678      available.  */
 679   if (VECTOR_MODE_P (GET_MODE (op0))
 680       && !MEM_P (op0)
 681       && optab_handler (vec_set_optab, GET_MODE (op0)) != CODE_FOR_nothing
 682       && fieldmode == GET_MODE_INNER (GET_MODE (op0))
 683       && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
 684       && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
 685     {
 686       struct expand_operand ops[3];
 687       machine_mode outermode = GET_MODE (op0);
 688       machine_mode innermode = GET_MODE_INNER (outermode);
 689       enum insn_code icode = optab_handler (vec_set_optab, outermode);
 690       int pos = bitnum / GET_MODE_BITSIZE (innermode);
 691
 692       create_fixed_operand (&ops[0], op0);
 693       create_input_operand (&ops[1], value, innermode);
 694       create_integer_operand (&ops[2], pos);
 695       if (maybe_expand_insn (icode, 3, ops))
 696         return true;
 697     }
 698
 699   /* If the target is a register, overwriting the entire object, or storing
 700      a full-word or multi-word field can be done with just a SUBREG.  */
 701   if (!MEM_P (op0)
 702       && bitsize == GET_MODE_BITSIZE (fieldmode)
 703       && ((bitsize == GET_MODE_BITSIZE (GET_MODE (op0)) && bitnum == 0)
 704           || (bitsize % BITS_PER_WORD == 0 && bitnum % BITS_PER_WORD == 0)))
 705     {
 706       /* Use the subreg machinery either to narrow OP0 to the required
 707          words or to cope with mode punning between equal-sized modes.
 708          In the latter case, use subreg on the rhs side, not lhs.  */
 709       rtx sub;
 710
 711       if (bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
 712         {
 713           sub = simplify_gen_subreg (GET_MODE (op0), value, fieldmode, 0);
 714           if (sub)
 715             {
 716               emit_move_insn (op0, sub);
 717               return true;
 718             }
 719         }
 720       else
 721         {
 722           sub = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0),
 723                                      bitnum / BITS_PER_UNIT);
 724           if (sub)
 725             {
 726               emit_move_insn (sub, value);
 727               return true;
 728             }
 729         }
 730     }
 731
 732   /* If the target is memory, storing any naturally aligned field can be
 733      done with a simple store.  For targets that support fast unaligned
 734      memory, any naturally sized, unit aligned field can be done directly.  */
 735   if (simple_mem_bitfield_p (op0, bitsize, bitnum, fieldmode))
 736     {
 737       op0 = adjust_bitfield_address (op0, fieldmode, bitnum / BITS_PER_UNIT);
 738       emit_move_insn (op0, value);
 739       return true;
 740     }
 741
 742   /* Make sure we are playing with integral modes.  Pun with subregs
 743      if we aren't.  This must come after the entire register case above,
 744      since that case is valid for any mode.  The following cases are only
 745      valid for integral modes.  */
 746   {
 747     machine_mode imode = int_mode_for_mode (GET_MODE (op0));
 748     if (imode != GET_MODE (op0))
 749       {
 750         if (MEM_P (op0))
 751           op0 = adjust_bitfield_address_size (op0, imode, 0, MEM_SIZE (op0));
 752         else
 753           {
 754             gcc_assert (imode != BLKmode);
 755             op0 = gen_lowpart (imode, op0);
 756           }
 757       }
 758   }
 759
 760   /* Storing an lsb-aligned field in a register
 761      can be done with a movstrict instruction.  */
 762
 763   if (!MEM_P (op0)
 764       && lowpart_bit_field_p (bitnum, bitsize, GET_MODE (op0))
 765       && bitsize == GET_MODE_BITSIZE (fieldmode)
 766       && optab_handler (movstrict_optab, fieldmode) != CODE_FOR_nothing)
 767     {
 768       struct expand_operand ops[2];
 769       enum insn_code icode = optab_handler (movstrict_optab, fieldmode);
 770       rtx arg0 = op0;
 771       unsigned HOST_WIDE_INT subreg_off;
 772
 773       if (GET_CODE (arg0) == SUBREG)
 774         {
 775           /* Else we've got some float mode source being extracted into
 776              a different float mode destination -- this combination of
 777              subregs results in Severe Tire Damage.  */
 778           gcc_assert (GET_MODE (SUBREG_REG (arg0)) == fieldmode
 779                       || GET_MODE_CLASS (fieldmode) == MODE_INT
 780                       || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT);
 781           arg0 = SUBREG_REG (arg0);
 782         }
 783
 784       subreg_off = bitnum / BITS_PER_UNIT;
 785       if (validate_subreg (fieldmode, GET_MODE (arg0), arg0, subreg_off))
 786         {
 787           arg0 = gen_rtx_SUBREG (fieldmode, arg0, subreg_off);
 788
 789           create_fixed_operand (&ops[0], arg0);
 790           /* Shrink the source operand to FIELDMODE.  */
 791           create_convert_operand_to (&ops[1], value, fieldmode, false);
 792           if (maybe_expand_insn (icode, 2, ops))
 793             return true;
 794         }
 795     }
 796
 797   /* Handle fields bigger than a word.  */
 798
 799   if (bitsize > BITS_PER_WORD)
 800     {
 801       /* Here we transfer the words of the field
 802          in the order least significant first.
 803          This is because the most significant word is the one which may
 804          be less than full.
 805          However, only do that if the value is not BLKmode.  */
 806
 807       unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
 808       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
 809       unsigned int i;
 810       rtx_insn *last;
 811
 812       /* This is the mode we must force value to, so that there will be enough
 813          subwords to extract.  Note that fieldmode will often (always?) be
 814          VOIDmode, because that is what store_field uses to indicate that this
 815          is a bit field, but passing VOIDmode to operand_subword_force
 816          is not allowed.  */
 817       fieldmode = GET_MODE (value);
 818       if (fieldmode == VOIDmode)
 819         fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
 820
 821       last = get_last_insn ();
 822       for (i = 0; i < nwords; i++)
 823         {
 824           /* If I is 0, use the low-order word in both field and target;
 825              if I is 1, use the next to lowest word; and so on.  */
 826           unsigned int wordnum = (backwards
 827                                   ? GET_MODE_SIZE (fieldmode) / UNITS_PER_WORD
 828                                   - i - 1
 829                                   : i);
 830           unsigned int bit_offset = (backwards
 831                                      ? MAX ((int) bitsize - ((int) i + 1)
 832                                             * BITS_PER_WORD,
 833                                             0)
 834                                      : (int) i * BITS_PER_WORD);
 835           rtx value_word = operand_subword_force (value, wordnum, fieldmode);
 836           unsigned HOST_WIDE_INT new_bitsize =
 837             MIN (BITS_PER_WORD, bitsize - i * BITS_PER_WORD);
 838
 839           /* If the remaining chunk doesn't have full wordsize we have
 840              to make sure that for big endian machines the higher order
 841              bits are used.  */
 842           if (new_bitsize < BITS_PER_WORD && BYTES_BIG_ENDIAN && !backwards)
 843             value_word = simplify_expand_binop (word_mode, lshr_optab,
 844                                                 value_word,
 845                                                 GEN_INT (BITS_PER_WORD
 846                                                          - new_bitsize),
 847                                                 NULL_RTX, true,
 848                                                 OPTAB_LIB_WIDEN);
 849
 850           if (!store_bit_field_1 (op0, new_bitsize,
 851                                   bitnum + bit_offset,
 852                                   bitregion_start, bitregion_end,
 853                                   word_mode,
 854                                   value_word, fallback_p))
 855             {
 856               delete_insns_since (last);
 857               return false;
 858             }
 859         }
 860       return true;
 861     }
 862
 863   /* If VALUE has a floating-point or complex mode, access it as an
 864      integer of the corresponding size.  This can occur on a machine
 865      with 64 bit registers that uses SFmode for float.  It can also
 866      occur for unaligned float or complex fields.  */
 867   orig_value = value;
 868   if (GET_MODE (value) != VOIDmode
 869       && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
 870       && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
 871     {
 872       value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value)));
 873       emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value);
 874     }
 875
 876   /* If OP0 is a multi-word register, narrow it to the affected word.
 877      If the region spans two words, defer to store_split_bit_field.  */
 878   if (!MEM_P (op0) && GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
 879     {
 880       op0 = simplify_gen_subreg (word_mode, op0, GET_MODE (op0),
 881                                  bitnum / BITS_PER_WORD * UNITS_PER_WORD);
 882       gcc_assert (op0);
 883       bitnum %= BITS_PER_WORD;
 884       if (bitnum + bitsize > BITS_PER_WORD)
 885         {
 886           if (!fallback_p)
 887             return false;
 888
 889           store_split_bit_field (op0, bitsize, bitnum, bitregion_start,
 890                                  bitregion_end, value);
 891           return true;
 892         }
 893     }
 894
 895   /* From here on we can assume that the field to be stored in fits
 896      within a word.  If the destination is a register, it too fits
 897      in a word.  */
 898
 899   extraction_insn insv;
 900   if (!MEM_P (op0)
 901       && get_best_reg_extraction_insn (&insv, EP_insv,
 902                                        GET_MODE_BITSIZE (GET_MODE (op0)),
 903                                        fieldmode)
 904       && store_bit_field_using_insv (&insv, op0, bitsize, bitnum, value))
 905     return true;
 906
 907   /* If OP0 is a memory, try copying it to a register and seeing if a
 908      cheap register alternative is available.  */
 909   if (MEM_P (op0))
 910     {
 911       if (get_best_mem_extraction_insn (&insv, EP_insv, bitsize, bitnum,
 912                                         fieldmode)
 913           && store_bit_field_using_insv (&insv, op0, bitsize, bitnum, value))
 914         return true;
 915
 916       rtx_insn *last = get_last_insn ();
 917
 918       /* Try loading part of OP0 into a register, inserting the bitfield
 919          into that, and then copying the result back to OP0.  */
 920       unsigned HOST_WIDE_INT bitpos;
 921       rtx xop0 = adjust_bit_field_mem_for_reg (EP_insv, op0, bitsize, bitnum,
 922                                                bitregion_start, bitregion_end,
 923                                                fieldmode, &bitpos);
 924       if (xop0)
 925         {
 926           rtx tempreg = copy_to_reg (xop0);
 927           if (store_bit_field_1 (tempreg, bitsize, bitpos,
 928                                  bitregion_start, bitregion_end,
 929                                  fieldmode, orig_value, false))
 930             {
 931               emit_move_insn (xop0, tempreg);
 932               return true;
 933             }
 934           delete_insns_since (last);
 935         }
 936     }
 937
 938   if (!fallback_p)
 939     return false;
 940
 941   store_fixed_bit_field (op0, bitsize, bitnum, bitregion_start,
 942                          bitregion_end, value);
 943   return true;
 944 }
 945
 946 /* Generate code to store value from rtx VALUE
 947    into a bit-field within structure STR_RTX
 948    containing BITSIZE bits starting at bit BITNUM.
 949
 950    BITREGION_START is bitpos of the first bitfield in this region.
 951    BITREGION_END is the bitpos of the ending bitfield in this region.
 952    These two fields are 0, if the C++ memory model does not apply,
 953    or we are not interested in keeping track of bitfield regions.
 954
 955    FIELDMODE is the machine-mode of the FIELD_DECL node for this field.  */
 956
 957 void
 958 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
 959                  unsigned HOST_WIDE_INT bitnum,
 960                  unsigned HOST_WIDE_INT bitregion_start,
 961                  unsigned HOST_WIDE_INT bitregion_end,
 962                  machine_mode fieldmode,
 963                  rtx value)
 964 {
 965   /* Handle -fstrict-volatile-bitfields in the cases where it applies.  */
 966   if (strict_volatile_bitfield_p (str_rtx, bitsize, bitnum, fieldmode,
 967                                   bitregion_start, bitregion_end))
 968     {
 969       /* Storing of a full word can be done with a simple store.
 970          We know here that the field can be accessed with one single
 971          instruction.  For targets that support unaligned memory,
 972          an unaligned access may be necessary.  */
 973       if (bitsize == GET_MODE_BITSIZE (fieldmode))
 974         {
 975           str_rtx = adjust_bitfield_address (str_rtx, fieldmode,
 976                                              bitnum / BITS_PER_UNIT);
 977           gcc_assert (bitnum % BITS_PER_UNIT == 0);
 978           emit_move_insn (str_rtx, value);
 979         }
 980       else
 981         {
 982           rtx temp;
 983
 984           str_rtx = narrow_bit_field_mem (str_rtx, fieldmode, bitsize, bitnum,
 985                                           &bitnum);
 986           gcc_assert (bitnum + bitsize <= GET_MODE_BITSIZE (fieldmode));
 987           temp = copy_to_reg (str_rtx);
 988           if (!store_bit_field_1 (temp, bitsize, bitnum, 0, 0,
 989                                   fieldmode, value, true))
 990             gcc_unreachable ();
 991
 992           emit_move_insn (str_rtx, temp);
 993         }
 994
 995       return;
 996     }
 997
 998   /* Under the C++0x memory model, we must not touch bits outside the
 999      bit region.  Adjust the address to start at the beginning of the
1000      bit region.  */
1001   if (MEM_P (str_rtx) && bitregion_start > 0)
1002     {
1003       machine_mode bestmode;
1004       HOST_WIDE_INT offset, size;
1005
1006       gcc_assert ((bitregion_start % BITS_PER_UNIT) == 0);
1007
1008       offset = bitregion_start / BITS_PER_UNIT;
1009       bitnum -= bitregion_start;
1010       size = (bitnum + bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT;
1011       bitregion_end -= bitregion_start;
1012       bitregion_start = 0;
1013       bestmode = get_best_mode (bitsize, bitnum,
1014                                 bitregion_start, bitregion_end,
1015                                 MEM_ALIGN (str_rtx), VOIDmode,
1016                                 MEM_VOLATILE_P (str_rtx));
1017       str_rtx = adjust_bitfield_address_size (str_rtx, bestmode, offset, size);
1018     }
1019
1020   if (!store_bit_field_1 (str_rtx, bitsize, bitnum,
1021                           bitregion_start, bitregion_end,
1022                           fieldmode, value, true))
1023     gcc_unreachable ();
1024 }
1025 \f
1026 /* Use shifts and boolean operations to store VALUE into a bit field of
1027    width BITSIZE in OP0, starting at bit BITNUM.  */
1028
1029 static void
1030 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1031                        unsigned HOST_WIDE_INT bitnum,
1032                        unsigned HOST_WIDE_INT bitregion_start,
1033                        unsigned HOST_WIDE_INT bitregion_end,
1034                        rtx value)
1035 {
1036   /* There is a case not handled here:
1037      a structure with a known alignment of just a halfword
1038      and a field split across two aligned halfwords within the structure.
1039      Or likewise a structure with a known alignment of just a byte
1040      and a field split across two bytes.
1041      Such cases are not supposed to be able to occur.  */
1042
1043   if (MEM_P (op0))
1044     {
1045       machine_mode mode = GET_MODE (op0);
1046       if (GET_MODE_BITSIZE (mode) == 0
1047           || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
1048         mode = word_mode;
1049       mode = get_best_mode (bitsize, bitnum, bitregion_start, bitregion_end,
1050                             MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
1051
1052       if (mode == VOIDmode)
1053         {
1054           /* The only way this should occur is if the field spans word
1055              boundaries.  */
1056           store_split_bit_field (op0, bitsize, bitnum, bitregion_start,
1057                                  bitregion_end, value);
1058           return;
1059         }
1060
1061       op0 = narrow_bit_field_mem (op0, mode, bitsize, bitnum, &bitnum);
1062     }
1063
1064   store_fixed_bit_field_1 (op0, bitsize, bitnum, value);
1065 }
1066
1067 /* Helper function for store_fixed_bit_field, stores
1068    the bit field always using the MODE of OP0.  */
1069
1070 static void
1071 store_fixed_bit_field_1 (rtx op0, unsigned HOST_WIDE_INT bitsize,
1072                          unsigned HOST_WIDE_INT bitnum,
1073                          rtx value)
1074 {
1075   machine_mode mode;
1076   rtx temp;
1077   int all_zero = 0;
1078   int all_one = 0;
1079
1080   mode = GET_MODE (op0);
1081   gcc_assert (SCALAR_INT_MODE_P (mode));
1082
1083   /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
1084      for invalid input, such as f5 from gcc.dg/pr48335-2.c.  */
1085
1086   if (BYTES_BIG_ENDIAN)
1087     /* BITNUM is the distance between our msb
1088        and that of the containing datum.
1089        Convert it to the distance from the lsb.  */
1090     bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
1091
1092   /* Now BITNUM is always the distance between our lsb
1093      and that of OP0.  */
1094
1095   /* Shift VALUE left by BITNUM bits.  If VALUE is not constant,
1096      we must first convert its mode to MODE.  */
1097
1098   if (CONST_INT_P (value))
1099     {
1100       unsigned HOST_WIDE_INT v = UINTVAL (value);
1101
1102       if (bitsize < HOST_BITS_PER_WIDE_INT)
1103         v &= ((unsigned HOST_WIDE_INT) 1 << bitsize) - 1;
1104
1105       if (v == 0)
1106         all_zero = 1;
1107       else if ((bitsize < HOST_BITS_PER_WIDE_INT
1108                 && v == ((unsigned HOST_WIDE_INT) 1 << bitsize) - 1)
1109                || (bitsize == HOST_BITS_PER_WIDE_INT
1110                    && v == (unsigned HOST_WIDE_INT) -1))
1111         all_one = 1;
1112
1113       value = lshift_value (mode, v, bitnum);
1114     }
1115   else
1116     {
1117       int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
1118                       && bitnum + bitsize != GET_MODE_BITSIZE (mode));
1119
1120       if (GET_MODE (value) != mode)
1121         value = convert_to_mode (mode, value, 1);
1122
1123       if (must_and)
1124         value = expand_binop (mode, and_optab, value,
1125                               mask_rtx (mode, 0, bitsize, 0),
1126                               NULL_RTX, 1, OPTAB_LIB_WIDEN);
1127       if (bitnum > 0)
1128         value = expand_shift (LSHIFT_EXPR, mode, value,
1129                               bitnum, NULL_RTX, 1);
1130     }
1131
1132   /* Now clear the chosen bits in OP0,
1133      except that if VALUE is -1 we need not bother.  */
1134   /* We keep the intermediates in registers to allow CSE to combine
1135      consecutive bitfield assignments.  */
1136
1137   temp = force_reg (mode, op0);
1138
1139   if (! all_one)
1140     {
1141       temp = expand_binop (mode, and_optab, temp,
1142                            mask_rtx (mode, bitnum, bitsize, 1),
1143                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
1144       temp = force_reg (mode, temp);
1145     }
1146
1147   /* Now logical-or VALUE into OP0, unless it is zero.  */
1148
1149   if (! all_zero)
1150     {
1151       temp = expand_binop (mode, ior_optab, temp, value,
1152                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
1153       temp = force_reg (mode, temp);
1154     }
1155
1156   if (op0 != temp)
1157     {
1158       op0 = copy_rtx (op0);
1159       emit_move_insn (op0, temp);
1160     }
1161 }
1162 \f
1163 /* Store a bit field that is split across multiple accessible memory objects.
1164
1165    OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
1166    BITSIZE is the field width; BITPOS the position of its first bit
1167    (within the word).
1168    VALUE is the value to store.
1169
1170    This does not yet handle fields wider than BITS_PER_WORD.  */
1171
1172 static void
1173 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1174                        unsigned HOST_WIDE_INT bitpos,
1175                        unsigned HOST_WIDE_INT bitregion_start,
1176                        unsigned HOST_WIDE_INT bitregion_end,
1177                        rtx value)
1178 {
1179   unsigned int unit;
1180   unsigned int bitsdone = 0;
1181
1182   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1183      much at a time.  */
1184   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1185     unit = BITS_PER_WORD;
1186   else
1187     unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1188
1189   /* If OP0 is a memory with a mode, then UNIT must not be larger than
1190      OP0's mode as well.  Otherwise, store_fixed_bit_field will call us
1191      again, and we will mutually recurse forever.  */
1192   if (MEM_P (op0) && GET_MODE_BITSIZE (GET_MODE (op0)) > 0)
1193     unit = MIN (unit, GET_MODE_BITSIZE (GET_MODE (op0)));
1194
1195   /* If VALUE is a constant other than a CONST_INT, get it into a register in
1196      WORD_MODE.  If we can do this using gen_lowpart_common, do so.  Note
1197      that VALUE might be a floating-point constant.  */
1198   if (CONSTANT_P (value) && !CONST_INT_P (value))
1199     {
1200       rtx word = gen_lowpart_common (word_mode, value);
1201
1202       if (word && (value != word))
1203         value = word;
1204       else
1205         value = gen_lowpart_common (word_mode,
1206                                     force_reg (GET_MODE (value) != VOIDmode
1207                                                ? GET_MODE (value)
1208                                                : word_mode, value));
1209     }
1210
1211   while (bitsdone < bitsize)
1212     {
1213       unsigned HOST_WIDE_INT thissize;
1214       rtx part, word;
1215       unsigned HOST_WIDE_INT thispos;
1216       unsigned HOST_WIDE_INT offset;
1217
1218       offset = (bitpos + bitsdone) / unit;
1219       thispos = (bitpos + bitsdone) % unit;
1220
1221       /* When region of bytes we can touch is restricted, decrease
1222          UNIT close to the end of the region as needed.  If op0 is a REG
1223          or SUBREG of REG, don't do this, as there can't be data races
1224          on a register and we can expand shorter code in some cases.  */
1225       if (bitregion_end
1226           && unit > BITS_PER_UNIT
1227           && bitpos + bitsdone - thispos + unit > bitregion_end + 1
1228           && !REG_P (op0)
1229           && (GET_CODE (op0) != SUBREG || !REG_P (SUBREG_REG (op0))))
1230         {
1231           unit = unit / 2;
1232           continue;
1233         }
1234
1235       /* THISSIZE must not overrun a word boundary.  Otherwise,
1236          store_fixed_bit_field will call us again, and we will mutually
1237          recurse forever.  */
1238       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1239       thissize = MIN (thissize, unit - thispos);
1240
1241       if (BYTES_BIG_ENDIAN)
1242         {
1243           /* Fetch successively less significant portions.  */
1244           if (CONST_INT_P (value))
1245             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1246                              >> (bitsize - bitsdone - thissize))
1247                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1248           else
1249             {
1250               int total_bits = GET_MODE_BITSIZE (GET_MODE (value));
1251               /* The args are chosen so that the last part includes the
1252                  lsb.  Give extract_bit_field the value it needs (with
1253                  endianness compensation) to fetch the piece we want.  */
1254               part = extract_fixed_bit_field (word_mode, value, thissize,
1255                                               total_bits - bitsize + bitsdone,
1256                                               NULL_RTX, 1);
1257             }
1258         }
1259       else
1260         {
1261           /* Fetch successively more significant portions.  */
1262           if (CONST_INT_P (value))
1263             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1264                              >> bitsdone)
1265                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1266           else
1267             part = extract_fixed_bit_field (word_mode, value, thissize,
1268                                             bitsdone, NULL_RTX, 1);
1269         }
1270
1271       /* If OP0 is a register, then handle OFFSET here.
1272
1273          When handling multiword bitfields, extract_bit_field may pass
1274          down a word_mode SUBREG of a larger REG for a bitfield that actually
1275          crosses a word boundary.  Thus, for a SUBREG, we must find
1276          the current word starting from the base register.  */
1277       if (GET_CODE (op0) == SUBREG)
1278         {
1279           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD)
1280                             + (offset * unit / BITS_PER_WORD);
1281           machine_mode sub_mode = GET_MODE (SUBREG_REG (op0));
1282           if (sub_mode != BLKmode && GET_MODE_SIZE (sub_mode) < UNITS_PER_WORD)
1283             word = word_offset ? const0_rtx : op0;
1284           else
1285             word = operand_subword_force (SUBREG_REG (op0), word_offset,
1286                                           GET_MODE (SUBREG_REG (op0)));
1287           offset &= BITS_PER_WORD / unit - 1;
1288         }
1289       else if (REG_P (op0))
1290         {
1291           machine_mode op0_mode = GET_MODE (op0);
1292           if (op0_mode != BLKmode && GET_MODE_SIZE (op0_mode) < UNITS_PER_WORD)
1293             word = offset ? const0_rtx : op0;
1294           else
1295             word = operand_subword_force (op0, offset * unit / BITS_PER_WORD,
1296                                           GET_MODE (op0));
1297           offset &= BITS_PER_WORD / unit - 1;
1298         }
1299       else
1300         word = op0;
1301
1302       /* OFFSET is in UNITs, and UNIT is in bits.  If WORD is const0_rtx,
1303          it is just an out-of-bounds access.  Ignore it.  */
1304       if (word != const0_rtx)
1305         store_fixed_bit_field (word, thissize, offset * unit + thispos,
1306                                bitregion_start, bitregion_end, part);
1307       bitsdone += thissize;
1308     }
1309 }
1310 \f
1311 /* A subroutine of extract_bit_field_1 that converts return value X
1312    to either MODE or TMODE.  MODE, TMODE and UNSIGNEDP are arguments
1313    to extract_bit_field.  */
1314
1315 static rtx
1316 convert_extracted_bit_field (rtx x, machine_mode mode,
1317                              machine_mode tmode, bool unsignedp)
1318 {
1319   if (GET_MODE (x) == tmode || GET_MODE (x) == mode)
1320     return x;
1321
1322   /* If the x mode is not a scalar integral, first convert to the
1323      integer mode of that size and then access it as a floating-point
1324      value via a SUBREG.  */
1325   if (!SCALAR_INT_MODE_P (tmode))
1326     {
1327       machine_mode smode;
1328
1329       smode = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0);
1330       x = convert_to_mode (smode, x, unsignedp);
1331       x = force_reg (smode, x);
1332       return gen_lowpart (tmode, x);
1333     }
1334
1335   return convert_to_mode (tmode, x, unsignedp);
1336 }
1337
1338 /* Try to use an ext(z)v pattern to extract a field from OP0.
1339    Return the extracted value on success, otherwise return null.
1340    EXT_MODE is the mode of the extraction and the other arguments
1341    are as for extract_bit_field.  */
1342
1343 static rtx
1344 extract_bit_field_using_extv (const extraction_insn *extv, rtx op0,
1345                               unsigned HOST_WIDE_INT bitsize,
1346                               unsigned HOST_WIDE_INT bitnum,
1347                               int unsignedp, rtx target,
1348                               machine_mode mode, machine_mode tmode)
1349 {
1350   struct expand_operand ops[4];
1351   rtx spec_target = target;
1352   rtx spec_target_subreg = 0;
1353   machine_mode ext_mode = extv->field_mode;
1354   unsigned unit = GET_MODE_BITSIZE (ext_mode);
1355
1356   if (bitsize == 0 || unit < bitsize)
1357     return NULL_RTX;
1358
1359   if (MEM_P (op0))
1360     /* Get a reference to the first byte of the field.  */
1361     op0 = narrow_bit_field_mem (op0, extv->struct_mode, bitsize, bitnum,
1362                                 &bitnum);
1363   else
1364     {
1365       /* Convert from counting within OP0 to counting in EXT_MODE.  */
1366       if (BYTES_BIG_ENDIAN)
1367         bitnum += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1368
1369       /* If op0 is a register, we need it in EXT_MODE to make it
1370          acceptable to the format of ext(z)v.  */
1371       if (GET_CODE (op0) == SUBREG && GET_MODE (op0) != ext_mode)
1372         return NULL_RTX;
1373       if (REG_P (op0) && GET_MODE (op0) != ext_mode)
1374         op0 = gen_lowpart_SUBREG (ext_mode, op0);
1375     }
1376
1377   /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
1378      "backwards" from the size of the unit we are extracting from.
1379      Otherwise, we count bits from the most significant on a
1380      BYTES/BITS_BIG_ENDIAN machine.  */
1381
1382   if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1383     bitnum = unit - bitsize - bitnum;
1384
1385   if (target == 0)
1386     target = spec_target = gen_reg_rtx (tmode);
1387
1388   if (GET_MODE (target) != ext_mode)
1389     {
1390       /* Don't use LHS paradoxical subreg if explicit truncation is needed
1391          between the mode of the extraction (word_mode) and the target
1392          mode.  Instead, create a temporary and use convert_move to set
1393          the target.  */
1394       if (REG_P (target)
1395           && TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (target), ext_mode))
1396         {
1397           target = gen_lowpart (ext_mode, target);
1398           if (GET_MODE_PRECISION (ext_mode)
1399               > GET_MODE_PRECISION (GET_MODE (spec_target)))
1400             spec_target_subreg = target;
1401         }
1402       else
1403         target = gen_reg_rtx (ext_mode);
1404     }
1405
1406   create_output_operand (&ops[0], target, ext_mode);
1407   create_fixed_operand (&ops[1], op0);
1408   create_integer_operand (&ops[2], bitsize);
1409   create_integer_operand (&ops[3], bitnum);
1410   if (maybe_expand_insn (extv->icode, 4, ops))
1411     {
1412       target = ops[0].value;
1413       if (target == spec_target)
1414         return target;
1415       if (target == spec_target_subreg)
1416         return spec_target;
1417       return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1418     }
1419   return NULL_RTX;
1420 }
1421
1422 /* A subroutine of extract_bit_field, with the same arguments.
1423    If FALLBACK_P is true, fall back to extract_fixed_bit_field
1424    if we can find no other means of implementing the operation.
1425    if FALLBACK_P is false, return NULL instead.  */
1426
1427 static rtx
1428 extract_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1429                      unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1430                      machine_mode mode, machine_mode tmode,
1431                      bool fallback_p)
1432 {
1433   rtx op0 = str_rtx;
1434   machine_mode int_mode;
1435   machine_mode mode1;
1436
1437   if (tmode == VOIDmode)
1438     tmode = mode;
1439
1440   while (GET_CODE (op0) == SUBREG)
1441     {
1442       bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1443       op0 = SUBREG_REG (op0);
1444     }
1445
1446   /* If we have an out-of-bounds access to a register, just return an
1447      uninitialized register of the required mode.  This can occur if the
1448      source code contains an out-of-bounds access to a small array.  */
1449   if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
1450     return gen_reg_rtx (tmode);
1451
1452   if (REG_P (op0)
1453       && mode == GET_MODE (op0)
1454       && bitnum == 0
1455       && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1456     {
1457       /* We're trying to extract a full register from itself.  */
1458       return op0;
1459     }
1460
1461   /* See if we can get a better vector mode before extracting.  */
1462   if (VECTOR_MODE_P (GET_MODE (op0))
1463       && !MEM_P (op0)
1464       && GET_MODE_INNER (GET_MODE (op0)) != tmode)
1465     {
1466       machine_mode new_mode;
1467
1468       if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1469         new_mode = MIN_MODE_VECTOR_FLOAT;
1470       else if (GET_MODE_CLASS (tmode) == MODE_FRACT)
1471         new_mode = MIN_MODE_VECTOR_FRACT;
1472       else if (GET_MODE_CLASS (tmode) == MODE_UFRACT)
1473         new_mode = MIN_MODE_VECTOR_UFRACT;
1474       else if (GET_MODE_CLASS (tmode) == MODE_ACCUM)
1475         new_mode = MIN_MODE_VECTOR_ACCUM;
1476       else if (GET_MODE_CLASS (tmode) == MODE_UACCUM)
1477         new_mode = MIN_MODE_VECTOR_UACCUM;
1478       else
1479         new_mode = MIN_MODE_VECTOR_INT;
1480
1481       for (; new_mode != VOIDmode ; new_mode = GET_MODE_WIDER_MODE (new_mode))
1482         if (GET_MODE_SIZE (new_mode) == GET_MODE_SIZE (GET_MODE (op0))
1483             && targetm.vector_mode_supported_p (new_mode))
1484           break;
1485       if (new_mode != VOIDmode)
1486         op0 = gen_lowpart (new_mode, op0);
1487     }
1488
1489   /* Use vec_extract patterns for extracting parts of vectors whenever
1490      available.  */
1491   if (VECTOR_MODE_P (GET_MODE (op0))
1492       && !MEM_P (op0)
1493       && optab_handler (vec_extract_optab, GET_MODE (op0)) != CODE_FOR_nothing
1494       && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1495           == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1496     {
1497       struct expand_operand ops[3];
1498       machine_mode outermode = GET_MODE (op0);
1499       machine_mode innermode = GET_MODE_INNER (outermode);
1500       enum insn_code icode = optab_handler (vec_extract_optab, outermode);
1501       unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode);
1502
1503       create_output_operand (&ops[0], target, innermode);
1504       create_input_operand (&ops[1], op0, outermode);
1505       create_integer_operand (&ops[2], pos);
1506       if (maybe_expand_insn (icode, 3, ops))
1507         {
1508           target = ops[0].value;
1509           if (GET_MODE (target) != mode)
1510             return gen_lowpart (tmode, target);
1511           return target;
1512         }
1513     }
1514
1515   /* Make sure we are playing with integral modes.  Pun with subregs
1516      if we aren't.  */
1517   {
1518     machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1519     if (imode != GET_MODE (op0))
1520       {
1521         if (MEM_P (op0))
1522           op0 = adjust_bitfield_address_size (op0, imode, 0, MEM_SIZE (op0));
1523         else if (imode != BLKmode)
1524           {
1525             op0 = gen_lowpart (imode, op0);
1526
1527             /* If we got a SUBREG, force it into a register since we
1528                aren't going to be able to do another SUBREG on it.  */
1529             if (GET_CODE (op0) == SUBREG)
1530               op0 = force_reg (imode, op0);
1531           }
1532         else if (REG_P (op0))
1533           {
1534             rtx reg, subreg;
1535             imode = smallest_mode_for_size (GET_MODE_BITSIZE (GET_MODE (op0)),
1536                                             MODE_INT);
1537             reg = gen_reg_rtx (imode);
1538             subreg = gen_lowpart_SUBREG (GET_MODE (op0), reg);
1539             emit_move_insn (subreg, op0);
1540             op0 = reg;
1541             bitnum += SUBREG_BYTE (subreg) * BITS_PER_UNIT;
1542           }
1543         else
1544           {
1545             HOST_WIDE_INT size = GET_MODE_SIZE (GET_MODE (op0));
1546             rtx mem = assign_stack_temp (GET_MODE (op0), size);
1547             emit_move_insn (mem, op0);
1548             op0 = adjust_bitfield_address_size (mem, BLKmode, 0, size);
1549           }
1550       }
1551   }
1552
1553   /* ??? We currently assume TARGET is at least as big as BITSIZE.
1554      If that's wrong, the solution is to test for it and set TARGET to 0
1555      if needed.  */
1556
1557   /* Get the mode of the field to use for atomic access or subreg
1558      conversion.  */
1559   mode1 = mode;
1560   if (SCALAR_INT_MODE_P (tmode))
1561     {
1562       machine_mode try_mode = mode_for_size (bitsize,
1563                                                   GET_MODE_CLASS (tmode), 0);
1564       if (try_mode != BLKmode)
1565         mode1 = try_mode;
1566     }
1567   gcc_assert (mode1 != BLKmode);
1568
1569   /* Extraction of a full MODE1 value can be done with a subreg as long
1570      as the least significant bit of the value is the least significant
1571      bit of either OP0 or a word of OP0.  */
1572   if (!MEM_P (op0)
1573       && lowpart_bit_field_p (bitnum, bitsize, GET_MODE (op0))
1574       && bitsize == GET_MODE_BITSIZE (mode1)
1575       && TRULY_NOOP_TRUNCATION_MODES_P (mode1, GET_MODE (op0)))
1576     {
1577       rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0),
1578                                      bitnum / BITS_PER_UNIT);
1579       if (sub)
1580         return convert_extracted_bit_field (sub, mode, tmode, unsignedp);
1581     }
1582
1583   /* Extraction of a full MODE1 value can be done with a load as long as
1584      the field is on a byte boundary and is sufficiently aligned.  */
1585   if (simple_mem_bitfield_p (op0, bitsize, bitnum, mode1))
1586     {
1587       op0 = adjust_bitfield_address (op0, mode1, bitnum / BITS_PER_UNIT);
1588       return convert_extracted_bit_field (op0, mode, tmode, unsignedp);
1589     }
1590
1591   /* Handle fields bigger than a word.  */
1592
1593   if (bitsize > BITS_PER_WORD)
1594     {
1595       /* Here we transfer the words of the field
1596          in the order least significant first.
1597          This is because the most significant word is the one which may
1598          be less than full.  */
1599
1600       unsigned int backwards = WORDS_BIG_ENDIAN;
1601       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1602       unsigned int i;
1603       rtx_insn *last;
1604
1605       if (target == 0 || !REG_P (target) || !valid_multiword_target_p (target))
1606         target = gen_reg_rtx (mode);
1607
1608       /* In case we're about to clobber a base register or something
1609          (see gcc.c-torture/execute/20040625-1.c).   */
1610       if (reg_mentioned_p (target, str_rtx))
1611         target = gen_reg_rtx (mode);
1612
1613       /* Indicate for flow that the entire target reg is being set.  */
1614       emit_clobber (target);
1615
1616       last = get_last_insn ();
1617       for (i = 0; i < nwords; i++)
1618         {
1619           /* If I is 0, use the low-order word in both field and target;
1620              if I is 1, use the next to lowest word; and so on.  */
1621           /* Word number in TARGET to use.  */
1622           unsigned int wordnum
1623             = (backwards
1624                ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1625                : i);
1626           /* Offset from start of field in OP0.  */
1627           unsigned int bit_offset = (backwards
1628                                      ? MAX ((int) bitsize - ((int) i + 1)
1629                                             * BITS_PER_WORD,
1630                                             0)
1631                                      : (int) i * BITS_PER_WORD);
1632           rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1633           rtx result_part
1634             = extract_bit_field_1 (op0, MIN (BITS_PER_WORD,
1635                                              bitsize - i * BITS_PER_WORD),
1636                                    bitnum + bit_offset, 1, target_part,
1637                                    mode, word_mode, fallback_p);
1638
1639           gcc_assert (target_part);
1640           if (!result_part)
1641             {
1642               delete_insns_since (last);
1643               return NULL;
1644             }
1645
1646           if (result_part != target_part)
1647             emit_move_insn (target_part, result_part);
1648         }
1649
1650       if (unsignedp)
1651         {
1652           /* Unless we've filled TARGET, the upper regs in a multi-reg value
1653              need to be zero'd out.  */
1654           if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1655             {
1656               unsigned int i, total_words;
1657
1658               total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1659               for (i = nwords; i < total_words; i++)
1660                 emit_move_insn
1661                   (operand_subword (target,
1662                                     backwards ? total_words - i - 1 : i,
1663                                     1, VOIDmode),
1664                    const0_rtx);
1665             }
1666           return target;
1667         }
1668
1669       /* Signed bit field: sign-extend with two arithmetic shifts.  */
1670       target = expand_shift (LSHIFT_EXPR, mode, target,
1671                              GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1672       return expand_shift (RSHIFT_EXPR, mode, target,
1673                            GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1674     }
1675
1676   /* If OP0 is a multi-word register, narrow it to the affected word.
1677      If the region spans two words, defer to extract_split_bit_field.  */
1678   if (!MEM_P (op0) && GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1679     {
1680       op0 = simplify_gen_subreg (word_mode, op0, GET_MODE (op0),
1681                                  bitnum / BITS_PER_WORD * UNITS_PER_WORD);
1682       bitnum %= BITS_PER_WORD;
1683       if (bitnum + bitsize > BITS_PER_WORD)
1684         {
1685           if (!fallback_p)
1686             return NULL_RTX;
1687           target = extract_split_bit_field (op0, bitsize, bitnum, unsignedp);
1688           return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1689         }
1690     }
1691
1692   /* From here on we know the desired field is smaller than a word.
1693      If OP0 is a register, it too fits within a word.  */
1694   enum extraction_pattern pattern = unsignedp ? EP_extzv : EP_extv;
1695   extraction_insn extv;
1696   if (!MEM_P (op0)
1697       /* ??? We could limit the structure size to the part of OP0 that
1698          contains the field, with appropriate checks for endianness
1699          and TRULY_NOOP_TRUNCATION.  */
1700       && get_best_reg_extraction_insn (&extv, pattern,
1701                                        GET_MODE_BITSIZE (GET_MODE (op0)),
1702                                        tmode))
1703     {
1704       rtx result = extract_bit_field_using_extv (&extv, op0, bitsize, bitnum,
1705                                                  unsignedp, target, mode,
1706                                                  tmode);
1707       if (result)
1708         return result;
1709     }
1710
1711   /* If OP0 is a memory, try copying it to a register and seeing if a
1712      cheap register alternative is available.  */
1713   if (MEM_P (op0))
1714     {
1715       if (get_best_mem_extraction_insn (&extv, pattern, bitsize, bitnum,
1716                                         tmode))
1717         {
1718           rtx result = extract_bit_field_using_extv (&extv, op0, bitsize,
1719                                                      bitnum, unsignedp,
1720                                                      target, mode,
1721                                                      tmode);
1722           if (result)
1723             return result;
1724         }
1725
1726       rtx_insn *last = get_last_insn ();
1727
1728       /* Try loading part of OP0 into a register and extracting the
1729          bitfield from that.  */
1730       unsigned HOST_WIDE_INT bitpos;
1731       rtx xop0 = adjust_bit_field_mem_for_reg (pattern, op0, bitsize, bitnum,
1732                                                0, 0, tmode, &bitpos);
1733       if (xop0)
1734         {
1735           xop0 = copy_to_reg (xop0);
1736           rtx result = extract_bit_field_1 (xop0, bitsize, bitpos,
1737                                             unsignedp, target,
1738                                             mode, tmode, false);
1739           if (result)
1740             return result;
1741           delete_insns_since (last);
1742         }
1743     }
1744
1745   if (!fallback_p)
1746     return NULL;
1747
1748   /* Find a correspondingly-sized integer field, so we can apply
1749      shifts and masks to it.  */
1750   int_mode = int_mode_for_mode (tmode);
1751   if (int_mode == BLKmode)
1752     int_mode = int_mode_for_mode (mode);
1753   /* Should probably push op0 out to memory and then do a load.  */
1754   gcc_assert (int_mode != BLKmode);
1755
1756   target = extract_fixed_bit_field (int_mode, op0, bitsize, bitnum,
1757                                     target, unsignedp);
1758   return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1759 }
1760
1761 /* Generate code to extract a byte-field from STR_RTX
1762    containing BITSIZE bits, starting at BITNUM,
1763    and put it in TARGET if possible (if TARGET is nonzero).
1764    Regardless of TARGET, we return the rtx for where the value is placed.
1765
1766    STR_RTX is the structure containing the byte (a REG or MEM).
1767    UNSIGNEDP is nonzero if this is an unsigned bit field.
1768    MODE is the natural mode of the field value once extracted.
1769    TMODE is the mode the caller would like the value to have;
1770    but the value may be returned with type MODE instead.
1771
1772    If a TARGET is specified and we can store in it at no extra cost,
1773    we do so, and return TARGET.
1774    Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1775    if they are equally easy.  */
1776
1777 rtx
1778 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1779                    unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1780                    machine_mode mode, machine_mode tmode)
1781 {
1782   machine_mode mode1;
1783
1784   /* Handle -fstrict-volatile-bitfields in the cases where it applies.  */
1785   if (GET_MODE_BITSIZE (GET_MODE (str_rtx)) > 0)
1786     mode1 = GET_MODE (str_rtx);
1787   else if (target && GET_MODE_BITSIZE (GET_MODE (target)) > 0)
1788     mode1 = GET_MODE (target);
1789   else
1790     mode1 = tmode;
1791
1792   if (strict_volatile_bitfield_p (str_rtx, bitsize, bitnum, mode1, 0, 0))
1793     {
1794       /* Extraction of a full MODE1 value can be done with a simple load.
1795          We know here that the field can be accessed with one single
1796          instruction.  For targets that support unaligned memory,
1797          an unaligned access may be necessary.  */
1798       if (bitsize == GET_MODE_BITSIZE (mode1))
1799         {
1800           rtx result = adjust_bitfield_address (str_rtx, mode1,
1801                                                 bitnum / BITS_PER_UNIT);
1802           gcc_assert (bitnum % BITS_PER_UNIT == 0);
1803           return convert_extracted_bit_field (result, mode, tmode, unsignedp);
1804         }
1805
1806       str_rtx = narrow_bit_field_mem (str_rtx, mode1, bitsize, bitnum,
1807                                       &bitnum);
1808       gcc_assert (bitnum + bitsize <= GET_MODE_BITSIZE (mode1));
1809       str_rtx = copy_to_reg (str_rtx);
1810     }
1811
1812   return extract_bit_field_1 (str_rtx, bitsize, bitnum, unsignedp,
1813                               target, mode, tmode, true);
1814 }
1815 \f
1816 /* Use shifts and boolean operations to extract a field of BITSIZE bits
1817    from bit BITNUM of OP0.
1818
1819    UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1820    If TARGET is nonzero, attempts to store the value there
1821    and return TARGET, but this is not guaranteed.
1822    If TARGET is not used, create a pseudo-reg of mode TMODE for the value.  */
1823
1824 static rtx
1825 extract_fixed_bit_field (machine_mode tmode, rtx op0,
1826                          unsigned HOST_WIDE_INT bitsize,
1827                          unsigned HOST_WIDE_INT bitnum, rtx target,
1828                          int unsignedp)
1829 {
1830   if (MEM_P (op0))
1831     {
1832       machine_mode mode
1833         = get_best_mode (bitsize, bitnum, 0, 0, MEM_ALIGN (op0), word_mode,
1834                          MEM_VOLATILE_P (op0));
1835
1836       if (mode == VOIDmode)
1837         /* The only way this should occur is if the field spans word
1838            boundaries.  */
1839         return extract_split_bit_field (op0, bitsize, bitnum, unsignedp);
1840
1841       op0 = narrow_bit_field_mem (op0, mode, bitsize, bitnum, &bitnum);
1842     }
1843
1844   return extract_fixed_bit_field_1 (tmode, op0, bitsize, bitnum,
1845                                     target, unsignedp);
1846 }
1847
1848 /* Helper function for extract_fixed_bit_field, extracts
1849    the bit field always using the MODE of OP0.  */
1850
1851 static rtx
1852 extract_fixed_bit_field_1 (machine_mode tmode, rtx op0,
1853                            unsigned HOST_WIDE_INT bitsize,
1854                            unsigned HOST_WIDE_INT bitnum, rtx target,
1855                            int unsignedp)
1856 {
1857   machine_mode mode = GET_MODE (op0);
1858   gcc_assert (SCALAR_INT_MODE_P (mode));
1859
1860   /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
1861      for invalid input, such as extract equivalent of f5 from
1862      gcc.dg/pr48335-2.c.  */
1863
1864   if (BYTES_BIG_ENDIAN)
1865     /* BITNUM is the distance between our msb and that of OP0.
1866        Convert it to the distance from the lsb.  */
1867     bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
1868
1869   /* Now BITNUM is always the distance between the field's lsb and that of OP0.
1870      We have reduced the big-endian case to the little-endian case.  */
1871
1872   if (unsignedp)
1873     {
1874       if (bitnum)
1875         {
1876           /* If the field does not already start at the lsb,
1877              shift it so it does.  */
1878           /* Maybe propagate the target for the shift.  */
1879           rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1880           if (tmode != mode)
1881             subtarget = 0;
1882           op0 = expand_shift (RSHIFT_EXPR, mode, op0, bitnum, subtarget, 1);
1883         }
1884       /* Convert the value to the desired mode.  */
1885       if (mode != tmode)
1886         op0 = convert_to_mode (tmode, op0, 1);
1887
1888       /* Unless the msb of the field used to be the msb when we shifted,
1889          mask out the upper bits.  */
1890
1891       if (GET_MODE_BITSIZE (mode) != bitnum + bitsize)
1892         return expand_binop (GET_MODE (op0), and_optab, op0,
1893                              mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1894                              target, 1, OPTAB_LIB_WIDEN);
1895       return op0;
1896     }
1897
1898   /* To extract a signed bit-field, first shift its msb to the msb of the word,
1899      then arithmetic-shift its lsb to the lsb of the word.  */
1900   op0 = force_reg (mode, op0);
1901
1902   /* Find the narrowest integer mode that contains the field.  */
1903
1904   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1905        mode = GET_MODE_WIDER_MODE (mode))
1906     if (GET_MODE_BITSIZE (mode) >= bitsize + bitnum)
1907       {
1908         op0 = convert_to_mode (mode, op0, 0);
1909         break;
1910       }
1911
1912   if (mode != tmode)
1913     target = 0;
1914
1915   if (GET_MODE_BITSIZE (mode) != (bitsize + bitnum))
1916     {
1917       int amount = GET_MODE_BITSIZE (mode) - (bitsize + bitnum);
1918       /* Maybe propagate the target for the shift.  */
1919       rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1920       op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1921     }
1922
1923   return expand_shift (RSHIFT_EXPR, mode, op0,
1924                        GET_MODE_BITSIZE (mode) - bitsize, target, 0);
1925 }
1926
1927 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1928    VALUE << BITPOS.  */
1929
1930 static rtx
1931 lshift_value (machine_mode mode, unsigned HOST_WIDE_INT value,
1932               int bitpos)
1933 {
1934   return immed_wide_int_const (wi::lshift (value, bitpos), mode);
1935 }
1936 \f
1937 /* Extract a bit field that is split across two words
1938    and return an RTX for the result.
1939
1940    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1941    BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1942    UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.  */
1943
1944 static rtx
1945 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1946                          unsigned HOST_WIDE_INT bitpos, int unsignedp)
1947 {
1948   unsigned int unit;
1949   unsigned int bitsdone = 0;
1950   rtx result = NULL_RTX;
1951   int first = 1;
1952
1953   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1954      much at a time.  */
1955   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1956     unit = BITS_PER_WORD;
1957   else
1958     unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1959
1960   while (bitsdone < bitsize)
1961     {
1962       unsigned HOST_WIDE_INT thissize;
1963       rtx part, word;
1964       unsigned HOST_WIDE_INT thispos;
1965       unsigned HOST_WIDE_INT offset;
1966
1967       offset = (bitpos + bitsdone) / unit;
1968       thispos = (bitpos + bitsdone) % unit;
1969
1970       /* THISSIZE must not overrun a word boundary.  Otherwise,
1971          extract_fixed_bit_field will call us again, and we will mutually
1972          recurse forever.  */
1973       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1974       thissize = MIN (thissize, unit - thispos);
1975
1976       /* If OP0 is a register, then handle OFFSET here.
1977
1978          When handling multiword bitfields, extract_bit_field may pass
1979          down a word_mode SUBREG of a larger REG for a bitfield that actually
1980          crosses a word boundary.  Thus, for a SUBREG, we must find
1981          the current word starting from the base register.  */
1982       if (GET_CODE (op0) == SUBREG)
1983         {
1984           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1985           word = operand_subword_force (SUBREG_REG (op0), word_offset,
1986                                         GET_MODE (SUBREG_REG (op0)));
1987           offset = 0;
1988         }
1989       else if (REG_P (op0))
1990         {
1991           word = operand_subword_force (op0, offset, GET_MODE (op0));
1992           offset = 0;
1993         }
1994       else
1995         word = op0;
1996
1997       /* Extract the parts in bit-counting order,
1998          whose meaning is determined by BYTES_PER_UNIT.
1999          OFFSET is in UNITs, and UNIT is in bits.  */
2000       part = extract_fixed_bit_field (word_mode, word, thissize,
2001                                       offset * unit + thispos, 0, 1);
2002       bitsdone += thissize;
2003
2004       /* Shift this part into place for the result.  */
2005       if (BYTES_BIG_ENDIAN)
2006         {
2007           if (bitsize != bitsdone)
2008             part = expand_shift (LSHIFT_EXPR, word_mode, part,
2009                                  bitsize - bitsdone, 0, 1);
2010         }
2011       else
2012         {
2013           if (bitsdone != thissize)
2014             part = expand_shift (LSHIFT_EXPR, word_mode, part,
2015                                  bitsdone - thissize, 0, 1);
2016         }
2017
2018       if (first)
2019         result = part;
2020       else
2021         /* Combine the parts with bitwise or.  This works
2022            because we extracted each part as an unsigned bit field.  */
2023         result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
2024                                OPTAB_LIB_WIDEN);
2025
2026       first = 0;
2027     }
2028
2029   /* Unsigned bit field: we are done.  */
2030   if (unsignedp)
2031     return result;
2032   /* Signed bit field: sign-extend with two arithmetic shifts.  */
2033   result = expand_shift (LSHIFT_EXPR, word_mode, result,
2034                          BITS_PER_WORD - bitsize, NULL_RTX, 0);
2035   return expand_shift (RSHIFT_EXPR, word_mode, result,
2036                        BITS_PER_WORD - bitsize, NULL_RTX, 0);
2037 }
2038 \f
2039 /* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
2040    the bit pattern.  SRC_MODE is the mode of SRC; if this is smaller than
2041    MODE, fill the upper bits with zeros.  Fail if the layout of either
2042    mode is unknown (as for CC modes) or if the extraction would involve
2043    unprofitable mode punning.  Return the value on success, otherwise
2044    return null.
2045
2046    This is different from gen_lowpart* in these respects:
2047
2048      - the returned value must always be considered an rvalue
2049
2050      - when MODE is wider than SRC_MODE, the extraction involves
2051        a zero extension
2052
2053      - when MODE is smaller than SRC_MODE, the extraction involves
2054        a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
2055
2056    In other words, this routine performs a computation, whereas the
2057    gen_lowpart* routines are conceptually lvalue or rvalue subreg
2058    operations.  */
2059
2060 rtx
2061 extract_low_bits (machine_mode mode, machine_mode src_mode, rtx src)
2062 {
2063   machine_mode int_mode, src_int_mode;
2064
2065   if (mode == src_mode)
2066     return src;
2067
2068   if (CONSTANT_P (src))
2069     {
2070       /* simplify_gen_subreg can't be used here, as if simplify_subreg
2071          fails, it will happily create (subreg (symbol_ref)) or similar
2072          invalid SUBREGs.  */
2073       unsigned int byte = subreg_lowpart_offset (mode, src_mode);
2074       rtx ret = simplify_subreg (mode, src, src_mode, byte);
2075       if (ret)
2076         return ret;
2077
2078       if (GET_MODE (src) == VOIDmode
2079           || !validate_subreg (mode, src_mode, src, byte))
2080         return NULL_RTX;
2081
2082       src = force_reg (GET_MODE (src), src);
2083       return gen_rtx_SUBREG (mode, src, byte);
2084     }
2085
2086   if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
2087     return NULL_RTX;
2088
2089   if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
2090       && MODES_TIEABLE_P (mode, src_mode))
2091     {
2092       rtx x = gen_lowpart_common (mode, src);
2093       if (x)
2094         return x;
2095     }
2096
2097   src_int_mode = int_mode_for_mode (src_mode);
2098   int_mode = int_mode_for_mode (mode);
2099   if (src_int_mode == BLKmode || int_mode == BLKmode)
2100     return NULL_RTX;
2101
2102   if (!MODES_TIEABLE_P (src_int_mode, src_mode))
2103     return NULL_RTX;
2104   if (!MODES_TIEABLE_P (int_mode, mode))
2105     return NULL_RTX;
2106
2107   src = gen_lowpart (src_int_mode, src);
2108   src = convert_modes (int_mode, src_int_mode, src, true);
2109   src = gen_lowpart (mode, src);
2110   return src;
2111 }
2112 \f
2113 /* Add INC into TARGET.  */
2114
2115 void
2116 expand_inc (rtx target, rtx inc)
2117 {
2118   rtx value = expand_binop (GET_MODE (target), add_optab,
2119                             target, inc,
2120                             target, 0, OPTAB_LIB_WIDEN);
2121   if (value != target)
2122     emit_move_insn (target, value);
2123 }
2124
2125 /* Subtract DEC from TARGET.  */
2126
2127 void
2128 expand_dec (rtx target, rtx dec)
2129 {
2130   rtx value = expand_binop (GET_MODE (target), sub_optab,
2131                             target, dec,
2132                             target, 0, OPTAB_LIB_WIDEN);
2133   if (value != target)
2134     emit_move_insn (target, value);
2135 }
2136 \f
2137 /* Output a shift instruction for expression code CODE,
2138    with SHIFTED being the rtx for the value to shift,
2139    and AMOUNT the rtx for the amount to shift by.
2140    Store the result in the rtx TARGET, if that is convenient.
2141    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2142    Return the rtx for where the value is.  */
2143
2144 static rtx
2145 expand_shift_1 (enum tree_code code, machine_mode mode, rtx shifted,
2146                 rtx amount, rtx target, int unsignedp)
2147 {
2148   rtx op1, temp = 0;
2149   int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2150   int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2151   optab lshift_optab = ashl_optab;
2152   optab rshift_arith_optab = ashr_optab;
2153   optab rshift_uns_optab = lshr_optab;
2154   optab lrotate_optab = rotl_optab;
2155   optab rrotate_optab = rotr_optab;
2156   machine_mode op1_mode;
2157   machine_mode scalar_mode = mode;
2158   int attempt;
2159   bool speed = optimize_insn_for_speed_p ();
2160
2161   if (VECTOR_MODE_P (mode))
2162     scalar_mode = GET_MODE_INNER (mode);
2163   op1 = amount;
2164   op1_mode = GET_MODE (op1);
2165
2166   /* Determine whether the shift/rotate amount is a vector, or scalar.  If the
2167      shift amount is a vector, use the vector/vector shift patterns.  */
2168   if (VECTOR_MODE_P (mode) && VECTOR_MODE_P (op1_mode))
2169     {
2170       lshift_optab = vashl_optab;
2171       rshift_arith_optab = vashr_optab;
2172       rshift_uns_optab = vlshr_optab;
2173       lrotate_optab = vrotl_optab;
2174       rrotate_optab = vrotr_optab;
2175     }
2176
2177   /* Previously detected shift-counts computed by NEGATE_EXPR
2178      and shifted in the other direction; but that does not work
2179      on all machines.  */
2180
2181   if (SHIFT_COUNT_TRUNCATED)
2182     {
2183       if (CONST_INT_P (op1)
2184           && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2185               (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (scalar_mode)))
2186         op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2187                        % GET_MODE_BITSIZE (scalar_mode));
2188       else if (GET_CODE (op1) == SUBREG
2189                && subreg_lowpart_p (op1)
2190                && SCALAR_INT_MODE_P (GET_MODE (SUBREG_REG (op1)))
2191                && SCALAR_INT_MODE_P (GET_MODE (op1)))
2192         op1 = SUBREG_REG (op1);
2193     }
2194
2195   /* Canonicalize rotates by constant amount.  If op1 is bitsize / 2,
2196      prefer left rotation, if op1 is from bitsize / 2 + 1 to
2197      bitsize - 1, use other direction of rotate with 1 .. bitsize / 2 - 1
2198      amount instead.  */
2199   if (rotate
2200       && CONST_INT_P (op1)
2201       && IN_RANGE (INTVAL (op1), GET_MODE_BITSIZE (scalar_mode) / 2 + left,
2202                    GET_MODE_BITSIZE (scalar_mode) - 1))
2203     {
2204       op1 = GEN_INT (GET_MODE_BITSIZE (scalar_mode) - INTVAL (op1));
2205       left = !left;
2206       code = left ? LROTATE_EXPR : RROTATE_EXPR;
2207     }
2208
2209   /* Rotation of 16bit values by 8 bits is effectively equivalent to a bswaphi.
2210      Note that this is not the case for bigger values.  For instance a rotation
2211      of 0x01020304 by 16 bits gives 0x03040102 which is different from
2212      0x04030201 (bswapsi).  */
2213   if (rotate
2214       && CONST_INT_P (op1)
2215       && INTVAL (op1) == BITS_PER_UNIT
2216       && GET_MODE_SIZE (scalar_mode) == 2
2217       && optab_handler (bswap_optab, HImode) != CODE_FOR_nothing)
2218     return expand_unop (HImode, bswap_optab, shifted, NULL_RTX,
2219                                   unsignedp);
2220
2221   if (op1 == const0_rtx)
2222     return shifted;
2223
2224   /* Check whether its cheaper to implement a left shift by a constant
2225      bit count by a sequence of additions.  */
2226   if (code == LSHIFT_EXPR
2227       && CONST_INT_P (op1)
2228       && INTVAL (op1) > 0
2229       && INTVAL (op1) < GET_MODE_PRECISION (scalar_mode)
2230       && INTVAL (op1) < MAX_BITS_PER_WORD
2231       && (shift_cost (speed, mode, INTVAL (op1))
2232           > INTVAL (op1) * add_cost (speed, mode))
2233       && shift_cost (speed, mode, INTVAL (op1)) != MAX_COST)
2234     {
2235       int i;
2236       for (i = 0; i < INTVAL (op1); i++)
2237         {
2238           temp = force_reg (mode, shifted);
2239           shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2240                                   unsignedp, OPTAB_LIB_WIDEN);
2241         }
2242       return shifted;
2243     }
2244
2245   for (attempt = 0; temp == 0 && attempt < 3; attempt++)
2246     {
2247       enum optab_methods methods;
2248
2249       if (attempt == 0)
2250         methods = OPTAB_DIRECT;
2251       else if (attempt == 1)
2252         methods = OPTAB_WIDEN;
2253       else
2254         methods = OPTAB_LIB_WIDEN;
2255
2256       if (rotate)
2257         {
2258           /* Widening does not work for rotation.  */
2259           if (methods == OPTAB_WIDEN)
2260             continue;
2261           else if (methods == OPTAB_LIB_WIDEN)
2262             {
2263               /* If we have been unable to open-code this by a rotation,
2264                  do it as the IOR of two shifts.  I.e., to rotate A
2265                  by N bits, compute
2266                  (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
2267                  where C is the bitsize of A.
2268
2269                  It is theoretically possible that the target machine might
2270                  not be able to perform either shift and hence we would
2271                  be making two libcalls rather than just the one for the
2272                  shift (similarly if IOR could not be done).  We will allow
2273                  this extremely unlikely lossage to avoid complicating the
2274                  code below.  */
2275
2276               rtx subtarget = target == shifted ? 0 : target;
2277               rtx new_amount, other_amount;
2278               rtx temp1;
2279
2280               new_amount = op1;
2281               if (op1 == const0_rtx)
2282                 return shifted;
2283               else if (CONST_INT_P (op1))
2284                 other_amount = GEN_INT (GET_MODE_BITSIZE (scalar_mode)
2285                                         - INTVAL (op1));
2286               else
2287                 {
2288                   other_amount
2289                     = simplify_gen_unary (NEG, GET_MODE (op1),
2290                                           op1, GET_MODE (op1));
2291                   HOST_WIDE_INT mask = GET_MODE_PRECISION (scalar_mode) - 1;
2292                   other_amount
2293                     = simplify_gen_binary (AND, GET_MODE (op1), other_amount,
2294                                            gen_int_mode (mask, GET_MODE (op1)));
2295                 }
2296
2297               shifted = force_reg (mode, shifted);
2298
2299               temp = expand_shift_1 (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2300                                      mode, shifted, new_amount, 0, 1);
2301               temp1 = expand_shift_1 (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2302                                       mode, shifted, other_amount,
2303                                       subtarget, 1);
2304               return expand_binop (mode, ior_optab, temp, temp1, target,
2305                                    unsignedp, methods);
2306             }
2307
2308           temp = expand_binop (mode,
2309                                left ? lrotate_optab : rrotate_optab,
2310                                shifted, op1, target, unsignedp, methods);
2311         }
2312       else if (unsignedp)
2313         temp = expand_binop (mode,
2314                              left ? lshift_optab : rshift_uns_optab,
2315                              shifted, op1, target, unsignedp, methods);
2316
2317       /* Do arithmetic shifts.
2318          Also, if we are going to widen the operand, we can just as well
2319          use an arithmetic right-shift instead of a logical one.  */
2320       if (temp == 0 && ! rotate
2321           && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2322         {
2323           enum optab_methods methods1 = methods;
2324
2325           /* If trying to widen a log shift to an arithmetic shift,
2326              don't accept an arithmetic shift of the same size.  */
2327           if (unsignedp)
2328             methods1 = OPTAB_MUST_WIDEN;
2329
2330           /* Arithmetic shift */
2331
2332           temp = expand_binop (mode,
2333                                left ? lshift_optab : rshift_arith_optab,
2334                                shifted, op1, target, unsignedp, methods1);
2335         }
2336
2337       /* We used to try extzv here for logical right shifts, but that was
2338          only useful for one machine, the VAX, and caused poor code
2339          generation there for lshrdi3, so the code was deleted and a
2340          define_expand for lshrsi3 was added to vax.md.  */
2341     }
2342
2343   gcc_assert (temp);
2344   return temp;
2345 }
2346
2347 /* Output a shift instruction for expression code CODE,
2348    with SHIFTED being the rtx for the value to shift,
2349    and AMOUNT the amount to shift by.
2350    Store the result in the rtx TARGET, if that is convenient.
2351    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2352    Return the rtx for where the value is.  */
2353
2354 rtx
2355 expand_shift (enum tree_code code, machine_mode mode, rtx shifted,
2356               int amount, rtx target, int unsignedp)
2357 {
2358   return expand_shift_1 (code, mode,
2359                          shifted, GEN_INT (amount), target, unsignedp);
2360 }
2361
2362 /* Output a shift instruction for expression code CODE,
2363    with SHIFTED being the rtx for the value to shift,
2364    and AMOUNT the tree for the amount to shift by.
2365    Store the result in the rtx TARGET, if that is convenient.
2366    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2367    Return the rtx for where the value is.  */
2368
2369 rtx
2370 expand_variable_shift (enum tree_code code, machine_mode mode, rtx shifted,
2371                        tree amount, rtx target, int unsignedp)
2372 {
2373   return expand_shift_1 (code, mode,
2374                          shifted, expand_normal (amount), target, unsignedp);
2375 }
2376
2377 \f
2378 /* Indicates the type of fixup needed after a constant multiplication.
2379    BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2380    the result should be negated, and ADD_VARIANT means that the
2381    multiplicand should be added to the result.  */
2382 enum mult_variant {basic_variant, negate_variant, add_variant};
2383
2384 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2385                         const struct mult_cost *, machine_mode mode);
2386 static bool choose_mult_variant (machine_mode, HOST_WIDE_INT,
2387                                  struct algorithm *, enum mult_variant *, int);
2388 static rtx expand_mult_const (machine_mode, rtx, HOST_WIDE_INT, rtx,
2389                               const struct algorithm *, enum mult_variant);
2390 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2391 static rtx extract_high_half (machine_mode, rtx);
2392 static rtx expmed_mult_highpart (machine_mode, rtx, rtx, rtx, int, int);
2393 static rtx expmed_mult_highpart_optab (machine_mode, rtx, rtx, rtx,
2394                                        int, int);
2395 /* Compute and return the best algorithm for multiplying by T.
2396    The algorithm must cost less than cost_limit
2397    If retval.cost >= COST_LIMIT, no algorithm was found and all
2398    other field of the returned struct are undefined.
2399    MODE is the machine mode of the multiplication.  */
2400
2401 static void
2402 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2403             const struct mult_cost *cost_limit, machine_mode mode)
2404 {
2405   int m;
2406   struct algorithm *alg_in, *best_alg;
2407   struct mult_cost best_cost;
2408   struct mult_cost new_limit;
2409   int op_cost, op_latency;
2410   unsigned HOST_WIDE_INT orig_t = t;
2411   unsigned HOST_WIDE_INT q;
2412   int maxm, hash_index;
2413   bool cache_hit = false;
2414   enum alg_code cache_alg = alg_zero;
2415   bool speed = optimize_insn_for_speed_p ();
2416   machine_mode imode;
2417   struct alg_hash_entry *entry_ptr;
2418
2419   /* Indicate that no algorithm is yet found.  If no algorithm
2420      is found, this value will be returned and indicate failure.  */
2421   alg_out->cost.cost = cost_limit->cost + 1;
2422   alg_out->cost.latency = cost_limit->latency + 1;
2423
2424   if (cost_limit->cost < 0
2425       || (cost_limit->cost == 0 && cost_limit->latency <= 0))
2426     return;
2427
2428   /* Be prepared for vector modes.  */
2429   imode = GET_MODE_INNER (mode);
2430   if (imode == VOIDmode)
2431     imode = mode;
2432
2433   maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (imode));
2434
2435   /* Restrict the bits of "t" to the multiplication's mode.  */
2436   t &= GET_MODE_MASK (imode);
2437
2438   /* t == 1 can be done in zero cost.  */
2439   if (t == 1)
2440     {
2441       alg_out->ops = 1;
2442       alg_out->cost.cost = 0;
2443       alg_out->cost.latency = 0;
2444       alg_out->op[0] = alg_m;
2445       return;
2446     }
2447
2448   /* t == 0 sometimes has a cost.  If it does and it exceeds our limit,
2449      fail now.  */
2450   if (t == 0)
2451     {
2452       if (MULT_COST_LESS (cost_limit, zero_cost (speed)))
2453         return;
2454       else
2455         {
2456           alg_out->ops = 1;
2457           alg_out->cost.cost = zero_cost (speed);
2458           alg_out->cost.latency = zero_cost (speed);
2459           alg_out->op[0] = alg_zero;
2460           return;
2461         }
2462     }
2463
2464   /* We'll be needing a couple extra algorithm structures now.  */
2465
2466   alg_in = XALLOCA (struct algorithm);
2467   best_alg = XALLOCA (struct algorithm);
2468   best_cost = *cost_limit;
2469
2470   /* Compute the hash index.  */
2471   hash_index = (t ^ (unsigned int) mode ^ (speed * 256)) % NUM_ALG_HASH_ENTRIES;
2472
2473   /* See if we already know what to do for T.  */
2474   entry_ptr = alg_hash_entry_ptr (hash_index);
2475   if (entry_ptr->t == t
2476       && entry_ptr->mode == mode
2477       && entry_ptr->mode == mode
2478       && entry_ptr->speed == speed
2479       && entry_ptr->alg != alg_unknown)
2480     {
2481       cache_alg = entry_ptr->alg;
2482
2483       if (cache_alg == alg_impossible)
2484         {
2485           /* The cache tells us that it's impossible to synthesize
2486              multiplication by T within entry_ptr->cost.  */
2487           if (!CHEAPER_MULT_COST (&entry_ptr->cost, cost_limit))
2488             /* COST_LIMIT is at least as restrictive as the one
2489                recorded in the hash table, in which case we have no
2490                hope of synthesizing a multiplication.  Just
2491                return.  */
2492             return;
2493
2494           /* If we get here, COST_LIMIT is less restrictive than the
2495              one recorded in the hash table, so we may be able to
2496              synthesize a multiplication.  Proceed as if we didn't
2497              have the cache entry.  */
2498         }
2499       else
2500         {
2501           if (CHEAPER_MULT_COST (cost_limit, &entry_ptr->cost))
2502             /* The cached algorithm shows that this multiplication
2503                requires more cost than COST_LIMIT.  Just return.  This
2504                way, we don't clobber this cache entry with
2505                alg_impossible but retain useful information.  */
2506             return;
2507
2508           cache_hit = true;
2509
2510           switch (cache_alg)
2511             {
2512             case alg_shift:
2513               goto do_alg_shift;
2514
2515             case alg_add_t_m2:
2516             case alg_sub_t_m2:
2517               goto do_alg_addsub_t_m2;
2518
2519             case alg_add_factor:
2520             case alg_sub_factor:
2521               goto do_alg_addsub_factor;
2522
2523             case alg_add_t2_m:
2524               goto do_alg_add_t2_m;
2525
2526             case alg_sub_t2_m:
2527               goto do_alg_sub_t2_m;
2528
2529             default:
2530               gcc_unreachable ();
2531             }
2532         }
2533     }
2534
2535   /* If we have a group of zero bits at the low-order part of T, try
2536      multiplying by the remaining bits and then doing a shift.  */
2537
2538   if ((t & 1) == 0)
2539     {
2540     do_alg_shift:
2541       m = floor_log2 (t & -t);  /* m = number of low zero bits */
2542       if (m < maxm)
2543         {
2544           q = t >> m;
2545           /* The function expand_shift will choose between a shift and
2546              a sequence of additions, so the observed cost is given as
2547              MIN (m * add_cost(speed, mode), shift_cost(speed, mode, m)).  */
2548           op_cost = m * add_cost (speed, mode);
2549           if (shift_cost (speed, mode, m) < op_cost)
2550             op_cost = shift_cost (speed, mode, m);
2551           new_limit.cost = best_cost.cost - op_cost;
2552           new_limit.latency = best_cost.latency - op_cost;
2553           synth_mult (alg_in, q, &new_limit, mode);
2554
2555           alg_in->cost.cost += op_cost;
2556           alg_in->cost.latency += op_cost;
2557           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2558             {
2559               best_cost = alg_in->cost;
2560               std::swap (alg_in, best_alg);
2561               best_alg->log[best_alg->ops] = m;
2562               best_alg->op[best_alg->ops] = alg_shift;
2563             }
2564
2565           /* See if treating ORIG_T as a signed number yields a better
2566              sequence.  Try this sequence only for a negative ORIG_T
2567              as it would be useless for a non-negative ORIG_T.  */
2568           if ((HOST_WIDE_INT) orig_t < 0)
2569             {
2570               /* Shift ORIG_T as follows because a right shift of a
2571                  negative-valued signed type is implementation
2572                  defined.  */
2573               q = ~(~orig_t >> m);
2574               /* The function expand_shift will choose between a shift
2575                  and a sequence of additions, so the observed cost is
2576                  given as MIN (m * add_cost(speed, mode),
2577                  shift_cost(speed, mode, m)).  */
2578               op_cost = m * add_cost (speed, mode);
2579               if (shift_cost (speed, mode, m) < op_cost)
2580                 op_cost = shift_cost (speed, mode, m);
2581               new_limit.cost = best_cost.cost - op_cost;
2582               new_limit.latency = best_cost.latency - op_cost;
2583               synth_mult (alg_in, q, &new_limit, mode);
2584
2585               alg_in->cost.cost += op_cost;
2586               alg_in->cost.latency += op_cost;
2587               if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2588                 {
2589                   best_cost = alg_in->cost;
2590                   std::swap (alg_in, best_alg);
2591                   best_alg->log[best_alg->ops] = m;
2592                   best_alg->op[best_alg->ops] = alg_shift;
2593                 }
2594             }
2595         }
2596       if (cache_hit)
2597         goto done;
2598     }
2599
2600   /* If we have an odd number, add or subtract one.  */
2601   if ((t & 1) != 0)
2602     {
2603       unsigned HOST_WIDE_INT w;
2604
2605     do_alg_addsub_t_m2:
2606       for (w = 1; (w & t) != 0; w <<= 1)
2607         ;
2608       /* If T was -1, then W will be zero after the loop.  This is another
2609          case where T ends with ...111.  Handling this with (T + 1) and
2610          subtract 1 produces slightly better code and results in algorithm
2611          selection much faster than treating it like the ...0111 case
2612          below.  */
2613       if (w == 0
2614           || (w > 2
2615               /* Reject the case where t is 3.
2616                  Thus we prefer addition in that case.  */
2617               && t != 3))
2618         {
2619           /* T ends with ...111.  Multiply by (T + 1) and subtract T.  */
2620
2621           op_cost = add_cost (speed, mode);
2622           new_limit.cost = best_cost.cost - op_cost;
2623           new_limit.latency = best_cost.latency - op_cost;
2624           synth_mult (alg_in, t + 1, &new_limit, mode);
2625
2626           alg_in->cost.cost += op_cost;
2627           alg_in->cost.latency += op_cost;
2628           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2629             {
2630               best_cost = alg_in->cost;
2631               std::swap (alg_in, best_alg);
2632               best_alg->log[best_alg->ops] = 0;
2633               best_alg->op[best_alg->ops] = alg_sub_t_m2;
2634             }
2635         }
2636       else
2637         {
2638           /* T ends with ...01 or ...011.  Multiply by (T - 1) and add T.  */
2639
2640           op_cost = add_cost (speed, mode);
2641           new_limit.cost = best_cost.cost - op_cost;
2642           new_limit.latency = best_cost.latency - op_cost;
2643           synth_mult (alg_in, t - 1, &new_limit, mode);
2644
2645           alg_in->cost.cost += op_cost;
2646           alg_in->cost.latency += op_cost;
2647           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2648             {
2649               best_cost = alg_in->cost;
2650               std::swap (alg_in, best_alg);
2651               best_alg->log[best_alg->ops] = 0;
2652               best_alg->op[best_alg->ops] = alg_add_t_m2;
2653             }
2654         }
2655
2656       /* We may be able to calculate a * -7, a * -15, a * -31, etc
2657          quickly with a - a * n for some appropriate constant n.  */
2658       m = exact_log2 (-orig_t + 1);
2659       if (m >= 0 && m < maxm)
2660         {
2661           op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2662           /* If the target has a cheap shift-and-subtract insn use
2663              that in preference to a shift insn followed by a sub insn.
2664              Assume that the shift-and-sub is "atomic" with a latency
2665              equal to it's cost, otherwise assume that on superscalar
2666              hardware the shift may be executed concurrently with the
2667              earlier steps in the algorithm.  */
2668           if (shiftsub1_cost (speed, mode, m) <= op_cost)
2669             {
2670               op_cost = shiftsub1_cost (speed, mode, m);
2671               op_latency = op_cost;
2672             }
2673           else
2674             op_latency = add_cost (speed, mode);
2675
2676           new_limit.cost = best_cost.cost - op_cost;
2677           new_limit.latency = best_cost.latency - op_latency;
2678           synth_mult (alg_in, (unsigned HOST_WIDE_INT) (-orig_t + 1) >> m,
2679                       &new_limit, mode);
2680
2681           alg_in->cost.cost += op_cost;
2682           alg_in->cost.latency += op_latency;
2683           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2684             {
2685               best_cost = alg_in->cost;
2686               std::swap (alg_in, best_alg);
2687               best_alg->log[best_alg->ops] = m;
2688               best_alg->op[best_alg->ops] = alg_sub_t_m2;
2689             }
2690         }
2691
2692       if (cache_hit)
2693         goto done;
2694     }
2695
2696   /* Look for factors of t of the form
2697      t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2698      If we find such a factor, we can multiply by t using an algorithm that
2699      multiplies by q, shift the result by m and add/subtract it to itself.
2700
2701      We search for large factors first and loop down, even if large factors
2702      are less probable than small; if we find a large factor we will find a
2703      good sequence quickly, and therefore be able to prune (by decreasing
2704      COST_LIMIT) the search.  */
2705
2706  do_alg_addsub_factor:
2707   for (m = floor_log2 (t - 1); m >= 2; m--)
2708     {
2709       unsigned HOST_WIDE_INT d;
2710
2711       d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2712       if (t % d == 0 && t > d && m < maxm
2713           && (!cache_hit || cache_alg == alg_add_factor))
2714         {
2715           op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2716           if (shiftadd_cost (speed, mode, m) <= op_cost)
2717             op_cost = shiftadd_cost (speed, mode, m);
2718
2719           op_latency = op_cost;
2720
2721
2722           new_limit.cost = best_cost.cost - op_cost;
2723           new_limit.latency = best_cost.latency - op_latency;
2724           synth_mult (alg_in, t / d, &new_limit, mode);
2725
2726           alg_in->cost.cost += op_cost;
2727           alg_in->cost.latency += op_latency;
2728           if (alg_in->cost.latency < op_cost)
2729             alg_in->cost.latency = op_cost;
2730           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2731             {
2732               best_cost = alg_in->cost;
2733               std::swap (alg_in, best_alg);
2734               best_alg->log[best_alg->ops] = m;
2735               best_alg->op[best_alg->ops] = alg_add_factor;
2736             }
2737           /* Other factors will have been taken care of in the recursion.  */
2738           break;
2739         }
2740
2741       d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2742       if (t % d == 0 && t > d && m < maxm
2743           && (!cache_hit || cache_alg == alg_sub_factor))
2744         {
2745           op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2746           if (shiftsub0_cost (speed, mode, m) <= op_cost)
2747             op_cost = shiftsub0_cost (speed, mode, m);
2748
2749           op_latency = op_cost;
2750
2751           new_limit.cost = best_cost.cost - op_cost;
2752           new_limit.latency = best_cost.latency - op_latency;
2753           synth_mult (alg_in, t / d, &new_limit, mode);
2754
2755           alg_in->cost.cost += op_cost;
2756           alg_in->cost.latency += op_latency;
2757           if (alg_in->cost.latency < op_cost)
2758             alg_in->cost.latency = op_cost;
2759           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2760             {
2761               best_cost = alg_in->cost;
2762               std::swap (alg_in, best_alg);
2763               best_alg->log[best_alg->ops] = m;
2764               best_alg->op[best_alg->ops] = alg_sub_factor;
2765             }
2766           break;
2767         }
2768     }
2769   if (cache_hit)
2770     goto done;
2771
2772   /* Try shift-and-add (load effective address) instructions,
2773      i.e. do a*3, a*5, a*9.  */
2774   if ((t & 1) != 0)
2775     {
2776     do_alg_add_t2_m:
2777       q = t - 1;
2778       q = q & -q;
2779       m = exact_log2 (q);
2780       if (m >= 0 && m < maxm)
2781         {
2782           op_cost = shiftadd_cost (speed, mode, m);
2783           new_limit.cost = best_cost.cost - op_cost;
2784           new_limit.latency = best_cost.latency - op_cost;
2785           synth_mult (alg_in, (t - 1) >> m, &new_limit, mode);
2786
2787           alg_in->cost.cost += op_cost;
2788           alg_in->cost.latency += op_cost;
2789           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2790             {
2791               best_cost = alg_in->cost;
2792               std::swap (alg_in, best_alg);
2793               best_alg->log[best_alg->ops] = m;
2794               best_alg->op[best_alg->ops] = alg_add_t2_m;
2795             }
2796         }
2797       if (cache_hit)
2798         goto done;
2799
2800     do_alg_sub_t2_m:
2801       q = t + 1;
2802       q = q & -q;
2803       m = exact_log2 (q);
2804       if (m >= 0 && m < maxm)
2805         {
2806           op_cost = shiftsub0_cost (speed, mode, m);
2807           new_limit.cost = best_cost.cost - op_cost;
2808           new_limit.latency = best_cost.latency - op_cost;
2809           synth_mult (alg_in, (t + 1) >> m, &new_limit, mode);
2810
2811           alg_in->cost.cost += op_cost;
2812           alg_in->cost.latency += op_cost;
2813           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2814             {
2815               best_cost = alg_in->cost;
2816               std::swap (alg_in, best_alg);
2817               best_alg->log[best_alg->ops] = m;
2818               best_alg->op[best_alg->ops] = alg_sub_t2_m;
2819             }
2820         }
2821       if (cache_hit)
2822         goto done;
2823     }
2824
2825  done:
2826   /* If best_cost has not decreased, we have not found any algorithm.  */
2827   if (!CHEAPER_MULT_COST (&best_cost, cost_limit))
2828     {
2829       /* We failed to find an algorithm.  Record alg_impossible for
2830          this case (that is, <T, MODE, COST_LIMIT>) so that next time
2831          we are asked to find an algorithm for T within the same or
2832          lower COST_LIMIT, we can immediately return to the
2833          caller.  */
2834       entry_ptr->t = t;
2835       entry_ptr->mode = mode;
2836       entry_ptr->speed = speed;
2837       entry_ptr->alg = alg_impossible;
2838       entry_ptr->cost = *cost_limit;
2839       return;
2840     }
2841
2842   /* Cache the result.  */
2843   if (!cache_hit)
2844     {
2845       entry_ptr->t = t;
2846       entry_ptr->mode = mode;
2847       entry_ptr->speed = speed;
2848       entry_ptr->alg = best_alg->op[best_alg->ops];
2849       entry_ptr->cost.cost = best_cost.cost;
2850       entry_ptr->cost.latency = best_cost.latency;
2851     }
2852
2853   /* If we are getting a too long sequence for `struct algorithm'
2854      to record, make this search fail.  */
2855   if (best_alg->ops == MAX_BITS_PER_WORD)
2856     return;
2857
2858   /* Copy the algorithm from temporary space to the space at alg_out.
2859      We avoid using structure assignment because the majority of
2860      best_alg is normally undefined, and this is a critical function.  */
2861   alg_out->ops = best_alg->ops + 1;
2862   alg_out->cost = best_cost;
2863   memcpy (alg_out->op, best_alg->op,
2864           alg_out->ops * sizeof *alg_out->op);
2865   memcpy (alg_out->log, best_alg->log,
2866           alg_out->ops * sizeof *alg_out->log);
2867 }
2868 \f
2869 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2870    Try three variations:
2871
2872        - a shift/add sequence based on VAL itself
2873        - a shift/add sequence based on -VAL, followed by a negation
2874        - a shift/add sequence based on VAL - 1, followed by an addition.
2875
2876    Return true if the cheapest of these cost less than MULT_COST,
2877    describing the algorithm in *ALG and final fixup in *VARIANT.  */
2878
2879 static bool
2880 choose_mult_variant (machine_mode mode, HOST_WIDE_INT val,
2881                      struct algorithm *alg, enum mult_variant *variant,
2882                      int mult_cost)
2883 {
2884   struct algorithm alg2;
2885   struct mult_cost limit;
2886   int op_cost;
2887   bool speed = optimize_insn_for_speed_p ();
2888
2889   /* Fail quickly for impossible bounds.  */
2890   if (mult_cost < 0)
2891     return false;
2892
2893   /* Ensure that mult_cost provides a reasonable upper bound.
2894      Any constant multiplication can be performed with less
2895      than 2 * bits additions.  */
2896   op_cost = 2 * GET_MODE_UNIT_BITSIZE (mode) * add_cost (speed, mode);
2897   if (mult_cost > op_cost)
2898     mult_cost = op_cost;
2899
2900   *variant = basic_variant;
2901   limit.cost = mult_cost;
2902   limit.latency = mult_cost;
2903   synth_mult (alg, val, &limit, mode);
2904
2905   /* This works only if the inverted value actually fits in an
2906      `unsigned int' */
2907   if (HOST_BITS_PER_INT >= GET_MODE_UNIT_BITSIZE (mode))
2908     {
2909       op_cost = neg_cost (speed, mode);
2910       if (MULT_COST_LESS (&alg->cost, mult_cost))
2911         {
2912           limit.cost = alg->cost.cost - op_cost;
2913           limit.latency = alg->cost.latency - op_cost;
2914         }
2915       else
2916         {
2917           limit.cost = mult_cost - op_cost;
2918           limit.latency = mult_cost - op_cost;
2919         }
2920
2921       synth_mult (&alg2, -val, &limit, mode);
2922       alg2.cost.cost += op_cost;
2923       alg2.cost.latency += op_cost;
2924       if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2925         *alg = alg2, *variant = negate_variant;
2926     }
2927
2928   /* This proves very useful for division-by-constant.  */
2929   op_cost = add_cost (speed, mode);
2930   if (MULT_COST_LESS (&alg->cost, mult_cost))
2931     {
2932       limit.cost = alg->cost.cost - op_cost;
2933       limit.latency = alg->cost.latency - op_cost;
2934     }
2935   else
2936     {
2937       limit.cost = mult_cost - op_cost;
2938       limit.latency = mult_cost - op_cost;
2939     }
2940
2941   synth_mult (&alg2, val - 1, &limit, mode);
2942   alg2.cost.cost += op_cost;
2943   alg2.cost.latency += op_cost;
2944   if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2945     *alg = alg2, *variant = add_variant;
2946
2947   return MULT_COST_LESS (&alg->cost, mult_cost);
2948 }
2949
2950 /* A subroutine of expand_mult, used for constant multiplications.
2951    Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2952    convenient.  Use the shift/add sequence described by ALG and apply
2953    the final fixup specified by VARIANT.  */
2954
2955 static rtx
2956 expand_mult_const (machine_mode mode, rtx op0, HOST_WIDE_INT val,
2957                    rtx target, const struct algorithm *alg,
2958                    enum mult_variant variant)
2959 {
2960   HOST_WIDE_INT val_so_far;
2961   rtx_insn *insn;
2962   rtx accum, tem;
2963   int opno;
2964   machine_mode nmode;
2965
2966   /* Avoid referencing memory over and over and invalid sharing
2967      on SUBREGs.  */
2968   op0 = force_reg (mode, op0);
2969
2970   /* ACCUM starts out either as OP0 or as a zero, depending on
2971      the first operation.  */
2972
2973   if (alg->op[0] == alg_zero)
2974     {
2975       accum = copy_to_mode_reg (mode, CONST0_RTX (mode));
2976       val_so_far = 0;
2977     }
2978   else if (alg->op[0] == alg_m)
2979     {
2980       accum = copy_to_mode_reg (mode, op0);
2981       val_so_far = 1;
2982     }
2983   else
2984     gcc_unreachable ();
2985
2986   for (opno = 1; opno < alg->ops; opno++)
2987     {
2988       int log = alg->log[opno];
2989       rtx shift_subtarget = optimize ? 0 : accum;
2990       rtx add_target
2991         = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2992            && !optimize)
2993           ? target : 0;
2994       rtx accum_target = optimize ? 0 : accum;
2995       rtx accum_inner;
2996
2997       switch (alg->op[opno])
2998         {
2999         case alg_shift:
3000           tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3001           /* REG_EQUAL note will be attached to the following insn.  */
3002           emit_move_insn (accum, tem);
3003           val_so_far <<= log;
3004           break;
3005
3006         case alg_add_t_m2:
3007           tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
3008           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3009                                  add_target ? add_target : accum_target);
3010           val_so_far += (HOST_WIDE_INT) 1 << log;
3011           break;
3012
3013         case alg_sub_t_m2:
3014           tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
3015           accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
3016                                  add_target ? add_target : accum_target);
3017           val_so_far -= (HOST_WIDE_INT) 1 << log;
3018           break;
3019
3020         case alg_add_t2_m:
3021           accum = expand_shift (LSHIFT_EXPR, mode, accum,
3022                                 log, shift_subtarget, 0);
3023           accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
3024                                  add_target ? add_target : accum_target);
3025           val_so_far = (val_so_far << log) + 1;
3026           break;
3027
3028         case alg_sub_t2_m:
3029           accum = expand_shift (LSHIFT_EXPR, mode, accum,
3030                                 log, shift_subtarget, 0);
3031           accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
3032                                  add_target ? add_target : accum_target);
3033           val_so_far = (val_so_far << log) - 1;
3034           break;
3035
3036         case alg_add_factor:
3037           tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3038           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3039                                  add_target ? add_target : accum_target);
3040           val_so_far += val_so_far << log;
3041           break;
3042
3043         case alg_sub_factor:
3044           tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3045           accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
3046                                  (add_target
3047                                   ? add_target : (optimize ? 0 : tem)));
3048           val_so_far = (val_so_far << log) - val_so_far;
3049           break;
3050
3051         default:
3052           gcc_unreachable ();
3053         }
3054
3055       if (SCALAR_INT_MODE_P (mode))
3056         {
3057           /* Write a REG_EQUAL note on the last insn so that we can cse
3058              multiplication sequences.  Note that if ACCUM is a SUBREG,
3059              we've set the inner register and must properly indicate that.  */
3060           tem = op0, nmode = mode;
3061           accum_inner = accum;
3062           if (GET_CODE (accum) == SUBREG)
3063             {
3064               accum_inner = SUBREG_REG (accum);
3065               nmode = GET_MODE (accum_inner);
3066               tem = gen_lowpart (nmode, op0);
3067             }
3068
3069           insn = get_last_insn ();
3070           set_dst_reg_note (insn, REG_EQUAL,
3071                             gen_rtx_MULT (nmode, tem,
3072                                           gen_int_mode (val_so_far, nmode)),
3073                             accum_inner);
3074         }
3075     }
3076
3077   if (variant == negate_variant)
3078     {
3079       val_so_far = -val_so_far;
3080       accum = expand_unop (mode, neg_optab, accum, target, 0);
3081     }
3082   else if (variant == add_variant)
3083     {
3084       val_so_far = val_so_far + 1;
3085       accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
3086     }
3087
3088   /* Compare only the bits of val and val_so_far that are significant
3089      in the result mode, to avoid sign-/zero-extension confusion.  */
3090   nmode = GET_MODE_INNER (mode);
3091   if (nmode == VOIDmode)
3092     nmode = mode;
3093   val &= GET_MODE_MASK (nmode);
3094   val_so_far &= GET_MODE_MASK (nmode);
3095   gcc_assert (val == val_so_far);
3096
3097   return accum;
3098 }
3099
3100 /* Perform a multiplication and return an rtx for the result.
3101    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3102    TARGET is a suggestion for where to store the result (an rtx).
3103
3104    We check specially for a constant integer as OP1.
3105    If you want this check for OP0 as well, then before calling
3106    you should swap the two operands if OP0 would be constant.  */
3107
3108 rtx
3109 expand_mult (machine_mode mode, rtx op0, rtx op1, rtx target,
3110              int unsignedp)
3111 {
3112   enum mult_variant variant;
3113   struct algorithm algorithm;
3114   rtx scalar_op1;
3115   int max_cost;
3116   bool speed = optimize_insn_for_speed_p ();
3117   bool do_trapv = flag_trapv && SCALAR_INT_MODE_P (mode) && !unsignedp;
3118
3119   if (CONSTANT_P (op0))
3120     std::swap (op0, op1);
3121
3122   /* For vectors, there are several simplifications that can be made if
3123      all elements of the vector constant are identical.  */
3124   scalar_op1 = op1;
3125   if (GET_CODE (op1) == CONST_VECTOR)
3126     {
3127       int i, n = CONST_VECTOR_NUNITS (op1);
3128       scalar_op1 = CONST_VECTOR_ELT (op1, 0);
3129       for (i = 1; i < n; ++i)
3130         if (!rtx_equal_p (scalar_op1, CONST_VECTOR_ELT (op1, i)))
3131           goto skip_scalar;
3132     }
3133
3134   if (INTEGRAL_MODE_P (mode))
3135     {
3136       rtx fake_reg;
3137       HOST_WIDE_INT coeff;
3138       bool is_neg;
3139       int mode_bitsize;
3140
3141       if (op1 == CONST0_RTX (mode))
3142         return op1;
3143       if (op1 == CONST1_RTX (mode))
3144         return op0;
3145       if (op1 == CONSTM1_RTX (mode))
3146         return expand_unop (mode, do_trapv ? negv_optab : neg_optab,
3147                             op0, target, 0);
3148
3149       if (do_trapv)
3150         goto skip_synth;
3151
3152       /* If mode is integer vector mode, check if the backend supports
3153          vector lshift (by scalar or vector) at all.  If not, we can't use
3154          synthetized multiply.  */
3155       if (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
3156           && optab_handler (vashl_optab, mode) == CODE_FOR_nothing
3157           && optab_handler (ashl_optab, mode) == CODE_FOR_nothing)
3158         goto skip_synth;
3159
3160       /* These are the operations that are potentially turned into
3161          a sequence of shifts and additions.  */
3162       mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
3163
3164       /* synth_mult does an `unsigned int' multiply.  As long as the mode is
3165          less than or equal in size to `unsigned int' this doesn't matter.
3166          If the mode is larger than `unsigned int', then synth_mult works
3167          only if the constant value exactly fits in an `unsigned int' without
3168          any truncation.  This means that multiplying by negative values does
3169          not work; results are off by 2^32 on a 32 bit machine.  */
3170       if (CONST_INT_P (scalar_op1))
3171         {
3172           coeff = INTVAL (scalar_op1);
3173           is_neg = coeff < 0;
3174         }
3175 #if TARGET_SUPPORTS_WIDE_INT
3176       else if (CONST_WIDE_INT_P (scalar_op1))
3177 #else
3178       else if (CONST_DOUBLE_AS_INT_P (scalar_op1))
3179 #endif
3180         {
3181           int shift = wi::exact_log2 (std::make_pair (scalar_op1, mode));
3182           /* Perfect power of 2 (other than 1, which is handled above).  */
3183           if (shift > 0)
3184             return expand_shift (LSHIFT_EXPR, mode, op0,
3185                                  shift, target, unsignedp);
3186           else
3187             goto skip_synth;
3188         }
3189       else
3190         goto skip_synth;
3191
3192       /* We used to test optimize here, on the grounds that it's better to
3193          produce a smaller program when -O is not used.  But this causes
3194          such a terrible slowdown sometimes that it seems better to always
3195          use synth_mult.  */
3196
3197       /* Special case powers of two.  */
3198       if (EXACT_POWER_OF_2_OR_ZERO_P (coeff)
3199           && !(is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT))
3200         return expand_shift (LSHIFT_EXPR, mode, op0,
3201                              floor_log2 (coeff), target, unsignedp);
3202
3203       fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3204
3205       /* Attempt to handle multiplication of DImode values by negative
3206          coefficients, by performing the multiplication by a positive
3207          multiplier and then inverting the result.  */
3208       if (is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT)
3209         {
3210           /* Its safe to use -coeff even for INT_MIN, as the
3211              result is interpreted as an unsigned coefficient.
3212              Exclude cost of op0 from max_cost to match the cost
3213              calculation of the synth_mult.  */
3214           coeff = -(unsigned HOST_WIDE_INT) coeff;
3215           max_cost = (set_src_cost (gen_rtx_MULT (mode, fake_reg, op1), speed)
3216                       - neg_cost (speed, mode));
3217           if (max_cost <= 0)
3218             goto skip_synth;
3219
3220           /* Special case powers of two.  */
3221           if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3222             {
3223               rtx temp = expand_shift (LSHIFT_EXPR, mode, op0,
3224                                        floor_log2 (coeff), target, unsignedp);
3225               return expand_unop (mode, neg_optab, temp, target, 0);
3226             }
3227
3228           if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3229                                    max_cost))
3230             {
3231               rtx temp = expand_mult_const (mode, op0, coeff, NULL_RTX,
3232                                             &algorithm, variant);
3233               return expand_unop (mode, neg_optab, temp, target, 0);
3234             }
3235           goto skip_synth;
3236         }
3237
3238       /* Exclude cost of op0 from max_cost to match the cost
3239          calculation of the synth_mult.  */
3240       max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, op1), speed);
3241       if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3242         return expand_mult_const (mode, op0, coeff, target,
3243                                   &algorithm, variant);
3244     }
3245  skip_synth:
3246
3247   /* Expand x*2.0 as x+x.  */
3248   if (CONST_DOUBLE_AS_FLOAT_P (scalar_op1))
3249     {
3250       REAL_VALUE_TYPE d;
3251       REAL_VALUE_FROM_CONST_DOUBLE (d, scalar_op1);
3252
3253       if (REAL_VALUES_EQUAL (d, dconst2))
3254         {
3255           op0 = force_reg (GET_MODE (op0), op0);
3256           return expand_binop (mode, add_optab, op0, op0,
3257                                target, unsignedp, OPTAB_LIB_WIDEN);
3258         }
3259     }
3260  skip_scalar:
3261
3262   /* This used to use umul_optab if unsigned, but for non-widening multiply
3263      there is no difference between signed and unsigned.  */
3264   op0 = expand_binop (mode, do_trapv ? smulv_optab : smul_optab,
3265                       op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
3266   gcc_assert (op0);
3267   return op0;
3268 }
3269
3270 /* Return a cost estimate for multiplying a register by the given
3271    COEFFicient in the given MODE and SPEED.  */
3272
3273 int
3274 mult_by_coeff_cost (HOST_WIDE_INT coeff, machine_mode mode, bool speed)
3275 {
3276   int max_cost;
3277   struct algorithm algorithm;
3278   enum mult_variant variant;
3279
3280   rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3281   max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, fake_reg), speed);
3282   if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3283     return algorithm.cost.cost;
3284   else
3285     return max_cost;
3286 }
3287
3288 /* Perform a widening multiplication and return an rtx for the result.
3289    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3290    TARGET is a suggestion for where to store the result (an rtx).
3291    THIS_OPTAB is the optab we should use, it must be either umul_widen_optab
3292    or smul_widen_optab.
3293
3294    We check specially for a constant integer as OP1, comparing the
3295    cost of a widening multiply against the cost of a sequence of shifts
3296    and adds.  */
3297
3298 rtx
3299 expand_widening_mult (machine_mode mode, rtx op0, rtx op1, rtx target,
3300                       int unsignedp, optab this_optab)
3301 {
3302   bool speed = optimize_insn_for_speed_p ();
3303   rtx cop1;
3304
3305   if (CONST_INT_P (op1)
3306       && GET_MODE (op0) != VOIDmode
3307       && (cop1 = convert_modes (mode, GET_MODE (op0), op1,
3308                                 this_optab == umul_widen_optab))
3309       && CONST_INT_P (cop1)
3310       && (INTVAL (cop1) >= 0
3311           || HWI_COMPUTABLE_MODE_P (mode)))
3312     {
3313       HOST_WIDE_INT coeff = INTVAL (cop1);
3314       int max_cost;
3315       enum mult_variant variant;
3316       struct algorithm algorithm;
3317
3318       if (coeff == 0)
3319         return CONST0_RTX (mode);
3320
3321       /* Special case powers of two.  */
3322       if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3323         {
3324           op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3325           return expand_shift (LSHIFT_EXPR, mode, op0,
3326                                floor_log2 (coeff), target, unsignedp);
3327         }
3328
3329       /* Exclude cost of op0 from max_cost to match the cost
3330          calculation of the synth_mult.  */
3331       max_cost = mul_widen_cost (speed, mode);
3332       if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3333                                max_cost))
3334         {
3335           op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3336           return expand_mult_const (mode, op0, coeff, target,
3337                                     &algorithm, variant);
3338         }
3339     }
3340   return expand_binop (mode, this_optab, op0, op1, target,
3341                        unsignedp, OPTAB_LIB_WIDEN);
3342 }
3343 \f
3344 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
3345    replace division by D, and put the least significant N bits of the result
3346    in *MULTIPLIER_PTR and return the most significant bit.
3347
3348    The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
3349    needed precision is in PRECISION (should be <= N).
3350
3351    PRECISION should be as small as possible so this function can choose
3352    multiplier more freely.
3353
3354    The rounded-up logarithm of D is placed in *lgup_ptr.  A shift count that
3355    is to be used for a final right shift is placed in *POST_SHIFT_PTR.
3356
3357    Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
3358    where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier.  */
3359
3360 unsigned HOST_WIDE_INT
3361 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
3362                    unsigned HOST_WIDE_INT *multiplier_ptr,
3363                    int *post_shift_ptr, int *lgup_ptr)
3364 {
3365   int lgup, post_shift;
3366   int pow, pow2;
3367
3368   /* lgup = ceil(log2(divisor)); */
3369   lgup = ceil_log2 (d);
3370
3371   gcc_assert (lgup <= n);
3372
3373   pow = n + lgup;
3374   pow2 = n + lgup - precision;
3375
3376   /* mlow = 2^(N + lgup)/d */
3377   wide_int val = wi::set_bit_in_zero (pow, HOST_BITS_PER_DOUBLE_INT);
3378   wide_int mlow = wi::udiv_trunc (val, d);
3379
3380   /* mhigh = (2^(N + lgup) + 2^(N + lgup - precision))/d */
3381   val |= wi::set_bit_in_zero (pow2, HOST_BITS_PER_DOUBLE_INT);
3382   wide_int mhigh = wi::udiv_trunc (val, d);
3383
3384   /* If precision == N, then mlow, mhigh exceed 2^N
3385      (but they do not exceed 2^(N+1)).  */
3386
3387   /* Reduce to lowest terms.  */
3388   for (post_shift = lgup; post_shift > 0; post_shift--)
3389     {
3390       unsigned HOST_WIDE_INT ml_lo = wi::extract_uhwi (mlow, 1,
3391                                                        HOST_BITS_PER_WIDE_INT);
3392       unsigned HOST_WIDE_INT mh_lo = wi::extract_uhwi (mhigh, 1,
3393                                                        HOST_BITS_PER_WIDE_INT);
3394       if (ml_lo >= mh_lo)
3395         break;
3396
3397       mlow = wi::uhwi (ml_lo, HOST_BITS_PER_DOUBLE_INT);
3398       mhigh = wi::uhwi (mh_lo, HOST_BITS_PER_DOUBLE_INT);
3399     }
3400
3401   *post_shift_ptr = post_shift;
3402   *lgup_ptr = lgup;
3403   if (n < HOST_BITS_PER_WIDE_INT)
3404     {
3405       unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
3406       *multiplier_ptr = mhigh.to_uhwi () & mask;
3407       return mhigh.to_uhwi () >= mask;
3408     }
3409   else
3410     {
3411       *multiplier_ptr = mhigh.to_uhwi ();
3412       return wi::extract_uhwi (mhigh, HOST_BITS_PER_WIDE_INT, 1);
3413     }
3414 }
3415
3416 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
3417    congruent to 1 (mod 2**N).  */
3418
3419 static unsigned HOST_WIDE_INT
3420 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
3421 {
3422   /* Solve x*y == 1 (mod 2^n), where x is odd.  Return y.  */
3423
3424   /* The algorithm notes that the choice y = x satisfies
3425      x*y == 1 mod 2^3, since x is assumed odd.
3426      Each iteration doubles the number of bits of significance in y.  */
3427
3428   unsigned HOST_WIDE_INT mask;
3429   unsigned HOST_WIDE_INT y = x;
3430   int nbit = 3;
3431
3432   mask = (n == HOST_BITS_PER_WIDE_INT
3433           ? ~(unsigned HOST_WIDE_INT) 0
3434           : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
3435
3436   while (nbit < n)
3437     {
3438       y = y * (2 - x*y) & mask;         /* Modulo 2^N */
3439       nbit *= 2;
3440     }
3441   return y;
3442 }
3443
3444 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
3445    flavor of OP0 and OP1.  ADJ_OPERAND is already the high half of the
3446    product OP0 x OP1.  If UNSIGNEDP is nonzero, adjust the signed product
3447    to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
3448    become signed.
3449
3450    The result is put in TARGET if that is convenient.
3451
3452    MODE is the mode of operation.  */
3453
3454 rtx
3455 expand_mult_highpart_adjust (machine_mode mode, rtx adj_operand, rtx op0,
3456                              rtx op1, rtx target, int unsignedp)
3457 {
3458   rtx tem;
3459   enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
3460
3461   tem = expand_shift (RSHIFT_EXPR, mode, op0,
3462                       GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3463   tem = expand_and (mode, tem, op1, NULL_RTX);
3464   adj_operand
3465     = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3466                      adj_operand);
3467
3468   tem = expand_shift (RSHIFT_EXPR, mode, op1,
3469                       GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3470   tem = expand_and (mode, tem, op0, NULL_RTX);
3471   target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3472                           target);
3473
3474   return target;
3475 }
3476
3477 /* Subroutine of expmed_mult_highpart.  Return the MODE high part of OP.  */
3478
3479 static rtx
3480 extract_high_half (machine_mode mode, rtx op)
3481 {
3482   machine_mode wider_mode;
3483
3484   if (mode == word_mode)
3485     return gen_highpart (mode, op);
3486
3487   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3488
3489   wider_mode = GET_MODE_WIDER_MODE (mode);
3490   op = expand_shift (RSHIFT_EXPR, wider_mode, op,
3491                      GET_MODE_BITSIZE (mode), 0, 1);
3492   return convert_modes (mode, wider_mode, op, 0);
3493 }
3494
3495 /* Like expmed_mult_highpart, but only consider using a multiplication
3496    optab.  OP1 is an rtx for the constant operand.  */
3497
3498 static rtx
3499 expmed_mult_highpart_optab (machine_mode mode, rtx op0, rtx op1,
3500                             rtx target, int unsignedp, int max_cost)
3501 {
3502   rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
3503   machine_mode wider_mode;
3504   optab moptab;
3505   rtx tem;
3506   int size;
3507   bool speed = optimize_insn_for_speed_p ();
3508
3509   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3510
3511   wider_mode = GET_MODE_WIDER_MODE (mode);
3512   size = GET_MODE_BITSIZE (mode);
3513
3514   /* Firstly, try using a multiplication insn that only generates the needed
3515      high part of the product, and in the sign flavor of unsignedp.  */
3516   if (mul_highpart_cost (speed, mode) < max_cost)
3517     {
3518       moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
3519       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3520                           unsignedp, OPTAB_DIRECT);
3521       if (tem)
3522         return tem;
3523     }
3524
3525   /* Secondly, same as above, but use sign flavor opposite of unsignedp.
3526      Need to adjust the result after the multiplication.  */
3527   if (size - 1 < BITS_PER_WORD
3528       && (mul_highpart_cost (speed, mode)
3529           + 2 * shift_cost (speed, mode, size-1)
3530           + 4 * add_cost (speed, mode) < max_cost))
3531     {
3532       moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
3533       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3534                           unsignedp, OPTAB_DIRECT);
3535       if (tem)
3536         /* We used the wrong signedness.  Adjust the result.  */
3537         return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3538                                             tem, unsignedp);
3539     }
3540
3541   /* Try widening multiplication.  */
3542   moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
3543   if (widening_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3544       && mul_widen_cost (speed, wider_mode) < max_cost)
3545     {
3546       tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
3547                           unsignedp, OPTAB_WIDEN);
3548       if (tem)
3549         return extract_high_half (mode, tem);
3550     }
3551
3552   /* Try widening the mode and perform a non-widening multiplication.  */
3553   if (optab_handler (smul_optab, wider_mode) != CODE_FOR_nothing
3554       && size - 1 < BITS_PER_WORD
3555       && (mul_cost (speed, wider_mode) + shift_cost (speed, mode, size-1)
3556           < max_cost))
3557     {
3558       rtx_insn *insns;
3559       rtx wop0, wop1;
3560
3561       /* We need to widen the operands, for example to ensure the
3562          constant multiplier is correctly sign or zero extended.
3563          Use a sequence to clean-up any instructions emitted by
3564          the conversions if things don't work out.  */
3565       start_sequence ();
3566       wop0 = convert_modes (wider_mode, mode, op0, unsignedp);
3567       wop1 = convert_modes (wider_mode, mode, op1, unsignedp);
3568       tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0,
3569                           unsignedp, OPTAB_WIDEN);
3570       insns = get_insns ();
3571       end_sequence ();
3572
3573       if (tem)
3574         {
3575           emit_insn (insns);
3576           return extract_high_half (mode, tem);
3577         }
3578     }
3579
3580   /* Try widening multiplication of opposite signedness, and adjust.  */
3581   moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
3582   if (widening_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3583       && size - 1 < BITS_PER_WORD
3584       && (mul_widen_cost (speed, wider_mode)
3585           + 2 * shift_cost (speed, mode, size-1)
3586           + 4 * add_cost (speed, mode) < max_cost))
3587     {
3588       tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3589                           NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3590       if (tem != 0)
3591         {
3592           tem = extract_high_half (mode, tem);
3593           /* We used the wrong signedness.  Adjust the result.  */
3594           return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3595                                               target, unsignedp);
3596         }
3597     }
3598
3599   return 0;
3600 }
3601
3602 /* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant),
3603    putting the high half of the result in TARGET if that is convenient,
3604    and return where the result is.  If the operation can not be performed,
3605    0 is returned.
3606
3607    MODE is the mode of operation and result.
3608
3609    UNSIGNEDP nonzero means unsigned multiply.
3610
3611    MAX_COST is the total allowed cost for the expanded RTL.  */
3612
3613 static rtx
3614 expmed_mult_highpart (machine_mode mode, rtx op0, rtx op1,
3615                       rtx target, int unsignedp, int max_cost)
3616 {
3617   machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
3618   unsigned HOST_WIDE_INT cnst1;
3619   int extra_cost;
3620   bool sign_adjust = false;
3621   enum mult_variant variant;
3622   struct algorithm alg;
3623   rtx tem;
3624   bool speed = optimize_insn_for_speed_p ();
3625
3626   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3627   /* We can't support modes wider than HOST_BITS_PER_INT.  */
3628   gcc_assert (HWI_COMPUTABLE_MODE_P (mode));
3629
3630   cnst1 = INTVAL (op1) & GET_MODE_MASK (mode);
3631
3632   /* We can't optimize modes wider than BITS_PER_WORD.
3633      ??? We might be able to perform double-word arithmetic if
3634      mode == word_mode, however all the cost calculations in
3635      synth_mult etc. assume single-word operations.  */
3636   if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3637     return expmed_mult_highpart_optab (mode, op0, op1, target,
3638                                        unsignedp, max_cost);
3639
3640   extra_cost = shift_cost (speed, mode, GET_MODE_BITSIZE (mode) - 1);
3641
3642   /* Check whether we try to multiply by a negative constant.  */
3643   if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3644     {
3645       sign_adjust = true;
3646       extra_cost += add_cost (speed, mode);
3647     }
3648
3649   /* See whether shift/add multiplication is cheap enough.  */
3650   if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3651                            max_cost - extra_cost))
3652     {
3653       /* See whether the specialized multiplication optabs are
3654          cheaper than the shift/add version.  */
3655       tem = expmed_mult_highpart_optab (mode, op0, op1, target, unsignedp,
3656                                         alg.cost.cost + extra_cost);
3657       if (tem)
3658         return tem;
3659
3660       tem = convert_to_mode (wider_mode, op0, unsignedp);
3661       tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3662       tem = extract_high_half (mode, tem);
3663
3664       /* Adjust result for signedness.  */
3665       if (sign_adjust)
3666         tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3667
3668       return tem;
3669     }
3670   return expmed_mult_highpart_optab (mode, op0, op1, target,
3671                                      unsignedp, max_cost);
3672 }
3673
3674
3675 /* Expand signed modulus of OP0 by a power of two D in mode MODE.  */
3676
3677 static rtx
3678 expand_smod_pow2 (machine_mode mode, rtx op0, HOST_WIDE_INT d)
3679 {
3680   rtx result, temp, shift;
3681   rtx_code_label *label;
3682   int logd;
3683   int prec = GET_MODE_PRECISION (mode);
3684
3685   logd = floor_log2 (d);
3686   result = gen_reg_rtx (mode);
3687
3688   /* Avoid conditional branches when they're expensive.  */
3689   if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2
3690       && optimize_insn_for_speed_p ())
3691     {
3692       rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3693                                       mode, 0, -1);
3694       if (signmask)
3695         {
3696           HOST_WIDE_INT masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3697           signmask = force_reg (mode, signmask);
3698           shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd);
3699
3700           /* Use the rtx_cost of a LSHIFTRT instruction to determine
3701              which instruction sequence to use.  If logical right shifts
3702              are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3703              use a LSHIFTRT, 1 ADD, 1 SUB and an AND.  */
3704
3705           temp = gen_rtx_LSHIFTRT (mode, result, shift);
3706           if (optab_handler (lshr_optab, mode) == CODE_FOR_nothing
3707               || (set_src_cost (temp, optimize_insn_for_speed_p ())
3708                   > COSTS_N_INSNS (2)))
3709             {
3710               temp = expand_binop (mode, xor_optab, op0, signmask,
3711                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3712               temp = expand_binop (mode, sub_optab, temp, signmask,
3713                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3714               temp = expand_binop (mode, and_optab, temp,
3715                                    gen_int_mode (masklow, mode),
3716                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3717               temp = expand_binop (mode, xor_optab, temp, signmask,
3718                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3719               temp = expand_binop (mode, sub_optab, temp, signmask,
3720                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3721             }
3722           else
3723             {
3724               signmask = expand_binop (mode, lshr_optab, signmask, shift,
3725                                        NULL_RTX, 1, OPTAB_LIB_WIDEN);
3726               signmask = force_reg (mode, signmask);
3727
3728               temp = expand_binop (mode, add_optab, op0, signmask,
3729                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3730               temp = expand_binop (mode, and_optab, temp,
3731                                    gen_int_mode (masklow, mode),
3732                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3733               temp = expand_binop (mode, sub_optab, temp, signmask,
3734                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3735             }
3736           return temp;
3737         }
3738     }
3739
3740   /* Mask contains the mode's signbit and the significant bits of the
3741      modulus.  By including the signbit in the operation, many targets
3742      can avoid an explicit compare operation in the following comparison
3743      against zero.  */
3744   wide_int mask = wi::mask (logd, false, prec);
3745   mask = wi::set_bit (mask, prec - 1);
3746
3747   temp = expand_binop (mode, and_optab, op0,
3748                        immed_wide_int_const (mask, mode),
3749                        result, 1, OPTAB_LIB_WIDEN);
3750   if (temp != result)
3751     emit_move_insn (result, temp);
3752
3753   label = gen_label_rtx ();
3754   do_cmp_and_jump (result, const0_rtx, GE, mode, label);
3755
3756   temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
3757                        0, OPTAB_LIB_WIDEN);
3758
3759   mask = wi::mask (logd, true, prec);
3760   temp = expand_binop (mode, ior_optab, temp,
3761                        immed_wide_int_const (mask, mode),
3762                        result, 1, OPTAB_LIB_WIDEN);
3763   temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
3764                        0, OPTAB_LIB_WIDEN);
3765   if (temp != result)
3766     emit_move_insn (result, temp);
3767   emit_label (label);
3768   return result;
3769 }
3770
3771 /* Expand signed division of OP0 by a power of two D in mode MODE.
3772    This routine is only called for positive values of D.  */
3773
3774 static rtx
3775 expand_sdiv_pow2 (machine_mode mode, rtx op0, HOST_WIDE_INT d)
3776 {
3777   rtx temp;
3778   rtx_code_label *label;
3779   int logd;
3780
3781   logd = floor_log2 (d);
3782
3783   if (d == 2
3784       && BRANCH_COST (optimize_insn_for_speed_p (),
3785                       false) >= 1)
3786     {
3787       temp = gen_reg_rtx (mode);
3788       temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1);
3789       temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3790                            0, OPTAB_LIB_WIDEN);
3791       return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3792     }
3793
3794   if (HAVE_conditional_move
3795       && BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2)
3796     {
3797       rtx temp2;
3798
3799       start_sequence ();
3800       temp2 = copy_to_mode_reg (mode, op0);
3801       temp = expand_binop (mode, add_optab, temp2, gen_int_mode (d - 1, mode),
3802                            NULL_RTX, 0, OPTAB_LIB_WIDEN);
3803       temp = force_reg (mode, temp);
3804
3805       /* Construct "temp2 = (temp2 < 0) ? temp : temp2".  */
3806       temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx,
3807                                      mode, temp, temp2, mode, 0);
3808       if (temp2)
3809         {
3810           rtx_insn *seq = get_insns ();
3811           end_sequence ();
3812           emit_insn (seq);
3813           return expand_shift (RSHIFT_EXPR, mode, temp2, logd, NULL_RTX, 0);
3814         }
3815       end_sequence ();
3816     }
3817
3818   if (BRANCH_COST (optimize_insn_for_speed_p (),
3819                    false) >= 2)
3820     {
3821       int ushift = GET_MODE_BITSIZE (mode) - logd;
3822
3823       temp = gen_reg_rtx (mode);
3824       temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1);
3825       if (GET_MODE_BITSIZE (mode) >= BITS_PER_WORD
3826           || shift_cost (optimize_insn_for_speed_p (), mode, ushift)
3827              > COSTS_N_INSNS (1))
3828         temp = expand_binop (mode, and_optab, temp, gen_int_mode (d - 1, mode),
3829                              NULL_RTX, 0, OPTAB_LIB_WIDEN);
3830       else
3831         temp = expand_shift (RSHIFT_EXPR, mode, temp,
3832                              ushift, NULL_RTX, 1);
3833       temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3834                            0, OPTAB_LIB_WIDEN);
3835       return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3836     }
3837
3838   label = gen_label_rtx ();
3839   temp = copy_to_mode_reg (mode, op0);
3840   do_cmp_and_jump (temp, const0_rtx, GE, mode, label);
3841   expand_inc (temp, gen_int_mode (d - 1, mode));
3842   emit_label (label);
3843   return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3844 }
3845 \f
3846 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3847    if that is convenient, and returning where the result is.
3848    You may request either the quotient or the remainder as the result;
3849    specify REM_FLAG nonzero to get the remainder.
3850
3851    CODE is the expression code for which kind of division this is;
3852    it controls how rounding is done.  MODE is the machine mode to use.
3853    UNSIGNEDP nonzero means do unsigned division.  */
3854
3855 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3856    and then correct it by or'ing in missing high bits
3857    if result of ANDI is nonzero.
3858    For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3859    This could optimize to a bfexts instruction.
3860    But C doesn't use these operations, so their optimizations are
3861    left for later.  */
3862 /* ??? For modulo, we don't actually need the highpart of the first product,
3863    the low part will do nicely.  And for small divisors, the second multiply
3864    can also be a low-part only multiply or even be completely left out.
3865    E.g. to calculate the remainder of a division by 3 with a 32 bit
3866    multiply, multiply with 0x55555556 and extract the upper two bits;
3867    the result is exact for inputs up to 0x1fffffff.
3868    The input range can be reduced by using cross-sum rules.
3869    For odd divisors >= 3, the following table gives right shift counts
3870    so that if a number is shifted by an integer multiple of the given
3871    amount, the remainder stays the same:
3872    2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3873    14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3874    0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3875    20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3876    0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3877
3878    Cross-sum rules for even numbers can be derived by leaving as many bits
3879    to the right alone as the divisor has zeros to the right.
3880    E.g. if x is an unsigned 32 bit number:
3881    (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3882    */
3883
3884 rtx
3885 expand_divmod (int rem_flag, enum tree_code code, machine_mode mode,
3886                rtx op0, rtx op1, rtx target, int unsignedp)
3887 {
3888   machine_mode compute_mode;
3889   rtx tquotient;
3890   rtx quotient = 0, remainder = 0;
3891   rtx_insn *last;
3892   int size;
3893   rtx_insn *insn;
3894   optab optab1, optab2;
3895   int op1_is_constant, op1_is_pow2 = 0;
3896   int max_cost, extra_cost;
3897   static HOST_WIDE_INT last_div_const = 0;
3898   bool speed = optimize_insn_for_speed_p ();
3899
3900   op1_is_constant = CONST_INT_P (op1);
3901   if (op1_is_constant)
3902     {
3903       unsigned HOST_WIDE_INT ext_op1 = UINTVAL (op1);
3904       if (unsignedp)
3905         ext_op1 &= GET_MODE_MASK (mode);
3906       op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3907                      || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3908     }
3909
3910   /*
3911      This is the structure of expand_divmod:
3912
3913      First comes code to fix up the operands so we can perform the operations
3914      correctly and efficiently.
3915
3916      Second comes a switch statement with code specific for each rounding mode.
3917      For some special operands this code emits all RTL for the desired
3918      operation, for other cases, it generates only a quotient and stores it in
3919      QUOTIENT.  The case for trunc division/remainder might leave quotient = 0,
3920      to indicate that it has not done anything.
3921
3922      Last comes code that finishes the operation.  If QUOTIENT is set and
3923      REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1.  If
3924      QUOTIENT is not set, it is computed using trunc rounding.
3925
3926      We try to generate special code for division and remainder when OP1 is a
3927      constant.  If |OP1| = 2**n we can use shifts and some other fast
3928      operations.  For other values of OP1, we compute a carefully selected
3929      fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3930      by m.
3931
3932      In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3933      half of the product.  Different strategies for generating the product are
3934      implemented in expmed_mult_highpart.
3935
3936      If what we actually want is the remainder, we generate that by another
3937      by-constant multiplication and a subtraction.  */
3938
3939   /* We shouldn't be called with OP1 == const1_rtx, but some of the
3940      code below will malfunction if we are, so check here and handle
3941      the special case if so.  */
3942   if (op1 == const1_rtx)
3943     return rem_flag ? const0_rtx : op0;
3944
3945     /* When dividing by -1, we could get an overflow.
3946      negv_optab can handle overflows.  */
3947   if (! unsignedp && op1 == constm1_rtx)
3948     {
3949       if (rem_flag)
3950         return const0_rtx;
3951       return expand_unop (mode, flag_trapv && GET_MODE_CLASS (mode) == MODE_INT
3952                           ? negv_optab : neg_optab, op0, target, 0);
3953     }
3954
3955   if (target
3956       /* Don't use the function value register as a target
3957          since we have to read it as well as write it,
3958          and function-inlining gets confused by this.  */
3959       && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3960           /* Don't clobber an operand while doing a multi-step calculation.  */
3961           || ((rem_flag || op1_is_constant)
3962               && (reg_mentioned_p (target, op0)
3963                   || (MEM_P (op0) && MEM_P (target))))
3964           || reg_mentioned_p (target, op1)
3965           || (MEM_P (op1) && MEM_P (target))))
3966     target = 0;
3967
3968   /* Get the mode in which to perform this computation.  Normally it will
3969      be MODE, but sometimes we can't do the desired operation in MODE.
3970      If so, pick a wider mode in which we can do the operation.  Convert
3971      to that mode at the start to avoid repeated conversions.
3972
3973      First see what operations we need.  These depend on the expression
3974      we are evaluating.  (We assume that divxx3 insns exist under the
3975      same conditions that modxx3 insns and that these insns don't normally
3976      fail.  If these assumptions are not correct, we may generate less
3977      efficient code in some cases.)
3978
3979      Then see if we find a mode in which we can open-code that operation
3980      (either a division, modulus, or shift).  Finally, check for the smallest
3981      mode for which we can do the operation with a library call.  */
3982
3983   /* We might want to refine this now that we have division-by-constant
3984      optimization.  Since expmed_mult_highpart tries so many variants, it is
3985      not straightforward to generalize this.  Maybe we should make an array
3986      of possible modes in init_expmed?  Save this for GCC 2.7.  */
3987
3988   optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3989             ? (unsignedp ? lshr_optab : ashr_optab)
3990             : (unsignedp ? udiv_optab : sdiv_optab));
3991   optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3992             ? optab1
3993             : (unsignedp ? udivmod_optab : sdivmod_optab));
3994
3995   for (compute_mode = mode; compute_mode != VOIDmode;
3996        compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3997     if (optab_handler (optab1, compute_mode) != CODE_FOR_nothing
3998         || optab_handler (optab2, compute_mode) != CODE_FOR_nothing)
3999       break;
4000
4001   if (compute_mode == VOIDmode)
4002     for (compute_mode = mode; compute_mode != VOIDmode;
4003          compute_mode = GET_MODE_WIDER_MODE (compute_mode))
4004       if (optab_libfunc (optab1, compute_mode)
4005           || optab_libfunc (optab2, compute_mode))
4006         break;
4007
4008   /* If we still couldn't find a mode, use MODE, but expand_binop will
4009      probably die.  */
4010   if (compute_mode == VOIDmode)
4011     compute_mode = mode;
4012
4013   if (target && GET_MODE (target) == compute_mode)
4014     tquotient = target;
4015   else
4016     tquotient = gen_reg_rtx (compute_mode);
4017
4018   size = GET_MODE_BITSIZE (compute_mode);
4019 #if 0
4020   /* It should be possible to restrict the precision to GET_MODE_BITSIZE
4021      (mode), and thereby get better code when OP1 is a constant.  Do that
4022      later.  It will require going over all usages of SIZE below.  */
4023   size = GET_MODE_BITSIZE (mode);
4024 #endif
4025
4026   /* Only deduct something for a REM if the last divide done was
4027      for a different constant.   Then set the constant of the last
4028      divide.  */
4029   max_cost = (unsignedp
4030               ? udiv_cost (speed, compute_mode)
4031               : sdiv_cost (speed, compute_mode));
4032   if (rem_flag && ! (last_div_const != 0 && op1_is_constant
4033                      && INTVAL (op1) == last_div_const))
4034     max_cost -= (mul_cost (speed, compute_mode)
4035                  + add_cost (speed, compute_mode));
4036
4037   last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
4038
4039   /* Now convert to the best mode to use.  */
4040   if (compute_mode != mode)
4041     {
4042       op0 = convert_modes (compute_mode, mode, op0, unsignedp);
4043       op1 = convert_modes (compute_mode, mode, op1, unsignedp);
4044
4045       /* convert_modes may have placed op1 into a register, so we
4046          must recompute the following.  */
4047       op1_is_constant = CONST_INT_P (op1);
4048       op1_is_pow2 = (op1_is_constant
4049                      && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4050                           || (! unsignedp
4051                               && EXACT_POWER_OF_2_OR_ZERO_P (-UINTVAL (op1))))));
4052     }
4053
4054   /* If one of the operands is a volatile MEM, copy it into a register.  */
4055
4056   if (MEM_P (op0) && MEM_VOLATILE_P (op0))
4057     op0 = force_reg (compute_mode, op0);
4058   if (MEM_P (op1) && MEM_VOLATILE_P (op1))
4059     op1 = force_reg (compute_mode, op1);
4060
4061   /* If we need the remainder or if OP1 is constant, we need to
4062      put OP0 in a register in case it has any queued subexpressions.  */
4063   if (rem_flag || op1_is_constant)
4064     op0 = force_reg (compute_mode, op0);
4065
4066   last = get_last_insn ();
4067
4068   /* Promote floor rounding to trunc rounding for unsigned operations.  */
4069   if (unsignedp)
4070     {
4071       if (code == FLOOR_DIV_EXPR)
4072         code = TRUNC_DIV_EXPR;
4073       if (code == FLOOR_MOD_EXPR)
4074         code = TRUNC_MOD_EXPR;
4075       if (code == EXACT_DIV_EXPR && op1_is_pow2)
4076         code = TRUNC_DIV_EXPR;
4077     }
4078
4079   if (op1 != const0_rtx)
4080     switch (code)
4081       {
4082       case TRUNC_MOD_EXPR:
4083       case TRUNC_DIV_EXPR:
4084         if (op1_is_constant)
4085           {
4086             if (unsignedp)
4087               {
4088                 unsigned HOST_WIDE_INT mh, ml;
4089                 int pre_shift, post_shift;
4090                 int dummy;
4091                 unsigned HOST_WIDE_INT d = (INTVAL (op1)
4092                                             & GET_MODE_MASK (compute_mode));
4093
4094                 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4095                   {
4096                     pre_shift = floor_log2 (d);
4097                     if (rem_flag)
4098                       {
4099                         unsigned HOST_WIDE_INT mask
4100                           = ((unsigned HOST_WIDE_INT) 1 << pre_shift) - 1;
4101                         remainder
4102                           = expand_binop (compute_mode, and_optab, op0,
4103                                           gen_int_mode (mask, compute_mode),
4104                                           remainder, 1,
4105                                           OPTAB_LIB_WIDEN);
4106                         if (remainder)
4107                           return gen_lowpart (mode, remainder);
4108                       }
4109                     quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4110                                              pre_shift, tquotient, 1);
4111                   }
4112                 else if (size <= HOST_BITS_PER_WIDE_INT)
4113                   {
4114                     if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
4115                       {
4116                         /* Most significant bit of divisor is set; emit an scc
4117                            insn.  */
4118                         quotient = emit_store_flag_force (tquotient, GEU, op0, op1,
4119                                                           compute_mode, 1, 1);
4120                       }
4121                     else
4122                       {
4123                         /* Find a suitable multiplier and right shift count
4124                            instead of multiplying with D.  */
4125
4126                         mh = choose_multiplier (d, size, size,
4127                                                 &ml, &post_shift, &dummy);
4128
4129                         /* If the suggested multiplier is more than SIZE bits,
4130                            we can do better for even divisors, using an
4131                            initial right shift.  */
4132                         if (mh != 0 && (d & 1) == 0)
4133                           {
4134                             pre_shift = floor_log2 (d & -d);
4135                             mh = choose_multiplier (d >> pre_shift, size,
4136                                                     size - pre_shift,
4137                                                     &ml, &post_shift, &dummy);
4138                             gcc_assert (!mh);
4139                           }
4140                         else
4141                           pre_shift = 0;
4142
4143                         if (mh != 0)
4144                           {
4145                             rtx t1, t2, t3, t4;
4146
4147                             if (post_shift - 1 >= BITS_PER_WORD)
4148                               goto fail1;
4149
4150                             extra_cost
4151                               = (shift_cost (speed, compute_mode, post_shift - 1)
4152                                  + shift_cost (speed, compute_mode, 1)
4153                                  + 2 * add_cost (speed, compute_mode));
4154                             t1 = expmed_mult_highpart
4155                               (compute_mode, op0,
4156                                gen_int_mode (ml, compute_mode),
4157                                NULL_RTX, 1, max_cost - extra_cost);
4158                             if (t1 == 0)
4159                               goto fail1;
4160                             t2 = force_operand (gen_rtx_MINUS (compute_mode,
4161                                                                op0, t1),
4162                                                 NULL_RTX);
4163                             t3 = expand_shift (RSHIFT_EXPR, compute_mode,
4164                                                t2, 1, NULL_RTX, 1);
4165                             t4 = force_operand (gen_rtx_PLUS (compute_mode,
4166                                                               t1, t3),
4167                                                 NULL_RTX);
4168                             quotient = expand_shift
4169                               (RSHIFT_EXPR, compute_mode, t4,
4170                                post_shift - 1, tquotient, 1);
4171                           }
4172                         else
4173                           {
4174                             rtx t1, t2;
4175
4176                             if (pre_shift >= BITS_PER_WORD
4177                                 || post_shift >= BITS_PER_WORD)
4178                               goto fail1;
4179
4180                             t1 = expand_shift
4181                               (RSHIFT_EXPR, compute_mode, op0,
4182                                pre_shift, NULL_RTX, 1);
4183                             extra_cost
4184                               = (shift_cost (speed, compute_mode, pre_shift)
4185                                  + shift_cost (speed, compute_mode, post_shift));
4186                             t2 = expmed_mult_highpart
4187                               (compute_mode, t1,
4188                                gen_int_mode (ml, compute_mode),
4189                                NULL_RTX, 1, max_cost - extra_cost);
4190                             if (t2 == 0)
4191                               goto fail1;
4192                             quotient = expand_shift
4193                               (RSHIFT_EXPR, compute_mode, t2,
4194                                post_shift, tquotient, 1);
4195                           }
4196                       }
4197                   }
4198                 else            /* Too wide mode to use tricky code */
4199                   break;
4200
4201                 insn = get_last_insn ();
4202                 if (insn != last)
4203                   set_dst_reg_note (insn, REG_EQUAL,
4204                                     gen_rtx_UDIV (compute_mode, op0, op1),
4205                                     quotient);
4206               }
4207             else                /* TRUNC_DIV, signed */
4208               {
4209                 unsigned HOST_WIDE_INT ml;
4210                 int lgup, post_shift;
4211                 rtx mlr;
4212                 HOST_WIDE_INT d = INTVAL (op1);
4213                 unsigned HOST_WIDE_INT abs_d;
4214
4215                 /* Since d might be INT_MIN, we have to cast to
4216                    unsigned HOST_WIDE_INT before negating to avoid
4217                    undefined signed overflow.  */
4218                 abs_d = (d >= 0
4219                          ? (unsigned HOST_WIDE_INT) d
4220                          : - (unsigned HOST_WIDE_INT) d);
4221
4222                 /* n rem d = n rem -d */
4223                 if (rem_flag && d < 0)
4224                   {
4225                     d = abs_d;
4226                     op1 = gen_int_mode (abs_d, compute_mode);
4227                   }
4228
4229                 if (d == 1)
4230                   quotient = op0;
4231                 else if (d == -1)
4232                   quotient = expand_unop (compute_mode, neg_optab, op0,
4233                                           tquotient, 0);
4234                 else if (HOST_BITS_PER_WIDE_INT >= size
4235                          && abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
4236                   {
4237                     /* This case is not handled correctly below.  */
4238                     quotient = emit_store_flag (tquotient, EQ, op0, op1,
4239                                                 compute_mode, 1, 1);
4240                     if (quotient == 0)
4241                       goto fail1;
4242                   }
4243                 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
4244                          && (rem_flag
4245                              ? smod_pow2_cheap (speed, compute_mode)
4246                              : sdiv_pow2_cheap (speed, compute_mode))
4247                          /* We assume that cheap metric is true if the
4248                             optab has an expander for this mode.  */
4249                          && ((optab_handler ((rem_flag ? smod_optab
4250                                               : sdiv_optab),
4251                                              compute_mode)
4252                               != CODE_FOR_nothing)
4253                              || (optab_handler (sdivmod_optab,
4254                                                 compute_mode)
4255                                  != CODE_FOR_nothing)))
4256                   ;
4257                 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
4258                   {
4259                     if (rem_flag)
4260                       {
4261                         remainder = expand_smod_pow2 (compute_mode, op0, d);
4262                         if (remainder)
4263                           return gen_lowpart (mode, remainder);
4264                       }
4265
4266                     if (sdiv_pow2_cheap (speed, compute_mode)
4267                         && ((optab_handler (sdiv_optab, compute_mode)
4268                              != CODE_FOR_nothing)
4269                             || (optab_handler (sdivmod_optab, compute_mode)
4270                                 != CODE_FOR_nothing)))
4271                       quotient = expand_divmod (0, TRUNC_DIV_EXPR,
4272                                                 compute_mode, op0,
4273                                                 gen_int_mode (abs_d,
4274                                                               compute_mode),
4275                                                 NULL_RTX, 0);
4276                     else
4277                       quotient = expand_sdiv_pow2 (compute_mode, op0, abs_d);
4278
4279                     /* We have computed OP0 / abs(OP1).  If OP1 is negative,
4280                        negate the quotient.  */
4281                     if (d < 0)
4282                       {
4283                         insn = get_last_insn ();
4284                         if (insn != last
4285                             && abs_d < ((unsigned HOST_WIDE_INT) 1
4286                                         << (HOST_BITS_PER_WIDE_INT - 1)))
4287                           set_dst_reg_note (insn, REG_EQUAL,
4288                                             gen_rtx_DIV (compute_mode, op0,
4289                                                          gen_int_mode
4290                                                            (abs_d,
4291                                                             compute_mode)),
4292                                             quotient);
4293
4294                         quotient = expand_unop (compute_mode, neg_optab,
4295                                                 quotient, quotient, 0);
4296                       }
4297                   }
4298                 else if (size <= HOST_BITS_PER_WIDE_INT)
4299                   {
4300                     choose_multiplier (abs_d, size, size - 1,
4301                                        &ml, &post_shift, &lgup);
4302                     if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
4303                       {
4304                         rtx t1, t2, t3;
4305
4306                         if (post_shift >= BITS_PER_WORD
4307                             || size - 1 >= BITS_PER_WORD)
4308                           goto fail1;
4309
4310                         extra_cost = (shift_cost (speed, compute_mode, post_shift)
4311                                       + shift_cost (speed, compute_mode, size - 1)
4312                                       + add_cost (speed, compute_mode));
4313                         t1 = expmed_mult_highpart
4314                           (compute_mode, op0, gen_int_mode (ml, compute_mode),
4315                            NULL_RTX, 0, max_cost - extra_cost);
4316                         if (t1 == 0)
4317                           goto fail1;
4318                         t2 = expand_shift
4319                           (RSHIFT_EXPR, compute_mode, t1,
4320                            post_shift, NULL_RTX, 0);
4321                         t3 = expand_shift
4322                           (RSHIFT_EXPR, compute_mode, op0,
4323                            size - 1, NULL_RTX, 0);
4324                         if (d < 0)
4325                           quotient
4326                             = force_operand (gen_rtx_MINUS (compute_mode,
4327                                                             t3, t2),
4328                                              tquotient);
4329                         else
4330                           quotient
4331                             = force_operand (gen_rtx_MINUS (compute_mode,
4332                                                             t2, t3),
4333                                              tquotient);
4334                       }
4335                     else
4336                       {
4337                         rtx t1, t2, t3, t4;
4338
4339                         if (post_shift >= BITS_PER_WORD
4340                             || size - 1 >= BITS_PER_WORD)
4341                           goto fail1;
4342
4343                         ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
4344                         mlr = gen_int_mode (ml, compute_mode);
4345                         extra_cost = (shift_cost (speed, compute_mode, post_shift)
4346                                       + shift_cost (speed, compute_mode, size - 1)
4347                                       + 2 * add_cost (speed, compute_mode));
4348                         t1 = expmed_mult_highpart (compute_mode, op0, mlr,
4349                                                    NULL_RTX, 0,
4350                                                    max_cost - extra_cost);
4351                         if (t1 == 0)
4352                           goto fail1;
4353                         t2 = force_operand (gen_rtx_PLUS (compute_mode,
4354                                                           t1, op0),
4355                                             NULL_RTX);
4356                         t3 = expand_shift
4357                           (RSHIFT_EXPR, compute_mode, t2,
4358                            post_shift, NULL_RTX, 0);
4359                         t4 = expand_shift
4360                           (RSHIFT_EXPR, compute_mode, op0,
4361                            size - 1, NULL_RTX, 0);
4362                         if (d < 0)
4363                           quotient
4364                             = force_operand (gen_rtx_MINUS (compute_mode,
4365                                                             t4, t3),
4366                                              tquotient);
4367                         else
4368                           quotient
4369                             = force_operand (gen_rtx_MINUS (compute_mode,
4370                                                             t3, t4),
4371                                              tquotient);
4372                       }
4373                   }
4374                 else            /* Too wide mode to use tricky code */
4375                   break;
4376
4377                 insn = get_last_insn ();
4378                 if (insn != last)
4379                   set_dst_reg_note (insn, REG_EQUAL,
4380                                     gen_rtx_DIV (compute_mode, op0, op1),
4381                                     quotient);
4382               }
4383             break;
4384           }
4385       fail1:
4386         delete_insns_since (last);
4387         break;
4388
4389       case FLOOR_DIV_EXPR:
4390       case FLOOR_MOD_EXPR:
4391       /* We will come here only for signed operations.  */
4392         if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4393           {
4394             unsigned HOST_WIDE_INT mh, ml;
4395             int pre_shift, lgup, post_shift;
4396             HOST_WIDE_INT d = INTVAL (op1);
4397
4398             if (d > 0)
4399               {
4400                 /* We could just as easily deal with negative constants here,
4401                    but it does not seem worth the trouble for GCC 2.6.  */
4402                 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4403                   {
4404                     pre_shift = floor_log2 (d);
4405                     if (rem_flag)
4406                       {
4407                         unsigned HOST_WIDE_INT mask
4408                           = ((unsigned HOST_WIDE_INT) 1 << pre_shift) - 1;
4409                         remainder = expand_binop
4410                           (compute_mode, and_optab, op0,
4411                            gen_int_mode (mask, compute_mode),
4412                            remainder, 0, OPTAB_LIB_WIDEN);
4413                         if (remainder)
4414                           return gen_lowpart (mode, remainder);
4415                       }
4416                     quotient = expand_shift
4417                       (RSHIFT_EXPR, compute_mode, op0,
4418                        pre_shift, tquotient, 0);
4419                   }
4420                 else
4421                   {
4422                     rtx t1, t2, t3, t4;
4423
4424                     mh = choose_multiplier (d, size, size - 1,
4425                                             &ml, &post_shift, &lgup);
4426                     gcc_assert (!mh);
4427
4428                     if (post_shift < BITS_PER_WORD
4429                         && size - 1 < BITS_PER_WORD)
4430                       {
4431                         t1 = expand_shift
4432                           (RSHIFT_EXPR, compute_mode, op0,
4433                            size - 1, NULL_RTX, 0);
4434                         t2 = expand_binop (compute_mode, xor_optab, op0, t1,
4435                                            NULL_RTX, 0, OPTAB_WIDEN);
4436                         extra_cost = (shift_cost (speed, compute_mode, post_shift)
4437                                       + shift_cost (speed, compute_mode, size - 1)
4438                                       + 2 * add_cost (speed, compute_mode));
4439                         t3 = expmed_mult_highpart
4440                           (compute_mode, t2, gen_int_mode (ml, compute_mode),
4441                            NULL_RTX, 1, max_cost - extra_cost);
4442                         if (t3 != 0)
4443                           {
4444                             t4 = expand_shift
4445                               (RSHIFT_EXPR, compute_mode, t3,
4446                                post_shift, NULL_RTX, 1);
4447                             quotient = expand_binop (compute_mode, xor_optab,
4448                                                      t4, t1, tquotient, 0,
4449                                                      OPTAB_WIDEN);
4450                           }
4451                       }
4452                   }
4453               }
4454             else
4455               {
4456                 rtx nsign, t1, t2, t3, t4;
4457                 t1 = force_operand (gen_rtx_PLUS (compute_mode,
4458                                                   op0, constm1_rtx), NULL_RTX);
4459                 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
4460                                    0, OPTAB_WIDEN);
4461                 nsign = expand_shift
4462                   (RSHIFT_EXPR, compute_mode, t2,
4463                    size - 1, NULL_RTX, 0);
4464                 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
4465                                     NULL_RTX);
4466                 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
4467                                     NULL_RTX, 0);
4468                 if (t4)
4469                   {
4470                     rtx t5;
4471                     t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
4472                                       NULL_RTX, 0);
4473                     quotient = force_operand (gen_rtx_PLUS (compute_mode,
4474                                                             t4, t5),
4475                                               tquotient);
4476                   }
4477               }
4478           }
4479
4480         if (quotient != 0)
4481           break;
4482         delete_insns_since (last);
4483
4484         /* Try using an instruction that produces both the quotient and
4485            remainder, using truncation.  We can easily compensate the quotient
4486            or remainder to get floor rounding, once we have the remainder.
4487            Notice that we compute also the final remainder value here,
4488            and return the result right away.  */
4489         if (target == 0 || GET_MODE (target) != compute_mode)
4490           target = gen_reg_rtx (compute_mode);
4491
4492         if (rem_flag)
4493           {
4494             remainder
4495               = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4496             quotient = gen_reg_rtx (compute_mode);
4497           }
4498         else
4499           {
4500             quotient
4501               = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4502             remainder = gen_reg_rtx (compute_mode);
4503           }
4504
4505         if (expand_twoval_binop (sdivmod_optab, op0, op1,
4506                                  quotient, remainder, 0))
4507           {
4508             /* This could be computed with a branch-less sequence.
4509                Save that for later.  */
4510             rtx tem;
4511             rtx_code_label *label = gen_label_rtx ();
4512             do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
4513             tem = expand_binop (compute_mode, xor_optab, op0, op1,
4514                                 NULL_RTX, 0, OPTAB_WIDEN);
4515             do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
4516             expand_dec (quotient, const1_rtx);
4517             expand_inc (remainder, op1);
4518             emit_label (label);
4519             return gen_lowpart (mode, rem_flag ? remainder : quotient);
4520           }
4521
4522         /* No luck with division elimination or divmod.  Have to do it
4523            by conditionally adjusting op0 *and* the result.  */
4524         {
4525           rtx_code_label *label1, *label2, *label3, *label4, *label5;
4526           rtx adjusted_op0;
4527           rtx tem;
4528
4529           quotient = gen_reg_rtx (compute_mode);
4530           adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4531           label1 = gen_label_rtx ();
4532           label2 = gen_label_rtx ();
4533           label3 = gen_label_rtx ();
4534           label4 = gen_label_rtx ();
4535           label5 = gen_label_rtx ();
4536           do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4537           do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
4538           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4539                               quotient, 0, OPTAB_LIB_WIDEN);
4540           if (tem != quotient)
4541             emit_move_insn (quotient, tem);
4542           emit_jump_insn (gen_jump (label5));
4543           emit_barrier ();
4544           emit_label (label1);
4545           expand_inc (adjusted_op0, const1_rtx);
4546           emit_jump_insn (gen_jump (label4));
4547           emit_barrier ();
4548           emit_label (label2);
4549           do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
4550           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4551                               quotient, 0, OPTAB_LIB_WIDEN);
4552           if (tem != quotient)
4553             emit_move_insn (quotient, tem);
4554           emit_jump_insn (gen_jump (label5));
4555           emit_barrier ();
4556           emit_label (label3);
4557           expand_dec (adjusted_op0, const1_rtx);
4558           emit_label (label4);
4559           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4560                               quotient, 0, OPTAB_LIB_WIDEN);
4561           if (tem != quotient)
4562             emit_move_insn (quotient, tem);
4563           expand_dec (quotient, const1_rtx);
4564           emit_label (label5);
4565         }
4566         break;
4567
4568       case CEIL_DIV_EXPR:
4569       case CEIL_MOD_EXPR:
4570         if (unsignedp)
4571           {
4572             if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
4573               {
4574                 rtx t1, t2, t3;
4575                 unsigned HOST_WIDE_INT d = INTVAL (op1);
4576                 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4577                                    floor_log2 (d), tquotient, 1);
4578                 t2 = expand_binop (compute_mode, and_optab, op0,
4579                                    gen_int_mode (d - 1, compute_mode),
4580                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
4581                 t3 = gen_reg_rtx (compute_mode);
4582                 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4583                                       compute_mode, 1, 1);
4584                 if (t3 == 0)
4585                   {
4586                     rtx_code_label *lab;
4587                     lab = gen_label_rtx ();
4588                     do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4589                     expand_inc (t1, const1_rtx);
4590                     emit_label (lab);
4591                     quotient = t1;
4592                   }
4593                 else
4594                   quotient = force_operand (gen_rtx_PLUS (compute_mode,
4595                                                           t1, t3),
4596                                             tquotient);
4597                 break;
4598               }
4599
4600             /* Try using an instruction that produces both the quotient and
4601                remainder, using truncation.  We can easily compensate the
4602                quotient or remainder to get ceiling rounding, once we have the
4603                remainder.  Notice that we compute also the final remainder
4604                value here, and return the result right away.  */
4605             if (target == 0 || GET_MODE (target) != compute_mode)
4606               target = gen_reg_rtx (compute_mode);
4607
4608             if (rem_flag)
4609               {
4610                 remainder = (REG_P (target)
4611                              ? target : gen_reg_rtx (compute_mode));
4612                 quotient = gen_reg_rtx (compute_mode);
4613               }
4614             else
4615               {
4616                 quotient = (REG_P (target)
4617                             ? target : gen_reg_rtx (compute_mode));
4618                 remainder = gen_reg_rtx (compute_mode);
4619               }
4620
4621             if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
4622                                      remainder, 1))
4623               {
4624                 /* This could be computed with a branch-less sequence.
4625                    Save that for later.  */
4626                 rtx_code_label *label = gen_label_rtx ();
4627                 do_cmp_and_jump (remainder, const0_rtx, EQ,
4628                                  compute_mode, label);
4629                 expand_inc (quotient, const1_rtx);
4630                 expand_dec (remainder, op1);
4631                 emit_label (label);
4632                 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4633               }
4634
4635             /* No luck with division elimination or divmod.  Have to do it
4636                by conditionally adjusting op0 *and* the result.  */
4637             {
4638               rtx_code_label *label1, *label2;
4639               rtx adjusted_op0, tem;
4640
4641               quotient = gen_reg_rtx (compute_mode);
4642               adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4643               label1 = gen_label_rtx ();
4644               label2 = gen_label_rtx ();
4645               do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
4646                                compute_mode, label1);
4647               emit_move_insn  (quotient, const0_rtx);
4648               emit_jump_insn (gen_jump (label2));
4649               emit_barrier ();
4650               emit_label (label1);
4651               expand_dec (adjusted_op0, const1_rtx);
4652               tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
4653                                   quotient, 1, OPTAB_LIB_WIDEN);
4654               if (tem != quotient)
4655                 emit_move_insn (quotient, tem);
4656               expand_inc (quotient, const1_rtx);
4657               emit_label (label2);
4658             }
4659           }
4660         else /* signed */
4661           {
4662             if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4663                 && INTVAL (op1) >= 0)
4664               {
4665                 /* This is extremely similar to the code for the unsigned case
4666                    above.  For 2.7 we should merge these variants, but for
4667                    2.6.1 I don't want to touch the code for unsigned since that
4668                    get used in C.  The signed case will only be used by other
4669                    languages (Ada).  */
4670
4671                 rtx t1, t2, t3;
4672                 unsigned HOST_WIDE_INT d = INTVAL (op1);
4673                 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4674                                    floor_log2 (d), tquotient, 0);
4675                 t2 = expand_binop (compute_mode, and_optab, op0,
4676                                    gen_int_mode (d - 1, compute_mode),
4677                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
4678                 t3 = gen_reg_rtx (compute_mode);
4679                 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4680                                       compute_mode, 1, 1);
4681                 if (t3 == 0)
4682                   {
4683                     rtx_code_label *lab;
4684                     lab = gen_label_rtx ();
4685                     do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4686                     expand_inc (t1, const1_rtx);
4687                     emit_label (lab);
4688                     quotient = t1;
4689                   }
4690                 else
4691                   quotient = force_operand (gen_rtx_PLUS (compute_mode,
4692                                                           t1, t3),
4693                                             tquotient);
4694                 break;
4695               }
4696
4697             /* Try using an instruction that produces both the quotient and
4698                remainder, using truncation.  We can easily compensate the
4699                quotient or remainder to get ceiling rounding, once we have the
4700                remainder.  Notice that we compute also the final remainder
4701                value here, and return the result right away.  */
4702             if (target == 0 || GET_MODE (target) != compute_mode)
4703               target = gen_reg_rtx (compute_mode);
4704             if (rem_flag)
4705               {
4706                 remainder= (REG_P (target)
4707                             ? target : gen_reg_rtx (compute_mode));
4708                 quotient = gen_reg_rtx (compute_mode);
4709               }
4710             else
4711               {
4712                 quotient = (REG_P (target)
4713                             ? target : gen_reg_rtx (compute_mode));
4714                 remainder = gen_reg_rtx (compute_mode);
4715               }
4716
4717             if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
4718                                      remainder, 0))
4719               {
4720                 /* This could be computed with a branch-less sequence.
4721                    Save that for later.  */
4722                 rtx tem;
4723                 rtx_code_label *label = gen_label_rtx ();
4724                 do_cmp_and_jump (remainder, const0_rtx, EQ,
4725                                  compute_mode, label);
4726                 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4727                                     NULL_RTX, 0, OPTAB_WIDEN);
4728                 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
4729                 expand_inc (quotient, const1_rtx);
4730                 expand_dec (remainder, op1);
4731                 emit_label (label);
4732                 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4733               }
4734
4735             /* No luck with division elimination or divmod.  Have to do it
4736                by conditionally adjusting op0 *and* the result.  */
4737             {
4738               rtx_code_label *label1, *label2, *label3, *label4, *label5;
4739               rtx adjusted_op0;
4740               rtx tem;
4741
4742               quotient = gen_reg_rtx (compute_mode);
4743               adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4744               label1 = gen_label_rtx ();
4745               label2 = gen_label_rtx ();
4746               label3 = gen_label_rtx ();
4747               label4 = gen_label_rtx ();
4748               label5 = gen_label_rtx ();
4749               do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4750               do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
4751                                compute_mode, label1);
4752               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4753                                   quotient, 0, OPTAB_LIB_WIDEN);
4754               if (tem != quotient)
4755                 emit_move_insn (quotient, tem);
4756               emit_jump_insn (gen_jump (label5));
4757               emit_barrier ();
4758               emit_label (label1);
4759               expand_dec (adjusted_op0, const1_rtx);
4760               emit_jump_insn (gen_jump (label4));
4761               emit_barrier ();
4762               emit_label (label2);
4763               do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
4764                                compute_mode, label3);
4765               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4766                                   quotient, 0, OPTAB_LIB_WIDEN);
4767               if (tem != quotient)
4768                 emit_move_insn (quotient, tem);
4769               emit_jump_insn (gen_jump (label5));
4770               emit_barrier ();
4771               emit_label (label3);
4772               expand_inc (adjusted_op0, const1_rtx);
4773               emit_label (label4);
4774               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4775                                   quotient, 0, OPTAB_LIB_WIDEN);
4776               if (tem != quotient)
4777                 emit_move_insn (quotient, tem);
4778               expand_inc (quotient, const1_rtx);
4779               emit_label (label5);
4780             }
4781           }
4782         break;
4783
4784       case EXACT_DIV_EXPR:
4785         if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4786           {
4787             HOST_WIDE_INT d = INTVAL (op1);
4788             unsigned HOST_WIDE_INT ml;
4789             int pre_shift;
4790             rtx t1;
4791
4792             pre_shift = floor_log2 (d & -d);
4793             ml = invert_mod2n (d >> pre_shift, size);
4794             t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4795                                pre_shift, NULL_RTX, unsignedp);
4796             quotient = expand_mult (compute_mode, t1,
4797                                     gen_int_mode (ml, compute_mode),
4798                                     NULL_RTX, 1);
4799
4800             insn = get_last_insn ();
4801             set_dst_reg_note (insn, REG_EQUAL,
4802                               gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
4803                                               compute_mode, op0, op1),
4804                               quotient);
4805           }
4806         break;
4807
4808       case ROUND_DIV_EXPR:
4809       case ROUND_MOD_EXPR:
4810         if (unsignedp)
4811           {
4812             rtx tem;
4813             rtx_code_label *label;
4814             label = gen_label_rtx ();
4815             quotient = gen_reg_rtx (compute_mode);
4816             remainder = gen_reg_rtx (compute_mode);
4817             if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
4818               {
4819                 rtx tem;
4820                 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
4821                                          quotient, 1, OPTAB_LIB_WIDEN);
4822                 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
4823                 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4824                                           remainder, 1, OPTAB_LIB_WIDEN);
4825               }
4826             tem = plus_constant (compute_mode, op1, -1);
4827             tem = expand_shift (RSHIFT_EXPR, compute_mode, tem, 1, NULL_RTX, 1);
4828             do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
4829             expand_inc (quotient, const1_rtx);
4830             expand_dec (remainder, op1);
4831             emit_label (label);
4832           }
4833         else
4834           {
4835             rtx abs_rem, abs_op1, tem, mask;
4836             rtx_code_label *label;
4837             label = gen_label_rtx ();
4838             quotient = gen_reg_rtx (compute_mode);
4839             remainder = gen_reg_rtx (compute_mode);
4840             if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
4841               {
4842                 rtx tem;
4843                 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
4844                                          quotient, 0, OPTAB_LIB_WIDEN);
4845                 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
4846                 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4847                                           remainder, 0, OPTAB_LIB_WIDEN);
4848               }
4849             abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
4850             abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
4851             tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
4852                                 1, NULL_RTX, 1);
4853             do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
4854             tem = expand_binop (compute_mode, xor_optab, op0, op1,
4855                                 NULL_RTX, 0, OPTAB_WIDEN);
4856             mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4857                                  size - 1, NULL_RTX, 0);
4858             tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
4859                                 NULL_RTX, 0, OPTAB_WIDEN);
4860             tem = expand_binop (compute_mode, sub_optab, tem, mask,
4861                                 NULL_RTX, 0, OPTAB_WIDEN);
4862             expand_inc (quotient, tem);
4863             tem = expand_binop (compute_mode, xor_optab, mask, op1,
4864                                 NULL_RTX, 0, OPTAB_WIDEN);
4865             tem = expand_binop (compute_mode, sub_optab, tem, mask,
4866                                 NULL_RTX, 0, OPTAB_WIDEN);
4867             expand_dec (remainder, tem);
4868             emit_label (label);
4869           }
4870         return gen_lowpart (mode, rem_flag ? remainder : quotient);
4871
4872       default:
4873         gcc_unreachable ();
4874       }
4875
4876   if (quotient == 0)
4877     {
4878       if (target && GET_MODE (target) != compute_mode)
4879         target = 0;
4880
4881       if (rem_flag)
4882         {
4883           /* Try to produce the remainder without producing the quotient.
4884              If we seem to have a divmod pattern that does not require widening,
4885              don't try widening here.  We should really have a WIDEN argument
4886              to expand_twoval_binop, since what we'd really like to do here is
4887              1) try a mod insn in compute_mode
4888              2) try a divmod insn in compute_mode
4889              3) try a div insn in compute_mode and multiply-subtract to get
4890                 remainder
4891              4) try the same things with widening allowed.  */
4892           remainder
4893             = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4894                                  op0, op1, target,
4895                                  unsignedp,
4896                                  ((optab_handler (optab2, compute_mode)
4897                                    != CODE_FOR_nothing)
4898                                   ? OPTAB_DIRECT : OPTAB_WIDEN));
4899           if (remainder == 0)
4900             {
4901               /* No luck there.  Can we do remainder and divide at once
4902                  without a library call?  */
4903               remainder = gen_reg_rtx (compute_mode);
4904               if (! expand_twoval_binop ((unsignedp
4905                                           ? udivmod_optab
4906                                           : sdivmod_optab),
4907                                          op0, op1,
4908                                          NULL_RTX, remainder, unsignedp))
4909                 remainder = 0;
4910             }
4911
4912           if (remainder)
4913             return gen_lowpart (mode, remainder);
4914         }
4915
4916       /* Produce the quotient.  Try a quotient insn, but not a library call.
4917          If we have a divmod in this mode, use it in preference to widening
4918          the div (for this test we assume it will not fail). Note that optab2
4919          is set to the one of the two optabs that the call below will use.  */
4920       quotient
4921         = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
4922                              op0, op1, rem_flag ? NULL_RTX : target,
4923                              unsignedp,
4924                              ((optab_handler (optab2, compute_mode)
4925                                != CODE_FOR_nothing)
4926                               ? OPTAB_DIRECT : OPTAB_WIDEN));
4927
4928       if (quotient == 0)
4929         {
4930           /* No luck there.  Try a quotient-and-remainder insn,
4931              keeping the quotient alone.  */
4932           quotient = gen_reg_rtx (compute_mode);
4933           if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
4934                                      op0, op1,
4935                                      quotient, NULL_RTX, unsignedp))
4936             {
4937               quotient = 0;
4938               if (! rem_flag)
4939                 /* Still no luck.  If we are not computing the remainder,
4940                    use a library call for the quotient.  */
4941                 quotient = sign_expand_binop (compute_mode,
4942                                               udiv_optab, sdiv_optab,
4943                                               op0, op1, target,
4944                                               unsignedp, OPTAB_LIB_WIDEN);
4945             }
4946         }
4947     }
4948
4949   if (rem_flag)
4950     {
4951       if (target && GET_MODE (target) != compute_mode)
4952         target = 0;
4953
4954       if (quotient == 0)
4955         {
4956           /* No divide instruction either.  Use library for remainder.  */
4957           remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4958                                          op0, op1, target,
4959                                          unsignedp, OPTAB_LIB_WIDEN);
4960           /* No remainder function.  Try a quotient-and-remainder
4961              function, keeping the remainder.  */
4962           if (!remainder)
4963             {
4964               remainder = gen_reg_rtx (compute_mode);
4965               if (!expand_twoval_binop_libfunc
4966                   (unsignedp ? udivmod_optab : sdivmod_optab,
4967                    op0, op1,
4968                    NULL_RTX, remainder,
4969                    unsignedp ? UMOD : MOD))
4970                 remainder = NULL_RTX;
4971             }
4972         }
4973       else
4974         {
4975           /* We divided.  Now finish doing X - Y * (X / Y).  */
4976           remainder = expand_mult (compute_mode, quotient, op1,
4977                                    NULL_RTX, unsignedp);
4978           remainder = expand_binop (compute_mode, sub_optab, op0,
4979                                     remainder, target, unsignedp,
4980                                     OPTAB_LIB_WIDEN);
4981         }
4982     }
4983
4984   return gen_lowpart (mode, rem_flag ? remainder : quotient);
4985 }
4986 \f
4987 /* Return a tree node with data type TYPE, describing the value of X.
4988    Usually this is an VAR_DECL, if there is no obvious better choice.
4989    X may be an expression, however we only support those expressions
4990    generated by loop.c.  */
4991
4992 tree
4993 make_tree (tree type, rtx x)
4994 {
4995   tree t;
4996
4997   switch (GET_CODE (x))
4998     {
4999     case CONST_INT:
5000     case CONST_WIDE_INT:
5001       t = wide_int_to_tree (type, std::make_pair (x, TYPE_MODE (type)));
5002       return t;
5003
5004     case CONST_DOUBLE:
5005       STATIC_ASSERT (HOST_BITS_PER_WIDE_INT * 2 <= MAX_BITSIZE_MODE_ANY_INT);
5006       if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
5007         t = wide_int_to_tree (type,
5008                               wide_int::from_array (&CONST_DOUBLE_LOW (x), 2,
5009                                                     HOST_BITS_PER_WIDE_INT * 2));
5010       else
5011         {
5012           REAL_VALUE_TYPE d;
5013
5014           REAL_VALUE_FROM_CONST_DOUBLE (d, x);
5015           t = build_real (type, d);
5016         }
5017
5018       return t;
5019
5020     case CONST_VECTOR:
5021       {
5022         int units = CONST_VECTOR_NUNITS (x);
5023         tree itype = TREE_TYPE (type);
5024         tree *elts;
5025         int i;
5026
5027         /* Build a tree with vector elements.  */
5028         elts = XALLOCAVEC (tree, units);
5029         for (i = units - 1; i >= 0; --i)
5030           {
5031             rtx elt = CONST_VECTOR_ELT (x, i);
5032             elts[i] = make_tree (itype, elt);
5033           }
5034
5035         return build_vector (type, elts);
5036       }
5037
5038     case PLUS:
5039       return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5040                           make_tree (type, XEXP (x, 1)));
5041
5042     case MINUS:
5043       return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5044                           make_tree (type, XEXP (x, 1)));
5045
5046     case NEG:
5047       return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0)));
5048
5049     case MULT:
5050       return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
5051                           make_tree (type, XEXP (x, 1)));
5052
5053     case ASHIFT:
5054       return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
5055                           make_tree (type, XEXP (x, 1)));
5056
5057     case LSHIFTRT:
5058       t = unsigned_type_for (type);
5059       return fold_convert (type, build2 (RSHIFT_EXPR, t,
5060                                          make_tree (t, XEXP (x, 0)),
5061                                          make_tree (type, XEXP (x, 1))));
5062
5063     case ASHIFTRT:
5064       t = signed_type_for (type);
5065       return fold_convert (type, build2 (RSHIFT_EXPR, t,
5066                                          make_tree (t, XEXP (x, 0)),
5067                                          make_tree (type, XEXP (x, 1))));
5068
5069     case DIV:
5070       if (TREE_CODE (type) != REAL_TYPE)
5071         t = signed_type_for (type);
5072       else
5073         t = type;
5074
5075       return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5076                                          make_tree (t, XEXP (x, 0)),
5077                                          make_tree (t, XEXP (x, 1))));
5078     case UDIV:
5079       t = unsigned_type_for (type);
5080       return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5081                                          make_tree (t, XEXP (x, 0)),
5082                                          make_tree (t, XEXP (x, 1))));
5083
5084     case SIGN_EXTEND:
5085     case ZERO_EXTEND:
5086       t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)),
5087                                           GET_CODE (x) == ZERO_EXTEND);
5088       return fold_convert (type, make_tree (t, XEXP (x, 0)));
5089
5090     case CONST:
5091       return make_tree (type, XEXP (x, 0));
5092
5093     case SYMBOL_REF:
5094       t = SYMBOL_REF_DECL (x);
5095       if (t)
5096         return fold_convert (type, build_fold_addr_expr (t));
5097       /* else fall through.  */
5098
5099     default:
5100       t = build_decl (RTL_LOCATION (x), VAR_DECL, NULL_TREE, type);
5101
5102       /* If TYPE is a POINTER_TYPE, we might need to convert X from
5103          address mode to pointer mode.  */
5104       if (POINTER_TYPE_P (type))
5105         x = convert_memory_address_addr_space
5106               (TYPE_MODE (type), x, TYPE_ADDR_SPACE (TREE_TYPE (type)));
5107
5108       /* Note that we do *not* use SET_DECL_RTL here, because we do not
5109          want set_decl_rtl to go adjusting REG_ATTRS for this temporary.  */
5110       t->decl_with_rtl.rtl = x;
5111
5112       return t;
5113     }
5114 }
5115 \f
5116 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
5117    and returning TARGET.
5118
5119    If TARGET is 0, a pseudo-register or constant is returned.  */
5120
5121 rtx
5122 expand_and (machine_mode mode, rtx op0, rtx op1, rtx target)
5123 {
5124   rtx tem = 0;
5125
5126   if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
5127     tem = simplify_binary_operation (AND, mode, op0, op1);
5128   if (tem == 0)
5129     tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
5130
5131   if (target == 0)
5132     target = tem;
5133   else if (tem != target)
5134     emit_move_insn (target, tem);
5135   return target;
5136 }
5137
5138 /* Helper function for emit_store_flag.  */
5139 rtx
5140 emit_cstore (rtx target, enum insn_code icode, enum rtx_code code,
5141              machine_mode mode, machine_mode compare_mode,
5142              int unsignedp, rtx x, rtx y, int normalizep,
5143              machine_mode target_mode)
5144 {
5145   struct expand_operand ops[4];
5146   rtx op0, comparison, subtarget;
5147   rtx_insn *last;
5148   machine_mode result_mode = targetm.cstore_mode (icode);
5149
5150   last = get_last_insn ();
5151   x = prepare_operand (icode, x, 2, mode, compare_mode, unsignedp);
5152   y = prepare_operand (icode, y, 3, mode, compare_mode, unsignedp);
5153   if (!x || !y)
5154     {
5155       delete_insns_since (last);
5156       return NULL_RTX;
5157     }
5158
5159   if (target_mode == VOIDmode)
5160     target_mode = result_mode;
5161   if (!target)
5162     target = gen_reg_rtx (target_mode);
5163
5164   comparison = gen_rtx_fmt_ee (code, result_mode, x, y);
5165
5166   create_output_operand (&ops[0], optimize ? NULL_RTX : target, result_mode);
5167   create_fixed_operand (&ops[1], comparison);
5168   create_fixed_operand (&ops[2], x);
5169   create_fixed_operand (&ops[3], y);
5170   if (!maybe_expand_insn (icode, 4, ops))
5171     {
5172       delete_insns_since (last);
5173       return NULL_RTX;
5174     }
5175   subtarget = ops[0].value;
5176
5177   /* If we are converting to a wider mode, first convert to
5178      TARGET_MODE, then normalize.  This produces better combining
5179      opportunities on machines that have a SIGN_EXTRACT when we are
5180      testing a single bit.  This mostly benefits the 68k.
5181
5182      If STORE_FLAG_VALUE does not have the sign bit set when
5183      interpreted in MODE, we can do this conversion as unsigned, which
5184      is usually more efficient.  */
5185   if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (result_mode))
5186     {
5187       convert_move (target, subtarget,
5188                     val_signbit_known_clear_p (result_mode,
5189                                                STORE_FLAG_VALUE));
5190       op0 = target;
5191       result_mode = target_mode;
5192     }
5193   else
5194     op0 = subtarget;
5195
5196   /* If we want to keep subexpressions around, don't reuse our last
5197      target.  */
5198   if (optimize)
5199     subtarget = 0;
5200
5201   /* Now normalize to the proper value in MODE.  Sometimes we don't
5202      have to do anything.  */
5203   if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
5204     ;
5205   /* STORE_FLAG_VALUE might be the most negative number, so write
5206      the comparison this way to avoid a compiler-time warning.  */
5207   else if (- normalizep == STORE_FLAG_VALUE)
5208     op0 = expand_unop (result_mode, neg_optab, op0, subtarget, 0);
5209
5210   /* We don't want to use STORE_FLAG_VALUE < 0 below since this makes
5211      it hard to use a value of just the sign bit due to ANSI integer
5212      constant typing rules.  */
5213   else if (val_signbit_known_set_p (result_mode, STORE_FLAG_VALUE))
5214     op0 = expand_shift (RSHIFT_EXPR, result_mode, op0,
5215                         GET_MODE_BITSIZE (result_mode) - 1, subtarget,
5216                         normalizep == 1);
5217   else
5218     {
5219       gcc_assert (STORE_FLAG_VALUE & 1);
5220
5221       op0 = expand_and (result_mode, op0, const1_rtx, subtarget);
5222       if (normalizep == -1)
5223         op0 = expand_unop (result_mode, neg_optab, op0, op0, 0);
5224     }
5225
5226   /* If we were converting to a smaller mode, do the conversion now.  */
5227   if (target_mode != result_mode)
5228     {
5229       convert_move (target, op0, 0);
5230       return target;
5231     }
5232   else
5233     return op0;
5234 }
5235
5236
5237 /* A subroutine of emit_store_flag only including "tricks" that do not
5238    need a recursive call.  These are kept separate to avoid infinite
5239    loops.  */
5240
5241 static rtx
5242 emit_store_flag_1 (rtx target, enum rtx_code code, rtx op0, rtx op1,
5243                    machine_mode mode, int unsignedp, int normalizep,
5244                    machine_mode target_mode)
5245 {
5246   rtx subtarget;
5247   enum insn_code icode;
5248   machine_mode compare_mode;
5249   enum mode_class mclass;
5250   enum rtx_code scode;
5251
5252   if (unsignedp)
5253     code = unsigned_condition (code);
5254   scode = swap_condition (code);
5255
5256   /* If one operand is constant, make it the second one.  Only do this
5257      if the other operand is not constant as well.  */
5258
5259   if (swap_commutative_operands_p (op0, op1))
5260     {
5261       std::swap (op0, op1);
5262       code = swap_condition (code);
5263     }
5264
5265   if (mode == VOIDmode)
5266     mode = GET_MODE (op0);
5267
5268   /* For some comparisons with 1 and -1, we can convert this to
5269      comparisons with zero.  This will often produce more opportunities for
5270      store-flag insns.  */
5271
5272   switch (code)
5273     {
5274     case LT:
5275       if (op1 == const1_rtx)
5276         op1 = const0_rtx, code = LE;
5277       break;
5278     case LE:
5279       if (op1 == constm1_rtx)
5280         op1 = const0_rtx, code = LT;
5281       break;
5282     case GE:
5283       if (op1 == const1_rtx)
5284         op1 = const0_rtx, code = GT;
5285       break;
5286     case GT:
5287       if (op1 == constm1_rtx)
5288         op1 = const0_rtx, code = GE;
5289       break;
5290     case GEU:
5291       if (op1 == const1_rtx)
5292         op1 = const0_rtx, code = NE;
5293       break;
5294     case LTU:
5295       if (op1 == const1_rtx)
5296         op1 = const0_rtx, code = EQ;
5297       break;
5298     default:
5299       break;
5300     }
5301
5302   /* If we are comparing a double-word integer with zero or -1, we can
5303      convert the comparison into one involving a single word.  */
5304   if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
5305       && GET_MODE_CLASS (mode) == MODE_INT
5306       && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0)))
5307     {
5308       rtx tem;
5309       if ((code == EQ || code == NE)
5310           && (op1 == const0_rtx || op1 == constm1_rtx))
5311         {
5312           rtx op00, op01;
5313
5314           /* Do a logical OR or AND of the two words and compare the
5315              result.  */
5316           op00 = simplify_gen_subreg (word_mode, op0, mode, 0);
5317           op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD);
5318           tem = expand_binop (word_mode,
5319                               op1 == const0_rtx ? ior_optab : and_optab,
5320                               op00, op01, NULL_RTX, unsignedp,
5321                               OPTAB_DIRECT);
5322
5323           if (tem != 0)
5324             tem = emit_store_flag (NULL_RTX, code, tem, op1, word_mode,
5325                                    unsignedp, normalizep);
5326         }
5327       else if ((code == LT || code == GE) && op1 == const0_rtx)
5328         {
5329           rtx op0h;
5330
5331           /* If testing the sign bit, can just test on high word.  */
5332           op0h = simplify_gen_subreg (word_mode, op0, mode,
5333                                       subreg_highpart_offset (word_mode,
5334                                                               mode));
5335           tem = emit_store_flag (NULL_RTX, code, op0h, op1, word_mode,
5336                                  unsignedp, normalizep);
5337         }
5338       else
5339         tem = NULL_RTX;
5340
5341       if (tem)
5342         {
5343           if (target_mode == VOIDmode || GET_MODE (tem) == target_mode)
5344             return tem;
5345           if (!target)
5346             target = gen_reg_rtx (target_mode);
5347
5348           convert_move (target, tem,
5349                         !val_signbit_known_set_p (word_mode,
5350                                                   (normalizep ? normalizep
5351                                                    : STORE_FLAG_VALUE)));
5352           return target;
5353         }
5354     }
5355
5356   /* If this is A < 0 or A >= 0, we can do this by taking the ones
5357      complement of A (for GE) and shifting the sign bit to the low bit.  */
5358   if (op1 == const0_rtx && (code == LT || code == GE)
5359       && GET_MODE_CLASS (mode) == MODE_INT
5360       && (normalizep || STORE_FLAG_VALUE == 1
5361           || val_signbit_p (mode, STORE_FLAG_VALUE)))
5362     {
5363       subtarget = target;
5364
5365       if (!target)
5366         target_mode = mode;
5367
5368       /* If the result is to be wider than OP0, it is best to convert it
5369          first.  If it is to be narrower, it is *incorrect* to convert it
5370          first.  */
5371       else if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
5372         {
5373           op0 = convert_modes (target_mode, mode, op0, 0);
5374           mode = target_mode;
5375         }
5376
5377       if (target_mode != mode)
5378         subtarget = 0;
5379
5380       if (code == GE)
5381         op0 = expand_unop (mode, one_cmpl_optab, op0,
5382                            ((STORE_FLAG_VALUE == 1 || normalizep)
5383                             ? 0 : subtarget), 0);
5384
5385       if (STORE_FLAG_VALUE == 1 || normalizep)
5386         /* If we are supposed to produce a 0/1 value, we want to do
5387            a logical shift from the sign bit to the low-order bit; for
5388            a -1/0 value, we do an arithmetic shift.  */
5389         op0 = expand_shift (RSHIFT_EXPR, mode, op0,
5390                             GET_MODE_BITSIZE (mode) - 1,
5391                             subtarget, normalizep != -1);
5392
5393       if (mode != target_mode)
5394         op0 = convert_modes (target_mode, mode, op0, 0);
5395
5396       return op0;
5397     }
5398
5399   mclass = GET_MODE_CLASS (mode);
5400   for (compare_mode = mode; compare_mode != VOIDmode;
5401        compare_mode = GET_MODE_WIDER_MODE (compare_mode))
5402     {
5403      machine_mode optab_mode = mclass == MODE_CC ? CCmode : compare_mode;
5404      icode = optab_handler (cstore_optab, optab_mode);
5405      if (icode != CODE_FOR_nothing)
5406         {
5407           do_pending_stack_adjust ();
5408           rtx tem = emit_cstore (target, icode, code, mode, compare_mode,
5409                                  unsignedp, op0, op1, normalizep, target_mode);
5410           if (tem)
5411             return tem;
5412
5413           if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5414             {
5415               tem = emit_cstore (target, icode, scode, mode, compare_mode,
5416                                  unsignedp, op1, op0, normalizep, target_mode);
5417               if (tem)
5418                 return tem;
5419             }
5420           break;
5421         }
5422     }
5423
5424   return 0;
5425 }
5426
5427 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
5428    and storing in TARGET.  Normally return TARGET.
5429    Return 0 if that cannot be done.
5430
5431    MODE is the mode to use for OP0 and OP1 should they be CONST_INTs.  If
5432    it is VOIDmode, they cannot both be CONST_INT.
5433
5434    UNSIGNEDP is for the case where we have to widen the operands
5435    to perform the operation.  It says to use zero-extension.
5436
5437    NORMALIZEP is 1 if we should convert the result to be either zero
5438    or one.  Normalize is -1 if we should convert the result to be
5439    either zero or -1.  If NORMALIZEP is zero, the result will be left
5440    "raw" out of the scc insn.  */
5441
5442 rtx
5443 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
5444                  machine_mode mode, int unsignedp, int normalizep)
5445 {
5446   machine_mode target_mode = target ? GET_MODE (target) : VOIDmode;
5447   enum rtx_code rcode;
5448   rtx subtarget;
5449   rtx tem, trueval;
5450   rtx_insn *last;
5451
5452   /* If we compare constants, we shouldn't use a store-flag operation,
5453      but a constant load.  We can get there via the vanilla route that
5454      usually generates a compare-branch sequence, but will in this case
5455      fold the comparison to a constant, and thus elide the branch.  */
5456   if (CONSTANT_P (op0) && CONSTANT_P (op1))
5457     return NULL_RTX;
5458
5459   tem = emit_store_flag_1 (target, code, op0, op1, mode, unsignedp, normalizep,
5460                            target_mode);
5461   if (tem)
5462     return tem;
5463
5464   /* If we reached here, we can't do this with a scc insn, however there
5465      are some comparisons that can be done in other ways.  Don't do any
5466      of these cases if branches are very cheap.  */
5467   if (BRANCH_COST (optimize_insn_for_speed_p (), false) == 0)
5468     return 0;
5469
5470   /* See what we need to return.  We can only return a 1, -1, or the
5471      sign bit.  */
5472
5473   if (normalizep == 0)
5474     {
5475       if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
5476         normalizep = STORE_FLAG_VALUE;
5477
5478       else if (val_signbit_p (mode, STORE_FLAG_VALUE))
5479         ;
5480       else
5481         return 0;
5482     }
5483
5484   last = get_last_insn ();
5485
5486   /* If optimizing, use different pseudo registers for each insn, instead
5487      of reusing the same pseudo.  This leads to better CSE, but slows
5488      down the compiler, since there are more pseudos */
5489   subtarget = (!optimize
5490                && (target_mode == mode)) ? target : NULL_RTX;
5491   trueval = GEN_INT (normalizep ? normalizep : STORE_FLAG_VALUE);
5492
5493   /* For floating-point comparisons, try the reverse comparison or try
5494      changing the "orderedness" of the comparison.  */
5495   if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5496     {
5497       enum rtx_code first_code;
5498       bool and_them;
5499
5500       rcode = reverse_condition_maybe_unordered (code);
5501       if (can_compare_p (rcode, mode, ccp_store_flag)
5502           && (code == ORDERED || code == UNORDERED
5503               || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
5504               || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
5505         {
5506           int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
5507                           || (STORE_FLAG_VALUE == -1 && normalizep == 1));
5508
5509           /* For the reverse comparison, use either an addition or a XOR.  */
5510           if (want_add
5511               && rtx_cost (GEN_INT (normalizep), PLUS, 1,
5512                            optimize_insn_for_speed_p ()) == 0)
5513             {
5514               tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5515                                        STORE_FLAG_VALUE, target_mode);
5516               if (tem)
5517                 return expand_binop (target_mode, add_optab, tem,
5518                                      gen_int_mode (normalizep, target_mode),
5519                                      target, 0, OPTAB_WIDEN);
5520             }
5521           else if (!want_add
5522                    && rtx_cost (trueval, XOR, 1,
5523                                 optimize_insn_for_speed_p ()) == 0)
5524             {
5525               tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5526                                        normalizep, target_mode);
5527               if (tem)
5528                 return expand_binop (target_mode, xor_optab, tem, trueval,
5529                                      target, INTVAL (trueval) >= 0, OPTAB_WIDEN);
5530             }
5531         }
5532
5533       delete_insns_since (last);
5534
5535       /* Cannot split ORDERED and UNORDERED, only try the above trick.   */
5536       if (code == ORDERED || code == UNORDERED)
5537         return 0;
5538
5539       and_them = split_comparison (code, mode, &first_code, &code);
5540
5541       /* If there are no NaNs, the first comparison should always fall through.
5542          Effectively change the comparison to the other one.  */
5543       if (!HONOR_NANS (mode))
5544         {
5545           gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
5546           return emit_store_flag_1 (target, code, op0, op1, mode, 0, normalizep,
5547                                     target_mode);
5548         }
5549
5550       if (!HAVE_conditional_move)
5551         return 0;
5552
5553       /* Try using a setcc instruction for ORDERED/UNORDERED, followed by a
5554          conditional move.  */
5555       tem = emit_store_flag_1 (subtarget, first_code, op0, op1, mode, 0,
5556                                normalizep, target_mode);
5557       if (tem == 0)
5558         return 0;
5559
5560       if (and_them)
5561         tem = emit_conditional_move (target, code, op0, op1, mode,
5562                                      tem, const0_rtx, GET_MODE (tem), 0);
5563       else
5564         tem = emit_conditional_move (target, code, op0, op1, mode,
5565                                      trueval, tem, GET_MODE (tem), 0);
5566
5567       if (tem == 0)
5568         delete_insns_since (last);
5569       return tem;
5570     }
5571
5572   /* The remaining tricks only apply to integer comparisons.  */
5573
5574   if (GET_MODE_CLASS (mode) != MODE_INT)
5575     return 0;
5576
5577   /* If this is an equality comparison of integers, we can try to exclusive-or
5578      (or subtract) the two operands and use a recursive call to try the
5579      comparison with zero.  Don't do any of these cases if branches are
5580      very cheap.  */
5581
5582   if ((code == EQ || code == NE) && op1 != const0_rtx)
5583     {
5584       tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
5585                           OPTAB_WIDEN);
5586
5587       if (tem == 0)
5588         tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
5589                             OPTAB_WIDEN);
5590       if (tem != 0)
5591         tem = emit_store_flag (target, code, tem, const0_rtx,
5592                                mode, unsignedp, normalizep);
5593       if (tem != 0)
5594         return tem;
5595
5596       delete_insns_since (last);
5597     }
5598
5599   /* For integer comparisons, try the reverse comparison.  However, for
5600      small X and if we'd have anyway to extend, implementing "X != 0"
5601      as "-(int)X >> 31" is still cheaper than inverting "(int)X == 0".  */
5602   rcode = reverse_condition (code);
5603   if (can_compare_p (rcode, mode, ccp_store_flag)
5604       && ! (optab_handler (cstore_optab, mode) == CODE_FOR_nothing
5605             && code == NE
5606             && GET_MODE_SIZE (mode) < UNITS_PER_WORD
5607             && op1 == const0_rtx))
5608     {
5609       int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
5610                       || (STORE_FLAG_VALUE == -1 && normalizep == 1));
5611
5612       /* Again, for the reverse comparison, use either an addition or a XOR.  */
5613       if (want_add
5614           && rtx_cost (GEN_INT (normalizep), PLUS, 1,
5615                        optimize_insn_for_speed_p ()) == 0)
5616         {
5617           tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5618                                    STORE_FLAG_VALUE, target_mode);
5619           if (tem != 0)
5620             tem = expand_binop (target_mode, add_optab, tem,
5621                                 gen_int_mode (normalizep, target_mode),
5622                                 target, 0, OPTAB_WIDEN);
5623         }
5624       else if (!want_add
5625                && rtx_cost (trueval, XOR, 1,
5626                             optimize_insn_for_speed_p ()) == 0)
5627         {
5628           tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5629                                    normalizep, target_mode);
5630           if (tem != 0)
5631             tem = expand_binop (target_mode, xor_optab, tem, trueval, target,
5632                                 INTVAL (trueval) >= 0, OPTAB_WIDEN);
5633         }
5634
5635       if (tem != 0)
5636         return tem;
5637       delete_insns_since (last);
5638     }
5639
5640   /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
5641      the constant zero.  Reject all other comparisons at this point.  Only
5642      do LE and GT if branches are expensive since they are expensive on
5643      2-operand machines.  */
5644
5645   if (op1 != const0_rtx
5646       || (code != EQ && code != NE
5647           && (BRANCH_COST (optimize_insn_for_speed_p (),
5648                            false) <= 1 || (code != LE && code != GT))))
5649     return 0;
5650
5651   /* Try to put the result of the comparison in the sign bit.  Assume we can't
5652      do the necessary operation below.  */
5653
5654   tem = 0;
5655
5656   /* To see if A <= 0, compute (A | (A - 1)).  A <= 0 iff that result has
5657      the sign bit set.  */
5658
5659   if (code == LE)
5660     {
5661       /* This is destructive, so SUBTARGET can't be OP0.  */
5662       if (rtx_equal_p (subtarget, op0))
5663         subtarget = 0;
5664
5665       tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
5666                           OPTAB_WIDEN);
5667       if (tem)
5668         tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
5669                             OPTAB_WIDEN);
5670     }
5671
5672   /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
5673      number of bits in the mode of OP0, minus one.  */
5674
5675   if (code == GT)
5676     {
5677       if (rtx_equal_p (subtarget, op0))
5678         subtarget = 0;
5679
5680       tem = expand_shift (RSHIFT_EXPR, mode, op0,
5681                           GET_MODE_BITSIZE (mode) - 1,
5682                           subtarget, 0);
5683       tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
5684                           OPTAB_WIDEN);
5685     }
5686
5687   if (code == EQ || code == NE)
5688     {
5689       /* For EQ or NE, one way to do the comparison is to apply an operation
5690          that converts the operand into a positive number if it is nonzero
5691          or zero if it was originally zero.  Then, for EQ, we subtract 1 and
5692          for NE we negate.  This puts the result in the sign bit.  Then we
5693          normalize with a shift, if needed.
5694
5695          Two operations that can do the above actions are ABS and FFS, so try
5696          them.  If that doesn't work, and MODE is smaller than a full word,
5697          we can use zero-extension to the wider mode (an unsigned conversion)
5698          as the operation.  */
5699
5700       /* Note that ABS doesn't yield a positive number for INT_MIN, but
5701          that is compensated by the subsequent overflow when subtracting
5702          one / negating.  */
5703
5704       if (optab_handler (abs_optab, mode) != CODE_FOR_nothing)
5705         tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
5706       else if (optab_handler (ffs_optab, mode) != CODE_FOR_nothing)
5707         tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
5708       else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5709         {
5710           tem = convert_modes (word_mode, mode, op0, 1);
5711           mode = word_mode;
5712         }
5713
5714       if (tem != 0)
5715         {
5716           if (code == EQ)
5717             tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
5718                                 0, OPTAB_WIDEN);
5719           else
5720             tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
5721         }
5722
5723       /* If we couldn't do it that way, for NE we can "or" the two's complement
5724          of the value with itself.  For EQ, we take the one's complement of
5725          that "or", which is an extra insn, so we only handle EQ if branches
5726          are expensive.  */
5727
5728       if (tem == 0
5729           && (code == NE
5730               || BRANCH_COST (optimize_insn_for_speed_p (),
5731                               false) > 1))
5732         {
5733           if (rtx_equal_p (subtarget, op0))
5734             subtarget = 0;
5735
5736           tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
5737           tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
5738                               OPTAB_WIDEN);
5739
5740           if (tem && code == EQ)
5741             tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
5742         }
5743     }
5744
5745   if (tem && normalizep)
5746     tem = expand_shift (RSHIFT_EXPR, mode, tem,
5747                         GET_MODE_BITSIZE (mode) - 1,
5748                         subtarget, normalizep == 1);
5749
5750   if (tem)
5751     {
5752       if (!target)
5753         ;
5754       else if (GET_MODE (tem) != target_mode)
5755         {
5756           convert_move (target, tem, 0);
5757           tem = target;
5758         }
5759       else if (!subtarget)
5760         {
5761           emit_move_insn (target, tem);
5762           tem = target;
5763         }
5764     }
5765   else
5766     delete_insns_since (last);
5767
5768   return tem;
5769 }
5770
5771 /* Like emit_store_flag, but always succeeds.  */
5772
5773 rtx
5774 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
5775                        machine_mode mode, int unsignedp, int normalizep)
5776 {
5777   rtx tem;
5778   rtx_code_label *label;
5779   rtx trueval, falseval;
5780
5781   /* First see if emit_store_flag can do the job.  */
5782   tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
5783   if (tem != 0)
5784     return tem;
5785
5786   if (!target)
5787     target = gen_reg_rtx (word_mode);
5788
5789   /* If this failed, we have to do this with set/compare/jump/set code.
5790      For foo != 0, if foo is in OP0, just replace it with 1 if nonzero.  */
5791   trueval = normalizep ? GEN_INT (normalizep) : const1_rtx;
5792   if (code == NE
5793       && GET_MODE_CLASS (mode) == MODE_INT
5794       && REG_P (target)
5795       && op0 == target
5796       && op1 == const0_rtx)
5797     {
5798       label = gen_label_rtx ();
5799       do_compare_rtx_and_jump (target, const0_rtx, EQ, unsignedp, mode,
5800                                NULL_RTX, NULL, label, -1);
5801       emit_move_insn (target, trueval);
5802       emit_label (label);
5803       return target;
5804     }
5805
5806   if (!REG_P (target)
5807       || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
5808     target = gen_reg_rtx (GET_MODE (target));
5809
5810   /* Jump in the right direction if the target cannot implement CODE
5811      but can jump on its reverse condition.  */
5812   falseval = const0_rtx;
5813   if (! can_compare_p (code, mode, ccp_jump)
5814       && (! FLOAT_MODE_P (mode)
5815           || code == ORDERED || code == UNORDERED
5816           || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
5817           || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
5818     {
5819       enum rtx_code rcode;
5820       if (FLOAT_MODE_P (mode))
5821         rcode = reverse_condition_maybe_unordered (code);
5822       else
5823         rcode = reverse_condition (code);
5824
5825       /* Canonicalize to UNORDERED for the libcall.  */
5826       if (can_compare_p (rcode, mode, ccp_jump)
5827           || (code == ORDERED && ! can_compare_p (ORDERED, mode, ccp_jump)))
5828         {
5829           falseval = trueval;
5830           trueval = const0_rtx;
5831           code = rcode;
5832         }
5833     }
5834
5835   emit_move_insn (target, trueval);
5836   label = gen_label_rtx ();
5837   do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX, NULL,
5838                            label, -1);
5839
5840   emit_move_insn (target, falseval);
5841   emit_label (label);
5842
5843   return target;
5844 }
5845 \f
5846 /* Perform possibly multi-word comparison and conditional jump to LABEL
5847    if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE.  This is
5848    now a thin wrapper around do_compare_rtx_and_jump.  */
5849
5850 static void
5851 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, machine_mode mode,
5852                  rtx_code_label *label)
5853 {
5854   int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU);
5855   do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode, NULL_RTX,
5856                            NULL, label, -1);
5857 }