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 Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  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
  40 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
  41                                    unsigned HOST_WIDE_INT,
  42                                    unsigned HOST_WIDE_INT, rtx);
  43 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
  44                                    unsigned HOST_WIDE_INT, rtx);
  45 static rtx extract_fixed_bit_field (enum machine_mode, rtx,
  46                                     unsigned HOST_WIDE_INT,
  47                                     unsigned HOST_WIDE_INT,
  48                                     unsigned HOST_WIDE_INT, rtx, int);
  49 static rtx mask_rtx (enum machine_mode, int, int, int);
  50 static rtx lshift_value (enum machine_mode, rtx, int, int);
  51 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
  52                                     unsigned HOST_WIDE_INT, int);
  53 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx);
  54 static rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
  55
  56 /* Nonzero means divides or modulus operations are relatively cheap for
  57    powers of two, so don't use branches; emit the operation instead.
  58    Usually, this will mean that the MD file will emit non-branch
  59    sequences.  */
  60
  61 static int sdiv_pow2_cheap[NUM_MACHINE_MODES];
  62 static int smod_pow2_cheap[NUM_MACHINE_MODES];
  63
  64 #ifndef SLOW_UNALIGNED_ACCESS
  65 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
  66 #endif
  67
  68 /* For compilers that support multiple targets with different word sizes,
  69    MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD.  An example
  70    is the H8/300(H) compiler.  */
  71
  72 #ifndef MAX_BITS_PER_WORD
  73 #define MAX_BITS_PER_WORD BITS_PER_WORD
  74 #endif
  75
  76 /* Reduce conditional compilation elsewhere.  */
  77 #ifndef HAVE_insv
  78 #define HAVE_insv       0
  79 #define CODE_FOR_insv   CODE_FOR_nothing
  80 #define gen_insv(a,b,c,d) NULL_RTX
  81 #endif
  82 #ifndef HAVE_extv
  83 #define HAVE_extv       0
  84 #define CODE_FOR_extv   CODE_FOR_nothing
  85 #define gen_extv(a,b,c,d) NULL_RTX
  86 #endif
  87 #ifndef HAVE_extzv
  88 #define HAVE_extzv      0
  89 #define CODE_FOR_extzv  CODE_FOR_nothing
  90 #define gen_extzv(a,b,c,d) NULL_RTX
  91 #endif
  92
  93 /* Cost of various pieces of RTL.  Note that some of these are indexed by
  94    shift count and some by mode.  */
  95 static int zero_cost;
  96 static int add_cost[NUM_MACHINE_MODES];
  97 static int neg_cost[NUM_MACHINE_MODES];
  98 static int shift_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
  99 static int shiftadd_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 100 static int shiftsub_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
 101 static int mul_cost[NUM_MACHINE_MODES];
 102 static int div_cost[NUM_MACHINE_MODES];
 103 static int mul_widen_cost[NUM_MACHINE_MODES];
 104 static int mul_highpart_cost[NUM_MACHINE_MODES];
 105
 106 void
 107 init_expmed (void)
 108 {
 109   struct
 110   {
 111     struct rtx_def reg;
 112     struct rtx_def plus;        rtunion plus_fld1;
 113     struct rtx_def neg;
 114     struct rtx_def udiv;        rtunion udiv_fld1;
 115     struct rtx_def mult;        rtunion mult_fld1;
 116     struct rtx_def div;         rtunion div_fld1;
 117     struct rtx_def mod;         rtunion mod_fld1;
 118     struct rtx_def zext;
 119     struct rtx_def wide_mult;   rtunion wide_mult_fld1;
 120     struct rtx_def wide_lshr;   rtunion wide_lshr_fld1;
 121     struct rtx_def wide_trunc;
 122     struct rtx_def shift;       rtunion shift_fld1;
 123     struct rtx_def shift_mult;  rtunion shift_mult_fld1;
 124     struct rtx_def shift_add;   rtunion shift_add_fld1;
 125     struct rtx_def shift_sub;   rtunion shift_sub_fld1;
 126   } all;
 127
 128   rtx pow2[MAX_BITS_PER_WORD];
 129   rtx cint[MAX_BITS_PER_WORD];
 130   int m, n;
 131   enum machine_mode mode, wider_mode;
 132
 133   zero_cost = rtx_cost (const0_rtx, 0);
 134
 135   for (m = 1; m < MAX_BITS_PER_WORD; m++)
 136     {
 137       pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
 138       cint[m] = GEN_INT (m);
 139     }
 140
 141   memset (&all, 0, sizeof all);
 142
 143   PUT_CODE (&all.reg, REG);
 144   REGNO (&all.reg) = 10000;
 145
 146   PUT_CODE (&all.plus, PLUS);
 147   XEXP (&all.plus, 0) = &all.reg;
 148   XEXP (&all.plus, 1) = &all.reg;
 149
 150   PUT_CODE (&all.neg, NEG);
 151   XEXP (&all.neg, 0) = &all.reg;
 152
 153   PUT_CODE (&all.udiv, UDIV);
 154   XEXP (&all.udiv, 0) = &all.reg;
 155   XEXP (&all.udiv, 1) = &all.reg;
 156
 157   PUT_CODE (&all.mult, MULT);
 158   XEXP (&all.mult, 0) = &all.reg;
 159   XEXP (&all.mult, 1) = &all.reg;
 160
 161   PUT_CODE (&all.div, DIV);
 162   XEXP (&all.div, 0) = &all.reg;
 163   XEXP (&all.div, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32);
 164
 165   PUT_CODE (&all.mod, MOD);
 166   XEXP (&all.mod, 0) = &all.reg;
 167   XEXP (&all.mod, 1) = XEXP (&all.div, 1);
 168
 169   PUT_CODE (&all.zext, ZERO_EXTEND);
 170   XEXP (&all.zext, 0) = &all.reg;
 171
 172   PUT_CODE (&all.wide_mult, MULT);
 173   XEXP (&all.wide_mult, 0) = &all.zext;
 174   XEXP (&all.wide_mult, 1) = &all.zext;
 175
 176   PUT_CODE (&all.wide_lshr, LSHIFTRT);
 177   XEXP (&all.wide_lshr, 0) = &all.wide_mult;
 178
 179   PUT_CODE (&all.wide_trunc, TRUNCATE);
 180   XEXP (&all.wide_trunc, 0) = &all.wide_lshr;
 181
 182   PUT_CODE (&all.shift, ASHIFT);
 183   XEXP (&all.shift, 0) = &all.reg;
 184
 185   PUT_CODE (&all.shift_mult, MULT);
 186   XEXP (&all.shift_mult, 0) = &all.reg;
 187
 188   PUT_CODE (&all.shift_add, PLUS);
 189   XEXP (&all.shift_add, 0) = &all.shift_mult;
 190   XEXP (&all.shift_add, 1) = &all.reg;
 191
 192   PUT_CODE (&all.shift_sub, MINUS);
 193   XEXP (&all.shift_sub, 0) = &all.shift_mult;
 194   XEXP (&all.shift_sub, 1) = &all.reg;
 195
 196   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
 197        mode != VOIDmode;
 198        mode = GET_MODE_WIDER_MODE (mode))
 199     {
 200       PUT_MODE (&all.reg, mode);
 201       PUT_MODE (&all.plus, mode);
 202       PUT_MODE (&all.neg, mode);
 203       PUT_MODE (&all.udiv, mode);
 204       PUT_MODE (&all.mult, mode);
 205       PUT_MODE (&all.div, mode);
 206       PUT_MODE (&all.mod, mode);
 207       PUT_MODE (&all.wide_trunc, mode);
 208       PUT_MODE (&all.shift, mode);
 209       PUT_MODE (&all.shift_mult, mode);
 210       PUT_MODE (&all.shift_add, mode);
 211       PUT_MODE (&all.shift_sub, mode);
 212
 213       add_cost[mode] = rtx_cost (&all.plus, SET);
 214       neg_cost[mode] = rtx_cost (&all.neg, SET);
 215       div_cost[mode] = rtx_cost (&all.udiv, SET);
 216       mul_cost[mode] = rtx_cost (&all.mult, SET);
 217
 218       sdiv_pow2_cheap[mode] = (rtx_cost (&all.div, SET) <= 2 * add_cost[mode]);
 219       smod_pow2_cheap[mode] = (rtx_cost (&all.mod, SET) <= 2 * add_cost[mode]);
 220
 221       wider_mode = GET_MODE_WIDER_MODE (mode);
 222       if (wider_mode != VOIDmode)
 223         {
 224           PUT_MODE (&all.zext, wider_mode);
 225           PUT_MODE (&all.wide_mult, wider_mode);
 226           PUT_MODE (&all.wide_lshr, wider_mode);
 227           XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode));
 228
 229           mul_widen_cost[wider_mode] = rtx_cost (&all.wide_mult, SET);
 230           mul_highpart_cost[mode] = rtx_cost (&all.wide_trunc, SET);
 231         }
 232
 233       shift_cost[mode][0] = 0;
 234       shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode];
 235
 236       n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode));
 237       for (m = 1; m < n; m++)
 238         {
 239           XEXP (&all.shift, 1) = cint[m];
 240           XEXP (&all.shift_mult, 1) = pow2[m];
 241
 242           shift_cost[mode][m] = rtx_cost (&all.shift, SET);
 243           shiftadd_cost[mode][m] = rtx_cost (&all.shift_add, SET);
 244           shiftsub_cost[mode][m] = rtx_cost (&all.shift_sub, SET);
 245         }
 246     }
 247 }
 248
 249 /* Return an rtx representing minus the value of X.
 250    MODE is the intended mode of the result,
 251    useful if X is a CONST_INT.  */
 252
 253 rtx
 254 negate_rtx (enum machine_mode mode, rtx x)
 255 {
 256   rtx result = simplify_unary_operation (NEG, mode, x, mode);
 257
 258   if (result == 0)
 259     result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
 260
 261   return result;
 262 }
 263
 264 /* Report on the availability of insv/extv/extzv and the desired mode
 265    of each of their operands.  Returns MAX_MACHINE_MODE if HAVE_foo
 266    is false; else the mode of the specified operand.  If OPNO is -1,
 267    all the caller cares about is whether the insn is available.  */
 268 enum machine_mode
 269 mode_for_extraction (enum extraction_pattern pattern, int opno)
 270 {
 271   const struct insn_data *data;
 272
 273   switch (pattern)
 274     {
 275     case EP_insv:
 276       if (HAVE_insv)
 277         {
 278           data = &insn_data[CODE_FOR_insv];
 279           break;
 280         }
 281       return MAX_MACHINE_MODE;
 282
 283     case EP_extv:
 284       if (HAVE_extv)
 285         {
 286           data = &insn_data[CODE_FOR_extv];
 287           break;
 288         }
 289       return MAX_MACHINE_MODE;
 290
 291     case EP_extzv:
 292       if (HAVE_extzv)
 293         {
 294           data = &insn_data[CODE_FOR_extzv];
 295           break;
 296         }
 297       return MAX_MACHINE_MODE;
 298
 299     default:
 300       abort ();
 301     }
 302
 303   if (opno == -1)
 304     return VOIDmode;
 305
 306   /* Everyone who uses this function used to follow it with
 307      if (result == VOIDmode) result = word_mode; */
 308   if (data->operand[opno].mode == VOIDmode)
 309     return word_mode;
 310   return data->operand[opno].mode;
 311 }
 312
 313 \f
 314 /* Generate code to store value from rtx VALUE
 315    into a bit-field within structure STR_RTX
 316    containing BITSIZE bits starting at bit BITNUM.
 317    FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
 318    ALIGN is the alignment that STR_RTX is known to have.
 319    TOTAL_SIZE is the size of the structure in bytes, or -1 if varying.  */
 320
 321 /* ??? Note that there are two different ideas here for how
 322    to determine the size to count bits within, for a register.
 323    One is BITS_PER_WORD, and the other is the size of operand 3
 324    of the insv pattern.
 325
 326    If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
 327    else, we use the mode of operand 3.  */
 328
 329 rtx
 330 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
 331                  unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode,
 332                  rtx value)
 333 {
 334   unsigned int unit
 335     = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
 336   unsigned HOST_WIDE_INT offset = bitnum / unit;
 337   unsigned HOST_WIDE_INT bitpos = bitnum % unit;
 338   rtx op0 = str_rtx;
 339   int byte_offset;
 340
 341   enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
 342
 343   while (GET_CODE (op0) == SUBREG)
 344     {
 345       /* The following line once was done only if WORDS_BIG_ENDIAN,
 346          but I think that is a mistake.  WORDS_BIG_ENDIAN is
 347          meaningful at a much higher level; when structures are copied
 348          between memory and regs, the higher-numbered regs
 349          always get higher addresses.  */
 350       offset += (SUBREG_BYTE (op0) / UNITS_PER_WORD);
 351       /* We used to adjust BITPOS here, but now we do the whole adjustment
 352          right after the loop.  */
 353       op0 = SUBREG_REG (op0);
 354     }
 355
 356   /* Use vec_set patterns for inserting parts of vectors whenever
 357      available.  */
 358   if (VECTOR_MODE_P (GET_MODE (op0))
 359       && !MEM_P (op0)
 360       && (vec_set_optab->handlers[GET_MODE (op0)].insn_code
 361           != CODE_FOR_nothing)
 362       && fieldmode == GET_MODE_INNER (GET_MODE (op0))
 363       && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
 364       && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
 365     {
 366       enum machine_mode outermode = GET_MODE (op0);
 367       enum machine_mode innermode = GET_MODE_INNER (outermode);
 368       int icode = (int) vec_set_optab->handlers[outermode].insn_code;
 369       int pos = bitnum / GET_MODE_BITSIZE (innermode);
 370       rtx rtxpos = GEN_INT (pos);
 371       rtx src = value;
 372       rtx dest = op0;
 373       rtx pat, seq;
 374       enum machine_mode mode0 = insn_data[icode].operand[0].mode;
 375       enum machine_mode mode1 = insn_data[icode].operand[1].mode;
 376       enum machine_mode mode2 = insn_data[icode].operand[2].mode;
 377
 378       start_sequence ();
 379
 380       if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
 381         src = copy_to_mode_reg (mode1, src);
 382
 383       if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
 384         rtxpos = copy_to_mode_reg (mode1, rtxpos);
 385
 386       /* We could handle this, but we should always be called with a pseudo
 387          for our targets and all insns should take them as outputs.  */
 388       if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)
 389           || ! (*insn_data[icode].operand[1].predicate) (src, mode1)
 390           || ! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
 391         abort ();
 392       pat = GEN_FCN (icode) (dest, src, rtxpos);
 393       seq = get_insns ();
 394       end_sequence ();
 395       if (pat)
 396         {
 397           emit_insn (seq);
 398           emit_insn (pat);
 399           return dest;
 400         }
 401     }
 402
 403   if (flag_force_mem)
 404     {
 405       int old_generating_concat_p = generating_concat_p;
 406       generating_concat_p = 0;
 407       value = force_not_mem (value);
 408       generating_concat_p = old_generating_concat_p;
 409     }
 410
 411   /* If the target is a register, overwriting the entire object, or storing
 412      a full-word or multi-word field can be done with just a SUBREG.
 413
 414      If the target is memory, storing any naturally aligned field can be
 415      done with a simple store.  For targets that support fast unaligned
 416      memory, any naturally sized, unit aligned field can be done directly.  */
 417
 418   byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
 419                 + (offset * UNITS_PER_WORD);
 420
 421   if (bitpos == 0
 422       && bitsize == GET_MODE_BITSIZE (fieldmode)
 423       && (!MEM_P (op0)
 424           ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
 425              || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
 426              && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
 427           : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
 428              || (offset * BITS_PER_UNIT % bitsize == 0
 429                  && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
 430     {
 431       if (GET_MODE (op0) != fieldmode)
 432         {
 433           if (GET_CODE (op0) == SUBREG)
 434             {
 435               if (GET_MODE (SUBREG_REG (op0)) == fieldmode
 436                   || GET_MODE_CLASS (fieldmode) == MODE_INT
 437                   || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
 438                 op0 = SUBREG_REG (op0);
 439               else
 440                 /* Else we've got some float mode source being extracted into
 441                    a different float mode destination -- this combination of
 442                    subregs results in Severe Tire Damage.  */
 443                 abort ();
 444             }
 445           if (REG_P (op0))
 446             op0 = gen_rtx_SUBREG (fieldmode, op0, byte_offset);
 447           else
 448             op0 = adjust_address (op0, fieldmode, offset);
 449         }
 450       emit_move_insn (op0, value);
 451       return value;
 452     }
 453
 454   /* Make sure we are playing with integral modes.  Pun with subregs
 455      if we aren't.  This must come after the entire register case above,
 456      since that case is valid for any mode.  The following cases are only
 457      valid for integral modes.  */
 458   {
 459     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
 460     if (imode != GET_MODE (op0))
 461       {
 462         if (MEM_P (op0))
 463           op0 = adjust_address (op0, imode, 0);
 464         else if (imode != BLKmode)
 465           op0 = gen_lowpart (imode, op0);
 466         else
 467           abort ();
 468       }
 469   }
 470
 471   /* We may be accessing data outside the field, which means
 472      we can alias adjacent data.  */
 473   if (MEM_P (op0))
 474     {
 475       op0 = shallow_copy_rtx (op0);
 476       set_mem_alias_set (op0, 0);
 477       set_mem_expr (op0, 0);
 478     }
 479
 480   /* If OP0 is a register, BITPOS must count within a word.
 481      But as we have it, it counts within whatever size OP0 now has.
 482      On a bigendian machine, these are not the same, so convert.  */
 483   if (BYTES_BIG_ENDIAN
 484       && !MEM_P (op0)
 485       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
 486     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
 487
 488   /* Storing an lsb-aligned field in a register
 489      can be done with a movestrict instruction.  */
 490
 491   if (!MEM_P (op0)
 492       && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
 493       && bitsize == GET_MODE_BITSIZE (fieldmode)
 494       && (movstrict_optab->handlers[fieldmode].insn_code
 495           != CODE_FOR_nothing))
 496     {
 497       int icode = movstrict_optab->handlers[fieldmode].insn_code;
 498
 499       /* Get appropriate low part of the value being stored.  */
 500       if (GET_CODE (value) == CONST_INT || REG_P (value))
 501         value = gen_lowpart (fieldmode, value);
 502       else if (!(GET_CODE (value) == SYMBOL_REF
 503                  || GET_CODE (value) == LABEL_REF
 504                  || GET_CODE (value) == CONST))
 505         value = convert_to_mode (fieldmode, value, 0);
 506
 507       if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
 508         value = copy_to_mode_reg (fieldmode, value);
 509
 510       if (GET_CODE (op0) == SUBREG)
 511         {
 512           if (GET_MODE (SUBREG_REG (op0)) == fieldmode
 513               || GET_MODE_CLASS (fieldmode) == MODE_INT
 514               || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
 515             op0 = SUBREG_REG (op0);
 516           else
 517             /* Else we've got some float mode source being extracted into
 518                a different float mode destination -- this combination of
 519                subregs results in Severe Tire Damage.  */
 520             abort ();
 521         }
 522
 523       emit_insn (GEN_FCN (icode)
 524                  (gen_rtx_SUBREG (fieldmode, op0,
 525                                   (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
 526                                   + (offset * UNITS_PER_WORD)),
 527                                   value));
 528
 529       return value;
 530     }
 531
 532   /* Handle fields bigger than a word.  */
 533
 534   if (bitsize > BITS_PER_WORD)
 535     {
 536       /* Here we transfer the words of the field
 537          in the order least significant first.
 538          This is because the most significant word is the one which may
 539          be less than full.
 540          However, only do that if the value is not BLKmode.  */
 541
 542       unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
 543       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
 544       unsigned int i;
 545
 546       /* This is the mode we must force value to, so that there will be enough
 547          subwords to extract.  Note that fieldmode will often (always?) be
 548          VOIDmode, because that is what store_field uses to indicate that this
 549          is a bit field, but passing VOIDmode to operand_subword_force will
 550          result in an abort.  */
 551       fieldmode = GET_MODE (value);
 552       if (fieldmode == VOIDmode)
 553         fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
 554
 555       for (i = 0; i < nwords; i++)
 556         {
 557           /* If I is 0, use the low-order word in both field and target;
 558              if I is 1, use the next to lowest word; and so on.  */
 559           unsigned int wordnum = (backwards ? nwords - i - 1 : i);
 560           unsigned int bit_offset = (backwards
 561                                      ? MAX ((int) bitsize - ((int) i + 1)
 562                                             * BITS_PER_WORD,
 563                                             0)
 564                                      : (int) i * BITS_PER_WORD);
 565
 566           store_bit_field (op0, MIN (BITS_PER_WORD,
 567                                      bitsize - i * BITS_PER_WORD),
 568                            bitnum + bit_offset, word_mode,
 569                            operand_subword_force (value, wordnum, fieldmode));
 570         }
 571       return value;
 572     }
 573
 574   /* From here on we can assume that the field to be stored in is
 575      a full-word (whatever type that is), since it is shorter than a word.  */
 576
 577   /* OFFSET is the number of words or bytes (UNIT says which)
 578      from STR_RTX to the first word or byte containing part of the field.  */
 579
 580   if (!MEM_P (op0))
 581     {
 582       if (offset != 0
 583           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
 584         {
 585           if (!REG_P (op0))
 586             {
 587               /* Since this is a destination (lvalue), we can't copy it to a
 588                  pseudo.  We can trivially remove a SUBREG that does not
 589                  change the size of the operand.  Such a SUBREG may have been
 590                  added above.  Otherwise, abort.  */
 591               if (GET_CODE (op0) == SUBREG
 592                   && (GET_MODE_SIZE (GET_MODE (op0))
 593                       == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
 594                 op0 = SUBREG_REG (op0);
 595               else
 596                 abort ();
 597             }
 598           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
 599                                 op0, (offset * UNITS_PER_WORD));
 600         }
 601       offset = 0;
 602     }
 603
 604   /* If VALUE is a floating-point mode, access it as an integer of the
 605      corresponding size.  This can occur on a machine with 64 bit registers
 606      that uses SFmode for float.  This can also occur for unaligned float
 607      structure fields.  */
 608   if (GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
 609       && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
 610     value = gen_lowpart ((GET_MODE (value) == VOIDmode
 611                           ? word_mode : int_mode_for_mode (GET_MODE (value))),
 612                          value);
 613
 614   /* Now OFFSET is nonzero only if OP0 is memory
 615      and is therefore always measured in bytes.  */
 616
 617   if (HAVE_insv
 618       && GET_MODE (value) != BLKmode
 619       && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
 620       /* Ensure insv's size is wide enough for this field.  */
 621       && (GET_MODE_BITSIZE (op_mode) >= bitsize)
 622       && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
 623             && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))))
 624     {
 625       int xbitpos = bitpos;
 626       rtx value1;
 627       rtx xop0 = op0;
 628       rtx last = get_last_insn ();
 629       rtx pat;
 630       enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
 631       int save_volatile_ok = volatile_ok;
 632
 633       volatile_ok = 1;
 634
 635       /* If this machine's insv can only insert into a register, copy OP0
 636          into a register and save it back later.  */
 637       /* This used to check flag_force_mem, but that was a serious
 638          de-optimization now that flag_force_mem is enabled by -O2.  */
 639       if (MEM_P (op0)
 640           && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
 641                 (op0, VOIDmode)))
 642         {
 643           rtx tempreg;
 644           enum machine_mode bestmode;
 645
 646           /* Get the mode to use for inserting into this field.  If OP0 is
 647              BLKmode, get the smallest mode consistent with the alignment. If
 648              OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
 649              mode. Otherwise, use the smallest mode containing the field.  */
 650
 651           if (GET_MODE (op0) == BLKmode
 652               || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
 653             bestmode
 654               = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
 655                                MEM_VOLATILE_P (op0));
 656           else
 657             bestmode = GET_MODE (op0);
 658
 659           if (bestmode == VOIDmode
 660               || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
 661                   && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
 662             goto insv_loses;
 663
 664           /* Adjust address to point to the containing unit of that mode.
 665              Compute offset as multiple of this unit, counting in bytes.  */
 666           unit = GET_MODE_BITSIZE (bestmode);
 667           offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
 668           bitpos = bitnum % unit;
 669           op0 = adjust_address (op0, bestmode,  offset);
 670
 671           /* Fetch that unit, store the bitfield in it, then store
 672              the unit.  */
 673           tempreg = copy_to_reg (op0);
 674           store_bit_field (tempreg, bitsize, bitpos, fieldmode, value);
 675           emit_move_insn (op0, tempreg);
 676           return value;
 677         }
 678       volatile_ok = save_volatile_ok;
 679
 680       /* Add OFFSET into OP0's address.  */
 681       if (MEM_P (xop0))
 682         xop0 = adjust_address (xop0, byte_mode, offset);
 683
 684       /* If xop0 is a register, we need it in MAXMODE
 685          to make it acceptable to the format of insv.  */
 686       if (GET_CODE (xop0) == SUBREG)
 687         /* We can't just change the mode, because this might clobber op0,
 688            and we will need the original value of op0 if insv fails.  */
 689         xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
 690       if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
 691         xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
 692
 693       /* On big-endian machines, we count bits from the most significant.
 694          If the bit field insn does not, we must invert.  */
 695
 696       if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
 697         xbitpos = unit - bitsize - xbitpos;
 698
 699       /* We have been counting XBITPOS within UNIT.
 700          Count instead within the size of the register.  */
 701       if (BITS_BIG_ENDIAN && !MEM_P (xop0))
 702         xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
 703
 704       unit = GET_MODE_BITSIZE (maxmode);
 705
 706       /* Convert VALUE to maxmode (which insv insn wants) in VALUE1.  */
 707       value1 = value;
 708       if (GET_MODE (value) != maxmode)
 709         {
 710           if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
 711             {
 712               /* Optimization: Don't bother really extending VALUE
 713                  if it has all the bits we will actually use.  However,
 714                  if we must narrow it, be sure we do it correctly.  */
 715
 716               if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
 717                 {
 718                   rtx tmp;
 719
 720                   tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0);
 721                   if (! tmp)
 722                     tmp = simplify_gen_subreg (maxmode,
 723                                                force_reg (GET_MODE (value),
 724                                                           value1),
 725                                                GET_MODE (value), 0);
 726                   value1 = tmp;
 727                 }
 728               else
 729                 value1 = gen_lowpart (maxmode, value1);
 730             }
 731           else if (GET_CODE (value) == CONST_INT)
 732             value1 = gen_int_mode (INTVAL (value), maxmode);
 733           else if (!CONSTANT_P (value))
 734             /* Parse phase is supposed to make VALUE's data type
 735                match that of the component reference, which is a type
 736                at least as wide as the field; so VALUE should have
 737                a mode that corresponds to that type.  */
 738             abort ();
 739         }
 740
 741       /* If this machine's insv insists on a register,
 742          get VALUE1 into a register.  */
 743       if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
 744              (value1, maxmode)))
 745         value1 = force_reg (maxmode, value1);
 746
 747       pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
 748       if (pat)
 749         emit_insn (pat);
 750       else
 751         {
 752           delete_insns_since (last);
 753           store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
 754         }
 755     }
 756   else
 757     insv_loses:
 758     /* Insv is not available; store using shifts and boolean ops.  */
 759     store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
 760   return value;
 761 }
 762 \f
 763 /* Use shifts and boolean operations to store VALUE
 764    into a bit field of width BITSIZE
 765    in a memory location specified by OP0 except offset by OFFSET bytes.
 766      (OFFSET must be 0 if OP0 is a register.)
 767    The field starts at position BITPOS within the byte.
 768     (If OP0 is a register, it may be a full word or a narrower mode,
 769      but BITPOS still counts within a full word,
 770      which is significant on bigendian machines.)  */
 771
 772 static void
 773 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset,
 774                        unsigned HOST_WIDE_INT bitsize,
 775                        unsigned HOST_WIDE_INT bitpos, rtx value)
 776 {
 777   enum machine_mode mode;
 778   unsigned int total_bits = BITS_PER_WORD;
 779   rtx subtarget, temp;
 780   int all_zero = 0;
 781   int all_one = 0;
 782
 783   /* There is a case not handled here:
 784      a structure with a known alignment of just a halfword
 785      and a field split across two aligned halfwords within the structure.
 786      Or likewise a structure with a known alignment of just a byte
 787      and a field split across two bytes.
 788      Such cases are not supposed to be able to occur.  */
 789
 790   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
 791     {
 792       if (offset != 0)
 793         abort ();
 794       /* Special treatment for a bit field split across two registers.  */
 795       if (bitsize + bitpos > BITS_PER_WORD)
 796         {
 797           store_split_bit_field (op0, bitsize, bitpos, value);
 798           return;
 799         }
 800     }
 801   else
 802     {
 803       /* Get the proper mode to use for this field.  We want a mode that
 804          includes the entire field.  If such a mode would be larger than
 805          a word, we won't be doing the extraction the normal way.
 806          We don't want a mode bigger than the destination.  */
 807
 808       mode = GET_MODE (op0);
 809       if (GET_MODE_BITSIZE (mode) == 0
 810           || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
 811         mode = word_mode;
 812       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
 813                             MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
 814
 815       if (mode == VOIDmode)
 816         {
 817           /* The only way this should occur is if the field spans word
 818              boundaries.  */
 819           store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
 820                                  value);
 821           return;
 822         }
 823
 824       total_bits = GET_MODE_BITSIZE (mode);
 825
 826       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
 827          be in the range 0 to total_bits-1, and put any excess bytes in
 828          OFFSET.  */
 829       if (bitpos >= total_bits)
 830         {
 831           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
 832           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
 833                      * BITS_PER_UNIT);
 834         }
 835
 836       /* Get ref to an aligned byte, halfword, or word containing the field.
 837          Adjust BITPOS to be position within a word,
 838          and OFFSET to be the offset of that word.
 839          Then alter OP0 to refer to that word.  */
 840       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
 841       offset -= (offset % (total_bits / BITS_PER_UNIT));
 842       op0 = adjust_address (op0, mode, offset);
 843     }
 844
 845   mode = GET_MODE (op0);
 846
 847   /* Now MODE is either some integral mode for a MEM as OP0,
 848      or is a full-word for a REG as OP0.  TOTAL_BITS corresponds.
 849      The bit field is contained entirely within OP0.
 850      BITPOS is the starting bit number within OP0.
 851      (OP0's mode may actually be narrower than MODE.)  */
 852
 853   if (BYTES_BIG_ENDIAN)
 854       /* BITPOS is the distance between our msb
 855          and that of the containing datum.
 856          Convert it to the distance from the lsb.  */
 857       bitpos = total_bits - bitsize - bitpos;
 858
 859   /* Now BITPOS is always the distance between our lsb
 860      and that of OP0.  */
 861
 862   /* Shift VALUE left by BITPOS bits.  If VALUE is not constant,
 863      we must first convert its mode to MODE.  */
 864
 865   if (GET_CODE (value) == CONST_INT)
 866     {
 867       HOST_WIDE_INT v = INTVAL (value);
 868
 869       if (bitsize < HOST_BITS_PER_WIDE_INT)
 870         v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
 871
 872       if (v == 0)
 873         all_zero = 1;
 874       else if ((bitsize < HOST_BITS_PER_WIDE_INT
 875                 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
 876                || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
 877         all_one = 1;
 878
 879       value = lshift_value (mode, value, bitpos, bitsize);
 880     }
 881   else
 882     {
 883       int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
 884                       && bitpos + bitsize != GET_MODE_BITSIZE (mode));
 885
 886       if (GET_MODE (value) != mode)
 887         {
 888           if ((REG_P (value) || GET_CODE (value) == SUBREG)
 889               && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
 890             value = gen_lowpart (mode, value);
 891           else
 892             value = convert_to_mode (mode, value, 1);
 893         }
 894
 895       if (must_and)
 896         value = expand_binop (mode, and_optab, value,
 897                               mask_rtx (mode, 0, bitsize, 0),
 898                               NULL_RTX, 1, OPTAB_LIB_WIDEN);
 899       if (bitpos > 0)
 900         value = expand_shift (LSHIFT_EXPR, mode, value,
 901                               build_int_2 (bitpos, 0), NULL_RTX, 1);
 902     }
 903
 904   /* Now clear the chosen bits in OP0,
 905      except that if VALUE is -1 we need not bother.  */
 906
 907   subtarget = (REG_P (op0) || ! flag_force_mem) ? op0 : 0;
 908
 909   if (! all_one)
 910     {
 911       temp = expand_binop (mode, and_optab, op0,
 912                            mask_rtx (mode, bitpos, bitsize, 1),
 913                            subtarget, 1, OPTAB_LIB_WIDEN);
 914       subtarget = temp;
 915     }
 916   else
 917     temp = op0;
 918
 919   /* Now logical-or VALUE into OP0, unless it is zero.  */
 920
 921   if (! all_zero)
 922     temp = expand_binop (mode, ior_optab, temp, value,
 923                          subtarget, 1, OPTAB_LIB_WIDEN);
 924   if (op0 != temp)
 925     emit_move_insn (op0, temp);
 926 }
 927 \f
 928 /* Store a bit field that is split across multiple accessible memory objects.
 929
 930    OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
 931    BITSIZE is the field width; BITPOS the position of its first bit
 932    (within the word).
 933    VALUE is the value to store.
 934
 935    This does not yet handle fields wider than BITS_PER_WORD.  */
 936
 937 static void
 938 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
 939                        unsigned HOST_WIDE_INT bitpos, rtx value)
 940 {
 941   unsigned int unit;
 942   unsigned int bitsdone = 0;
 943
 944   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
 945      much at a time.  */
 946   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
 947     unit = BITS_PER_WORD;
 948   else
 949     unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
 950
 951   /* If VALUE is a constant other than a CONST_INT, get it into a register in
 952      WORD_MODE.  If we can do this using gen_lowpart_common, do so.  Note
 953      that VALUE might be a floating-point constant.  */
 954   if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
 955     {
 956       rtx word = gen_lowpart_common (word_mode, value);
 957
 958       if (word && (value != word))
 959         value = word;
 960       else
 961         value = gen_lowpart_common (word_mode,
 962                                     force_reg (GET_MODE (value) != VOIDmode
 963                                                ? GET_MODE (value)
 964                                                : word_mode, value));
 965     }
 966
 967   while (bitsdone < bitsize)
 968     {
 969       unsigned HOST_WIDE_INT thissize;
 970       rtx part, word;
 971       unsigned HOST_WIDE_INT thispos;
 972       unsigned HOST_WIDE_INT offset;
 973
 974       offset = (bitpos + bitsdone) / unit;
 975       thispos = (bitpos + bitsdone) % unit;
 976
 977       /* THISSIZE must not overrun a word boundary.  Otherwise,
 978          store_fixed_bit_field will call us again, and we will mutually
 979          recurse forever.  */
 980       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
 981       thissize = MIN (thissize, unit - thispos);
 982
 983       if (BYTES_BIG_ENDIAN)
 984         {
 985           int total_bits;
 986
 987           /* We must do an endian conversion exactly the same way as it is
 988              done in extract_bit_field, so that the two calls to
 989              extract_fixed_bit_field will have comparable arguments.  */
 990           if (!MEM_P (value) || GET_MODE (value) == BLKmode)
 991             total_bits = BITS_PER_WORD;
 992           else
 993             total_bits = GET_MODE_BITSIZE (GET_MODE (value));
 994
 995           /* Fetch successively less significant portions.  */
 996           if (GET_CODE (value) == CONST_INT)
 997             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
 998                              >> (bitsize - bitsdone - thissize))
 999                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1000           else
1001             /* The args are chosen so that the last part includes the
1002                lsb.  Give extract_bit_field the value it needs (with
1003                endianness compensation) to fetch the piece we want.  */
1004             part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1005                                             total_bits - bitsize + bitsdone,
1006                                             NULL_RTX, 1);
1007         }
1008       else
1009         {
1010           /* Fetch successively more significant portions.  */
1011           if (GET_CODE (value) == CONST_INT)
1012             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1013                              >> bitsdone)
1014                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1015           else
1016             part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1017                                             bitsdone, NULL_RTX, 1);
1018         }
1019
1020       /* If OP0 is a register, then handle OFFSET here.
1021
1022          When handling multiword bitfields, extract_bit_field may pass
1023          down a word_mode SUBREG of a larger REG for a bitfield that actually
1024          crosses a word boundary.  Thus, for a SUBREG, we must find
1025          the current word starting from the base register.  */
1026       if (GET_CODE (op0) == SUBREG)
1027         {
1028           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1029           word = operand_subword_force (SUBREG_REG (op0), word_offset,
1030                                         GET_MODE (SUBREG_REG (op0)));
1031           offset = 0;
1032         }
1033       else if (REG_P (op0))
1034         {
1035           word = operand_subword_force (op0, offset, GET_MODE (op0));
1036           offset = 0;
1037         }
1038       else
1039         word = op0;
1040
1041       /* OFFSET is in UNITs, and UNIT is in bits.
1042          store_fixed_bit_field wants offset in bytes.  */
1043       store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
1044                              thispos, part);
1045       bitsdone += thissize;
1046     }
1047 }
1048 \f
1049 /* Generate code to extract a byte-field from STR_RTX
1050    containing BITSIZE bits, starting at BITNUM,
1051    and put it in TARGET if possible (if TARGET is nonzero).
1052    Regardless of TARGET, we return the rtx for where the value is placed.
1053    It may be a QUEUED.
1054
1055    STR_RTX is the structure containing the byte (a REG or MEM).
1056    UNSIGNEDP is nonzero if this is an unsigned bit field.
1057    MODE is the natural mode of the field value once extracted.
1058    TMODE is the mode the caller would like the value to have;
1059    but the value may be returned with type MODE instead.
1060
1061    TOTAL_SIZE is the size in bytes of the containing structure,
1062    or -1 if varying.
1063
1064    If a TARGET is specified and we can store in it at no extra cost,
1065    we do so, and return TARGET.
1066    Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1067    if they are equally easy.  */
1068
1069 rtx
1070 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1071                    unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1072                    enum machine_mode mode, enum machine_mode tmode)
1073 {
1074   unsigned int unit
1075     = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
1076   unsigned HOST_WIDE_INT offset = bitnum / unit;
1077   unsigned HOST_WIDE_INT bitpos = bitnum % unit;
1078   rtx op0 = str_rtx;
1079   rtx spec_target = target;
1080   rtx spec_target_subreg = 0;
1081   enum machine_mode int_mode;
1082   enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1083   enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1084   enum machine_mode mode1;
1085   int byte_offset;
1086
1087   if (tmode == VOIDmode)
1088     tmode = mode;
1089
1090   while (GET_CODE (op0) == SUBREG)
1091     {
1092       bitpos += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1093       if (bitpos > unit)
1094         {
1095           offset += (bitpos / unit);
1096           bitpos %= unit;
1097         }
1098       op0 = SUBREG_REG (op0);
1099     }
1100
1101   if (REG_P (op0)
1102       && mode == GET_MODE (op0)
1103       && bitnum == 0
1104       && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1105     {
1106       /* We're trying to extract a full register from itself.  */
1107       return op0;
1108     }
1109
1110   /* Use vec_extract patterns for extracting parts of vectors whenever
1111      available.  */
1112   if (VECTOR_MODE_P (GET_MODE (op0))
1113       && !MEM_P (op0)
1114       && (vec_extract_optab->handlers[GET_MODE (op0)].insn_code
1115           != CODE_FOR_nothing)
1116       && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1117           == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1118     {
1119       enum machine_mode outermode = GET_MODE (op0);
1120       enum machine_mode innermode = GET_MODE_INNER (outermode);
1121       int icode = (int) vec_extract_optab->handlers[outermode].insn_code;
1122       unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode);
1123       rtx rtxpos = GEN_INT (pos);
1124       rtx src = op0;
1125       rtx dest = NULL, pat, seq;
1126       enum machine_mode mode0 = insn_data[icode].operand[0].mode;
1127       enum machine_mode mode1 = insn_data[icode].operand[1].mode;
1128       enum machine_mode mode2 = insn_data[icode].operand[2].mode;
1129
1130       if (innermode == tmode || innermode == mode)
1131         dest = target;
1132
1133       if (!dest)
1134         dest = gen_reg_rtx (innermode);
1135
1136       start_sequence ();
1137
1138       if (! (*insn_data[icode].operand[0].predicate) (dest, mode0))
1139         dest = copy_to_mode_reg (mode0, dest);
1140
1141       if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
1142         src = copy_to_mode_reg (mode1, src);
1143
1144       if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1145         rtxpos = copy_to_mode_reg (mode1, rtxpos);
1146
1147       /* We could handle this, but we should always be called with a pseudo
1148          for our targets and all insns should take them as outputs.  */
1149       if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)
1150           || ! (*insn_data[icode].operand[1].predicate) (src, mode1)
1151           || ! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1152         abort ();
1153
1154       pat = GEN_FCN (icode) (dest, src, rtxpos);
1155       seq = get_insns ();
1156       end_sequence ();
1157       if (pat)
1158         {
1159           emit_insn (seq);
1160           emit_insn (pat);
1161           return dest;
1162         }
1163     }
1164
1165   /* Make sure we are playing with integral modes.  Pun with subregs
1166      if we aren't.  */
1167   {
1168     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1169     if (imode != GET_MODE (op0))
1170       {
1171         if (MEM_P (op0))
1172           op0 = adjust_address (op0, imode, 0);
1173         else if (imode != BLKmode)
1174           op0 = gen_lowpart (imode, op0);
1175         else
1176           abort ();
1177       }
1178   }
1179
1180   /* We may be accessing data outside the field, which means
1181      we can alias adjacent data.  */
1182   if (MEM_P (op0))
1183     {
1184       op0 = shallow_copy_rtx (op0);
1185       set_mem_alias_set (op0, 0);
1186       set_mem_expr (op0, 0);
1187     }
1188
1189   /* Extraction of a full-word or multi-word value from a structure
1190      in a register or aligned memory can be done with just a SUBREG.
1191      A subword value in the least significant part of a register
1192      can also be extracted with a SUBREG.  For this, we need the
1193      byte offset of the value in op0.  */
1194
1195   byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1196
1197   /* If OP0 is a register, BITPOS must count within a word.
1198      But as we have it, it counts within whatever size OP0 now has.
1199      On a bigendian machine, these are not the same, so convert.  */
1200   if (BYTES_BIG_ENDIAN
1201       && !MEM_P (op0)
1202       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1203     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1204
1205   /* ??? We currently assume TARGET is at least as big as BITSIZE.
1206      If that's wrong, the solution is to test for it and set TARGET to 0
1207      if needed.  */
1208
1209   /* Only scalar integer modes can be converted via subregs.  There is an
1210      additional problem for FP modes here in that they can have a precision
1211      which is different from the size.  mode_for_size uses precision, but
1212      we want a mode based on the size, so we must avoid calling it for FP
1213      modes.  */
1214   mode1  = (SCALAR_INT_MODE_P (tmode)
1215             ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0)
1216             : mode);
1217
1218   if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1219         && bitpos % BITS_PER_WORD == 0)
1220        || (mode1 != BLKmode
1221            /* ??? The big endian test here is wrong.  This is correct
1222               if the value is in a register, and if mode_for_size is not
1223               the same mode as op0.  This causes us to get unnecessarily
1224               inefficient code from the Thumb port when -mbig-endian.  */
1225            && (BYTES_BIG_ENDIAN
1226                ? bitpos + bitsize == BITS_PER_WORD
1227                : bitpos == 0)))
1228       && ((!MEM_P (op0)
1229            && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1230                                      GET_MODE_BITSIZE (GET_MODE (op0)))
1231            && GET_MODE_SIZE (mode1) != 0
1232            && byte_offset % GET_MODE_SIZE (mode1) == 0)
1233           || (MEM_P (op0)
1234               && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1235                   || (offset * BITS_PER_UNIT % bitsize == 0
1236                       && MEM_ALIGN (op0) % bitsize == 0)))))
1237     {
1238       if (mode1 != GET_MODE (op0))
1239         {
1240           if (GET_CODE (op0) == SUBREG)
1241             {
1242               if (GET_MODE (SUBREG_REG (op0)) == mode1
1243                   || GET_MODE_CLASS (mode1) == MODE_INT
1244                   || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1245                 op0 = SUBREG_REG (op0);
1246               else
1247                 /* Else we've got some float mode source being extracted into
1248                    a different float mode destination -- this combination of
1249                    subregs results in Severe Tire Damage.  */
1250                 goto no_subreg_mode_swap;
1251             }
1252           if (REG_P (op0))
1253             op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1254           else
1255             op0 = adjust_address (op0, mode1, offset);
1256         }
1257       if (mode1 != mode)
1258         return convert_to_mode (tmode, op0, unsignedp);
1259       return op0;
1260     }
1261  no_subreg_mode_swap:
1262
1263   /* Handle fields bigger than a word.  */
1264
1265   if (bitsize > BITS_PER_WORD)
1266     {
1267       /* Here we transfer the words of the field
1268          in the order least significant first.
1269          This is because the most significant word is the one which may
1270          be less than full.  */
1271
1272       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1273       unsigned int i;
1274
1275       if (target == 0 || !REG_P (target))
1276         target = gen_reg_rtx (mode);
1277
1278       /* Indicate for flow that the entire target reg is being set.  */
1279       emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1280
1281       for (i = 0; i < nwords; i++)
1282         {
1283           /* If I is 0, use the low-order word in both field and target;
1284              if I is 1, use the next to lowest word; and so on.  */
1285           /* Word number in TARGET to use.  */
1286           unsigned int wordnum
1287             = (WORDS_BIG_ENDIAN
1288                ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1289                : i);
1290           /* Offset from start of field in OP0.  */
1291           unsigned int bit_offset = (WORDS_BIG_ENDIAN
1292                                      ? MAX (0, ((int) bitsize - ((int) i + 1)
1293                                                 * (int) BITS_PER_WORD))
1294                                      : (int) i * BITS_PER_WORD);
1295           rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1296           rtx result_part
1297             = extract_bit_field (op0, MIN (BITS_PER_WORD,
1298                                            bitsize - i * BITS_PER_WORD),
1299                                  bitnum + bit_offset, 1, target_part, mode,
1300                                  word_mode);
1301
1302           if (target_part == 0)
1303             abort ();
1304
1305           if (result_part != target_part)
1306             emit_move_insn (target_part, result_part);
1307         }
1308
1309       if (unsignedp)
1310         {
1311           /* Unless we've filled TARGET, the upper regs in a multi-reg value
1312              need to be zero'd out.  */
1313           if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1314             {
1315               unsigned int i, total_words;
1316
1317               total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1318               for (i = nwords; i < total_words; i++)
1319                 emit_move_insn
1320                   (operand_subword (target,
1321                                     WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1322                                     1, VOIDmode),
1323                    const0_rtx);
1324             }
1325           return target;
1326         }
1327
1328       /* Signed bit field: sign-extend with two arithmetic shifts.  */
1329       target = expand_shift (LSHIFT_EXPR, mode, target,
1330                              build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1331                              NULL_RTX, 0);
1332       return expand_shift (RSHIFT_EXPR, mode, target,
1333                            build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1334                            NULL_RTX, 0);
1335     }
1336
1337   /* From here on we know the desired field is smaller than a word.  */
1338
1339   /* Check if there is a correspondingly-sized integer field, so we can
1340      safely extract it as one size of integer, if necessary; then
1341      truncate or extend to the size that is wanted; then use SUBREGs or
1342      convert_to_mode to get one of the modes we really wanted.  */
1343
1344   int_mode = int_mode_for_mode (tmode);
1345   if (int_mode == BLKmode)
1346     int_mode = int_mode_for_mode (mode);
1347   if (int_mode == BLKmode)
1348     abort ();    /* Should probably push op0 out to memory and then
1349                     do a load.  */
1350
1351   /* OFFSET is the number of words or bytes (UNIT says which)
1352      from STR_RTX to the first word or byte containing part of the field.  */
1353
1354   if (!MEM_P (op0))
1355     {
1356       if (offset != 0
1357           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1358         {
1359           if (!REG_P (op0))
1360             op0 = copy_to_reg (op0);
1361           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1362                                 op0, (offset * UNITS_PER_WORD));
1363         }
1364       offset = 0;
1365     }
1366
1367   /* Now OFFSET is nonzero only for memory operands.  */
1368
1369   if (unsignedp)
1370     {
1371       if (HAVE_extzv
1372           && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1373           && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
1374                 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1375         {
1376           unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1377           rtx bitsize_rtx, bitpos_rtx;
1378           rtx last = get_last_insn ();
1379           rtx xop0 = op0;
1380           rtx xtarget = target;
1381           rtx xspec_target = spec_target;
1382           rtx xspec_target_subreg = spec_target_subreg;
1383           rtx pat;
1384           enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1385
1386           if (MEM_P (xop0))
1387             {
1388               int save_volatile_ok = volatile_ok;
1389               volatile_ok = 1;
1390
1391               /* Is the memory operand acceptable?  */
1392               if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1393                      (xop0, GET_MODE (xop0))))
1394                 {
1395                   /* No, load into a reg and extract from there.  */
1396                   enum machine_mode bestmode;
1397
1398                   /* Get the mode to use for inserting into this field.  If
1399                      OP0 is BLKmode, get the smallest mode consistent with the
1400                      alignment. If OP0 is a non-BLKmode object that is no
1401                      wider than MAXMODE, use its mode. Otherwise, use the
1402                      smallest mode containing the field.  */
1403
1404                   if (GET_MODE (xop0) == BLKmode
1405                       || (GET_MODE_SIZE (GET_MODE (op0))
1406                           > GET_MODE_SIZE (maxmode)))
1407                     bestmode = get_best_mode (bitsize, bitnum,
1408                                               MEM_ALIGN (xop0), maxmode,
1409                                               MEM_VOLATILE_P (xop0));
1410                   else
1411                     bestmode = GET_MODE (xop0);
1412
1413                   if (bestmode == VOIDmode
1414                       || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1415                           && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1416                     goto extzv_loses;
1417
1418                   /* Compute offset as multiple of this unit,
1419                      counting in bytes.  */
1420                   unit = GET_MODE_BITSIZE (bestmode);
1421                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1422                   xbitpos = bitnum % unit;
1423                   xop0 = adjust_address (xop0, bestmode, xoffset);
1424
1425                   /* Fetch it to a register in that size.  */
1426                   xop0 = force_reg (bestmode, xop0);
1427
1428                   /* XBITPOS counts within UNIT, which is what is expected.  */
1429                 }
1430               else
1431                 /* Get ref to first byte containing part of the field.  */
1432                 xop0 = adjust_address (xop0, byte_mode, xoffset);
1433
1434               volatile_ok = save_volatile_ok;
1435             }
1436
1437           /* If op0 is a register, we need it in MAXMODE (which is usually
1438              SImode). to make it acceptable to the format of extzv.  */
1439           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1440             goto extzv_loses;
1441           if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
1442             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1443
1444           /* On big-endian machines, we count bits from the most significant.
1445              If the bit field insn does not, we must invert.  */
1446           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1447             xbitpos = unit - bitsize - xbitpos;
1448
1449           /* Now convert from counting within UNIT to counting in MAXMODE.  */
1450           if (BITS_BIG_ENDIAN && !MEM_P (xop0))
1451             xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1452
1453           unit = GET_MODE_BITSIZE (maxmode);
1454
1455           if (xtarget == 0
1456               || (flag_force_mem && MEM_P (xtarget)))
1457             xtarget = xspec_target = gen_reg_rtx (tmode);
1458
1459           if (GET_MODE (xtarget) != maxmode)
1460             {
1461               if (REG_P (xtarget))
1462                 {
1463                   int wider = (GET_MODE_SIZE (maxmode)
1464                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1465                   xtarget = gen_lowpart (maxmode, xtarget);
1466                   if (wider)
1467                     xspec_target_subreg = xtarget;
1468                 }
1469               else
1470                 xtarget = gen_reg_rtx (maxmode);
1471             }
1472
1473           /* If this machine's extzv insists on a register target,
1474              make sure we have one.  */
1475           if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1476                  (xtarget, maxmode)))
1477             xtarget = gen_reg_rtx (maxmode);
1478
1479           bitsize_rtx = GEN_INT (bitsize);
1480           bitpos_rtx = GEN_INT (xbitpos);
1481
1482           pat = gen_extzv (xtarget, xop0, bitsize_rtx, bitpos_rtx);
1483           if (pat)
1484             {
1485               emit_insn (pat);
1486               target = xtarget;
1487               spec_target = xspec_target;
1488               spec_target_subreg = xspec_target_subreg;
1489             }
1490           else
1491             {
1492               delete_insns_since (last);
1493               target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1494                                                 bitpos, target, 1);
1495             }
1496         }
1497       else
1498       extzv_loses:
1499         target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1500                                           bitpos, target, 1);
1501     }
1502   else
1503     {
1504       if (HAVE_extv
1505           && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1506           && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
1507                 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1508         {
1509           int xbitpos = bitpos, xoffset = offset;
1510           rtx bitsize_rtx, bitpos_rtx;
1511           rtx last = get_last_insn ();
1512           rtx xop0 = op0, xtarget = target;
1513           rtx xspec_target = spec_target;
1514           rtx xspec_target_subreg = spec_target_subreg;
1515           rtx pat;
1516           enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1517
1518           if (MEM_P (xop0))
1519             {
1520               /* Is the memory operand acceptable?  */
1521               if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1522                      (xop0, GET_MODE (xop0))))
1523                 {
1524                   /* No, load into a reg and extract from there.  */
1525                   enum machine_mode bestmode;
1526
1527                   /* Get the mode to use for inserting into this field.  If
1528                      OP0 is BLKmode, get the smallest mode consistent with the
1529                      alignment. If OP0 is a non-BLKmode object that is no
1530                      wider than MAXMODE, use its mode. Otherwise, use the
1531                      smallest mode containing the field.  */
1532
1533                   if (GET_MODE (xop0) == BLKmode
1534                       || (GET_MODE_SIZE (GET_MODE (op0))
1535                           > GET_MODE_SIZE (maxmode)))
1536                     bestmode = get_best_mode (bitsize, bitnum,
1537                                               MEM_ALIGN (xop0), maxmode,
1538                                               MEM_VOLATILE_P (xop0));
1539                   else
1540                     bestmode = GET_MODE (xop0);
1541
1542                   if (bestmode == VOIDmode
1543                       || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1544                           && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1545                     goto extv_loses;
1546
1547                   /* Compute offset as multiple of this unit,
1548                      counting in bytes.  */
1549                   unit = GET_MODE_BITSIZE (bestmode);
1550                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1551                   xbitpos = bitnum % unit;
1552                   xop0 = adjust_address (xop0, bestmode, xoffset);
1553
1554                   /* Fetch it to a register in that size.  */
1555                   xop0 = force_reg (bestmode, xop0);
1556
1557                   /* XBITPOS counts within UNIT, which is what is expected.  */
1558                 }
1559               else
1560                 /* Get ref to first byte containing part of the field.  */
1561                 xop0 = adjust_address (xop0, byte_mode, xoffset);
1562             }
1563
1564           /* If op0 is a register, we need it in MAXMODE (which is usually
1565              SImode) to make it acceptable to the format of extv.  */
1566           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1567             goto extv_loses;
1568           if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
1569             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1570
1571           /* On big-endian machines, we count bits from the most significant.
1572              If the bit field insn does not, we must invert.  */
1573           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1574             xbitpos = unit - bitsize - xbitpos;
1575
1576           /* XBITPOS counts within a size of UNIT.
1577              Adjust to count within a size of MAXMODE.  */
1578           if (BITS_BIG_ENDIAN && !MEM_P (xop0))
1579             xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1580
1581           unit = GET_MODE_BITSIZE (maxmode);
1582
1583           if (xtarget == 0
1584               || (flag_force_mem && MEM_P (xtarget)))
1585             xtarget = xspec_target = gen_reg_rtx (tmode);
1586
1587           if (GET_MODE (xtarget) != maxmode)
1588             {
1589               if (REG_P (xtarget))
1590                 {
1591                   int wider = (GET_MODE_SIZE (maxmode)
1592                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1593                   xtarget = gen_lowpart (maxmode, xtarget);
1594                   if (wider)
1595                     xspec_target_subreg = xtarget;
1596                 }
1597               else
1598                 xtarget = gen_reg_rtx (maxmode);
1599             }
1600
1601           /* If this machine's extv insists on a register target,
1602              make sure we have one.  */
1603           if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1604                  (xtarget, maxmode)))
1605             xtarget = gen_reg_rtx (maxmode);
1606
1607           bitsize_rtx = GEN_INT (bitsize);
1608           bitpos_rtx = GEN_INT (xbitpos);
1609
1610           pat = gen_extv (xtarget, xop0, bitsize_rtx, bitpos_rtx);
1611           if (pat)
1612             {
1613               emit_insn (pat);
1614               target = xtarget;
1615               spec_target = xspec_target;
1616               spec_target_subreg = xspec_target_subreg;
1617             }
1618           else
1619             {
1620               delete_insns_since (last);
1621               target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1622                                                 bitpos, target, 0);
1623             }
1624         }
1625       else
1626       extv_loses:
1627         target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1628                                           bitpos, target, 0);
1629     }
1630   if (target == spec_target)
1631     return target;
1632   if (target == spec_target_subreg)
1633     return spec_target;
1634   if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1635     {
1636       /* If the target mode is floating-point, first convert to the
1637          integer mode of that size and then access it as a floating-point
1638          value via a SUBREG.  */
1639       if (GET_MODE_CLASS (tmode) != MODE_INT
1640           && GET_MODE_CLASS (tmode) != MODE_PARTIAL_INT)
1641         {
1642           target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1643                                                    MODE_INT, 0),
1644                                     target, unsignedp);
1645           return gen_lowpart (tmode, target);
1646         }
1647       else
1648         return convert_to_mode (tmode, target, unsignedp);
1649     }
1650   return target;
1651 }
1652 \f
1653 /* Extract a bit field using shifts and boolean operations
1654    Returns an rtx to represent the value.
1655    OP0 addresses a register (word) or memory (byte).
1656    BITPOS says which bit within the word or byte the bit field starts in.
1657    OFFSET says how many bytes farther the bit field starts;
1658     it is 0 if OP0 is a register.
1659    BITSIZE says how many bits long the bit field is.
1660     (If OP0 is a register, it may be narrower than a full word,
1661      but BITPOS still counts within a full word,
1662      which is significant on bigendian machines.)
1663
1664    UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1665    If TARGET is nonzero, attempts to store the value there
1666    and return TARGET, but this is not guaranteed.
1667    If TARGET is not used, create a pseudo-reg of mode TMODE for the value.  */
1668
1669 static rtx
1670 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1671                          unsigned HOST_WIDE_INT offset,
1672                          unsigned HOST_WIDE_INT bitsize,
1673                          unsigned HOST_WIDE_INT bitpos, rtx target,
1674                          int unsignedp)
1675 {
1676   unsigned int total_bits = BITS_PER_WORD;
1677   enum machine_mode mode;
1678
1679   if (GET_CODE (op0) == SUBREG || REG_P (op0))
1680     {
1681       /* Special treatment for a bit field split across two registers.  */
1682       if (bitsize + bitpos > BITS_PER_WORD)
1683         return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1684     }
1685   else
1686     {
1687       /* Get the proper mode to use for this field.  We want a mode that
1688          includes the entire field.  If such a mode would be larger than
1689          a word, we won't be doing the extraction the normal way.  */
1690
1691       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1692                             MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1693
1694       if (mode == VOIDmode)
1695         /* The only way this should occur is if the field spans word
1696            boundaries.  */
1697         return extract_split_bit_field (op0, bitsize,
1698                                         bitpos + offset * BITS_PER_UNIT,
1699                                         unsignedp);
1700
1701       total_bits = GET_MODE_BITSIZE (mode);
1702
1703       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
1704          be in the range 0 to total_bits-1, and put any excess bytes in
1705          OFFSET.  */
1706       if (bitpos >= total_bits)
1707         {
1708           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1709           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1710                      * BITS_PER_UNIT);
1711         }
1712
1713       /* Get ref to an aligned byte, halfword, or word containing the field.
1714          Adjust BITPOS to be position within a word,
1715          and OFFSET to be the offset of that word.
1716          Then alter OP0 to refer to that word.  */
1717       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1718       offset -= (offset % (total_bits / BITS_PER_UNIT));
1719       op0 = adjust_address (op0, mode, offset);
1720     }
1721
1722   mode = GET_MODE (op0);
1723
1724   if (BYTES_BIG_ENDIAN)
1725     /* BITPOS is the distance between our msb and that of OP0.
1726        Convert it to the distance from the lsb.  */
1727     bitpos = total_bits - bitsize - bitpos;
1728
1729   /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1730      We have reduced the big-endian case to the little-endian case.  */
1731
1732   if (unsignedp)
1733     {
1734       if (bitpos)
1735         {
1736           /* If the field does not already start at the lsb,
1737              shift it so it does.  */
1738           tree amount = build_int_2 (bitpos, 0);
1739           /* Maybe propagate the target for the shift.  */
1740           /* But not if we will return it--could confuse integrate.c.  */
1741           rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1742           if (tmode != mode) subtarget = 0;
1743           op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1744         }
1745       /* Convert the value to the desired mode.  */
1746       if (mode != tmode)
1747         op0 = convert_to_mode (tmode, op0, 1);
1748
1749       /* Unless the msb of the field used to be the msb when we shifted,
1750          mask out the upper bits.  */
1751
1752       if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1753         return expand_binop (GET_MODE (op0), and_optab, op0,
1754                              mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1755                              target, 1, OPTAB_LIB_WIDEN);
1756       return op0;
1757     }
1758
1759   /* To extract a signed bit-field, first shift its msb to the msb of the word,
1760      then arithmetic-shift its lsb to the lsb of the word.  */
1761   op0 = force_reg (mode, op0);
1762   if (mode != tmode)
1763     target = 0;
1764
1765   /* Find the narrowest integer mode that contains the field.  */
1766
1767   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1768        mode = GET_MODE_WIDER_MODE (mode))
1769     if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1770       {
1771         op0 = convert_to_mode (mode, op0, 0);
1772         break;
1773       }
1774
1775   if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1776     {
1777       tree amount
1778         = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1779       /* Maybe propagate the target for the shift.  */
1780       rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1781       op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1782     }
1783
1784   return expand_shift (RSHIFT_EXPR, mode, op0,
1785                        build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1786                        target, 0);
1787 }
1788 \f
1789 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1790    of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1791    complement of that if COMPLEMENT.  The mask is truncated if
1792    necessary to the width of mode MODE.  The mask is zero-extended if
1793    BITSIZE+BITPOS is too small for MODE.  */
1794
1795 static rtx
1796 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1797 {
1798   HOST_WIDE_INT masklow, maskhigh;
1799
1800   if (bitsize == 0)
1801     masklow = 0;
1802   else if (bitpos < HOST_BITS_PER_WIDE_INT)
1803     masklow = (HOST_WIDE_INT) -1 << bitpos;
1804   else
1805     masklow = 0;
1806
1807   if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1808     masklow &= ((unsigned HOST_WIDE_INT) -1
1809                 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1810
1811   if (bitpos <= HOST_BITS_PER_WIDE_INT)
1812     maskhigh = -1;
1813   else
1814     maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1815
1816   if (bitsize == 0)
1817     maskhigh = 0;
1818   else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1819     maskhigh &= ((unsigned HOST_WIDE_INT) -1
1820                  >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1821   else
1822     maskhigh = 0;
1823
1824   if (complement)
1825     {
1826       maskhigh = ~maskhigh;
1827       masklow = ~masklow;
1828     }
1829
1830   return immed_double_const (masklow, maskhigh, mode);
1831 }
1832
1833 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1834    VALUE truncated to BITSIZE bits and then shifted left BITPOS bits.  */
1835
1836 static rtx
1837 lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize)
1838 {
1839   unsigned HOST_WIDE_INT v = INTVAL (value);
1840   HOST_WIDE_INT low, high;
1841
1842   if (bitsize < HOST_BITS_PER_WIDE_INT)
1843     v &= ~((HOST_WIDE_INT) -1 << bitsize);
1844
1845   if (bitpos < HOST_BITS_PER_WIDE_INT)
1846     {
1847       low = v << bitpos;
1848       high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1849     }
1850   else
1851     {
1852       low = 0;
1853       high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1854     }
1855
1856   return immed_double_const (low, high, mode);
1857 }
1858 \f
1859 /* Extract a bit field that is split across two words
1860    and return an RTX for the result.
1861
1862    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1863    BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1864    UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.  */
1865
1866 static rtx
1867 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1868                          unsigned HOST_WIDE_INT bitpos, int unsignedp)
1869 {
1870   unsigned int unit;
1871   unsigned int bitsdone = 0;
1872   rtx result = NULL_RTX;
1873   int first = 1;
1874
1875   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1876      much at a time.  */
1877   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1878     unit = BITS_PER_WORD;
1879   else
1880     unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1881
1882   while (bitsdone < bitsize)
1883     {
1884       unsigned HOST_WIDE_INT thissize;
1885       rtx part, word;
1886       unsigned HOST_WIDE_INT thispos;
1887       unsigned HOST_WIDE_INT offset;
1888
1889       offset = (bitpos + bitsdone) / unit;
1890       thispos = (bitpos + bitsdone) % unit;
1891
1892       /* THISSIZE must not overrun a word boundary.  Otherwise,
1893          extract_fixed_bit_field will call us again, and we will mutually
1894          recurse forever.  */
1895       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1896       thissize = MIN (thissize, unit - thispos);
1897
1898       /* If OP0 is a register, then handle OFFSET here.
1899
1900          When handling multiword bitfields, extract_bit_field may pass
1901          down a word_mode SUBREG of a larger REG for a bitfield that actually
1902          crosses a word boundary.  Thus, for a SUBREG, we must find
1903          the current word starting from the base register.  */
1904       if (GET_CODE (op0) == SUBREG)
1905         {
1906           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1907           word = operand_subword_force (SUBREG_REG (op0), word_offset,
1908                                         GET_MODE (SUBREG_REG (op0)));
1909           offset = 0;
1910         }
1911       else if (REG_P (op0))
1912         {
1913           word = operand_subword_force (op0, offset, GET_MODE (op0));
1914           offset = 0;
1915         }
1916       else
1917         word = op0;
1918
1919       /* Extract the parts in bit-counting order,
1920          whose meaning is determined by BYTES_PER_UNIT.
1921          OFFSET is in UNITs, and UNIT is in bits.
1922          extract_fixed_bit_field wants offset in bytes.  */
1923       part = extract_fixed_bit_field (word_mode, word,
1924                                       offset * unit / BITS_PER_UNIT,
1925                                       thissize, thispos, 0, 1);
1926       bitsdone += thissize;
1927
1928       /* Shift this part into place for the result.  */
1929       if (BYTES_BIG_ENDIAN)
1930         {
1931           if (bitsize != bitsdone)
1932             part = expand_shift (LSHIFT_EXPR, word_mode, part,
1933                                  build_int_2 (bitsize - bitsdone, 0), 0, 1);
1934         }
1935       else
1936         {
1937           if (bitsdone != thissize)
1938             part = expand_shift (LSHIFT_EXPR, word_mode, part,
1939                                  build_int_2 (bitsdone - thissize, 0), 0, 1);
1940         }
1941
1942       if (first)
1943         result = part;
1944       else
1945         /* Combine the parts with bitwise or.  This works
1946            because we extracted each part as an unsigned bit field.  */
1947         result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1948                                OPTAB_LIB_WIDEN);
1949
1950       first = 0;
1951     }
1952
1953   /* Unsigned bit field: we are done.  */
1954   if (unsignedp)
1955     return result;
1956   /* Signed bit field: sign-extend with two arithmetic shifts.  */
1957   result = expand_shift (LSHIFT_EXPR, word_mode, result,
1958                          build_int_2 (BITS_PER_WORD - bitsize, 0),
1959                          NULL_RTX, 0);
1960   return expand_shift (RSHIFT_EXPR, word_mode, result,
1961                        build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1962 }
1963 \f
1964 /* Add INC into TARGET.  */
1965
1966 void
1967 expand_inc (rtx target, rtx inc)
1968 {
1969   rtx value = expand_binop (GET_MODE (target), add_optab,
1970                             target, inc,
1971                             target, 0, OPTAB_LIB_WIDEN);
1972   if (value != target)
1973     emit_move_insn (target, value);
1974 }
1975
1976 /* Subtract DEC from TARGET.  */
1977
1978 void
1979 expand_dec (rtx target, rtx dec)
1980 {
1981   rtx value = expand_binop (GET_MODE (target), sub_optab,
1982                             target, dec,
1983                             target, 0, OPTAB_LIB_WIDEN);
1984   if (value != target)
1985     emit_move_insn (target, value);
1986 }
1987 \f
1988 /* Output a shift instruction for expression code CODE,
1989    with SHIFTED being the rtx for the value to shift,
1990    and AMOUNT the tree for the amount to shift by.
1991    Store the result in the rtx TARGET, if that is convenient.
1992    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1993    Return the rtx for where the value is.  */
1994
1995 rtx
1996 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
1997               tree amount, rtx target, int unsignedp)
1998 {
1999   rtx op1, temp = 0;
2000   int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2001   int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2002   int try;
2003
2004   /* Previously detected shift-counts computed by NEGATE_EXPR
2005      and shifted in the other direction; but that does not work
2006      on all machines.  */
2007
2008   op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
2009
2010   if (SHIFT_COUNT_TRUNCATED)
2011     {
2012       if (GET_CODE (op1) == CONST_INT
2013           && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2014               (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
2015         op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2016                        % GET_MODE_BITSIZE (mode));
2017       else if (GET_CODE (op1) == SUBREG
2018                && subreg_lowpart_p (op1))
2019         op1 = SUBREG_REG (op1);
2020     }
2021
2022   if (op1 == const0_rtx)
2023     return shifted;
2024
2025   /* Check whether its cheaper to implement a left shift by a constant
2026      bit count by a sequence of additions.  */
2027   if (code == LSHIFT_EXPR
2028       && GET_CODE (op1) == CONST_INT
2029       && INTVAL (op1) > 0
2030       && INTVAL (op1) < GET_MODE_BITSIZE (mode)
2031       && shift_cost[mode][INTVAL (op1)] > INTVAL (op1) * add_cost[mode])
2032     {
2033       int i;
2034       for (i = 0; i < INTVAL (op1); i++)
2035         {
2036           temp = force_reg (mode, shifted);
2037           shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2038                                   unsignedp, OPTAB_LIB_WIDEN);
2039         }
2040       return shifted;
2041     }
2042
2043   for (try = 0; temp == 0 && try < 3; try++)
2044     {
2045       enum optab_methods methods;
2046
2047       if (try == 0)
2048         methods = OPTAB_DIRECT;
2049       else if (try == 1)
2050         methods = OPTAB_WIDEN;
2051       else
2052         methods = OPTAB_LIB_WIDEN;
2053
2054       if (rotate)
2055         {
2056           /* Widening does not work for rotation.  */
2057           if (methods == OPTAB_WIDEN)
2058             continue;
2059           else if (methods == OPTAB_LIB_WIDEN)
2060             {
2061               /* If we have been unable to open-code this by a rotation,
2062                  do it as the IOR of two shifts.  I.e., to rotate A
2063                  by N bits, compute (A << N) | ((unsigned) A >> (C - N))
2064                  where C is the bitsize of A.
2065
2066                  It is theoretically possible that the target machine might
2067                  not be able to perform either shift and hence we would
2068                  be making two libcalls rather than just the one for the
2069                  shift (similarly if IOR could not be done).  We will allow
2070                  this extremely unlikely lossage to avoid complicating the
2071                  code below.  */
2072
2073               rtx subtarget = target == shifted ? 0 : target;
2074               rtx temp1;
2075               tree type = TREE_TYPE (amount);
2076               tree new_amount = make_tree (type, op1);
2077               tree other_amount
2078                 = fold (build (MINUS_EXPR, type,
2079                                convert (type,
2080                                         build_int_2 (GET_MODE_BITSIZE (mode),
2081                                                      0)),
2082                                amount));
2083
2084               shifted = force_reg (mode, shifted);
2085
2086               temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2087                                    mode, shifted, new_amount, subtarget, 1);
2088               temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2089                                     mode, shifted, other_amount, 0, 1);
2090               return expand_binop (mode, ior_optab, temp, temp1, target,
2091                                    unsignedp, methods);
2092             }
2093
2094           temp = expand_binop (mode,
2095                                left ? rotl_optab : rotr_optab,
2096                                shifted, op1, target, unsignedp, methods);
2097
2098           /* If we don't have the rotate, but we are rotating by a constant
2099              that is in range, try a rotate in the opposite direction.  */
2100
2101           if (temp == 0 && GET_CODE (op1) == CONST_INT
2102               && INTVAL (op1) > 0
2103               && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
2104             temp = expand_binop (mode,
2105                                  left ? rotr_optab : rotl_optab,
2106                                  shifted,
2107                                  GEN_INT (GET_MODE_BITSIZE (mode)
2108                                           - INTVAL (op1)),
2109                                  target, unsignedp, methods);
2110         }
2111       else if (unsignedp)
2112         temp = expand_binop (mode,
2113                              left ? ashl_optab : lshr_optab,
2114                              shifted, op1, target, unsignedp, methods);
2115
2116       /* Do arithmetic shifts.
2117          Also, if we are going to widen the operand, we can just as well
2118          use an arithmetic right-shift instead of a logical one.  */
2119       if (temp == 0 && ! rotate
2120           && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2121         {
2122           enum optab_methods methods1 = methods;
2123
2124           /* If trying to widen a log shift to an arithmetic shift,
2125              don't accept an arithmetic shift of the same size.  */
2126           if (unsignedp)
2127             methods1 = OPTAB_MUST_WIDEN;
2128
2129           /* Arithmetic shift */
2130
2131           temp = expand_binop (mode,
2132                                left ? ashl_optab : ashr_optab,
2133                                shifted, op1, target, unsignedp, methods1);
2134         }
2135
2136       /* We used to try extzv here for logical right shifts, but that was
2137          only useful for one machine, the VAX, and caused poor code
2138          generation there for lshrdi3, so the code was deleted and a
2139          define_expand for lshrsi3 was added to vax.md.  */
2140     }
2141
2142   if (temp == 0)
2143     abort ();
2144   return temp;
2145 }
2146 \f
2147 enum alg_code { alg_zero, alg_m, alg_shift,
2148                   alg_add_t_m2, alg_sub_t_m2,
2149                   alg_add_factor, alg_sub_factor,
2150                   alg_add_t2_m, alg_sub_t2_m,
2151                   alg_add, alg_subtract, alg_factor, alg_shiftop };
2152
2153 /* This structure records a sequence of operations.
2154    `ops' is the number of operations recorded.
2155    `cost' is their total cost.
2156    The operations are stored in `op' and the corresponding
2157    logarithms of the integer coefficients in `log'.
2158
2159    These are the operations:
2160    alg_zero             total := 0;
2161    alg_m                total := multiplicand;
2162    alg_shift            total := total * coeff
2163    alg_add_t_m2         total := total + multiplicand * coeff;
2164    alg_sub_t_m2         total := total - multiplicand * coeff;
2165    alg_add_factor       total := total * coeff + total;
2166    alg_sub_factor       total := total * coeff - total;
2167    alg_add_t2_m         total := total * coeff + multiplicand;
2168    alg_sub_t2_m         total := total * coeff - multiplicand;
2169
2170    The first operand must be either alg_zero or alg_m.  */
2171
2172 struct algorithm
2173 {
2174   short cost;
2175   short ops;
2176   /* The size of the OP and LOG fields are not directly related to the
2177      word size, but the worst-case algorithms will be if we have few
2178      consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2179      In that case we will generate shift-by-2, add, shift-by-2, add,...,
2180      in total wordsize operations.  */
2181   enum alg_code op[MAX_BITS_PER_WORD];
2182   char log[MAX_BITS_PER_WORD];
2183 };
2184
2185 /* Indicates the type of fixup needed after a constant multiplication.
2186    BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2187    the result should be negated, and ADD_VARIANT means that the
2188    multiplicand should be added to the result.  */
2189 enum mult_variant {basic_variant, negate_variant, add_variant};
2190
2191 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2192                         int, enum machine_mode mode);
2193 static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT,
2194                                  struct algorithm *, enum mult_variant *, int);
2195 static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx,
2196                               const struct algorithm *, enum mult_variant);
2197 static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int,
2198                                                  int, unsigned HOST_WIDE_INT *,
2199                                                  int *, int *);
2200 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2201 static rtx extract_high_half (enum machine_mode, rtx);
2202 static rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx,
2203                                        int, int);
2204 /* Compute and return the best algorithm for multiplying by T.
2205    The algorithm must cost less than cost_limit
2206    If retval.cost >= COST_LIMIT, no algorithm was found and all
2207    other field of the returned struct are undefined.
2208    MODE is the machine mode of the multiplication.  */
2209
2210 static void
2211 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2212             int cost_limit, enum machine_mode mode)
2213 {
2214   int m;
2215   struct algorithm *alg_in, *best_alg;
2216   int cost;
2217   unsigned HOST_WIDE_INT q;
2218   int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
2219
2220   /* Indicate that no algorithm is yet found.  If no algorithm
2221      is found, this value will be returned and indicate failure.  */
2222   alg_out->cost = cost_limit;
2223
2224   if (cost_limit <= 0)
2225     return;
2226
2227   /* Restrict the bits of "t" to the multiplication's mode.  */
2228   t &= GET_MODE_MASK (mode);
2229
2230   /* t == 1 can be done in zero cost.  */
2231   if (t == 1)
2232     {
2233       alg_out->ops = 1;
2234       alg_out->cost = 0;
2235       alg_out->op[0] = alg_m;
2236       return;
2237     }
2238
2239   /* t == 0 sometimes has a cost.  If it does and it exceeds our limit,
2240      fail now.  */
2241   if (t == 0)
2242     {
2243       if (zero_cost >= cost_limit)
2244         return;
2245       else
2246         {
2247           alg_out->ops = 1;
2248           alg_out->cost = zero_cost;
2249           alg_out->op[0] = alg_zero;
2250           return;
2251         }
2252     }
2253
2254   /* We'll be needing a couple extra algorithm structures now.  */
2255
2256   alg_in = alloca (sizeof (struct algorithm));
2257   best_alg = alloca (sizeof (struct algorithm));
2258
2259   /* If we have a group of zero bits at the low-order part of T, try
2260      multiplying by the remaining bits and then doing a shift.  */
2261
2262   if ((t & 1) == 0)
2263     {
2264       m = floor_log2 (t & -t);  /* m = number of low zero bits */
2265       if (m < maxm)
2266         {
2267           q = t >> m;
2268           /* The function expand_shift will choose between a shift and
2269              a sequence of additions, so the observed cost is given as
2270              MIN (m * add_cost[mode], shift_cost[mode][m]).  */
2271           cost = m * add_cost[mode];
2272           if (shift_cost[mode][m] < cost)
2273             cost = shift_cost[mode][m];
2274           synth_mult (alg_in, q, cost_limit - cost, mode);
2275
2276           cost += alg_in->cost;
2277           if (cost < cost_limit)
2278             {
2279               struct algorithm *x;
2280               x = alg_in, alg_in = best_alg, best_alg = x;
2281               best_alg->log[best_alg->ops] = m;
2282               best_alg->op[best_alg->ops] = alg_shift;
2283               cost_limit = cost;
2284             }
2285         }
2286     }
2287
2288   /* If we have an odd number, add or subtract one.  */
2289   if ((t & 1) != 0)
2290     {
2291       unsigned HOST_WIDE_INT w;
2292
2293       for (w = 1; (w & t) != 0; w <<= 1)
2294         ;
2295       /* If T was -1, then W will be zero after the loop.  This is another
2296          case where T ends with ...111.  Handling this with (T + 1) and
2297          subtract 1 produces slightly better code and results in algorithm
2298          selection much faster than treating it like the ...0111 case
2299          below.  */
2300       if (w == 0
2301           || (w > 2
2302               /* Reject the case where t is 3.
2303                  Thus we prefer addition in that case.  */
2304               && t != 3))
2305         {
2306           /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */
2307
2308           cost = add_cost[mode];
2309           synth_mult (alg_in, t + 1, cost_limit - cost, mode);
2310
2311           cost += alg_in->cost;
2312           if (cost < cost_limit)
2313             {
2314               struct algorithm *x;
2315               x = alg_in, alg_in = best_alg, best_alg = x;
2316               best_alg->log[best_alg->ops] = 0;
2317               best_alg->op[best_alg->ops] = alg_sub_t_m2;
2318               cost_limit = cost;
2319             }
2320         }
2321       else
2322         {
2323           /* T ends with ...01 or ...011.  Multiply by (T - 1) and add 1.  */
2324
2325           cost = add_cost[mode];
2326           synth_mult (alg_in, t - 1, cost_limit - cost, mode);
2327
2328           cost += alg_in->cost;
2329           if (cost < cost_limit)
2330             {
2331               struct algorithm *x;
2332               x = alg_in, alg_in = best_alg, best_alg = x;
2333               best_alg->log[best_alg->ops] = 0;
2334               best_alg->op[best_alg->ops] = alg_add_t_m2;
2335               cost_limit = cost;
2336             }
2337         }
2338     }
2339
2340   /* Look for factors of t of the form
2341      t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2342      If we find such a factor, we can multiply by t using an algorithm that
2343      multiplies by q, shift the result by m and add/subtract it to itself.
2344
2345      We search for large factors first and loop down, even if large factors
2346      are less probable than small; if we find a large factor we will find a
2347      good sequence quickly, and therefore be able to prune (by decreasing
2348      COST_LIMIT) the search.  */
2349
2350   for (m = floor_log2 (t - 1); m >= 2; m--)
2351     {
2352       unsigned HOST_WIDE_INT d;
2353
2354       d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2355       if (t % d == 0 && t > d && m < maxm)
2356         {
2357           cost = add_cost[mode] + shift_cost[mode][m];
2358           if (shiftadd_cost[mode][m] < cost)
2359             cost = shiftadd_cost[mode][m];
2360           synth_mult (alg_in, t / d, cost_limit - cost, mode);
2361
2362           cost += alg_in->cost;
2363           if (cost < cost_limit)
2364             {
2365               struct algorithm *x;
2366               x = alg_in, alg_in = best_alg, best_alg = x;
2367               best_alg->log[best_alg->ops] = m;
2368               best_alg->op[best_alg->ops] = alg_add_factor;
2369               cost_limit = cost;
2370             }
2371           /* Other factors will have been taken care of in the recursion.  */
2372           break;
2373         }
2374
2375       d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2376       if (t % d == 0 && t > d && m < maxm)
2377         {
2378           cost = add_cost[mode] + shift_cost[mode][m];
2379           if (shiftsub_cost[mode][m] < cost)
2380             cost = shiftsub_cost[mode][m];
2381           synth_mult (alg_in, t / d, cost_limit - cost, mode);
2382
2383           cost += alg_in->cost;
2384           if (cost < cost_limit)
2385             {
2386               struct algorithm *x;
2387               x = alg_in, alg_in = best_alg, best_alg = x;
2388               best_alg->log[best_alg->ops] = m;
2389               best_alg->op[best_alg->ops] = alg_sub_factor;
2390               cost_limit = cost;
2391             }
2392           break;
2393         }
2394     }
2395
2396   /* Try shift-and-add (load effective address) instructions,
2397      i.e. do a*3, a*5, a*9.  */
2398   if ((t & 1) != 0)
2399     {
2400       q = t - 1;
2401       q = q & -q;
2402       m = exact_log2 (q);
2403       if (m >= 0 && m < maxm)
2404         {
2405           cost = shiftadd_cost[mode][m];
2406           synth_mult (alg_in, (t - 1) >> m, cost_limit - cost, mode);
2407
2408           cost += alg_in->cost;
2409           if (cost < cost_limit)
2410             {
2411               struct algorithm *x;
2412               x = alg_in, alg_in = best_alg, best_alg = x;
2413               best_alg->log[best_alg->ops] = m;
2414               best_alg->op[best_alg->ops] = alg_add_t2_m;
2415               cost_limit = cost;
2416             }
2417         }
2418
2419       q = t + 1;
2420       q = q & -q;
2421       m = exact_log2 (q);
2422       if (m >= 0 && m < maxm)
2423         {
2424           cost = shiftsub_cost[mode][m];
2425           synth_mult (alg_in, (t + 1) >> m, cost_limit - cost, mode);
2426
2427           cost += alg_in->cost;
2428           if (cost < cost_limit)
2429             {
2430               struct algorithm *x;
2431               x = alg_in, alg_in = best_alg, best_alg = x;
2432               best_alg->log[best_alg->ops] = m;
2433               best_alg->op[best_alg->ops] = alg_sub_t2_m;
2434               cost_limit = cost;
2435             }
2436         }
2437     }
2438
2439   /* If cost_limit has not decreased since we stored it in alg_out->cost,
2440      we have not found any algorithm.  */
2441   if (cost_limit == alg_out->cost)
2442     return;
2443
2444   /* If we are getting a too long sequence for `struct algorithm'
2445      to record, make this search fail.  */
2446   if (best_alg->ops == MAX_BITS_PER_WORD)
2447     return;
2448
2449   /* Copy the algorithm from temporary space to the space at alg_out.
2450      We avoid using structure assignment because the majority of
2451      best_alg is normally undefined, and this is a critical function.  */
2452   alg_out->ops = best_alg->ops + 1;
2453   alg_out->cost = cost_limit;
2454   memcpy (alg_out->op, best_alg->op,
2455           alg_out->ops * sizeof *alg_out->op);
2456   memcpy (alg_out->log, best_alg->log,
2457           alg_out->ops * sizeof *alg_out->log);
2458 }
2459 \f
2460 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2461    Try three variations:
2462
2463        - a shift/add sequence based on VAL itself
2464        - a shift/add sequence based on -VAL, followed by a negation
2465        - a shift/add sequence based on VAL - 1, followed by an addition.
2466
2467    Return true if the cheapest of these cost less than MULT_COST,
2468    describing the algorithm in *ALG and final fixup in *VARIANT.  */
2469
2470 static bool
2471 choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val,
2472                      struct algorithm *alg, enum mult_variant *variant,
2473                      int mult_cost)
2474 {
2475   struct algorithm alg2;
2476
2477   *variant = basic_variant;
2478   synth_mult (alg, val, mult_cost, mode);
2479
2480   /* This works only if the inverted value actually fits in an
2481      `unsigned int' */
2482   if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2483     {
2484       synth_mult (&alg2, -val, MIN (alg->cost, mult_cost) - neg_cost[mode],
2485                   mode);
2486       alg2.cost += neg_cost[mode];
2487       if (alg2.cost < alg->cost)
2488         *alg = alg2, *variant = negate_variant;
2489     }
2490
2491   /* This proves very useful for division-by-constant.  */
2492   synth_mult (&alg2, val - 1, MIN (alg->cost, mult_cost) - add_cost[mode],
2493               mode);
2494   alg2.cost += add_cost[mode];
2495   if (alg2.cost < alg->cost)
2496     *alg = alg2, *variant = add_variant;
2497
2498   return alg->cost < mult_cost;
2499 }
2500
2501 /* A subroutine of expand_mult, used for constant multiplications.
2502    Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2503    convenient.  Use the shift/add sequence described by ALG and apply
2504    the final fixup specified by VARIANT.  */
2505
2506 static rtx
2507 expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val,
2508                    rtx target, const struct algorithm *alg,
2509                    enum mult_variant variant)
2510 {
2511   HOST_WIDE_INT val_so_far;
2512   rtx insn, accum, tem;
2513   int opno;
2514   enum machine_mode nmode;
2515
2516   /* Avoid referencing memory over and over.
2517      For speed, but also for correctness when mem is volatile.  */
2518   if (MEM_P (op0))
2519     op0 = force_reg (mode, op0);
2520
2521   /* ACCUM starts out either as OP0 or as a zero, depending on
2522      the first operation.  */
2523
2524   if (alg->op[0] == alg_zero)
2525     {
2526       accum = copy_to_mode_reg (mode, const0_rtx);
2527       val_so_far = 0;
2528     }
2529   else if (alg->op[0] == alg_m)
2530     {
2531       accum = copy_to_mode_reg (mode, op0);
2532       val_so_far = 1;
2533     }
2534   else
2535     abort ();
2536
2537   for (opno = 1; opno < alg->ops; opno++)
2538     {
2539       int log = alg->log[opno];
2540       int preserve = preserve_subexpressions_p ();
2541       rtx shift_subtarget = preserve ? 0 : accum;
2542       rtx add_target
2543         = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2544            && ! preserve)
2545           ? target : 0;
2546       rtx accum_target = preserve ? 0 : accum;
2547
2548       switch (alg->op[opno])
2549         {
2550         case alg_shift:
2551           accum = expand_shift (LSHIFT_EXPR, mode, accum,
2552                                 build_int_2 (log, 0), NULL_RTX, 0);
2553           val_so_far <<= log;
2554           break;
2555
2556         case alg_add_t_m2:
2557           tem = expand_shift (LSHIFT_EXPR, mode, op0,
2558                               build_int_2 (log, 0), NULL_RTX, 0);
2559           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2560                                  add_target ? add_target : accum_target);
2561           val_so_far += (HOST_WIDE_INT) 1 << log;
2562           break;
2563
2564         case alg_sub_t_m2:
2565           tem = expand_shift (LSHIFT_EXPR, mode, op0,
2566                               build_int_2 (log, 0), NULL_RTX, 0);
2567           accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2568                                  add_target ? add_target : accum_target);
2569           val_so_far -= (HOST_WIDE_INT) 1 << log;
2570           break;
2571
2572         case alg_add_t2_m:
2573           accum = expand_shift (LSHIFT_EXPR, mode, accum,
2574                                 build_int_2 (log, 0), shift_subtarget,
2575                                 0);
2576           accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2577                                  add_target ? add_target : accum_target);
2578           val_so_far = (val_so_far << log) + 1;
2579           break;
2580
2581         case alg_sub_t2_m:
2582           accum = expand_shift (LSHIFT_EXPR, mode, accum,
2583                                 build_int_2 (log, 0), shift_subtarget, 0);
2584           accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2585                                  add_target ? add_target : accum_target);
2586           val_so_far = (val_so_far << log) - 1;
2587           break;
2588
2589         case alg_add_factor:
2590           tem = expand_shift (LSHIFT_EXPR, mode, accum,
2591                               build_int_2 (log, 0), NULL_RTX, 0);
2592           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2593                                  add_target ? add_target : accum_target);
2594           val_so_far += val_so_far << log;
2595           break;
2596
2597         case alg_sub_factor:
2598           tem = expand_shift (LSHIFT_EXPR, mode, accum,
2599                               build_int_2 (log, 0), NULL_RTX, 0);
2600           accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2601                                  (add_target ? add_target
2602                                   : preserve ? 0 : tem));
2603           val_so_far = (val_so_far << log) - val_so_far;
2604           break;
2605
2606         default:
2607           abort ();
2608         }
2609
2610       /* Write a REG_EQUAL note on the last insn so that we can cse
2611          multiplication sequences.  Note that if ACCUM is a SUBREG,
2612          we've set the inner register and must properly indicate
2613          that.  */
2614
2615       tem = op0, nmode = mode;
2616       if (GET_CODE (accum) == SUBREG)
2617         {
2618           nmode = GET_MODE (SUBREG_REG (accum));
2619           tem = gen_lowpart (nmode, op0);
2620         }
2621
2622       insn = get_last_insn ();
2623       set_unique_reg_note (insn, REG_EQUAL,
2624                            gen_rtx_MULT (nmode, tem, GEN_INT (val_so_far)));
2625     }
2626
2627   if (variant == negate_variant)
2628     {
2629       val_so_far = -val_so_far;
2630       accum = expand_unop (mode, neg_optab, accum, target, 0);
2631     }
2632   else if (variant == add_variant)
2633     {
2634       val_so_far = val_so_far + 1;
2635       accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2636     }
2637
2638   /* Compare only the bits of val and val_so_far that are significant
2639      in the result mode, to avoid sign-/zero-extension confusion.  */
2640   val &= GET_MODE_MASK (mode);
2641   val_so_far &= GET_MODE_MASK (mode);
2642   if (val != val_so_far)
2643     abort ();
2644
2645   return accum;
2646 }
2647
2648 /* Perform a multiplication and return an rtx for the result.
2649    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2650    TARGET is a suggestion for where to store the result (an rtx).
2651
2652    We check specially for a constant integer as OP1.
2653    If you want this check for OP0 as well, then before calling
2654    you should swap the two operands if OP0 would be constant.  */
2655
2656 rtx
2657 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
2658              int unsignedp)
2659 {
2660   rtx const_op1 = op1;
2661   enum mult_variant variant;
2662   struct algorithm algorithm;
2663
2664   /* synth_mult does an `unsigned int' multiply.  As long as the mode is
2665      less than or equal in size to `unsigned int' this doesn't matter.
2666      If the mode is larger than `unsigned int', then synth_mult works only
2667      if the constant value exactly fits in an `unsigned int' without any
2668      truncation.  This means that multiplying by negative values does
2669      not work; results are off by 2^32 on a 32 bit machine.  */
2670
2671   /* If we are multiplying in DImode, it may still be a win
2672      to try to work with shifts and adds.  */
2673   if (GET_CODE (op1) == CONST_DOUBLE
2674       && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2675       && HOST_BITS_PER_INT >= BITS_PER_WORD
2676       && CONST_DOUBLE_HIGH (op1) == 0)
2677     const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2678   else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2679            && GET_CODE (op1) == CONST_INT
2680            && INTVAL (op1) < 0)
2681     const_op1 = 0;
2682
2683   /* We used to test optimize here, on the grounds that it's better to
2684      produce a smaller program when -O is not used.
2685      But this causes such a terrible slowdown sometimes
2686      that it seems better to use synth_mult always.  */
2687
2688   if (const_op1 && GET_CODE (const_op1) == CONST_INT
2689       && (unsignedp || !flag_trapv))
2690     {
2691       int mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2692
2693       if (choose_mult_variant (mode, INTVAL (const_op1), &algorithm, &variant,
2694                                mult_cost))
2695         return expand_mult_const (mode, op0, INTVAL (const_op1), target,
2696                                   &algorithm, variant);
2697     }
2698
2699   if (GET_CODE (op0) == CONST_DOUBLE)
2700     {
2701       rtx temp = op0;
2702       op0 = op1;
2703       op1 = temp;
2704     }
2705
2706   /* Expand x*2.0 as x+x.  */
2707   if (GET_CODE (op1) == CONST_DOUBLE
2708       && GET_MODE_CLASS (mode) == MODE_FLOAT)
2709     {
2710       REAL_VALUE_TYPE d;
2711       REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
2712
2713       if (REAL_VALUES_EQUAL (d, dconst2))
2714         {
2715           op0 = force_reg (GET_MODE (op0), op0);
2716           return expand_binop (mode, add_optab, op0, op0,
2717                                target, unsignedp, OPTAB_LIB_WIDEN);
2718         }
2719     }
2720
2721   /* This used to use umul_optab if unsigned, but for non-widening multiply
2722      there is no difference between signed and unsigned.  */
2723   op0 = expand_binop (mode,
2724                       ! unsignedp
2725                       && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2726                       ? smulv_optab : smul_optab,
2727                       op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2728   if (op0 == 0)
2729     abort ();
2730   return op0;
2731 }
2732 \f
2733 /* Return the smallest n such that 2**n >= X.  */
2734
2735 int
2736 ceil_log2 (unsigned HOST_WIDE_INT x)
2737 {
2738   return floor_log2 (x - 1) + 1;
2739 }
2740
2741 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2742    replace division by D, and put the least significant N bits of the result
2743    in *MULTIPLIER_PTR and return the most significant bit.
2744
2745    The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2746    needed precision is in PRECISION (should be <= N).
2747
2748    PRECISION should be as small as possible so this function can choose
2749    multiplier more freely.
2750
2751    The rounded-up logarithm of D is placed in *lgup_ptr.  A shift count that
2752    is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2753
2754    Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2755    where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier.  */
2756
2757 static
2758 unsigned HOST_WIDE_INT
2759 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
2760                    unsigned HOST_WIDE_INT *multiplier_ptr,
2761                    int *post_shift_ptr, int *lgup_ptr)
2762 {
2763   HOST_WIDE_INT mhigh_hi, mlow_hi;
2764   unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2765   int lgup, post_shift;
2766   int pow, pow2;
2767   unsigned HOST_WIDE_INT nl, dummy1;
2768   HOST_WIDE_INT nh, dummy2;
2769
2770   /* lgup = ceil(log2(divisor)); */
2771   lgup = ceil_log2 (d);
2772
2773   if (lgup > n)
2774     abort ();
2775
2776   pow = n + lgup;
2777   pow2 = n + lgup - precision;
2778
2779   if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2780     {
2781       /* We could handle this with some effort, but this case is much better
2782          handled directly with a scc insn, so rely on caller using that.  */
2783       abort ();
2784     }
2785
2786   /* mlow = 2^(N + lgup)/d */
2787  if (pow >= HOST_BITS_PER_WIDE_INT)
2788     {
2789       nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2790       nl = 0;
2791     }
2792   else
2793     {
2794       nh = 0;
2795       nl = (unsigned HOST_WIDE_INT) 1 << pow;
2796     }
2797   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2798                         &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2799
2800   /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2801   if (pow2 >= HOST_BITS_PER_WIDE_INT)
2802     nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2803   else
2804     nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2805   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2806                         &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2807
2808   if (mhigh_hi && nh - d >= d)
2809     abort ();
2810   if (mhigh_hi > 1 || mlow_hi > 1)
2811     abort ();
2812   /* Assert that mlow < mhigh.  */
2813   if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2814     abort ();
2815
2816   /* If precision == N, then mlow, mhigh exceed 2^N
2817      (but they do not exceed 2^(N+1)).  */
2818
2819   /* Reduce to lowest terms.  */
2820   for (post_shift = lgup; post_shift > 0; post_shift--)
2821     {
2822       unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2823       unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2824       if (ml_lo >= mh_lo)
2825         break;
2826
2827       mlow_hi = 0;
2828       mlow_lo = ml_lo;
2829       mhigh_hi = 0;
2830       mhigh_lo = mh_lo;
2831     }
2832
2833   *post_shift_ptr = post_shift;
2834   *lgup_ptr = lgup;
2835   if (n < HOST_BITS_PER_WIDE_INT)
2836     {
2837       unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2838       *multiplier_ptr = mhigh_lo & mask;
2839       return mhigh_lo >= mask;
2840     }
2841   else
2842     {
2843       *multiplier_ptr = mhigh_lo;
2844       return mhigh_hi;
2845     }
2846 }
2847
2848 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2849    congruent to 1 (mod 2**N).  */
2850
2851 static unsigned HOST_WIDE_INT
2852 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
2853 {
2854   /* Solve x*y == 1 (mod 2^n), where x is odd.  Return y.  */
2855
2856   /* The algorithm notes that the choice y = x satisfies
2857      x*y == 1 mod 2^3, since x is assumed odd.
2858      Each iteration doubles the number of bits of significance in y.  */
2859
2860   unsigned HOST_WIDE_INT mask;
2861   unsigned HOST_WIDE_INT y = x;
2862   int nbit = 3;
2863
2864   mask = (n == HOST_BITS_PER_WIDE_INT
2865           ? ~(unsigned HOST_WIDE_INT) 0
2866           : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2867
2868   while (nbit < n)
2869     {
2870       y = y * (2 - x*y) & mask;         /* Modulo 2^N */
2871       nbit *= 2;
2872     }
2873   return y;
2874 }
2875
2876 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2877    flavor of OP0 and OP1.  ADJ_OPERAND is already the high half of the
2878    product OP0 x OP1.  If UNSIGNEDP is nonzero, adjust the signed product
2879    to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2880    become signed.
2881
2882    The result is put in TARGET if that is convenient.
2883
2884    MODE is the mode of operation.  */
2885
2886 rtx
2887 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
2888                              rtx op1, rtx target, int unsignedp)
2889 {
2890   rtx tem;
2891   enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2892
2893   tem = expand_shift (RSHIFT_EXPR, mode, op0,
2894                       build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2895                       NULL_RTX, 0);
2896   tem = expand_and (mode, tem, op1, NULL_RTX);
2897   adj_operand
2898     = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2899                      adj_operand);
2900
2901   tem = expand_shift (RSHIFT_EXPR, mode, op1,
2902                       build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2903                       NULL_RTX, 0);
2904   tem = expand_and (mode, tem, op0, NULL_RTX);
2905   target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2906                           target);
2907
2908   return target;
2909 }
2910
2911 /* Subroutine of expand_mult_highpart.  Return the MODE high part of OP.  */
2912
2913 static rtx
2914 extract_high_half (enum machine_mode mode, rtx op)
2915 {
2916   enum machine_mode wider_mode;
2917
2918   if (mode == word_mode)
2919     return gen_highpart (mode, op);
2920
2921   wider_mode = GET_MODE_WIDER_MODE (mode);
2922   op = expand_shift (RSHIFT_EXPR, wider_mode, op,
2923                      build_int_2 (GET_MODE_BITSIZE (mode), 0), 0, 1);
2924   return convert_modes (mode, wider_mode, op, 0);
2925 }
2926
2927 /* Like expand_mult_highpart, but only consider using a multiplication
2928    optab.  OP1 is an rtx for the constant operand.  */
2929
2930 static rtx
2931 expand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1,
2932                             rtx target, int unsignedp, int max_cost)
2933 {
2934   rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
2935   enum machine_mode wider_mode;
2936   optab moptab;
2937   rtx tem;
2938   int size;
2939
2940   wider_mode = GET_MODE_WIDER_MODE (mode);
2941   size = GET_MODE_BITSIZE (mode);
2942
2943   /* Firstly, try using a multiplication insn that only generates the needed
2944      high part of the product, and in the sign flavor of unsignedp.  */
2945   if (mul_highpart_cost[mode] < max_cost)
2946     {
2947       moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2948       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
2949                           unsignedp, OPTAB_DIRECT);
2950       if (tem)
2951         return tem;
2952     }
2953
2954   /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2955      Need to adjust the result after the multiplication.  */
2956   if (size - 1 < BITS_PER_WORD
2957       && (mul_highpart_cost[mode] + 2 * shift_cost[mode][size-1]
2958           + 4 * add_cost[mode] < max_cost))
2959     {
2960       moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2961       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
2962                           unsignedp, OPTAB_DIRECT);
2963       if (tem)
2964         /* We used the wrong signedness.  Adjust the result.  */
2965         return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
2966                                             tem, unsignedp);
2967     }
2968
2969   /* Try widening multiplication.  */
2970   moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2971   if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing
2972       && mul_widen_cost[wider_mode] < max_cost)
2973     {
2974       tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
2975                           unsignedp, OPTAB_WIDEN);
2976       if (tem)
2977         return extract_high_half (mode, tem);
2978     }
2979
2980   /* Try widening the mode and perform a non-widening multiplication.  */
2981   moptab = smul_optab;
2982   if (smul_optab->handlers[wider_mode].insn_code != CODE_FOR_nothing
2983       && size - 1 < BITS_PER_WORD
2984       && mul_cost[wider_mode] + shift_cost[mode][size-1] < max_cost)
2985     {
2986       tem = expand_binop (wider_mode, moptab, op0, op1, 0,
2987                           unsignedp, OPTAB_WIDEN);
2988       if (tem)
2989         return extract_high_half (mode, tem);
2990     }
2991
2992   /* Try widening multiplication of opposite signedness, and adjust.  */
2993   moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2994   if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing
2995       && size - 1 < BITS_PER_WORD
2996       && (mul_widen_cost[wider_mode] + 2 * shift_cost[mode][size-1]
2997           + 4 * add_cost[mode] < max_cost))
2998     {
2999       tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3000                           NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3001       if (tem != 0)
3002         {
3003           tem = extract_high_half (mode, tem);
3004           /* We used the wrong signedness.  Adjust the result.  */
3005           return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3006                                               target, unsignedp);
3007         }
3008     }
3009
3010   return 0;
3011 }
3012
3013 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
3014    in TARGET if that is convenient, and return where the result is.  If the
3015    operation can not be performed, 0 is returned.
3016
3017    MODE is the mode of operation and result.
3018
3019    UNSIGNEDP nonzero means unsigned multiply.
3020
3021    MAX_COST is the total allowed cost for the expanded RTL.  */
3022
3023 rtx
3024 expand_mult_highpart (enum machine_mode mode, rtx op0,
3025                       unsigned HOST_WIDE_INT cnst1, rtx target,
3026                       int unsignedp, int max_cost)
3027 {
3028   enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
3029   int extra_cost;
3030   bool sign_adjust = false;
3031   enum mult_variant variant;
3032   struct algorithm alg;
3033   rtx op1, tem;
3034
3035   /* We can't support modes wider than HOST_BITS_PER_INT.  */
3036   if (GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT)
3037     abort ();
3038
3039   op1 = gen_int_mode (cnst1, wider_mode);
3040   cnst1 &= GET_MODE_MASK (mode);
3041
3042   /* We can't optimize modes wider than BITS_PER_WORD.
3043      ??? We might be able to perform double-word arithmetic if
3044      mode == word_mode, however all the cost calculations in
3045      synth_mult etc. assume single-word operations.  */
3046   if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3047     return expand_mult_highpart_optab (mode, op0, op1, target,
3048                                        unsignedp, max_cost);
3049
3050   extra_cost = shift_cost[mode][GET_MODE_BITSIZE (mode) - 1];
3051
3052   /* Check whether we try to multiply by a negative constant.  */
3053   if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3054     {
3055       sign_adjust = true;
3056       extra_cost += add_cost[mode];
3057     }
3058
3059   /* See whether shift/add multiplication is cheap enough.  */
3060   if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3061                            max_cost - extra_cost))
3062     {
3063       /* See whether the specialized multiplication optabs are
3064          cheaper than the shift/add version.  */
3065       tem = expand_mult_highpart_optab (mode, op0, op1, target,
3066                                         unsignedp, alg.cost + extra_cost);
3067       if (tem)
3068         return tem;
3069
3070       tem = convert_to_mode (wider_mode, op0, unsignedp);
3071       tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3072       tem = extract_high_half (mode, tem);
3073
3074       /* Adjust result for signedness.  */
3075       if (sign_adjust)
3076         tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3077
3078       return tem;
3079     }
3080   return expand_mult_highpart_optab (mode, op0, op1, target,
3081                                      unsignedp, max_cost);
3082 }
3083
3084
3085 /* Expand signed modulus of OP0 by a power of two D in mode MODE.  */
3086
3087 static rtx
3088 expand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3089 {
3090   unsigned HOST_WIDE_INT mask;
3091   rtx result, temp, shift, label;
3092   int logd;
3093
3094   logd = floor_log2 (d);
3095   result = gen_reg_rtx (mode);
3096
3097   /* Avoid conditional branches when they're expensive.  */
3098   if (BRANCH_COST >= 2
3099       && !optimize_size)
3100     {
3101       rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3102                                       mode, 0, -1);
3103       if (signmask)
3104         {
3105           signmask = force_reg (mode, signmask);
3106           mask = ((HOST_WIDE_INT) 1 << logd) - 1;
3107           shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd);
3108
3109           /* Use the rtx_cost of a LSHIFTRT instruction to determine
3110              which instruction sequence to use.  If logical right shifts
3111              are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3112              use a LSHIFTRT, 1 ADD, 1 SUB and an AND.  */
3113
3114           temp = gen_rtx_LSHIFTRT (mode, result, shift);
3115           if (lshr_optab->handlers[mode].insn_code == CODE_FOR_nothing
3116               || rtx_cost (temp, SET) > COSTS_N_INSNS (2))
3117             {
3118               temp = expand_binop (mode, xor_optab, op0, signmask,
3119                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3120               temp = expand_binop (mode, sub_optab, temp, signmask,
3121                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3122               temp = expand_binop (mode, and_optab, temp, GEN_INT (mask),
3123                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3124               temp = expand_binop (mode, xor_optab, temp, signmask,
3125                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3126               temp = expand_binop (mode, sub_optab, temp, signmask,
3127                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3128             }
3129           else
3130             {
3131               signmask = expand_binop (mode, lshr_optab, signmask, shift,
3132                                        NULL_RTX, 1, OPTAB_LIB_WIDEN);
3133               signmask = force_reg (mode, signmask);
3134
3135               temp = expand_binop (mode, add_optab, op0, signmask,
3136                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3137               temp = expand_binop (mode, and_optab, temp, GEN_INT (mask),
3138                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3139               temp = expand_binop (mode, sub_optab, temp, signmask,
3140                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3141             }
3142           return temp;
3143         }
3144     }
3145
3146   /* Mask contains the mode's signbit and the significant bits of the
3147      modulus.  By including the signbit in the operation, many targets
3148      can avoid an explicit compare operation in the following comparison
3149      against zero.  */
3150
3151   mask = (HOST_WIDE_INT) -1 << (GET_MODE_BITSIZE (mode) - 1)
3152          | (((HOST_WIDE_INT) 1 << logd) - 1);
3153
3154   temp = expand_binop (mode, and_optab, op0, GEN_INT (mask), result,
3155                        1, OPTAB_LIB_WIDEN);
3156   if (temp != result)
3157     emit_move_insn (result, temp);
3158
3159   label = gen_label_rtx ();
3160   do_cmp_and_jump (result, const0_rtx, GE, mode, label);
3161
3162   temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
3163                        0, OPTAB_LIB_WIDEN);
3164   mask = (HOST_WIDE_INT) -1 << logd;
3165   temp = expand_binop (mode, ior_optab, temp, GEN_INT (mask), result,
3166                        1, OPTAB_LIB_WIDEN);
3167   temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
3168                        0, OPTAB_LIB_WIDEN);
3169   if (temp != result)
3170     emit_move_insn (result, temp);
3171   emit_label (label);
3172   return result;
3173 }
3174 \f
3175 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3176    if that is convenient, and returning where the result is.
3177    You may request either the quotient or the remainder as the result;
3178    specify REM_FLAG nonzero to get the remainder.
3179
3180    CODE is the expression code for which kind of division this is;
3181    it controls how rounding is done.  MODE is the machine mode to use.
3182    UNSIGNEDP nonzero means do unsigned division.  */
3183
3184 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3185    and then correct it by or'ing in missing high bits
3186    if result of ANDI is nonzero.
3187    For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3188    This could optimize to a bfexts instruction.
3189    But C doesn't use these operations, so their optimizations are
3190    left for later.  */
3191 /* ??? For modulo, we don't actually need the highpart of the first product,
3192    the low part will do nicely.  And for small divisors, the second multiply
3193    can also be a low-part only multiply or even be completely left out.
3194    E.g. to calculate the remainder of a division by 3 with a 32 bit
3195    multiply, multiply with 0x55555556 and extract the upper two bits;
3196    the result is exact for inputs up to 0x1fffffff.
3197    The input range can be reduced by using cross-sum rules.
3198    For odd divisors >= 3, the following table gives right shift counts
3199    so that if a number is shifted by an integer multiple of the given
3200    amount, the remainder stays the same:
3201    2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3202    14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3203    0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3204    20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3205    0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3206
3207    Cross-sum rules for even numbers can be derived by leaving as many bits
3208    to the right alone as the divisor has zeros to the right.
3209    E.g. if x is an unsigned 32 bit number:
3210    (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3211    */
3212
3213 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
3214
3215 rtx
3216 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3217                rtx op0, rtx op1, rtx target, int unsignedp)
3218 {
3219   enum machine_mode compute_mode;
3220   rtx tquotient;
3221   rtx quotient = 0, remainder = 0;
3222   rtx last;
3223   int size;
3224   rtx insn, set;
3225   optab optab1, optab2;
3226   int op1_is_constant, op1_is_pow2 = 0;
3227   int max_cost, extra_cost;
3228   static HOST_WIDE_INT last_div_const = 0;
3229   static HOST_WIDE_INT ext_op1;
3230
3231   op1_is_constant = GET_CODE (op1) == CONST_INT;
3232   if (op1_is_constant)
3233     {
3234       ext_op1 = INTVAL (op1);
3235       if (unsignedp)
3236         ext_op1 &= GET_MODE_MASK (mode);
3237       op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3238                      || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3239     }
3240
3241   /*
3242      This is the structure of expand_divmod:
3243
3244      First comes code to fix up the operands so we can perform the operations
3245      correctly and efficiently.
3246
3247      Second comes a switch statement with code specific for each rounding mode.
3248      For some special operands this code emits all RTL for the desired
3249      operation, for other cases, it generates only a quotient and stores it in
3250      QUOTIENT.  The case for trunc division/remainder might leave quotient = 0,
3251      to indicate that it has not done anything.
3252
3253      Last comes code that finishes the operation.  If QUOTIENT is set and
3254      REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1.  If
3255      QUOTIENT is not set, it is computed using trunc rounding.
3256
3257      We try to generate special code for division and remainder when OP1 is a
3258      constant.  If |OP1| = 2**n we can use shifts and some other fast
3259      operations.  For other values of OP1, we compute a carefully selected
3260      fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3261      by m.
3262
3263      In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3264      half of the product.  Different strategies for generating the product are
3265      implemented in expand_mult_highpart.
3266
3267      If what we actually want is the remainder, we generate that by another
3268      by-constant multiplication and a subtraction.  */
3269
3270   /* We shouldn't be called with OP1 == const1_rtx, but some of the
3271      code below will malfunction if we are, so check here and handle
3272      the special case if so.  */
3273   if (op1 == const1_rtx)
3274     return rem_flag ? const0_rtx : op0;
3275
3276     /* When dividing by -1, we could get an overflow.
3277      negv_optab can handle overflows.  */
3278   if (! unsignedp && op1 == constm1_rtx)
3279     {
3280       if (rem_flag)
3281         return const0_rtx;
3282       return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3283                           ? negv_optab : neg_optab, op0, target, 0);
3284     }
3285
3286   if (target
3287       /* Don't use the function value register as a target
3288          since we have to read it as well as write it,
3289          and function-inlining gets confused by this.  */
3290       && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3291           /* Don't clobber an operand while doing a multi-step calculation.  */
3292           || ((rem_flag || op1_is_constant)
3293               && (reg_mentioned_p (target, op0)
3294                   || (MEM_P (op0) && MEM_P (target))))
3295           || reg_mentioned_p (target, op1)
3296           || (MEM_P (op1) && MEM_P (target))))
3297     target = 0;
3298
3299   /* Get the mode in which to perform this computation.  Normally it will
3300      be MODE, but sometimes we can't do the desired operation in MODE.
3301      If so, pick a wider mode in which we can do the operation.  Convert
3302      to that mode at the start to avoid repeated conversions.
3303
3304      First see what operations we need.  These depend on the expression
3305      we are evaluating.  (We assume that divxx3 insns exist under the
3306      same conditions that modxx3 insns and that these insns don't normally
3307      fail.  If these assumptions are not correct, we may generate less
3308      efficient code in some cases.)
3309
3310      Then see if we find a mode in which we can open-code that operation
3311      (either a division, modulus, or shift).  Finally, check for the smallest
3312      mode for which we can do the operation with a library call.  */
3313
3314   /* We might want to refine this now that we have division-by-constant
3315      optimization.  Since expand_mult_highpart tries so many variants, it is
3316      not straightforward to generalize this.  Maybe we should make an array
3317      of possible modes in init_expmed?  Save this for GCC 2.7.  */
3318
3319   optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3320             ? (unsignedp ? lshr_optab : ashr_optab)
3321             : (unsignedp ? udiv_optab : sdiv_optab));
3322   optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3323             ? optab1
3324             : (unsignedp ? udivmod_optab : sdivmod_optab));
3325
3326   for (compute_mode = mode; compute_mode != VOIDmode;
3327        compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3328     if (optab1->handlers[compute_mode].insn_code != CODE_FOR_nothing
3329         || optab2->handlers[compute_mode].insn_code != CODE_FOR_nothing)
3330       break;
3331
3332   if (compute_mode == VOIDmode)
3333     for (compute_mode = mode; compute_mode != VOIDmode;
3334          compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3335       if (optab1->handlers[compute_mode].libfunc
3336           || optab2->handlers[compute_mode].libfunc)
3337         break;
3338
3339   /* If we still couldn't find a mode, use MODE, but we'll probably abort
3340      in expand_binop.  */
3341   if (compute_mode == VOIDmode)
3342     compute_mode = mode;
3343
3344   if (target && GET_MODE (target) == compute_mode)
3345     tquotient = target;
3346   else
3347     tquotient = gen_reg_rtx (compute_mode);
3348
3349   size = GET_MODE_BITSIZE (compute_mode);
3350 #if 0
3351   /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3352      (mode), and thereby get better code when OP1 is a constant.  Do that
3353      later.  It will require going over all usages of SIZE below.  */
3354   size = GET_MODE_BITSIZE (mode);
3355 #endif
3356
3357   /* Only deduct something for a REM if the last divide done was
3358      for a different constant.   Then set the constant of the last
3359      divide.  */
3360   max_cost = div_cost[compute_mode]
3361     - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3362                       && INTVAL (op1) == last_div_const)
3363        ? mul_cost[compute_mode] + add_cost[compute_mode]
3364        : 0);
3365
3366   last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3367
3368   /* Now convert to the best mode to use.  */
3369   if (compute_mode != mode)
3370     {
3371       op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3372       op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3373
3374       /* convert_modes may have placed op1 into a register, so we
3375          must recompute the following.  */
3376       op1_is_constant = GET_CODE (op1) == CONST_INT;
3377       op1_is_pow2 = (op1_is_constant
3378                      && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3379                           || (! unsignedp
3380                               && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3381     }
3382</