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, 88, 89, 92-97, 1998 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, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "toplev.h"
  26 #include "rtl.h"
  27 #include "tree.h"
  28 #include "flags.h"
  29 #include "insn-flags.h"
  30 #include "insn-codes.h"
  31 #include "insn-config.h"
  32 #include "expr.h"
  33 #include "real.h"
  34 #include "recog.h"
  35
  36 static void store_fixed_bit_field       PROTO((rtx, int, int, int, rtx, int));
  37 static void store_split_bit_field       PROTO((rtx, int, int, rtx, int));
  38 static rtx extract_fixed_bit_field      PROTO((enum machine_mode, rtx, int,
  39                                                int, int, rtx, int, int));
  40 static rtx mask_rtx                     PROTO((enum machine_mode, int,
  41                                                int, int));
  42 static rtx lshift_value                 PROTO((enum machine_mode, rtx,
  43                                                int, int));
  44 static rtx extract_split_bit_field      PROTO((rtx, int, int, int, int));
  45 static void do_cmp_and_jump             PROTO((rtx, rtx, enum rtx_code,
  46                                                enum machine_mode, rtx));
  47
  48 #define CEIL(x,y) (((x) + (y) - 1) / (y))
  49
  50 /* Non-zero means divides or modulus operations are relatively cheap for
  51    powers of two, so don't use branches; emit the operation instead.
  52    Usually, this will mean that the MD file will emit non-branch
  53    sequences.  */
  54
  55 static int sdiv_pow2_cheap, smod_pow2_cheap;
  56
  57 #ifndef SLOW_UNALIGNED_ACCESS
  58 #define SLOW_UNALIGNED_ACCESS STRICT_ALIGNMENT
  59 #endif
  60
  61 /* For compilers that support multiple targets with different word sizes,
  62    MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD.  An example
  63    is the H8/300(H) compiler.  */
  64
  65 #ifndef MAX_BITS_PER_WORD
  66 #define MAX_BITS_PER_WORD BITS_PER_WORD
  67 #endif
  68
  69 /* Cost of various pieces of RTL.  Note that some of these are indexed by shift count,
  70    and some by mode.  */
  71 static int add_cost, negate_cost, zero_cost;
  72 static int shift_cost[MAX_BITS_PER_WORD];
  73 static int shiftadd_cost[MAX_BITS_PER_WORD];
  74 static int shiftsub_cost[MAX_BITS_PER_WORD];
  75 static int mul_cost[NUM_MACHINE_MODES];
  76 static int div_cost[NUM_MACHINE_MODES];
  77 static int mul_widen_cost[NUM_MACHINE_MODES];
  78 static int mul_highpart_cost[NUM_MACHINE_MODES];
  79
  80 void
  81 init_expmed ()
  82 {
  83   char *free_point;
  84   /* This is "some random pseudo register" for purposes of calling recog
  85      to see what insns exist.  */
  86   rtx reg = gen_rtx_REG (word_mode, 10000);
  87   rtx shift_insn, shiftadd_insn, shiftsub_insn;
  88   int dummy;
  89   int m;
  90   enum machine_mode mode, wider_mode;
  91
  92   start_sequence ();
  93
  94   /* Since we are on the permanent obstack, we must be sure we save this
  95      spot AFTER we call start_sequence, since it will reuse the rtl it
  96      makes.  */
  97   free_point = (char *) oballoc (0);
  98
  99   reg = gen_rtx (REG, word_mode, 10000);
 100
 101   zero_cost = rtx_cost (const0_rtx, 0);
 102   add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
 103
 104   shift_insn = emit_insn (gen_rtx_SET (VOIDmode, reg,
 105                                        gen_rtx_ASHIFT (word_mode, reg,
 106                                                        const0_rtx)));
 107
 108   shiftadd_insn
 109     = emit_insn (gen_rtx_SET (VOIDmode, reg,
 110                               gen_rtx_PLUS (word_mode,
 111                                             gen_rtx_MULT (word_mode,
 112                                                           reg, const0_rtx),
 113                                             reg)));
 114
 115   shiftsub_insn
 116     = emit_insn (gen_rtx_SET (VOIDmode, reg,
 117                               gen_rtx_MINUS (word_mode,
 118                                              gen_rtx_MULT (word_mode,
 119                                                            reg, const0_rtx),
 120                                              reg)));
 121
 122   init_recog ();
 123
 124   shift_cost[0] = 0;
 125   shiftadd_cost[0] = shiftsub_cost[0] = add_cost;
 126
 127   for (m = 1; m < MAX_BITS_PER_WORD; m++)
 128     {
 129       shift_cost[m] = shiftadd_cost[m] = shiftsub_cost[m] = 32000;
 130
 131       XEXP (SET_SRC (PATTERN (shift_insn)), 1) = GEN_INT (m);
 132       if (recog (PATTERN (shift_insn), shift_insn, &dummy) >= 0)
 133         shift_cost[m] = rtx_cost (SET_SRC (PATTERN (shift_insn)), SET);
 134
 135       XEXP (XEXP (SET_SRC (PATTERN (shiftadd_insn)), 0), 1)
 136         = GEN_INT ((HOST_WIDE_INT) 1 << m);
 137       if (recog (PATTERN (shiftadd_insn), shiftadd_insn, &dummy) >= 0)
 138         shiftadd_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftadd_insn)), SET);
 139
 140       XEXP (XEXP (SET_SRC (PATTERN (shiftsub_insn)), 0), 1)
 141         = GEN_INT ((HOST_WIDE_INT) 1 << m);
 142       if (recog (PATTERN (shiftsub_insn), shiftsub_insn, &dummy) >= 0)
 143         shiftsub_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftsub_insn)), SET);
 144     }
 145
 146   negate_cost = rtx_cost (gen_rtx_NEG (word_mode, reg), SET);
 147
 148   sdiv_pow2_cheap
 149     = (rtx_cost (gen_rtx_DIV (word_mode, reg, GEN_INT (32)), SET)
 150        <= 2 * add_cost);
 151   smod_pow2_cheap
 152     = (rtx_cost (gen_rtx_MOD (word_mode, reg, GEN_INT (32)), SET)
 153        <= 2 * add_cost);
 154
 155   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
 156        mode != VOIDmode;
 157        mode = GET_MODE_WIDER_MODE (mode))
 158     {
 159       reg = gen_rtx_REG (mode, 10000);
 160       div_cost[(int) mode] = rtx_cost (gen_rtx_UDIV (mode, reg, reg), SET);
 161       mul_cost[(int) mode] = rtx_cost (gen_rtx_MULT (mode, reg, reg), SET);
 162       wider_mode = GET_MODE_WIDER_MODE (mode);
 163       if (wider_mode != VOIDmode)
 164         {
 165           mul_widen_cost[(int) wider_mode]
 166             = rtx_cost (gen_rtx_MULT (wider_mode,
 167                                       gen_rtx_ZERO_EXTEND (wider_mode, reg),
 168                                       gen_rtx_ZERO_EXTEND (wider_mode, reg)),
 169                         SET);
 170           mul_highpart_cost[(int) mode]
 171             = rtx_cost (gen_rtx_TRUNCATE
 172                         (mode,
 173                          gen_rtx_LSHIFTRT
 174                          (wider_mode,
 175                           gen_rtx_MULT (wider_mode,
 176                                         gen_rtx_ZERO_EXTEND (wider_mode, reg),
 177                                         gen_rtx_ZERO_EXTEND (wider_mode, reg)),
 178                           GEN_INT (GET_MODE_BITSIZE (mode)))),
 179                         SET);
 180         }
 181     }
 182
 183   /* Free the objects we just allocated.  */
 184   end_sequence ();
 185   obfree (free_point);
 186 }
 187
 188 /* Return an rtx representing minus the value of X.
 189    MODE is the intended mode of the result,
 190    useful if X is a CONST_INT.  */
 191
 192 rtx
 193 negate_rtx (mode, x)
 194      enum machine_mode mode;
 195      rtx x;
 196 {
 197   rtx result = simplify_unary_operation (NEG, mode, x, mode);
 198
 199   if (result == 0)
 200     result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
 201
 202   return result;
 203 }
 204 \f
 205 /* Generate code to store value from rtx VALUE
 206    into a bit-field within structure STR_RTX
 207    containing BITSIZE bits starting at bit BITNUM.
 208    FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
 209    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
 210    TOTAL_SIZE is the size of the structure in bytes, or -1 if varying.  */
 211
 212 /* ??? Note that there are two different ideas here for how
 213    to determine the size to count bits within, for a register.
 214    One is BITS_PER_WORD, and the other is the size of operand 3
 215    of the insv pattern.
 216
 217    If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
 218    else, we use the mode of operand 3.  */
 219
 220 rtx
 221 store_bit_field (str_rtx, bitsize, bitnum, fieldmode, value, align, total_size)
 222      rtx str_rtx;
 223      register int bitsize;
 224      int bitnum;
 225      enum machine_mode fieldmode;
 226      rtx value;
 227      int align;
 228      int total_size;
 229 {
 230   int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
 231   register int offset = bitnum / unit;
 232   register int bitpos = bitnum % unit;
 233   register rtx op0 = str_rtx;
 234 #ifdef HAVE_insv
 235   int insv_bitsize;
 236
 237   if (insn_operand_mode[(int) CODE_FOR_insv][3] == VOIDmode)
 238     insv_bitsize = GET_MODE_BITSIZE (word_mode);
 239   else
 240     insv_bitsize = GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_insv][3]);
 241 #endif
 242
 243   if (GET_CODE (str_rtx) == MEM && ! MEM_IN_STRUCT_P (str_rtx))
 244     abort ();
 245
 246   /* Discount the part of the structure before the desired byte.
 247      We need to know how many bytes are safe to reference after it.  */
 248   if (total_size >= 0)
 249     total_size -= (bitpos / BIGGEST_ALIGNMENT
 250                    * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
 251
 252   while (GET_CODE (op0) == SUBREG)
 253     {
 254       /* The following line once was done only if WORDS_BIG_ENDIAN,
 255          but I think that is a mistake.  WORDS_BIG_ENDIAN is
 256          meaningful at a much higher level; when structures are copied
 257          between memory and regs, the higher-numbered regs
 258          always get higher addresses.  */
 259       offset += SUBREG_WORD (op0);
 260       /* We used to adjust BITPOS here, but now we do the whole adjustment
 261          right after the loop.  */
 262       op0 = SUBREG_REG (op0);
 263     }
 264
 265   /* Make sure we are playing with integral modes.  Pun with subregs
 266      if we aren't.  */
 267   {
 268     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
 269     if (imode != GET_MODE (op0))
 270       {
 271         if (GET_CODE (op0) == MEM)
 272           op0 = change_address (op0, imode, NULL_RTX);
 273         else if (imode != BLKmode)
 274           op0 = gen_lowpart (imode, op0);
 275         else
 276           abort ();
 277       }
 278   }
 279
 280   /* If OP0 is a register, BITPOS must count within a word.
 281      But as we have it, it counts within whatever size OP0 now has.
 282      On a bigendian machine, these are not the same, so convert.  */
 283   if (BYTES_BIG_ENDIAN
 284       && GET_CODE (op0) != MEM
 285       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
 286     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
 287
 288   value = protect_from_queue (value, 0);
 289
 290   if (flag_force_mem)
 291     value = force_not_mem (value);
 292
 293   /* Note that the adjustment of BITPOS above has no effect on whether
 294      BITPOS is 0 in a REG bigger than a word.  */
 295   if (GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
 296       && (GET_CODE (op0) != MEM
 297           || ! SLOW_UNALIGNED_ACCESS
 298           || (offset * BITS_PER_UNIT % bitsize == 0
 299               && align % GET_MODE_SIZE (fieldmode) == 0))
 300       && bitpos == 0 && bitsize == GET_MODE_BITSIZE (fieldmode))
 301     {
 302       /* Storing in a full-word or multi-word field in a register
 303          can be done with just SUBREG.  */
 304       if (GET_MODE (op0) != fieldmode)
 305         {
 306           if (GET_CODE (op0) == SUBREG)
 307             {
 308               if (GET_MODE (SUBREG_REG (op0)) == fieldmode
 309                   || GET_MODE_CLASS (fieldmode) == MODE_INT
 310                   || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
 311                 op0 = SUBREG_REG (op0);
 312               else
 313                 /* Else we've got some float mode source being extracted into
 314                    a different float mode destination -- this combination of
 315                    subregs results in Severe Tire Damage.  */
 316                 abort ();
 317             }
 318           if (GET_CODE (op0) == REG)
 319             op0 = gen_rtx_SUBREG (fieldmode, op0, offset);
 320           else
 321             op0 = change_address (op0, fieldmode,
 322                                   plus_constant (XEXP (op0, 0), offset));
 323         }
 324       emit_move_insn (op0, value);
 325       return value;
 326     }
 327
 328   /* Storing an lsb-aligned field in a register
 329      can be done with a movestrict instruction.  */
 330
 331   if (GET_CODE (op0) != MEM
 332       && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
 333       && bitsize == GET_MODE_BITSIZE (fieldmode)
 334       && (GET_MODE (op0) == fieldmode
 335           || (movstrict_optab->handlers[(int) fieldmode].insn_code
 336               != CODE_FOR_nothing)))
 337     {
 338       /* Get appropriate low part of the value being stored.  */
 339       if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
 340         value = gen_lowpart (fieldmode, value);
 341       else if (!(GET_CODE (value) == SYMBOL_REF
 342                  || GET_CODE (value) == LABEL_REF
 343                  || GET_CODE (value) == CONST))
 344         value = convert_to_mode (fieldmode, value, 0);
 345
 346       if (GET_MODE (op0) == fieldmode)
 347         emit_move_insn (op0, value);
 348       else
 349         {
 350           int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
 351           if (! (*insn_operand_predicate[icode][1]) (value, fieldmode))
 352             value = copy_to_mode_reg (fieldmode, value);
 353
 354           if (GET_CODE (op0) == SUBREG)
 355             {
 356               if (GET_MODE (SUBREG_REG (op0)) == fieldmode
 357                   || GET_MODE_CLASS (fieldmode) == MODE_INT
 358                   || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
 359                 op0 = SUBREG_REG (op0);
 360               else
 361                 /* Else we've got some float mode source being extracted into
 362                    a different float mode destination -- this combination of
 363                    subregs results in Severe Tire Damage.  */
 364                 abort ();
 365             }
 366
 367           emit_insn (GEN_FCN (icode)
 368                    (gen_rtx_SUBREG (fieldmode, op0, offset), value));
 369         }
 370       return value;
 371     }
 372
 373   /* Handle fields bigger than a word.  */
 374
 375   if (bitsize > BITS_PER_WORD)
 376     {
 377       /* Here we transfer the words of the field
 378          in the order least significant first.
 379          This is because the most significant word is the one which may
 380          be less than full.
 381          However, only do that if the value is not BLKmode.  */
 382
 383       int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
 384
 385       int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
 386       int i;
 387
 388       /* This is the mode we must force value to, so that there will be enough
 389          subwords to extract.  Note that fieldmode will often (always?) be
 390          VOIDmode, because that is what store_field uses to indicate that this
 391          is a bit field, but passing VOIDmode to operand_subword_force will
 392          result in an abort.  */
 393       fieldmode = mode_for_size (nwords * BITS_PER_WORD, MODE_INT, 0);
 394
 395       for (i = 0; i < nwords; i++)
 396         {
 397           /* If I is 0, use the low-order word in both field and target;
 398              if I is 1, use the next to lowest word; and so on.  */
 399           int wordnum = (backwards ? nwords - i - 1 : i);
 400           int bit_offset = (backwards
 401                             ? MAX (bitsize - (i + 1) * BITS_PER_WORD, 0)
 402                             : i * BITS_PER_WORD);
 403           store_bit_field (op0, MIN (BITS_PER_WORD,
 404                                      bitsize - i * BITS_PER_WORD),
 405                            bitnum + bit_offset, word_mode,
 406                            operand_subword_force (value, wordnum,
 407                                                   (GET_MODE (value) == VOIDmode
 408                                                    ? fieldmode
 409                                                    : GET_MODE (value))),
 410                            align, total_size);
 411         }
 412       return value;
 413     }
 414
 415   /* From here on we can assume that the field to be stored in is
 416      a full-word (whatever type that is), since it is shorter than a word.  */
 417
 418   /* OFFSET is the number of words or bytes (UNIT says which)
 419      from STR_RTX to the first word or byte containing part of the field.  */
 420
 421   if (GET_CODE (op0) != MEM)
 422     {
 423       if (offset != 0
 424           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
 425         {
 426           if (GET_CODE (op0) != REG)
 427             {
 428               /* Since this is a destination (lvalue), we can't copy it to a
 429                  pseudo.  We can trivially remove a SUBREG that does not
 430                  change the size of the operand.  Such a SUBREG may have been
 431                  added above.  Otherwise, abort.  */
 432               if (GET_CODE (op0) == SUBREG
 433                   && (GET_MODE_SIZE (GET_MODE (op0))
 434                       == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
 435                 op0 = SUBREG_REG (op0);
 436               else
 437                 abort ();
 438             }
 439           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
 440                                 op0, offset);
 441         }
 442       offset = 0;
 443     }
 444   else
 445     {
 446       op0 = protect_from_queue (op0, 1);
 447     }
 448
 449   /* If VALUE is a floating-point mode, access it as an integer of the
 450      corresponding size.  This can occur on a machine with 64 bit registers
 451      that uses SFmode for float.  This can also occur for unaligned float
 452      structure fields.  */
 453   if (GET_MODE_CLASS (GET_MODE (value)) == MODE_FLOAT)
 454     {
 455       if (GET_CODE (value) != REG)
 456         value = copy_to_reg (value);
 457       value = gen_rtx_SUBREG (word_mode, value, 0);
 458     }
 459
 460   /* Now OFFSET is nonzero only if OP0 is memory
 461      and is therefore always measured in bytes.  */
 462
 463 #ifdef HAVE_insv
 464   if (HAVE_insv
 465       && GET_MODE (value) != BLKmode
 466       && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
 467       /* Ensure insv's size is wide enough for this field.  */
 468       && (insv_bitsize >= bitsize)
 469       && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
 470             && (bitsize + bitpos > insv_bitsize)))
 471     {
 472       int xbitpos = bitpos;
 473       rtx value1;
 474       rtx xop0 = op0;
 475       rtx last = get_last_insn ();
 476       rtx pat;
 477       enum machine_mode maxmode;
 478       int save_volatile_ok = volatile_ok;
 479
 480       maxmode = insn_operand_mode[(int) CODE_FOR_insv][3];
 481       if (maxmode == VOIDmode)
 482         maxmode = word_mode;
 483
 484       volatile_ok = 1;
 485
 486       /* If this machine's insv can only insert into a register, copy OP0
 487          into a register and save it back later.  */
 488       /* This used to check flag_force_mem, but that was a serious
 489          de-optimization now that flag_force_mem is enabled by -O2.  */
 490       if (GET_CODE (op0) == MEM
 491           && ! ((*insn_operand_predicate[(int) CODE_FOR_insv][0])
 492                 (op0, VOIDmode)))
 493         {
 494           rtx tempreg;
 495           enum machine_mode bestmode;
 496
 497           /* Get the mode to use for inserting into this field.  If OP0 is
 498              BLKmode, get the smallest mode consistent with the alignment. If
 499              OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
 500              mode. Otherwise, use the smallest mode containing the field.  */
 501
 502           if (GET_MODE (op0) == BLKmode
 503               || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
 504             bestmode
 505               = get_best_mode (bitsize, bitnum, align * BITS_PER_UNIT, maxmode,
 506                                MEM_VOLATILE_P (op0));
 507           else
 508             bestmode = GET_MODE (op0);
 509
 510           if (bestmode == VOIDmode
 511               || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
 512             goto insv_loses;
 513
 514           /* Adjust address to point to the containing unit of that mode.  */
 515           unit = GET_MODE_BITSIZE (bestmode);
 516           /* Compute offset as multiple of this unit, counting in bytes.  */
 517           offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
 518           bitpos = bitnum % unit;
 519           op0 = change_address (op0, bestmode,
 520                                 plus_constant (XEXP (op0, 0), offset));
 521
 522           /* Fetch that unit, store the bitfield in it, then store the unit.  */
 523           tempreg = copy_to_reg (op0);
 524           store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
 525                            align, total_size);
 526           emit_move_insn (op0, tempreg);
 527           return value;
 528         }
 529       volatile_ok = save_volatile_ok;
 530
 531       /* Add OFFSET into OP0's address.  */
 532       if (GET_CODE (xop0) == MEM)
 533         xop0 = change_address (xop0, byte_mode,
 534                                plus_constant (XEXP (xop0, 0), offset));
 535
 536       /* If xop0 is a register, we need it in MAXMODE
 537          to make it acceptable to the format of insv.  */
 538       if (GET_CODE (xop0) == SUBREG)
 539         /* We can't just change the mode, because this might clobber op0,
 540            and we will need the original value of op0 if insv fails.  */
 541         xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_WORD (xop0));
 542       if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
 543         xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
 544
 545       /* On big-endian machines, we count bits from the most significant.
 546          If the bit field insn does not, we must invert.  */
 547
 548       if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
 549         xbitpos = unit - bitsize - xbitpos;
 550
 551       /* We have been counting XBITPOS within UNIT.
 552          Count instead within the size of the register.  */
 553       if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
 554         xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
 555
 556       unit = GET_MODE_BITSIZE (maxmode);
 557
 558       /* Convert VALUE to maxmode (which insv insn wants) in VALUE1.  */
 559       value1 = value;
 560       if (GET_MODE (value) != maxmode)
 561         {
 562           if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
 563             {
 564               /* Optimization: Don't bother really extending VALUE
 565                  if it has all the bits we will actually use.  However,
 566                  if we must narrow it, be sure we do it correctly.  */
 567
 568               if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
 569                 {
 570                   /* Avoid making subreg of a subreg, or of a mem.  */
 571                   if (GET_CODE (value1) != REG)
 572                     value1 = copy_to_reg (value1);
 573                   value1 = gen_rtx_SUBREG (maxmode, value1, 0);
 574                 }
 575               else
 576                 value1 = gen_lowpart (maxmode, value1);
 577             }
 578           else if (!CONSTANT_P (value))
 579             /* Parse phase is supposed to make VALUE's data type
 580                match that of the component reference, which is a type
 581                at least as wide as the field; so VALUE should have
 582                a mode that corresponds to that type.  */
 583             abort ();
 584         }
 585
 586       /* If this machine's insv insists on a register,
 587          get VALUE1 into a register.  */
 588       if (! ((*insn_operand_predicate[(int) CODE_FOR_insv][3])
 589              (value1, maxmode)))
 590         value1 = force_reg (maxmode, value1);
 591
 592       pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
 593       if (pat)
 594         emit_insn (pat);
 595       else
 596         {
 597           delete_insns_since (last);
 598           store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
 599         }
 600     }
 601   else
 602     insv_loses:
 603 #endif
 604     /* Insv is not available; store using shifts and boolean ops.  */
 605     store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
 606   return value;
 607 }
 608 \f
 609 /* Use shifts and boolean operations to store VALUE
 610    into a bit field of width BITSIZE
 611    in a memory location specified by OP0 except offset by OFFSET bytes.
 612      (OFFSET must be 0 if OP0 is a register.)
 613    The field starts at position BITPOS within the byte.
 614     (If OP0 is a register, it may be a full word or a narrower mode,
 615      but BITPOS still counts within a full word,
 616      which is significant on bigendian machines.)
 617    STRUCT_ALIGN is the alignment the structure is known to have (in bytes).
 618
 619    Note that protect_from_queue has already been done on OP0 and VALUE.  */
 620
 621 static void
 622 store_fixed_bit_field (op0, offset, bitsize, bitpos, value, struct_align)
 623      register rtx op0;
 624      register int offset, bitsize, bitpos;
 625      register rtx value;
 626      int struct_align;
 627 {
 628   register enum machine_mode mode;
 629   int total_bits = BITS_PER_WORD;
 630   rtx subtarget, temp;
 631   int all_zero = 0;
 632   int all_one = 0;
 633
 634   if (! SLOW_UNALIGNED_ACCESS)
 635     struct_align = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
 636
 637   /* There is a case not handled here:
 638      a structure with a known alignment of just a halfword
 639      and a field split across two aligned halfwords within the structure.
 640      Or likewise a structure with a known alignment of just a byte
 641      and a field split across two bytes.
 642      Such cases are not supposed to be able to occur.  */
 643
 644   if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
 645     {
 646       if (offset != 0)
 647         abort ();
 648       /* Special treatment for a bit field split across two registers.  */
 649       if (bitsize + bitpos > BITS_PER_WORD)
 650         {
 651           store_split_bit_field (op0, bitsize, bitpos,
 652                                  value, BITS_PER_WORD);
 653           return;
 654         }
 655     }
 656   else
 657     {
 658       /* Get the proper mode to use for this field.  We want a mode that
 659          includes the entire field.  If such a mode would be larger than
 660          a word, we won't be doing the extraction the normal way.  */
 661
 662       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
 663                             struct_align * BITS_PER_UNIT, word_mode,
 664                             GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
 665
 666       if (mode == VOIDmode)
 667         {
 668           /* The only way this should occur is if the field spans word
 669              boundaries.  */
 670           store_split_bit_field (op0,
 671                                  bitsize, bitpos + offset * BITS_PER_UNIT,
 672                                  value, struct_align);
 673           return;
 674         }
 675
 676       total_bits = GET_MODE_BITSIZE (mode);
 677
 678       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
 679          be in the range 0 to total_bits-1, and put any excess bytes in
 680          OFFSET.  */
 681       if (bitpos >= total_bits)
 682         {
 683           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
 684           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
 685                      * BITS_PER_UNIT);
 686         }
 687
 688       /* Get ref to an aligned byte, halfword, or word containing the field.
 689          Adjust BITPOS to be position within a word,
 690          and OFFSET to be the offset of that word.
 691          Then alter OP0 to refer to that word.  */
 692       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
 693       offset -= (offset % (total_bits / BITS_PER_UNIT));
 694       op0 = change_address (op0, mode,
 695                             plus_constant (XEXP (op0, 0), offset));
 696     }
 697
 698   mode = GET_MODE (op0);
 699
 700   /* Now MODE is either some integral mode for a MEM as OP0,
 701      or is a full-word for a REG as OP0.  TOTAL_BITS corresponds.
 702      The bit field is contained entirely within OP0.
 703      BITPOS is the starting bit number within OP0.
 704      (OP0's mode may actually be narrower than MODE.)  */
 705
 706   if (BYTES_BIG_ENDIAN)
 707       /* BITPOS is the distance between our msb
 708          and that of the containing datum.
 709          Convert it to the distance from the lsb.  */
 710       bitpos = total_bits - bitsize - bitpos;
 711
 712   /* Now BITPOS is always the distance between our lsb
 713      and that of OP0.  */
 714
 715   /* Shift VALUE left by BITPOS bits.  If VALUE is not constant,
 716      we must first convert its mode to MODE.  */
 717
 718   if (GET_CODE (value) == CONST_INT)
 719     {
 720       register HOST_WIDE_INT v = INTVAL (value);
 721
 722       if (bitsize < HOST_BITS_PER_WIDE_INT)
 723         v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
 724
 725       if (v == 0)
 726         all_zero = 1;
 727       else if ((bitsize < HOST_BITS_PER_WIDE_INT
 728                 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
 729                || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
 730         all_one = 1;
 731
 732       value = lshift_value (mode, value, bitpos, bitsize);
 733     }
 734   else
 735     {
 736       int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
 737                       && bitpos + bitsize != GET_MODE_BITSIZE (mode));
 738
 739       if (GET_MODE (value) != mode)
 740         {
 741           if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
 742               && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
 743             value = gen_lowpart (mode, value);
 744           else
 745             value = convert_to_mode (mode, value, 1);
 746         }
 747
 748       if (must_and)
 749         value = expand_binop (mode, and_optab, value,
 750                               mask_rtx (mode, 0, bitsize, 0),
 751                               NULL_RTX, 1, OPTAB_LIB_WIDEN);
 752       if (bitpos > 0)
 753         value = expand_shift (LSHIFT_EXPR, mode, value,
 754                               build_int_2 (bitpos, 0), NULL_RTX, 1);
 755     }
 756
 757   /* Now clear the chosen bits in OP0,
 758      except that if VALUE is -1 we need not bother.  */
 759
 760   subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
 761
 762   if (! all_one)
 763     {
 764       temp = expand_binop (mode, and_optab, op0,
 765                            mask_rtx (mode, bitpos, bitsize, 1),
 766                            subtarget, 1, OPTAB_LIB_WIDEN);
 767       subtarget = temp;
 768     }
 769   else
 770     temp = op0;
 771
 772   /* Now logical-or VALUE into OP0, unless it is zero.  */
 773
 774   if (! all_zero)
 775     temp = expand_binop (mode, ior_optab, temp, value,
 776                          subtarget, 1, OPTAB_LIB_WIDEN);
 777   if (op0 != temp)
 778     emit_move_insn (op0, temp);
 779 }
 780 \f
 781 /* Store a bit field that is split across multiple accessible memory objects.
 782
 783    OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
 784    BITSIZE is the field width; BITPOS the position of its first bit
 785    (within the word).
 786    VALUE is the value to store.
 787    ALIGN is the known alignment of OP0, measured in bytes.
 788    This is also the size of the memory objects to be used.
 789
 790    This does not yet handle fields wider than BITS_PER_WORD.  */
 791
 792 static void
 793 store_split_bit_field (op0, bitsize, bitpos, value, align)
 794      rtx op0;
 795      int bitsize, bitpos;
 796      rtx value;
 797      int align;
 798 {
 799   int unit;
 800   int bitsdone = 0;
 801
 802   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
 803      much at a time.  */
 804   if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
 805     unit = BITS_PER_WORD;
 806   else
 807     unit = MIN (align * BITS_PER_UNIT, BITS_PER_WORD);
 808
 809   /* If VALUE is a constant other than a CONST_INT, get it into a register in
 810      WORD_MODE.  If we can do this using gen_lowpart_common, do so.  Note
 811      that VALUE might be a floating-point constant.  */
 812   if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
 813     {
 814       rtx word = gen_lowpart_common (word_mode, value);
 815
 816       if (word && (value != word))
 817         value = word;
 818       else
 819         value = gen_lowpart_common (word_mode,
 820                                     force_reg (GET_MODE (value) != VOIDmode
 821                                                ? GET_MODE (value)
 822                                                : word_mode, value));
 823     }
 824   else if (GET_CODE (value) == ADDRESSOF)
 825     value = copy_to_reg (value);
 826
 827   while (bitsdone < bitsize)
 828     {
 829       int thissize;
 830       rtx part, word;
 831       int thispos;
 832       int offset;
 833
 834       offset = (bitpos + bitsdone) / unit;
 835       thispos = (bitpos + bitsdone) % unit;
 836
 837       /* THISSIZE must not overrun a word boundary.  Otherwise,
 838          store_fixed_bit_field will call us again, and we will mutually
 839          recurse forever.  */
 840       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
 841       thissize = MIN (thissize, unit - thispos);
 842
 843       if (BYTES_BIG_ENDIAN)
 844         {
 845           int total_bits;
 846
 847           /* We must do an endian conversion exactly the same way as it is
 848              done in extract_bit_field, so that the two calls to
 849              extract_fixed_bit_field will have comparable arguments.  */
 850           if (GET_CODE (value) != MEM || GET_MODE (value) == BLKmode)
 851             total_bits = BITS_PER_WORD;
 852           else
 853             total_bits = GET_MODE_BITSIZE (GET_MODE (value));
 854
 855           /* Fetch successively less significant portions.  */
 856           if (GET_CODE (value) == CONST_INT)
 857             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
 858                              >> (bitsize - bitsdone - thissize))
 859                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
 860           else
 861             /* The args are chosen so that the last part includes the
 862                lsb.  Give extract_bit_field the value it needs (with
 863                endianness compensation) to fetch the piece we want.
 864
 865                ??? We have no idea what the alignment of VALUE is, so
 866                we have to use a guess.  */
 867             part
 868               = extract_fixed_bit_field
 869                 (word_mode, value, 0, thissize,
 870                  total_bits - bitsize + bitsdone, NULL_RTX, 1,
 871                  GET_MODE (value) == VOIDmode
 872                  ? UNITS_PER_WORD
 873                  : (GET_MODE (value) == BLKmode
 874                     ? 1
 875                     : GET_MODE_ALIGNMENT (GET_MODE (value)) / BITS_PER_UNIT));
 876         }
 877       else
 878         {
 879           /* Fetch successively more significant portions.  */
 880           if (GET_CODE (value) == CONST_INT)
 881             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
 882                              >> bitsdone)
 883                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
 884           else
 885             part
 886               = extract_fixed_bit_field
 887                 (word_mode, value, 0, thissize, bitsdone, NULL_RTX, 1,
 888                  GET_MODE (value) == VOIDmode
 889                  ? UNITS_PER_WORD
 890                  : (GET_MODE (value) == BLKmode
 891                     ? 1
 892                     : GET_MODE_ALIGNMENT (GET_MODE (value)) / BITS_PER_UNIT));
 893         }
 894
 895       /* If OP0 is a register, then handle OFFSET here.
 896
 897          When handling multiword bitfields, extract_bit_field may pass
 898          down a word_mode SUBREG of a larger REG for a bitfield that actually
 899          crosses a word boundary.  Thus, for a SUBREG, we must find
 900          the current word starting from the base register.  */
 901       if (GET_CODE (op0) == SUBREG)
 902         {
 903           word = operand_subword_force (SUBREG_REG (op0),
 904                                         SUBREG_WORD (op0) + offset,
 905                                         GET_MODE (SUBREG_REG (op0)));
 906           offset = 0;
 907         }
 908       else if (GET_CODE (op0) == REG)
 909         {
 910           word = operand_subword_force (op0, offset, GET_MODE (op0));
 911           offset = 0;
 912         }
 913       else
 914         word = op0;
 915
 916       /* OFFSET is in UNITs, and UNIT is in bits.
 917          store_fixed_bit_field wants offset in bytes.  */
 918       store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT,
 919                              thissize, thispos, part, align);
 920       bitsdone += thissize;
 921     }
 922 }
 923 \f
 924 /* Generate code to extract a byte-field from STR_RTX
 925    containing BITSIZE bits, starting at BITNUM,
 926    and put it in TARGET if possible (if TARGET is nonzero).
 927    Regardless of TARGET, we return the rtx for where the value is placed.
 928    It may be a QUEUED.
 929
 930    STR_RTX is the structure containing the byte (a REG or MEM).
 931    UNSIGNEDP is nonzero if this is an unsigned bit field.
 932    MODE is the natural mode of the field value once extracted.
 933    TMODE is the mode the caller would like the value to have;
 934    but the value may be returned with type MODE instead.
 935
 936    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
 937    TOTAL_SIZE is the size in bytes of the containing structure,
 938    or -1 if varying.
 939
 940    If a TARGET is specified and we can store in it at no extra cost,
 941    we do so, and return TARGET.
 942    Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
 943    if they are equally easy.  */
 944
 945 rtx
 946 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
 947                    target, mode, tmode, align, total_size)
 948      rtx str_rtx;
 949      register int bitsize;
 950      int bitnum;
 951      int unsignedp;
 952      rtx target;
 953      enum machine_mode mode, tmode;
 954      int align;
 955      int total_size;
 956 {
 957   int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
 958   register int offset = bitnum / unit;
 959   register int bitpos = bitnum % unit;
 960   register rtx op0 = str_rtx;
 961   rtx spec_target = target;
 962   rtx spec_target_subreg = 0;
 963 #ifdef HAVE_extv
 964   int extv_bitsize;
 965 #endif
 966 #ifdef HAVE_extzv
 967   int extzv_bitsize;
 968 #endif
 969
 970 #ifdef HAVE_extv
 971   if (insn_operand_mode[(int) CODE_FOR_extv][0] == VOIDmode)
 972     extv_bitsize = GET_MODE_BITSIZE (word_mode);
 973   else
 974     extv_bitsize = GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extv][0]);
 975 #endif
 976
 977 #ifdef HAVE_extzv
 978   if (insn_operand_mode[(int) CODE_FOR_extzv][0] == VOIDmode)
 979     extzv_bitsize = GET_MODE_BITSIZE (word_mode);
 980   else
 981     extzv_bitsize
 982       = GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extzv][0]);
 983 #endif
 984
 985   /* Discount the part of the structure before the desired byte.
 986      We need to know how many bytes are safe to reference after it.  */
 987   if (total_size >= 0)
 988     total_size -= (bitpos / BIGGEST_ALIGNMENT
 989                    * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
 990
 991   if (tmode == VOIDmode)
 992     tmode = mode;
 993   while (GET_CODE (op0) == SUBREG)
 994     {
 995       int outer_size = GET_MODE_BITSIZE (GET_MODE (op0));
 996       int inner_size = GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (op0)));
 997
 998       offset += SUBREG_WORD (op0);
 999
