OSDN Git Service

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