home *** CD-ROM | disk | FTP | other *** search
/ Education Sampler 1992 [NeXTSTEP] / Education_1992_Sampler.iso / NeXT / GnuSource / cc-61.0.1 / cc / expmed.c < prev    next >
C/C++ Source or Header  |  1991-12-19  |  85KB  |  2,694 lines

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