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