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 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21
  22 #include "config.h"
  23 #include "rtl.h"
  24 #include "tree.h"
  25 #include "flags.h"
  26 #include "insn-flags.h"
  27 #include "insn-codes.h"
  28 #include "insn-config.h"
  29 #include "expr.h"
  30 #include "real.h"
  31 #include "recog.h"
  32
  33 static rtx extract_split_bit_field ();
  34 static rtx extract_fixed_bit_field ();
  35 static void store_split_bit_field ();
  36 static void store_fixed_bit_field ();
  37 static rtx mask_rtx ();
  38 static rtx lshift_value ();
  39
  40 #define CEIL(x,y) (((x) + (y) - 1) / (y))
  41
  42 /* Non-zero means multiply instructions are cheaper than shifts.  */
  43 int mult_is_very_cheap;
  44
  45 /* Non-zero means divides or modulus operations are relatively cheap for
  46    powers of two, so don't use branches; emit the operation instead.
  47    Usually, this will mean that the MD file will emit non-branch
  48    sequences.  */
  49
  50 static int sdiv_pow2_cheap, smod_pow2_cheap;
  51
  52 /* Cost of various pieces of RTL.  */
  53 static int add_cost, shift_cost, mult_cost, negate_cost, lea_cost;
  54
  55 /* Max scale factor for scaled address in lea instruction.  */
  56 static int lea_max_mul;
  57
  58 void
  59 init_expmed ()
  60 {
  61   char *free_point = (char *) oballoc (1);
  62   /* This is "some random pseudo register" for purposes of calling recog
  63      to see what insns exist.  */
  64   rtx reg = gen_rtx (REG, word_mode, FIRST_PSEUDO_REGISTER);
  65   rtx pow2 = gen_rtx (CONST_INT, VOIDmode, 32);
  66   rtx lea;
  67   int i, dummy;
  68
  69   add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg));
  70   shift_cost = rtx_cost (gen_rtx (LSHIFT, word_mode, reg,
  71                                   /* Using a constant gives better
  72                                      estimate of typical costs.
  73                                      1 or 2 might have quirks.  */
  74                                   gen_rtx (CONST_INT, VOIDmode, 3)));
  75   mult_cost = rtx_cost (gen_rtx (MULT, word_mode, reg, reg));
  76   negate_cost = rtx_cost (gen_rtx (NEG, word_mode, reg));
  77
  78   /* 999999 is chosen to avoid any plausible faster special case.  */
  79   mult_is_very_cheap
  80     = (rtx_cost (gen_rtx (MULT, word_mode, reg,
  81                           gen_rtx (CONST_INT, VOIDmode, 999999)))
  82        < rtx_cost (gen_rtx (LSHIFT, word_mode, reg,
  83                             gen_rtx (CONST_INT, VOIDmode, 7))));
  84
  85   sdiv_pow2_cheap
  86     = rtx_cost (gen_rtx (DIV, word_mode, reg, pow2)) <= 2 * add_cost;
  87   smod_pow2_cheap
  88     = rtx_cost (gen_rtx (MOD, word_mode, reg, pow2)) <= 2 * add_cost;
  89
  90   init_recog ();
  91   for (i = 2;; i <<= 1)
  92     {
  93       lea = gen_rtx (SET, VOIDmode, reg,
  94                      gen_rtx (PLUS, word_mode,
  95                               gen_rtx (MULT, word_mode, reg,
  96                                        gen_rtx (CONST_INT, VOIDmode, i)),
  97                               reg));
  98       /* Using 0 as second argument is not quite right,
  99          but what else is there to do?  */
 100       if (recog (lea, 0, &dummy) < 0)
 101         break;
 102       lea_max_mul = i;
 103       lea_cost = rtx_cost (SET_SRC (lea));
 104     }
 105
 106   /* Free the objects we just allocated.  */
 107   obfree (free_point);
 108 }
 109
 110 /* Return an rtx representing minus the value of X.
 111    MODE is the intended mode of the result,
 112    useful if X is a CONST_INT.  */
 113
 114 rtx
 115 negate_rtx (mode, x)
 116      enum machine_mode mode;
 117      rtx x;
 118 {
 119   if (GET_CODE (x) == CONST_INT)
 120     {
 121       int val = - INTVAL (x);
 122       if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_INT)
 123         {
 124           /* Sign extend the value from the bits that are significant.  */
 125           if (val & (1 << (GET_MODE_BITSIZE (mode) - 1)))
 126             val |= (-1) << GET_MODE_BITSIZE (mode);
 127           else
 128             val &= (1 << GET_MODE_BITSIZE (mode)) - 1;
 129         }
 130       return gen_rtx (CONST_INT, VOIDmode, val);
 131     }
 132   else
 133     return expand_unop (GET_MODE (x), neg_optab, x, 0, 0);
 134 }
 135 \f
 136 /* Generate code to store value from rtx VALUE
 137    into a bit-field within structure STR_RTX
 138    containing BITSIZE bits starting at bit BITNUM.
 139    FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
 140    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
 141    TOTAL_SIZE is the size of the structure in bytes, or -1 if varying.  */
 142
 143 /* ??? Note that there are two different ideas here for how
 144    to determine the size to count bits within, for a register.
 145    One is BITS_PER_WORD, and the other is the size of operand 3
 146    of the insv pattern.  (The latter assumes that an n-bit machine
 147    will be able to insert bit fields up to n bits wide.)
 148    It isn't certain that either of these is right.
 149    extract_bit_field has the same quandary.  */
 150
 151 rtx
 152 store_bit_field (str_rtx, bitsize, bitnum, fieldmode, value, align, total_size)
 153      rtx str_rtx;
 154      register int bitsize;
 155      int bitnum;
 156      enum machine_mode fieldmode;
 157      rtx value;
 158      int align;
 159      int total_size;
 160 {
 161   int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
 162   register int offset = bitnum / unit;
 163   register int bitpos = bitnum % unit;
 164   register rtx op0 = str_rtx;
 165
 166   if (GET_CODE (str_rtx) == MEM && ! MEM_IN_STRUCT_P (str_rtx))
 167     abort ();
 168
 169   /* Discount the part of the structure before the desired byte.
 170      We need to know how many bytes are safe to reference after it.  */
 171   if (total_size >= 0)
 172     total_size -= (bitpos / BIGGEST_ALIGNMENT
 173                    * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
 174
 175   while (GET_CODE (op0) == SUBREG)
 176     {
 177       /* The following line once was done only if WORDS_BIG_ENDIAN,
 178          but I think that is a mistake.  WORDS_BIG_ENDIAN is
 179          meaningful at a much higher level; when structures are copied
 180          between memory and regs, the higher-numbered regs
 181          always get higher addresses.  */
 182       offset += SUBREG_WORD (op0);
 183       /* We used to adjust BITPOS here, but now we do the whole adjustment
 184          right after the loop.  */
 185       op0 = SUBREG_REG (op0);
 186     }
 187
 188 #if BYTES_BIG_ENDIAN
 189   /* If OP0 is a register, BITPOS must count within a word.
 190      But as we have it, it counts within whatever size OP0 now has.
 191      On a bigendian machine, these are not the same, so convert.  */
 192   if (GET_CODE (op0) != MEM && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
 193     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
 194 #endif
 195
 196   value = protect_from_queue (value, 0);
 197
 198   if (flag_force_mem)
 199     value = force_not_mem (value);
 200
 201   /* Note that the adjustment of BITPOS above has no effect on whether
 202      BITPOS is 0 in a REG bigger than a word.  */
 203   if (GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD && GET_CODE (op0) != MEM
 204       && bitpos == 0 && bitsize == GET_MODE_BITSIZE (fieldmode))
 205     {
 206       /* Storing in a full-word or multi-word field in a register
 207          can be done with just SUBREG.  */
 208       if (GET_MODE (op0) != fieldmode)
 209         op0 = gen_rtx (SUBREG, fieldmode, op0, offset);
 210       emit_move_insn (op0, value);
 211       return value;
 212     }
 213
 214   /* Storing an lsb-aligned field in a register
 215      can be done with a movestrict instruction.  */
 216
 217   if (GET_CODE (op0) != MEM
 218 #if BYTES_BIG_ENDIAN
 219       && bitpos + bitsize == unit
 220 #else
 221       && bitpos == 0
 222 #endif
 223       && bitsize == GET_MODE_BITSIZE (fieldmode)
 224       && (GET_MODE (op0) == fieldmode
 225           || (movstrict_optab->handlers[(int) fieldmode].insn_code
 226               != CODE_FOR_nothing)))
 227     {
 228       /* Get appropriate low part of the value being stored.  */
 229       if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
 230         value = gen_lowpart (fieldmode, value);
 231       else if (!(GET_CODE (value) == SYMBOL_REF
 232                  || GET_CODE (value) == LABEL_REF
 233                  || GET_CODE (value) == CONST))
 234         value = convert_to_mode (fieldmode, value, 0);
 235
 236       if (GET_MODE (op0) == fieldmode)
 237         emit_move_insn (op0, value);
 238       else
 239         {
 240           int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
 241           if(! (*insn_operand_predicate[icode][1]) (value, fieldmode))
 242             value = copy_to_mode_reg (fieldmode, value);
 243           emit_insn (GEN_FCN (icode)
 244                    (gen_rtx (SUBREG, fieldmode, op0, offset), value));
 245         }
 246       return value;
 247     }
 248
 249   /* Handle fields bigger than a word.  */
 250
 251   if (bitsize > BITS_PER_WORD)
 252     {
 253       /* Here we transfer the words of the field
 254          in the order least significant first.
 255          This is because the most significant word is the one which may
 256          be less than full.  */
 257
 258       int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
 259       int i;
 260
 261       /* This is the mode we must force value to, so that there will be enough
 262          subwords to extract.  Note that fieldmode will often (always?) be
 263          VOIDmode, because that is what store_field uses to indicate that this
 264          is a bit field, but passing VOIDmode to operand_subword_force will
 265          result in an abort.  */
 266       fieldmode = mode_for_size (nwords * BITS_PER_WORD, MODE_INT, 0);
 267
 268       for (i = 0; i < nwords; i++)
 269         {
 270           /* If I is 0, use the low-order word in both field and target;
 271              if I is 1, use the next to lowest word; and so on.  */
 272           int wordnum = (WORDS_BIG_ENDIAN ? nwords - i - 1 : i);
 273           int bit_offset = (WORDS_BIG_ENDIAN
 274                             ? MAX (bitsize - (i + 1) * BITS_PER_WORD, 0)
 275                             : i * BITS_PER_WORD);
 276           store_bit_field (op0, MIN (BITS_PER_WORD,
 277                                      bitsize - i * BITS_PER_WORD),
 278                            bitnum + bit_offset, word_mode,
 279                            operand_subword_force (value, wordnum, fieldmode),
 280                            align, total_size);
 281         }
 282       return value;
 283     }
 284
 285   /* From here on we can assume that the field to be stored in is
 286      a full-word (whatever type that is), since it is shorter than a word.  */
 287
 288   /* OFFSET is the number of words or bytes (UNIT says which)
 289      from STR_RTX to the first word or byte containing part of the field.  */
 290
 291   if (GET_CODE (op0) == REG)
 292     {
 293       if (offset != 0
 294           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
 295         op0 = gen_rtx (SUBREG, TYPE_MODE (type_for_size (BITS_PER_WORD, 0)),
 296                        op0, offset);
 297       offset = 0;
 298     }
 299   else
 300     {
 301       op0 = protect_from_queue (op0, 1);
 302     }
 303
 304   /* Now OFFSET is nonzero only if OP0 is memory
 305      and is therefore always measured in bytes.  */
 306
 307 #ifdef HAVE_insv
 308   if (HAVE_insv
 309       && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
 310       /* Ensure insv's size is wide enough for this field.  */
 311       && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_insv][3])
 312           >= bitsize))
 313     {
 314       int xbitpos = bitpos;
 315       rtx value1;
 316       rtx xop0 = op0;
 317       rtx last = get_last_insn ();
 318       rtx pat;
 319       enum machine_mode maxmode
 320         = insn_operand_mode[(int) CODE_FOR_insv][3];
 321
 322       int save_volatile_ok = volatile_ok;
 323       volatile_ok = 1;
 324
 325       /* If this machine's insv can only insert into a register, or if we
 326          are to force MEMs into a register, copy OP0 into a register and
 327          save it back later.  */
 328       if (GET_CODE (op0) == MEM
 329           && (flag_force_mem
 330               || ! ((*insn_operand_predicate[(int) CODE_FOR_insv][0])
 331                     (op0, VOIDmode))))
 332         {
 333           rtx tempreg;
 334           enum machine_mode bestmode;
 335
 336           /* Get the mode to use for inserting into this field.  If OP0 is
 337              BLKmode, get the smallest mode consistent with the alignment. If
 338              OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
 339              mode. Otherwise, use the smallest mode containing the field.  */
 340
 341           if (GET_MODE (op0) == BLKmode
 342               || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
 343             bestmode
 344               = get_best_mode (bitsize, bitnum,
 345                                align * BITS_PER_UNIT, maxmode,
 346                                GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
 347           else
 348             bestmode = GET_MODE (op0);
 349
 350           if (bestmode == VOIDmode)
 351             goto insv_loses;
 352
 353           /* Adjust address to point to the containing unit of that mode.  */
 354           unit = GET_MODE_BITSIZE (bestmode);
 355           /* Compute offset as multiple of this unit, counting in bytes.  */
 356           offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
 357           bitpos = bitnum % unit;
 358           op0 = change_address (op0, bestmode,
 359                                 plus_constant (XEXP (op0, 0), offset));
 360
 361           /* Fetch that unit, store the bitfield in it, then store the unit.  */
 362           tempreg = copy_to_reg (op0);
 363           store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
 364                            align, total_size);
 365           emit_move_insn (op0, tempreg);
 366           return value;
 367         }
 368       volatile_ok = save_volatile_ok;
 369
 370       /* Add OFFSET into OP0's address.  */
 371       if (GET_CODE (xop0) == MEM)
 372         xop0 = change_address (xop0, byte_mode,
 373                                plus_constant (XEXP (xop0, 0), offset));
 374
 375       /* If xop0 is a register, we need it in MAXMODE
 376          to make it acceptable to the format of insv.  */
 377       if (GET_CODE (xop0) == SUBREG)
 378         PUT_MODE (xop0, maxmode);
 379       if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
 380         xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
 381
 382       /* On big-endian machines, we count bits from the most significant.
 383          If the bit field insn does not, we must invert.  */
 384
 385 #if BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN
 386       xbitpos = unit - bitsize - xbitpos;
 387 #endif
 388       /* We have been counting XBITPOS within UNIT.
 389          Count instead within the size of the register.  */
 390 #if BITS_BIG_ENDIAN
 391       if (GET_CODE (xop0) != MEM)
 392         xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
 393 #endif
 394       unit = GET_MODE_BITSIZE (maxmode);
 395
 396       /* Convert VALUE to maxmode (which insv insn wants) in VALUE1.  */
 397       value1 = value;
 398       if (GET_MODE (value) != maxmode)
 399         {
 400           if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
 401             {
 402               /* Optimization: Don't bother really extending VALUE
 403                  if it has all the bits we will actually use.  */
 404
 405               /* Avoid making subreg of a subreg, or of a mem.  */
 406               if (GET_CODE (value1) != REG)
 407                 value1 = copy_to_reg (value1);
 408               value1 = gen_rtx (SUBREG, maxmode, value1, 0);
 409             }
 410           else if (!CONSTANT_P (value))
 411             /* Parse phase is supposed to make VALUE's data type
 412                match that of the component reference, which is a type
 413                at least as wide as the field; so VALUE should have
 414                a mode that corresponds to that type.  */
 415             abort ();
 416         }
 417
 418       /* If this machine's insv insists on a register,
 419          get VALUE1 into a register.  */
 420       if (! ((*insn_operand_predicate[(int) CODE_FOR_insv][3])
 421              (value1, maxmode)))
 422         value1 = force_reg (maxmode, value1);
 423
 424       pat = gen_insv (xop0,
 425                       gen_rtx (CONST_INT, VOIDmode, bitsize),
 426                       gen_rtx (CONST_INT, VOIDmode, xbitpos),
 427                       value1);
 428       if (pat)
 429         emit_insn (pat);
 430       else
 431         {
 432           delete_insns_since (last);
 433           store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
 434         }
 435     }
 436   else
 437     insv_loses:
 438 #endif
 439     /* Insv is not available; store using shifts and boolean ops.  */
 440     store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
 441   return value;
 442 }
 443 \f
 444 /* Use shifts and boolean operations to store VALUE
 445    into a bit field of width BITSIZE
 446    in a memory location specified by OP0 except offset by OFFSET bytes.
 447      (OFFSET must be 0 if OP0 is a register.)
 448    The field starts at position BITPOS within the byte.
 449     (If OP0 is a register, it may be a full word or a narrower mode,
 450      but BITPOS still counts within a full word,
 451      which is significant on bigendian machines.)
 452    STRUCT_ALIGN is the alignment the structure is known to have (in bytes).
 453
 454    Note that protect_from_queue has already been done on OP0 and VALUE.  */
 455
 456 static void
 457 store_fixed_bit_field (op0, offset, bitsize, bitpos, value, struct_align)
 458      register rtx op0;
 459      register int offset, bitsize, bitpos;
 460      register rtx value;
 461      int struct_align;
 462 {
 463   register enum machine_mode mode;
 464   int total_bits = BITS_PER_WORD;
 465   rtx subtarget, temp;
 466   int all_zero = 0;
 467   int all_one = 0;
 468
 469   /* Add OFFSET to OP0's address (if it is in memory)
 470      and if a single byte contains the whole bit field
 471      change OP0 to a byte.  */
 472
 473   /* There is a case not handled here:
 474      a structure with a known alignment of just a halfword
 475      and a field split across two aligned halfwords within the structure.
 476      Or likewise a structure with a known alignment of just a byte
 477      and a field split across two bytes.
 478      Such cases are not supposed to be able to occur.  */
 479
 480   if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
 481     {
 482       if (offset != 0)
 483         abort ();
 484       /* Special treatment for a bit field split across two registers.  */
 485       if (bitsize + bitpos > BITS_PER_WORD)
 486         {
 487           store_split_bit_field (op0, bitsize, bitpos, value, BITS_PER_WORD);
 488           return;
 489         }
 490     }
 491   else
 492     {
 493       /* Get the proper mode to use for this field.  We want a mode that
 494          includes the entire field.  If such a mode would be larger than
 495          a word, we won't be doing the extraction the normal way.  */
 496
 497       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
 498                             struct_align * BITS_PER_UNIT, word_mode,
 499                             GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
 500
 501       if (mode == VOIDmode)
 502         {
 503           /* The only way this should occur is if the field spans word
 504              boundaries.  */
 505           store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
 506                                  value, struct_align);
 507           return;
 508         }
 509
 510       total_bits = GET_MODE_BITSIZE (mode);
 511
 512       /* Get ref to an aligned byte, halfword, or word containing the field.
 513          Adjust BITPOS to be position within a word,
 514          and OFFSET to be the offset of that word.
 515          Then alter OP0 to refer to that word.  */
 516       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
 517       offset -= (offset % (total_bits / BITS_PER_UNIT));
 518       op0 = change_address (op0, mode,
 519                             plus_constant (XEXP (op0, 0), offset));
 520     }
 521
 522   mode = GET_MODE (op0);
 523
 524   /* Now MODE is either some integral mode for a MEM as OP0,
 525      or is a full-word for a REG as OP0.  TOTAL_BITS corresponds.
 526      The bit field is contained entirely within OP0.
 527      BITPOS is the starting bit number within OP0.
 528      (OP0's mode may actually be narrower than MODE.)  */
 529
 530 #if BYTES_BIG_ENDIAN
 531   /* BITPOS is the distance between our msb
 532      and that of the containing datum.
 533      Convert it to the distance from the lsb.  */
 534
 535   bitpos = total_bits - bitsize - bitpos;
 536 #endif
 537   /* Now BITPOS is always the distance between our lsb
 538      and that of OP0.  */
 539
 540   /* Shift VALUE left by BITPOS bits.  If VALUE is not constant,
 541      we must first convert its mode to MODE.  */
 542
 543   if (GET_CODE (value) == CONST_INT)
 544     {
 545       register int v = INTVAL (value);
 546
 547       if (bitsize < HOST_BITS_PER_INT)
 548         v &= (1 << bitsize) - 1;
 549
 550       if (v == 0)
 551         all_zero = 1;
 552       else if ((bitsize < HOST_BITS_PER_INT && v == (1 << bitsize) - 1)
 553                || (bitsize == HOST_BITS_PER_INT && v == -1))
 554         all_one = 1;
 555
 556       value = lshift_value (mode, value, bitpos, bitsize);
 557     }
 558   else
 559     {
 560       int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
 561                       && bitpos + bitsize != GET_MODE_BITSIZE (mode));
 562
 563       if (GET_MODE (value) != mode)
 564         {
 565           /* If VALUE is a floating-point mode, access it as an integer
 566              of the corresponding size, then convert it.  This can occur on
 567              a machine with 64 bit registers that uses SFmode for float.  */
 568           if (GET_MODE_CLASS (GET_MODE (value)) == MODE_FLOAT)
 569             {
 570               if (GET_CODE (value) != REG)
 571                 value = copy_to_reg (value);
 572               value
 573                 = gen_rtx (SUBREG, word_mode, value, 0);
 574             }
 575
 576           if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
 577               && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
 578             value = gen_lowpart (mode, value);
 579           else
 580             value = convert_to_mode (mode, value, 1);
 581         }
 582
 583       if (must_and)
 584         value = expand_binop (mode, and_optab, value,
 585                               mask_rtx (mode, 0, bitsize, 0),
 586                               0, 1, OPTAB_LIB_WIDEN);
 587       if (bitpos > 0)
 588         value = expand_shift (LSHIFT_EXPR, mode, value,
 589                               build_int_2 (bitpos, 0), 0, 1);
 590     }
 591
 592   /* Now clear the chosen bits in OP0,
 593      except that if VALUE is -1 we need not bother.  */
 594
 595   subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
 596
 597   if (! all_one)
 598     {
 599       temp = expand_binop (mode, and_optab, op0,
 600                            mask_rtx (mode, bitpos, bitsize, 1),
 601                            subtarget, 1, OPTAB_LIB_WIDEN);
 602       subtarget = temp;
 603     }
 604   else
 605     temp = op0;
 606
 607   /* Now logical-or VALUE into OP0, unless it is zero.  */
 608
 609   if (! all_zero)
 610     temp = expand_binop (mode, ior_optab, temp, value,
 611                          subtarget, 1, OPTAB_LIB_WIDEN);
 612   if (op0 != temp)
 613     emit_move_insn (op0, temp);
 614 }
 615 \f
 616 /* Store a bit field that is split across two words.
 617
 618    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
 619    BITSIZE is the field width; BITPOS the position of its first bit
 620    (within the word).
 621    VALUE is the value to store.  */
 622
 623 static void
 624 store_split_bit_field (op0, bitsize, bitpos, value, align)
 625      rtx op0;
 626      int bitsize, bitpos;
 627      rtx value;
 628      int align;
 629 {
 630   /* BITSIZE_1 is size of the part in the first word.  */
 631   int bitsize_1 = BITS_PER_WORD - bitpos % BITS_PER_WORD;
 632   /* BITSIZE_2 is size of the rest (in the following word).  */
 633   int bitsize_2 = bitsize - bitsize_1;
 634   rtx part1, part2;
 635   int unit = GET_CODE (op0) == MEM ? BITS_PER_UNIT : BITS_PER_WORD;
 636   int offset = bitpos / unit;
 637   rtx word;
 638
 639   /* The field must span exactly one word boundary.  */
 640   if (bitpos / BITS_PER_WORD != (bitpos + bitsize - 1) / BITS_PER_WORD - 1)
 641     abort ();
 642
 643   if (GET_MODE (value) != VOIDmode)
 644     value = convert_to_mode (word_mode, value, 1);
 645   if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
 646     value = copy_to_reg (value);
 647
 648   /* Split the value into two parts:
 649      PART1 gets that which goes in the first word; PART2 the other.  */
 650 #if BYTES_BIG_ENDIAN
 651   /* PART1 gets the more significant part.  */
 652   if (GET_CODE (value) == CONST_INT)
 653     {
 654       part1 = gen_rtx (CONST_INT, VOIDmode,
 655                        (unsigned) (INTVAL (value)) >> bitsize_2);
 656       part2 = gen_rtx (CONST_INT, VOIDmode,
 657                        (unsigned) (INTVAL (value)) & ((1 << bitsize_2) - 1));
 658     }
 659   else
 660     {
 661       part1 = extract_fixed_bit_field (word_mode, value, 0, bitsize_1,
 662                                        BITS_PER_WORD - bitsize, 0, 1,
 663                                        BITS_PER_WORD);
 664       part2 = extract_fixed_bit_field (word_mode, value, 0, bitsize_2,
 665                                        BITS_PER_WORD - bitsize_2, 0, 1,
 666                                        BITS_PER_WORD);
 667     }
 668 #else
 669   /* PART1 gets the less significant part.  */
 670   if (GET_CODE (value) == CONST_INT)
 671     {
 672       part1 = gen_rtx (CONST_INT, VOIDmode,
 673                        (unsigned) (INTVAL (value)) & ((1 << bitsize_1) - 1));
 674       part2 = gen_rtx (CONST_INT, VOIDmode,
 675                        (unsigned) (INTVAL (value)) >> bitsize_1);
 676     }
 677   else
 678     {
 679       part1 = extract_fixed_bit_field (word_mode, value, 0, bitsize_1, 0,
 680                                        0, 1, BITS_PER_WORD);
 681       part2 = extract_fixed_bit_field (word_mode, value, 0, bitsize_2,
 682                                        bitsize_1, 0, 1, BITS_PER_WORD);
 683     }
 684 #endif
 685
 686   /* Store PART1 into the first word.  If OP0 is a MEM, pass OP0 and the
 687      offset computed above.  Otherwise, get the proper word and pass an
 688      offset of zero.  */
 689   word = (GET_CODE (op0) == MEM ? op0
 690           : operand_subword (op0, offset, 1, GET_MODE (op0)));
 691   if (word == 0)
 692     abort ();
 693
 694   store_fixed_bit_field (word, GET_CODE (op0) == MEM ? offset : 0,
 695                          bitsize_1, bitpos % unit, part1, align);
 696
 697   /* Offset op0 by 1 word to get to the following one.  */
 698   if (GET_CODE (op0) == SUBREG)
 699     word = operand_subword (SUBREG_REG (op0), SUBREG_WORD (op0) + offset + 1,
 700                             1, VOIDmode);
 701   else if (GET_CODE (op0) == MEM)
 702     word = op0;
 703   else
 704     word = operand_subword (op0, offset + 1, 1, GET_MODE (op0));
 705
 706   if (word == 0)
 707     abort ();
 708
 709   /* Store PART2 into the second word.  */
 710   store_fixed_bit_field (word,
 711                          (GET_CODE (op0) == MEM
 712                           ? CEIL (offset + 1, UNITS_PER_WORD) * UNITS_PER_WORD
 713                           : 0),
 714                          bitsize_2, 0, part2, align);
 715 }
 716 \f
 717 /* Generate code to extract a byte-field from STR_RTX
 718    containing BITSIZE bits, starting at BITNUM,
 719    and put it in TARGET if possible (if TARGET is nonzero).
 720    Regardless of TARGET, we return the rtx for where the value is placed.
 721    It may be a QUEUED.
 722
 723    STR_RTX is the structure containing the byte (a REG or MEM).
 724    UNSIGNEDP is nonzero if this is an unsigned bit field.
 725    MODE is the natural mode of the field value once extracted.
 726    TMODE is the mode the caller would like the value to have;
 727    but the value may be returned with type MODE instead.
 728
 729    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
 730    TOTAL_SIZE is the size in bytes of the containing structure,
 731    or -1 if varying.
 732
 733    If a TARGET is specified and we can store in it at no extra cost,
 734    we do so, and return TARGET.
 735    Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
 736    if they are equally easy.  */
 737
 738 rtx
 739 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
 740                    target, mode, tmode, align, total_size)
 741      rtx str_rtx;
 742      register int bitsize;
 743      int bitnum;
 744      int unsignedp;
 745      rtx target;
 746      enum machine_mode mode, tmode;
 747      int align;
 748      int total_size;
 749 {
 750   int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
 751   register int offset = bitnum / unit;
 752   register int bitpos = bitnum % unit;
 753   register rtx op0 = str_rtx;
 754   rtx spec_target = target;
 755   rtx spec_target_subreg = 0;
 756
 757   if (GET_CODE (str_rtx) == MEM && ! MEM_IN_STRUCT_P (str_rtx))
 758     abort ();
 759
 760   /* Discount the part of the structure before the desired byte.
 761      We need to know how many bytes are safe to reference after it.  */
 762   if (total_size >= 0)
 763     total_size -= (bitpos / BIGGEST_ALIGNMENT
 764                    * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
 765
 766   if (tmode == VOIDmode)
 767     tmode = mode;
 768
 769   while (GET_CODE (op0) == SUBREG)
 770     {
 771       offset += SUBREG_WORD (op0);
 772       op0 = SUBREG_REG (op0);
 773     }
 774
 775 #if BYTES_BIG_ENDIAN
 776   /* If OP0 is a register, BITPOS must count within a word.
 777      But as we have it, it counts within whatever size OP0 now has.
 778      On a bigendian machine, these are not the same, so convert.  */
 779   if (GET_CODE (op0) != MEM && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
 780     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
 781 #endif
 782
 783   /* Extracting a full-word or multi-word value
 784      from a structure in a register.
 785      This can be done with just SUBREG.
 786      So too extracting a subword value in
 787      the least significant part of the register.  */
 788
 789   if (GET_CODE (op0) == REG
 790       && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
 791            && bitpos % BITS_PER_WORD == 0)
 792           || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
 793 #if BYTES_BIG_ENDIAN
 794               && bitpos + bitsize == BITS_PER_WORD
 795 #else
 796               && bitpos == 0
 797 #endif
 798               )))
 799     {
 800       enum machine_mode mode1
 801         = mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0);
 802
 803       if (mode1 != GET_MODE (op0))
 804         op0 = gen_rtx (SUBREG, mode1, op0, offset);
 805
 806       if (mode1 != mode)
 807         return convert_to_mode (tmode, op0, unsignedp);
 808       return op0;
 809     }
 810
 811   /* Handle fields bigger than a word.  */
 812
 813   if (bitsize > BITS_PER_WORD)
 814     {
 815       /* Here we transfer the words of the field
 816          in the order least significant first.
 817          This is because the most significant word is the one which may
 818          be less than full.  */
 819
 820       int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
 821       int i;
 822
 823       if (target == 0 || GET_CODE (target) != REG)
 824         target = gen_reg_rtx (mode);
 825
 826       for (i = 0; i < nwords; i++)
 827         {
 828           /* If I is 0, use the low-order word in both field and target;
 829              if I is 1, use the next to lowest word; and so on.  */
 830           int wordnum = (WORDS_BIG_ENDIAN ? nwords - i - 1 : i);
 831           int bit_offset = (WORDS_BIG_ENDIAN
 832                             ? MAX (0, bitsize - (i + 1) * BITS_PER_WORD)
 833                             : i * BITS_PER_WORD);
 834           rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
 835           rtx result_part
 836             = extract_bit_field (op0, MIN (BITS_PER_WORD,
 837                                            bitsize - i * BITS_PER_WORD),
 838                                  bitnum + bit_offset,
 839                                  1, target_part, mode, word_mode,
 840                                  align, total_size);
 841
 842           if (target_part == 0)
 843             abort ();
 844
 845           if (result_part != target_part)
 846             emit_move_insn (target_part, result_part);
 847         }
 848
 849       return target;
 850     }
 851
 852   /* From here on we know the desired field is smaller than a word
 853      so we can assume it is an integer.  So we can safely extract it as one
 854      size of integer, if necessary, and then truncate or extend
 855      to the size that is wanted.  */
 856
 857   /* OFFSET is the number of words or bytes (UNIT says which)
 858      from STR_RTX to the first word or byte containing part of the field.  */
 859
 860   if (GET_CODE (op0) == REG)
 861     {
 862       if (offset != 0
 863           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
 864         op0 = gen_rtx (SUBREG, TYPE_MODE (type_for_size (BITS_PER_WORD, 0)),
 865                        op0, offset);
 866       offset = 0;
 867     }
 868   else
 869     {
 870       op0 = protect_from_queue (str_rtx, 1);
 871     }
 872
 873   /* Now OFFSET is nonzero only for memory operands.  */
 874
 875   if (unsignedp)
 876     {
 877 #ifdef HAVE_extzv
 878       if (HAVE_extzv
 879           && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extzv][0])
 880               >= bitsize))
 881         {
 882           int xbitpos = bitpos, xoffset = offset;
 883           rtx bitsize_rtx, bitpos_rtx;
 884           rtx last = get_last_insn();
 885           rtx xop0 = op0;
 886           rtx xtarget = target;
 887           rtx xspec_target = spec_target;
 888           rtx xspec_target_subreg = spec_target_subreg;
 889           rtx pat;
 890           enum machine_mode maxmode
 891             = insn_operand_mode[(int) CODE_FOR_extzv][0];
 892
 893           if (GET_CODE (xop0) == MEM)
 894             {
 895               int save_volatile_ok = volatile_ok;
 896               volatile_ok = 1;
 897
 898               /* Is the memory operand acceptable?  */
 899               if (flag_force_mem
 900                   || ! ((*insn_operand_predicate[(int) CODE_FOR_extzv][1])
 901                         (xop0, GET_MODE (xop0))))
 902                 {
 903                   /* No, load into a reg and extract from there.  */
 904                   enum machine_mode bestmode;
 905
 906                   /* Get the mode to use for inserting into this field.  If
 907                      OP0 is BLKmode, get the smallest mode consistent with the
 908                      alignment. If OP0 is a non-BLKmode object that is no
 909                      wider than MAXMODE, use its mode. Otherwise, use the
 910                      smallest mode containing the field.  */
 911
 912                   if (GET_MODE (xop0) == BLKmode
 913                       || (GET_MODE_SIZE (GET_MODE (op0))
 914                           > GET_MODE_SIZE (maxmode)))
 915                     bestmode = get_best_mode (bitsize, bitnum,
 916                                               align * BITS_PER_UNIT, maxmode,
 917                                               (GET_CODE (xop0) == MEM
 918                                                && MEM_VOLATILE_P (xop0)));
 919                   else
 920                     bestmode = GET_MODE (xop0);
 921
 922                   if (bestmode == VOIDmode)
 923                     goto extzv_loses;
 924
 925                   /* Compute offset as multiple of this unit,
 926                      counting in bytes.  */
 927                   unit = GET_MODE_BITSIZE (bestmode);
 928                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
 929                   xbitpos = bitnum % unit;
 930                   xop0 = change_address (xop0, bestmode,
 931                                          plus_constant (XEXP (xop0, 0),
 932                                                         xoffset));
 933                   /* Fetch it to a register in that size.  */
 934                   xop0 = force_reg (bestmode, xop0);
 935
 936                   /* XBITPOS counts within UNIT, which is what is expected.  */
 937                 }
 938               else
 939                 /* Get ref to first byte containing part of the field.  */
 940                 xop0 = change_address (xop0, byte_mode,
 941                                        plus_constant (XEXP (xop0, 0), xoffset));
 942
 943               volatile_ok = save_volatile_ok;
 944             }
 945
 946           /* If op0 is a register, we need it in MAXMODE (which is usually
 947              SImode). to make it acceptable to the format of extzv.  */
 948           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
 949             abort ();
 950           if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
 951             xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
 952
 953           /* On big-endian machines, we count bits from the most significant.
 954              If the bit field insn does not, we must invert.  */
 955 #if BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN
 956           xbitpos = unit - bitsize - xbitpos;
 957 #endif
 958           /* Now convert from counting within UNIT to counting in MAXMODE.  */
 959 #if BITS_BIG_ENDIAN
 960           if (GET_CODE (xop0) != MEM)
 961             xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
 962 #endif
 963           unit = GET_MODE_BITSIZE (maxmode);
 964
 965           if (xtarget == 0
 966               || (flag_force_mem && GET_CODE (xtarget) == MEM))
 967             xtarget = xspec_target = gen_reg_rtx (tmode);
 968
 969           if (GET_MODE (xtarget) != maxmode)
 970             {
 971               if (GET_CODE (xtarget) == REG)
 972                 xspec_target_subreg = xtarget = gen_lowpart (maxmode, xtarget);
 973               else
 974                 xtarget = gen_reg_rtx (maxmode);
 975             }
 976
 977           /* If this machine's extzv insists on a register target,
 978              make sure we have one.  */
 979           if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][0])
 980                  (xtarget, maxmode)))
 981             xtarget = gen_reg_rtx (maxmode);
 982
 983           bitsize_rtx = gen_rtx (CONST_INT, VOIDmode, bitsize);
 984           bitpos_rtx = gen_rtx (CONST_INT, VOIDmode, xbitpos);
 985
 986           pat = gen_extzv (protect_from_queue (xtarget, 1),
 987                            xop0, bitsize_rtx, bitpos_rtx);
 988           if (pat)
 989             {
 990               emit_insn (pat);
 991               target = xtarget;
 992               spec_target = xspec_target;
 993               spec_target_subreg = xspec_target_subreg;
 994             }
 995           else
 996             {
 997               delete_insns_since (last);
 998               target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
 999                                                 bitpos, target, 1, align);
