OSDN Git Service

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