OSDN Git Service

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