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