1000       inner_size = MIN (inner_size, BITS_PER_WORD);
1001
1002       if (BYTES_BIG_ENDIAN && (outer_size < inner_size))
1003         {
1004           bitpos += inner_size - outer_size;
1005           if (bitpos > unit)
1006             {
1007               offset += (bitpos / unit);
1008               bitpos %= unit;
1009             }
1010         }
1011
1012       op0 = SUBREG_REG (op0);
1013     }
1014
1015   /* Make sure we are playing with integral modes.  Pun with subregs
1016      if we aren't.  */
1017   {
1018     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1019     if (imode != GET_MODE (op0))
1020       {
1021         if (GET_CODE (op0) == MEM)
1022           op0 = change_address (op0, imode, NULL_RTX);
1023         else if (imode != BLKmode)
1024           op0 = gen_lowpart (imode, op0);
1025         else
1026           abort ();
1027       }
1028   }
1029
1030   /* ??? We currently assume TARGET is at least as big as BITSIZE.
1031      If that's wrong, the solution is to test for it and set TARGET to 0
1032      if needed.  */
1033
1034   /* If OP0 is a register, BITPOS must count within a word.
1035      But as we have it, it counts within whatever size OP0 now has.
1036      On a bigendian machine, these are not the same, so convert.  */
1037   if (BYTES_BIG_ENDIAN
1038       && GET_CODE (op0) != MEM
1039       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1040     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1041
1042   /* Extracting a full-word or multi-word value
1043      from a structure in a register or aligned memory.
1044      This can be done with just SUBREG.
1045      So too extracting a subword value in
1046      the least significant part of the register.  */
1047
1048   if (((GET_CODE (op0) != MEM
1049         && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1050                                   GET_MODE_BITSIZE (GET_MODE (op0))))
1051        || (GET_CODE (op0) == MEM
1052            && (! SLOW_UNALIGNED_ACCESS
1053                || (offset * BITS_PER_UNIT % bitsize == 0
1054                    && align * BITS_PER_UNIT % bitsize == 0))))
1055       && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1056            && bitpos % BITS_PER_WORD == 0)
1057           || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
1058               /* ??? The big endian test here is wrong.  This is correct
1059                  if the value is in a register, and if mode_for_size is not
1060                  the same mode as op0.  This causes us to get unnecessarily
1061                  inefficient code from the Thumb port when -mbig-endian.  */
1062               && (BYTES_BIG_ENDIAN
1063                   ? bitpos + bitsize == BITS_PER_WORD
1064                   : bitpos == 0))))
1065     {
1066       enum machine_mode mode1
1067         = mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0);
1068
1069       if (mode1 != GET_MODE (op0))
1070         {
1071           if (GET_CODE (op0) == SUBREG)
1072             {
1073               if (GET_MODE (SUBREG_REG (op0)) == mode1
1074                   || GET_MODE_CLASS (mode1) == MODE_INT
1075                   || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1076                 op0 = SUBREG_REG (op0);
1077               else
1078                 /* Else we've got some float mode source being extracted into
1079                    a different float mode destination -- this combination of
1080                    subregs results in Severe Tire Damage.  */
1081                 abort ();
1082             }
1083           if (GET_CODE (op0) == REG)
1084             op0 = gen_rtx_SUBREG (mode1, op0, offset);
1085           else
1086             op0 = change_address (op0, mode1,
1087                                   plus_constant (XEXP (op0, 0), offset));
1088         }
1089       if (mode1 != mode)
1090         return convert_to_mode (tmode, op0, unsignedp);
1091       return op0;
1092     }
1093
1094   /* Handle fields bigger than a word.  */
1095
1096   if (bitsize > BITS_PER_WORD)
1097     {
1098       /* Here we transfer the words of the field
1099          in the order least significant first.
1100          This is because the most significant word is the one which may
1101          be less than full.  */
1102
1103       int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1104       int i;
1105
1106       if (target == 0 || GET_CODE (target) != REG)
1107         target = gen_reg_rtx (mode);
1108
1109       /* Indicate for flow that the entire target reg is being set.  */
1110       emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1111
1112       for (i = 0; i < nwords; i++)
1113         {
1114           /* If I is 0, use the low-order word in both field and target;
1115              if I is 1, use the next to lowest word; and so on.  */
1116           /* Word number in TARGET to use.  */
1117           int wordnum = (WORDS_BIG_ENDIAN
1118                          ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1119                          : i);
1120           /* Offset from start of field in OP0.  */
1121           int bit_offset = (WORDS_BIG_ENDIAN
1122                             ? MAX (0, bitsize - (i + 1) * BITS_PER_WORD)
1123                             : i * BITS_PER_WORD);
1124           rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1125           rtx result_part
1126             = extract_bit_field (op0, MIN (BITS_PER_WORD,
1127                                            bitsize - i * BITS_PER_WORD),
1128                                  bitnum + bit_offset,
1129                                  1, target_part, mode, word_mode,
1130                                  align, total_size);
1131
1132           if (target_part == 0)
1133             abort ();
1134
1135           if (result_part != target_part)
1136             emit_move_insn (target_part, result_part);
1137         }
1138
1139       if (unsignedp)
1140         {
1141           /* Unless we've filled TARGET, the upper regs in a multi-reg value
1142              need to be zero'd out.  */
1143           if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1144             {
1145               int i,total_words;
1146
1147               total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1148               for (i = nwords; i < total_words; i++)
1149                 {
1150                   int wordnum = WORDS_BIG_ENDIAN ? total_words - i - 1 : i;
1151                   rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1152                   emit_move_insn (target_part, const0_rtx);
1153                 }
1154             }
1155           return target;
1156         }
1157
1158       /* Signed bit field: sign-extend with two arithmetic shifts.  */
1159       target = expand_shift (LSHIFT_EXPR, mode, target,
1160                              build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1161                              NULL_RTX, 0);
1162       return expand_shift (RSHIFT_EXPR, mode, target,
1163                            build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1164                            NULL_RTX, 0);
1165     }
1166
1167   /* From here on we know the desired field is smaller than a word
1168      so we can assume it is an integer.  So we can safely extract it as one
1169      size of integer, if necessary, and then truncate or extend
1170      to the size that is wanted.  */
1171
1172   /* OFFSET is the number of words or bytes (UNIT says which)
1173      from STR_RTX to the first word or byte containing part of the field.  */
1174
1175   if (GET_CODE (op0) != MEM)
1176     {
1177       if (offset != 0
1178           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1179         {
1180           if (GET_CODE (op0) != REG)
1181             op0 = copy_to_reg (op0);
1182           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1183                                 op0, offset);
1184         }
1185       offset = 0;
1186     }
1187   else
1188     {
1189       op0 = protect_from_queue (str_rtx, 1);
1190     }
1191
1192   /* Now OFFSET is nonzero only for memory operands.  */
1193
1194   if (unsignedp)
1195     {
1196 #ifdef HAVE_extzv
1197       if (HAVE_extzv
1198           && (extzv_bitsize >= bitsize)
1199           && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1200                 && (bitsize + bitpos > extzv_bitsize)))
1201         {
1202           int xbitpos = bitpos, xoffset = offset;
1203           rtx bitsize_rtx, bitpos_rtx;
1204           rtx last = get_last_insn ();
1205           rtx xop0 = op0;
1206           rtx xtarget = target;
1207           rtx xspec_target = spec_target;
1208           rtx xspec_target_subreg = spec_target_subreg;
1209           rtx pat;
1210           enum machine_mode maxmode;
1211
1212           maxmode = insn_operand_mode[(int) CODE_FOR_extzv][0];
1213           if (maxmode == VOIDmode)
1214             maxmode = word_mode;
1215
1216           if (GET_CODE (xop0) == MEM)
1217             {
1218               int save_volatile_ok = volatile_ok;
1219               volatile_ok = 1;
1220
1221               /* Is the memory operand acceptable?  */
1222               if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][1])
1223                      (xop0, GET_MODE (xop0))))
1224                 {
1225                   /* No, load into a reg and extract from there.  */
1226                   enum machine_mode bestmode;
1227
1228                   /* Get the mode to use for inserting into this field.  If
1229                      OP0 is BLKmode, get the smallest mode consistent with the
1230                      alignment. If OP0 is a non-BLKmode object that is no
1231                      wider than MAXMODE, use its mode. Otherwise, use the
1232                      smallest mode containing the field.  */
1233
1234                   if (GET_MODE (xop0) == BLKmode
1235                       || (GET_MODE_SIZE (GET_MODE (op0))
1236                           > GET_MODE_SIZE (maxmode)))
1237                     bestmode = get_best_mode (bitsize, bitnum,
1238                                               align * BITS_PER_UNIT, maxmode,
1239                                               MEM_VOLATILE_P (xop0));
1240                   else
1241                     bestmode = GET_MODE (xop0);
1242
1243                   if (bestmode == VOIDmode
1244                       || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
1245                     goto extzv_loses;
1246
1247                   /* Compute offset as multiple of this unit,
1248                      counting in bytes.  */
1249                   unit = GET_MODE_BITSIZE (bestmode);
1250                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1251                   xbitpos = bitnum % unit;
1252                   xop0 = change_address (xop0, bestmode,
1253                                          plus_constant (XEXP (xop0, 0),
1254                                                         xoffset));
1255                   /* Fetch it to a register in that size.  */
1256                   xop0 = force_reg (bestmode, xop0);
1257
1258                   /* XBITPOS counts within UNIT, which is what is expected.  */
1259                 }
1260               else
1261                 /* Get ref to first byte containing part of the field.  */
1262                 xop0 = change_address (xop0, byte_mode,
1263                                        plus_constant (XEXP (xop0, 0), xoffset));
1264
1265               volatile_ok = save_volatile_ok;
1266             }
1267
1268           /* If op0 is a register, we need it in MAXMODE (which is usually
1269              SImode). to make it acceptable to the format of extzv.  */
1270           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1271             goto extzv_loses;
1272           if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1273             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1274
1275           /* On big-endian machines, we count bits from the most significant.
1276              If the bit field insn does not, we must invert.  */
1277           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1278             xbitpos = unit - bitsize - xbitpos;
1279
1280           /* Now convert from counting within UNIT to counting in MAXMODE.  */
1281           if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1282             xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1283
1284           unit = GET_MODE_BITSIZE (maxmode);
1285
1286           if (xtarget == 0
1287               || (flag_force_mem && GET_CODE (xtarget) == MEM))
1288             xtarget = xspec_target = gen_reg_rtx (tmode);
1289
1290           if (GET_MODE (xtarget) != maxmode)
1291             {
1292               if (GET_CODE (xtarget) == REG)
1293                 {
1294                   int wider = (GET_MODE_SIZE (maxmode)
1295                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1296                   xtarget = gen_lowpart (maxmode, xtarget);
1297                   if (wider)
1298                     xspec_target_subreg = xtarget;
1299                 }
1300               else
1301                 xtarget = gen_reg_rtx (maxmode);
1302             }
1303
1304           /* If this machine's extzv insists on a register target,
1305              make sure we have one.  */
1306           if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][0])
1307                  (xtarget, maxmode)))
1308             xtarget = gen_reg_rtx (maxmode);
1309
1310           bitsize_rtx = GEN_INT (bitsize);
1311           bitpos_rtx = GEN_INT (xbitpos);
1312
1313           pat = gen_extzv (protect_from_queue (xtarget, 1),
1314                            xop0, bitsize_rtx, bitpos_rtx);
1315           if (pat)
1316             {
1317               emit_insn (pat);
1318               target = xtarget;
1319               spec_target = xspec_target;
1320               spec_target_subreg = xspec_target_subreg;
1321             }
1322           else
1323             {
1324               delete_insns_since (last);
1325               target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
1326                                                 bitpos, target, 1, align);
1327             }
1328         }
1329       else
1330         extzv_loses:
1331 #endif
1332         target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1333                                           target, 1, align);
1334     }
1335   else
1336     {
1337 #ifdef HAVE_extv
1338       if (HAVE_extv
1339           && (extv_bitsize >= bitsize)
1340           && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1341                 && (bitsize + bitpos > extv_bitsize)))
1342         {
1343           int xbitpos = bitpos, xoffset = offset;
1344           rtx bitsize_rtx, bitpos_rtx;
1345           rtx last = get_last_insn ();
1346           rtx xop0 = op0, xtarget = target;
1347           rtx xspec_target = spec_target;
1348           rtx xspec_target_subreg = spec_target_subreg;
1349           rtx pat;
1350           enum machine_mode maxmode;
1351
1352           maxmode = insn_operand_mode[(int) CODE_FOR_extv][0];
1353           if (maxmode == VOIDmode)
1354             maxmode = word_mode;
1355
1356           if (GET_CODE (xop0) == MEM)
1357             {
1358               /* Is the memory operand acceptable?  */
1359               if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][1])
1360                      (xop0, GET_MODE (xop0))))
1361                 {
1362                   /* No, load into a reg and extract from there.  */
1363                   enum machine_mode bestmode;
1364
1365                   /* Get the mode to use for inserting into this field.  If
1366                      OP0 is BLKmode, get the smallest mode consistent with the
1367                      alignment. If OP0 is a non-BLKmode object that is no
1368                      wider than MAXMODE, use its mode. Otherwise, use the
1369                      smallest mode containing the field.  */
1370
1371                   if (GET_MODE (xop0) == BLKmode
1372                       || (GET_MODE_SIZE (GET_MODE (op0))
1373                           > GET_MODE_SIZE (maxmode)))
1374                     bestmode = get_best_mode (bitsize, bitnum,
1375                                               align * BITS_PER_UNIT, maxmode,
1376                                               MEM_VOLATILE_P (xop0));
1377                   else
1378                     bestmode = GET_MODE (xop0);
1379
1380                   if (bestmode == VOIDmode
1381                       || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
1382                     goto extv_loses;
1383
1384                   /* Compute offset as multiple of this unit,
1385                      counting in bytes.  */
1386                   unit = GET_MODE_BITSIZE (bestmode);
1387                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1388                   xbitpos = bitnum % unit;
1389                   xop0 = change_address (xop0, bestmode,
1390                                          plus_constant (XEXP (xop0, 0),
1391                                                         xoffset));
1392                   /* Fetch it to a register in that size.  */
1393                   xop0 = force_reg (bestmode, xop0);
1394
1395                   /* XBITPOS counts within UNIT, which is what is expected.  */
1396                 }
1397               else
1398                 /* Get ref to first byte containing part of the field.  */
1399                 xop0 = change_address (xop0, byte_mode,
1400                                        plus_constant (XEXP (xop0, 0), xoffset));
1401             }
1402
1403           /* If op0 is a register, we need it in MAXMODE (which is usually
1404              SImode) to make it acceptable to the format of extv.  */
1405           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1406             goto extv_loses;
1407           if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1408             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1409
1410           /* On big-endian machines, we count bits from the most significant.
1411              If the bit field insn does not, we must invert.  */
1412           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1413             xbitpos = unit - bitsize - xbitpos;
1414
1415           /* XBITPOS counts within a size of UNIT.
1416              Adjust to count within a size of MAXMODE.  */
1417           if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1418             xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1419
1420           unit = GET_MODE_BITSIZE (maxmode);
1421
1422           if (xtarget == 0
1423               || (flag_force_mem && GET_CODE (xtarget) == MEM))
1424             xtarget = xspec_target = gen_reg_rtx (tmode);
1425
1426           if (GET_MODE (xtarget) != maxmode)
1427             {
1428               if (GET_CODE (xtarget) == REG)
1429                 {
1430                   int wider = (GET_MODE_SIZE (maxmode)
1431                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1432                   xtarget = gen_lowpart (maxmode, xtarget);
1433                   if (wider)
1434                     xspec_target_subreg = xtarget;
1435                 }
1436               else
1437                 xtarget = gen_reg_rtx (maxmode);
1438             }
1439
1440           /* If this machine's extv insists on a register target,
1441              make sure we have one.  */
1442           if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][0])
1443                  (xtarget, maxmode)))
1444             xtarget = gen_reg_rtx (maxmode);
1445
1446           bitsize_rtx = GEN_INT (bitsize);
1447           bitpos_rtx = GEN_INT (xbitpos);
1448
1449           pat = gen_extv (protect_from_queue (xtarget, 1),
1450                           xop0, bitsize_rtx, bitpos_rtx);
1451           if (pat)
1452             {
1453               emit_insn (pat);
1454               target = xtarget;
1455               spec_target = xspec_target;
1456               spec_target_subreg = xspec_target_subreg;
1457             }
1458           else
1459             {
1460               delete_insns_since (last);
1461               target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
1462                                                 bitpos, target, 0, align);
1463             }
1464         }
1465       else
1466         extv_loses:
1467 #endif
1468         target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1469                                           target, 0, align);
1470     }
1471   if (target == spec_target)
1472     return target;
1473   if (target == spec_target_subreg)
1474     return spec_target;
1475   if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1476     {
1477       /* If the target mode is floating-point, first convert to the
1478          integer mode of that size and then access it as a floating-point
1479          value via a SUBREG.  */
1480       if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1481         {
1482           target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1483                                                    MODE_INT, 0),
1484                                     target, unsignedp);
1485           if (GET_CODE (target) != REG)
1486             target = copy_to_reg (target);
1487           return gen_rtx_SUBREG (tmode, target, 0);
1488         }
1489       else
1490         return convert_to_mode (tmode, target, unsignedp);
1491     }
1492   return target;
1493 }
1494 \f
1495 /* Extract a bit field using shifts and boolean operations
1496    Returns an rtx to represent the value.
1497    OP0 addresses a register (word) or memory (byte).
1498    BITPOS says which bit within the word or byte the bit field starts in.
1499    OFFSET says how many bytes farther the bit field starts;
1500     it is 0 if OP0 is a register.
1501    BITSIZE says how many bits long the bit field is.
1502     (If OP0 is a register, it may be narrower than a full word,
1503      but BITPOS still counts within a full word,
1504      which is significant on bigendian machines.)
1505
1506    UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1507    If TARGET is nonzero, attempts to store the value there
1508    and return TARGET, but this is not guaranteed.
1509    If TARGET is not used, create a pseudo-reg of mode TMODE for the value.
1510
1511    ALIGN is the alignment that STR_RTX is known to have, measured in bytes.  */
1512
1513 static rtx
1514 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1515                          target, unsignedp, align)
1516      enum machine_mode tmode;
1517      register rtx op0, target;
1518      register int offset, bitsize, bitpos;
1519      int unsignedp;
1520      int align;
1521 {
1522   int total_bits = BITS_PER_WORD;
1523   enum machine_mode mode;
1524
1525   if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1526     {
1527       /* Special treatment for a bit field split across two registers.  */
1528       if (bitsize + bitpos > BITS_PER_WORD)
1529         return extract_split_bit_field (op0, bitsize, bitpos,
1530                                         unsignedp, align);
1531     }
1532   else
1533     {
1534       /* Get the proper mode to use for this field.  We want a mode that
1535          includes the entire field.  If such a mode would be larger than
1536          a word, we won't be doing the extraction the normal way.  */
1537
1538       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1539                             align * BITS_PER_UNIT, word_mode,
1540                             GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
1541
1542       if (mode == VOIDmode)
1543         /* The only way this should occur is if the field spans word
1544            boundaries.  */
1545         return extract_split_bit_field (op0, bitsize,
1546                                         bitpos + offset * BITS_PER_UNIT,
1547                                         unsignedp, align);
1548
1549       total_bits = GET_MODE_BITSIZE (mode);
1550
1551       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
1552          be in the range 0 to total_bits-1, and put any excess bytes in
1553          OFFSET.  */
1554       if (bitpos >= total_bits)
1555         {
1556           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1557           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1558                      * BITS_PER_UNIT);
1559         }
1560
1561       /* Get ref to an aligned byte, halfword, or word containing the field.
1562          Adjust BITPOS to be position within a word,
1563          and OFFSET to be the offset of that word.
1564          Then alter OP0 to refer to that word.  */
1565       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1566       offset -= (offset % (total_bits / BITS_PER_UNIT));
1567       op0 = change_address (op0, mode,
1568                             plus_constant (XEXP (op0, 0), offset));
1569     }
1570
1571   mode = GET_MODE (op0);
1572
1573   if (BYTES_BIG_ENDIAN)
1574     {
1575       /* BITPOS is the distance between our msb and that of OP0.
1576          Convert it to the distance from the lsb.  */
1577
1578       bitpos = total_bits - bitsize - bitpos;
1579     }
1580
1581   /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1582      We have reduced the big-endian case to the little-endian case.  */
1583
1584   if (unsignedp)
1585     {
1586       if (bitpos)
1587         {
1588           /* If the field does not already start at the lsb,
1589              shift it so it does.  */
1590           tree amount = build_int_2 (bitpos, 0);
1591           /* Maybe propagate the target for the shift.  */
1592           /* But not if we will return it--could confuse integrate.c.  */
1593           rtx subtarget = (target != 0 && GET_CODE (target) == REG
1594                            && !REG_FUNCTION_VALUE_P (target)
1595                            ? target : 0);
1596           if (tmode != mode) subtarget = 0;
1597           op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1598         }
1599       /* Convert the value to the desired mode.  */
1600       if (mode != tmode)
1601         op0 = convert_to_mode (tmode, op0, 1);
1602
1603       /* Unless the msb of the field used to be the msb when we shifted,
1604          mask out the upper bits.  */
1605
1606       if (GET_MODE_BITSIZE (mode) != bitpos + bitsize
1607 #if 0
1608 #ifdef SLOW_ZERO_EXTEND
1609           /* Always generate an `and' if
1610              we just zero-extended op0 and SLOW_ZERO_EXTEND, since it
1611              will combine fruitfully with the zero-extend.  */
1612           || tmode != mode
1613 #endif
1614 #endif
1615           )
1616         return expand_binop (GET_MODE (op0), and_optab, op0,
1617                              mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1618                              target, 1, OPTAB_LIB_WIDEN);
1619       return op0;
1620     }
1621
1622   /* To extract a signed bit-field, first shift its msb to the msb of the word,
1623      then arithmetic-shift its lsb to the lsb of the word.  */
1624   op0 = force_reg (mode, op0);
1625   if (mode != tmode)
1626     target = 0;
1627
1628   /* Find the narrowest integer mode that contains the field.  */
1629
1630   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1631        mode = GET_MODE_WIDER_MODE (mode))
1632     if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1633       {
1634         op0 = convert_to_mode (mode, op0, 0);
1635         break;
1636       }
1637
1638   if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1639     {
1640       tree amount = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1641       /* Maybe propagate the target for the shift.  */
1642       /* But not if we will return the result--could confuse integrate.c.  */
1643       rtx subtarget = (target != 0 && GET_CODE (target) == REG
1644                        && ! REG_FUNCTION_VALUE_P (target)
1645                        ? target : 0);
1646       op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1647     }
1648
1649   return expand_shift (RSHIFT_EXPR, mode, op0,
1650                        build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1651                        target, 0);
1652 }
1653 \f
1654 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1655    of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1656    complement of that if COMPLEMENT.  The mask is truncated if
1657    necessary to the width of mode MODE.  The mask is zero-extended if
1658    BITSIZE+BITPOS is too small for MODE.  */
1659
1660 static rtx
1661 mask_rtx (mode, bitpos, bitsize, complement)
1662      enum machine_mode mode;
1663      int bitpos, bitsize, complement;
1664 {
1665   HOST_WIDE_INT masklow, maskhigh;
1666
1667   if (bitpos < HOST_BITS_PER_WIDE_INT)
1668     masklow = (HOST_WIDE_INT) -1 << bitpos;
1669   else
1670     masklow = 0;
1671
1672   if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1673     masklow &= ((unsigned HOST_WIDE_INT) -1
1674                 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1675
1676   if (bitpos <= HOST_BITS_PER_WIDE_INT)
1677     maskhigh = -1;
1678   else
1679     maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1680
1681   if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1682     maskhigh &= ((unsigned HOST_WIDE_INT) -1
1683                  >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1684   else
1685     maskhigh = 0;
1686
1687   if (complement)
1688     {
1689       maskhigh = ~maskhigh;
1690       masklow = ~masklow;
1691     }
1692
1693   return immed_double_const (masklow, maskhigh, mode);
1694 }
1695
1696 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1697    VALUE truncated to BITSIZE bits and then shifted left BITPOS bits.  */
1698
1699 static rtx
1700 lshift_value (mode, value, bitpos, bitsize)
1701      enum machine_mode mode;
1702      rtx value;
1703      int bitpos, bitsize;
1704 {
1705   unsigned HOST_WIDE_INT v = INTVAL (value);
1706   HOST_WIDE_INT low, high;
1707
1708   if (bitsize < HOST_BITS_PER_WIDE_INT)
1709     v &= ~((HOST_WIDE_INT) -1 << bitsize);
1710
1711   if (bitpos < HOST_BITS_PER_WIDE_INT)
1712     {
1713       low = v << bitpos;
1714       high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1715     }
1716   else
1717     {
1718       low = 0;
1719       high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1720     }
1721
1722   return immed_double_const (low, high, mode);
1723 }
1724 \f
1725 /* Extract a bit field that is split across two words
1726    and return an RTX for the result.
1727
1728    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1729    BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1730    UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.
1731
1732    ALIGN is the known alignment of OP0, measured in bytes.
1733    This is also the size of the memory objects to be used.  */
1734
1735 static rtx
1736 extract_split_bit_field (op0, bitsize, bitpos, unsignedp, align)
1737      rtx op0;
1738      int bitsize, bitpos, unsignedp, align;
1739 {
1740   int unit;
1741   int bitsdone = 0;
1742   rtx result = NULL_RTX;
1743   int first = 1;
1744
1745   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1746      much at a time.  */
1747   if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1748     unit = BITS_PER_WORD;
1749   else
1750     unit = MIN (align * BITS_PER_UNIT, BITS_PER_WORD);
1751
1752   while (bitsdone < bitsize)
1753     {
1754       int thissize;
1755       rtx part, word;
1756       int thispos;
1757       int offset;
1758
1759       offset = (bitpos + bitsdone) / unit;
1760       thispos = (bitpos + bitsdone) % unit;
1761
1762       /* THISSIZE must not overrun a word boundary.  Otherwise,
1763          extract_fixed_bit_field will call us again, and we will mutually
1764          recurse forever.  */
1765       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1766       thissize = MIN (thissize, unit - thispos);
1767
1768       /* If OP0 is a register, then handle OFFSET here.
1769
1770          When handling multiword bitfields, extract_bit_field may pass
1771          down a word_mode SUBREG of a larger REG for a bitfield that actually
1772          crosses a word boundary.  Thus, for a SUBREG, we must find
1773          the current word starting from the base register.  */
1774       if (GET_CODE (op0) == SUBREG)
1775         {
1776           word = operand_subword_force (SUBREG_REG (op0),
1777                                         SUBREG_WORD (op0) + offset,
1778                                         GET_MODE (SUBREG_REG (op0)));
1779           offset = 0;
1780         }
1781       else if (GET_CODE (op0) == REG)
1782         {
1783           word = operand_subword_force (op0, offset, GET_MODE (op0));
1784           offset = 0;
1785         }
1786       else
1787         word = op0;
1788
1789       /* Extract the parts in bit-counting order,
1790          whose meaning is determined by BYTES_PER_UNIT.
1791          OFFSET is in UNITs, and UNIT is in bits.
1792          extract_fixed_bit_field wants offset in bytes.  */
1793       part = extract_fixed_bit_field (word_mode, word,
1794                                       offset * unit / BITS_PER_UNIT,
1795                                       thissize, thispos, 0, 1, align);
1796       bitsdone += thissize;
1797
1798       /* Shift this part into place for the result.  */
1799       if (BYTES_BIG_ENDIAN)
1800         {
1801           if (bitsize != bitsdone)
1802             part = expand_shift (LSHIFT_EXPR, word_mode, part,
1803                                  build_int_2 (bitsize - bitsdone, 0), 0, 1);
1804         }
1805       else
1806         {
1807           if (bitsdone != thissize)
1808             part = expand_shift (LSHIFT_EXPR, word_mode, part,
1809                                  build_int_2 (bitsdone - thissize, 0), 0, 1);
1810         }
1811
1812       if (first)
1813         result = part;
1814       else
1815         /* Combine the parts with bitwise or.  This works
1816            because we extracted each part as an unsigned bit field.  */
1817         result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1818                                OPTAB_LIB_WIDEN);
1819
1820       first = 0;
1821     }
1822
1823   /* Unsigned bit field: we are done.  */
1824   if (unsignedp)
1825     return result;
1826   /* Signed bit field: sign-extend with two arithmetic shifts.  */
1827   result = expand_shift (LSHIFT_EXPR, word_mode, result,
1828                          build_int_2 (BITS_PER_WORD - bitsize, 0),
1829                          NULL_RTX, 0);
1830   return expand_shift (RSHIFT_EXPR, word_mode, result,
1831                        build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1832 }
1833 \f
1834 /* Add INC into TARGET.  */
1835
1836 void
1837 expand_inc (target, inc)
1838      rtx target, inc;
1839 {
1840   rtx value = expand_binop (GET_MODE (target), add_optab,
1841                             target, inc,
1842                             target, 0, OPTAB_LIB_WIDEN);
1843   if (value != target)
1844     emit_move_insn (target, value);
1845 }
1846
1847 /* Subtract DEC from TARGET.  */
1848
1849 void
1850 expand_dec (target, dec)
1851      rtx target, dec;
1852 {
1853   rtx value = expand_binop (GET_MODE (target), sub_optab,
1854                             target, dec,
1855                             target, 0, OPTAB_LIB_WIDEN);
1856   if (value != target)
1857     emit_move_insn (target, value);
1858 }
1859 \f
1860 /* Output a shift instruction for expression code CODE,
1861    with SHIFTED being the rtx for the value to shift,
1862    and AMOUNT the tree for the amount to shift by.
1863    Store the result in the rtx TARGET, if that is convenient.
1864    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1865    Return the rtx for where the value is.  */
1866
1867 rtx
1868 expand_shift (code, mode, shifted, amount, target, unsignedp)
1869      enum tree_code code;
1870      register enum machine_mode mode;
1871      rtx shifted;
1872      tree amount;
1873      register rtx target;
1874      int unsignedp;
1875 {
1876   register rtx op1, temp = 0;
1877   register int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1878   register int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1879   int try;
1880
1881   /* Previously detected shift-counts computed by NEGATE_EXPR
1882      and shifted in the other direction; but that does not work
1883      on all machines.  */
1884
1885   op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1886
1887 #ifdef SHIFT_COUNT_TRUNCATED
1888   if (SHIFT_COUNT_TRUNCATED)
1889     {
1890       if (GET_CODE (op1) == CONST_INT
1891           && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
1892               (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
1893         op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
1894                        % GET_MODE_BITSIZE (mode));
1895       else if (GET_CODE (op1) == SUBREG
1896                && SUBREG_WORD (op1) == 0)
1897         op1 = SUBREG_REG (op1);
1898     }
1899 #endif
1900
1901   if (op1 == const0_rtx)
1902     return shifted;
1903
1904   for (try = 0; temp == 0 && try < 3; try++)
1905     {
1906       enum optab_methods methods;
1907
1908       if (try == 0)
1909         methods = OPTAB_DIRECT;
1910       else if (try == 1)
1911         methods = OPTAB_WIDEN;
1912       else
1913         methods = OPTAB_LIB_WIDEN;
1914
1915       if (rotate)
1916         {
1917           /* Widening does not work for rotation.  */
1918           if (methods == OPTAB_WIDEN)
1919             continue;
1920           else if (methods == OPTAB_LIB_WIDEN)
1921             {
1922               /* If we have been unable to open-code this by a rotation,
1923                  do it as the IOR of two shifts.  I.e., to rotate A
1924                  by N bits, compute (A << N) | ((unsigned) A >> (C - N))
1925                  where C is the bitsize of A.
1926
1927                  It is theoretically possible that the target machine might
1928                  not be able to perform either shift and hence we would
1929                  be making two libcalls rather than just the one for the
1930                  shift (similarly if IOR could not be done).  We will allow
1931                  this extremely unlikely lossage to avoid complicating the
1932                  code below.  */
1933
1934               rtx subtarget = target == shifted ? 0 : target;
1935               rtx temp1;
1936               tree type = TREE_TYPE (amount);
1937               tree new_amount = make_tree (type, op1);
1938               tree other_amount
1939                 = fold (build (MINUS_EXPR, type,
1940                                convert (type,
1941                                         build_int_2 (GET_MODE_BITSIZE (mode),
1942                                                      0)),
1943                                amount));
1944
1945               shifted = force_reg (mode, shifted);
1946
1947               temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
1948                                    mode, shifted, new_amount, subtarget, 1);
1949               temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
1950                                     mode, shifted, other_amount, 0, 1);
1951               return expand_binop (mode, ior_optab, temp, temp1, target,
1952                                    unsignedp, methods);
1953             }
1954
1955           temp = expand_binop (mode,
1956                                left ? rotl_optab : rotr_optab,
1957                                shifted, op1, target, unsignedp, methods);
1958
1959           /* If we don't have the rotate, but we are rotating by a constant
1960              that is in range, try a rotate in the opposite direction.  */
1961
1962           if (temp == 0 && GET_CODE (op1) == CONST_INT
1963               && INTVAL (op1) > 0 && INTVAL (op1) < GET_MODE_BITSIZE (mode))
1964             temp = expand_binop (mode,
1965                                  left ? rotr_optab : rotl_optab,
1966                                  shifted,
1967                                  GEN_INT (GET_MODE_BITSIZE (mode)
1968                                           - INTVAL (op1)),
1969                                  target, unsignedp, methods);
1970         }
1971       else if (unsignedp)
1972         temp = expand_binop (mode,
1973                              left ? ashl_optab : lshr_optab,
1974                              shifted, op1, target, unsignedp, methods);
1975
1976       /* Do arithmetic shifts.
1977          Also, if we are going to widen the operand, we can just as well
1978          use an arithmetic right-shift instead of a logical one.  */
1979       if (temp == 0 && ! rotate
1980           && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
1981         {
1982           enum optab_methods methods1 = methods;
1983
1984           /* If trying to widen a log shift to an arithmetic shift,
1985              don't accept an arithmetic shift of the same size.  */
1986           if (unsignedp)
1987             methods1 = OPTAB_MUST_WIDEN;
1988
1989           /* Arithmetic shift */
1990
1991           temp = expand_binop (mode,
1992                                left ? ashl_optab : ashr_optab,
1993                                shifted, op1, target, unsignedp, methods1);
1994         }
1995
1996       /* We used to try extzv here for logical right shifts, but that was
1997          only useful for one machine, the VAX, and caused poor code
1998          generation there for lshrdi3, so the code was deleted and a
1999          define_expand for lshrsi3 was added to vax.md.  */
2000     }
2001
2002   if (temp == 0)
2003     abort ();
2004   return temp;
2005 }
2006 \f
2007 enum alg_code { alg_zero, alg_m, alg_shift,
2008                   alg_add_t_m2, alg_sub_t_m2,
2009                   alg_add_factor, alg_sub_factor,
2010                   alg_add_t2_m, alg_sub_t2_m,
2011                   alg_add, alg_subtract, alg_factor, alg_shiftop };
2012
2013 /* This structure records a sequence of operations.
2014    `ops' is the number of operations recorded.
2015    `cost' is their total cost.
2016    The operations are stored in `op' and the corresponding
2017    logarithms of the integer coefficients in `log'.
2018
2019    These are the operations:
2020    alg_zero             total := 0;
2021    alg_m                total := multiplicand;
2022    alg_shift            total := total * coeff
2023    alg_add_t_m2         total := total + multiplicand * coeff;
2024    alg_sub_t_m2         total := total - multiplicand * coeff;
2025    alg_add_factor       total := total * coeff + total;
2026    alg_sub_factor       total := total * coeff - total;
2027    alg_add_t2_m         total := total * coeff + multiplicand;
2028    alg_sub_t2_m         total := total * coeff - multiplicand;
2029
2030    The first operand must be either alg_zero or alg_m.  */
2031
2032 struct algorithm
2033 {
2034   short cost;
2035   short ops;
2036   /* The size of the OP and LOG fields are not directly related to the
2037      word size, but the worst-case algorithms will be if we have few
2038      consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2039      In that case we will generate shift-by-2, add, shift-by-2, add,...,
2040      in total wordsize operations.  */
2041   enum alg_code op[MAX_BITS_PER_WORD];
2042   char log[MAX_BITS_PER_WORD];
2043 };
2044
2045 static void synth_mult                  PROTO((struct algorithm *,
2046                                                unsigned HOST_WIDE_INT,
2047                                                int));
2048 static unsigned HOST_WIDE_INT choose_multiplier PROTO((unsigned HOST_WIDE_INT,
2049                                                        int, int,
2050                                                        unsigned HOST_WIDE_INT *,
2051                                                        int *, int *));
2052 static unsigned HOST_WIDE_INT invert_mod2n      PROTO((unsigned HOST_WIDE_INT,
2053                                                        int));
2054 /* Compute and return the best algorithm for multiplying by T.
2055    The algorithm must cost less than cost_limit
2056    If retval.cost >= COST_LIMIT, no algorithm was found and all
2057    other field of the returned struct are undefined.  */
2058
2059 static void
2060 synth_mult (alg_out, t, cost_limit)
2061      struct algorithm *alg_out;
2062      unsigned HOST_WIDE_INT t;
2063      int cost_limit;
2064 {
2065   int m;
2066   struct algorithm *alg_in, *best_alg;
2067   int cost;
2068   unsigned HOST_WIDE_INT q;
2069
2070   /* Indicate that no algorithm is yet found.  If no algorithm
2071      is found, this value will be returned and indicate failure.  */
2072   alg_out->cost = cost_limit;
2073
2074   if (cost_limit <= 0)
2075     return;
2076
2077   /* t == 1 can be done in zero cost.  */
2078   if (t == 1)
2079     {
2080       alg_out->ops = 1;
2081       alg_out->cost = 0;
2082       alg_out->op[0] = alg_m;
2083       return;
2084     }
2085
2086   /* t == 0 sometimes has a cost.  If it does and it exceeds our limit,
2087      fail now.  */
2088   if (t == 0)
2089     {
2090       if (zero_cost >= cost_limit)
2091         return;
2092       else
2093         {
2094           alg_out->ops = 1;
2095           alg_out->cost = zero_cost;
2096           alg_out->op[0] = alg_zero;
2097           return;
2098         }
2099     }
2100
2101   /* We'll be needing a couple extra algorithm structures now.  */
2102
2103   alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
2104   best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
2105
2106   /* If we have a group of zero bits at the low-order part of T, try
2107      multiplying by the remaining bits and then doing a shift.  */
2108
2109   if ((t & 1) == 0)
2110     {
2111       m = floor_log2 (t & -t);  /* m = number of low zero bits */
2112       q = t >> m;
2113       cost = shift_cost[m];
2114       synth_mult (alg_in, q, cost_limit - cost);
2115
2116       cost += alg_in->cost;
2117       if (cost < cost_limit)
2118         {
2119           struct algorithm *x;
2120           x = alg_in, alg_in = best_alg, best_alg = x;
2121           best_alg->log[best_alg->ops] = m;
2122           best_alg->op[best_alg->ops] = alg_shift;
2123           cost_limit = cost;
2124         }
2125     }
2126
2127   /* If we have an odd number, add or subtract one.  */
2128   if ((t & 1) != 0)
2129     {
2130       unsigned HOST_WIDE_INT w;
2131
2132       for (w = 1; (w & t) != 0; w <<= 1)
2133         ;
2134       /* If T was -1, then W will be zero after the loop.  This is another
2135          case where T ends with ...111.  Handling this with (T + 1) and
2136          subtract 1 produces slightly better code and results in algorithm
2137          selection much faster than treating it like the ...0111 case
2138          below.  */
2139       if (w == 0
2140           || (w > 2
2141               /* Reject the case where t is 3.
2142                  Thus we prefer addition in that case.  */
2143               && t != 3))
2144         {
2145           /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */
2146
2147           cost = add_cost;
2148           synth_mult (alg_in, t + 1, cost_limit - cost);
2149
2150           cost += alg_in->cost;
2151           if (cost < cost_limit)
2152             {
2153               struct algorithm *x;
2154               x = alg_in, alg_in = best_alg, best_alg = x;
2155               best_alg->log[best_alg->ops] = 0;
2156               best_alg->op[best_alg->ops] = alg_sub_t_m2;
2157               cost_limit = cost;
2158             }
2159         }
2160       else
2161         {
2162           /* T ends with ...01 or ...011.  Multiply by (T - 1) and add 1.  */
2163
2164           cost = add_cost;
2165           synth_mult (alg_in, t - 1, cost_limit - cost);
2166
2167           cost += alg_in->cost;
2168           if (cost < cost_limit)
2169             {
2170               struct algorithm *x;
2171               x = alg_in, alg_in = best_alg, best_alg = x;
2172               best_alg->log[best_alg->ops] = 0;
2173               best_alg->op[best_alg->ops] = alg_add_t_m2;
2174               cost_limit = cost;
2175             }
2176         }
2177     }
2178
2179   /* Look for factors of t of the form
2180      t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2181      If we find such a factor, we can multiply by t using an algorithm that
2182      multiplies by q, shift the result by m and add/subtract it to itself.
2183
2184      We search for large factors first and loop down, even if large factors
2185      are less probable than small; if we find a large factor we will find a
2186      good sequence quickly, and therefore be able to prune (by decreasing
2187      COST_LIMIT) the search.  */
2188
2189   for (m = floor_log2 (t - 1); m >= 2; m--)
2190     {
2191       unsigned HOST_WIDE_INT d;
2192
2193       d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2194       if (t % d == 0 && t > d)
2195         {
2196           cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2197           synth_mult (alg_in, t / d, cost_limit - cost);
2198
2199           cost += alg_in->cost;
2200           if (cost < cost_limit)
2201             {
2202               struct algorithm *x;
2203               x = alg_in, alg_in = best_alg, best_alg = x;
2204               best_alg->log[best_alg->ops] = m;
2205               best_alg->op[best_alg->ops] = alg_add_factor;
2206               cost_limit = cost;
2207             }
2208           /* Other factors will have been taken care of in the recursion.  */
2209           break;
2210         }
2211
2212       d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2213       if (t % d == 0 && t > d)
2214         {
2215           cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2216           synth_mult (alg_in, t / d, cost_limit - cost);
2217
2218           cost += alg_in->cost;
2219           if (cost < cost_limit)
2220             {
2221               struct algorithm *x;
2222               x = alg_in, alg_in = best_alg, best_alg = x;
2223               best_alg->log[best_alg->ops] = m;
2224               best_alg->op[best_alg->ops] = alg_sub_factor;
2225               cost_limit = cost;
2226             }
2227           break;
2228         }
2229     }
2230
2231   /* Try shift-and-add (load effective address) instructions,
2232      i.e. do a*3, a*5, a*9.  */
2233   if ((t & 1) != 0)
2234     {
2235       q = t - 1;
2236       q = q & -q;
2237       m = exact_log2 (q);
2238       if (m >= 0)
2239         {
2240           cost = shiftadd_cost[m];
2241           synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2242
2243           cost += alg_in->cost;
2244           if (cost < cost_limit)
2245             {
2246               struct algorithm *x;
2247               x = alg_in, alg_in = best_alg, best_alg = x;
2248               best_alg->log[best_alg->ops] = m;
2249               best_alg->op[best_alg->ops] = alg_add_t2_m;
2250               cost_limit = cost;
2251             }
2252         }
2253
2254       q = t + 1;
2255       q = q & -q;
2256       m = exact_log2 (q);
2257       if (m >= 0)
2258         {
2259           cost = shiftsub_cost[m];
2260           synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2261
2262           cost += alg_in->cost;
2263           if (cost < cost_limit)
2264             {
2265               struct algorithm *x;
2266               x = alg_in, alg_in = best_alg, best_alg = x;
2267               best_alg->log[best_alg->ops] = m;
2268               best_alg->op[best_alg->ops] = alg_sub_t2_m;
2269               cost_limit = cost;
2270             }
2271         }
2272     }
2273
2274   /* If cost_limit has not decreased since we stored it in alg_out->cost,
2275      we have not found any algorithm.  */
2276   if (cost_limit == alg_out->cost)
2277     return;
2278
2279   /* If we are getting a too long sequence for `struct algorithm'
2280      to record, make this search fail.  */
2281   if (best_alg->ops == MAX_BITS_PER_WORD)
2282     return;
2283
2284   /* Copy the algorithm from temporary space to the space at alg_out.
2285      We avoid using structure assignment because the majority of
2286      best_alg is normally undefined, and this is a critical function.  */
2287   alg_out->ops = best_alg->ops + 1;
2288   alg_out->cost = cost_limit;
2289   bcopy ((char *) best_alg->op, (char *) alg_out->op,
2290          alg_out->ops * sizeof *alg_out->op);
2291   bcopy ((char *) best_alg->log, (char *) alg_out->log,
2292          alg_out->ops * sizeof *alg_out->log);
2293 }
2294 \f
2295 /* Perform a multiplication and return an rtx for the result.
2296    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2297    TARGET is a suggestion for where to store the result (an rtx).
2298
2299    We check specially for a constant integer as OP1.
2300    If you want this check for OP0 as well, then before calling
2301    you should swap the two operands if OP0 would be constant.  */
2302
2303 rtx
2304 expand_mult (mode, op0, op1, target, unsignedp)
2305      enum machine_mode mode;
2306      register rtx op0, op1, target;
2307      int unsignedp;
2308 {
2309   rtx const_op1 = op1;
2310
2311   /* synth_mult does an `unsigned int' multiply.  As long as the mode is
2312      less than or equal in size to `unsigned int' this doesn't matter.
2313      If the mode is larger than `unsigned int', then synth_mult works only
2314      if the constant value exactly fits in an `unsigned int' without any
2315      truncation.  This means that multiplying by negative values does
2316      not work; results are off by 2^32 on a 32 bit machine.  */
2317
2318   /* If we are multiplying in DImode, it may still be a win
2319      to try to work with shifts and adds.  */
2320   if (GET_CODE (op1) == CONST_DOUBLE
2321       && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2322       && HOST_BITS_PER_INT >= BITS_PER_WORD
2323       && CONST_DOUBLE_HIGH (op1) == 0)
2324     const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2325   else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2326            && GET_CODE (op1) == CONST_INT
2327            && INTVAL (op1) < 0)
2328     const_op1 = 0;
2329
2330   /* We used to test optimize here, on the grounds that it's better to
2331      produce a smaller program when -O is not used.
2332      But this causes such a terrible slowdown sometimes
2333      that it seems better to use synth_mult always.  */
2334
2335   if (const_op1 && GET_CODE (const_op1) == CONST_INT)
2336     {
2337       struct algorithm alg;
2338       struct algorithm alg2;
2339       HOST_WIDE_INT val = INTVAL (op1);
2340       HOST_WIDE_INT val_so_far;
2341       rtx insn;
2342       int mult_cost;
2343       enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2344
2345       /* Try to do the computation three ways: multiply by the negative of OP1
2346          and then negate, do the multiplication directly, or do multiplication
2347          by OP1 - 1.  */
2348
2349       mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2350       mult_cost = MIN (12 * add_cost, mult_cost);
2351
2352       synth_mult (&alg, val, mult_cost);
2353
2354       /* This works only if the inverted value actually fits in an
2355          `unsigned int' */
2356       if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2357         {
2358           synth_mult (&alg2, - val,
2359                       (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2360           if (alg2.cost + negate_cost < alg.cost)
2361             alg = alg2, variant = negate_variant;
2362         }
2363
2364       /* This proves very useful for division-by-constant.  */
2365       synth_mult (&alg2, val - 1,
2366                   (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2367       if (alg2.cost + add_cost < alg.cost)
2368         alg = alg2, variant = add_variant;
2369
2370       if (alg.cost < mult_cost)
2371         {
2372           /* We found something cheaper than a multiply insn.  */
2373           int opno;
2374           rtx accum, tem;
2375
2376           op0 = protect_from_queue (op0, 0);
2377
2378           /* Avoid referencing memory over and over.
2379              For speed, but also for correctness when mem is volatile.  */
2380           if (GET_CODE (op0) == MEM)
2381             op0 = force_reg (mode, op0);
2382
2383           /* ACCUM starts out either as OP0 or as a zero, depending on
2384              the first operation.  */
2385
2386           if (alg.op[0] == alg_zero)
2387             {
2388               accum = copy_to_mode_reg (mode, const0_rtx);
2389               val_so_far = 0;
2390             }
2391           else if (alg.op[0] == alg_m)
2392             {
2393               accum = copy_to_mode_reg (mode, op0);
2394               val_so_far = 1;
2395             }
2396           else
2397             abort ();
2398
2399           for (opno = 1; opno < alg.ops; opno++)
2400             {
2401               int log = alg.log[opno];
2402               int preserve = preserve_subexpressions_p ();
2403               rtx shift_subtarget = preserve ? 0 : accum;
2404               rtx add_target
2405                 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2406                    && ! preserve)
2407                   ? target : 0;
2408               rtx accum_target = preserve ? 0 : accum;
2409
2410               switch (alg.op[opno])
2411                 {
2412                 case alg_shift:
2413                   accum = expand_shift (LSHIFT_EXPR, mode, accum,
2414                                         build_int_2 (log, 0), NULL_RTX, 0);
2415                   val_so_far <<= log;
2416                   break;
2417
2418                 case alg_add_t_m2:
2419                   tem = expand_shift (LSHIFT_EXPR, mode, op0,
2420                                       build_int_2 (log, 0), NULL_RTX, 0);
2421                   accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2422                                          add_target ? add_target : accum_target);
2423                   val_so_far += (HOST_WIDE_INT) 1 << log;
2424                   break;
2425
2426                 case alg_sub_t_m2:
2427                   tem = expand_shift (LSHIFT_EXPR, mode, op0,
2428                                       build_int_2 (log, 0), NULL_RTX, 0);
2429                   accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2430                                          add_target ? add_target : accum_target);
2431                   val_so_far -= (HOST_WIDE_INT) 1 << log;
2432                   break;
2433
2434                 case alg_add_t2_m:
2435                   accum = expand_shift (LSHIFT_EXPR, mode, accum,
2436                                         build_int_2 (log, 0), shift_subtarget,
2437                                         0);
2438                   accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2439                                          add_target ? add_target : accum_target);
2440                   val_so_far = (val_so_far << log) + 1;
2441                   break;
2442
2443                 case alg_sub_t2_m:
2444                   accum = expand_shift (LSHIFT_EXPR, mode, accum,
2445                                         build_int_2 (log, 0), shift_subtarget,
2446                                         0);
2447                   accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2448                                          add_target ? add_target : accum_target);
2449                   val_so_far = (val_so_far << log) - 1;
2450                   break;
2451
2452                 case alg_add_factor:
2453                   tem = expand_shift (LSHIFT_EXPR, mode, accum,
2454                                       build_int_2 (log, 0), NULL_RTX, 0);
2455                   accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2456                                          add_target ? add_target : accum_target);
2457                   val_so_far += val_so_far << log;
2458                   break;
2459
2460                 case alg_sub_factor:
2461                   tem = expand_shift (LSHIFT_EXPR, mode, accum,
2462                                       build_int_2 (log, 0), NULL_RTX, 0);
2463                   accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2464                                          (add_target ? add_target
2465                                           : preserve ? 0 : tem));
2466                   val_so_far = (val_so_far << log) - val_so_far;
2467                   break;
2468
2469                 default:
2470                   abort ();;
2471                 }
2472
2473               /* Write a REG_EQUAL note on the last insn so that we can cse
2474                  multiplication sequences.  */
2475
2476               insn = get_last_insn ();
2477               set_unique_reg_note (insn,
2478                                    REG_EQUAL,
2479                                    gen_rtx_MULT (mode, op0,
2480                                                  GEN_INT (val_so_far)));
2481             }
2482
2483           if (variant == negate_variant)
2484             {
2485               val_so_far = - val_so_far;
2486               accum = expand_unop (mode, neg_optab, accum, target, 0);
2487             }
2488           else if (variant == add_variant)
2489             {
2490               val_so_far = val_so_far + 1;
2491               accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2492             }
2493
2494           if (val != val_so_far)
2495             abort ();
2496
2497           return accum;
2498         }
2499     }
2500
2501   /* This used to use umul_optab if unsigned, but for non-widening multiply
2502      there is no difference between signed and unsigned.  */
2503   op0 = expand_binop (mode, smul_optab,
2504                       op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2505   if (op0 == 0)
2506     abort ();
2507   return op0;
2508 }
2509 \f
2510 /* Return the smallest n such that 2**n >= X.  */
2511
2512 int
2513 ceil_log2 (x)
2514      unsigned HOST_WIDE_INT x;
2515 {
2516   return floor_log2 (x - 1) + 1;
2517 }
2518
2519 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2520    replace division by D, and put the least significant N bits of the result
2521    in *MULTIPLIER_PTR and return the most significant bit.
2522
2523    The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2524    needed precision is in PRECISION (should be <= N).
2525
2526    PRECISION should be as small as possible so this function can choose
2527    multiplier more freely.
2528
2529    The rounded-up logarithm of D is placed in *lgup_ptr.  A shift count that
2530    is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2531
2532    Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2533    where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier.  */
2534
2535 static
2536 unsigned HOST_WIDE_INT
2537 choose_multiplier (d, n, precision, multiplier_ptr, post_shift_ptr, lgup_ptr)
2538      unsigned HOST_WIDE_INT d;
2539      int n;
2540      int precision;
2541      unsigned HOST_WIDE_INT *multiplier_ptr;
2542      int *post_shift_ptr;
2543      int *lgup_ptr;
2544 {
2545   unsigned HOST_WIDE_INT mhigh_hi, mhigh_lo;
2546   unsigned HOST_WIDE_INT mlow_hi, mlow_lo;
2547   int lgup, post_shift;
2548   int pow, pow2;
2549   unsigned HOST_WIDE_INT nh, nl, dummy1, dummy2;
2550
2551   /* lgup = ceil(log2(divisor)); */
2552   lgup = ceil_log2 (d);
2553
2554   if (lgup > n)
2555     abort ();
2556
2557   pow = n + lgup;
2558   pow2 = n + lgup - precision;
2559
2560   if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2561     {
2562       /* We could handle this with some effort, but this case is much better
2563          handled directly with a scc insn, so rely on caller using that.  */
2564       abort ();
2565     }
2566
2567   /* mlow = 2^(N + lgup)/d */
2568  if (pow >= HOST_BITS_PER_WIDE_INT)
2569     {
2570       nh = (unsigned HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2571       nl = 0;
2572     }
2573   else
2574     {
2575       nh = 0;
2576       nl = (unsigned HOST_WIDE_INT) 1 << pow;
2577     }
2578   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2579                         &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2580
2581   /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2582   if (pow2 >= HOST_BITS_PER_WIDE_INT)
2583     nh |= (unsigned HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2584   else
2585     nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2586   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2587                         &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2588
2589   if (mhigh_hi && nh - d >= d)
2590     abort ();
2591   if (mhigh_hi > 1 || mlow_hi > 1)
2592     abort ();
2593   /* assert that mlow < mhigh.  */
2594   if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2595     abort();
2596
2597   /* If precision == N, then mlow, mhigh exceed 2^N
2598      (but they do not exceed 2^(N+1)).  */
2599
2600   /* Reduce to lowest terms */
2601   for (post_shift = lgup; post_shift > 0; post_shift--)
2602     {
2603       unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2604       unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2605       if (ml_lo >= mh_lo)
2606         break;
2607
2608       mlow_hi = 0;
2609       mlow_lo = ml_lo;
2610       mhigh_hi = 0;
2611       mhigh_lo = mh_lo;
2612     }
2613
2614   *post_shift_ptr = post_shift;
2615   *lgup_ptr = lgup;
2616   if (n < HOST_BITS_PER_WIDE_INT)
2617     {
2618       unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2619       *multiplier_ptr = mhigh_lo & mask;
2620       return mhigh_lo >= mask;
2621     }
2622   else
2623     {
2624       *multiplier_ptr = mhigh_lo;
2625       return mhigh_hi;
2626     }
2627 }
2628
2629 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2630    congruent to 1 (mod 2**N).  */
2631
2632 static unsigned HOST_WIDE_INT
2633 invert_mod2n (x, n)
2634      unsigned HOST_WIDE_INT x;
2635      int n;
2636 {
2637   /* Solve x*y == 1 (mod 2^n), where x is odd.  Return y.  */
2638
2639   /* The algorithm notes that the choice y = x satisfies
2640      x*y == 1 mod 2^3, since x is assumed odd.
2641      Each iteration doubles the number of bits of significance in y.  */
2642
2643   unsigned HOST_WIDE_INT mask;
2644   unsigned HOST_WIDE_INT y = x;
2645   int nbit = 3;
2646
2647   mask = (n == HOST_BITS_PER_WIDE_INT
2648           ? ~(unsigned HOST_WIDE_INT) 0
2649           : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2650
2651   while (nbit < n)
2652     {
2653       y = y * (2 - x*y) & mask;         /* Modulo 2^N */
2654       nbit *= 2;
2655     }
2656   return y;
2657 }
2658
2659 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2660    flavor of OP0 and OP1.  ADJ_OPERAND is already the high half of the
2661    product OP0 x OP1.  If UNSIGNEDP is nonzero, adjust the signed product
2662    to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2663    become signed.
2664
2665    The result is put in TARGET if that is convenient.
2666
2667    MODE is the mode of operation.  */
2668
2669 rtx
2670 expand_mult_highpart_adjust (mode, adj_operand, op0, op1, target, unsignedp)
2671      enum machine_mode mode;
2672      register rtx adj_operand, op0, op1, target;
2673      int unsignedp;
2674 {
2675   rtx tem;
2676   enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2677
2678   tem = expand_shift (RSHIFT_EXPR, mode, op0,
2679                       build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2680                       NULL_RTX, 0);
2681   tem = expand_and (tem, op1, NULL_RTX);
2682   adj_operand
2683     = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2684                      adj_operand);
2685
2686   tem = expand_shift (RSHIFT_EXPR, mode, op1,
2687                       build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2688                       NULL_RTX, 0);
2689   tem = expand_and (tem, op0, NULL_RTX);
2690   target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2691                           target);
2692
2693   return target;
2694 }
2695
2696 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2697    in TARGET if that is convenient, and return where the result is.  If the
2698    operation can not be performed, 0 is returned.
2699
2700    MODE is the mode of operation and result.
2701
2702    UNSIGNEDP nonzero means unsigned multiply.
2703
2704    MAX_COST is the total allowed cost for the expanded RTL.  */
2705
2706 rtx
2707 expand_mult_highpart (mode, op0, cnst1, target, unsignedp, max_cost)
2708      enum machine_mode mode;
2709      register rtx op0, target;
2710      unsigned HOST_WIDE_INT cnst1;
2711      int unsignedp;
2712      int max_cost;
2713 {
2714   enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2715   optab mul_highpart_optab;
2716   optab moptab;
2717   rtx tem;
2718   int size = GET_MODE_BITSIZE (mode);
2719   rtx op1, wide_op1;
2720
2721   /* We can't support modes wider than HOST_BITS_PER_INT.  */
2722   if (size > HOST_BITS_PER_WIDE_INT)
2723     abort ();
2724
2725   op1 = GEN_INT (cnst1);
2726
2727   if (GET_MODE_BITSIZE (wider_mode) <= HOST_BITS_PER_INT)
2728     wide_op1 = op1;
2729   else
2730     wide_op1
2731       = immed_double_const (cnst1,
2732                             (unsignedp
2733                              ? (HOST_WIDE_INT) 0
2734                              : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2735                             wider_mode);
2736
2737   /* expand_mult handles constant multiplication of word_mode
2738      or narrower.  It does a poor job for large modes.  */
2739   if (size < BITS_PER_WORD
2740       && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2741     {
2742       /* We have to do this, since expand_binop doesn't do conversion for
2743          multiply.  Maybe change expand_binop to handle widening multiply?  */
2744       op0 = convert_to_mode (wider_mode, op0, unsignedp);
2745
2746       tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, unsignedp);
2747       tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2748                           build_int_2 (size, 0), NULL_RTX, 1);
2749       return convert_modes (mode, wider_mode, tem, unsignedp);
2750     }
2751
2752   if (target == 0)
2753     target = gen_reg_rtx (mode);
2754
2755   /* Firstly, try using a multiplication insn that only generates the needed
2756      high part of the product, and in the sign flavor of unsignedp.  */
2757   if (mul_highpart_cost[(int) mode] < max_cost)
2758     {
2759       mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2760       target = expand_binop (mode, mul_highpart_optab,
2761                              op0, wide_op1, target, unsignedp, OPTAB_DIRECT);
2762       if (target)
2763         return target;
2764     }
2765
2766   /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2767      Need to adjust the result after the multiplication.  */
2768   if (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost < max_cost)
2769     {
2770       mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2771       target = expand_binop (mode, mul_highpart_optab,
2772                              op0, wide_op1, target, unsignedp, OPTAB_DIRECT);
2773       if (target)
2774         /* We used the wrong signedness.  Adjust the result.  */
2775         return expand_mult_highpart_adjust (mode, target, op0,
2776                                             op1, target, unsignedp);
2777     }
2778
2779   /* Try widening multiplication.  */
2780   moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2781   if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2782       && mul_widen_cost[(int) wider_mode] < max_cost)
2783     {
2784       op1 = force_reg (mode, op1);
2785       goto try;
2786     }
2787
2788   /* Try widening the mode and perform a non-widening multiplication.  */
2789   moptab = smul_optab;
2790   if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2791       && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2792     {
2793       op1 = wide_op1;
2794       goto try;
2795     }
2796
2797   /* Try widening multiplication of opposite signedness, and adjust.  */
2798   moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2799   if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2800       && (mul_widen_cost[(int) wider_mode]
2801           + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2802     {
2803       rtx regop1 = force_reg (mode, op1);
2804       tem = expand_binop (wider_mode, moptab, op0, regop1,
2805                           NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2806       if (tem != 0)
2807         {
2808           /* Extract the high half of the just generated product.  */
2809           tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2810                               build_int_2 (size, 0), NULL_RTX, 1);
2811           tem = convert_modes (mode, wider_mode, tem, unsignedp);
2812           /* We used the wrong signedness.  Adjust the result.  */
2813           return expand_mult_highpart_adjust (mode, tem, op0, op1,
2814                                               target, unsignedp);
2815         }
2816     }
2817
2818   return 0;
2819
2820  try:
2821   /* Pass NULL_RTX as target since TARGET has wrong mode.  */
2822   tem = expand_binop (wider_mode, moptab, op0, op1,
2823                       NULL_RTX, unsignedp, OPTAB_WIDEN);
2824   if (tem == 0)
2825     return 0;
2826
2827   /* Extract the high half of the just generated product.  */
2828   if (mode == word_mode)
2829     {
2830       return gen_highpart (mode, tem);
2831     }
2832   else
2833     {
2834       tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2835                           build_int_2 (size, 0), NULL_RTX, 1);
2836       return convert_modes (mode, wider_mode, tem, unsignedp);
2837     }
2838 }
2839 \f
2840 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2841    if that is convenient, and returning where the result is.
2842    You may request either the quotient or the remainder as the result;
2843    specify REM_FLAG nonzero to get the remainder.
2844
2845    CODE is the expression code for which kind of division this is;
2846    it controls how rounding is done.  MODE is the machine mode to use.
2847    UNSIGNEDP nonzero means do unsigned division.  */
2848
2849 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2850    and then correct it by or'ing in missing high bits
2851    if result of ANDI is nonzero.
2852    For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2853    This could optimize to a bfexts instruction.
2854    But C doesn't use these operations, so their optimizations are
2855    left for later.  */
2856 /* ??? For modulo, we don't actually need the highpart of the first product,
2857    the low part will do nicely.  And for small divisors, the second multiply
2858    can also be a low-part only multiply or even be completely left out.
2859    E.g. to calculate the remainder of a division by 3 with a 32 bit
2860    multiply, multiply with 0x55555556 and extract the upper two bits;
2861    the result is exact for inputs up to 0x1fffffff.
2862    The input range can be reduced by using cross-sum rules.
2863    For odd divisors >= 3, the following table gives right shift counts
2864    so that if an number is shifted by an integer multiple of the given
2865    amount, the remainder stays the same:
2866    2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
2867    14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
2868    0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
2869    20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
2870    0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
2871
2872    Cross-sum rules for even numbers can be derived by leaving as many bits
2873    to the right alone as the divisor has zeros to the right.
2874    E.g. if x is an unsigned 32 bit number:
2875    (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
2876    */
2877
2878 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
2879
2880 rtx
2881 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2882      int rem_flag;
2883      enum tree_code code;
2884      enum machine_mode mode;
2885      register rtx op0, op1, target;
2886      int unsignedp;
2887 {
2888   enum machine_mode compute_mode;
2889   register rtx tquotient;
2890   rtx quotient = 0, remainder = 0;
2891   rtx last;
2892   int size;
2893   rtx insn, set;
2894   optab optab1, optab2;
2895   int op1_is_constant, op1_is_pow2;
2896   int max_cost, extra_cost;
2897   static HOST_WIDE_INT last_div_const = 0;
2898
2899   op1_is_constant = GET_CODE (op1) == CONST_INT;
2900   op1_is_pow2 = (op1_is_constant
2901                  && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
2902                       || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1))))));
2903
2904   /*
2905      This is the structure of expand_divmod:
2906
2907      First comes code to fix up the operands so we can perform the operations
2908      correctly and efficiently.
2909
2910      Second comes a switch statement with code specific for each rounding mode.
2911      For some special operands this code emits all RTL for the desired
2912      operation, for other cases, it generates only a quotient and stores it in
2913      QUOTIENT.  The case for trunc division/remainder might leave quotient = 0,
2914      to indicate that it has not done anything.
2915
2916      Last comes code that finishes the operation.  If QUOTIENT is set and
2917      REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1.  If
2918      QUOTIENT is not set, it is computed using trunc rounding.
2919
2920      We try to generate special code for division and remainder when OP1 is a
2921      constant.  If |OP1| = 2**n we can use shifts and some other fast
2922      operations.  For other values of OP1, we compute a carefully selected
2923      fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
2924      by m.
2925
2926      In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
2927      half of the product.  Different strategies for generating the product are
2928      implemented in expand_mult_highpart.
2929
2930      If what we actually want is the remainder, we generate that by another
2931      by-constant multiplication and a subtraction.  */
2932
2933   /* We shouldn't be called with OP1 == const1_rtx, but some of the
2934      code below will malfunction if we are, so check here and handle
2935      the special case if so.  */
2936   if (op1 == const1_rtx)
2937     return rem_flag ? const0_rtx : op0;
2938
2939   if (target
2940       /* Don't use the function value register as a target
2941          since we have to read it as well as write it,
2942          and function-inlining gets confused by this.  */
2943       && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
2944           /* Don't clobber an operand while doing a multi-step calculation.  */
2945           || ((rem_flag || op1_is_constant)
2946               && (reg_mentioned_p (target, op0)
2947                   || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
2948           || reg_mentioned_p (target, op1)
2949           || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
2950     target = 0;
2951
2952   /* Get the mode in which to perform this computation.  Normally it will
2953      be MODE, but sometimes we can't do the desired operation in MODE.
2954      If so, pick a wider mode in which we can do the operation.  Convert
2955      to that mode at the start to avoid repeated conversions.
2956
2957      First see what operations we need.  These depend on the expression
2958      we are evaluating.  (We assume that divxx3 insns exist under the
2959      same conditions that modxx3 insns and that these insns don't normally
2960      fail.  If these assumptions are not correct, we may generate less
2961      efficient code in some cases.)
2962
2963      Then see if we find a mode in which we can open-code that operation
2964      (either a division, modulus, or shift).  Finally, check for the smallest
2965      mode for which we can do the operation with a library call.  */
2966
2967   /* We might want to refine this now that we have division-by-constant
2968      optimization.  Since expand_mult_highpart tries so many variants, it is
2969      not straightforward to generalize this.  Maybe we should make an array
2970      of possible modes in init_expmed?  Save this for GCC 2.7.  */
2971
2972   optab1 = (op1_is_pow2 ? (unsignedp ? lshr_optab : ashr_optab)
2973             : (unsignedp ? udiv_optab : sdiv_optab));
2974   optab2 = (op1_is_pow2 ? optab1 : (unsignedp ? udivmod_optab : sdivmod_optab));
2975
2976   for (compute_mode = mode; compute_mode != VOIDmode;
2977        compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2978     if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
2979         || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
2980       break;
2981
2982   if (compute_mode == VOIDmode)
2983     for (compute_mode = mode; compute_mode != VOIDmode;
2984          compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2985       if (optab1->handlers[(int) compute_mode].libfunc
2986           || optab2->handlers[(int) compute_mode].libfunc)
2987         break;
2988
2989   /* If we still couldn't find a mode, use MODE, but we'll probably abort
2990      in expand_binop.  */
2991   if (compute_mode == VOIDmode)
2992     compute_mode = mode;
2993
2994   if (target && GET_MODE (target) == compute_mode)
2995     tquotient = target;
2996   else
2997     tquotient = gen_reg_rtx (compute_mode);
2998
2999   size = GET_MODE_BITSIZE (compute_mode);
3000 #if 0
3001   /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3002      (mode), and thereby get better code when OP1 is a constant.  Do that
3003      later.  It will require going over all usages of SIZE below.  */
3004   size = GET_MODE_BITSIZE (mode);
3005 #endif
3006
3007   /* Only deduct something for a REM if the last divide done was
3008      for a different constant.   Then set the constant of the last
3009      divide.  */
3010   max_cost = div_cost[(int) compute_mode]
3011     - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3012                       && INTVAL (op1) == last_div_const)
3013        ? mul_cost[(int) compute_mode] + add_cost : 0);
3014
3015   last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3016
3017   /* Now convert to the best mode to use.  */
3018   if (compute_mode != mode)
3019     {
3020       op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3021       op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3022
3023       /* convert_modes may have placed op1 into a register, so we
3024          must recompute the following.  */
3025       op1_is_constant = GET_CODE (op1) == CONST_INT;
3026       op1_is_pow2 = (op1_is_constant
3027                      && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3028                           || (! unsignedp
3029                               && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3030     }
3031
3032   /* If one of the operands is a volatile MEM, copy it into a register.  */
3033
3034   if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3035     op0 = force_reg (compute_mode, op0);
3036   if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3037     op1 = force_reg (compute_mode, op1);
3038
3039   /* If we need the remainder or if OP1 is constant, we need to
3040      put OP0 in a register in case it has any queued subexpressions.  */
3041   if (rem_flag || op1_is_constant)
3042     op0 = force_reg (compute_mode, op0);
3043
3044   last = get_last_insn ();
3045
3046   /* Promote floor rounding to trunc rounding for unsigned operations.  */
3047   if (unsignedp)
3048     {
3049       if (code == FLOOR_DIV_EXPR)
3050         code = TRUNC_DIV_EXPR;
3051       if (code == FLOOR_MOD_EXPR)
3052         code = TRUNC_MOD_EXPR;
3053       if (code == EXACT_DIV_EXPR && op1_is_pow2)
3054         code = TRUNC_DIV_EXPR;
3055     }
3056
3057   if (op1 != const0_rtx)
3058     switch (code)
3059       {
3060       case TRUNC_MOD_EXPR:
3061       case TRUNC_DIV_EXPR:
3062         if (op1_is_constant)
3063           {
3064             if (unsignedp)
3065               {
3066                 unsigned HOST_WIDE_INT mh, ml;
3067                 int pre_shift, post_shift;
3068                 int dummy;
3069                 unsigned HOST_WIDE_INT d = INTVAL (op1);
3070
3071                 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3072                   {
3073                     pre_shift = floor_log2 (d);
3074                     if (rem_flag)
3075                       {
3076                         remainder
3077                           = expand_binop (compute_mode, and_optab, op0,
3078                                           GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3079                                           remainder, 1,
3080                                           OPTAB_LIB_WIDEN);
3081                         if (remainder)
3082                           return gen_lowpart (mode, remainder);
3083                       }
3084                     quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3085                                              build_int_2 (pre_shift, 0),
3086                                              tquotient, 1);
3087                   }
3088                 else if (size <= HOST_BITS_PER_WIDE_INT)
3089                   {
3090                     if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3091                       {
3092                         /* Most significant bit of divisor is set; emit an scc
3093                            insn.  */
3094                         quotient = emit_store_flag (tquotient, GEU, op0, op1,
3095                                                     compute_mode, 1, 1);
3096                         if (quotient == 0)
3097                           goto fail1;
3098                       }
3099                     else
3100                       {
3101                         /* Find a suitable multiplier and right shift count
3102                            instead of multiplying with D.  */
3103
3104                         mh = choose_multiplier (d, size, size,
3105                                                 &ml, &post_shift, &dummy);
3106
3107                         /* If the suggested multiplier is more than SIZE bits,
3108                            we can do better for even divisors, using an
3109                            initial right shift.  */
3110                         if (mh != 0 && (d & 1) == 0)
3111                           {
3112                             pre_shift = floor_log2 (d & -d);
3113                             mh = choose_multiplier (d >> pre_shift, size,
3114                                                     size - pre_shift,
3115                                                     &ml, &post_shift, &dummy);
3116                             if (mh)
3117                               abort ();
3118                           }
3119                         else
3120                           pre_shift = 0;
3121
3122                         if (mh != 0)
3123                           {
3124                             rtx t1, t2, t3, t4;
3125
3126                             extra_cost = (shift_cost[post_shift - 1]
3127                                           + shift_cost[1] + 2 * add_cost);
3128                             t1 = expand_mult_highpart (compute_mode, op0, ml,
3129                                                        NULL_RTX, 1,
3130                                                        max_cost - extra_cost);
3131                             if (t1 == 0)
3132                               goto fail1;
3133                             t2 = force_operand (gen_rtx_MINUS (compute_mode,
3134                                                                op0, t1),
3135                                                 NULL_RTX);
3136                             t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3137                                                build_int_2 (1, 0), NULL_RTX,1);
3138                             t4 = force_operand (gen_rtx_PLUS (compute_mode,
3139                                                               t1, t3),
3140                                                 NULL_RTX);
3141                             quotient
3142                               = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3143                                               build_int_2 (post_shift - 1, 0),
3144                                               tquotient, 1);
3145                           }
3146                         else
3147                           {
3148                             rtx t1, t2;
3149
3150                             t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3151                                                build_int_2 (pre_shift, 0),
3152                                                NULL_RTX, 1);
3153                             extra_cost = (shift_cost[pre_shift]
3154                                           + shift_cost[post_shift]);
3155                             t2 = expand_mult_highpart (compute_mode, t1, ml,
3156                                                        NULL_RTX, 1,
3157                                                        max_cost - extra_cost);
3158                             if (t2 == 0)
3159                               goto fail1;
3160                             quotient
3161                               = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3162                                               build_int_2 (post_shift, 0),
3163                                               tquotient, 1);
3164                           }
3165                       }
3166                   }
3167                 else            /* Too wide mode to use tricky code */
3168                   break;
3169
3170                 insn = get_last_insn ();
3171                 if (insn != last
3172                     && (set = single_set (insn)) != 0
3173                     && SET_DEST (set) == quotient)
3174                   set_unique_reg_note (insn,
3175                                        REG_EQUAL,
3176                                        gen_rtx_UDIV (compute_mode, op0, op1));
3177               }
3178             else                /* TRUNC_DIV, signed */
3179               {
3180                 unsigned HOST_WIDE_INT ml;
3181                 int lgup, post_shift;
3182                 HOST_WIDE_INT d = INTVAL (op1);
3183                 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3184
3185                 /* n rem d = n rem -d */
3186                 if (rem_flag && d < 0)
3187                   {
3188                     d = abs_d;
3189                     op1 = GEN_INT (abs_d);
3190                   }
3191
3192                 if (d == 1)
3193                   quotient = op0;
3194                 else if (d == -1)
3195                   quotient = expand_unop (compute_mode, neg_optab, op0,
3196                                           tquotient, 0);
3197                 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3198                   {
3199                     /* This case is not handled correctly below.  */
3200                     quotient = emit_store_flag (tquotient, EQ, op0, op1,
3201                                                 compute_mode, 1, 1);
3202                     if (quotient == 0)
3203                       goto fail1;
3204                   }
3205                 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3206                          && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap))
3207                   ;
3208                 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3209                   {
3210                     lgup = floor_log2 (abs_d);
3211                     if (abs_d != 2 && BRANCH_COST < 3)
3212                       {
3213                         rtx label = gen_label_rtx ();
3214                         rtx t1;
3215
3216                         t1 = copy_to_mode_reg (compute_mode, op0);
3217                         do_cmp_and_jump (t1, const0_rtx, GE,
3218                                          compute_mode, label);
3219                         expand_inc (t1, GEN_INT (abs_d - 1));
3220                         emit_label (label);
3221                         quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3222                                                  build_int_2 (lgup, 0),
3223                                                  tquotient, 0);
3224                       }
3225                     else
3226                       {
3227                         rtx t1, t2, t3;
3228                         t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3229                                            build_int_2 (size - 1, 0),
3230                                            NULL_RTX, 0);
3231                         t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3232                                            build_int_2 (size - lgup, 0),
3233                                            NULL_RTX, 1);
3234                         t3 = force_operand (gen_rtx_PLUS (compute_mode,
3235                                                           op0, t2),
3236                                             NULL_RTX);
3237                         quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3238                                                  build_int_2 (lgup, 0),
3239                                                  tquotient, 0);
3240                       }
3241
3242                     /* We have computed OP0 / abs(OP1).  If OP1 is negative, negate
3243                        the quotient.  */
3244                     if (d < 0)
3245                       {
3246                         insn = get_last_insn ();
3247                         if (insn != last
3248                             && (set = single_set (insn)) != 0
3249                             && SET_DEST (set) == quotient
3250                             && abs_d < ((unsigned HOST_WIDE_INT) 1
3251                                         << (HOST_BITS_PER_WIDE_INT - 1)))
3252                           set_unique_reg_note (insn,
3253                                                REG_EQUAL,
3254                                                gen_rtx_DIV (compute_mode,
3255                                                             op0,
3256                                                             GEN_INT (abs_d)));
3257
3258                         quotient = expand_unop (compute_mode, neg_optab,
3259                                                 quotient, quotient, 0);
3260                       }
3261                   }
3262                 else if (size <= HOST_BITS_PER_WIDE_INT)
3263                   {
3264                     choose_multiplier (abs_d, size, size - 1,
3265                                        &ml, &post_shift, &lgup);
3266                     if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3267                       {
3268                         rtx t1, t2, t3;
3269
3270                         extra_cost = (shift_cost[post_shift]
3271                                       + shift_cost[size - 1] + add_cost);
3272                         t1 = expand_mult_highpart (compute_mode, op0, ml,
3273                                                    NULL_RTX, 0,
3274                                                    max_cost - extra_cost);
3275                         if (t1 == 0)
3276                           goto fail1;
3277                         t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3278                                            build_int_2 (post_shift, 0), NULL_RTX, 0);
3279                         t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3280                                            build_int_2 (size - 1, 0), NULL_RTX, 0);
3281                         if (d < 0)
3282                           quotient = force_operand (gen_rtx_MINUS (compute_mode, t3, t2),
3283                                                     tquotient);
3284                         else
3285                           quotient = force_operand (gen_rtx_MINUS (compute_mode, t2, t3),
3286                                                     tquotient);
3287                       }
3288                     else
3289                       {
3290                         rtx t1, t2, t3, t4;
3291
3292                         ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3293                         extra_cost = (shift_cost[post_shift]
3294                                       + shift_cost[size - 1] + 2 * add_cost);
3295                         t1 = expand_mult_highpart (compute_mode, op0, ml,
3296                                                    NULL_RTX, 0,
3297                                                    max_cost - extra_cost);
3298                         if (t1 == 0)
3299                           goto fail1;
3300                         t2 = force_operand (gen_rtx_PLUS (compute_mode, t1, op0),
3301                                             NULL_RTX);
3302                         t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3303                                            build_int_2 (post_shift, 0), NULL_RTX, 0);
3304                         t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3305                                            build_int_2 (size - 1, 0), NULL_RTX, 0);
3306                         if (d < 0)
3307                           quotient = force_operand (gen_rtx_MINUS (compute_mode, t4, t3),
3308                                                     tquotient);
3309                         else
3310                           quotient = force_operand (gen_rtx_MINUS (compute_mode, t3, t4),
3311                                                     tquotient);
3312                       }
3313                   }
3314                 else            /* Too wide mode to use tricky code */
3315                   break;
3316
3317                 insn = get_last_insn ();
3318                 if (insn != last
3319                     && (set = single_set (insn)) != 0
3320                     && SET_DEST (set) == quotient)
3321                   set_unique_reg_note (insn,
3322                                        REG_EQUAL,
3323                                        gen_rtx_DIV (compute_mode, op0, op1));
3324               }
3325             break;
3326           }
3327       fail1:
3328         delete_insns_since (last);
3329         break;
3330
3331       case FLOOR_DIV_EXPR:
3332       case FLOOR_MOD_EXPR:
3333       /* We will come here only for signed operations.  */
3334         if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3335           {
3336             unsigned HOST_WIDE_INT mh, ml;
3337             int pre_shift, lgup, post_shift;
3338             HOST_WIDE_INT d = INTVAL (op1);
3339
3340             if (d > 0)
3341               {
3342                 /* We could just as easily deal with negative constants here,
3343                    but it does not seem worth the trouble for GCC 2.6.  */
3344                 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3345                   {
3346                     pre_shift = floor_log2 (d);
3347                     if (rem_flag)
3348                       {
3349                         remainder = expand_binop (compute_mode, and_optab, op0,
3350                                                   GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3351                                                   remainder, 0, OPTAB_LIB_WIDEN);
3352                         if (remainder)
3353                           return gen_lowpart (mode, remainder);
3354                       }
3355                     quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3356                                              build_int_2 (pre_shift, 0),
3357                                              tquotient, 0);
3358                   }
3359                 else
3360                   {
3361                     rtx t1, t2, t3, t4;
3362
3363                     mh = choose_multiplier (d, size, size - 1,
3364                                             &ml, &post_shift, &lgup);
3365                     if (mh)
3366                       abort ();
3367
3368                     t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3369                                        build_int_2 (size - 1, 0), NULL_RTX, 0);
3370                     t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3371                                        NULL_RTX, 0, OPTAB_WIDEN);
3372                     extra_cost = (shift_cost[post_shift]
3373                                   + shift_cost[size - 1] + 2 * add_cost);
3374                     t3 = expand_mult_highpart (compute_mode, t2, ml,
3375                                                NULL_RTX, 1,
3376                                                max_cost - extra_cost);
3377                     if (t3 != 0)
3378                       {
3379                         t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3380                                            build_int_2 (post_shift, 0),
3381                                            NULL_RTX, 1);
3382                         quotient = expand_binop (compute_mode, xor_optab,
3383                                                  t4, t1, tquotient, 0,
3384                                                  OPTAB_WIDEN);
3385                       }
3386                   }
3387               }
3388             else
3389               {
3390                 rtx nsign, t1, t2, t3, t4;
3391                 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3392                                                   op0, constm1_rtx), NULL_RTX);
3393                 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3394                                    0, OPTAB_WIDEN);
3395                 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3396                                       build_int_2 (size - 1, 0), NULL_RTX, 0);
3397                 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3398                                     NULL_RTX);
3399                 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3400                                     NULL_RTX, 0);
3401                 if (t4)
3402                   {
3403                     rtx t5;
3404                     t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3405                                       NULL_RTX, 0);
3406                     quotient = force_operand (gen_rtx_PLUS (compute_mode,
3407                                                             t4, t5),
3408                                               tquotient);
3409                   }
3410               }
3411           }
3412
3413         if (quotient != 0)
3414           break;
3415         delete_insns_since (last);
3416
3417         /* Try using an instruction that produces both the quotient and
3418            remainder, using truncation.  We can easily compensate the quotient
3419            or remainder to get floor rounding, once we have the remainder.
3420            Notice that we compute also the final remainder value here,
3421            and return the result right away.  */
3422         if (target == 0 || GET_MODE (target) != compute_mode)
3423           target = gen_reg_rtx (compute_mode);
3424
3425         if (rem_flag)
3426           {
3427             remainder
3428               = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3429             quotient = gen_reg_rtx (compute_mode);
3430           }
3431         else
3432           {
3433             quotient
3434               = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3435             remainder = gen_reg_rtx (compute_mode);
3436           }
3437
3438         if (expand_twoval_binop (sdivmod_optab, op0, op1,
3439                                  quotient, remainder, 0))
3440           {
3441             /* This could be computed with a branch-less sequence.
3442                Save that for later.  */
3443             rtx tem;
3444             rtx label = gen_label_rtx ();
3445             do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3446             tem = expand_binop (compute_mode, xor_optab, op0, op1,
3447                                 NULL_RTX, 0, OPTAB_WIDEN);
3448             do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3449             expand_dec (quotient, const1_rtx);
3450             expand_inc (remainder, op1);
3451             emit_label (label);
3452             return gen_lowpart (mode, rem_flag ? remainder : quotient);
3453           }
3454
3455         /* No luck with division elimination or divmod.  Have to do it
3456            by conditionally adjusting op0 *and* the result.  */
3457         {
3458           rtx label1, label2, label3, label4, label5;
3459           rtx adjusted_op0;
3460           rtx tem;
3461
3462           quotient = gen_reg_rtx (compute_mode);
3463           adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3464           label1 = gen_label_rtx ();
3465           label2 = gen_label_rtx ();
3466           label3 = gen_label_rtx ();
3467           label4 = gen_label_rtx ();
3468           label5 = gen_label_rtx ();
3469           do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3470           do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3471           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3472                               quotient, 0, OPTAB_LIB_WIDEN);
3473           if (tem != quotient)
3474             emit_move_insn (quotient, tem);
3475           emit_jump_insn (gen_jump (label5));
3476           emit_barrier ();
3477           emit_label (label1);
3478           expand_inc (adjusted_op0, const1_rtx);
3479           emit_jump_insn (gen_jump (label4));
3480           emit_barrier ();
3481           emit_label (label2);
3482           do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3483           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3484                               quotient, 0, OPTAB_LIB_WIDEN);
3485           if (tem != quotient)
3486             emit_move_insn (quotient, tem);
3487           emit_jump_insn (gen_jump (label5));
3488           emit_barrier ();
3489           emit_label (label3);
3490           expand_dec (adjusted_op0, const1_rtx);
3491           emit_label (label4);
3492           tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3493                               quotient, 0, OPTAB_LIB_WIDEN);
3494           if (tem != quotient)
3495             emit_move_insn (quotient, tem);
3496           expand_dec (quotient, const1_rtx);
3497           emit_label (label5);
3498         }
3499         break;
3500
3501       case CEIL_DIV_EXPR:
3502       case CEIL_MOD_EXPR:
3503         if (unsignedp)
3504           {
3505             if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3506               {
3507                 rtx t1, t2, t3;
3508                 unsigned HOST_WIDE_INT d = INTVAL (op1);
3509                 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3510                                    build_int_2 (floor_log2 (d), 0),
3511                                    tquotient, 1);
3512                 t2 = expand_binop (compute_mode, and_optab, op0,
3513                                    GEN_INT (d - 1),
3514                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3515                 t3 = gen_reg_rtx (compute_mode);
3516                 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3517                                       compute_mode, 1, 1);
3518                 if (t3 == 0)
3519                   {
3520                     rtx lab;
3521                     lab = gen_label_rtx ();
3522                     do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3523                     expand_inc (t1, const1_rtx);
3524                     emit_label (lab);
3525                     quotient = t1;
3526                   }
3527                 else
3528                   quotient = force_operand (gen_rtx_PLUS (compute_mode,
3529                                                           t1, t3),
3530                                             tquotient);
3531                 break;
3532               }
3533
3534             /* Try using an instruction that produces both the quotient and
3535                remainder, using truncation.  We can easily compensate the
3536                quotient or remainder to get ceiling rounding, once we have the
3537                remainder.  Notice that we compute also the final remainder
3538                value here, and return the result right away.  */
3539             if (target == 0 || GET_MODE (target) != compute_mode)
3540               target = gen_reg_rtx (compute_mode);
3541
3542             if (rem_flag)
3543               {
3544                 remainder = (GET_CODE (target) == REG
3545                              ? target : gen_reg_rtx (compute_mode));
3546                 quotient = gen_reg_rtx (compute_mode);
3547               }
3548             else
3549               {
3550                 quotient = (GET_CODE (target) == REG
3551                             ? target : gen_reg_rtx (compute_mode));
3552                 remainder = gen_reg_rtx (compute_mode);
3553               }
3554
3555             if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3556                                      remainder, 1))
3557               {
3558                 /* This could be computed with a branch-less sequence.
3559                    Save that for later.  */
3560                 rtx label = gen_label_rtx ();
3561                 do_cmp_and_jump (remainder, const0_rtx, EQ,
3562                                  compute_mode, label);
3563                 expand_inc (quotient, const1_rtx);
3564                 expand_dec (remainder, op1);
3565                 emit_label (label);
3566                 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3567               }
3568
3569             /* No luck with division elimination or divmod.  Have to do it
3570                by conditionally adjusting op0 *and* the result.  */
3571             {
3572               rtx label1, label2;
3573               rtx adjusted_op0, tem;
3574
3575               quotient = gen_reg_rtx (compute_mode);
3576               adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3577               label1 = gen_label_rtx ();
3578               label2 = gen_label_rtx ();
3579               do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3580                                compute_mode, label1);
3581               emit_move_insn  (quotient, const0_rtx);
3582               emit_jump_insn (gen_jump (label2));
3583               emit_barrier ();
3584               emit_label (label1);
3585               expand_dec (adjusted_op0, const1_rtx);
3586               tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3587                                   quotient, 1, OPTAB_LIB_WIDEN);
3588               if (tem != quotient)
3589                 emit_move_insn (quotient, tem);
3590               expand_inc (quotient, const1_rtx);
3591               emit_label (label2);
3592             }
3593           }
3594         else /* signed */
3595           {
3596             if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3597                 && INTVAL (op1) >= 0)
3598               {
3599                 /* This is extremely similar to the code for the unsigned case
3600                    above.  For 2.7 we should merge these variants, but for
3601                    2.6.1 I don't want to touch the code for unsigned since that
3602                    get used in C.  The signed case will only be used by other
3603                    languages (Ada).  */
3604
3605                 rtx t1, t2, t3;
3606                 unsigned HOST_WIDE_INT d = INTVAL (op1);
3607                 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3608                                    build_int_2 (floor_log2 (d), 0),
3609                                    tquotient, 0);
3610                 t2 = expand_binop (compute_mode, and_optab, op0,
3611                                    GEN_INT (d - 1),
3612                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3613                 t3 = gen_reg_rtx (compute_mode);
3614                 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3615                                       compute_mode, 1, 1);
3616                 if (t3 == 0)
3617                   {
3618                     rtx lab;
3619                     lab = gen_label_rtx ();
3620                     do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3621                     expand_inc (t1, const1_rtx);
3622                     emit_label (lab);
3623                     quotient = t1;
3624                   }
3625                 else
3626                   quotient = force_operand (gen_rtx_PLUS (compute_mode,
3627                                                           t1, t3),
3628                                             tquotient);
3629                 break;
3630               }
3631
3632             /* Try using an instruction that produces both the quotient and
3633                remainder, using truncation.  We can easily compensate the
3634                quotient or remainder to get ceiling rounding, once we have the
3635                remainder.  Notice that we compute also the final remainder
3636                value here, and return the result right away.  */
3637             if (target == 0 || GET_MODE (target) != compute_mode)
3638               target = gen_reg_rtx (compute_mode);
3639             if (rem_flag)
3640               {
3641                 remainder= (GET_CODE (target) == REG
3642                             ? target : gen_reg_rtx (compute_mode));
3643                 quotient = gen_reg_rtx (compute_mode);
3644               }
3645             else
3646               {
3647                 quotient = (GET_CODE (target) == REG
3648                             ? target : gen_reg_rtx (compute_mode));
3649                 remainder = gen_reg_rtx (compute_mode);
3650               }
3651
3652             if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3653                                      remainder, 0))
3654               {
3655                 /* This could be computed with a branch-less sequence.
3656                    Save that for later.  */
3657                 rtx tem;
3658                 rtx label = gen_label_rtx ();
3659                 do_cmp_and_jump (remainder, const0_rtx, EQ,
3660                                  compute_mode, label);
3661                 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3662                                     NULL_RTX, 0, OPTAB_WIDEN);
3663                 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3664                 expand_inc (quotient, const1_rtx);
3665                 expand_dec (remainder, op1);
3666                 emit_label (label);
3667                 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3668               }
3669
3670             /* No luck with division elimination or divmod.  Have to do it
3671                by conditionally adjusting op0 *and* the result.  */
3672             {
3673               rtx label1, label2, label3, label4, label5;
3674               rtx adjusted_op0;
3675               rtx tem;
3676
3677               quotient = gen_reg_rtx (compute_mode);
3678               adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3679               label1 = gen_label_rtx ();
3680               label2 = gen_label_rtx ();
3681               label3 = gen_label_rtx ();
3682               label4 = gen_label_rtx ();
3683               label5 = gen_label_rtx ();
3684               do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3685               do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3686                                compute_mode, label1);
3687               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3688                                   quotient, 0, OPTAB_LIB_WIDEN);
3689               if (tem != quotient)
3690                 emit_move_insn (quotient, tem);
3691               emit_jump_insn (gen_jump (label5));
3692               emit_barrier ();
3693               emit_label (label1);
3694               expand_dec (adjusted_op0, const1_rtx);
3695               emit_jump_insn (gen_jump (label4));
3696               emit_barrier ();
3697               emit_label (label2);
3698               do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3699                                compute_mode, label3);
3700               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3701                                   quotient, 0, OPTAB_LIB_WIDEN);
3702               if (tem != quotient)
3703                 emit_move_insn (quotient, tem);
3704               emit_jump_insn (gen_jump (label5));
3705               emit_barrier ();
3706               emit_label (label3);
3707               expand_inc (adjusted_op0, const1_rtx);
3708               emit_label (label4);
3709               tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3710                                   quotient, 0, OPTAB_LIB_WIDEN);
3711               if (tem != quotient)
3712                 emit_move_insn (quotient, tem);
3713               expand_inc (quotient, const1_rtx);
3714               emit_label (label5);
3715             }
3716           }
3717         break;
3718
3719       case EXACT_DIV_EXPR:
3720         if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3721           {
3722             HOST_WIDE_INT d = INTVAL (op1);
3723             unsigned HOST_WIDE_INT ml;
3724             int post_shift;
3725             rtx t1;
3726
3727             post_shift = floor_log2 (d & -d);
3728             ml = invert_mod2n (d >> post_shift, size);
3729             t1 = expand_mult (compute_mode, op0, GEN_INT (ml), NULL_RTX,
3730                               unsignedp);
3731             quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3732                                      build_int_2 (post_shift, 0),
3733                                      NULL_RTX, unsignedp);
3734
3735             insn = get_last_insn ();
3736             set_unique_reg_note (insn,
3737                                  REG_EQUAL,
3738                                  gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
3739                                                  compute_mode,
3740                                                  op0, op1));
3741           }
3742         break;
3743
3744       case ROUND_DIV_EXPR:
3745       case ROUND_MOD_EXPR:
3746         if (unsignedp)
3747           {
3748             rtx tem;
3749             rtx label;
3750             label = gen_label_rtx ();
3751             quotient = gen_reg_rtx (compute_mode);
3752             remainder = gen_reg_rtx (compute_mode);
3753             if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3754               {
3755                 rtx tem;
3756                 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3757                                          quotient, 1, OPTAB_LIB_WIDEN);
3758                 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3759                 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3760                                           remainder, 1, OPTAB_LIB_WIDEN);
3761               }
3762             tem = plus_constant (op1, -1);
3763             tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3764                                 build_int_2 (1, 0), NULL_RTX, 1);
3765             do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
3766             expand_inc (quotient, const1_rtx);
3767             expand_dec (remainder, op1);
3768             emit_label (label);
3769           }
3770         else
3771           {
3772             rtx abs_rem, abs_op1, tem, mask;
3773             rtx label;
3774             label = gen_label_rtx ();
3775             quotient = gen_reg_rtx (compute_mode);
3776             remainder = gen_reg_rtx (compute_mode);
3777             if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3778               {
3779                 rtx tem;
3780                 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3781                                          quotient, 0, OPTAB_LIB_WIDEN);
3782                 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3783                 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3784                                           remainder, 0, OPTAB_LIB_WIDEN);
3785               }
3786             abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 0);
3787             abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 0);
3788             tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3789                                 build_int_2 (1, 0), NULL_RTX, 1);
3790             do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
3791             tem = expand_binop (compute_mode, xor_optab, op0, op1,
3792                                 NULL_RTX, 0, OPTAB_WIDEN);
3793             mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3794                                 build_int_2 (size - 1, 0), NULL_RTX, 0);
3795             tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3796                                 NULL_RTX, 0, OPTAB_WIDEN);
3797             tem = expand_binop (compute_mode, sub_optab, tem, mask,
3798                                 NULL_RTX, 0, OPTAB_WIDEN);
3799             expand_inc (quotient, tem);
3800             tem = expand_binop (compute_mode, xor_optab, mask, op1,
3801                                 NULL_RTX, 0, OPTAB_WIDEN);
3802             tem = expand_binop (compute_mode, sub_optab, tem, mask,
3803                                 NULL_RTX, 0, OPTAB_WIDEN);
3804             expand_dec (remainder, tem);
3805             emit_label (label);
3806           }
3807         return gen_lowpart (mode, rem_flag ? remainder : quotient);
3808
3809       default:
3810         abort ();
3811       }
3812
3813   if (quotient == 0)
3814     {
3815       if (target && GET_MODE (target) != compute_mode)
3816         target = 0;
3817
3818       if (rem_flag)
3819         {
3820           /* Try to produce the remainder without producing the quotient.
3821              If we seem to have a divmod patten that does not require widening,
3822              don't try windening here.  We should really have an WIDEN argument
3823              to expand_twoval_binop, since what we'd really like to do here is
3824              1) try a mod insn in compute_mode
3825              2) try a divmod insn in compute_mode
3826              3) try a div insn in compute_mode and multiply-subtract to get
3827                 remainder
3828              4) try the same things with widening allowed.  */
3829           remainder
3830             = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3831                                  op0, op1, target,
3832                                  unsignedp,
3833                                  ((optab2->handlers[(int) compute_mode].insn_code
3834                                    != CODE_FOR_nothing)
3835                                   ? OPTAB_DIRECT : OPTAB_WIDEN));
3836           if (remainder == 0)
3837             {
3838               /* No luck there.  Can we do remainder and divide at once
3839                  without a library call?  */
3840               remainder = gen_reg_rtx (compute_mode);
3841               if (! expand_twoval_binop ((unsignedp
3842                                           ? udivmod_optab
3843                                           : sdivmod_optab),
3844                                          op0, op1,
3845                                          NULL_RTX, remainder, unsignedp))
3846                 remainder = 0;
3847             }
3848
3849           if (remainder)
3850             return gen_lowpart (mode, remainder);
3851         }
3852
3853       /* Produce the quotient.  Try a quotient insn, but not a library call.
3854          If we have a divmod in this mode, use it in preference to widening
3855          the div (for this test we assume it will not fail). Note that optab2
3856          is set to the one of the two optabs that the call below will use.  */
3857       quotient
3858         = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
3859                              op0, op1, rem_flag ? NULL_RTX : target,
3860                              unsignedp,
3861                              ((optab2->handlers[(int) compute_mode].insn_code
3862                                != CODE_FOR_nothing)
3863                               ? OPTAB_DIRECT : OPTAB_WIDEN));
3864
3865       if (quotient == 0)
3866         {
3867           /* No luck there.  Try a quotient-and-remainder insn,
3868              keeping the quotient alone.  */
3869           quotient = gen_reg_rtx (compute_mode);
3870           if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
3871                                      op0, op1,
3872                                      quotient, NULL_RTX, unsignedp))
3873             {
3874               quotient = 0;
3875               if (! rem_flag)
3876                 /* Still no luck.  If we are not computing the remainder,
3877                    use a library call for the quotient.  */
3878                 quotient = sign_expand_binop (compute_mode,
3879                                               udiv_optab, sdiv_optab,
3880                                               op0, op1, target,
3881                                               unsignedp, OPTAB_LIB_WIDEN);
3882             }
3883         }
3884     }
3885
3886   if (rem_flag)
3887     {
3888       if (target && GET_MODE (target) != compute_mode)
3889         target = 0;
3890
3891       if (quotient == 0)
3892         /* No divide instruction either.  Use library for remainder.  */
3893         remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3894                                        op0, op1, target,
3895                                        unsignedp, OPTAB_LIB_WIDEN);
3896       else
3897         {
3898           /* We divided.  Now finish doing X - Y * (X / Y).  */
3899           remainder = expand_mult (compute_mode, quotient, op1,
3900                                    NULL_RTX, unsignedp);
3901           remainder = expand_binop (compute_mode, sub_optab, op0,
3902                                     remainder, target, unsignedp,
3903                                     OPTAB_LIB_WIDEN);
3904         }
3905     }
3906
3907   return gen_lowpart (mode, rem_flag ? remainder : quotient);
3908 }
3909 \f
3910 /* Return a tree node with data type TYPE, describing the value of X.
3911    Usually this is an RTL_EXPR, if there is no obvious better choice.
3912    X may be an expression, however we only support those expressions
3913    generated by loop.c.   */
3914
3915 tree
3916 make_tree (type, x)
3917      tree type;
3918      rtx x;
3919 {
3920   tree t;
3921
3922   switch (GET_CODE (x))
3923     {
3924     case CONST_INT:
3925       t = build_int_2 (INTVAL (x),
3926                        (TREE_UNSIGNED (type)
3927                         && (GET_MODE_BITSIZE (TYPE_MODE (type)) < HOST_BITS_PER_WIDE_INT))
3928                        || INTVAL (x) >= 0 ? 0 : -1);
3929       TREE_TYPE (t) = type;
3930       return t;
3931
3932     case CONST_DOUBLE:
3933       if (GET_MODE (x) == VOIDmode)
3934         {
3935           t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
3936           TREE_TYPE (t) = type;
3937         }
3938       else
3939         {
3940           REAL_VALUE_TYPE d;
3941
3942           REAL_VALUE_FROM_CONST_DOUBLE (d, x);
3943           t = build_real (type, d);
3944         }
3945
3946       return t;
3947
3948     case PLUS:
3949       return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
3950                           make_tree (type, XEXP (x, 1))));
3951
3952     case MINUS:
3953       return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
3954                           make_tree (type, XEXP (x, 1))));
3955
3956     case NEG:
3957       return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
3958
3959     case MULT:
3960       return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
3961                           make_tree (type, XEXP (x, 1))));
3962
3963     case ASHIFT:
3964       return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
3965                           make_tree (type, XEXP (x, 1))));
3966
3967     case LSHIFTRT:
3968       return fold (convert (type,
3969                             build (RSHIFT_EXPR, unsigned_type (type),
3970                                    make_tree (unsigned_type (type),
3971                                               XEXP (x, 0)),
3972                                    make_tree (type, XEXP (x, 1)))));
3973
3974     case ASHIFTRT:
3975       return fold (convert (type,
3976                             build (RSHIFT_EXPR, signed_type (type),
3977                                    make_tree (signed_type (type), XEXP (x, 0)),
3978                                    make_tree (type, XEXP (x, 1)))));
3979
3980     case DIV:
3981       if (TREE_CODE (type) != REAL_TYPE)
3982         t = signed_type (type);
3983       else
3984         t = type;
3985
3986       return fold (convert (type,
3987                             build (TRUNC_DIV_EXPR, t,
3988                                    make_tree (t, XEXP (x, 0)),
3989                                    make_tree (t, XEXP (x, 1)))));
3990     case UDIV:
3991       t = unsigned_type (type);
3992       return fold (convert (type,
3993                             build (TRUNC_DIV_EXPR, t,
3994                                    make_tree (t, XEXP (x, 0)),
3995                                    make_tree (t, XEXP (x, 1)))));
3996    default:
3997       t = make_node (RTL_EXPR);
3998       TREE_TYPE (t) = type;
3999       RTL_EXPR_RTL (t) = x;
4000       /* There are no insns to be output
4001          when this rtl_expr is used.  */
4002       RTL_EXPR_SEQUENCE (t) = 0;
4003       return t;
4004     }
4005 }
4006
4007 /* Return an rtx representing the value of X * MULT + ADD.
4008    TARGET is a suggestion for where to store the result (an rtx).
4009    MODE is the machine mode for the computation.
4010    X and MULT must have mode MODE.  ADD may have a different mode.
4011    So can X (defaults to same as MODE).
4012    UNSIGNEDP is non-zero to do unsigned multiplication.
4013    This may emit insns.  */
4014
4015 rtx
4016 expand_mult_add (x, target, mult, add, mode, unsignedp)
4017      rtx x, target, mult, add;
4018      enum machine_mode mode;
4019      int unsignedp;
4020 {
4021   tree type = type_for_mode (mode, unsignedp);
4022   tree add_type = (GET_MODE (add) == VOIDmode
4023                    ? type : type_for_mode (GET_MODE (add), unsignedp));
4024   tree result =  fold (build (PLUS_EXPR, type,
4025                               fold (build (MULT_EXPR, type,
4026                                            make_tree (type, x),
4027                                            make_tree (type, mult))),
4028                               make_tree (add_type, add)));
4029
4030   return expand_expr (result, target, VOIDmode, 0);
4031 }
4032 \f
4033 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4034    and returning TARGET.
4035
4036    If TARGET is 0, a pseudo-register or constant is returned.  */
4037
4038 rtx
4039 expand_and (op0, op1, target)
4040      rtx op0, op1, target;
4041 {
4042   enum machine_mode mode = VOIDmode;
4043   rtx tem;
4044
4045   if (GET_MODE (op0) != VOIDmode)
4046     mode = GET_MODE (op0);
4047   else if (GET_MODE (op1) != VOIDmode)
4048     mode = GET_MODE (op1);
4049
4050   if (mode != VOIDmode)
4051     tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4052   else if (GET_CODE (op0) == CONST_INT && GET_CODE (op1) == CONST_INT)
4053     tem = GEN_INT (INTVAL (op0) & INTVAL (op1));
4054   else
4055     abort ();
4056
4057   if (target == 0)
4058     target = tem;
4059   else if (tem != target)
4060     emit_move_insn (target, tem);
4061   return target;
4062 }
4063 \f
4064 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4065    and storing in TARGET.  Normally return TARGET.
4066    Return 0 if that cannot be done.
4067
4068    MODE is the mode to use for OP0 and OP1 should they be CONST_INTs.  If
4069    it is VOIDmode, they cannot both be CONST_INT.
4070
4071    UNSIGNEDP is for the case where we have to widen the operands
4072    to perform the operation.  It says to use zero-extension.
4073
4074    NORMALIZEP is 1 if we should convert the result to be either zero
4075    or one.  Normalize is -1 if we should convert the result to be
4076    either zero or -1.  If NORMALIZEP is zero, the result will be left
4077    "raw" out of the scc insn.  */
4078
4079 rtx
4080 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
4081      rtx target;
4082      enum rtx_code code;
4083      rtx op0, op1;
4084      enum machine_mode mode;
4085      int unsignedp;
4086      int normalizep;
4087 {
4088   rtx subtarget;
4089   enum insn_code icode;
4090   enum machine_mode compare_mode;
4091   enum machine_mode target_mode = GET_MODE (target);
4092   rtx tem;
4093   rtx last = get_last_insn ();
4094   rtx pattern, comparison;
4095
4096   /* If one operand is constant, make it the second one.  Only do this
4097      if the other operand is not constant as well.  */
4098
4099   if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
4100       || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
4101     {
4102       tem = op0;
4103       op0 = op1;
4104       op1 = tem;
4105       code = swap_condition (code);
4106     }
4107
4108   if (mode == VOIDmode)
4109     mode = GET_MODE (op0);
4110
4111   /* For some comparisons with 1 and -1, we can convert this to
4112      comparisons with zero.  This will often produce more opportunities for
4113      store-flag insns.  */
4114
4115   switch (code)
4116     {
4117     case LT:
4118       if (op1 == const1_rtx)
4119         op1 = const0_rtx, code = LE;
4120       break;
4121     case LE:
4122       if (op1 == constm1_rtx)
4123         op1 = const0_rtx, code = LT;
4124       break;
4125     case GE:
4126       if (op1 == const1_rtx)
4127         op1 = const0_rtx, code = GT;
4128       break;
4129     case GT:
4130       if (op1 == constm1_rtx)
4131         op1 = const0_rtx, code = GE;
4132       break;
4133     case GEU:
4134       if (op1 == const1_rtx)
4135         op1 = const0_rtx, code = NE;
4136       break;
4137     case LTU:
4138       if (op1 == const1_rtx)
4139         op1 = const0_rtx, code = EQ;
4140       break;
4141     default:
4142       break;
4143     }
4144
4145   /* From now on, we won't change CODE, so set ICODE now.  */
4146   icode = setcc_gen_code[(int) code];
4147
4148   /* If this is A < 0 or A >= 0, we can do this by taking the ones
4149      complement of A (for GE) and shifting the sign bit to the low bit.  */
4150   if (op1 == const0_rtx && (code == LT || code == GE)
4151       && GET_MODE_CLASS (mode) == MODE_INT
4152       && (normalizep || STORE_FLAG_VALUE == 1
4153           || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4154               && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4155                   == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4156     {
4157       subtarget = target;
4158
4159       /* If the result is to be wider than OP0, it is best to convert it
4160          first.  If it is to be narrower, it is *incorrect* to convert it
4161          first.  */
4162       if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4163         {
4164           op0 = protect_from_queue (op0, 0);
4165           op0 = convert_modes (target_mode, mode, op0, 0);
4166           mode = target_mode;
4167         }
4168
4169       if (target_mode != mode)
4170         subtarget = 0;
4171
4172       if (code == GE)
4173         op0 = expand_unop (mode, one_cmpl_optab, op0,
4174                            ((STORE_FLAG_VALUE == 1 || normalizep)
4175                             ? 0 : subtarget), 0);
4176
4177       if (STORE_FLAG_VALUE == 1 || normalizep)
4178         /* If we are supposed to produce a 0/1 value, we want to do
4179            a logical shift from the sign bit to the low-order bit; for
4180            a -1/0 value, we do an arithmetic shift.  */
4181         op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4182                             size_int (GET_MODE_BITSIZE (mode) - 1),
4183                             subtarget, normalizep != -1);
4184
4185       if (mode != target_mode)
4186         op0 = convert_modes (target_mode, mode, op0, 0);
4187
4188       return op0;
4189     }
4190
4191   if (icode != CODE_FOR_nothing)
4192     {
4193       /* We think we may be able to do this with a scc insn.  Emit the
4194          comparison and then the scc insn.
4195
4196          compare_from_rtx may call emit_queue, which would be deleted below
4197          if the scc insn fails.  So call it ourselves before setting LAST.  */
4198
4199       emit_queue ();
4200       last = get_last_insn ();
4201
4202       comparison
4203         = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX, 0);
4204       if (GET_CODE (comparison) == CONST_INT)
4205         return (comparison == const0_rtx ? const0_rtx
4206                 : normalizep == 1 ? const1_rtx
4207                 : normalizep == -1 ? constm1_rtx
4208                 : const_true_rtx);
4209
4210       /* If the code of COMPARISON doesn't match CODE, something is
4211          wrong; we can no longer be sure that we have the operation.
4212          We could handle this case, but it should not happen.  */
4213
4214       if (GET_CODE (comparison) != code)
4215         abort ();
4216
4217       /* Get a reference to the target in the proper mode for this insn.  */
4218       compare_mode = insn_operand_mode[(int) icode][0];
4219       subtarget = target;
4220       if (preserve_subexpressions_p ()
4221           || ! (*insn_operand_predicate[(int) icode][0]) (subtarget, compare_mode))
4222         subtarget = gen_reg_rtx (compare_mode);
4223
4224       pattern = GEN_FCN (icode) (subtarget);
4225       if (pattern)
4226         {
4227           emit_insn (pattern);
4228
4229           /* If we are converting to a wider mode, first convert to
4230              TARGET_MODE, then normalize.  This produces better combining
4231              opportunities on machines that have a SIGN_EXTRACT when we are
4232              testing a single bit.  This mostly benefits the 68k.
4233
4234              If STORE_FLAG_VALUE does not have the sign bit set when
4235              interpreted in COMPARE_MODE, we can do this conversion as
4236              unsigned, which is usually more efficient.  */
4237           if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4238             {
4239               convert_move (target, subtarget,
4240                             (GET_MODE_BITSIZE (compare_mode)
4241                              <= HOST_BITS_PER_WIDE_INT)
4242                             && 0 == (STORE_FLAG_VALUE
4243                                      & ((HOST_WIDE_INT) 1
4244                                         << (GET_MODE_BITSIZE (compare_mode) -1))));
4245               op0 = target;
4246               compare_mode = target_mode;
4247             }
4248           else
4249             op0 = subtarget;
4250
4251           /* If we want to keep subexpressions around, don't reuse our
4252              last target.  */
4253
4254           if (preserve_subexpressions_p ())
4255             subtarget = 0;
4256
4257           /* Now normalize to the proper value in COMPARE_MODE.  Sometimes
4258              we don't have to do anything.  */
4259           if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4260             ;
4261           else if (normalizep == - STORE_FLAG_VALUE)
4262             op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4263
4264           /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4265              makes it hard to use a value of just the sign bit due to
4266              ANSI integer constant typing rules.  */
4267           else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4268                    && (STORE_FLAG_VALUE
4269                        & ((HOST_WIDE_INT) 1
4270                           << (GET_MODE_BITSIZE (compare_mode) - 1))))
4271             op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4272                                 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4273                                 subtarget, normalizep == 1);
4274           else if (STORE_FLAG_VALUE & 1)
4275             {
4276               op0 = expand_and (op0, const1_rtx, subtarget);
4277               if (normalizep == -1)
4278                 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4279             }
4280           else
4281             abort ();
4282
4283           /* If we were converting to a smaller mode, do the
4284              conversion now.  */
4285           if (target_mode != compare_mode)
4286             {
4287               convert_move (target, op0, 0);
4288               return target;
4289             }
4290           else
4291             return op0;
4292         }
4293     }
4294
4295   delete_insns_since (last);
4296
4297   /* If expensive optimizations, use different pseudo registers for each
4298      insn, instead of reusing the same pseudo.  This leads to better CSE,
4299      but slows down the compiler, since there are more pseudos */
4300   subtarget = (!flag_expensive_optimizations
4301                && (target_mode == mode)) ? target : NULL_RTX;
4302
4303   /* If we reached here, we can't do this with a scc insn.  However, there
4304      are some comparisons that can be done directly.  For example, if
4305      this is an equality comparison of integers, we can try to exclusive-or
4306      (or subtract) the two operands and use a recursive call to try the
4307      comparison with zero.  Don't do any of these cases if branches are
4308      very cheap.  */
4309
4310   if (BRANCH_COST > 0
4311       && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4312       && op1 != const0_rtx)
4313     {
4314       tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4315                           OPTAB_WIDEN);
4316
4317       if (tem == 0)
4318         tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4319                             OPTAB_WIDEN);
4320       if (tem != 0)
4321         tem = emit_store_flag (target, code, tem, const0_rtx,
4322                                mode, unsignedp, normalizep);
4323       if (tem == 0)
4324         delete_insns_since (last);
4325       return tem;
4326     }
4327
4328   /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4329      the constant zero.  Reject all other comparisons at this point.  Only
4330      do LE and GT if branches are expensive since they are expensive on
4331      2-operand machines.  */
4332
4333   if (BRANCH_COST == 0
4334       || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4335       || (code != EQ && code != NE
4336           && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4337     return 0;
4338
4339   /* See what we need to return.  We can only return a 1, -1, or the
4340      sign bit.  */
4341
4342   if (normalizep == 0)
4343     {
4344       if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4345         normalizep = STORE_FLAG_VALUE;
4346
4347       else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4348                && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4349                    == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4350         ;
4351       else
4352         return 0;
4353     }
4354
4355   /* Try to put the result of the comparison in the sign bit.  Assume we can't
4356      do the necessary operation below.  */
4357
4358   tem = 0;
4359
4360   /* To see if A <= 0, compute (A | (A - 1)).  A <= 0 iff that result has
4361      the sign bit set.  */
4362
4363   if (code == LE)
4364     {
4365       /* This is destructive, so SUBTARGET can't be OP0.  */
4366       if (rtx_equal_p (subtarget, op0))
4367         subtarget = 0;
4368
4369       tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4370                           OPTAB_WIDEN);
4371       if (tem)
4372         tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4373                             OPTAB_WIDEN);
4374     }
4375
4376   /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4377      number of bits in the mode of OP0, minus one.  */
4378
4379   if (code == GT)
4380     {
4381       if (rtx_equal_p (subtarget, op0))
4382         subtarget = 0;
4383
4384       tem = expand_shift (RSHIFT_EXPR, mode, op0,
4385                           size_int (GET_MODE_BITSIZE (mode) - 1),
4386                           subtarget, 0);
4387       tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4388                           OPTAB_WIDEN);
4389     }
4390
4391   if (code == EQ || code == NE)
4392     {
4393       /* For EQ or NE, one way to do the comparison is to apply an operation
4394          that converts the operand into a positive number if it is non-zero
4395          or zero if it was originally zero.  Then, for EQ, we subtract 1 and
4396          for NE we negate.  This puts the result in the sign bit.  Then we
4397          normalize with a shift, if needed.
4398
4399          Two operations that can do the above actions are ABS and FFS, so try
4400          them.  If that doesn't work, and MODE is smaller than a full word,
4401          we can use zero-extension to the wider mode (an unsigned conversion)
4402          as the operation.  */
4403
4404       if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4405         tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4406       else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4407         tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4408       else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4409         {
4410           op0 = protect_from_queue (op0, 0);
4411           tem = convert_modes (word_mode, mode, op0, 1);
4412           mode = word_mode;
4413         }
4414
4415       if (tem != 0)
4416         {
4417           if (code == EQ)
4418             tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4419                                 0, OPTAB_WIDEN);
4420           else
4421             tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4422         }
4423
4424       /* If we couldn't do it that way, for NE we can "or" the two's complement
4425          of the value with itself.  For EQ, we take the one's complement of
4426          that "or", which is an extra insn, so we only handle EQ if branches
4427          are expensive.  */
4428
4429       if (tem == 0 && (code == NE || BRANCH_COST > 1))
4430         {
4431           if (rtx_equal_p (subtarget, op0))
4432             subtarget = 0;
4433
4434           tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4435           tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4436                               OPTAB_WIDEN);
4437
4438           if (tem && code == EQ)
4439             tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4440         }
4441     }
4442
4443   if (tem && normalizep)
4444     tem = expand_shift (RSHIFT_EXPR, mode, tem,
4445                         size_int (GET_MODE_BITSIZE (mode) - 1),
4446                         subtarget, normalizep == 1);
4447
4448   if (tem)
4449     {
4450       if (GET_MODE (tem) != target_mode)
4451         {
4452           convert_move (target, tem, 0);
4453           tem = target;
4454         }
4455       else if (!subtarget)
4456         {
4457           emit_move_insn (target, tem);
4458           tem = target;
4459         }
4460     }
4461   else
4462     delete_insns_since (last);
4463
4464   return tem;
4465 }
4466
4467 /* Like emit_store_flag, but always succeeds.  */
4468
4469 rtx
4470 emit_store_flag_force (target, code, op0, op1, mode, unsignedp, normalizep)
4471      rtx target;
4472      enum rtx_code code;
4473      rtx op0, op1;
4474      enum machine_mode mode;
4475      int unsignedp;
4476      int normalizep;
4477 {
4478   rtx tem, label;
4479
4480   /* First see if emit_store_flag can do the job.  */
4481   tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4482   if (tem != 0)
4483     return tem;
4484
4485   if (normalizep == 0)
4486     normalizep = 1;
4487
4488   /* If this failed, we have to do this with set/compare/jump/set code.  */
4489
4490   if (GET_CODE (target) != REG
4491       || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4492     target = gen_reg_rtx (GET_MODE (target));
4493
4494   emit_move_insn (target, const1_rtx);
4495   tem = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX, 0);
4496   if (GET_CODE (tem) == CONST_INT)
4497     return tem;
4498
4499   label = gen_label_rtx ();
4500   if (bcc_gen_fctn[(int) code] == 0)
4501     abort ();
4502
4503   emit_jump_insn ((*bcc_gen_fctn[(int) code]) (label));
4504   emit_move_insn (target, const0_rtx);
4505   emit_label (label);
4506
4507   return target;
4508 }
4509 \f
4510 /* Perform possibly multi-word comparison and conditional jump to LABEL
4511    if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4512
4513    The algorithm is based on the code in expr.c:do_jump.
4514
4515    Note that this does not perform a general comparison.  Only variants
4516    generated within expmed.c are correctly handled, others abort (but could
4517    be handled if needed).  */
4518
4519 static void
4520 do_cmp_and_jump (arg1, arg2, op, mode, label)
4521      rtx arg1, arg2, label;
4522     enum rtx_code op;
4523     enum machine_mode mode;
4524 {
4525   /* If this mode is an integer too wide to compare properly,
4526      compare word by word.  Rely on cse to optimize constant cases.  */
4527
4528   if (GET_MODE_CLASS (mode) == MODE_INT && !can_compare_p (mode))
4529     {
4530       rtx label2 = gen_label_rtx ();
4531
4532       switch (op)
4533         {
4534         case LTU:
4535           do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4536           break;
4537
4538         case LEU:
4539           do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4540           break;
4541
4542         case LT:
4543           do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4544           break;
4545
4546         case GT:
4547           do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4548           break;
4549
4550         case GE:
4551           do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4552           break;
4553
4554           /* do_jump_by_parts_equality_rtx compares with zero.  Luckily
4555              that's the only equality operations we do */
4556         case EQ:
4557           if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4558             abort();
4559           do_jump_by_parts_equality_rtx (arg1, label2, label);
4560           break;
4561
4562         case NE:
4563           if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4564             abort();
4565           do_jump_by_parts_equality_rtx (arg1, label, label2);
4566           break;
4567
4568         default:
4569           abort();
4570         }
4571
4572       emit_label (label2);
4573     }
4574   else
4575     {
4576       emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, 0, label);
4577     }
4578 }