1000             }
1001         }
1002       else
1003         extzv_loses:
1004 #endif
1005         target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1006                                           target, 1, align);
1007     }
1008   else
1009     {
1010 #ifdef HAVE_extv
1011       if (HAVE_extv
1012           && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extv][0])
1013               >= bitsize))
1014         {
1015           int xbitpos = bitpos, xoffset = offset;
1016           rtx bitsize_rtx, bitpos_rtx;
1017           rtx last = get_last_insn();
1018           rtx xop0 = op0, xtarget = target;
1019           rtx xspec_target = spec_target;
1020           rtx xspec_target_subreg = spec_target_subreg;
1021           rtx pat;
1022           enum machine_mode maxmode
1023             = insn_operand_mode[(int) CODE_FOR_extv][0];
1024
1025           if (GET_CODE (xop0) == MEM)
1026             {
1027               /* Is the memory operand acceptable?  */
1028               if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][1])
1029                      (xop0, GET_MODE (xop0))))
1030                 {
1031                   /* No, load into a reg and extract from there.  */
1032                   enum machine_mode bestmode;
1033
1034                   /* Get the mode to use for inserting into this field.  If
1035                      OP0 is BLKmode, get the smallest mode consistent with the
1036                      alignment. If OP0 is a non-BLKmode object that is no
1037                      wider than MAXMODE, use its mode. Otherwise, use the
1038                      smallest mode containing the field.  */
1039
1040                   if (GET_MODE (xop0) == BLKmode
1041                       || (GET_MODE_SIZE (GET_MODE (op0))
1042                           > GET_MODE_SIZE (maxmode)))
1043                     bestmode = get_best_mode (bitsize, bitnum,
1044                                               align * BITS_PER_UNIT, maxmode,
1045                                               (GET_CODE (xop0) == MEM
1046                                                && MEM_VOLATILE_P (xop0)));
1047                   else
1048                     bestmode = GET_MODE (xop0);
1049
1050                   if (bestmode == VOIDmode)
1051                     goto extv_loses;
1052
1053                   /* Compute offset as multiple of this unit,
1054                      counting in bytes.  */
1055                   unit = GET_MODE_BITSIZE (bestmode);
1056                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1057                   xbitpos = bitnum % unit;
1058                   xop0 = change_address (xop0, bestmode,
1059                                          plus_constant (XEXP (xop0, 0),
1060                                                         xoffset));
1061                   /* Fetch it to a register in that size.  */
1062                   xop0 = force_reg (bestmode, xop0);
1063
1064                   /* XBITPOS counts within UNIT, which is what is expected.  */
1065                 }
1066               else
1067                 /* Get ref to first byte containing part of the field.  */
1068                 xop0 = change_address (xop0, byte_mode,
1069                                        plus_constant (XEXP (xop0, 0), xoffset));
1070             }
1071
1072           /* If op0 is a register, we need it in MAXMODE (which is usually
1073              SImode) to make it acceptable to the format of extv.  */
1074           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1075             abort ();
1076           if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1077             xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
1078
1079           /* On big-endian machines, we count bits from the most significant.
1080              If the bit field insn does not, we must invert.  */
1081 #if BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN
1082           xbitpos = unit - bitsize - xbitpos;
1083 #endif
1084           /* XBITPOS counts within a size of UNIT.
1085              Adjust to count within a size of MAXMODE.  */
1086 #if BITS_BIG_ENDIAN
1087           if (GET_CODE (xop0) != MEM)
1088             xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1089 #endif
1090           unit = GET_MODE_BITSIZE (maxmode);
1091
1092           if (xtarget == 0
1093               || (flag_force_mem && GET_CODE (xtarget) == MEM))
1094             xtarget = xspec_target = gen_reg_rtx (tmode);
1095
1096           if (GET_MODE (xtarget) != maxmode)
1097             {
1098               if (GET_CODE (xtarget) == REG)
1099                 xspec_target_subreg = xtarget = gen_lowpart (maxmode, xtarget);
1100               else
1101                 xtarget = gen_reg_rtx (maxmode);
1102             }
1103
1104           /* If this machine's extv insists on a register target,
1105              make sure we have one.  */
1106           if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][0])
1107                  (xtarget, maxmode)))
1108             xtarget = gen_reg_rtx (maxmode);
1109
1110           bitsize_rtx = gen_rtx (CONST_INT, VOIDmode, bitsize);
1111           bitpos_rtx = gen_rtx (CONST_INT, VOIDmode, xbitpos);
1112
1113           pat = gen_extv (protect_from_queue (xtarget, 1),
1114                           xop0, bitsize_rtx, bitpos_rtx);
1115           if (pat)
1116             {
1117               emit_insn (pat);
1118               target = xtarget;
1119               spec_target = xspec_target;
1120               spec_target_subreg = xspec_target_subreg;
1121             }
1122           else
1123             {
1124               delete_insns_since (last);
1125               target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
1126                                                 bitpos, target, 0, align);
1127             }
1128         }
1129       else
1130         extv_loses:
1131 #endif
1132         target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1133                                           target, 0, align);
1134     }
1135   if (target == spec_target)
1136     return target;
1137   if (target == spec_target_subreg)
1138     return spec_target;
1139   if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1140     {
1141       /* If the target mode is floating-point, first convert to the
1142          integer mode of that size and then access it as a floating-point
1143          value via a SUBREG.  */
1144       if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1145         {
1146           target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1147                                                    MODE_INT, 0),
1148                                     target, unsignedp);
1149           if (GET_CODE (target) != REG)
1150             target = copy_to_reg (target);
1151           return gen_rtx (SUBREG, tmode, target, 0);
1152         }
1153       else
1154         return convert_to_mode (tmode, target, unsignedp);
1155     }
1156   return target;
1157 }
1158 \f
1159 /* Extract a bit field using shifts and boolean operations
1160    Returns an rtx to represent the value.
1161    OP0 addresses a register (word) or memory (byte).
1162    BITPOS says which bit within the word or byte the bit field starts in.
1163    OFFSET says how many bytes farther the bit field starts;
1164     it is 0 if OP0 is a register.
1165    BITSIZE says how many bits long the bit field is.
1166     (If OP0 is a register, it may be narrower than a full word,
1167      but BITPOS still counts within a full word,
1168      which is significant on bigendian machines.)
1169
1170    UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1171    If TARGET is nonzero, attempts to store the value there
1172    and return TARGET, but this is not guaranteed.
1173    If TARGET is not used, create a pseudo-reg of mode TMODE for the value.
1174
1175    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.  */
1176
1177 static rtx
1178 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1179                          target, unsignedp, align)
1180      enum machine_mode tmode;
1181      register rtx op0, target;
1182      register int offset, bitsize, bitpos;
1183      int unsignedp;
1184      int align;
1185 {
1186   int total_bits = BITS_PER_WORD;
1187   enum machine_mode mode;
1188
1189   if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1190     {
1191       /* Special treatment for a bit field split across two registers.  */
1192       if (bitsize + bitpos > BITS_PER_WORD)
1193         return extract_split_bit_field (op0, bitsize, bitpos,
1194                                         unsignedp, align);
1195     }
1196   else
1197     {
1198       /* Get the proper mode to use for this field.  We want a mode that
1199          includes the entire field.  If such a mode would be larger than
1200          a word, we won't be doing the extraction the normal way.  */
1201
1202       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1203                             align * BITS_PER_UNIT, word_mode,
1204                             GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
1205
1206       if (mode == VOIDmode)
1207         /* The only way this should occur is if the field spans word
1208            boundaries.  */
1209         return extract_split_bit_field (op0, bitsize,
1210                                         bitpos + offset * BITS_PER_UNIT,
1211                                         unsignedp, align);
1212
1213       total_bits = GET_MODE_BITSIZE (mode);
1214
1215       /* Get ref to an aligned byte, halfword, or word containing the field.
1216          Adjust BITPOS to be position within a word,
1217          and OFFSET to be the offset of that word.
1218          Then alter OP0 to refer to that word.  */
1219       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1220       offset -= (offset % (total_bits / BITS_PER_UNIT));
1221       op0 = change_address (op0, mode,
1222                             plus_constant (XEXP (op0, 0), offset));
1223     }
1224
1225   mode = GET_MODE (op0);
1226
1227 #if BYTES_BIG_ENDIAN
1228   /* BITPOS is the distance between our msb and that of OP0.
1229      Convert it to the distance from the lsb.  */
1230
1231   bitpos = total_bits - bitsize - bitpos;
1232 #endif
1233   /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1234      We have reduced the big-endian case to the little-endian case.  */
1235
1236   if (unsignedp)
1237     {
1238       if (bitpos)
1239         {
1240           /* If the field does not already start at the lsb,
1241              shift it so it does.  */
1242           tree amount = build_int_2 (bitpos, 0);
1243           /* Maybe propagate the target for the shift.  */
1244           /* But not if we will return it--could confuse integrate.c.  */
1245           rtx subtarget = (target != 0 && GET_CODE (target) == REG
1246                            && !REG_FUNCTION_VALUE_P (target)
1247                            ? target : 0);
1248           if (tmode != mode) subtarget = 0;
1249           op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1250         }
1251       /* Convert the value to the desired mode.  */
1252       if (mode != tmode)
1253         op0 = convert_to_mode (tmode, op0, 1);
1254
1255       /* Unless the msb of the field used to be the msb when we shifted,
1256          mask out the upper bits.  */
1257
1258       if (GET_MODE_BITSIZE (mode) != bitpos + bitsize
1259 #if 0
1260 #ifdef SLOW_ZERO_EXTEND
1261           /* Always generate an `and' if
1262              we just zero-extended op0 and SLOW_ZERO_EXTEND, since it
1263              will combine fruitfully with the zero-extend. */
1264           || tmode != mode
1265 #endif
1266 #endif
1267           )
1268         return expand_binop (GET_MODE (op0), and_optab, op0,
1269                              mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1270                              target, 1, OPTAB_LIB_WIDEN);
1271       return op0;
1272     }
1273
1274   /* To extract a signed bit-field, first shift its msb to the msb of the word,
1275      then arithmetic-shift its lsb to the lsb of the word.  */
1276   op0 = force_reg (mode, op0);
1277   if (mode != tmode)
1278     target = 0;
1279
1280   /* Find the narrowest integer mode that contains the field.  */
1281
1282   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1283        mode = GET_MODE_WIDER_MODE (mode))
1284     if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1285       {
1286         op0 = convert_to_mode (mode, op0, 0);
1287         break;
1288       }
1289
1290   if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1291     {
1292       tree amount = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1293       /* Maybe propagate the target for the shift.  */
1294       /* But not if we will return the result--could confuse integrate.c.  */
1295       rtx subtarget = (target != 0 && GET_CODE (target) == REG
1296                        && ! REG_FUNCTION_VALUE_P (target)
1297                        ? target : 0);
1298       op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1299     }
1300
1301   return expand_shift (RSHIFT_EXPR, mode, op0,
1302                        build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1303                        target, 0);
1304 }
1305 \f
1306 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1307    of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1308    complement of that if COMPLEMENT.  The mask is truncated if
1309    necessary to the width of mode MODE.  */
1310
1311 static rtx
1312 mask_rtx (mode, bitpos, bitsize, complement)
1313      enum machine_mode mode;
1314      int bitpos, bitsize, complement;
1315 {
1316   int masklow, maskhigh;
1317
1318   if (bitpos < HOST_BITS_PER_INT)
1319     masklow = -1 << bitpos;
1320   else
1321     masklow = 0;
1322
1323   if (bitpos + bitsize < HOST_BITS_PER_INT)
1324     masklow &= (unsigned) -1 >> (HOST_BITS_PER_INT - bitpos - bitsize);
1325
1326   if (bitpos <= HOST_BITS_PER_INT)
1327     maskhigh = -1;
1328   else
1329     maskhigh = -1 << (bitpos - HOST_BITS_PER_INT);
1330
1331   if (bitpos + bitsize > HOST_BITS_PER_INT)
1332     maskhigh &= (unsigned) -1 >> (2 * HOST_BITS_PER_INT - bitpos - bitsize);
1333   else
1334     maskhigh = 0;
1335
1336   if (complement)
1337     {
1338       maskhigh = ~maskhigh;
1339       masklow = ~masklow;
1340     }
1341
1342   return immed_double_const (masklow, maskhigh, mode);
1343 }
1344
1345 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1346    VALUE truncated to BITSIZE bits and then shifted left BITPOS bits.  */
1347
1348 static rtx
1349 lshift_value (mode, value, bitpos, bitsize)
1350      enum machine_mode mode;
1351      rtx value;
1352      int bitpos, bitsize;
1353 {
1354   unsigned v = INTVAL (value);
1355   int low, high;
1356
1357   if (bitsize < HOST_BITS_PER_INT)
1358     v &= ~(-1 << bitsize);
1359
1360   if (bitpos < HOST_BITS_PER_INT)
1361     {
1362       low = v << bitpos;
1363       high = (bitpos > 0 ? (v >> (HOST_BITS_PER_INT - bitpos)) : 0);
1364     }
1365   else
1366     {
1367       low = 0;
1368       high = v << (bitpos - HOST_BITS_PER_INT);
1369     }
1370
1371   return immed_double_const (low, high, mode);
1372 }
1373 \f
1374 /* Extract a bit field that is split across two words
1375    and return an RTX for the result.
1376
1377    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1378    BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1379    UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.  */
1380
1381 static rtx
1382 extract_split_bit_field (op0, bitsize, bitpos, unsignedp, align)
1383      rtx op0;
1384      int bitsize, bitpos, unsignedp, align;
1385 {
1386   /* BITSIZE_1 is size of the part in the first word.  */
1387   int bitsize_1 = BITS_PER_WORD - bitpos % BITS_PER_WORD;
1388   /* BITSIZE_2 is size of the rest (in the following word).  */
1389   int bitsize_2 = bitsize - bitsize_1;
1390   rtx part1, part2, result;
1391   int unit = GET_CODE (op0) == MEM ? BITS_PER_UNIT : BITS_PER_WORD;
1392   int offset = bitpos / unit;
1393   rtx word;
1394
1395   /* The field must span exactly one word boundary.  */
1396   if (bitpos / BITS_PER_WORD != (bitpos + bitsize - 1) / BITS_PER_WORD - 1)
1397     abort ();
1398
1399   /* Get the part of the bit field from the first word.  If OP0 is a MEM,
1400      pass OP0 and the offset computed above.  Otherwise, get the proper
1401      word and pass an offset of zero.  */
1402   word = (GET_CODE (op0) == MEM ? op0
1403           : operand_subword_force (op0, offset, GET_MODE (op0)));
1404   part1 = extract_fixed_bit_field (word_mode, word,
1405                                    GET_CODE (op0) == MEM ? offset : 0,
1406                                    bitsize_1, bitpos % unit, 0, 1, align);
1407
1408   /* Offset op0 by 1 word to get to the following one.  */
1409   if (GET_CODE (op0) == SUBREG)
1410     word = operand_subword_force (SUBREG_REG (op0),
1411                                   SUBREG_WORD (op0) + offset + 1, VOIDmode);
1412   else if (GET_CODE (op0) == MEM)
1413     word = op0;
1414   else
1415     word = operand_subword_force (op0, offset + 1, GET_MODE (op0));
1416
1417   /* Get the part of the bit field from the second word.  */
1418   part2 = extract_fixed_bit_field (word_mode, word,
1419                                    (GET_CODE (op0) == MEM
1420                                     ? CEIL (offset + 1, UNITS_PER_WORD) * UNITS_PER_WORD
1421                                     : 0),
1422                                    bitsize_2, 0, 0, 1, align);
1423
1424   /* Shift the more significant part up to fit above the other part.  */
1425 #if BYTES_BIG_ENDIAN
1426   part1 = expand_shift (LSHIFT_EXPR, word_mode, part1,
1427                         build_int_2 (bitsize_2, 0), 0, 1);
1428 #else
1429   part2 = expand_shift (LSHIFT_EXPR, word_mode, part2,
1430                         build_int_2 (bitsize_1, 0), 0, 1);
1431 #endif
1432
1433   /* Combine the two parts with bitwise or.  This works
1434      because we extracted both parts as unsigned bit fields.  */
1435   result = expand_binop (word_mode, ior_optab, part1, part2, 0, 1,
1436                          OPTAB_LIB_WIDEN);
1437
1438   /* Unsigned bit field: we are done.  */
1439   if (unsignedp)
1440     return result;
1441   /* Signed bit field: sign-extend with two arithmetic shifts.  */
1442   result = expand_shift (LSHIFT_EXPR, word_mode, result,
1443                          build_int_2 (BITS_PER_WORD - bitsize, 0), 0, 0);
1444   return expand_shift (RSHIFT_EXPR, word_mode, result,
1445                        build_int_2 (BITS_PER_WORD - bitsize, 0), 0, 0);
1446 }
1447 \f
1448 /* Add INC into TARGET.  */
1449
1450 void
1451 expand_inc (target, inc)
1452      rtx target, inc;
1453 {
1454   rtx value = expand_binop (GET_MODE (target), add_optab,
1455                             target, inc,
1456                             target, 0, OPTAB_LIB_WIDEN);
1457   if (value != target)
1458     emit_move_insn (target, value);
1459 }
1460
1461 /* Subtract DEC from TARGET.  */
1462
1463 void
1464 expand_dec (target, dec)
1465      rtx target, dec;
1466 {
1467   rtx value = expand_binop (GET_MODE (target), sub_optab,
1468                             target, dec,
1469                             target, 0, OPTAB_LIB_WIDEN);
1470   if (value != target)
1471     emit_move_insn (target, value);
1472 }
1473 \f
1474 /* Output a shift instruction for expression code CODE,
1475    with SHIFTED being the rtx for the value to shift,
1476    and AMOUNT the tree for the amount to shift by.
1477    Store the result in the rtx TARGET, if that is convenient.
1478    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1479    Return the rtx for where the value is.  */
1480
1481 rtx
1482 expand_shift (code, mode, shifted, amount, target, unsignedp)
1483      enum tree_code code;
1484      register enum machine_mode mode;
1485      rtx shifted;
1486      tree amount;
1487      register rtx target;
1488      int unsignedp;
1489 {
1490   register rtx op1, temp = 0;
1491   register int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1492   register int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1493   int try;
1494
1495   /* Previously detected shift-counts computed by NEGATE_EXPR
1496      and shifted in the other direction; but that does not work
1497      on all machines.  */
1498
1499   op1 = expand_expr (amount, 0, VOIDmode, 0);
1500
1501   if (op1 == const0_rtx)
1502     return shifted;
1503
1504   for (try = 0; temp == 0 && try < 3; try++)
1505     {
1506       enum optab_methods methods;
1507
1508       if (try == 0)
1509         methods = OPTAB_DIRECT;
1510       else if (try == 1)
1511         methods = OPTAB_WIDEN;
1512       else
1513         methods = OPTAB_LIB_WIDEN;
1514
1515       if (rotate)
1516         {
1517           /* Widening does not work for rotation.  */
1518           if (methods == OPTAB_WIDEN)
1519             continue;
1520           else if (methods == OPTAB_LIB_WIDEN)
1521             methods = OPTAB_LIB;
1522
1523           temp = expand_binop (mode,
1524                                left ? rotl_optab : rotr_optab,
1525                                shifted, op1, target, unsignedp, methods);
1526         }
1527       else if (unsignedp)
1528         {
1529           temp = expand_binop (mode,
1530                                left ? lshl_optab : lshr_optab,
1531                                shifted, op1, target, unsignedp, methods);
1532           if (temp == 0 && left)
1533             temp = expand_binop (mode, ashl_optab,
1534                                  shifted, op1, target, unsignedp, methods);
1535         }
1536
1537       /* Do arithmetic shifts.
1538          Also, if we are going to widen the operand, we can just as well
1539          use an arithmetic right-shift instead of a logical one.  */
1540       if (temp == 0 && ! rotate
1541           && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
1542         {
1543           enum optab_methods methods1 = methods;
1544
1545           /* If trying to widen a log shift to an arithmetic shift,
1546              don't accept an arithmetic shift of the same size.  */
1547           if (unsignedp)
1548             methods1 = OPTAB_MUST_WIDEN;
1549
1550           /* Arithmetic shift */
1551
1552           temp = expand_binop (mode,
1553                                left ? ashl_optab : ashr_optab,
1554                                shifted, op1, target, unsignedp, methods1);
1555         }
1556
1557 #ifdef HAVE_extzv
1558       /* We can do a logical (unsigned) right shift with a bit-field
1559          extract insn.  But first check if one of the above methods worked.  */
1560       if (temp != 0)
1561         return temp;
1562
1563       if (unsignedp && code == RSHIFT_EXPR && ! BITS_BIG_ENDIAN && HAVE_extzv)
1564         {
1565           enum machine_mode output_mode
1566             = insn_operand_mode[(int) CODE_FOR_extzv][0];
1567
1568           if ((methods == OPTAB_DIRECT && mode == output_mode)
1569               || (methods == OPTAB_WIDEN
1570                   && GET_MODE_SIZE (mode) < GET_MODE_SIZE (output_mode)))
1571             {
1572               /* Note convert_to_mode does protect_from_queue.  */
1573               rtx shifted1 = convert_to_mode (output_mode, shifted, 1);
1574               enum machine_mode length_mode
1575                 = insn_operand_mode[(int) CODE_FOR_extzv][2];
1576               enum machine_mode pos_mode
1577                 = insn_operand_mode[(int) CODE_FOR_extzv][3];
1578               rtx target1 = 0;
1579               rtx last = get_last_insn ();
1580               rtx width;
1581               rtx xop1 = op1;
1582               rtx pat;
1583
1584               if (target != 0)
1585                 target1 = protect_from_queue (target, 1);
1586
1587               /* We define extract insns as having OUTPUT_MODE in a register
1588                  and the mode of operand 1 in memory.  Since we want
1589                  OUTPUT_MODE, we will always force the operand into a
1590                  register.  At some point we might want to support MEM
1591                  directly. */
1592               shifted1 = force_reg (output_mode, shifted1);
1593
1594               /* If we don't have or cannot use a suggested target,
1595                  make a place for the result, in the proper mode.  */
1596               if (methods == OPTAB_WIDEN || target1 == 0
1597                   || ! ((*insn_operand_predicate[(int) CODE_FOR_extzv][0])
1598                         (target1, output_mode)))
1599                 target1 = gen_reg_rtx (output_mode);
1600
1601               xop1 = convert_to_mode (pos_mode, xop1,
1602                                       TREE_UNSIGNED (TREE_TYPE (amount)));
1603
1604               /* If this machine's extzv insists on a register for
1605                  operand 3 (position), arrange for that.  */
1606               if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][3])
1607                      (xop1, pos_mode)))
1608                 xop1 = force_reg (pos_mode, xop1);
1609
1610               /* WIDTH gets the width of the bit field to extract:
1611                  wordsize minus # bits to shift by.  */
1612               if (GET_CODE (xop1) == CONST_INT)
1613                 width = gen_rtx (CONST_INT, VOIDmode,
1614                                  (GET_MODE_BITSIZE (mode) - INTVAL (op1)));
1615               else
1616                 {
1617                   /* Now get the width in the proper mode.  */
1618                   width = convert_to_mode (length_mode, op1,
1619                                            TREE_UNSIGNED (TREE_TYPE (amount)));
1620
1621                   width = expand_binop (length_mode, sub_optab,
1622                                         gen_rtx (CONST_INT, VOIDmode,
1623                                                  GET_MODE_BITSIZE (mode)),
1624                                         width, 0, 0, OPTAB_LIB_WIDEN);
1625                 }
1626
1627               /* If this machine's extzv insists on a register for
1628                  operand 2 (length), arrange for that.  */
1629               if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][2])
1630                      (width, length_mode)))
1631                 width = force_reg (length_mode, width);
1632
1633               /* Now extract with WIDTH, omitting OP1 least sig bits.  */
1634               pat = gen_extzv (target1, shifted1, width, xop1);
1635               if (pat)
1636                 {
1637                   emit_insn (pat);
1638                   temp = convert_to_mode (mode, target1, 1);
1639                 }
1640               else
1641                 delete_insns_since (last);
1642             }
1643
1644           /* Can also do logical shift with signed bit-field extract
1645              followed by inserting the bit-field at a different position.
1646              That strategy is not yet implemented.  */
1647         }
1648 #endif /* HAVE_extzv */
1649     }
1650
1651   if (temp == 0)
1652     abort ();
1653   return temp;
1654 }
1655 \f
1656 enum alg_code { alg_add, alg_subtract, alg_compound };
1657
1658 /* This structure records a sequence of operations.
1659    `ops' is the number of operations recorded.
1660    `cost' is their total cost.
1661    The operations are stored in `op' and the corresponding
1662    integer coefficients in `coeff'.
1663    These are the operations:
1664    alg_add       Add to the total the multiplicand times the coefficient.
1665    alg_subtract  Subtract the multiplicand times the coefficient.
1666    alg_compound  This coefficient plus or minus the following one
1667                  is multiplied into the total.  The following operation
1668                  is alg_add or alg_subtract to indicate whether to add
1669                  or subtract the two coefficients.  */
1670
1671 #ifndef MAX_BITS_PER_WORD
1672 #define MAX_BITS_PER_WORD BITS_PER_WORD
1673 #endif
1674
1675 struct algorithm
1676 {
1677   int cost;
1678   unsigned int ops;
1679   enum alg_code op[MAX_BITS_PER_WORD];
1680   unsigned int coeff[MAX_BITS_PER_WORD];
1681 };
1682
1683 /* Compute and return the best algorithm for multiplying by T.
1684    Assume that add insns cost ADD_COST and shifts cost SHIFT_COST.
1685    Return cost -1 if would cost more than MAX_COST.  */
1686
1687 static struct algorithm
1688 synth_mult (t, add_cost, shift_cost, max_cost)
1689      unsigned int t;
1690      int add_cost, shift_cost;
1691      int max_cost;
1692 {
1693   int m, n;
1694   struct algorithm *best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
1695   struct algorithm *alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
1696   unsigned int cost;
1697
1698   /* No matter what happens, we want to return a valid algorithm.  */
1699   best_alg->cost = max_cost;
1700   best_alg->ops = 0;
1701
1702   /* Is t an exponent of 2, so we can just do a shift?  */
1703
1704   if ((t & -t) == t)
1705     {
1706       if (t > 1)
1707         {
1708           if (max_cost >= shift_cost)
1709             {
1710               best_alg->cost = shift_cost;
1711               best_alg->ops = 1;
1712               best_alg->op[0] = alg_add;
1713               best_alg->coeff[0] = t;
1714             }
1715           else
1716             best_alg->cost = -1;
1717         }
1718       else if (t == 1)
1719         {
1720           if (max_cost >= 0)
1721             best_alg->cost = 0;
1722         }
1723       else
1724         best_alg->cost = 0;
1725
1726       return *best_alg;
1727     }
1728
1729   /* If MAX_COST just permits as little as an addition (or less), we won't
1730      succeed in synthesizing an algorithm for t.  Return immediately with
1731      an indication of failure.  */
1732   if (max_cost <= add_cost)
1733     {
1734       best_alg->cost = -1;
1735       return *best_alg;
1736     }
1737
1738   /* Look for factors of t of the form
1739      t = q(2**m +- 1), 2 <= m <= floor(log2(t)) - 1.
1740      If we find such a factor, we can multiply by t using an algorithm that
1741      multiplies by q, shift the result by m and add/subtract it to itself.  */
1742
1743   for (m = floor_log2 (t) - 1; m >= 2; m--)
1744     {
1745       int m_exp_2 = 1 << m;
1746       int d;
1747
1748       d = m_exp_2 + 1;
1749       if (t % d == 0)
1750         {
1751           int q = t / d;
1752
1753           cost = add_cost + shift_cost * 2;
1754
1755           *alg_in = synth_mult (q, add_cost, shift_cost,
1756                                 MIN (max_cost, best_alg->cost) - cost);
1757
1758           if (alg_in->cost >= 0)
1759             {
1760               cost += alg_in->cost;
1761
1762               if (cost < best_alg->cost)
1763                 {
1764                   struct algorithm *x;
1765                   x = alg_in;
1766                   alg_in = best_alg;
1767                   best_alg = x;
1768                   best_alg->coeff[best_alg->ops] = m_exp_2;
1769                   best_alg->op[best_alg->ops++] = alg_compound;
1770                   best_alg->coeff[best_alg->ops] = 1;
1771                   best_alg->op[best_alg->ops++] = alg_add;
1772                   best_alg->cost = cost;
1773                 }
1774             }
1775         }
1776
1777       d = m_exp_2 - 1;
1778       if (t % d == 0)
1779         {
1780           int q = t / d;
1781
1782           cost = add_cost + shift_cost * 2;
1783
1784           *alg_in = synth_mult (q, add_cost, shift_cost,
1785                                 MIN (max_cost, best_alg->cost) - cost);
1786
1787           if (alg_in->cost >= 0)
1788             {
1789               cost += alg_in->cost;
1790
1791               if (cost < best_alg->cost)
1792                 {
1793                   struct algorithm *x;
1794                   x = alg_in;
1795                   alg_in = best_alg;
1796                   best_alg = x;
1797                   best_alg->coeff[best_alg->ops] = m_exp_2;
1798                   best_alg->op[best_alg->ops++] = alg_compound;
1799                   best_alg->coeff[best_alg->ops] = 1;
1800                   best_alg->op[best_alg->ops++] = alg_subtract;
1801                   best_alg->cost = cost;
1802                 }
1803             }
1804         }
1805     }
1806
1807   /* Try load effective address instructions, i.e. do a*3, a*5, a*9.  */
1808
1809   {
1810     int q;
1811     int w;
1812
1813     q = t & -t;                 /* get out lsb */
1814     w = (t - q) & -(t - q);     /* get out next lsb */
1815
1816     if (w / q <= lea_max_mul)
1817       {
1818         cost = lea_cost + (q != 1 ? shift_cost : 0);
1819
1820         *alg_in = synth_mult (t - q - w, add_cost, shift_cost,
1821                               MIN (max_cost, best_alg->cost) - cost);
1822
1823         if (alg_in->cost >= 0)
1824           {
1825             cost += alg_in->cost;
1826
1827             /* Use <= to prefer this method to the factoring method
1828                when the cost appears the same, because this method
1829                uses fewer temporary registers.  */
1830             if (cost <= best_alg->cost)
1831               {
1832                 struct algorithm *x;
1833                 x = alg_in;
1834                 alg_in = best_alg;
1835                 best_alg = x;
1836                 best_alg->coeff[best_alg->ops] = w;
1837                 best_alg->op[best_alg->ops++] = alg_add;
1838                 best_alg->coeff[best_alg->ops] = q;
1839                 best_alg->op[best_alg->ops++] = alg_add;
1840                 best_alg->cost = cost;
1841               }
1842           }
1843       }
1844   }
1845
1846   /* Now, use the good old method to add or subtract at the leftmost
1847      1-bit.  */
1848
1849   {
1850     int q;
1851     int w;
1852
1853     q = t & -t;                 /* get out lsb */
1854     for (w = q; (w & t) != 0; w <<= 1)
1855       ;
1856     if ((w > q << 1)
1857         /* Reject the case where t has only two bits.
1858            Thus we prefer addition in that case.  */
1859         && !(t < w && w == q << 2))
1860       {
1861         /* There are many bits in a row.  Make 'em by subtraction.  */
1862
1863         cost = add_cost;
1864         if (q != 1)
1865           cost += shift_cost;
1866
1867         *alg_in = synth_mult (t + q, add_cost, shift_cost,
1868                               MIN (max_cost, best_alg->cost) - cost);
1869
1870         if (alg_in->cost >= 0)
1871           {
1872             cost += alg_in->cost;
1873
1874             /* Use <= to prefer this method to the factoring method
1875                when the cost appears the same, because this method
1876                uses fewer temporary registers.  */
1877             if (cost <= best_alg->cost)
1878               {
1879                 struct algorithm *x;
1880                 x = alg_in;
1881                 alg_in = best_alg;
1882                 best_alg = x;
1883                 best_alg->coeff[best_alg->ops] = q;
1884                 best_alg->op[best_alg->ops++] = alg_subtract;
1885                 best_alg->cost = cost;
1886               }
1887           }
1888       }
1889     else
1890       {
1891         /* There's only one bit at the left.  Make it by addition.  */
1892
1893         cost = add_cost;
1894         if (q != 1)
1895           cost += shift_cost;
1896
1897         *alg_in = synth_mult (t - q, add_cost, shift_cost,
1898                               MIN (max_cost, best_alg->cost) - cost);
1899
1900         if (alg_in->cost >= 0)
1901           {
1902             cost += alg_in->cost;
1903
1904             if (cost <= best_alg->cost)
1905               {
1906                 struct algorithm *x;
1907                 x = alg_in;
1908                 alg_in = best_alg;
1909                 best_alg = x;
1910                 best_alg->coeff[best_alg->ops] = q;
1911                 best_alg->op[best_alg->ops++] = alg_add;
1912                 best_alg->cost = cost;
1913               }
1914           }
1915       }
1916   }
1917
1918   if (best_alg->cost >= max_cost)
1919     best_alg->cost = -1;
1920   return *best_alg;
1921 }
1922 \f
1923 /* Perform a multiplication and return an rtx for the result.
1924    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
1925    TARGET is a suggestion for where to store the result (an rtx).
1926
1927    We check specially for a constant integer as OP1.
1928    If you want this check for OP0 as well, then before calling
1929    you should swap the two operands if OP0 would be constant.  */
1930
1931 rtx
1932 expand_mult (mode, op0, op1, target, unsignedp)
1933      enum machine_mode mode;
1934      register rtx op0, op1, target;
1935      int unsignedp;
1936 {
1937   rtx const_op1 = op1;
1938
1939   /* If we are multiplying in DImode, it may still be a win
1940      to try to work with shifts and adds.  */
1941   if (GET_CODE (op1) == CONST_DOUBLE
1942       && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
1943       && HOST_BITS_PER_INT <= BITS_PER_WORD)
1944     {
1945       if ((CONST_DOUBLE_HIGH (op1) == 0 && CONST_DOUBLE_LOW (op1) >= 0)
1946           || (CONST_DOUBLE_HIGH (op1) == -1 && CONST_DOUBLE_LOW (op1) < 0))
1947         const_op1 = gen_rtx (CONST_INT, VOIDmode, CONST_DOUBLE_LOW (op1));
1948     }
1949
1950   if (GET_CODE (const_op1) == CONST_INT && ! mult_is_very_cheap && optimize)
1951     {
1952       struct algorithm alg;
1953       struct algorithm neg_alg;
1954       int negate = 0;
1955       int absval = INTVAL (op1);
1956       rtx last;
1957
1958       /* Try to do the computation two ways: multiply by the negative of OP1
1959          and then negate, or do the multiplication directly.  The latter is
1960          usually faster for positive numbers and the former for negative
1961          numbers, but the opposite can be faster if the original value
1962          has a factor of 2**m +/- 1, while the negated value does not or
1963          vice versa.  */
1964
1965       alg = synth_mult (absval, add_cost, shift_cost, mult_cost);
1966       neg_alg = synth_mult (- absval, add_cost, shift_cost,
1967                             mult_cost - negate_cost);
1968
1969       if (neg_alg.cost >= 0 && neg_alg.cost + negate_cost < alg.cost)
1970         alg = neg_alg, negate = 1, absval = - absval;
1971
1972       if (alg.cost >= 0)
1973         {
1974           /* If we found something, it must be cheaper than multiply.
1975              So use it.  */
1976           int opno = 0;
1977           rtx accum, tem;
1978           int factors_seen = 0;
1979
1980           op0 = protect_from_queue (op0, 0);
1981
1982           /* Avoid referencing memory over and over.
1983              For speed, but also for correctness when mem is volatile.  */
1984           if (GET_CODE (op0) == MEM)
1985             op0 = force_reg (mode, op0);
1986
1987           if (alg.ops == 0)
1988             accum = copy_to_mode_reg (mode, op0);
1989           else
1990             {
1991               /* 1 if this is the last in a series of adds and subtracts.  */
1992               int last = (1 == alg.ops || alg.op[1] == alg_compound);
1993               int log = floor_log2 (alg.coeff[0]);
1994               if (! factors_seen && ! last)
1995                 log -= floor_log2 (alg.coeff[1]);
1996
1997               if (alg.op[0] != alg_add)
1998                 abort ();
1999               accum = expand_shift (LSHIFT_EXPR, mode, op0,
2000                                     build_int_2 (log, 0),
2001                                     0, 0);
2002             }
2003
2004           while (++opno < alg.ops)
2005             {
2006               int log = floor_log2 (alg.coeff[opno]);
2007               /* 1 if this is the last in a series of adds and subtracts.  */
2008               int last = (opno + 1 == alg.ops
2009                           || alg.op[opno + 1] == alg_compound);
2010
2011               /* If we have not yet seen any separate factors (alg_compound)
2012                  then turn op0<<a1 + op0<<a2 + op0<<a3... into
2013                  (op0<<(a1-a2) + op0)<<(a2-a3) + op0...  */
2014               switch (alg.op[opno])
2015                 {
2016                 case alg_add:
2017                   if (factors_seen)
2018                     {
2019                       tem = expand_shift (LSHIFT_EXPR, mode, op0,
2020                                           build_int_2 (log, 0), 0, 0);
2021                       accum = force_operand (gen_rtx (PLUS, mode, accum, tem),
2022                                              accum);
2023                     }
2024                   else
2025                     {
2026                       if (! last)
2027                         log -= floor_log2 (alg.coeff[opno + 1]);
2028                       accum = force_operand (gen_rtx (PLUS, mode, accum, op0),
2029                                              accum);
2030                       accum = expand_shift (LSHIFT_EXPR, mode, accum,
2031                                             build_int_2 (log, 0), accum, 0);
2032                     }
2033                   break;
2034
2035                 case alg_subtract:
2036                   if (factors_seen)
2037                     {
2038                       tem = expand_shift (LSHIFT_EXPR, mode, op0,
2039                                           build_int_2 (log, 0), 0, 0);
2040                       accum = force_operand (gen_rtx (MINUS, mode, accum, tem),
2041                                              accum);
2042                     }
2043                   else
2044                     {
2045                       if (! last)
2046                         log -= floor_log2 (alg.coeff[opno + 1]);
2047                       accum = force_operand (gen_rtx (MINUS, mode, accum, op0),
2048                                              accum);
2049                       accum = expand_shift (LSHIFT_EXPR, mode, accum,
2050                                             build_int_2 (log, 0), accum, 0);
2051                     }
2052
2053                   break;
2054
2055                 case alg_compound:
2056                   factors_seen = 1;
2057                   tem = expand_shift (LSHIFT_EXPR, mode, accum,
2058                                       build_int_2 (log, 0), 0, 0);
2059
2060                   log = floor_log2 (alg.coeff[opno + 1]);
2061                   accum = expand_shift (LSHIFT_EXPR, mode, accum,
2062                                         build_int_2 (log, 0), 0, 0);
2063                   opno++;
2064                   if (alg.op[opno] == alg_add)
2065                     accum = force_operand (gen_rtx (PLUS, mode, tem, accum),
2066                                            tem);
2067                   else
2068                     accum = force_operand (gen_rtx (MINUS, mode, tem, accum),
2069                                            tem);
2070                 }
2071             }
2072
2073           /* Write a REG_EQUAL note on the last insn so that we can cse
2074              multiplication sequences.  We need not do this if we were
2075              multiplying by a power of two, since only one insn would have
2076              been generated.
2077
2078              ??? We could also write REG_EQUAL notes on the last insn of
2079              each sequence that uses a single temporary, but it is not
2080              clear how to calculate the partial product so far.
2081
2082              Torbjorn: Can you do this?  */
2083
2084           if (exact_log2 (absval) < 0)
2085             {
2086               last = get_last_insn ();
2087               REG_NOTES (last)
2088                 = gen_rtx (EXPR_LIST, REG_EQUAL,
2089                            gen_rtx (MULT, mode, op0,
2090                                     negate ? gen_rtx (CONST_INT,
2091                                                       VOIDmode, absval)
2092                                     : op1),
2093                            REG_NOTES (last));
2094             }
2095
2096           return (negate ? expand_unop (mode, neg_optab, accum, target, 0)
2097                   : accum);
2098         }
2099     }
2100
2101   /* This used to use umul_optab if unsigned,
2102      but I think that for non-widening multiply there is no difference
2103      between signed and unsigned.  */
2104   op0 = expand_binop (mode, smul_optab,
2105                       op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2106   if (op0 == 0)
2107     abort ();
2108   return op0;
2109 }
2110 \f
2111 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2112    if that is convenient, and returning where the result is.
2113    You may request either the quotient or the remainder as the result;
2114    specify REM_FLAG nonzero to get the remainder.
2115
2116    CODE is the expression code for which kind of division this is;
2117    it controls how rounding is done.  MODE is the machine mode to use.
2118    UNSIGNEDP nonzero means do unsigned division.  */
2119
2120 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2121    and then correct it by or'ing in missing high bits
2122    if result of ANDI is nonzero.
2123    For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2124    This could optimize to a bfexts instruction.
2125    But C doesn't use these operations, so their optimizations are
2126    left for later.  */
2127
2128 rtx
2129 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2130      int rem_flag;
2131      enum tree_code code;
2132      enum machine_mode mode;
2133      register rtx op0, op1, target;
2134      int unsignedp;
2135 {
2136   register rtx result = 0;
2137   enum machine_mode compute_mode;
2138   int log = -1;
2139   int can_clobber_op0;
2140   int mod_insn_no_good = 0;
2141   rtx adjusted_op0 = op0;
2142   optab optab1, optab2;
2143
2144   /* Don't use the function value register as a target
2145      since we have to read it as well as write it,
2146      and function-inlining gets confused by this.  */
2147   if (target && REG_P (target) && REG_FUNCTION_VALUE_P (target))
2148     target = 0;
2149
2150   /* Don't clobber an operand while doing a multi-step calculation.  */
2151   if (target)
2152     if ((rem_flag && (reg_mentioned_p (target, op0)
2153                       || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
2154         || reg_mentioned_p (target, op1)
2155         || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM))
2156       target = 0;
2157
2158   can_clobber_op0 = (GET_CODE (op0) == REG && op0 == target);
2159
2160   if (GET_CODE (op1) == CONST_INT)
2161     log = exact_log2 (INTVAL (op1));
2162
2163   /* If log is >= 0, we are dividing by 2**log, and will do it by shifting,
2164      which is really floor-division.  Otherwise we will really do a divide,
2165      and we assume that is trunc-division.
2166
2167      We must correct the dividend by adding or subtracting something
2168      based on the divisor, in order to do the kind of rounding specified
2169      by CODE.  The correction depends on what kind of rounding is actually
2170      available, and that depends on whether we will shift or divide.
2171
2172      In many of these cases it is possible to perform the operation by a
2173      clever series of logical operations (shifts and/or exclusive-ors).
2174      Although avoiding the jump has the advantage that it extends the basic
2175      block and allows further optimization, the branch-free code is normally
2176      at least one instruction longer in the (most common) case where the
2177      dividend is non-negative.  Performance measurements of the two
2178      alternatives show that the branch-free code is slightly faster on the
2179      IBM ROMP but slower on CISC processors (significantly slower on the
2180      VAX).  Accordingly, the jump code has been retained.
2181
2182      On machines where the jump code is slower, the cost of a DIV or MOD
2183      operation can be set small (less than twice that of an addition); in
2184      that case, we pretend that we don't have a power of two and perform
2185      a normal division or modulus operation.  */
2186
2187   if ((code == TRUNC_MOD_EXPR || code == TRUNC_DIV_EXPR)
2188       && ! unsignedp
2189       && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap))
2190     log = -1;
2191
2192   /* Get the mode in which to perform this computation.  Normally it will
2193      be MODE, but sometimes we can't do the desired operation in MODE.
2194      If so, pick a wider mode in which we can do the operation.  Convert
2195      to that mode at the start to avoid repeated conversions.
2196
2197      First see what operations we need.  These depend on the expression
2198      we are evaluating.  (We assume that divxx3 insns exist under the
2199      same conditions that modxx3 insns and that these insns don't normally
2200      fail.  If these assumptions are not correct, we may generate less
2201      efficient code in some cases.)
2202
2203      Then see if we find a mode in which we can open-code that operation
2204      (either a division, modulus, or shift).  Finally, check for the smallest
2205      mode for which we can do the operation with a library call.  */
2206
2207   optab1 = (log >= 0 ? (unsignedp ? lshr_optab : ashr_optab)
2208             : (unsignedp ? udiv_optab : sdiv_optab));
2209   optab2 = (log >= 0 ? optab1 : (unsignedp ? udivmod_optab : sdivmod_optab));
2210
2211   for (compute_mode = mode; compute_mode != VOIDmode;
2212        compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2213     if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
2214         || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
2215       break;
2216
2217   if (compute_mode == VOIDmode)
2218     for (compute_mode = mode; compute_mode != VOIDmode;
2219          compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2220       if (optab1->handlers[(int) compute_mode].libfunc
2221           || optab2->handlers[(int) compute_mode].libfunc)
2222         break;
2223
2224   /* If we still couldn't find a mode, use MODE; we'll probably abort in
2225      expand_binop.  */
2226   if (compute_mode == VOIDmode)
2227     compute_mode = mode;
2228
2229   /* Now convert to the best mode to use.  Show we made a copy of OP0
2230      and hence we can clobber it (we cannot use a SUBREG to widen
2231      something.  */
2232   if (compute_mode != mode)
2233     {
2234       adjusted_op0 = op0 = convert_to_mode (compute_mode, op0, unsignedp);
2235       can_clobber_op0 = 1;
2236       op1 = convert_to_mode (compute_mode, op1, unsignedp);
2237     }
2238
2239   if (target == 0 || GET_MODE (target) != compute_mode)
2240     target = gen_reg_rtx (compute_mode);
2241
2242   switch (code)
2243     {
2244     case TRUNC_MOD_EXPR:
2245     case TRUNC_DIV_EXPR:
2246       if (log >= 0 && ! unsignedp)
2247         {
2248           rtx label = gen_label_rtx ();
2249           if (! can_clobber_op0)
2250             {
2251               adjusted_op0 = copy_to_suggested_reg (adjusted_op0, target,
2252                                                     compute_mode);
2253               /* Copy op0 to a reg, since emit_cmp_insn will call emit_queue
2254                  which will screw up mem refs for autoincrements.  */
2255               op0 = force_reg (compute_mode, op0);
2256             }
2257           emit_cmp_insn (adjusted_op0, const0_rtx, GE, 0, compute_mode, 0, 0);
2258           emit_jump_insn (gen_bge (label));
2259           expand_inc (adjusted_op0, plus_constant (op1, -1));
2260           emit_label (label);
2261           mod_insn_no_good = 1;
2262         }
2263       break;
2264
2265     case FLOOR_DIV_EXPR:
2266     case FLOOR_MOD_EXPR:
2267       if (log < 0 && ! unsignedp)
2268         {
2269           rtx label = gen_label_rtx ();
2270           if (! can_clobber_op0)
2271             {
2272               adjusted_op0 = copy_to_suggested_reg (adjusted_op0, target,
2273                                                     compute_mode);
2274               /* Copy op0 to a reg, since emit_cmp_insn will call emit_queue
2275                  which will screw up mem refs for autoincrements.  */
2276               op0 = force_reg (compute_mode, op0);
2277             }
2278           emit_cmp_insn (adjusted_op0, const0_rtx, GE, 0, compute_mode, 0, 0);
2279           emit_jump_insn (gen_bge (label));
2280           expand_dec (adjusted_op0, op1);
2281           expand_inc (adjusted_op0, const1_rtx);
2282           emit_label (label);
2283           mod_insn_no_good = 1;
2284         }
2285       break;
2286
2287     case CEIL_DIV_EXPR:
2288     case CEIL_MOD_EXPR:
2289       if (! can_clobber_op0)
2290         {
2291           adjusted_op0 = copy_to_suggested_reg (adjusted_op0, target,
2292                                                 compute_mode);
2293           /* Copy op0 to a reg, since emit_cmp_insn will call emit_queue
2294              which will screw up mem refs for autoincrements.  */
2295           op0 = force_reg (compute_mode, op0);
2296         }
2297       if (log < 0)
2298         {
2299           rtx label = 0;
2300           if (! unsignedp)
2301             {
2302               label = gen_label_rtx ();
2303               emit_cmp_insn (adjusted_op0, const0_rtx, LE, 0, compute_mode, 0, 0);
2304               emit_jump_insn (gen_ble (label));
2305             }
2306           expand_inc (adjusted_op0, op1);
2307           expand_dec (adjusted_op0, const1_rtx);
2308           if (! unsignedp)
2309             emit_label (label);
2310         }
2311       else
2312         {
2313           adjusted_op0 = expand_binop (compute_mode, add_optab,
2314                                        adjusted_op0, plus_constant (op1, -1),
2315                                        0, 0, OPTAB_LIB_WIDEN);
2316         }
2317       mod_insn_no_good = 1;
2318       break;
2319
2320     case ROUND_DIV_EXPR:
2321     case ROUND_MOD_EXPR:
2322       if (! can_clobber_op0)
2323         {
2324           adjusted_op0 = copy_to_suggested_reg (adjusted_op0, target,
2325                                                 compute_mode);
2326           /* Copy op0 to a reg, since emit_cmp_insn will call emit_queue
2327              which will screw up mem refs for autoincrements.  */
2328           op0 = force_reg (compute_mode, op0);
2329         }
2330       if (log < 0)
2331         {
2332           op1 = expand_shift (RSHIFT_EXPR, compute_mode, op1,
2333                               integer_one_node, 0, 0);
2334           if (! unsignedp)
2335             {
2336               rtx label = gen_label_rtx ();
2337               emit_cmp_insn (adjusted_op0, const0_rtx, GE, 0, compute_mode, 0, 0);
2338               emit_jump_insn (gen_bge (label));
2339               expand_unop (compute_mode, neg_optab, op1, op1, 0);
2340               emit_label (label);
2341             }
2342           expand_inc (adjusted_op0, op1);
2343         }
2344       else
2345         {
2346           op1 = gen_rtx (CONST_INT, VOIDmode, (1 << log) / 2);
2347           expand_inc (adjusted_op0, op1);
2348         }
2349       mod_insn_no_good = 1;
2350       break;
2351     }
2352
2353   if (rem_flag && !mod_insn_no_good)
2354     {
2355       /* Try to produce the remainder directly */
2356       if (log >= 0)
2357         result = expand_binop (compute_mode, and_optab, adjusted_op0,
2358                                gen_rtx (CONST_INT, VOIDmode,
2359                                         (1 << log) - 1),
2360                                target, 1, OPTAB_LIB_WIDEN);
2361       else
2362         {
2363           /* See if we can do remainder without a library call.  */
2364           result = sign_expand_binop (mode, umod_optab, smod_optab,
2365                                       adjusted_op0, op1, target,
2366                                       unsignedp, OPTAB_WIDEN);
2367           if (result == 0)
2368             {
2369               /* No luck there.  Can we do remainder and divide at once
2370                  without a library call?  */
2371               result = gen_reg_rtx (compute_mode);
2372               if (! expand_twoval_binop (unsignedp
2373                                          ? udivmod_optab : sdivmod_optab,
2374                                          adjusted_op0, op1,
2375                                          0, result, unsignedp))
2376                 result = 0;
2377             }
2378         }
2379     }
2380
2381   if (result)
2382     return gen_lowpart (mode, result);
2383
2384   /* Produce the quotient.  */
2385   if (log >= 0)
2386     result = expand_shift (RSHIFT_EXPR, compute_mode, adjusted_op0,
2387                            build_int_2 (log, 0), target, unsignedp);
2388   else if (rem_flag && !mod_insn_no_good)
2389     /* If producing quotient in order to subtract for remainder,
2390        and a remainder subroutine would be ok,
2391        don't use a divide subroutine.  */
2392     result = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
2393                                 adjusted_op0, op1, 0, unsignedp, OPTAB_WIDEN);
2394   else
2395     {
2396       /* Try a quotient insn, but not a library call.  */
2397       result = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
2398                                   adjusted_op0, op1, rem_flag ? 0 : target,
2399                                   unsignedp, OPTAB_WIDEN);
2400       if (result == 0)
2401         {
2402           /* No luck there.  Try a quotient-and-remainder insn,
2403              keeping the quotient alone.  */
2404           result = gen_reg_rtx (mode);
2405           if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
2406                                      adjusted_op0, op1,
2407                                      result, 0, unsignedp))
2408             result = 0;
2409         }
2410
2411       /* If still no luck, use a library call.  */
2412       if (result == 0)
2413         result = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
2414                                     adjusted_op0, op1, rem_flag ? 0 : target,
2415                                     unsignedp, OPTAB_LIB_WIDEN);
2416     }
2417
2418   /* If we really want the remainder, get it by subtraction.  */
2419   if (rem_flag)
2420     {
2421       if (result == 0)
2422         /* No divide instruction either.  Use library for remainder.  */
2423         result = sign_expand_binop (compute_mode, umod_optab, smod_optab,
2424                                     op0, op1, target,
2425                                     unsignedp, OPTAB_LIB_WIDEN);
2426       else
2427         {
2428           /* We divided.  Now finish doing X - Y * (X / Y).  */
2429           result = expand_mult (compute_mode, result, op1, target, unsignedp);
2430           if (! result) abort ();
2431           result = expand_binop (compute_mode, sub_optab, op0,
2432                                  result, target, unsignedp, OPTAB_LIB_WIDEN);
2433         }
2434     }
2435
2436   if (result == 0)
2437     abort ();
2438
2439   return gen_lowpart (mode, result);
2440 }
2441 \f
2442 /* Return a tree node with data type TYPE, describing the value of X.
2443    Usually this is an RTL_EXPR, if there is no obvious better choice.
2444    X may be an expression, however we only support those expressions
2445    generated by loop.c.   */
2446
2447 tree
2448 make_tree (type, x)
2449      tree type;
2450      rtx x;
2451 {
2452   tree t;
2453
2454   switch (GET_CODE (x))
2455     {
2456     case CONST_INT:
2457       t = build_int_2 (INTVAL (x),
2458                        ! TREE_UNSIGNED (type) && INTVAL (x) >= 0 ? 0 : -1);
2459       TREE_TYPE (t) = type;
2460       return t;
2461
2462     case CONST_DOUBLE:
2463       if (GET_MODE (x) == VOIDmode)
2464         {
2465           t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
2466           TREE_TYPE (t) = type;
2467         }
2468       else
2469         {
2470           REAL_VALUE_TYPE d;
2471
2472           REAL_VALUE_FROM_CONST_DOUBLE (d, x);
2473           t = build_real (type, d);
2474         }
2475
2476       return t;
2477
2478     case PLUS:
2479       return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
2480                           make_tree (type, XEXP (x, 1))));
2481
2482     case MINUS:
2483       return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
2484                           make_tree (type, XEXP (x, 1))));
2485
2486     case NEG:
2487       return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
2488
2489     case MULT:
2490       return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
2491                           make_tree (type, XEXP (x, 1))));
2492
2493     case ASHIFT:
2494       return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
2495                           make_tree (type, XEXP (x, 1))));
2496
2497     case LSHIFTRT:
2498       return fold (convert (type,
2499                             build (RSHIFT_EXPR, unsigned_type (type),
2500                                    make_tree (unsigned_type (type),
2501                                               XEXP (x, 0)),
2502                                    make_tree (type, XEXP (x, 1)))));
2503
2504     case ASHIFTRT:
2505       return fold (convert (type,
2506                             build (RSHIFT_EXPR, signed_type (type),
2507                                    make_tree (signed_type (type), XEXP (x, 0)),
2508                                    make_tree (type, XEXP (x, 1)))));
2509
2510     case DIV:
2511       if (TREE_CODE (type) != REAL_TYPE)
2512         t = signed_type (type);
2513       else
2514         t = type;
2515
2516       return fold (convert (type,
2517                             build (TRUNC_DIV_EXPR, t,
2518                                    make_tree (t, XEXP (x, 0)),
2519                                    make_tree (t, XEXP (x, 1)))));
2520     case UDIV:
2521       t = unsigned_type (type);
2522       return fold (convert (type,
2523                             build (TRUNC_DIV_EXPR, t,
2524                                    make_tree (t, XEXP (x, 0)),
2525                                    make_tree (t, XEXP (x, 1)))));
2526    default:
2527       t = make_node (RTL_EXPR);
2528       TREE_TYPE (t) = type;
2529       RTL_EXPR_RTL (t) = x;
2530       /* There are no insns to be output
2531          when this rtl_expr is used.  */
2532       RTL_EXPR_SEQUENCE (t) = 0;
2533       return t;
2534     }
2535 }
2536
2537 /* Return an rtx representing the value of X * MULT + ADD.
2538    TARGET is a suggestion for where to store the result (an rtx).
2539    MODE is the machine mode for the computation.
2540    X and MULT must have mode MODE.  ADD may have a different mode.
2541    So can X (defaults to same as MODE).
2542    UNSIGNEDP is non-zero to do unsigned multiplication.
2543    This may emit insns.  */
2544
2545 rtx
2546 expand_mult_add (x, target, mult, add, mode, unsignedp)
2547      rtx x, target, mult, add;
2548      enum machine_mode mode;
2549      int unsignedp;
2550 {
2551   tree type = type_for_mode (mode, unsignedp);
2552   tree add_type = (GET_MODE (add) == VOIDmode
2553                    ? type : type_for_mode (GET_MODE (add), unsignedp));
2554   tree result =  fold (build (PLUS_EXPR, type,
2555                               fold (build (MULT_EXPR, type,
2556                                            make_tree (type, x),
2557                                            make_tree (type, mult))),
2558                               make_tree (add_type, add)));
2559
2560   return expand_expr (result, target, VOIDmode, 0);
2561 }
2562 \f
2563 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
2564    and returning TARGET.
2565
2566    If TARGET is 0, a pseudo-register or constant is returned.  */
2567
2568 rtx
2569 expand_and (op0, op1, target)
2570      rtx op0, op1, target;
2571 {
2572   enum machine_mode mode = VOIDmode;
2573   rtx tem;
2574
2575   if (GET_MODE (op0) != VOIDmode)
2576     mode = GET_MODE (op0);
2577   else if (GET_MODE (op1) != VOIDmode)
2578     mode = GET_MODE (op1);
2579
2580   if (mode != VOIDmode)
2581     tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
2582   else if (GET_CODE (op0) == CONST_INT && GET_CODE (op1) == CONST_INT)
2583     tem = gen_rtx (CONST_INT, VOIDmode, INTVAL (op0) & INTVAL (op1));
2584   else
2585     abort ();
2586
2587   if (target == 0)
2588     target = tem;
2589   else if (tem != target)
2590     emit_move_insn (target, tem);
2591   return target;
2592 }
2593 \f
2594 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
2595    and storing in TARGET.  Normally return TARGET.
2596    Return 0 if that cannot be done.
2597
2598    MODE is the mode to use for OP0 and OP1 should they be CONST_INTs.  If
2599    it is VOIDmode, they cannot both be CONST_INT.
2600
2601    UNSIGNEDP is for the case where we have to widen the operands
2602    to perform the operation.  It says to use zero-extension.
2603
2604    NORMALIZEP is 1 if we should convert the result to be either zero
2605    or one one.  Normalize is -1 if we should convert the result to be
2606    either zero or -1.  If NORMALIZEP is zero, the result will be left
2607    "raw" out of the scc insn.  */
2608
2609 rtx
2610 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
2611      rtx target;
2612      enum rtx_code code;
2613      rtx op0, op1;
2614      enum machine_mode mode;
2615      int unsignedp;
2616      int normalizep;
2617 {
2618   rtx subtarget;
2619   enum insn_code icode;
2620   enum machine_mode compare_mode;
2621   enum machine_mode target_mode = GET_MODE (target);
2622   rtx tem;
2623   rtx last = 0;
2624   rtx pattern, comparison;
2625
2626   if (mode == VOIDmode)
2627     mode = GET_MODE (op0);
2628
2629   /* For some comparisons with 1 and -1, we can convert this to
2630      comparisons with zero.  This will often produce more opportunities for
2631      store-flag insns. */
2632
2633   switch (code)
2634     {
2635     case LT:
2636       if (op1 == const1_rtx)
2637         op1 = const0_rtx, code = LE;
2638       break;
2639     case LE:
2640       if (op1 == constm1_rtx)
2641         op1 = const0_rtx, code = LT;
2642       break;
2643     case GE:
2644       if (op1 == const1_rtx)
2645         op1 = const0_rtx, code = GT;
2646       break;
2647     case GT:
2648       if (op1 == constm1_rtx)
2649         op1 = const0_rtx, code = GE;
2650       break;
2651     case GEU:
2652       if (op1 == const1_rtx)
2653         op1 = const0_rtx, code = NE;
2654       break;
2655     case LTU:
2656       if (op1 == const1_rtx)
2657         op1 = const0_rtx, code = EQ;
2658       break;
2659     }
2660
2661   /* From now on, we won't change CODE, so set ICODE now.  */
2662   icode = setcc_gen_code[(int) code];
2663
2664   /* If this is A < 0 or A >= 0, we can do this by taking the ones
2665      complement of A (for GE) and shifting the sign bit to the low bit.  */
2666   if (op1 == const0_rtx && (code == LT || code == GE)
2667       && GET_MODE_CLASS (mode) == MODE_INT
2668       && (normalizep || STORE_FLAG_VALUE == 1
2669           || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_INT
2670               && STORE_FLAG_VALUE == 1 << (GET_MODE_BITSIZE (mode) - 1))))
2671     {
2672       rtx subtarget = target;
2673
2674       /* If the result is to be wider than OP0, it is best to convert it
2675          first.  If it is to be narrower, it is *incorrect* to convert it
2676          first.  */
2677       if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
2678         {
2679           op0 = convert_to_mode (target_mode, op0, 0);
2680           mode = target_mode;
2681         }
2682
2683       if (target_mode != mode)
2684         subtarget = 0;
2685
2686       if (code == GE)
2687         op0 = expand_unop (mode, one_cmpl_optab, op0, subtarget, 0);
2688
2689       if (normalizep || STORE_FLAG_VALUE == 1)
2690         /* If we are supposed to produce a 0/1 value, we want to do
2691            a logical shift from the sign bit to the low-order bit; for
2692            a -1/0 value, we do an arithmetic shift.  */
2693         op0 = expand_shift (RSHIFT_EXPR, mode, op0,
2694                             size_int (GET_MODE_BITSIZE (mode) - 1),
2695                             subtarget, normalizep != -1);
2696
2697       if (mode != target_mode)
2698         op0 = convert_to_mode (target_mode, op0, 0);
2699
2700       return op0;
2701     }
2702
2703   if (icode != CODE_FOR_nothing)
2704     {
2705       /* We think we may be able to do this with a scc insn.  Emit the
2706          comparison and then the scc insn.
2707
2708          compare_from_rtx may call emit_queue, which would be deleted below
2709          if the scc insn fails.  So call it ourselves before setting LAST.  */
2710
2711       emit_queue ();
2712       last = get_last_insn ();
2713
2714       comparison = compare_from_rtx (op0, op1, code, unsignedp, mode, 0, 0);
2715       if (GET_CODE (comparison) == CONST_INT)
2716         return (comparison == const0_rtx ? const0_rtx
2717                 : normalizep == 1 ? const1_rtx
2718                 : normalizep == -1 ? constm1_rtx
2719                 : const_true_rtx);
2720
2721       /* Get a reference to the target in the proper mode for this insn.  */
2722       compare_mode = insn_operand_mode[(int) icode][0];
2723       subtarget = target;
2724       if (preserve_subexpressions_p ()
2725           || ! (*insn_operand_predicate[(int) icode][0]) (subtarget, compare_mode))
2726         subtarget = gen_reg_rtx (compare_mode);
2727
2728       pattern = GEN_FCN (icode) (subtarget);
2729       if (pattern)
2730         {
2731           emit_insn (pattern);
2732
2733           /* If we are converting to a wider mode, first convert to
2734              TARGET_MODE, then normalize.  This produces better combining
2735              opportunities on machines that have a SIGN_EXTRACT when we are
2736              testing a single bit.  This mostly benefits the 68k.
2737
2738              If STORE_FLAG_VALUE does not have the sign bit set when
2739              interpreted in COMPARE_MODE, we can do this conversion as
2740              unsigned, which is usually more efficient.  */
2741           if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
2742             {
2743               convert_move (target, subtarget,
2744                             (GET_MODE_BITSIZE (compare_mode)
2745                              <= HOST_BITS_PER_INT)
2746                             && 0 == (STORE_FLAG_VALUE
2747                                      & (1 << (GET_MODE_BITSIZE (compare_mode) -1))));
2748               op0 = target;
2749               compare_mode = target_mode;
2750             }
2751           else
2752             op0 = subtarget;
2753
2754           /* Now normalize to the proper value in COMPARE_MODE.  Sometimes
2755              we don't have to do anything.  */
2756           if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
2757             ;
2758           else if (normalizep == - STORE_FLAG_VALUE)
2759             op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
2760
2761           /* We don't want to use STORE_FLAG_VALUE < 0 below since this
2762              makes it hard to use a value of just the sign bit due to
2763              ANSI integer constant typing rules.  */
2764           else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_INT
2765                    && (STORE_FLAG_VALUE
2766                        & (1 << (GET_MODE_BITSIZE (compare_mode) - 1))))
2767             op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
2768                                 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
2769                                 subtarget, normalizep == 1);
2770           else if (STORE_FLAG_VALUE & 1)
2771             {
2772               op0 = expand_and (op0, const1_rtx, subtarget);
2773               if (normalizep == -1)
2774                 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
2775             }
2776           else
2777             abort ();
2778
2779           /* If we were converting to a smaller mode, do the
2780              conversion now.  */
2781           if (target_mode != compare_mode)
2782             {
2783               convert_move (target, op0);
2784               return target;
2785             }
2786           else
2787             return op0;
2788         }
2789     }
2790
2791   if (last)
2792     delete_insns_since (last);
2793
2794   subtarget = target_mode == mode ? target : 0;
2795
2796   /* If we reached here, we can't do this with a scc insn.  However, there
2797      are some comparisons that can be done directly.  For example, if
2798      this is an equality comparison of integers, we can try to exclusive-or
2799      (or subtract) the two operands and use a recursive call to try the
2800      comparison with zero.  Don't do any of these cases if branches are
2801      very cheap.  */
2802
2803   if (BRANCH_COST >= 0
2804       && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
2805       && op1 != const0_rtx)
2806     {
2807       tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
2808                           OPTAB_WIDEN);
2809
2810       if (tem == 0)
2811         tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
2812                             OPTAB_WIDEN);
2813       if (tem != 0)
2814         tem = emit_store_flag (target, code, tem, const0_rtx,
2815                                mode, unsignedp, normalizep);
2816       if (tem == 0)
2817         delete_insns_since (last);
2818       return tem;
2819     }
2820
2821   /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
2822      the constant zero.  Reject all other comparisons at this point.  Only
2823      do LE and GT if branches are expensive since they are expensive on
2824      2-operand machines.  */
2825
2826   if (BRANCH_COST == 0
2827       || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
2828       || (code != EQ && code != NE
2829           && (BRANCH_COST <= 1 || (code != LE && code != GT))))
2830     return 0;
2831
2832   /* See what we need to return.  We can only return a 1, -1, or the
2833      sign bit.  */
2834
2835   if (normalizep == 0)
2836     {
2837       if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
2838         normalizep = STORE_FLAG_VALUE;
2839
2840       else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_INT
2841                && STORE_FLAG_VALUE == 1 << (GET_MODE_BITSIZE (mode) - 1))
2842         ;
2843       else
2844         return 0;
2845     }
2846
2847   /* Try to put the result of the comparison in the sign bit.  Assume we can't
2848      do the necessary operation below.  */
2849
2850   tem = 0;
2851
2852   /* To see if A <= 0, compute (A | (A - 1)).  A <= 0 iff that result has
2853      the sign bit set.  */
2854
2855   if (code == LE)
2856     {
2857       /* This is destructive, so SUBTARGET can't be OP0.  */
2858       if (rtx_equal_p (subtarget, op0))
2859         subtarget = 0;
2860
2861       tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
2862                           OPTAB_WIDEN);
2863       if (tem)
2864         tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
2865                             OPTAB_WIDEN);
2866     }
2867
2868   /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
2869      number of bits in the mode of OP0, minus one.  */
2870
2871   if (code == GT)
2872     {
2873       if (rtx_equal_p (subtarget, op0))
2874         subtarget = 0;
2875
2876       tem = expand_shift (RSHIFT_EXPR, mode, op0,
2877                           size_int (GET_MODE_BITSIZE (mode) - 1),
2878                           subtarget, 0);
2879       tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
2880                           OPTAB_WIDEN);
2881     }
2882
2883   if (code == EQ || code == NE)
2884     {
2885       /* For EQ or NE, one way to do the comparison is to apply an operation
2886          that converts the operand into a positive number if it is non-zero
2887          or zero if it was originally zero.  Then, for EQ, we subtract 1 and
2888          for NE we negate.  This puts the result in the sign bit.  Then we
2889          normalize with a shift, if needed.
2890
2891          Two operations that can do the above actions are ABS and FFS, so try
2892          them.  If that doesn't work, and MODE is smaller than a full word,
2893          we can use zero-extension to the wider mode (an unsigned conversion)
2894          as the operation.  */
2895
2896       if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
2897         tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
2898       else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
2899         tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
2900       else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
2901         {
2902           mode = word_mode;
2903           tem = convert_to_mode (mode, op0, 1);
2904         }
2905
2906       if (tem != 0)
2907         {
2908           if (code == EQ)
2909             tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
2910                                 0, OPTAB_WIDEN);
2911           else
2912             tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
2913         }
2914
2915       /* If we couldn't do it that way, for NE we can "or" the two's complement
2916          of the value with itself.  For EQ, we take the one's complement of
2917          that "or", which is an extra insn, so we only handle EQ if branches
2918          are expensive.  */
2919
2920       if (tem == 0 && (code == NE || BRANCH_COST > 1))
2921         {
2922           if (rtx_equal_p (subtarget, op0))
2923             subtarget = 0;
2924
2925           tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
2926           tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
2927                               OPTAB_WIDEN);
2928
2929           if (tem && code == EQ)
2930             tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
2931         }
2932     }
2933
2934   if (tem && normalizep)
2935     tem = expand_shift (RSHIFT_EXPR, mode, tem,
2936                         size_int (GET_MODE_BITSIZE (mode) - 1),
2937                         tem, normalizep == 1);
2938
2939   if (tem && GET_MODE (tem) != target_mode)
2940     {
2941       convert_move (target, tem, 0);
2942       tem = target;
2943     }
2944
2945   if (tem == 0)
2946     delete_insns_since (last);
2947
2948   return tem;
2949 }
2950   emit_jump_insn ((*bcc_gen_fctn[(int) code]) (label));
2951   emit_move_insn (target, const1_rtx);
2952   emit_label (label);
2953
2954   return target;
2955 }