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