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