OSDN Git Service

56c0d24bd66fee2bef217c9ee512b447659ef9ad
[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, 2001, 2002, 2003, 2004, 2005, 2006
5    Free Software Foundation, Inc.
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 02110-1301, USA.  */
23
24
25 #include "config.h"
26 #include "system.h"
27 #include "coretypes.h"
28 #include "tm.h"
29 #include "toplev.h"
30 #include "rtl.h"
31 #include "tree.h"
32 #include "tm_p.h"
33 #include "flags.h"
34 #include "insn-config.h"
35 #include "expr.h"
36 #include "optabs.h"
37 #include "real.h"
38 #include "recog.h"
39 #include "langhooks.h"
40
41 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
42                                    unsigned HOST_WIDE_INT,
43                                    unsigned HOST_WIDE_INT, rtx);
44 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
45                                    unsigned HOST_WIDE_INT, rtx);
46 static rtx extract_fixed_bit_field (enum machine_mode, rtx,
47                                     unsigned HOST_WIDE_INT,
48                                     unsigned HOST_WIDE_INT,
49                                     unsigned HOST_WIDE_INT, rtx, int);
50 static rtx mask_rtx (enum machine_mode, int, int, int);
51 static rtx lshift_value (enum machine_mode, rtx, int, int);
52 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
53                                     unsigned HOST_WIDE_INT, int);
54 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx);
55 static rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
56 static rtx expand_sdiv_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
57
58 /* Test whether a value is zero of a power of two.  */
59 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
60
61 /* Nonzero means divides or modulus operations are relatively cheap for
62    powers of two, so don't use branches; emit the operation instead.
63    Usually, this will mean that the MD file will emit non-branch
64    sequences.  */
65
66 static bool sdiv_pow2_cheap[NUM_MACHINE_MODES];
67 static bool smod_pow2_cheap[NUM_MACHINE_MODES];
68
69 #ifndef SLOW_UNALIGNED_ACCESS
70 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
71 #endif
72
73 /* For compilers that support multiple targets with different word sizes,
74    MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD.  An example
75    is the H8/300(H) compiler.  */
76
77 #ifndef MAX_BITS_PER_WORD
78 #define MAX_BITS_PER_WORD BITS_PER_WORD
79 #endif
80
81 /* Reduce conditional compilation elsewhere.  */
82 #ifndef HAVE_insv
83 #define HAVE_insv       0
84 #define CODE_FOR_insv   CODE_FOR_nothing
85 #define gen_insv(a,b,c,d) NULL_RTX
86 #endif
87 #ifndef HAVE_extv
88 #define HAVE_extv       0
89 #define CODE_FOR_extv   CODE_FOR_nothing
90 #define gen_extv(a,b,c,d) NULL_RTX
91 #endif
92 #ifndef HAVE_extzv
93 #define HAVE_extzv      0
94 #define CODE_FOR_extzv  CODE_FOR_nothing
95 #define gen_extzv(a,b,c,d) NULL_RTX
96 #endif
97
98 /* Cost of various pieces of RTL.  Note that some of these are indexed by
99    shift count and some by mode.  */
100 static int zero_cost;
101 static int add_cost[NUM_MACHINE_MODES];
102 static int neg_cost[NUM_MACHINE_MODES];
103 static int shift_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
104 static int shiftadd_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
105 static int shiftsub_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
106 static int mul_cost[NUM_MACHINE_MODES];
107 static int sdiv_cost[NUM_MACHINE_MODES];
108 static int udiv_cost[NUM_MACHINE_MODES];
109 static int mul_widen_cost[NUM_MACHINE_MODES];
110 static int mul_highpart_cost[NUM_MACHINE_MODES];
111
112 void
113 init_expmed (void)
114 {
115   struct
116   {
117     struct rtx_def reg;         rtunion reg_fld[2];
118     struct rtx_def plus;        rtunion plus_fld1;
119     struct rtx_def neg;
120     struct rtx_def mult;        rtunion mult_fld1;
121     struct rtx_def sdiv;        rtunion sdiv_fld1;
122     struct rtx_def udiv;        rtunion udiv_fld1;
123     struct rtx_def zext;
124     struct rtx_def sdiv_32;     rtunion sdiv_32_fld1;
125     struct rtx_def smod_32;     rtunion smod_32_fld1;
126     struct rtx_def wide_mult;   rtunion wide_mult_fld1;
127     struct rtx_def wide_lshr;   rtunion wide_lshr_fld1;
128     struct rtx_def wide_trunc;
129     struct rtx_def shift;       rtunion shift_fld1;
130     struct rtx_def shift_mult;  rtunion shift_mult_fld1;
131     struct rtx_def shift_add;   rtunion shift_add_fld1;
132     struct rtx_def shift_sub;   rtunion shift_sub_fld1;
133   } all;
134
135   rtx pow2[MAX_BITS_PER_WORD];
136   rtx cint[MAX_BITS_PER_WORD];
137   int m, n;
138   enum machine_mode mode, wider_mode;
139
140   zero_cost = rtx_cost (const0_rtx, 0);
141
142   for (m = 1; m < MAX_BITS_PER_WORD; m++)
143     {
144       pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
145       cint[m] = GEN_INT (m);
146     }
147
148   memset (&all, 0, sizeof all);
149
150   PUT_CODE (&all.reg, REG);
151   /* Avoid using hard regs in ways which may be unsupported.  */
152   REGNO (&all.reg) = LAST_VIRTUAL_REGISTER + 1;
153
154   PUT_CODE (&all.plus, PLUS);
155   XEXP (&all.plus, 0) = &all.reg;
156   XEXP (&all.plus, 1) = &all.reg;
157
158   PUT_CODE (&all.neg, NEG);
159   XEXP (&all.neg, 0) = &all.reg;
160
161   PUT_CODE (&all.mult, MULT);
162   XEXP (&all.mult, 0) = &all.reg;
163   XEXP (&all.mult, 1) = &all.reg;
164
165   PUT_CODE (&all.sdiv, DIV);
166   XEXP (&all.sdiv, 0) = &all.reg;
167   XEXP (&all.sdiv, 1) = &all.reg;
168
169   PUT_CODE (&all.udiv, UDIV);
170   XEXP (&all.udiv, 0) = &all.reg;
171   XEXP (&all.udiv, 1) = &all.reg;
172
173   PUT_CODE (&all.sdiv_32, DIV);
174   XEXP (&all.sdiv_32, 0) = &all.reg;
175   XEXP (&all.sdiv_32, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32);
176
177   PUT_CODE (&all.smod_32, MOD);
178   XEXP (&all.smod_32, 0) = &all.reg;
179   XEXP (&all.smod_32, 1) = XEXP (&all.sdiv_32, 1);
180
181   PUT_CODE (&all.zext, ZERO_EXTEND);
182   XEXP (&all.zext, 0) = &all.reg;
183
184   PUT_CODE (&all.wide_mult, MULT);
185   XEXP (&all.wide_mult, 0) = &all.zext;
186   XEXP (&all.wide_mult, 1) = &all.zext;
187
188   PUT_CODE (&all.wide_lshr, LSHIFTRT);
189   XEXP (&all.wide_lshr, 0) = &all.wide_mult;
190
191   PUT_CODE (&all.wide_trunc, TRUNCATE);
192   XEXP (&all.wide_trunc, 0) = &all.wide_lshr;
193
194   PUT_CODE (&all.shift, ASHIFT);
195   XEXP (&all.shift, 0) = &all.reg;
196
197   PUT_CODE (&all.shift_mult, MULT);
198   XEXP (&all.shift_mult, 0) = &all.reg;
199
200   PUT_CODE (&all.shift_add, PLUS);
201   XEXP (&all.shift_add, 0) = &all.shift_mult;
202   XEXP (&all.shift_add, 1) = &all.reg;
203
204   PUT_CODE (&all.shift_sub, MINUS);
205   XEXP (&all.shift_sub, 0) = &all.shift_mult;
206   XEXP (&all.shift_sub, 1) = &all.reg;
207
208   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
209        mode != VOIDmode;
210        mode = GET_MODE_WIDER_MODE (mode))
211     {
212       PUT_MODE (&all.reg, mode);
213       PUT_MODE (&all.plus, mode);
214       PUT_MODE (&all.neg, mode);
215       PUT_MODE (&all.mult, mode);
216       PUT_MODE (&all.sdiv, mode);
217       PUT_MODE (&all.udiv, mode);
218       PUT_MODE (&all.sdiv_32, mode);
219       PUT_MODE (&all.smod_32, mode);
220       PUT_MODE (&all.wide_trunc, mode);
221       PUT_MODE (&all.shift, mode);
222       PUT_MODE (&all.shift_mult, mode);
223       PUT_MODE (&all.shift_add, mode);
224       PUT_MODE (&all.shift_sub, mode);
225
226       add_cost[mode] = rtx_cost (&all.plus, SET);
227       neg_cost[mode] = rtx_cost (&all.neg, SET);
228       mul_cost[mode] = rtx_cost (&all.mult, SET);
229       sdiv_cost[mode] = rtx_cost (&all.sdiv, SET);
230       udiv_cost[mode] = rtx_cost (&all.udiv, SET);
231
232       sdiv_pow2_cheap[mode] = (rtx_cost (&all.sdiv_32, SET)
233                                <= 2 * add_cost[mode]);
234       smod_pow2_cheap[mode] = (rtx_cost (&all.smod_32, SET)
235                                <= 4 * add_cost[mode]);
236
237       wider_mode = GET_MODE_WIDER_MODE (mode);
238       if (wider_mode != VOIDmode)
239         {
240           PUT_MODE (&all.zext, wider_mode);
241           PUT_MODE (&all.wide_mult, wider_mode);
242           PUT_MODE (&all.wide_lshr, wider_mode);
243           XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode));
244
245           mul_widen_cost[wider_mode] = rtx_cost (&all.wide_mult, SET);
246           mul_highpart_cost[mode] = rtx_cost (&all.wide_trunc, SET);
247         }
248
249       shift_cost[mode][0] = 0;
250       shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode];
251
252       n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode));
253       for (m = 1; m < n; m++)
254         {
255           XEXP (&all.shift, 1) = cint[m];
256           XEXP (&all.shift_mult, 1) = pow2[m];
257
258           shift_cost[mode][m] = rtx_cost (&all.shift, SET);
259           shiftadd_cost[mode][m] = rtx_cost (&all.shift_add, SET);
260           shiftsub_cost[mode][m] = rtx_cost (&all.shift_sub, SET);
261         }
262     }
263 }
264
265 /* Return an rtx representing minus the value of X.
266    MODE is the intended mode of the result,
267    useful if X is a CONST_INT.  */
268
269 rtx
270 negate_rtx (enum machine_mode mode, rtx x)
271 {
272   rtx result = simplify_unary_operation (NEG, mode, x, mode);
273
274   if (result == 0)
275     result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
276
277   return result;
278 }
279
280 /* Report on the availability of insv/extv/extzv and the desired mode
281    of each of their operands.  Returns MAX_MACHINE_MODE if HAVE_foo
282    is false; else the mode of the specified operand.  If OPNO is -1,
283    all the caller cares about is whether the insn is available.  */
284 enum machine_mode
285 mode_for_extraction (enum extraction_pattern pattern, int opno)
286 {
287   const struct insn_data *data;
288
289   switch (pattern)
290     {
291     case EP_insv:
292       if (HAVE_insv)
293         {
294           data = &insn_data[CODE_FOR_insv];
295           break;
296         }
297       return MAX_MACHINE_MODE;
298
299     case EP_extv:
300       if (HAVE_extv)
301         {
302           data = &insn_data[CODE_FOR_extv];
303           break;
304         }
305       return MAX_MACHINE_MODE;
306
307     case EP_extzv:
308       if (HAVE_extzv)
309         {
310           data = &insn_data[CODE_FOR_extzv];
311           break;
312         }
313       return MAX_MACHINE_MODE;
314
315     default:
316       gcc_unreachable ();
317     }
318
319   if (opno == -1)
320     return VOIDmode;
321
322   /* Everyone who uses this function used to follow it with
323      if (result == VOIDmode) result = word_mode; */
324   if (data->operand[opno].mode == VOIDmode)
325     return word_mode;
326   return data->operand[opno].mode;
327 }
328
329 \f
330 /* Generate code to store value from rtx VALUE
331    into a bit-field within structure STR_RTX
332    containing BITSIZE bits starting at bit BITNUM.
333    FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
334    ALIGN is the alignment that STR_RTX is known to have.
335    TOTAL_SIZE is the size of the structure in bytes, or -1 if varying.  */
336
337 /* ??? Note that there are two different ideas here for how
338    to determine the size to count bits within, for a register.
339    One is BITS_PER_WORD, and the other is the size of operand 3
340    of the insv pattern.
341
342    If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
343    else, we use the mode of operand 3.  */
344
345 rtx
346 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
347                  unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode,
348                  rtx value)
349 {
350   unsigned int unit
351     = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
352   unsigned HOST_WIDE_INT offset, bitpos;
353   rtx op0 = str_rtx;
354   int byte_offset;
355   rtx orig_value;
356
357   enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
358
359   while (GET_CODE (op0) == SUBREG)
360     {
361       /* The following line once was done only if WORDS_BIG_ENDIAN,
362          but I think that is a mistake.  WORDS_BIG_ENDIAN is
363          meaningful at a much higher level; when structures are copied
364          between memory and regs, the higher-numbered regs
365          always get higher addresses.  */
366       int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)));
367       int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0));
368       
369       byte_offset = 0;
370
371       /* Paradoxical subregs need special handling on big endian machines.  */
372       if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size)
373         {
374           int difference = inner_mode_size - outer_mode_size;
375
376           if (WORDS_BIG_ENDIAN)
377             byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
378           if (BYTES_BIG_ENDIAN)
379             byte_offset += difference % UNITS_PER_WORD;
380         }
381       else
382         byte_offset = SUBREG_BYTE (op0);
383
384       bitnum += byte_offset * BITS_PER_UNIT;
385       op0 = SUBREG_REG (op0);
386     }
387
388   /* No action is needed if the target is a register and if the field
389      lies completely outside that register.  This can occur if the source
390      code contains an out-of-bounds access to a small array.  */
391   if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
392     return value;
393
394   /* Use vec_set patterns for inserting parts of vectors whenever
395      available.  */
396   if (VECTOR_MODE_P (GET_MODE (op0))
397       && !MEM_P (op0)
398       && (vec_set_optab->handlers[GET_MODE (op0)].insn_code
399           != CODE_FOR_nothing)
400       && fieldmode == GET_MODE_INNER (GET_MODE (op0))
401       && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
402       && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
403     {
404       enum machine_mode outermode = GET_MODE (op0);
405       enum machine_mode innermode = GET_MODE_INNER (outermode);
406       int icode = (int) vec_set_optab->handlers[outermode].insn_code;
407       int pos = bitnum / GET_MODE_BITSIZE (innermode);
408       rtx rtxpos = GEN_INT (pos);
409       rtx src = value;
410       rtx dest = op0;
411       rtx pat, seq;
412       enum machine_mode mode0 = insn_data[icode].operand[0].mode;
413       enum machine_mode mode1 = insn_data[icode].operand[1].mode;
414       enum machine_mode mode2 = insn_data[icode].operand[2].mode;
415
416       start_sequence ();
417
418       if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
419         src = copy_to_mode_reg (mode1, src);
420
421       if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
422         rtxpos = copy_to_mode_reg (mode1, rtxpos);
423
424       /* We could handle this, but we should always be called with a pseudo
425          for our targets and all insns should take them as outputs.  */
426       gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0)
427                   && (*insn_data[icode].operand[1].predicate) (src, mode1)
428                   && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2));
429       pat = GEN_FCN (icode) (dest, src, rtxpos);
430       seq = get_insns ();
431       end_sequence ();
432       if (pat)
433         {
434           emit_insn (seq);
435           emit_insn (pat);
436           return dest;
437         }
438     }
439
440   /* If the target is a register, overwriting the entire object, or storing
441      a full-word or multi-word field can be done with just a SUBREG.
442
443      If the target is memory, storing any naturally aligned field can be
444      done with a simple store.  For targets that support fast unaligned
445      memory, any naturally sized, unit aligned field can be done directly.  */
446
447   offset = bitnum / unit;
448   bitpos = bitnum % unit;
449   byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
450                 + (offset * UNITS_PER_WORD);
451
452   if (bitpos == 0
453       && bitsize == GET_MODE_BITSIZE (fieldmode)
454       && (!MEM_P (op0)
455           ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
456              || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
457              && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
458           : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
459              || (offset * BITS_PER_UNIT % bitsize == 0
460                  && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
461     {
462       if (MEM_P (op0))
463         op0 = adjust_address (op0, fieldmode, offset);
464       else if (GET_MODE (op0) != fieldmode)
465         op0 = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0),
466                                    byte_offset);
467       emit_move_insn (op0, value);
468       return value;
469     }
470
471   /* Make sure we are playing with integral modes.  Pun with subregs
472      if we aren't.  This must come after the entire register case above,
473      since that case is valid for any mode.  The following cases are only
474      valid for integral modes.  */
475   {
476     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
477     if (imode != GET_MODE (op0))
478       {
479         if (MEM_P (op0))
480           op0 = adjust_address (op0, imode, 0);
481         else
482           {
483             gcc_assert (imode != BLKmode);
484             op0 = gen_lowpart (imode, op0);
485           }
486       }
487   }
488
489   /* We may be accessing data outside the field, which means
490      we can alias adjacent data.  */
491   if (MEM_P (op0))
492     {
493       op0 = shallow_copy_rtx (op0);
494       set_mem_alias_set (op0, 0);
495       set_mem_expr (op0, 0);
496     }
497
498   /* If OP0 is a register, BITPOS must count within a word.
499      But as we have it, it counts within whatever size OP0 now has.
500      On a bigendian machine, these are not the same, so convert.  */
501   if (BYTES_BIG_ENDIAN
502       && !MEM_P (op0)
503       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
504     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
505
506   /* Storing an lsb-aligned field in a register
507      can be done with a movestrict instruction.  */
508
509   if (!MEM_P (op0)
510       && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
511       && bitsize == GET_MODE_BITSIZE (fieldmode)
512       && (movstrict_optab->handlers[fieldmode].insn_code
513           != CODE_FOR_nothing))
514     {
515       int icode = movstrict_optab->handlers[fieldmode].insn_code;
516
517       /* Get appropriate low part of the value being stored.  */
518       if (GET_CODE (value) == CONST_INT || REG_P (value))
519         value = gen_lowpart (fieldmode, value);
520       else if (!(GET_CODE (value) == SYMBOL_REF
521                  || GET_CODE (value) == LABEL_REF
522                  || GET_CODE (value) == CONST))
523         value = convert_to_mode (fieldmode, value, 0);
524
525       if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
526         value = copy_to_mode_reg (fieldmode, value);
527
528       if (GET_CODE (op0) == SUBREG)
529         {
530           /* Else we've got some float mode source being extracted into
531              a different float mode destination -- this combination of
532              subregs results in Severe Tire Damage.  */
533           gcc_assert (GET_MODE (SUBREG_REG (op0)) == fieldmode
534                       || GET_MODE_CLASS (fieldmode) == MODE_INT
535                       || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT);
536           op0 = SUBREG_REG (op0);
537         }
538
539       emit_insn (GEN_FCN (icode)
540                  (gen_rtx_SUBREG (fieldmode, op0,
541                                   (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
542                                   + (offset * UNITS_PER_WORD)),
543                                   value));
544
545       return value;
546     }
547
548   /* Handle fields bigger than a word.  */
549
550   if (bitsize > BITS_PER_WORD)
551     {
552       /* Here we transfer the words of the field
553          in the order least significant first.
554          This is because the most significant word is the one which may
555          be less than full.
556          However, only do that if the value is not BLKmode.  */
557
558       unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
559       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
560       unsigned int i;
561
562       /* This is the mode we must force value to, so that there will be enough
563          subwords to extract.  Note that fieldmode will often (always?) be
564          VOIDmode, because that is what store_field uses to indicate that this
565          is a bit field, but passing VOIDmode to operand_subword_force
566          is not allowed.  */
567       fieldmode = GET_MODE (value);
568       if (fieldmode == VOIDmode)
569         fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
570
571       for (i = 0; i < nwords; i++)
572         {
573           /* If I is 0, use the low-order word in both field and target;
574              if I is 1, use the next to lowest word; and so on.  */
575           unsigned int wordnum = (backwards ? nwords - i - 1 : i);
576           unsigned int bit_offset = (backwards
577                                      ? MAX ((int) bitsize - ((int) i + 1)
578                                             * BITS_PER_WORD,
579                                             0)
580                                      : (int) i * BITS_PER_WORD);
581
582           store_bit_field (op0, MIN (BITS_PER_WORD,
583                                      bitsize - i * BITS_PER_WORD),
584                            bitnum + bit_offset, word_mode,
585                            operand_subword_force (value, wordnum, fieldmode));
586         }
587       return value;
588     }
589
590   /* From here on we can assume that the field to be stored in is
591      a full-word (whatever type that is), since it is shorter than a word.  */
592
593   /* OFFSET is the number of words or bytes (UNIT says which)
594      from STR_RTX to the first word or byte containing part of the field.  */
595
596   if (!MEM_P (op0))
597     {
598       if (offset != 0
599           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
600         {
601           if (!REG_P (op0))
602             {
603               /* Since this is a destination (lvalue), we can't copy
604                  it to a pseudo.  We can remove a SUBREG that does not
605                  change the size of the operand.  Such a SUBREG may
606                  have been added above.  */
607               gcc_assert (GET_CODE (op0) == SUBREG
608                           && (GET_MODE_SIZE (GET_MODE (op0))
609                               == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))));
610               op0 = SUBREG_REG (op0);
611             }
612           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
613                                 op0, (offset * UNITS_PER_WORD));
614         }
615       offset = 0;
616     }
617
618   /* If VALUE has a floating-point or complex mode, access it as an
619      integer of the corresponding size.  This can occur on a machine
620      with 64 bit registers that uses SFmode for float.  It can also
621      occur for unaligned float or complex fields.  */
622   orig_value = value;
623   if (GET_MODE (value) != VOIDmode
624       && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
625       && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
626     {
627       value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value)));
628       emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value);
629     }
630
631   /* Now OFFSET is nonzero only if OP0 is memory
632      and is therefore always measured in bytes.  */
633
634   if (HAVE_insv
635       && GET_MODE (value) != BLKmode
636       && bitsize > 0
637       && GET_MODE_BITSIZE (op_mode) >= bitsize
638       && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
639             && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode)))
640       && insn_data[CODE_FOR_insv].operand[1].predicate (GEN_INT (bitsize),
641                                                         VOIDmode))
642     {
643       int xbitpos = bitpos;
644       rtx value1;
645       rtx xop0 = op0;
646       rtx last = get_last_insn ();
647       rtx pat;
648       enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
649       int save_volatile_ok = volatile_ok;
650
651       volatile_ok = 1;
652
653       /* If this machine's insv can only insert into a register, copy OP0
654          into a register and save it back later.  */
655       if (MEM_P (op0)
656           && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
657                 (op0, VOIDmode)))
658         {
659           rtx tempreg;
660           enum machine_mode bestmode;
661
662           /* Get the mode to use for inserting into this field.  If OP0 is
663              BLKmode, get the smallest mode consistent with the alignment. If
664              OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
665              mode. Otherwise, use the smallest mode containing the field.  */
666
667           if (GET_MODE (op0) == BLKmode
668               || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
669             bestmode
670               = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
671                                MEM_VOLATILE_P (op0));
672           else
673             bestmode = GET_MODE (op0);
674
675           if (bestmode == VOIDmode
676               || GET_MODE_SIZE (bestmode) < GET_MODE_SIZE (fieldmode)
677               || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
678                   && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
679             goto insv_loses;
680
681           /* Adjust address to point to the containing unit of that mode.
682              Compute offset as multiple of this unit, counting in bytes.  */
683           unit = GET_MODE_BITSIZE (bestmode);
684           offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
685           bitpos = bitnum % unit;
686           op0 = adjust_address (op0, bestmode,  offset);
687
688           /* Fetch that unit, store the bitfield in it, then store
689              the unit.  */
690           tempreg = copy_to_reg (op0);
691           store_bit_field (tempreg, bitsize, bitpos, fieldmode, orig_value);
692           emit_move_insn (op0, tempreg);
693           return value;
694         }
695       volatile_ok = save_volatile_ok;
696
697       /* Add OFFSET into OP0's address.  */
698       if (MEM_P (xop0))
699         xop0 = adjust_address (xop0, byte_mode, offset);
700
701       /* If xop0 is a register, we need it in MAXMODE
702          to make it acceptable to the format of insv.  */
703       if (GET_CODE (xop0) == SUBREG)
704         /* We can't just change the mode, because this might clobber op0,
705            and we will need the original value of op0 if insv fails.  */
706         xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
707       if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
708         xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
709
710       /* On big-endian machines, we count bits from the most significant.
711          If the bit field insn does not, we must invert.  */
712
713       if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
714         xbitpos = unit - bitsize - xbitpos;
715
716       /* We have been counting XBITPOS within UNIT.
717          Count instead within the size of the register.  */
718       if (BITS_BIG_ENDIAN && !MEM_P (xop0))
719         xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
720
721       unit = GET_MODE_BITSIZE (maxmode);
722
723       /* Convert VALUE to maxmode (which insv insn wants) in VALUE1.  */
724       value1 = value;
725       if (GET_MODE (value) != maxmode)
726         {
727           if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
728             {
729               /* Optimization: Don't bother really extending VALUE
730                  if it has all the bits we will actually use.  However,
731                  if we must narrow it, be sure we do it correctly.  */
732
733               if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
734                 {
735                   rtx tmp;
736
737                   tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0);
738                   if (! tmp)
739                     tmp = simplify_gen_subreg (maxmode,
740                                                force_reg (GET_MODE (value),
741                                                           value1),
742                                                GET_MODE (value), 0);
743                   value1 = tmp;
744                 }
745               else
746                 value1 = gen_lowpart (maxmode, value1);
747             }
748           else if (GET_CODE (value) == CONST_INT)
749             value1 = gen_int_mode (INTVAL (value), maxmode);
750           else
751             /* Parse phase is supposed to make VALUE's data type
752                match that of the component reference, which is a type
753                at least as wide as the field; so VALUE should have
754                a mode that corresponds to that type.  */
755             gcc_assert (CONSTANT_P (value));
756         }
757
758       /* If this machine's insv insists on a register,
759          get VALUE1 into a register.  */
760       if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
761              (value1, maxmode)))
762         value1 = force_reg (maxmode, value1);
763
764       pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
765       if (pat)
766         emit_insn (pat);
767       else
768         {
769           delete_insns_since (last);
770           store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
771         }
772     }
773   else
774     insv_loses:
775     /* Insv is not available; store using shifts and boolean ops.  */
776     store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
777   return value;
778 }
779 \f
780 /* Use shifts and boolean operations to store VALUE
781    into a bit field of width BITSIZE
782    in a memory location specified by OP0 except offset by OFFSET bytes.
783      (OFFSET must be 0 if OP0 is a register.)
784    The field starts at position BITPOS within the byte.
785     (If OP0 is a register, it may be a full word or a narrower mode,
786      but BITPOS still counts within a full word,
787      which is significant on bigendian machines.)  */
788
789 static void
790 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset,
791                        unsigned HOST_WIDE_INT bitsize,
792                        unsigned HOST_WIDE_INT bitpos, rtx value)
793 {
794   enum machine_mode mode;
795   unsigned int total_bits = BITS_PER_WORD;
796   rtx temp;
797   int all_zero = 0;
798   int all_one = 0;
799
800   /* There is a case not handled here:
801      a structure with a known alignment of just a halfword
802      and a field split across two aligned halfwords within the structure.
803      Or likewise a structure with a known alignment of just a byte
804      and a field split across two bytes.
805      Such cases are not supposed to be able to occur.  */
806
807   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
808     {
809       gcc_assert (!offset);
810       /* Special treatment for a bit field split across two registers.  */
811       if (bitsize + bitpos > BITS_PER_WORD)
812         {
813           store_split_bit_field (op0, bitsize, bitpos, value);
814           return;
815         }
816     }
817   else
818     {
819       /* Get the proper mode to use for this field.  We want a mode that
820          includes the entire field.  If such a mode would be larger than
821          a word, we won't be doing the extraction the normal way.
822          We don't want a mode bigger than the destination.  */
823
824       mode = GET_MODE (op0);
825       if (GET_MODE_BITSIZE (mode) == 0
826           || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
827         mode = word_mode;
828       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
829                             MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
830
831       if (mode == VOIDmode)
832         {
833           /* The only way this should occur is if the field spans word
834              boundaries.  */
835           store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
836                                  value);
837           return;
838         }
839
840       total_bits = GET_MODE_BITSIZE (mode);
841
842       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
843          be in the range 0 to total_bits-1, and put any excess bytes in
844          OFFSET.  */
845       if (bitpos >= total_bits)
846         {
847           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
848           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
849                      * BITS_PER_UNIT);
850         }
851
852       /* Get ref to an aligned byte, halfword, or word containing the field.
853          Adjust BITPOS to be position within a word,
854          and OFFSET to be the offset of that word.
855          Then alter OP0 to refer to that word.  */
856       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
857       offset -= (offset % (total_bits / BITS_PER_UNIT));
858       op0 = adjust_address (op0, mode, offset);
859     }
860
861   mode = GET_MODE (op0);
862
863   /* Now MODE is either some integral mode for a MEM as OP0,
864      or is a full-word for a REG as OP0.  TOTAL_BITS corresponds.
865      The bit field is contained entirely within OP0.
866      BITPOS is the starting bit number within OP0.
867      (OP0's mode may actually be narrower than MODE.)  */
868
869   if (BYTES_BIG_ENDIAN)
870       /* BITPOS is the distance between our msb
871          and that of the containing datum.
872          Convert it to the distance from the lsb.  */
873       bitpos = total_bits - bitsize - bitpos;
874
875   /* Now BITPOS is always the distance between our lsb
876      and that of OP0.  */
877
878   /* Shift VALUE left by BITPOS bits.  If VALUE is not constant,
879      we must first convert its mode to MODE.  */
880
881   if (GET_CODE (value) == CONST_INT)
882     {
883       HOST_WIDE_INT v = INTVAL (value);
884
885       if (bitsize < HOST_BITS_PER_WIDE_INT)
886         v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
887
888       if (v == 0)
889         all_zero = 1;
890       else if ((bitsize < HOST_BITS_PER_WIDE_INT
891                 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
892                || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
893         all_one = 1;
894
895       value = lshift_value (mode, value, bitpos, bitsize);
896     }
897   else
898     {
899       int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
900                       && bitpos + bitsize != GET_MODE_BITSIZE (mode));
901
902       if (GET_MODE (value) != mode)
903         {
904           if ((REG_P (value) || GET_CODE (value) == SUBREG)
905               && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
906             value = gen_lowpart (mode, value);
907           else
908             value = convert_to_mode (mode, value, 1);
909         }
910
911       if (must_and)
912         value = expand_binop (mode, and_optab, value,
913                               mask_rtx (mode, 0, bitsize, 0),
914                               NULL_RTX, 1, OPTAB_LIB_WIDEN);
915       if (bitpos > 0)
916         value = expand_shift (LSHIFT_EXPR, mode, value,
917                               build_int_cst (NULL_TREE, bitpos), NULL_RTX, 1);
918     }
919
920   /* Now clear the chosen bits in OP0,
921      except that if VALUE is -1 we need not bother.  */
922   /* We keep the intermediates in registers to allow CSE to combine
923      consecutive bitfield assignments.  */
924
925   temp = force_reg (mode, op0);
926
927   if (! all_one)
928     {
929       temp = expand_binop (mode, and_optab, temp,
930                            mask_rtx (mode, bitpos, bitsize, 1),
931                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
932       temp = force_reg (mode, temp);
933     }
934
935   /* Now logical-or VALUE into OP0, unless it is zero.  */
936
937   if (! all_zero)
938     {
939       temp = expand_binop (mode, ior_optab, temp, value,
940                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
941       temp = force_reg (mode, temp);
942     }
943
944   if (op0 != temp)
945     emit_move_insn (op0, temp);
946 }
947 \f
948 /* Store a bit field that is split across multiple accessible memory objects.
949
950    OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
951    BITSIZE is the field width; BITPOS the position of its first bit
952    (within the word).
953    VALUE is the value to store.
954
955    This does not yet handle fields wider than BITS_PER_WORD.  */
956
957 static void
958 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
959                        unsigned HOST_WIDE_INT bitpos, rtx value)
960 {
961   unsigned int unit;
962   unsigned int bitsdone = 0;
963
964   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
965      much at a time.  */
966   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
967     unit = BITS_PER_WORD;
968   else
969     unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
970
971   /* If VALUE is a constant other than a CONST_INT, get it into a register in
972      WORD_MODE.  If we can do this using gen_lowpart_common, do so.  Note
973      that VALUE might be a floating-point constant.  */
974   if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
975     {
976       rtx word = gen_lowpart_common (word_mode, value);
977
978       if (word && (value != word))
979         value = word;
980       else
981         value = gen_lowpart_common (word_mode,
982                                     force_reg (GET_MODE (value) != VOIDmode
983                                                ? GET_MODE (value)
984                                                : word_mode, value));
985     }
986
987   while (bitsdone < bitsize)
988     {
989       unsigned HOST_WIDE_INT thissize;
990       rtx part, word;
991       unsigned HOST_WIDE_INT thispos;
992       unsigned HOST_WIDE_INT offset;
993
994       offset = (bitpos + bitsdone) / unit;
995       thispos = (bitpos + bitsdone) % unit;
996
997       /* THISSIZE must not overrun a word boundary.  Otherwise,
998          store_fixed_bit_field will call us again, and we will mutually
999          recurse forever.  */
1000       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1001       thissize = MIN (thissize, unit - thispos);
1002
1003       if (BYTES_BIG_ENDIAN)
1004         {
1005           int total_bits;
1006
1007           /* We must do an endian conversion exactly the same way as it is
1008              done in extract_bit_field, so that the two calls to
1009              extract_fixed_bit_field will have comparable arguments.  */
1010           if (!MEM_P (value) || GET_MODE (value) == BLKmode)
1011             total_bits = BITS_PER_WORD;
1012           else
1013             total_bits = GET_MODE_BITSIZE (GET_MODE (value));
1014
1015           /* Fetch successively less significant portions.  */
1016           if (GET_CODE (value) == CONST_INT)
1017             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1018                              >> (bitsize - bitsdone - thissize))
1019                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1020           else
1021             /* The args are chosen so that the last part includes the
1022                lsb.  Give extract_bit_field the value it needs (with
1023                endianness compensation) to fetch the piece we want.  */
1024             part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1025                                             total_bits - bitsize + bitsdone,
1026                                             NULL_RTX, 1);
1027         }
1028       else
1029         {
1030           /* Fetch successively more significant portions.  */
1031           if (GET_CODE (value) == CONST_INT)
1032             part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1033                              >> bitsdone)
1034                             & (((HOST_WIDE_INT) 1 << thissize) - 1));
1035           else
1036             part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1037                                             bitsdone, NULL_RTX, 1);
1038         }
1039
1040       /* If OP0 is a register, then handle OFFSET here.
1041
1042          When handling multiword bitfields, extract_bit_field may pass
1043          down a word_mode SUBREG of a larger REG for a bitfield that actually
1044          crosses a word boundary.  Thus, for a SUBREG, we must find
1045          the current word starting from the base register.  */
1046       if (GET_CODE (op0) == SUBREG)
1047         {
1048           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1049           word = operand_subword_force (SUBREG_REG (op0), word_offset,
1050                                         GET_MODE (SUBREG_REG (op0)));
1051           offset = 0;
1052         }
1053       else if (REG_P (op0))
1054         {
1055           word = operand_subword_force (op0, offset, GET_MODE (op0));
1056           offset = 0;
1057         }
1058       else
1059         word = op0;
1060
1061       /* OFFSET is in UNITs, and UNIT is in bits.
1062          store_fixed_bit_field wants offset in bytes.  */
1063       store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
1064                              thispos, part);
1065       bitsdone += thissize;
1066     }
1067 }
1068 \f
1069 /* Generate code to extract a byte-field from STR_RTX
1070    containing BITSIZE bits, starting at BITNUM,
1071    and put it in TARGET if possible (if TARGET is nonzero).
1072    Regardless of TARGET, we return the rtx for where the value is placed.
1073
1074    STR_RTX is the structure containing the byte (a REG or MEM).
1075    UNSIGNEDP is nonzero if this is an unsigned bit field.
1076    MODE is the natural mode of the field value once extracted.
1077    TMODE is the mode the caller would like the value to have;
1078    but the value may be returned with type MODE instead.
1079
1080    TOTAL_SIZE is the size in bytes of the containing structure,
1081    or -1 if varying.
1082
1083    If a TARGET is specified and we can store in it at no extra cost,
1084    we do so, and return TARGET.
1085    Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1086    if they are equally easy.  */
1087
1088 rtx
1089 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1090                    unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1091                    enum machine_mode mode, enum machine_mode tmode)
1092 {
1093   unsigned int unit
1094     = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
1095   unsigned HOST_WIDE_INT offset, bitpos;
1096   rtx op0 = str_rtx;
1097   rtx spec_target = target;
1098   rtx spec_target_subreg = 0;
1099   enum machine_mode int_mode;
1100   enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1101   enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1102   enum machine_mode mode1;
1103   int byte_offset;
1104
1105   if (tmode == VOIDmode)
1106     tmode = mode;
1107
1108   while (GET_CODE (op0) == SUBREG)
1109     {
1110       bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1111       op0 = SUBREG_REG (op0);
1112     }
1113
1114   /* If we have an out-of-bounds access to a register, just return an
1115      uninitialized register of the required mode.  This can occur if the
1116      source code contains an out-of-bounds access to a small array.  */
1117   if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
1118     return gen_reg_rtx (tmode);
1119
1120   if (REG_P (op0)
1121       && mode == GET_MODE (op0)
1122       && bitnum == 0
1123       && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1124     {
1125       /* We're trying to extract a full register from itself.  */
1126       return op0;
1127     }
1128
1129   /* Use vec_extract patterns for extracting parts of vectors whenever
1130      available.  */
1131   if (VECTOR_MODE_P (GET_MODE (op0))
1132       && !MEM_P (op0)
1133       && (vec_extract_optab->handlers[GET_MODE (op0)].insn_code
1134           != CODE_FOR_nothing)
1135       && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1136           == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1137     {
1138       enum machine_mode outermode = GET_MODE (op0);
1139       enum machine_mode innermode = GET_MODE_INNER (outermode);
1140       int icode = (int) vec_extract_optab->handlers[outermode].insn_code;
1141       unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode);
1142       rtx rtxpos = GEN_INT (pos);
1143       rtx src = op0;
1144       rtx dest = NULL, pat, seq;
1145       enum machine_mode mode0 = insn_data[icode].operand[0].mode;
1146       enum machine_mode mode1 = insn_data[icode].operand[1].mode;
1147       enum machine_mode mode2 = insn_data[icode].operand[2].mode;
1148
1149       if (innermode == tmode || innermode == mode)
1150         dest = target;
1151
1152       if (!dest)
1153         dest = gen_reg_rtx (innermode);
1154
1155       start_sequence ();
1156
1157       if (! (*insn_data[icode].operand[0].predicate) (dest, mode0))
1158         dest = copy_to_mode_reg (mode0, dest);
1159
1160       if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
1161         src = copy_to_mode_reg (mode1, src);
1162
1163       if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1164         rtxpos = copy_to_mode_reg (mode1, rtxpos);
1165
1166       /* We could handle this, but we should always be called with a pseudo
1167          for our targets and all insns should take them as outputs.  */
1168       gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0)
1169                   && (*insn_data[icode].operand[1].predicate) (src, mode1)
1170                   && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2));
1171
1172       pat = GEN_FCN (icode) (dest, src, rtxpos);
1173       seq = get_insns ();
1174       end_sequence ();
1175       if (pat)
1176         {
1177           emit_insn (seq);
1178           emit_insn (pat);
1179           return dest;
1180         }
1181     }
1182
1183   /* Make sure we are playing with integral modes.  Pun with subregs
1184      if we aren't.  */
1185   {
1186     enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1187     if (imode != GET_MODE (op0))
1188       {
1189         if (MEM_P (op0))
1190           op0 = adjust_address (op0, imode, 0);
1191         else
1192           {
1193             gcc_assert (imode != BLKmode);
1194             op0 = gen_lowpart (imode, op0);
1195
1196             /* If we got a SUBREG, force it into a register since we
1197                aren't going to be able to do another SUBREG on it.  */
1198             if (GET_CODE (op0) == SUBREG)
1199               op0 = force_reg (imode, op0);
1200           }
1201       }
1202   }
1203
1204   /* We may be accessing data outside the field, which means
1205      we can alias adjacent data.  */
1206   if (MEM_P (op0))
1207     {
1208       op0 = shallow_copy_rtx (op0);
1209       set_mem_alias_set (op0, 0);
1210       set_mem_expr (op0, 0);
1211     }
1212
1213   /* Extraction of a full-word or multi-word value from a structure
1214      in a register or aligned memory can be done with just a SUBREG.
1215      A subword value in the least significant part of a register
1216      can also be extracted with a SUBREG.  For this, we need the
1217      byte offset of the value in op0.  */
1218
1219   bitpos = bitnum % unit;
1220   offset = bitnum / unit;
1221   byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1222
1223   /* If OP0 is a register, BITPOS must count within a word.
1224      But as we have it, it counts within whatever size OP0 now has.
1225      On a bigendian machine, these are not the same, so convert.  */
1226   if (BYTES_BIG_ENDIAN
1227       && !MEM_P (op0)
1228       && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1229     bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1230
1231   /* ??? We currently assume TARGET is at least as big as BITSIZE.
1232      If that's wrong, the solution is to test for it and set TARGET to 0
1233      if needed.  */
1234
1235   /* Only scalar integer modes can be converted via subregs.  There is an
1236      additional problem for FP modes here in that they can have a precision
1237      which is different from the size.  mode_for_size uses precision, but
1238      we want a mode based on the size, so we must avoid calling it for FP
1239      modes.  */
1240   mode1  = (SCALAR_INT_MODE_P (tmode)
1241             ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0)
1242             : mode);
1243
1244   if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1245         && bitpos % BITS_PER_WORD == 0)
1246        || (mode1 != BLKmode
1247            /* ??? The big endian test here is wrong.  This is correct
1248               if the value is in a register, and if mode_for_size is not
1249               the same mode as op0.  This causes us to get unnecessarily
1250               inefficient code from the Thumb port when -mbig-endian.  */
1251            && (BYTES_BIG_ENDIAN
1252                ? bitpos + bitsize == BITS_PER_WORD
1253                : bitpos == 0)))
1254       && ((!MEM_P (op0)
1255            && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1256                                      GET_MODE_BITSIZE (GET_MODE (op0)))
1257            && GET_MODE_SIZE (mode1) != 0
1258            && byte_offset % GET_MODE_SIZE (mode1) == 0)
1259           || (MEM_P (op0)
1260               && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1261                   || (offset * BITS_PER_UNIT % bitsize == 0
1262                       && MEM_ALIGN (op0) % bitsize == 0)))))
1263     {
1264       if (mode1 != GET_MODE (op0))
1265         {
1266           if (MEM_P (op0))
1267             op0 = adjust_address (op0, mode1, offset);
1268           else
1269             {
1270               rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0),
1271                                              byte_offset);
1272               if (sub == NULL)
1273                 goto no_subreg_mode_swap;
1274               op0 = sub;
1275             }
1276         }
1277       if (mode1 != mode)
1278         return convert_to_mode (tmode, op0, unsignedp);
1279       return op0;
1280     }
1281  no_subreg_mode_swap:
1282
1283   /* Handle fields bigger than a word.  */
1284
1285   if (bitsize > BITS_PER_WORD)
1286     {
1287       /* Here we transfer the words of the field
1288          in the order least significant first.
1289          This is because the most significant word is the one which may
1290          be less than full.  */
1291
1292       unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1293       unsigned int i;
1294
1295       if (target == 0 || !REG_P (target))
1296         target = gen_reg_rtx (mode);
1297
1298       /* Indicate for flow that the entire target reg is being set.  */
1299       emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1300
1301       for (i = 0; i < nwords; i++)
1302         {
1303           /* If I is 0, use the low-order word in both field and target;
1304              if I is 1, use the next to lowest word; and so on.  */
1305           /* Word number in TARGET to use.  */
1306           unsigned int wordnum
1307             = (WORDS_BIG_ENDIAN
1308                ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1309                : i);
1310           /* Offset from start of field in OP0.  */
1311           unsigned int bit_offset = (WORDS_BIG_ENDIAN
1312                                      ? MAX (0, ((int) bitsize - ((int) i + 1)
1313                                                 * (int) BITS_PER_WORD))
1314                                      : (int) i * BITS_PER_WORD);
1315           rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1316           rtx result_part
1317             = extract_bit_field (op0, MIN (BITS_PER_WORD,
1318                                            bitsize - i * BITS_PER_WORD),
1319                                  bitnum + bit_offset, 1, target_part, mode,
1320                                  word_mode);
1321
1322           gcc_assert (target_part);
1323
1324           if (result_part != target_part)
1325             emit_move_insn (target_part, result_part);
1326         }
1327
1328       if (unsignedp)
1329         {
1330           /* Unless we've filled TARGET, the upper regs in a multi-reg value
1331              need to be zero'd out.  */
1332           if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1333             {
1334               unsigned int i, total_words;
1335
1336               total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1337               for (i = nwords; i < total_words; i++)
1338                 emit_move_insn
1339                   (operand_subword (target,
1340                                     WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1341                                     1, VOIDmode),
1342                    const0_rtx);
1343             }
1344           return target;
1345         }
1346
1347       /* Signed bit field: sign-extend with two arithmetic shifts.  */
1348       target = expand_shift (LSHIFT_EXPR, mode, target,
1349                              build_int_cst (NULL_TREE,
1350                                             GET_MODE_BITSIZE (mode) - bitsize),
1351                              NULL_RTX, 0);
1352       return expand_shift (RSHIFT_EXPR, mode, target,
1353                            build_int_cst (NULL_TREE,
1354                                           GET_MODE_BITSIZE (mode) - bitsize),
1355                            NULL_RTX, 0);
1356     }
1357
1358   /* From here on we know the desired field is smaller than a word.  */
1359
1360   /* Check if there is a correspondingly-sized integer field, so we can
1361      safely extract it as one size of integer, if necessary; then
1362      truncate or extend to the size that is wanted; then use SUBREGs or
1363      convert_to_mode to get one of the modes we really wanted.  */
1364
1365   int_mode = int_mode_for_mode (tmode);
1366   if (int_mode == BLKmode)
1367     int_mode = int_mode_for_mode (mode);
1368   /* Should probably push op0 out to memory and then do a load.  */
1369   gcc_assert (int_mode != BLKmode);
1370
1371   /* OFFSET is the number of words or bytes (UNIT says which)
1372      from STR_RTX to the first word or byte containing part of the field.  */
1373   if (!MEM_P (op0))
1374     {
1375       if (offset != 0
1376           || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1377         {
1378           if (!REG_P (op0))
1379             op0 = copy_to_reg (op0);
1380           op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1381                                 op0, (offset * UNITS_PER_WORD));
1382         }
1383       offset = 0;
1384     }
1385
1386   /* Now OFFSET is nonzero only for memory operands.  */
1387
1388   if (unsignedp)
1389     {
1390       if (HAVE_extzv
1391           && bitsize > 0
1392           && GET_MODE_BITSIZE (extzv_mode) >= bitsize
1393           && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
1394                 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1395         {
1396           unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1397           rtx bitsize_rtx, bitpos_rtx;
1398           rtx last = get_last_insn ();
1399           rtx xop0 = op0;
1400           rtx xtarget = target;
1401           rtx xspec_target = spec_target;
1402           rtx xspec_target_subreg = spec_target_subreg;
1403           rtx pat;
1404           enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1405
1406           if (MEM_P (xop0))
1407             {
1408               int save_volatile_ok = volatile_ok;
1409               volatile_ok = 1;
1410
1411               /* Is the memory operand acceptable?  */
1412               if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1413                      (xop0, GET_MODE (xop0))))
1414                 {
1415                   /* No, load into a reg and extract from there.  */
1416                   enum machine_mode bestmode;
1417
1418                   /* Get the mode to use for inserting into this field.  If
1419                      OP0 is BLKmode, get the smallest mode consistent with the
1420                      alignment. If OP0 is a non-BLKmode object that is no
1421                      wider than MAXMODE, use its mode. Otherwise, use the
1422                      smallest mode containing the field.  */
1423
1424                   if (GET_MODE (xop0) == BLKmode
1425                       || (GET_MODE_SIZE (GET_MODE (op0))
1426                           > GET_MODE_SIZE (maxmode)))
1427                     bestmode = get_best_mode (bitsize, bitnum,
1428                                               MEM_ALIGN (xop0), maxmode,
1429                                               MEM_VOLATILE_P (xop0));
1430                   else
1431                     bestmode = GET_MODE (xop0);
1432
1433                   if (bestmode == VOIDmode
1434                       || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1435                           && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1436                     goto extzv_loses;
1437
1438                   /* Compute offset as multiple of this unit,
1439                      counting in bytes.  */
1440                   unit = GET_MODE_BITSIZE (bestmode);
1441                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1442                   xbitpos = bitnum % unit;
1443                   xop0 = adjust_address (xop0, bestmode, xoffset);
1444
1445                   /* Make sure register is big enough for the whole field. */
1446                   if (xoffset * BITS_PER_UNIT + unit 
1447                       < offset * BITS_PER_UNIT + bitsize)
1448                     goto extzv_loses;
1449
1450                   /* Fetch it to a register in that size.  */
1451                   xop0 = force_reg (bestmode, xop0);
1452
1453                   /* XBITPOS counts within UNIT, which is what is expected.  */
1454                 }
1455               else
1456                 /* Get ref to first byte containing part of the field.  */
1457                 xop0 = adjust_address (xop0, byte_mode, xoffset);
1458
1459               volatile_ok = save_volatile_ok;
1460             }
1461
1462           /* If op0 is a register, we need it in MAXMODE (which is usually
1463              SImode). to make it acceptable to the format of extzv.  */
1464           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1465             goto extzv_loses;
1466           if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
1467             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1468
1469           /* On big-endian machines, we count bits from the most significant.
1470              If the bit field insn does not, we must invert.  */
1471           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1472             xbitpos = unit - bitsize - xbitpos;
1473
1474           /* Now convert from counting within UNIT to counting in MAXMODE.  */
1475           if (BITS_BIG_ENDIAN && !MEM_P (xop0))
1476             xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1477
1478           unit = GET_MODE_BITSIZE (maxmode);
1479
1480           if (xtarget == 0)
1481             xtarget = xspec_target = gen_reg_rtx (tmode);
1482
1483           if (GET_MODE (xtarget) != maxmode)
1484             {
1485               if (REG_P (xtarget))
1486                 {
1487                   int wider = (GET_MODE_SIZE (maxmode)
1488                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1489                   xtarget = gen_lowpart (maxmode, xtarget);
1490                   if (wider)
1491                     xspec_target_subreg = xtarget;
1492                 }
1493               else
1494                 xtarget = gen_reg_rtx (maxmode);
1495             }
1496
1497           /* If this machine's extzv insists on a register target,
1498              make sure we have one.  */
1499           if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1500                  (xtarget, maxmode)))
1501             xtarget = gen_reg_rtx (maxmode);
1502
1503           bitsize_rtx = GEN_INT (bitsize);
1504           bitpos_rtx = GEN_INT (xbitpos);
1505
1506           pat = gen_extzv (xtarget, xop0, bitsize_rtx, bitpos_rtx);
1507           if (pat)
1508             {
1509               emit_insn (pat);
1510               target = xtarget;
1511               spec_target = xspec_target;
1512               spec_target_subreg = xspec_target_subreg;
1513             }
1514           else
1515             {
1516               delete_insns_since (last);
1517               target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1518                                                 bitpos, target, 1);
1519             }
1520         }
1521       else
1522       extzv_loses:
1523         target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1524                                           bitpos, target, 1);
1525     }
1526   else
1527     {
1528       if (HAVE_extv
1529           && bitsize > 0
1530           && GET_MODE_BITSIZE (extv_mode) >= bitsize
1531           && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
1532                 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1533         {
1534           int xbitpos = bitpos, xoffset = offset;
1535           rtx bitsize_rtx, bitpos_rtx;
1536           rtx last = get_last_insn ();
1537           rtx xop0 = op0, xtarget = target;
1538           rtx xspec_target = spec_target;
1539           rtx xspec_target_subreg = spec_target_subreg;
1540           rtx pat;
1541           enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1542
1543           if (MEM_P (xop0))
1544             {
1545               /* Is the memory operand acceptable?  */
1546               if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1547                      (xop0, GET_MODE (xop0))))
1548                 {
1549                   /* No, load into a reg and extract from there.  */
1550                   enum machine_mode bestmode;
1551
1552                   /* Get the mode to use for inserting into this field.  If
1553                      OP0 is BLKmode, get the smallest mode consistent with the
1554                      alignment. If OP0 is a non-BLKmode object that is no
1555                      wider than MAXMODE, use its mode. Otherwise, use the
1556                      smallest mode containing the field.  */
1557
1558                   if (GET_MODE (xop0) == BLKmode
1559                       || (GET_MODE_SIZE (GET_MODE (op0))
1560                           > GET_MODE_SIZE (maxmode)))
1561                     bestmode = get_best_mode (bitsize, bitnum,
1562                                               MEM_ALIGN (xop0), maxmode,
1563                                               MEM_VOLATILE_P (xop0));
1564                   else
1565                     bestmode = GET_MODE (xop0);
1566
1567                   if (bestmode == VOIDmode
1568                       || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1569                           && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1570                     goto extv_loses;
1571
1572                   /* Compute offset as multiple of this unit,
1573                      counting in bytes.  */
1574                   unit = GET_MODE_BITSIZE (bestmode);
1575                   xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1576                   xbitpos = bitnum % unit;
1577                   xop0 = adjust_address (xop0, bestmode, xoffset);
1578
1579                   /* Make sure register is big enough for the whole field. */
1580                   if (xoffset * BITS_PER_UNIT + unit 
1581                       < offset * BITS_PER_UNIT + bitsize)
1582                     goto extv_loses;
1583
1584                   /* Fetch it to a register in that size.  */
1585                   xop0 = force_reg (bestmode, xop0);
1586
1587                   /* XBITPOS counts within UNIT, which is what is expected.  */
1588                 }
1589               else
1590                 /* Get ref to first byte containing part of the field.  */
1591                 xop0 = adjust_address (xop0, byte_mode, xoffset);
1592             }
1593
1594           /* If op0 is a register, we need it in MAXMODE (which is usually
1595              SImode) to make it acceptable to the format of extv.  */
1596           if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1597             goto extv_loses;
1598           if (REG_P (xop0) && GET_MODE (xop0) != maxmode)
1599             xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1600
1601           /* On big-endian machines, we count bits from the most significant.
1602              If the bit field insn does not, we must invert.  */
1603           if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1604             xbitpos = unit - bitsize - xbitpos;
1605
1606           /* XBITPOS counts within a size of UNIT.
1607              Adjust to count within a size of MAXMODE.  */
1608           if (BITS_BIG_ENDIAN && !MEM_P (xop0))
1609             xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1610
1611           unit = GET_MODE_BITSIZE (maxmode);
1612
1613           if (xtarget == 0)
1614             xtarget = xspec_target = gen_reg_rtx (tmode);
1615
1616           if (GET_MODE (xtarget) != maxmode)
1617             {
1618               if (REG_P (xtarget))
1619                 {
1620                   int wider = (GET_MODE_SIZE (maxmode)
1621                                > GET_MODE_SIZE (GET_MODE (xtarget)));
1622                   xtarget = gen_lowpart (maxmode, xtarget);
1623                   if (wider)
1624                     xspec_target_subreg = xtarget;
1625                 }
1626               else
1627                 xtarget = gen_reg_rtx (maxmode);
1628             }
1629
1630           /* If this machine's extv insists on a register target,
1631              make sure we have one.  */
1632           if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1633                  (xtarget, maxmode)))
1634             xtarget = gen_reg_rtx (maxmode);
1635
1636           bitsize_rtx = GEN_INT (bitsize);
1637           bitpos_rtx = GEN_INT (xbitpos);
1638
1639           pat = gen_extv (xtarget, xop0, bitsize_rtx, bitpos_rtx);
1640           if (pat)
1641             {
1642               emit_insn (pat);
1643               target = xtarget;
1644               spec_target = xspec_target;
1645               spec_target_subreg = xspec_target_subreg;
1646             }
1647           else
1648             {
1649               delete_insns_since (last);
1650               target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1651                                                 bitpos, target, 0);
1652             }
1653         }
1654       else
1655       extv_loses:
1656         target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1657                                           bitpos, target, 0);
1658     }
1659   if (target == spec_target)
1660     return target;
1661   if (target == spec_target_subreg)
1662     return spec_target;
1663   if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1664     {
1665       /* If the target mode is not a scalar integral, first convert to the
1666          integer mode of that size and then access it as a floating-point
1667          value via a SUBREG.  */
1668       if (!SCALAR_INT_MODE_P (tmode))
1669         {
1670           enum machine_mode smode
1671             = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0);
1672           target = convert_to_mode (smode, target, unsignedp);
1673           target = force_reg (smode, target);
1674           return gen_lowpart (tmode, target);
1675         }
1676
1677       return convert_to_mode (tmode, target, unsignedp);
1678     }
1679   return target;
1680 }
1681 \f
1682 /* Extract a bit field using shifts and boolean operations
1683    Returns an rtx to represent the value.
1684    OP0 addresses a register (word) or memory (byte).
1685    BITPOS says which bit within the word or byte the bit field starts in.
1686    OFFSET says how many bytes farther the bit field starts;
1687     it is 0 if OP0 is a register.
1688    BITSIZE says how many bits long the bit field is.
1689     (If OP0 is a register, it may be narrower than a full word,
1690      but BITPOS still counts within a full word,
1691      which is significant on bigendian machines.)
1692
1693    UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1694    If TARGET is nonzero, attempts to store the value there
1695    and return TARGET, but this is not guaranteed.
1696    If TARGET is not used, create a pseudo-reg of mode TMODE for the value.  */
1697
1698 static rtx
1699 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1700                          unsigned HOST_WIDE_INT offset,
1701                          unsigned HOST_WIDE_INT bitsize,
1702                          unsigned HOST_WIDE_INT bitpos, rtx target,
1703                          int unsignedp)
1704 {
1705   unsigned int total_bits = BITS_PER_WORD;
1706   enum machine_mode mode;
1707
1708   if (GET_CODE (op0) == SUBREG || REG_P (op0))
1709     {
1710       /* Special treatment for a bit field split across two registers.  */
1711       if (bitsize + bitpos > BITS_PER_WORD)
1712         return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1713     }
1714   else
1715     {
1716       /* Get the proper mode to use for this field.  We want a mode that
1717          includes the entire field.  If such a mode would be larger than
1718          a word, we won't be doing the extraction the normal way.  */
1719
1720       mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1721                             MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1722
1723       if (mode == VOIDmode)
1724         /* The only way this should occur is if the field spans word
1725            boundaries.  */
1726         return extract_split_bit_field (op0, bitsize,
1727                                         bitpos + offset * BITS_PER_UNIT,
1728                                         unsignedp);
1729
1730       total_bits = GET_MODE_BITSIZE (mode);
1731
1732       /* Make sure bitpos is valid for the chosen mode.  Adjust BITPOS to
1733          be in the range 0 to total_bits-1, and put any excess bytes in
1734          OFFSET.  */
1735       if (bitpos >= total_bits)
1736         {
1737           offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1738           bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1739                      * BITS_PER_UNIT);
1740         }
1741
1742       /* Get ref to an aligned byte, halfword, or word containing the field.
1743          Adjust BITPOS to be position within a word,
1744          and OFFSET to be the offset of that word.
1745          Then alter OP0 to refer to that word.  */
1746       bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1747       offset -= (offset % (total_bits / BITS_PER_UNIT));
1748       op0 = adjust_address (op0, mode, offset);
1749     }
1750
1751   mode = GET_MODE (op0);
1752
1753   if (BYTES_BIG_ENDIAN)
1754     /* BITPOS is the distance between our msb and that of OP0.
1755        Convert it to the distance from the lsb.  */
1756     bitpos = total_bits - bitsize - bitpos;
1757
1758   /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1759      We have reduced the big-endian case to the little-endian case.  */
1760
1761   if (unsignedp)
1762     {
1763       if (bitpos)
1764         {
1765           /* If the field does not already start at the lsb,
1766              shift it so it does.  */
1767           tree amount = build_int_cst (NULL_TREE, bitpos);
1768           /* Maybe propagate the target for the shift.  */
1769           /* But not if we will return it--could confuse integrate.c.  */
1770           rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1771           if (tmode != mode) subtarget = 0;
1772           op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1773         }
1774       /* Convert the value to the desired mode.  */
1775       if (mode != tmode)
1776         op0 = convert_to_mode (tmode, op0, 1);
1777
1778       /* Unless the msb of the field used to be the msb when we shifted,
1779          mask out the upper bits.  */
1780
1781       if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1782         return expand_binop (GET_MODE (op0), and_optab, op0,
1783                              mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1784                              target, 1, OPTAB_LIB_WIDEN);
1785       return op0;
1786     }
1787
1788   /* To extract a signed bit-field, first shift its msb to the msb of the word,
1789      then arithmetic-shift its lsb to the lsb of the word.  */
1790   op0 = force_reg (mode, op0);
1791   if (mode != tmode)
1792     target = 0;
1793
1794   /* Find the narrowest integer mode that contains the field.  */
1795
1796   for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1797        mode = GET_MODE_WIDER_MODE (mode))
1798     if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1799       {
1800         op0 = convert_to_mode (mode, op0, 0);
1801         break;
1802       }
1803
1804   if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1805     {
1806       tree amount
1807         = build_int_cst (NULL_TREE,
1808                          GET_MODE_BITSIZE (mode) - (bitsize + bitpos));
1809       /* Maybe propagate the target for the shift.  */
1810       rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1811       op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1812     }
1813
1814   return expand_shift (RSHIFT_EXPR, mode, op0,
1815                        build_int_cst (NULL_TREE,
1816                                       GET_MODE_BITSIZE (mode) - bitsize),
1817                        target, 0);
1818 }
1819 \f
1820 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1821    of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1822    complement of that if COMPLEMENT.  The mask is truncated if
1823    necessary to the width of mode MODE.  The mask is zero-extended if
1824    BITSIZE+BITPOS is too small for MODE.  */
1825
1826 static rtx
1827 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1828 {
1829   HOST_WIDE_INT masklow, maskhigh;
1830
1831   if (bitsize == 0)
1832     masklow = 0;
1833   else if (bitpos < HOST_BITS_PER_WIDE_INT)
1834     masklow = (HOST_WIDE_INT) -1 << bitpos;
1835   else
1836     masklow = 0;
1837
1838   if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1839     masklow &= ((unsigned HOST_WIDE_INT) -1
1840                 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1841
1842   if (bitpos <= HOST_BITS_PER_WIDE_INT)
1843     maskhigh = -1;
1844   else
1845     maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1846
1847   if (bitsize == 0)
1848     maskhigh = 0;
1849   else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1850     maskhigh &= ((unsigned HOST_WIDE_INT) -1
1851                  >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1852   else
1853     maskhigh = 0;
1854
1855   if (complement)
1856     {
1857       maskhigh = ~maskhigh;
1858       masklow = ~masklow;
1859     }
1860
1861   return immed_double_const (masklow, maskhigh, mode);
1862 }
1863
1864 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1865    VALUE truncated to BITSIZE bits and then shifted left BITPOS bits.  */
1866
1867 static rtx
1868 lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize)
1869 {
1870   unsigned HOST_WIDE_INT v = INTVAL (value);
1871   HOST_WIDE_INT low, high;
1872
1873   if (bitsize < HOST_BITS_PER_WIDE_INT)
1874     v &= ~((HOST_WIDE_INT) -1 << bitsize);
1875
1876   if (bitpos < HOST_BITS_PER_WIDE_INT)
1877     {
1878       low = v << bitpos;
1879       high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1880     }
1881   else
1882     {
1883       low = 0;
1884       high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1885     }
1886
1887   return immed_double_const (low, high, mode);
1888 }
1889 \f
1890 /* Extract a bit field from a memory by forcing the alignment of the
1891    memory.  This efficient only if the field spans at least 4 boundaries.
1892
1893    OP0 is the MEM.
1894    BITSIZE is the field width; BITPOS is the position of the first bit.
1895    UNSIGNEDP is true if the result should be zero-extended.  */
1896
1897 static rtx
1898 extract_force_align_mem_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1899                                    unsigned HOST_WIDE_INT bitpos,
1900                                    int unsignedp)
1901 {
1902   enum machine_mode mode, dmode;
1903   unsigned int m_bitsize, m_size;
1904   unsigned int sign_shift_up, sign_shift_dn;
1905   rtx base, a1, a2, v1, v2, comb, shift, result, start;
1906
1907   /* Choose a mode that will fit BITSIZE.  */
1908   mode = smallest_mode_for_size (bitsize, MODE_INT);
1909   m_size = GET_MODE_SIZE (mode);
1910   m_bitsize = GET_MODE_BITSIZE (mode);
1911
1912   /* Choose a mode twice as wide.  Fail if no such mode exists.  */
1913   dmode = mode_for_size (m_bitsize * 2, MODE_INT, false);
1914   if (dmode == BLKmode)
1915     return NULL;
1916
1917   do_pending_stack_adjust ();
1918   start = get_last_insn ();
1919
1920   /* At the end, we'll need an additional shift to deal with sign/zero
1921      extension.  By default this will be a left+right shift of the
1922      appropriate size.  But we may be able to eliminate one of them.  */
1923   sign_shift_up = sign_shift_dn = m_bitsize - bitsize;
1924
1925   if (STRICT_ALIGNMENT)
1926     {
1927       base = plus_constant (XEXP (op0, 0), bitpos / BITS_PER_UNIT);
1928       bitpos %= BITS_PER_UNIT;
1929
1930       /* We load two values to be concatenate.  There's an edge condition
1931          that bears notice -- an aligned value at the end of a page can
1932          only load one value lest we segfault.  So the two values we load
1933          are at "base & -size" and "(base + size - 1) & -size".  If base
1934          is unaligned, the addresses will be aligned and sequential; if
1935          base is aligned, the addresses will both be equal to base.  */
1936
1937       a1 = expand_simple_binop (Pmode, AND, force_operand (base, NULL),
1938                                 GEN_INT (-(HOST_WIDE_INT)m_size),
1939                                 NULL, true, OPTAB_LIB_WIDEN);
1940       mark_reg_pointer (a1, m_bitsize);
1941       v1 = gen_rtx_MEM (mode, a1);
1942       set_mem_align (v1, m_bitsize);
1943       v1 = force_reg (mode, validize_mem (v1));
1944
1945       a2 = plus_constant (base, GET_MODE_SIZE (mode) - 1);
1946       a2 = expand_simple_binop (Pmode, AND, force_operand (a2, NULL),
1947                                 GEN_INT (-(HOST_WIDE_INT)m_size),
1948                                 NULL, true, OPTAB_LIB_WIDEN);
1949       v2 = gen_rtx_MEM (mode, a2);
1950       set_mem_align (v2, m_bitsize);
1951       v2 = force_reg (mode, validize_mem (v2));
1952
1953       /* Combine these two values into a double-word value.  */
1954       if (m_bitsize == BITS_PER_WORD)
1955         {
1956           comb = gen_reg_rtx (dmode);
1957           emit_insn (gen_rtx_CLOBBER (VOIDmode, comb));
1958           emit_move_insn (gen_rtx_SUBREG (mode, comb, 0), v1);
1959           emit_move_insn (gen_rtx_SUBREG (mode, comb, m_size), v2);
1960         }
1961       else
1962         {
1963           if (BYTES_BIG_ENDIAN)
1964             comb = v1, v1 = v2, v2 = comb;
1965           v1 = convert_modes (dmode, mode, v1, true);
1966           if (v1 == NULL)
1967             goto fail;
1968           v2 = convert_modes (dmode, mode, v2, true);
1969           v2 = expand_simple_binop (dmode, ASHIFT, v2, GEN_INT (m_bitsize),
1970                                     NULL, true, OPTAB_LIB_WIDEN);
1971           if (v2 == NULL)
1972             goto fail;
1973           comb = expand_simple_binop (dmode, IOR, v1, v2, NULL,
1974                                       true, OPTAB_LIB_WIDEN);
1975           if (comb == NULL)
1976             goto fail;
1977         }
1978
1979       shift = expand_simple_binop (Pmode, AND, base, GEN_INT (m_size - 1),
1980                                    NULL, true, OPTAB_LIB_WIDEN);
1981       shift = expand_mult (Pmode, shift, GEN_INT (BITS_PER_UNIT), NULL, 1);
1982
1983       if (bitpos != 0)
1984         {
1985           if (sign_shift_up <= bitpos)
1986             bitpos -= sign_shift_up, sign_shift_up = 0;
1987           shift = expand_simple_binop (Pmode, PLUS, shift, GEN_INT (bitpos),
1988                                        NULL, true, OPTAB_LIB_WIDEN);
1989         }
1990     }
1991   else
1992     {
1993       unsigned HOST_WIDE_INT offset = bitpos / BITS_PER_UNIT;
1994       bitpos %= BITS_PER_UNIT;
1995
1996       /* When strict alignment is not required, we can just load directly
1997          from memory without masking.  If the remaining BITPOS offset is
1998          small enough, we may be able to do all operations in MODE as 
1999          opposed to DMODE.  */
2000       if (bitpos + bitsize <= m_bitsize)
2001         dmode = mode;
2002       comb = adjust_address (op0, dmode, offset);
2003
2004       if (sign_shift_up <= bitpos)
2005         bitpos -= sign_shift_up, sign_shift_up = 0;
2006       shift = GEN_INT (bitpos);
2007     }
2008
2009   /* Shift down the double-word such that the requested value is at bit 0.  */
2010   if (shift != const0_rtx)
2011     comb = expand_simple_binop (dmode, unsignedp ? LSHIFTRT : ASHIFTRT,
2012                                 comb, shift, NULL, unsignedp, OPTAB_LIB_WIDEN);
2013   if (comb == NULL)
2014     goto fail;
2015
2016   /* If the field exactly matches MODE, then all we need to do is return the
2017      lowpart.  Otherwise, shift to get the sign bits set properly.  */
2018   result = force_reg (mode, gen_lowpart (mode, comb));
2019
2020   if (sign_shift_up)
2021     result = expand_simple_binop (mode, ASHIFT, result,
2022                                   GEN_INT (sign_shift_up),
2023                                   NULL_RTX, 0, OPTAB_LIB_WIDEN);
2024   if (sign_shift_dn)
2025     result = expand_simple_binop (mode, unsignedp ? LSHIFTRT : ASHIFTRT,
2026                                   result, GEN_INT (sign_shift_dn),
2027                                   NULL_RTX, 0, OPTAB_LIB_WIDEN);
2028
2029   return result;
2030
2031  fail:
2032   delete_insns_since (start);
2033   return NULL;
2034 }
2035
2036 /* Extract a bit field that is split across two words
2037    and return an RTX for the result.
2038
2039    OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
2040    BITSIZE is the field width; BITPOS, position of its first bit, in the word.
2041    UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.  */
2042
2043 static rtx
2044 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
2045                          unsigned HOST_WIDE_INT bitpos, int unsignedp)
2046 {
2047   unsigned int unit;
2048   unsigned int bitsdone = 0;
2049   rtx result = NULL_RTX;
2050   int first = 1;
2051
2052   /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
2053      much at a time.  */
2054   if (REG_P (op0) || GET_CODE (op0) == SUBREG)
2055     unit = BITS_PER_WORD;
2056   else
2057     {
2058       unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
2059       if (0 && bitsize / unit > 2)
2060         {
2061           rtx tmp = extract_force_align_mem_bit_field (op0, bitsize, bitpos,
2062                                                        unsignedp);
2063           if (tmp)
2064             return tmp;
2065         }
2066     }
2067
2068   while (bitsdone < bitsize)
2069     {
2070       unsigned HOST_WIDE_INT thissize;
2071       rtx part, word;
2072       unsigned HOST_WIDE_INT thispos;
2073       unsigned HOST_WIDE_INT offset;
2074
2075       offset = (bitpos + bitsdone) / unit;
2076       thispos = (bitpos + bitsdone) % unit;
2077
2078       /* THISSIZE must not overrun a word boundary.  Otherwise,
2079          extract_fixed_bit_field will call us again, and we will mutually
2080          recurse forever.  */
2081       thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
2082       thissize = MIN (thissize, unit - thispos);
2083
2084       /* If OP0 is a register, then handle OFFSET here.
2085
2086          When handling multiword bitfields, extract_bit_field may pass
2087          down a word_mode SUBREG of a larger REG for a bitfield that actually
2088          crosses a word boundary.  Thus, for a SUBREG, we must find
2089          the current word starting from the base register.  */
2090       if (GET_CODE (op0) == SUBREG)
2091         {
2092           int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
2093           word = operand_subword_force (SUBREG_REG (op0), word_offset,
2094                                         GET_MODE (SUBREG_REG (op0)));
2095           offset = 0;
2096         }
2097       else if (REG_P (op0))
2098         {
2099           word = operand_subword_force (op0, offset, GET_MODE (op0));
2100           offset = 0;
2101         }
2102       else
2103         word = op0;
2104
2105       /* Extract the parts in bit-counting order,
2106          whose meaning is determined by BYTES_PER_UNIT.
2107          OFFSET is in UNITs, and UNIT is in bits.
2108          extract_fixed_bit_field wants offset in bytes.  */
2109       part = extract_fixed_bit_field (word_mode, word,
2110                                       offset * unit / BITS_PER_UNIT,
2111                                       thissize, thispos, 0, 1);
2112       bitsdone += thissize;
2113
2114       /* Shift this part into place for the result.  */
2115       if (BYTES_BIG_ENDIAN)
2116         {
2117           if (bitsize != bitsdone)
2118             part = expand_shift (LSHIFT_EXPR, word_mode, part,
2119                                  build_int_cst (NULL_TREE, bitsize - bitsdone),
2120                                  0, 1);
2121         }
2122       else
2123         {
2124           if (bitsdone != thissize)
2125             part = expand_shift (LSHIFT_EXPR, word_mode, part,
2126                                  build_int_cst (NULL_TREE,
2127                                                 bitsdone - thissize), 0, 1);
2128         }
2129
2130       if (first)
2131         result = part;
2132       else
2133         /* Combine the parts with bitwise or.  This works
2134            because we extracted each part as an unsigned bit field.  */
2135         result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
2136                                OPTAB_LIB_WIDEN);
2137
2138       first = 0;
2139     }
2140
2141   /* Unsigned bit field: we are done.  */
2142   if (unsignedp)
2143     return result;
2144   /* Signed bit field: sign-extend with two arithmetic shifts.  */
2145   result = expand_shift (LSHIFT_EXPR, word_mode, result,
2146                          build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize),
2147                          NULL_RTX, 0);
2148   return expand_shift (RSHIFT_EXPR, word_mode, result,
2149                        build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize),
2150                        NULL_RTX, 0);
2151 }
2152 \f
2153 /* Add INC into TARGET.  */
2154
2155 void
2156 expand_inc (rtx target, rtx inc)
2157 {
2158   rtx value = expand_binop (GET_MODE (target), add_optab,
2159                             target, inc,
2160                             target, 0, OPTAB_LIB_WIDEN);
2161   if (value != target)
2162     emit_move_insn (target, value);
2163 }
2164
2165 /* Subtract DEC from TARGET.  */
2166
2167 void
2168 expand_dec (rtx target, rtx dec)
2169 {
2170   rtx value = expand_binop (GET_MODE (target), sub_optab,
2171                             target, dec,
2172                             target, 0, OPTAB_LIB_WIDEN);
2173   if (value != target)
2174     emit_move_insn (target, value);
2175 }
2176 \f
2177 /* Output a shift instruction for expression code CODE,
2178    with SHIFTED being the rtx for the value to shift,
2179    and AMOUNT the tree for the amount to shift by.
2180    Store the result in the rtx TARGET, if that is convenient.
2181    If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2182    Return the rtx for where the value is.  */
2183
2184 rtx
2185 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
2186               tree amount, rtx target, int unsignedp)
2187 {
2188   rtx op1, temp = 0;
2189   int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2190   int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2191   int try;
2192
2193   /* Previously detected shift-counts computed by NEGATE_EXPR
2194      and shifted in the other direction; but that does not work
2195      on all machines.  */
2196
2197   op1 = expand_normal (amount);
2198
2199   if (SHIFT_COUNT_TRUNCATED)
2200     {
2201       if (GET_CODE (op1) == CONST_INT
2202           && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2203               (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
2204         op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2205                        % GET_MODE_BITSIZE (mode));
2206       else if (GET_CODE (op1) == SUBREG
2207                && subreg_lowpart_p (op1))
2208         op1 = SUBREG_REG (op1);
2209     }
2210
2211   if (op1 == const0_rtx)
2212     return shifted;
2213
2214   /* Check whether its cheaper to implement a left shift by a constant
2215      bit count by a sequence of additions.  */
2216   if (code == LSHIFT_EXPR
2217       && GET_CODE (op1) == CONST_INT
2218       && INTVAL (op1) > 0
2219       && INTVAL (op1) < GET_MODE_BITSIZE (mode)
2220       && shift_cost[mode][INTVAL (op1)] > INTVAL (op1) * add_cost[mode])
2221     {
2222       int i;
2223       for (i = 0; i < INTVAL (op1); i++)
2224         {
2225           temp = force_reg (mode, shifted);
2226           shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2227                                   unsignedp, OPTAB_LIB_WIDEN);
2228         }
2229       return shifted;
2230     }
2231
2232   for (try = 0; temp == 0 && try < 3; try++)
2233     {
2234       enum optab_methods methods;
2235
2236       if (try == 0)
2237         methods = OPTAB_DIRECT;
2238       else if (try == 1)
2239         methods = OPTAB_WIDEN;
2240       else
2241         methods = OPTAB_LIB_WIDEN;
2242
2243       if (rotate)
2244         {
2245           /* Widening does not work for rotation.  */
2246           if (methods == OPTAB_WIDEN)
2247             continue;
2248           else if (methods == OPTAB_LIB_WIDEN)
2249             {
2250               /* If we have been unable to open-code this by a rotation,
2251                  do it as the IOR of two shifts.  I.e., to rotate A
2252                  by N bits, compute (A << N) | ((unsigned) A >> (C - N))
2253                  where C is the bitsize of A.
2254
2255                  It is theoretically possible that the target machine might
2256                  not be able to perform either shift and hence we would
2257                  be making two libcalls rather than just the one for the
2258                  shift (similarly if IOR could not be done).  We will allow
2259                  this extremely unlikely lossage to avoid complicating the
2260                  code below.  */
2261
2262               rtx subtarget = target == shifted ? 0 : target;
2263               rtx temp1;
2264               tree type = TREE_TYPE (amount);
2265               tree new_amount = make_tree (type, op1);
2266               tree other_amount
2267                 = fold_build2 (MINUS_EXPR, type,
2268                                build_int_cst (type, GET_MODE_BITSIZE (mode)),
2269                                amount);
2270
2271               shifted = force_reg (mode, shifted);
2272
2273               temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2274                                    mode, shifted, new_amount, 0, 1);
2275               temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2276                                     mode, shifted, other_amount, subtarget, 1);
2277               return expand_binop (mode, ior_optab, temp, temp1, target,
2278                                    unsignedp, methods);
2279             }
2280
2281           temp = expand_binop (mode,
2282                                left ? rotl_optab : rotr_optab,
2283                                shifted, op1, target, unsignedp, methods);
2284         }
2285       else if (unsignedp)
2286         temp = expand_binop (mode,
2287                              left ? ashl_optab : lshr_optab,
2288                              shifted, op1, target, unsignedp, methods);
2289
2290       /* Do arithmetic shifts.
2291          Also, if we are going to widen the operand, we can just as well
2292          use an arithmetic right-shift instead of a logical one.  */
2293       if (temp == 0 && ! rotate
2294           && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2295         {
2296           enum optab_methods methods1 = methods;
2297
2298           /* If trying to widen a log shift to an arithmetic shift,
2299              don't accept an arithmetic shift of the same size.  */
2300           if (unsignedp)
2301             methods1 = OPTAB_MUST_WIDEN;
2302
2303           /* Arithmetic shift */
2304
2305           temp = expand_binop (mode,
2306                                left ? ashl_optab : ashr_optab,
2307                                shifted, op1, target, unsignedp, methods1);
2308         }
2309
2310       /* We used to try extzv here for logical right shifts, but that was
2311          only useful for one machine, the VAX, and caused poor code
2312          generation there for lshrdi3, so the code was deleted and a
2313          define_expand for lshrsi3 was added to vax.md.  */
2314     }
2315
2316   gcc_assert (temp);
2317   return temp;
2318 }
2319 \f
2320 enum alg_code {
2321   alg_unknown,
2322   alg_zero,
2323   alg_m, alg_shift,
2324   alg_add_t_m2,
2325   alg_sub_t_m2,
2326   alg_add_factor,
2327   alg_sub_factor,
2328   alg_add_t2_m,
2329   alg_sub_t2_m,
2330   alg_impossible
2331 };
2332
2333 /* This structure holds the "cost" of a multiply sequence.  The
2334    "cost" field holds the total rtx_cost of every operator in the
2335    synthetic multiplication sequence, hence cost(a op b) is defined
2336    as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero.
2337    The "latency" field holds the minimum possible latency of the
2338    synthetic multiply, on a hypothetical infinitely parallel CPU.
2339    This is the critical path, or the maximum height, of the expression
2340    tree which is the sum of rtx_costs on the most expensive path from
2341    any leaf to the root.  Hence latency(a op b) is defined as zero for
2342    leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise.  */
2343
2344 struct mult_cost {
2345   short cost;     /* Total rtx_cost of the multiplication sequence.  */
2346   short latency;  /* The latency of the multiplication sequence.  */
2347 };
2348
2349 /* This macro is used to compare a pointer to a mult_cost against an
2350    single integer "rtx_cost" value.  This is equivalent to the macro
2351    CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}.  */
2352 #define MULT_COST_LESS(X,Y) ((X)->cost < (Y)    \
2353                              || ((X)->cost == (Y) && (X)->latency < (Y)))
2354
2355 /* This macro is used to compare two pointers to mult_costs against
2356    each other.  The macro returns true if X is cheaper than Y.
2357    Currently, the cheaper of two mult_costs is the one with the
2358    lower "cost".  If "cost"s are tied, the lower latency is cheaper.  */
2359 #define CHEAPER_MULT_COST(X,Y)  ((X)->cost < (Y)->cost          \
2360                                  || ((X)->cost == (Y)->cost     \
2361                                      && (X)->latency < (Y)->latency))
2362
2363 /* This structure records a sequence of operations.
2364    `ops' is the number of operations recorded.
2365    `cost' is their total cost.
2366    The operations are stored in `op' and the corresponding
2367    logarithms of the integer coefficients in `log'.
2368
2369    These are the operations:
2370    alg_zero             total := 0;
2371    alg_m                total := multiplicand;
2372    alg_shift            total := total * coeff
2373    alg_add_t_m2         total := total + multiplicand * coeff;
2374    alg_sub_t_m2         total := total - multiplicand * coeff;
2375    alg_add_factor       total := total * coeff + total;
2376    alg_sub_factor       total := total * coeff - total;
2377    alg_add_t2_m         total := total * coeff + multiplicand;
2378    alg_sub_t2_m         total := total * coeff - multiplicand;
2379
2380    The first operand must be either alg_zero or alg_m.  */
2381
2382 struct algorithm
2383 {
2384   struct mult_cost cost;
2385   short ops;
2386   /* The size of the OP and LOG fields are not directly related to the
2387      word size, but the worst-case algorithms will be if we have few
2388      consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2389      In that case we will generate shift-by-2, add, shift-by-2, add,...,
2390      in total wordsize operations.  */
2391   enum alg_code op[MAX_BITS_PER_WORD];
2392   char log[MAX_BITS_PER_WORD];
2393 };
2394
2395 /* The entry for our multiplication cache/hash table.  */
2396 struct alg_hash_entry {
2397   /* The number we are multiplying by.  */
2398   unsigned int t;
2399
2400   /* The mode in which we are multiplying something by T.  */
2401   enum machine_mode mode;
2402
2403   /* The best multiplication algorithm for t.  */
2404   enum alg_code alg;
2405
2406   /* The cost of multiplication if ALG_CODE is not alg_impossible.
2407      Otherwise, the cost within which multiplication by T is
2408      impossible.  */
2409   struct mult_cost cost;
2410 };
2411
2412 /* The number of cache/hash entries.  */
2413 #define NUM_ALG_HASH_ENTRIES 307
2414
2415 /* Each entry of ALG_HASH caches alg_code for some integer.  This is
2416    actually a hash table.  If we have a collision, that the older
2417    entry is kicked out.  */
2418 static struct alg_hash_entry alg_hash[NUM_ALG_HASH_ENTRIES];
2419
2420 /* Indicates the type of fixup needed after a constant multiplication.
2421    BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2422    the result should be negated, and ADD_VARIANT means that the
2423    multiplicand should be added to the result.  */
2424 enum mult_variant {basic_variant, negate_variant, add_variant};
2425
2426 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2427                         const struct mult_cost *, enum machine_mode mode);
2428 static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT,
2429                                  struct algorithm *, enum mult_variant *, int);
2430 static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx,
2431                               const struct algorithm *, enum mult_variant);
2432 static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int,
2433                                                  int, rtx *, int *, int *);
2434 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2435 static rtx extract_high_half (enum machine_mode, rtx);
2436 static rtx expand_mult_highpart (enum machine_mode, rtx, rtx, rtx, int, int);
2437 static rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx,
2438                                        int, int);
2439 /* Compute and return the best algorithm for multiplying by T.
2440    The algorithm must cost less than cost_limit
2441    If retval.cost >= COST_LIMIT, no algorithm was found and all
2442    other field of the returned struct are undefined.
2443    MODE is the machine mode of the multiplication.  */
2444
2445 static void
2446 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2447             const struct mult_cost *cost_limit, enum machine_mode mode)
2448 {
2449   int m;
2450   struct algorithm *alg_in, *best_alg;
2451   struct mult_cost best_cost;
2452   struct mult_cost new_limit;
2453   int op_cost, op_latency;
2454   unsigned HOST_WIDE_INT q;
2455   int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
2456   int hash_index;
2457   bool cache_hit = false;
2458   enum alg_code cache_alg = alg_zero;
2459
2460   /* Indicate that no algorithm is yet found.  If no algorithm
2461      is found, this value will be returned and indicate failure.  */
2462   alg_out->cost.cost = cost_limit->cost + 1;
2463   alg_out->cost.latency = cost_limit->latency + 1;
2464
2465   if (cost_limit->cost < 0
2466       || (cost_limit->cost == 0 && cost_limit->latency <= 0))
2467     return;
2468
2469   /* Restrict the bits of "t" to the multiplication's mode.  */
2470   t &= GET_MODE_MASK (mode);
2471
2472   /* t == 1 can be done in zero cost.  */
2473   if (t == 1)
2474     {
2475       alg_out->ops = 1;
2476       alg_out->cost.cost = 0;
2477       alg_out->cost.latency = 0;
2478       alg_out->op[0] = alg_m;
2479       return;
2480     }
2481
2482   /* t == 0 sometimes has a cost.  If it does and it exceeds our limit,
2483      fail now.  */
2484   if (t == 0)
2485     {
2486       if (MULT_COST_LESS (cost_limit, zero_cost))
2487         return;
2488       else
2489         {
2490           alg_out->ops = 1;
2491           alg_out->cost.cost = zero_cost;
2492           alg_out->cost.latency = zero_cost;
2493           alg_out->op[0] = alg_zero;
2494           return;
2495         }
2496     }
2497
2498   /* We'll be needing a couple extra algorithm structures now.  */
2499
2500   alg_in = alloca (sizeof (struct algorithm));
2501   best_alg = alloca (sizeof (struct algorithm));
2502   best_cost = *cost_limit;
2503
2504   /* Compute the hash index.  */
2505   hash_index = (t ^ (unsigned int) mode) % NUM_ALG_HASH_ENTRIES;
2506
2507   /* See if we already know what to do for T.  */
2508   if (alg_hash[hash_index].t == t
2509       && alg_hash[hash_index].mode == mode
2510       && alg_hash[hash_index].alg != alg_unknown)
2511     {
2512       cache_alg = alg_hash[hash_index].alg;
2513
2514       if (cache_alg == alg_impossible)
2515         {
2516           /* The cache tells us that it's impossible to synthesize
2517              multiplication by T within alg_hash[hash_index].cost.  */
2518           if (!CHEAPER_MULT_COST (&alg_hash[hash_index].cost, cost_limit))
2519             /* COST_LIMIT is at least as restrictive as the one
2520                recorded in the hash table, in which case we have no
2521                hope of synthesizing a multiplication.  Just
2522                return.  */
2523             return;
2524
2525           /* If we get here, COST_LIMIT is less restrictive than the
2526              one recorded in the hash table, so we may be able to
2527              synthesize a multiplication.  Proceed as if we didn't
2528              have the cache entry.  */
2529         }
2530       else
2531         {
2532           if (CHEAPER_MULT_COST (cost_limit, &alg_hash[hash_index].cost))
2533             /* The cached algorithm shows that this multiplication
2534                requires more cost than COST_LIMIT.  Just return.  This
2535                way, we don't clobber this cache entry with
2536                alg_impossible but retain useful information.  */
2537             return;
2538
2539           cache_hit = true;
2540
2541           switch (cache_alg)
2542             {
2543             case alg_shift:
2544               goto do_alg_shift;
2545
2546             case alg_add_t_m2:
2547             case alg_sub_t_m2:
2548               goto do_alg_addsub_t_m2;
2549
2550             case alg_add_factor:
2551             case alg_sub_factor:
2552               goto do_alg_addsub_factor;
2553
2554             case alg_add_t2_m:
2555               goto do_alg_add_t2_m;
2556
2557             case alg_sub_t2_m:
2558               goto do_alg_sub_t2_m;
2559
2560             default:
2561               gcc_unreachable ();
2562             }
2563         }
2564     }
2565
2566   /* If we have a group of zero bits at the low-order part of T, try
2567      multiplying by the remaining bits and then doing a shift.  */
2568
2569   if ((t & 1) == 0)
2570     {
2571     do_alg_shift:
2572       m = floor_log2 (t & -t);  /* m = number of low zero bits */
2573       if (m < maxm)
2574         {
2575           q = t >> m;
2576           /* The function expand_shift will choose between a shift and
2577              a sequence of additions, so the observed cost is given as
2578              MIN (m * add_cost[mode], shift_cost[mode][m]).  */
2579           op_cost = m * add_cost[mode];
2580           if (shift_cost[mode][m] < op_cost)
2581             op_cost = shift_cost[mode][m];
2582           new_limit.cost = best_cost.cost - op_cost;
2583           new_limit.latency = best_cost.latency - op_cost;
2584           synth_mult (alg_in, q, &new_limit, mode);
2585
2586           alg_in->cost.cost += op_cost;
2587           alg_in->cost.latency += op_cost;
2588           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2589             {
2590               struct algorithm *x;
2591               best_cost = alg_in->cost;
2592               x = alg_in, alg_in = best_alg, best_alg = x;
2593               best_alg->log[best_alg->ops] = m;
2594               best_alg->op[best_alg->ops] = alg_shift;
2595             }
2596         }
2597       if (cache_hit)
2598         goto done;
2599     }
2600
2601   /* If we have an odd number, add or subtract one.  */
2602   if ((t & 1) != 0)
2603     {
2604       unsigned HOST_WIDE_INT w;
2605
2606     do_alg_addsub_t_m2:
2607       for (w = 1; (w & t) != 0; w <<= 1)
2608         ;
2609       /* If T was -1, then W will be zero after the loop.  This is another
2610          case where T ends with ...111.  Handling this with (T + 1) and
2611          subtract 1 produces slightly better code and results in algorithm
2612          selection much faster than treating it like the ...0111 case
2613          below.  */
2614       if (w == 0
2615           || (w > 2
2616               /* Reject the case where t is 3.
2617                  Thus we prefer addition in that case.  */
2618               && t != 3))
2619         {
2620           /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */
2621
2622           op_cost = add_cost[mode];
2623           new_limit.cost = best_cost.cost - op_cost;
2624           new_limit.latency = best_cost.latency - op_cost;
2625           synth_mult (alg_in, t + 1, &new_limit, mode);
2626
2627           alg_in->cost.cost += op_cost;
2628           alg_in->cost.latency += op_cost;
2629           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2630             {
2631               struct algorithm *x;
2632               best_cost = alg_in->cost;
2633               x = alg_in, alg_in = best_alg, best_alg = x;
2634               best_alg->log[best_alg->ops] = 0;
2635               best_alg->op[best_alg->ops] = alg_sub_t_m2;
2636             }
2637         }
2638       else
2639         {
2640           /* T ends with ...01 or ...011.  Multiply by (T - 1) and add 1.  */
2641
2642           op_cost = add_cost[mode];
2643           new_limit.cost = best_cost.cost - op_cost;
2644           new_limit.latency = best_cost.latency - op_cost;
2645           synth_mult (alg_in, t - 1, &new_limit, mode);
2646
2647           alg_in->cost.cost += op_cost;
2648           alg_in->cost.latency += op_cost;
2649           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2650             {
2651               struct algorithm *x;
2652               best_cost = alg_in->cost;
2653               x = alg_in, alg_in = best_alg, best_alg = x;
2654               best_alg->log[best_alg->ops] = 0;
2655               best_alg->op[best_alg->ops] = alg_add_t_m2;
2656             }
2657         }
2658       if (cache_hit)
2659         goto done;
2660     }
2661
2662   /* Look for factors of t of the form
2663      t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2664      If we find such a factor, we can multiply by t using an algorithm that
2665      multiplies by q, shift the result by m and add/subtract it to itself.
2666
2667      We search for large factors first and loop down, even if large factors
2668      are less probable than small; if we find a large factor we will find a
2669      good sequence quickly, and therefore be able to prune (by decreasing
2670      COST_LIMIT) the search.  */
2671
2672  do_alg_addsub_factor:
2673   for (m = floor_log2 (t - 1); m >= 2; m--)
2674     {
2675       unsigned HOST_WIDE_INT d;
2676
2677       d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2678       if (t % d == 0 && t > d && m < maxm
2679           && (!cache_hit || cache_alg == alg_add_factor))
2680         {
2681           /* If the target has a cheap shift-and-add instruction use
2682              that in preference to a shift insn followed by an add insn.
2683              Assume that the shift-and-add is "atomic" with a latency
2684              equal to its cost, otherwise assume that on superscalar
2685              hardware the shift may be executed concurrently with the
2686              earlier steps in the algorithm.  */
2687           op_cost = add_cost[mode] + shift_cost[mode][m];
2688           if (shiftadd_cost[mode][m] < op_cost)
2689             {
2690               op_cost = shiftadd_cost[mode][m];
2691               op_latency = op_cost;
2692             }
2693           else
2694             op_latency = add_cost[mode];
2695
2696           new_limit.cost = best_cost.cost - op_cost;
2697           new_limit.latency = best_cost.latency - op_latency;
2698           synth_mult (alg_in, t / d, &new_limit, mode);
2699
2700           alg_in->cost.cost += op_cost;
2701           alg_in->cost.latency += op_latency;
2702           if (alg_in->cost.latency < op_cost)
2703             alg_in->cost.latency = op_cost;
2704           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2705             {
2706               struct algorithm *x;
2707               best_cost = alg_in->cost;
2708               x = alg_in, alg_in = best_alg, best_alg = x;
2709               best_alg->log[best_alg->ops] = m;
2710               best_alg->op[best_alg->ops] = alg_add_factor;
2711             }
2712           /* Other factors will have been taken care of in the recursion.  */
2713           break;
2714         }
2715
2716       d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2717       if (t % d == 0 && t > d && m < maxm
2718           && (!cache_hit || cache_alg == alg_sub_factor))
2719         {
2720           /* If the target has a cheap shift-and-subtract insn use
2721              that in preference to a shift insn followed by a sub insn.
2722              Assume that the shift-and-sub is "atomic" with a latency
2723              equal to it's cost, otherwise assume that on superscalar
2724              hardware the shift may be executed concurrently with the
2725              earlier steps in the algorithm.  */
2726           op_cost = add_cost[mode] + shift_cost[mode][m];
2727           if (shiftsub_cost[mode][m] < op_cost)
2728             {
2729               op_cost = shiftsub_cost[mode][m];
2730               op_latency = op_cost;
2731             }
2732           else
2733             op_latency = add_cost[mode];
2734
2735           new_limit.cost = best_cost.cost - op_cost;
2736           new_limit.latency = best_cost.latency - op_latency;
2737           synth_mult (alg_in, t / d, &new_limit, mode);
2738
2739           alg_in->cost.cost += op_cost;
2740           alg_in->cost.latency += op_latency;
2741           if (alg_in->cost.latency < op_cost)
2742             alg_in->cost.latency = op_cost;
2743           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2744             {
2745               struct algorithm *x;
2746               best_cost = alg_in->cost;
2747               x = alg_in, alg_in = best_alg, best_alg = x;
2748               best_alg->log[best_alg->ops] = m;
2749               best_alg->op[best_alg->ops] = alg_sub_factor;
2750             }
2751           break;
2752         }
2753     }
2754   if (cache_hit)
2755     goto done;
2756
2757   /* Try shift-and-add (load effective address) instructions,
2758      i.e. do a*3, a*5, a*9.  */
2759   if ((t & 1) != 0)
2760     {
2761     do_alg_add_t2_m:
2762       q = t - 1;
2763       q = q & -q;
2764       m = exact_log2 (q);
2765       if (m >= 0 && m < maxm)
2766         {
2767           op_cost = shiftadd_cost[mode][m];
2768           new_limit.cost = best_cost.cost - op_cost;
2769           new_limit.latency = best_cost.latency - op_cost;
2770           synth_mult (alg_in, (t - 1) >> m, &new_limit, mode);
2771
2772           alg_in->cost.cost += op_cost;
2773           alg_in->cost.latency += op_cost;
2774           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2775             {
2776               struct algorithm *x;
2777               best_cost = alg_in->cost;
2778               x = alg_in, alg_in = best_alg, best_alg = x;
2779               best_alg->log[best_alg->ops] = m;
2780               best_alg->op[best_alg->ops] = alg_add_t2_m;
2781             }
2782         }
2783       if (cache_hit)
2784         goto done;
2785
2786     do_alg_sub_t2_m:
2787       q = t + 1;
2788       q = q & -q;
2789       m = exact_log2 (q);
2790       if (m >= 0 && m < maxm)
2791         {
2792           op_cost = shiftsub_cost[mode][m];
2793           new_limit.cost = best_cost.cost - op_cost;
2794           new_limit.latency = best_cost.latency - op_cost;
2795           synth_mult (alg_in, (t + 1) >> m, &new_limit, mode);
2796
2797           alg_in->cost.cost += op_cost;
2798           alg_in->cost.latency += op_cost;
2799           if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2800             {
2801               struct algorithm *x;
2802               best_cost = alg_in->cost;
2803               x = alg_in, alg_in = best_alg, best_alg = x;
2804               best_alg->log[best_alg->ops] = m;
2805               best_alg->op[best_alg->ops] = alg_sub_t2_m;
2806             }
2807         }
2808       if (cache_hit)
2809         goto done;
2810     }
2811
2812  done:
2813   /* If best_cost has not decreased, we have not found any algorithm.  */
2814   if (!CHEAPER_MULT_COST (&best_cost, cost_limit))
2815     {
2816       /* We failed to find an algorithm.  Record alg_impossible for
2817          this case (that is, <T, MODE, COST_LIMIT>) so that next time
2818          we are asked to find an algorithm for T within the same or
2819          lower COST_LIMIT, we can immediately return to the
2820          caller.  */
2821       alg_hash[hash_index].t = t;
2822       alg_hash[hash_index].mode = mode;
2823       alg_hash[hash_index].alg = alg_impossible;
2824       alg_hash[hash_index].cost = *cost_limit;
2825       return;
2826     }
2827
2828   /* Cache the result.  */
2829   if (!cache_hit)
2830     {
2831       alg_hash[hash_index].t = t;
2832       alg_hash[hash_index].mode = mode;
2833       alg_hash[hash_index].alg = best_alg->op[best_alg->ops];
2834       alg_hash[hash_index].cost.cost = best_cost.cost;
2835       alg_hash[hash_index].cost.latency = best_cost.latency;
2836     }
2837
2838   /* If we are getting a too long sequence for `struct algorithm'
2839      to record, make this search fail.  */
2840   if (best_alg->ops == MAX_BITS_PER_WORD)
2841     return;
2842
2843   /* Copy the algorithm from temporary space to the space at alg_out.
2844      We avoid using structure assignment because the majority of
2845      best_alg is normally undefined, and this is a critical function.  */
2846   alg_out->ops = best_alg->ops + 1;
2847   alg_out->cost = best_cost;
2848   memcpy (alg_out->op, best_alg->op,
2849           alg_out->ops * sizeof *alg_out->op);
2850   memcpy (alg_out->log, best_alg->log,
2851           alg_out->ops * sizeof *alg_out->log);
2852 }
2853 \f
2854 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2855    Try three variations:
2856
2857        - a shift/add sequence based on VAL itself
2858        - a shift/add sequence based on -VAL, followed by a negation
2859        - a shift/add sequence based on VAL - 1, followed by an addition.
2860
2861    Return true if the cheapest of these cost less than MULT_COST,
2862    describing the algorithm in *ALG and final fixup in *VARIANT.  */
2863
2864 static bool
2865 choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val,
2866                      struct algorithm *alg, enum mult_variant *variant,
2867                      int mult_cost)
2868 {
2869   struct algorithm alg2;
2870   struct mult_cost limit;
2871   int op_cost;
2872
2873   /* Fail quickly for impossible bounds.  */
2874   if (mult_cost < 0)
2875     return false;
2876
2877   /* Ensure that mult_cost provides a reasonable upper bound.
2878      Any constant multiplication can be performed with less
2879      than 2 * bits additions.  */
2880   op_cost = 2 * GET_MODE_BITSIZE (mode) * add_cost[mode];
2881   if (mult_cost > op_cost)
2882     mult_cost = op_cost;
2883
2884   *variant = basic_variant;
2885   limit.cost = mult_cost;
2886   limit.latency = mult_cost;
2887   synth_mult (alg, val, &limit, mode);
2888
2889   /* This works only if the inverted value actually fits in an
2890      `unsigned int' */
2891   if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2892     {
2893       op_cost = neg_cost[mode];
2894       if (MULT_COST_LESS (&alg->cost, mult_cost))
2895         {
2896           limit.cost = alg->cost.cost - op_cost;
2897           limit.latency = alg->cost.latency - op_cost;
2898         }
2899       else
2900         {
2901           limit.cost = mult_cost - op_cost;
2902           limit.latency = mult_cost - op_cost;
2903         }
2904
2905       synth_mult (&alg2, -val, &limit, mode);
2906       alg2.cost.cost += op_cost;
2907       alg2.cost.latency += op_cost;
2908       if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2909         *alg = alg2, *variant = negate_variant;
2910     }
2911
2912   /* This proves very useful for division-by-constant.  */
2913   op_cost = add_cost[mode];
2914   if (MULT_COST_LESS (&alg->cost, mult_cost))
2915     {
2916       limit.cost = alg->cost.cost - op_cost;
2917       limit.latency = alg->cost.latency - op_cost;
2918     }
2919   else
2920     {
2921       limit.cost = mult_cost - op_cost;
2922       limit.latency = mult_cost - op_cost;
2923     }
2924
2925   synth_mult (&alg2, val - 1, &limit, mode);
2926   alg2.cost.cost += op_cost;
2927   alg2.cost.latency += op_cost;
2928   if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2929     *alg = alg2, *variant = add_variant;
2930
2931   return MULT_COST_LESS (&alg->cost, mult_cost);
2932 }
2933
2934 /* A subroutine of expand_mult, used for constant multiplications.
2935    Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2936    convenient.  Use the shift/add sequence described by ALG and apply
2937    the final fixup specified by VARIANT.  */
2938
2939 static rtx
2940 expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val,
2941                    rtx target, const struct algorithm *alg,
2942                    enum mult_variant variant)
2943 {
2944   HOST_WIDE_INT val_so_far;
2945   rtx insn, accum, tem;
2946   int opno;
2947   enum machine_mode nmode;
2948
2949   /* Avoid referencing memory over and over.
2950      For speed, but also for correctness when mem is volatile.  */
2951   if (MEM_P (op0))
2952     op0 = force_reg (mode, op0);
2953
2954   /* ACCUM starts out either as OP0 or as a zero, depending on
2955      the first operation.  */
2956
2957   if (alg->op[0] == alg_zero)
2958     {
2959       accum = copy_to_mode_reg (mode, const0_rtx);
2960       val_so_far = 0;
2961     }
2962   else if (alg->op[0] == alg_m)
2963     {
2964       accum = copy_to_mode_reg (mode, op0);
2965       val_so_far = 1;
2966     }
2967   else
2968     gcc_unreachable ();
2969
2970   for (opno = 1; opno < alg->ops; opno++)
2971     {
2972       int log = alg->log[opno];
2973       rtx shift_subtarget = optimize ? 0 : accum;
2974       rtx add_target
2975         = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2976            && !optimize)
2977           ? target : 0;
2978       rtx accum_target = optimize ? 0 : accum;
2979
2980       switch (alg->op[opno])
2981         {
2982         case alg_shift:
2983           accum = expand_shift (LSHIFT_EXPR, mode, accum,
2984                                 build_int_cst (NULL_TREE, log),
2985                                 NULL_RTX, 0);
2986           val_so_far <<= log;
2987           break;
2988
2989         case alg_add_t_m2:
2990           tem = expand_shift (LSHIFT_EXPR, mode, op0,
2991                               build_int_cst (NULL_TREE, log),
2992                               NULL_RTX, 0);
2993           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2994                                  add_target ? add_target : accum_target);
2995           val_so_far += (HOST_WIDE_INT) 1 << log;
2996           break;
2997
2998         case alg_sub_t_m2:
2999           tem = expand_shift (LSHIFT_EXPR, mode, op0,
3000                               build_int_cst (NULL_TREE, log),
3001                               NULL_RTX, 0);
3002           accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
3003                                  add_target ? add_target : accum_target);
3004           val_so_far -= (HOST_WIDE_INT) 1 << log;
3005           break;
3006
3007         case alg_add_t2_m:
3008           accum = expand_shift (LSHIFT_EXPR, mode, accum,
3009                                 build_int_cst (NULL_TREE, log),
3010                                 shift_subtarget,
3011                                 0);
3012           accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
3013                                  add_target ? add_target : accum_target);
3014           val_so_far = (val_so_far << log) + 1;
3015           break;
3016
3017         case alg_sub_t2_m:
3018           accum = expand_shift (LSHIFT_EXPR, mode, accum,
3019                                 build_int_cst (NULL_TREE, log),
3020                                 shift_subtarget, 0);
3021           accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
3022                                  add_target ? add_target : accum_target);
3023           val_so_far = (val_so_far << log) - 1;
3024           break;
3025
3026         case alg_add_factor:
3027           tem = expand_shift (LSHIFT_EXPR, mode, accum,
3028                               build_int_cst (NULL_TREE, log),
3029                               NULL_RTX, 0);
3030           accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3031                                  add_target ? add_target : accum_target);
3032           val_so_far += val_so_far << log;
3033           break;
3034
3035         case alg_sub_factor:
3036           tem = expand_shift (LSHIFT_EXPR, mode, accum,
3037                               build_int_cst (NULL_TREE, log),
3038                               NULL_RTX, 0);
3039           accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
3040                                  (add_target
3041                                   ? add_target : (optimize ? 0 : tem)));
3042           val_so_far = (val_so_far << log) - val_so_far;
3043           break;
3044
3045         default:
3046           gcc_unreachable ();
3047         }
3048
3049       /* Write a REG_EQUAL note on the last insn so that we can cse
3050          multiplication sequences.  Note that if ACCUM is a SUBREG,
3051          we've set the inner register and must properly indicate
3052          that.  */
3053
3054       tem = op0, nmode = mode;
3055       if (GET_CODE (accum) == SUBREG)
3056         {
3057           nmode = GET_MODE (SUBREG_REG (accum));
3058           tem = gen_lowpart (nmode, op0);
3059         }
3060
3061       insn = get_last_insn ();
3062       set_unique_reg_note (insn, REG_EQUAL,
3063                            gen_rtx_MULT (nmode, tem, GEN_INT (val_so_far)));
3064     }
3065
3066   if (variant == negate_variant)
3067     {
3068       val_so_far = -val_so_far;
3069       accum = expand_unop (mode, neg_optab, accum, target, 0);
3070     }
3071   else if (variant == add_variant)
3072     {
3073       val_so_far = val_so_far + 1;
3074       accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
3075     }
3076
3077   /* Compare only the bits of val and val_so_far that are significant
3078      in the result mode, to avoid sign-/zero-extension confusion.  */
3079   val &= GET_MODE_MASK (mode);
3080   val_so_far &= GET_MODE_MASK (mode);
3081   gcc_assert (val == val_so_far);
3082
3083   return accum;
3084 }
3085
3086 /* Perform a multiplication and return an rtx for the result.
3087    MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3088    TARGET is a suggestion for where to store the result (an rtx).
3089
3090    We check specially for a constant integer as OP1.
3091    If you want this check for OP0 as well, then before calling
3092    you should swap the two operands if OP0 would be constant.  */
3093
3094 rtx
3095 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3096              int unsignedp)
3097 {
3098   enum mult_variant variant;
3099   struct algorithm algorithm;
3100   int max_cost;
3101
3102   /* Handling const0_rtx here allows us to use zero as a rogue value for
3103      coeff below.  */
3104   if (op1 == const0_rtx)
3105     return const0_rtx;
3106   if (op1 == const1_rtx)
3107     return op0;
3108   if (op1 == constm1_rtx)
3109     return expand_unop (mode,
3110                         GET_MODE_CLASS (mode) == MODE_INT
3111                         && !unsignedp && flag_trapv
3112                         ? negv_optab : neg_optab,
3113                         op0, target, 0);
3114
3115   /* These are the operations that are potentially turned into a sequence
3116      of shifts and additions.  */
3117   if (SCALAR_INT_MODE_P (mode)
3118       && (unsignedp || !flag_trapv))
3119     {
3120       HOST_WIDE_INT coeff = 0;
3121       rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3122
3123       /* synth_mult does an `unsigned int' multiply.  As long as the mode is
3124          less than or equal in size to `unsigned int' this doesn't matter.
3125          If the mode is larger than `unsigned int', then synth_mult works
3126          only if the constant value exactly fits in an `unsigned int' without
3127          any truncation.  This means that multiplying by negative values does
3128          not work; results are off by 2^32 on a 32 bit machine.  */
3129
3130       if (GET_CODE (op1) == CONST_INT)
3131         {
3132           /* Attempt to handle multiplication of DImode values by negative
3133              coefficients, by performing the multiplication by a positive
3134              multiplier and then inverting the result.  */
3135           if (INTVAL (op1) < 0
3136               && GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT)
3137             {
3138               /* Its safe to use -INTVAL (op1) even for INT_MIN, as the
3139                  result is interpreted as an unsigned coefficient.
3140                  Exclude cost of op0 from max_cost to match the cost
3141                  calculation of the synth_mult.  */
3142               max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET)
3143                          - neg_cost[mode];
3144               if (max_cost > 0
3145                   && choose_mult_variant (mode, -INTVAL (op1), &algorithm,
3146                                           &variant, max_cost))
3147                 {
3148                   rtx temp = expand_mult_const (mode, op0, -INTVAL (op1),
3149                                                 NULL_RTX, &algorithm,
3150                                                 variant);
3151                   return expand_unop (mode, neg_optab, temp, target, 0);
3152                 }
3153             }
3154           else coeff = INTVAL (op1);
3155         }
3156       else if (GET_CODE (op1) == CONST_DOUBLE)
3157         {
3158           /* If we are multiplying in DImode, it may still be a win
3159              to try to work with shifts and adds.  */
3160           if (CONST_DOUBLE_HIGH (op1) == 0)
3161             coeff = CONST_DOUBLE_LOW (op1);
3162           else if (CONST_DOUBLE_LOW (op1) == 0
3163                    && EXACT_POWER_OF_2_OR_ZERO_P (CONST_DOUBLE_HIGH (op1)))
3164             {
3165               int shift = floor_log2 (CONST_DOUBLE_HIGH (op1))
3166                           + HOST_BITS_PER_WIDE_INT;
3167               return expand_shift (LSHIFT_EXPR, mode, op0,
3168                                    build_int_cst (NULL_TREE, shift),
3169                                    target, unsignedp);
3170             }
3171         }
3172         
3173       /* We used to test optimize here, on the grounds that it's better to
3174          produce a smaller program when -O is not used.  But this causes
3175          such a terrible slowdown sometimes that it seems better to always
3176          use synth_mult.  */
3177       if (coeff != 0)
3178         {
3179           /* Special case powers of two.  */
3180           if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3181             return expand_shift (LSHIFT_EXPR, mode, op0,
3182                                  build_int_cst (NULL_TREE, floor_log2 (coeff)),
3183                                  target, unsignedp);
3184
3185           /* Exclude cost of op0 from max_cost to match the cost
3186              calculation of the synth_mult.  */
3187           max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET);
3188           if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3189                                    max_cost))
3190             return expand_mult_const (mode, op0, coeff, target,
3191                                       &algorithm, variant);
3192         }
3193     }
3194
3195   if (GET_CODE (op0) == CONST_DOUBLE)
3196     {
3197       rtx temp = op0;
3198       op0 = op1;
3199       op1 = temp;
3200     }
3201
3202   /* Expand x*2.0 as x+x.  */
3203   if (GET_CODE (op1) == CONST_DOUBLE
3204       && SCALAR_FLOAT_MODE_P (mode))
3205     {
3206       REAL_VALUE_TYPE d;
3207       REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
3208
3209       if (REAL_VALUES_EQUAL (d, dconst2))
3210         {
3211           op0 = force_reg (GET_MODE (op0), op0);
3212           return expand_binop (mode, add_optab, op0, op0,
3213                                target, unsignedp, OPTAB_LIB_WIDEN);
3214         }
3215     }
3216
3217   /* This used to use umul_optab if unsigned, but for non-widening multiply
3218      there is no difference between signed and unsigned.  */
3219   op0 = expand_binop (mode,
3220                       ! unsignedp
3221                       && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
3222                       ? smulv_optab : smul_optab,
3223                       op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
3224   gcc_assert (op0);
3225   return op0;
3226 }
3227 \f
3228 /* Return the smallest n such that 2**n >= X.  */
3229
3230 int
3231 ceil_log2 (unsigned HOST_WIDE_INT x)
3232 {
3233   return floor_log2 (x - 1) + 1;
3234 }
3235
3236 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
3237    replace division by D, and put the least significant N bits of the result
3238    in *MULTIPLIER_PTR and return the most significant bit.
3239
3240    The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
3241    needed precision is in PRECISION (should be <= N).
3242
3243    PRECISION should be as small as possible so this function can choose
3244    multiplier more freely.
3245
3246    The rounded-up logarithm of D is placed in *lgup_ptr.  A shift count that
3247    is to be used for a final right shift is placed in *POST_SHIFT_PTR.
3248
3249    Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
3250    where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier.  */
3251
3252 static
3253 unsigned HOST_WIDE_INT
3254 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
3255                    rtx *multiplier_ptr, int *post_shift_ptr, int *lgup_ptr)
3256 {
3257   HOST_WIDE_INT mhigh_hi, mlow_hi;
3258   unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
3259   int lgup, post_shift;
3260   int pow, pow2;
3261   unsigned HOST_WIDE_INT nl, dummy1;
3262   HOST_WIDE_INT nh, dummy2;
3263
3264   /* lgup = ceil(log2(divisor)); */
3265   lgup = ceil_log2 (d);
3266
3267   gcc_assert (lgup <= n);
3268
3269   pow = n + lgup;
3270   pow2 = n + lgup - precision;
3271
3272   /* We could handle this with some effort, but this case is much
3273      better handled directly with a scc insn, so rely on caller using
3274      that.  */
3275   gcc_assert (pow != 2 * HOST_BITS_PER_WIDE_INT);
3276
3277   /* mlow = 2^(N + lgup)/d */
3278  if (pow >= HOST_BITS_PER_WIDE_INT)
3279     {
3280       nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
3281       nl = 0;
3282     }
3283   else
3284     {
3285       nh = 0;
3286       nl = (unsigned HOST_WIDE_INT) 1 << pow;
3287     }
3288   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
3289                         &mlow_lo, &mlow_hi, &dummy1, &dummy2);
3290
3291   /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
3292   if (pow2 >= HOST_BITS_PER_WIDE_INT)
3293     nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
3294   else
3295     nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
3296   div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
3297                         &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
3298
3299   gcc_assert (!mhigh_hi || nh - d < d);
3300   gcc_assert (mhigh_hi <= 1 && mlow_hi <= 1);
3301   /* Assert that mlow < mhigh.  */
3302   gcc_assert (mlow_hi < mhigh_hi
3303               || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo));
3304
3305   /* If precision == N, then mlow, mhigh exceed 2^N
3306      (but they do not exceed 2^(N+1)).  */
3307
3308   /* Reduce to lowest terms.  */
3309   for (post_shift = lgup; post_shift > 0; post_shift--)
3310     {
3311       unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
3312       unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
3313       if (ml_lo >= mh_lo)
3314         break;
3315
3316       mlow_hi = 0;
3317       mlow_lo = ml_lo;
3318       mhigh_hi = 0;
3319       mhigh_lo = mh_lo;
3320     }
3321
3322   *post_shift_ptr = post_shift;
3323   *lgup_ptr = lgup;
3324   if (n < HOST_BITS_PER_WIDE_INT)
3325     {
3326       unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
3327       *multiplier_ptr = GEN_INT (mhigh_lo & mask);
3328       return mhigh_lo >= mask;
3329     }
3330   else
3331     {
3332       *multiplier_ptr = GEN_INT (mhigh_lo);
3333       return mhigh_hi;
3334     }
3335 }
3336
3337 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
3338    congruent to 1 (mod 2**N).  */
3339
3340 static unsigned HOST_WIDE_INT
3341 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
3342 {
3343   /* Solve x*y == 1 (mod 2^n), where x is odd.  Return y.  */
3344
3345   /* The algorithm notes that the choice y = x satisfies
3346      x*y == 1 mod 2^3, since x is assumed odd.
3347      Each iteration doubles the number of bits of significance in y.  */
3348
3349   unsigned HOST_WIDE_INT mask;
3350   unsigned HOST_WIDE_INT y = x;
3351   int nbit = 3;
3352
3353   mask = (n == HOST_BITS_PER_WIDE_INT
3354           ? ~(unsigned HOST_WIDE_INT) 0
3355           : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
3356
3357   while (nbit < n)
3358     {
3359       y = y * (2 - x*y) & mask;         /* Modulo 2^N */
3360       nbit *= 2;
3361     }
3362   return y;
3363 }
3364
3365 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
3366    flavor of OP0 and OP1.  ADJ_OPERAND is already the high half of the
3367    product OP0 x OP1.  If UNSIGNEDP is nonzero, adjust the signed product
3368    to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
3369    become signed.
3370
3371    The result is put in TARGET if that is convenient.
3372
3373    MODE is the mode of operation.  */
3374
3375 rtx
3376 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
3377                              rtx op1, rtx target, int unsignedp)
3378 {
3379   rtx tem;
3380   enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
3381
3382   tem = expand_shift (RSHIFT_EXPR, mode, op0,
3383                       build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1),
3384                       NULL_RTX, 0);
3385   tem = expand_and (mode, tem, op1, NULL_RTX);
3386   adj_operand
3387     = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3388                      adj_operand);
3389
3390   tem = expand_shift (RSHIFT_EXPR, mode, op1,
3391                       build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1),
3392                       NULL_RTX, 0);
3393   tem = expand_and (mode, tem, op0, NULL_RTX);
3394   target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3395                           target);
3396
3397   return target;
3398 }
3399
3400 /* Subroutine of expand_mult_highpart.  Return the MODE high part of OP.  */
3401
3402 static rtx
3403 extract_high_half (enum machine_mode mode, rtx op)
3404 {
3405   enum machine_mode wider_mode;
3406
3407   if (mode == word_mode)
3408     return gen_highpart (mode, op);
3409
3410   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3411
3412   wider_mode = GET_MODE_WIDER_MODE (mode);
3413   op = expand_shift (RSHIFT_EXPR, wider_mode, op,
3414                      build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode)), 0, 1);
3415   return convert_modes (mode, wider_mode, op, 0);
3416 }
3417
3418 /* Like expand_mult_highpart, but only consider using a multiplication
3419    optab.  OP1 is an rtx for the constant operand.  */
3420
3421 static rtx
3422 expand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1,
3423                             rtx target, int unsignedp, int max_cost)
3424 {
3425   rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
3426   enum machine_mode wider_mode;
3427   optab moptab;
3428   rtx tem;
3429   int size;
3430
3431   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3432
3433   wider_mode = GET_MODE_WIDER_MODE (mode);
3434   size = GET_MODE_BITSIZE (mode);
3435
3436   /* Firstly, try using a multiplication insn that only generates the needed
3437      high part of the product, and in the sign flavor of unsignedp.  */
3438   if (mul_highpart_cost[mode] < max_cost)
3439     {
3440       moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
3441       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3442                           unsignedp, OPTAB_DIRECT);
3443       if (tem)
3444         return tem;
3445     }
3446
3447   /* Secondly, same as above, but use sign flavor opposite of unsignedp.
3448      Need to adjust the result after the multiplication.  */
3449   if (size - 1 < BITS_PER_WORD
3450       && (mul_highpart_cost[mode] + 2 * shift_cost[mode][size-1]
3451           + 4 * add_cost[mode] < max_cost))
3452     {
3453       moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
3454       tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3455                           unsignedp, OPTAB_DIRECT);
3456       if (tem)
3457         /* We used the wrong signedness.  Adjust the result.  */
3458         return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3459                                             tem, unsignedp);
3460     }
3461
3462   /* Try widening multiplication.  */
3463   moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
3464   if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing
3465       && mul_widen_cost[wider_mode] < max_cost)
3466     {
3467       tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
3468                           unsignedp, OPTAB_WIDEN);
3469       if (tem)
3470         return extract_high_half (mode, tem);
3471     }
3472
3473   /* Try widening the mode and perform a non-widening multiplication.  */
3474   if (smul_optab->handlers[wider_mode].insn_code != CODE_FOR_nothing
3475       && size - 1 < BITS_PER_WORD
3476       && mul_cost[wider_mode] + shift_cost[mode][size-1] < max_cost)
3477     {
3478       rtx insns, wop0, wop1;
3479
3480       /* We need to widen the operands, for example to ensure the
3481          constant multiplier is correctly sign or zero extended.
3482          Use a sequence to clean-up any instructions emitted by
3483          the conversions if things don't work out.  */
3484       start_sequence ();
3485       wop0 = convert_modes (wider_mode, mode, op0, unsignedp);
3486       wop1 = convert_modes (wider_mode, mode, op1, unsignedp);
3487       tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0,
3488                           unsignedp, OPTAB_WIDEN);
3489       insns = get_insns ();
3490       end_sequence ();
3491
3492       if (tem)
3493         {
3494           emit_insn (insns);
3495           return extract_high_half (mode, tem);
3496         }
3497     }
3498
3499   /* Try widening multiplication of opposite signedness, and adjust.  */
3500   moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
3501   if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing
3502       && size - 1 < BITS_PER_WORD
3503       && (mul_widen_cost[wider_mode] + 2 * shift_cost[mode][size-1]
3504           + 4 * add_cost[mode] < max_cost))
3505     {
3506       tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3507                           NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3508       if (tem != 0)
3509         {
3510           tem = extract_high_half (mode, tem);
3511           /* We used the wrong signedness.  Adjust the result.  */
3512           return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3513                                               target, unsignedp);
3514         }
3515     }
3516
3517   return 0;
3518 }
3519
3520 /* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant),
3521    putting the high half of the result in TARGET if that is convenient,
3522    and return where the result is.  If the operation can not be performed,
3523    0 is returned.
3524
3525    MODE is the mode of operation and result.
3526
3527    UNSIGNEDP nonzero means unsigned multiply.
3528
3529    MAX_COST is the total allowed cost for the expanded RTL.  */
3530
3531 static rtx
3532 expand_mult_highpart (enum machine_mode mode, rtx op0, rtx op1,
3533                       rtx target, int unsignedp, int max_cost)
3534 {
3535   enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
3536   unsigned HOST_WIDE_INT cnst1;
3537   int extra_cost;
3538   bool sign_adjust = false;
3539   enum mult_variant variant;
3540   struct algorithm alg;
3541   rtx tem;
3542
3543   gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3544   /* We can't support modes wider than HOST_BITS_PER_INT.  */
3545   gcc_assert (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT);
3546
3547   cnst1 = INTVAL (op1) & GET_MODE_MASK (mode);
3548
3549   /* We can't optimize modes wider than BITS_PER_WORD. 
3550      ??? We might be able to perform double-word arithmetic if 
3551      mode == word_mode, however all the cost calculations in
3552      synth_mult etc. assume single-word operations.  */
3553   if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3554     return expand_mult_highpart_optab (mode, op0, op1, target,
3555                                        unsignedp, max_cost);
3556
3557   extra_cost = shift_cost[mode][GET_MODE_BITSIZE (mode) - 1];
3558
3559   /* Check whether we try to multiply by a negative constant.  */
3560   if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3561     {
3562       sign_adjust = true;
3563       extra_cost += add_cost[mode];
3564     }
3565
3566   /* See whether shift/add multiplication is cheap enough.  */
3567   if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3568                            max_cost - extra_cost))
3569     {
3570       /* See whether the specialized multiplication optabs are
3571          cheaper than the shift/add version.  */
3572       tem = expand_mult_highpart_optab (mode, op0, op1, target, unsignedp,
3573                                         alg.cost.cost + extra_cost);
3574       if (tem)
3575         return tem;
3576
3577       tem = convert_to_mode (wider_mode, op0, unsignedp);
3578       tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3579       tem = extract_high_half (mode, tem);
3580
3581       /* Adjust result for signedness.  */
3582       if (sign_adjust)
3583         tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3584
3585       return tem;
3586     }
3587   return expand_mult_highpart_optab (mode, op0, op1, target,
3588                                      unsignedp, max_cost);
3589 }
3590
3591
3592 /* Expand signed modulus of OP0 by a power of two D in mode MODE.  */
3593
3594 static rtx
3595 expand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3596 {
3597   unsigned HOST_WIDE_INT masklow, maskhigh;
3598   rtx result, temp, shift, label;
3599   int logd;
3600
3601   logd = floor_log2 (d);
3602   result = gen_reg_rtx (mode);
3603
3604   /* Avoid conditional branches when they're expensive.  */
3605   if (BRANCH_COST >= 2
3606       && !optimize_size)
3607     {
3608       rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3609                                       mode, 0, -1);
3610       if (signmask)
3611         {
3612           signmask = force_reg (mode, signmask);
3613           masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3614           shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd);
3615
3616           /* Use the rtx_cost of a LSHIFTRT instruction to determine
3617              which instruction sequence to use.  If logical right shifts
3618              are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3619              use a LSHIFTRT, 1 ADD, 1 SUB and an AND.  */
3620
3621           temp = gen_rtx_LSHIFTRT (mode, result, shift);
3622           if (lshr_optab->handlers[mode].insn_code == CODE_FOR_nothing
3623               || rtx_cost (temp, SET) > COSTS_N_INSNS (2))
3624             {
3625               temp = expand_binop (mode, xor_optab, op0, signmask,
3626                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3627               temp = expand_binop (mode, sub_optab, temp, signmask,
3628                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3629               temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow),
3630                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3631               temp = expand_binop (mode, xor_optab, temp, signmask,
3632                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3633               temp = expand_binop (mode, sub_optab, temp, signmask,
3634                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3635             }
3636           else
3637             {
3638               signmask = expand_binop (mode, lshr_optab, signmask, shift,
3639                                        NULL_RTX, 1, OPTAB_LIB_WIDEN);
3640               signmask = force_reg (mode, signmask);
3641
3642               temp = expand_binop (mode, add_optab, op0, signmask,
3643                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3644               temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow),
3645                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3646               temp = expand_binop (mode, sub_optab, temp, signmask,
3647                                    NULL_RTX, 1, OPTAB_LIB_WIDEN);
3648             }
3649           return temp;
3650         }
3651     }
3652
3653   /* Mask contains the mode's signbit and the significant bits of the
3654      modulus.  By including the signbit in the operation, many targets
3655      can avoid an explicit compare operation in the following comparison
3656      against zero.  */
3657
3658   masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3659   if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
3660     {
3661       masklow |= (HOST_WIDE_INT) -1 << (GET_MODE_BITSIZE (mode) - 1);
3662       maskhigh = -1;
3663     }
3664   else
3665     maskhigh = (HOST_WIDE_INT) -1
3666                  << (GET_MODE_BITSIZE (mode) - HOST_BITS_PER_WIDE_INT - 1);
3667
3668   temp = expand_binop (mode, and_optab, op0,
3669                        immed_double_const (masklow, maskhigh, mode),
3670                        result, 1, OPTAB_LIB_WIDEN);
3671   if (temp != result)
3672     emit_move_insn (result, temp);
3673
3674   label = gen_label_rtx ();
3675   do_cmp_and_jump (result, const0_rtx, GE, mode, label);
3676
3677   temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
3678                        0, OPTAB_LIB_WIDEN);
3679   masklow = (HOST_WIDE_INT) -1 << logd;
3680   maskhigh = -1;
3681   temp = expand_binop (mode, ior_optab, temp,
3682                        immed_double_const (masklow, maskhigh, mode),
3683                        result, 1, OPTAB_LIB_WIDEN);
3684   temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
3685                        0, OPTAB_LIB_WIDEN);
3686   if (temp != result)
3687     emit_move_insn (result, temp);
3688   emit_label (label);
3689   return result;
3690 }
3691
3692 /* Expand signed division of OP0 by a power of two D in mode MODE.
3693    This routine is only called for positive values of D.  */
3694
3695 static rtx
3696 expand_sdiv_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3697 {
3698   rtx temp, label;
3699   tree shift;
3700   int logd;
3701
3702   logd = floor_log2 (d);
3703   shift = build_int_cst (NULL_TREE, logd);
3704
3705   if (d == 2 && BRANCH_COST >= 1)
3706     {
3707       temp = gen_reg_rtx (mode);
3708       temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1);
3709       temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3710                            0, OPTAB_LIB_WIDEN);
3711       return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3712     }
3713
3714 #ifdef HAVE_conditional_move
3715   if (BRANCH_COST >= 2)
3716     {
3717       rtx temp2;
3718
3719       /* ??? emit_conditional_move forces a stack adjustment via
3720          compare_from_rtx so, if the sequence is discarded, it will
3721          be lost.  Do it now instead.  */
3722       do_pending_stack_adjust ();
3723
3724       start_sequence ();
3725       temp2 = copy_to_mode_reg (mode, op0);
3726       temp = expand_binop (mode, add_optab, temp2, GEN_INT (d-1),
3727                            NULL_RTX, 0, OPTAB_LIB_WIDEN);
3728       temp = force_reg (mode, temp);
3729
3730       /* Construct "temp2 = (temp2 < 0) ? temp : temp2".  */
3731       temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx,
3732                                      mode, temp, temp2, mode, 0);
3733       if (temp2)
3734         {
3735           rtx seq = get_insns ();
3736           end_sequence ();
3737           emit_insn (seq);
3738           return expand_shift (RSHIFT_EXPR, mode, temp2, shift, NULL_RTX, 0);
3739         }
3740       end_sequence ();
3741     }
3742 #endif
3743
3744   if (BRANCH_COST >= 2)
3745     {
3746       int ushift = GET_MODE_BITSIZE (mode) - logd;
3747
3748       temp = gen_reg_rtx (mode);
3749       temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1);
3750       if (shift_cost[mode][ushift] > COSTS_N_INSNS (1))
3751         temp = expand_binop (mode, and_optab, temp, GEN_INT (d - 1),
3752                              NULL_RTX, 0, OPTAB_LIB_WIDEN);
3753       else
3754         temp = expand_shift (RSHIFT_EXPR, mode, temp,
3755                              build_int_cst (NULL_TREE, ushift),
3756                              NULL_RTX, 1);
3757       temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3758                            0, OPTAB_LIB_WIDEN);
3759       return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3760     }
3761
3762   label = gen_label_rtx ();
3763   temp = copy_to_mode_reg (mode, op0);
3764   do_cmp_and_jump (temp, const0_rtx, GE, mode, label);
3765   expand_inc (temp, GEN_INT (d - 1));
3766   emit_label (label);
3767   return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3768 }
3769 \f
3770 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3771    if that is convenient, and returning where the result is.
3772    You may request either the quotient or the remainder as the result;
3773    specify REM_FLAG nonzero to get the remainder.
3774
3775    CODE is the expression code for which kind of division this is;
3776    it controls how rounding is done.  MODE is the machine mode to use.
3777    UNSIGNEDP nonzero means do unsigned division.  */
3778
3779 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3780    and then correct it by or'ing in missing high bits
3781    if result of ANDI is nonzero.
3782    For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3783    This could optimize to a bfexts instruction.
3784    But C doesn't use these operations, so their optimizations are
3785    left for later.  */
3786 /* ??? For modulo, we don't actually need the highpart of the first product,
3787    the low part will do nicely.  And for small divisors, the second multiply
3788    can also be a low-part only multiply or even be completely left out.
3789    E.g. to calculate the remainder of a division by 3 with a 32 bit
3790    multiply, multiply with 0x55555556 and extract the upper two bits;
3791    the result is exact for inputs up to 0x1fffffff.
3792    The input range can be reduced by using cross-sum rules.
3793    For odd divisors >= 3, the following table gives right shift counts
3794    so that if a number is shifted by an integer multiple of the given
3795    amount, the remainder stays the same:
3796    2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3797    14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3798    0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3799    20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3800    0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3801
3802    Cross-sum rules for even numbers can be derived by leaving as many bits
3803    to the right alone as the divisor has zeros to the right.
3804    E.g. if x is an unsigned 32 bit number:
3805    (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3806    */
3807
3808 rtx
3809 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3810                rtx op0, rtx op1, rtx target, int unsignedp)
3811 {
3812   enum machine_mode compute_mode;
3813   rtx tquotient;
3814   rtx quotient = 0, remainder = 0;
3815   rtx last;
3816   int size;
3817   rtx insn, set;
3818   optab optab1, optab2;
3819   int op1_is_constant, op1_is_pow2 = 0;
3820   int max_cost, extra_cost;
3821   static HOST_WIDE_INT last_div_const = 0;
3822   static HOST_WIDE_INT ext_op1;
3823
3824   op1_is_constant = GET_CODE (op1) == CONST_INT;
3825   if (op1_is_constant)
3826     {
3827       ext_op1 = INTVAL (op1);
3828       if (unsignedp)
3829         ext_op1 &= GET_MODE_MASK (mode);
3830       op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3831                      || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3832     }
3833
3834   /*
3835      This is the structure of expand_divmod:
3836
3837      First comes code to fix up the operands so we can perform the operations
3838      correctly and efficiently.
3839
3840      Second comes a switch statement with code specific for each rounding mode.
3841      For some special operands this code emits all RTL for the desired
3842      operation, for other cases, it generates only a quotient and stores it in
3843      QUOTIENT.  The case for trunc division/remainder might leave quotient = 0,
3844      to indicate that it has not done anything.
3845
3846      Last comes code that finishes the operation.  If QUOTIENT is set and
3847      REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1.  If
3848      QUOTIENT is not set, it is computed using trunc rounding.
3849
3850      We try to generate special code for division and remainder when OP1 is a
3851      constant.  If |OP1| = 2**n we can use shifts and some other fast
3852      operations.  For other values of OP1, we compute a carefully selected
3853      fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3854      by m.
3855
3856      In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3857      half of the product.  Different strategies for generating the product are
3858      implemented in expand_mult_highpart.
3859
3860      If what we actually want is the remainder, we generate that by another
3861      by-constant multiplication and a subtraction.  */
3862
3863   /* We shouldn't be called with OP1 == const1_rtx, but some of the
3864      code below will malfunction if we are, so check here and handle
3865      the special case if so.  */
3866   if (op1 == const1_rtx)
3867     return rem_flag ? const0_rtx : op0;
3868
3869     /* When dividing by -1, we could get an overflow.
3870      negv_optab can handle overflows.  */
3871   if (! unsignedp && op1 == constm1_rtx)
3872     {
3873       if (rem_flag)
3874         return const0_rtx;
3875       return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3876                           ? negv_optab : neg_optab, op0, target, 0);
3877     }
3878
3879   if (target
3880       /* Don't use the function value register as a target
3881          since we have to read it as well as write it,
3882          and function-inlining gets confused by this.  */
3883       && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3884           /* Don't clobber an operand while doing a multi-step calculation.  */
3885           || ((rem_flag || op1_is_constant)
3886               && (reg_mentioned_p (target, op0)
3887                   || (MEM_P (op0) && MEM_P (target))))
3888           || reg_mentioned_p (target, op1)
3889           || (MEM_P (op1) && MEM_P (target))))
3890     target = 0;
3891
3892   /* Get the mode in which to perform this computation.  Normally it will
3893      be MODE, but sometimes we can't do the desired operation in MODE.
3894      If so, pick a wider mode in which we can do the operation.  Convert
3895      to that mode at the start to avoid repeated conversions.
3896
3897      First see what operations we need.  These depend on the expression
3898      we are evaluating.  (We assume that divxx3 insns exist under the
3899      same conditions that modxx3 insns and that these insns don't normally
3900      fail.  If these assumptions are not correct, we may generate less
3901      efficient code in some cases.)
3902
3903      Then see if we find a mode in which we can open-code that operation
3904      (either a division, modulus, or shift).  Finally, check for the smallest
3905      mode for which we can do the operation with a library call.  */
3906
3907   /* We might want to refine this now that we have division-by-constant
3908      optimization.  Since expand_mult_highpart tries so many variants, it is
3909      not straightforward to generalize this.  Maybe we should make an array
3910      of possible modes in init_expmed?  Save this for GCC 2.7.  */
3911
3912   optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3913             ? (unsignedp ? lshr_optab : ashr_optab)
3914             : (unsignedp ? udiv_optab : sdiv_optab));
3915   optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3916             ? optab1
3917             : (unsignedp ? udivmod_optab : sdivmod_optab));
3918
3919   for (compute_mode = mode; compute_mode != VOIDmode;
3920        compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3921     if (optab1->handlers[compute_mode].insn_code != CODE_FOR_nothing
3922         || optab2->handlers[compute_mode].insn_code != CODE_FOR_nothing)
3923       break;
3924
3925   if (compute_mode == VOIDmode)
3926     for (compute_mode = mode; compute_mode != VOIDmode;
3927          compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3928       if (optab1->handlers[compute_mode].libfunc
3929           || optab2->handlers[compute_mode].libfunc)
3930         break;
3931
3932   /* If we still couldn't find a mode, use MODE, but expand_binop will
3933      probably die.  */
3934   if (compute_mode == VOIDmode)
3935     compute_mode = mode;
3936
3937   if (target && GET_MODE (target) == compute_mode)
3938     tquotient = target;
3939   else
3940     tquotient = gen_reg_rtx (compute_mode);
3941
3942   size = GET