Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / optabs.c
1 /* Expand the basic unary and binary arithmetic operations, for GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
4    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 3, 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 COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "toplev.h"
28
29 /* Include insn-config.h before expr.h so that HAVE_conditional_move
30    is properly defined.  */
31 #include "insn-config.h"
32 #include "rtl.h"
33 #include "tree.h"
34 #include "tm_p.h"
35 #include "flags.h"
36 #include "function.h"
37 #include "except.h"
38 #include "expr.h"
39 #include "optabs.h"
40 #include "libfuncs.h"
41 #include "recog.h"
42 #include "reload.h"
43 #include "ggc.h"
44 #include "real.h"
45 #include "basic-block.h"
46 #include "target.h"
47
48 /* Each optab contains info on how this target machine
49    can perform a particular operation
50    for all sizes and kinds of operands.
51
52    The operation to be performed is often specified
53    by passing one of these optabs as an argument.
54
55    See expr.h for documentation of these optabs.  */
56
57 #if GCC_VERSION >= 4000
58 __extension__ struct optab optab_table[OTI_MAX]
59   = { [0 ... OTI_MAX - 1].handlers[0 ... NUM_MACHINE_MODES - 1].insn_code
60       = CODE_FOR_nothing };
61 #else
62 /* init_insn_codes will do runtime initialization otherwise.  */
63 struct optab optab_table[OTI_MAX];
64 #endif
65
66 rtx libfunc_table[LTI_MAX];
67
68 /* Tables of patterns for converting one mode to another.  */
69 #if GCC_VERSION >= 4000
70 __extension__ struct convert_optab convert_optab_table[COI_MAX]
71   = { [0 ... COI_MAX - 1].handlers[0 ... NUM_MACHINE_MODES - 1]
72         [0 ... NUM_MACHINE_MODES - 1].insn_code
73       = CODE_FOR_nothing };
74 #else
75 /* init_convert_optab will do runtime initialization otherwise.  */
76 struct convert_optab convert_optab_table[COI_MAX];
77 #endif
78
79 /* Contains the optab used for each rtx code.  */
80 optab code_to_optab[NUM_RTX_CODE + 1];
81
82 /* Indexed by the rtx-code for a conditional (eg. EQ, LT,...)
83    gives the gen_function to make a branch to test that condition.  */
84
85 rtxfun bcc_gen_fctn[NUM_RTX_CODE];
86
87 /* Indexed by the rtx-code for a conditional (eg. EQ, LT,...)
88    gives the insn code to make a store-condition insn
89    to test that condition.  */
90
91 enum insn_code setcc_gen_code[NUM_RTX_CODE];
92
93 #ifdef HAVE_conditional_move
94 /* Indexed by the machine mode, gives the insn code to make a conditional
95    move insn.  This is not indexed by the rtx-code like bcc_gen_fctn and
96    setcc_gen_code to cut down on the number of named patterns.  Consider a day
97    when a lot more rtx codes are conditional (eg: for the ARM).  */
98
99 enum insn_code movcc_gen_code[NUM_MACHINE_MODES];
100 #endif
101
102 /* Indexed by the machine mode, gives the insn code for vector conditional
103    operation.  */
104
105 enum insn_code vcond_gen_code[NUM_MACHINE_MODES];
106 enum insn_code vcondu_gen_code[NUM_MACHINE_MODES];
107
108 /* The insn generating function can not take an rtx_code argument.
109    TRAP_RTX is used as an rtx argument.  Its code is replaced with
110    the code to be used in the trap insn and all other fields are ignored.  */
111 static GTY(()) rtx trap_rtx;
112
113 static void prepare_float_lib_cmp (rtx *, rtx *, enum rtx_code *,
114                                    enum machine_mode *, int *);
115 static rtx expand_unop_direct (enum machine_mode, optab, rtx, rtx, int);
116
117 /* Debug facility for use in GDB.  */
118 void debug_optab_libfuncs (void);
119
120 #ifndef HAVE_conditional_trap
121 #define HAVE_conditional_trap 0
122 #define gen_conditional_trap(a,b) (gcc_unreachable (), NULL_RTX)
123 #endif
124
125 /* Prefixes for the current version of decimal floating point (BID vs. DPD) */
126 #if ENABLE_DECIMAL_BID_FORMAT
127 #define DECIMAL_PREFIX "bid_"
128 #else
129 #define DECIMAL_PREFIX "dpd_"
130 #endif
131 \f
132
133 /* Info about libfunc.  We use same hashtable for normal optabs and conversion
134    optab.  In the first case mode2 is unused.  */
135 struct libfunc_entry GTY(())
136 {
137   size_t optab;
138   enum machine_mode mode1, mode2;
139   rtx libfunc;
140 };
141
142 /* Hash table used to convert declarations into nodes.  */
143 static GTY((param_is (struct libfunc_entry))) htab_t libfunc_hash;
144
145 /* Used for attribute_hash.  */
146
147 static hashval_t
148 hash_libfunc (const void *p)
149 {
150   const struct libfunc_entry *const e = (const struct libfunc_entry *) p;
151
152   return (((int) e->mode1 + (int) e->mode2 * NUM_MACHINE_MODES)
153           ^ e->optab);
154 }
155
156 /* Used for optab_hash.  */
157
158 static int
159 eq_libfunc (const void *p, const void *q)
160 {
161   const struct libfunc_entry *const e1 = (const struct libfunc_entry *) p;
162   const struct libfunc_entry *const e2 = (const struct libfunc_entry *) q;
163
164   return (e1->optab == e2->optab
165           && e1->mode1 == e2->mode1
166           && e1->mode2 == e2->mode2);
167 }
168
169 /* Return libfunc corresponding operation defined by OPTAB converting
170    from MODE2 to MODE1.  Trigger lazy initialization if needed, return NULL
171    if no libfunc is available.  */
172 rtx
173 convert_optab_libfunc (convert_optab optab, enum machine_mode mode1,
174                        enum machine_mode mode2)
175 {
176   struct libfunc_entry e;
177   struct libfunc_entry **slot;
178
179   e.optab = (size_t) (optab - &convert_optab_table[0]);
180   e.mode1 = mode1;
181   e.mode2 = mode2;
182   slot = (struct libfunc_entry **) htab_find_slot (libfunc_hash, &e, NO_INSERT);
183   if (!slot)
184     {
185       if (optab->libcall_gen)
186         {
187           optab->libcall_gen (optab, optab->libcall_basename, mode1, mode2);
188           slot = (struct libfunc_entry **) htab_find_slot (libfunc_hash, &e, NO_INSERT);
189           if (slot)
190             return (*slot)->libfunc;
191           else
192             return NULL;
193         }
194       return NULL;
195     }
196   return (*slot)->libfunc;
197 }
198
199 /* Return libfunc corresponding operation defined by OPTAB in MODE.
200    Trigger lazy initialization if needed, return NULL if no libfunc is
201    available.  */
202 rtx
203 optab_libfunc (optab optab, enum machine_mode mode)
204 {
205   struct libfunc_entry e;
206   struct libfunc_entry **slot;
207
208   e.optab = (size_t) (optab - &optab_table[0]);
209   e.mode1 = mode;
210   e.mode2 = VOIDmode;
211   slot = (struct libfunc_entry **) htab_find_slot (libfunc_hash, &e, NO_INSERT);
212   if (!slot)
213     {
214       if (optab->libcall_gen)
215         {
216           optab->libcall_gen (optab, optab->libcall_basename,
217                               optab->libcall_suffix, mode);
218           slot = (struct libfunc_entry **) htab_find_slot (libfunc_hash,
219                                                            &e, NO_INSERT);
220           if (slot)
221             return (*slot)->libfunc;
222           else
223             return NULL;
224         }
225       return NULL;
226     }
227   return (*slot)->libfunc;
228 }
229
230 \f
231 /* Add a REG_EQUAL note to the last insn in INSNS.  TARGET is being set to
232    the result of operation CODE applied to OP0 (and OP1 if it is a binary
233    operation).
234
235    If the last insn does not set TARGET, don't do anything, but return 1.
236
237    If a previous insn sets TARGET and TARGET is one of OP0 or OP1,
238    don't add the REG_EQUAL note but return 0.  Our caller can then try
239    again, ensuring that TARGET is not one of the operands.  */
240
241 static int
242 add_equal_note (rtx insns, rtx target, enum rtx_code code, rtx op0, rtx op1)
243 {
244   rtx last_insn, insn, set;
245   rtx note;
246
247   gcc_assert (insns && INSN_P (insns) && NEXT_INSN (insns));
248
249   if (GET_RTX_CLASS (code) != RTX_COMM_ARITH
250       && GET_RTX_CLASS (code) != RTX_BIN_ARITH
251       && GET_RTX_CLASS (code) != RTX_COMM_COMPARE
252       && GET_RTX_CLASS (code) != RTX_COMPARE
253       && GET_RTX_CLASS (code) != RTX_UNARY)
254     return 1;
255
256   if (GET_CODE (target) == ZERO_EXTRACT)
257     return 1;
258
259   for (last_insn = insns;
260        NEXT_INSN (last_insn) != NULL_RTX;
261        last_insn = NEXT_INSN (last_insn))
262     ;
263
264   set = single_set (last_insn);
265   if (set == NULL_RTX)
266     return 1;
267
268   if (! rtx_equal_p (SET_DEST (set), target)
269       /* For a STRICT_LOW_PART, the REG_NOTE applies to what is inside it.  */
270       && (GET_CODE (SET_DEST (set)) != STRICT_LOW_PART
271           || ! rtx_equal_p (XEXP (SET_DEST (set), 0), target)))
272     return 1;
273
274   /* If TARGET is in OP0 or OP1, check if anything in SEQ sets TARGET
275      besides the last insn.  */
276   if (reg_overlap_mentioned_p (target, op0)
277       || (op1 && reg_overlap_mentioned_p (target, op1)))
278     {
279       insn = PREV_INSN (last_insn);
280       while (insn != NULL_RTX)
281         {
282           if (reg_set_p (target, insn))
283             return 0;
284
285           insn = PREV_INSN (insn);
286         }
287     }
288
289   if (GET_RTX_CLASS (code) == RTX_UNARY)
290     note = gen_rtx_fmt_e (code, GET_MODE (target), copy_rtx (op0));
291   else
292     note = gen_rtx_fmt_ee (code, GET_MODE (target), copy_rtx (op0), copy_rtx (op1));
293
294   set_unique_reg_note (last_insn, REG_EQUAL, note);
295
296   return 1;
297 }
298 \f
299 /* Widen OP to MODE and return the rtx for the widened operand.  UNSIGNEDP
300    says whether OP is signed or unsigned.  NO_EXTEND is nonzero if we need
301    not actually do a sign-extend or zero-extend, but can leave the
302    higher-order bits of the result rtx undefined, for example, in the case
303    of logical operations, but not right shifts.  */
304
305 static rtx
306 widen_operand (rtx op, enum machine_mode mode, enum machine_mode oldmode,
307                int unsignedp, int no_extend)
308 {
309   rtx result;
310
311   /* If we don't have to extend and this is a constant, return it.  */
312   if (no_extend && GET_MODE (op) == VOIDmode)
313     return op;
314
315   /* If we must extend do so.  If OP is a SUBREG for a promoted object, also
316      extend since it will be more efficient to do so unless the signedness of
317      a promoted object differs from our extension.  */
318   if (! no_extend
319       || (GET_CODE (op) == SUBREG && SUBREG_PROMOTED_VAR_P (op)
320           && SUBREG_PROMOTED_UNSIGNED_P (op) == unsignedp))
321     return convert_modes (mode, oldmode, op, unsignedp);
322
323   /* If MODE is no wider than a single word, we return a paradoxical
324      SUBREG.  */
325   if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
326     return gen_rtx_SUBREG (mode, force_reg (GET_MODE (op), op), 0);
327
328   /* Otherwise, get an object of MODE, clobber it, and set the low-order
329      part to OP.  */
330
331   result = gen_reg_rtx (mode);
332   emit_clobber (result);
333   emit_move_insn (gen_lowpart (GET_MODE (op), result), op);
334   return result;
335 }
336 \f
337 /* Return the optab used for computing the operation given by the tree code,
338    CODE and the tree EXP.  This function is not always usable (for example, it
339    cannot give complete results for multiplication or division) but probably
340    ought to be relied on more widely throughout the expander.  */
341 optab
342 optab_for_tree_code (enum tree_code code, const_tree type,
343                      enum optab_subtype subtype)
344 {
345   bool trapv;
346   switch (code)
347     {
348     case BIT_AND_EXPR:
349       return and_optab;
350
351     case BIT_IOR_EXPR:
352       return ior_optab;
353
354     case BIT_NOT_EXPR:
355       return one_cmpl_optab;
356
357     case BIT_XOR_EXPR:
358       return xor_optab;
359
360     case TRUNC_MOD_EXPR:
361     case CEIL_MOD_EXPR:
362     case FLOOR_MOD_EXPR:
363     case ROUND_MOD_EXPR:
364       return TYPE_UNSIGNED (type) ? umod_optab : smod_optab;
365
366     case RDIV_EXPR:
367     case TRUNC_DIV_EXPR:
368     case CEIL_DIV_EXPR:
369     case FLOOR_DIV_EXPR:
370     case ROUND_DIV_EXPR:
371     case EXACT_DIV_EXPR:
372       if (TYPE_SATURATING(type))
373         return TYPE_UNSIGNED(type) ? usdiv_optab : ssdiv_optab;
374       return TYPE_UNSIGNED (type) ? udiv_optab : sdiv_optab;
375
376     case LSHIFT_EXPR:
377       if (VECTOR_MODE_P (TYPE_MODE (type)))
378         {
379           if (subtype == optab_vector)
380             return TYPE_SATURATING (type) ? NULL : vashl_optab;
381
382           gcc_assert (subtype == optab_scalar);
383         }
384       if (TYPE_SATURATING(type))
385         return TYPE_UNSIGNED(type) ? usashl_optab : ssashl_optab;
386       return ashl_optab;
387
388     case RSHIFT_EXPR:
389       if (VECTOR_MODE_P (TYPE_MODE (type)))
390         {
391           if (subtype == optab_vector)
392             return TYPE_UNSIGNED (type) ? vlshr_optab : vashr_optab;
393
394           gcc_assert (subtype == optab_scalar);
395         }
396       return TYPE_UNSIGNED (type) ? lshr_optab : ashr_optab;
397
398     case LROTATE_EXPR:
399       if (VECTOR_MODE_P (TYPE_MODE (type)))
400         {
401           if (subtype == optab_vector)
402             return vrotl_optab;
403
404           gcc_assert (subtype == optab_scalar);
405         }
406       return rotl_optab;
407
408     case RROTATE_EXPR:
409       if (VECTOR_MODE_P (TYPE_MODE (type)))
410         {
411           if (subtype == optab_vector)
412             return vrotr_optab;
413
414           gcc_assert (subtype == optab_scalar);
415         }
416       return rotr_optab;
417
418     case MAX_EXPR:
419       return TYPE_UNSIGNED (type) ? umax_optab : smax_optab;
420
421     case MIN_EXPR:
422       return TYPE_UNSIGNED (type) ? umin_optab : smin_optab;
423
424     case REALIGN_LOAD_EXPR:
425       return vec_realign_load_optab;
426
427     case WIDEN_SUM_EXPR:
428       return TYPE_UNSIGNED (type) ? usum_widen_optab : ssum_widen_optab;
429
430     case DOT_PROD_EXPR:
431       return TYPE_UNSIGNED (type) ? udot_prod_optab : sdot_prod_optab;
432
433     case REDUC_MAX_EXPR:
434       return TYPE_UNSIGNED (type) ? reduc_umax_optab : reduc_smax_optab;
435
436     case REDUC_MIN_EXPR:
437       return TYPE_UNSIGNED (type) ? reduc_umin_optab : reduc_smin_optab;
438
439     case REDUC_PLUS_EXPR:
440       return TYPE_UNSIGNED (type) ? reduc_uplus_optab : reduc_splus_optab;
441
442     case VEC_LSHIFT_EXPR:
443       return vec_shl_optab;
444
445     case VEC_RSHIFT_EXPR:
446       return vec_shr_optab;
447
448     case VEC_WIDEN_MULT_HI_EXPR:
449       return TYPE_UNSIGNED (type) ? 
450         vec_widen_umult_hi_optab : vec_widen_smult_hi_optab;
451
452     case VEC_WIDEN_MULT_LO_EXPR:
453       return TYPE_UNSIGNED (type) ? 
454         vec_widen_umult_lo_optab : vec_widen_smult_lo_optab;
455
456     case VEC_UNPACK_HI_EXPR:
457       return TYPE_UNSIGNED (type) ?
458         vec_unpacku_hi_optab : vec_unpacks_hi_optab;
459
460     case VEC_UNPACK_LO_EXPR:
461       return TYPE_UNSIGNED (type) ? 
462         vec_unpacku_lo_optab : vec_unpacks_lo_optab;
463
464     case VEC_UNPACK_FLOAT_HI_EXPR:
465       /* The signedness is determined from input operand.  */
466       return TYPE_UNSIGNED (type) ?
467         vec_unpacku_float_hi_optab : vec_unpacks_float_hi_optab;
468
469     case VEC_UNPACK_FLOAT_LO_EXPR:
470       /* The signedness is determined from input operand.  */
471       return TYPE_UNSIGNED (type) ? 
472         vec_unpacku_float_lo_optab : vec_unpacks_float_lo_optab;
473
474     case VEC_PACK_TRUNC_EXPR:
475       return vec_pack_trunc_optab;
476
477     case VEC_PACK_SAT_EXPR:
478       return TYPE_UNSIGNED (type) ? vec_pack_usat_optab : vec_pack_ssat_optab;
479
480     case VEC_PACK_FIX_TRUNC_EXPR:
481       /* The signedness is determined from output operand.  */
482       return TYPE_UNSIGNED (type) ?
483         vec_pack_ufix_trunc_optab : vec_pack_sfix_trunc_optab;
484
485     default:
486       break;
487     }
488
489   trapv = INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type);
490   switch (code)
491     {
492     case POINTER_PLUS_EXPR:
493     case PLUS_EXPR:
494       if (TYPE_SATURATING(type))
495         return TYPE_UNSIGNED(type) ? usadd_optab : ssadd_optab;
496       return trapv ? addv_optab : add_optab;
497
498     case MINUS_EXPR:
499       if (TYPE_SATURATING(type))
500         return TYPE_UNSIGNED(type) ? ussub_optab : sssub_optab;
501       return trapv ? subv_optab : sub_optab;
502
503     case MULT_EXPR:
504       if (TYPE_SATURATING(type))
505         return TYPE_UNSIGNED(type) ? usmul_optab : ssmul_optab;
506       return trapv ? smulv_optab : smul_optab;
507
508     case NEGATE_EXPR:
509       if (TYPE_SATURATING(type))
510         return TYPE_UNSIGNED(type) ? usneg_optab : ssneg_optab;
511       return trapv ? negv_optab : neg_optab;
512
513     case ABS_EXPR:
514       return trapv ? absv_optab : abs_optab;
515
516     case VEC_EXTRACT_EVEN_EXPR:
517       return vec_extract_even_optab;
518
519     case VEC_EXTRACT_ODD_EXPR:
520       return vec_extract_odd_optab;
521
522     case VEC_INTERLEAVE_HIGH_EXPR:
523       return vec_interleave_high_optab;
524
525     case VEC_INTERLEAVE_LOW_EXPR:
526       return vec_interleave_low_optab;
527
528     default:
529       return NULL;
530     }
531 }
532 \f
533
534 /* Expand vector widening operations.
535
536    There are two different classes of operations handled here:
537    1) Operations whose result is wider than all the arguments to the operation.
538       Examples: VEC_UNPACK_HI/LO_EXPR, VEC_WIDEN_MULT_HI/LO_EXPR
539       In this case OP0 and optionally OP1 would be initialized,
540       but WIDE_OP wouldn't (not relevant for this case).
541    2) Operations whose result is of the same size as the last argument to the
542       operation, but wider than all the other arguments to the operation.
543       Examples: WIDEN_SUM_EXPR, VEC_DOT_PROD_EXPR.
544       In the case WIDE_OP, OP0 and optionally OP1 would be initialized.
545
546    E.g, when called to expand the following operations, this is how
547    the arguments will be initialized:
548                                 nops    OP0     OP1     WIDE_OP
549    widening-sum                 2       oprnd0  -       oprnd1          
550    widening-dot-product         3       oprnd0  oprnd1  oprnd2
551    widening-mult                2       oprnd0  oprnd1  -
552    type-promotion (vec-unpack)  1       oprnd0  -       -  */
553
554 rtx
555 expand_widen_pattern_expr (tree exp, rtx op0, rtx op1, rtx wide_op, rtx target,
556                            int unsignedp)
557 {   
558   tree oprnd0, oprnd1, oprnd2;
559   enum machine_mode wmode = 0, tmode0, tmode1 = 0;
560   optab widen_pattern_optab;
561   int icode; 
562   enum machine_mode xmode0, xmode1 = 0, wxmode = 0;
563   rtx temp;
564   rtx pat;
565   rtx xop0, xop1, wxop;
566   int nops = TREE_OPERAND_LENGTH (exp);
567
568   oprnd0 = TREE_OPERAND (exp, 0);
569   tmode0 = TYPE_MODE (TREE_TYPE (oprnd0));
570   widen_pattern_optab =
571     optab_for_tree_code (TREE_CODE (exp), TREE_TYPE (oprnd0), optab_default);
572   icode = (int) optab_handler (widen_pattern_optab, tmode0)->insn_code;
573   gcc_assert (icode != CODE_FOR_nothing);
574   xmode0 = insn_data[icode].operand[1].mode;
575
576   if (nops >= 2)
577     {
578       oprnd1 = TREE_OPERAND (exp, 1);
579       tmode1 = TYPE_MODE (TREE_TYPE (oprnd1));
580       xmode1 = insn_data[icode].operand[2].mode;
581     }
582
583   /* The last operand is of a wider mode than the rest of the operands.  */
584   if (nops == 2)
585     {
586       wmode = tmode1;
587       wxmode = xmode1;
588     }
589   else if (nops == 3)
590     {
591       gcc_assert (tmode1 == tmode0);
592       gcc_assert (op1);
593       oprnd2 = TREE_OPERAND (exp, 2);
594       wmode = TYPE_MODE (TREE_TYPE (oprnd2));
595       wxmode = insn_data[icode].operand[3].mode;
596     }
597
598   if (!wide_op)
599     wmode = wxmode = insn_data[icode].operand[0].mode;
600
601   if (!target
602       || ! (*insn_data[icode].operand[0].predicate) (target, wmode))
603     temp = gen_reg_rtx (wmode);
604   else
605     temp = target;
606
607   xop0 = op0;
608   xop1 = op1;
609   wxop = wide_op;
610
611   /* In case the insn wants input operands in modes different from
612      those of the actual operands, convert the operands.  It would
613      seem that we don't need to convert CONST_INTs, but we do, so
614      that they're properly zero-extended, sign-extended or truncated
615      for their mode.  */
616
617   if (GET_MODE (op0) != xmode0 && xmode0 != VOIDmode)
618     xop0 = convert_modes (xmode0,
619                           GET_MODE (op0) != VOIDmode
620                           ? GET_MODE (op0)
621                           : tmode0,
622                           xop0, unsignedp);
623
624   if (op1)
625     if (GET_MODE (op1) != xmode1 && xmode1 != VOIDmode)
626       xop1 = convert_modes (xmode1,
627                             GET_MODE (op1) != VOIDmode
628                             ? GET_MODE (op1)
629                             : tmode1,
630                             xop1, unsignedp);
631
632   if (wide_op)
633     if (GET_MODE (wide_op) != wxmode && wxmode != VOIDmode)
634       wxop = convert_modes (wxmode,
635                             GET_MODE (wide_op) != VOIDmode
636                             ? GET_MODE (wide_op)
637                             : wmode,
638                             wxop, unsignedp);
639
640   /* Now, if insn's predicates don't allow our operands, put them into
641      pseudo regs.  */
642
643   if (! (*insn_data[icode].operand[1].predicate) (xop0, xmode0)
644       && xmode0 != VOIDmode)
645     xop0 = copy_to_mode_reg (xmode0, xop0);
646
647   if (op1)
648     {
649       if (! (*insn_data[icode].operand[2].predicate) (xop1, xmode1)
650           && xmode1 != VOIDmode)
651         xop1 = copy_to_mode_reg (xmode1, xop1);
652
653       if (wide_op)
654         {
655           if (! (*insn_data[icode].operand[3].predicate) (wxop, wxmode)
656               && wxmode != VOIDmode)
657             wxop = copy_to_mode_reg (wxmode, wxop);
658
659           pat = GEN_FCN (icode) (temp, xop0, xop1, wxop);
660         }
661       else
662         pat = GEN_FCN (icode) (temp, xop0, xop1);
663     }
664   else
665     {
666       if (wide_op)
667         {
668           if (! (*insn_data[icode].operand[2].predicate) (wxop, wxmode)
669               && wxmode != VOIDmode)
670             wxop = copy_to_mode_reg (wxmode, wxop);
671
672           pat = GEN_FCN (icode) (temp, xop0, wxop);
673         }
674       else
675         pat = GEN_FCN (icode) (temp, xop0);
676     }
677
678   emit_insn (pat);
679   return temp;
680 }
681
682 /* Generate code to perform an operation specified by TERNARY_OPTAB
683    on operands OP0, OP1 and OP2, with result having machine-mode MODE.
684
685    UNSIGNEDP is for the case where we have to widen the operands
686    to perform the operation.  It says to use zero-extension.
687
688    If TARGET is nonzero, the value
689    is generated there, if it is convenient to do so.
690    In all cases an rtx is returned for the locus of the value;
691    this may or may not be TARGET.  */
692
693 rtx
694 expand_ternary_op (enum machine_mode mode, optab ternary_optab, rtx op0,
695                    rtx op1, rtx op2, rtx target, int unsignedp)
696 {
697   int icode = (int) optab_handler (ternary_optab, mode)->insn_code;
698   enum machine_mode mode0 = insn_data[icode].operand[1].mode;
699   enum machine_mode mode1 = insn_data[icode].operand[2].mode;
700   enum machine_mode mode2 = insn_data[icode].operand[3].mode;
701   rtx temp;
702   rtx pat;
703   rtx xop0 = op0, xop1 = op1, xop2 = op2;
704
705   gcc_assert (optab_handler (ternary_optab, mode)->insn_code
706               != CODE_FOR_nothing);
707
708   if (!target || !insn_data[icode].operand[0].predicate (target, mode))
709     temp = gen_reg_rtx (mode);
710   else
711     temp = target;
712
713   /* In case the insn wants input operands in modes different from
714      those of the actual operands, convert the operands.  It would
715      seem that we don't need to convert CONST_INTs, but we do, so
716      that they're properly zero-extended, sign-extended or truncated
717      for their mode.  */
718
719   if (GET_MODE (op0) != mode0 && mode0 != VOIDmode)
720     xop0 = convert_modes (mode0,
721                           GET_MODE (op0) != VOIDmode
722                           ? GET_MODE (op0)
723                           : mode,
724                           xop0, unsignedp);
725
726   if (GET_MODE (op1) != mode1 && mode1 != VOIDmode)
727     xop1 = convert_modes (mode1,
728                           GET_MODE (op1) != VOIDmode
729                           ? GET_MODE (op1)
730                           : mode,
731                           xop1, unsignedp);
732
733   if (GET_MODE (op2) != mode2 && mode2 != VOIDmode)
734     xop2 = convert_modes (mode2,
735                           GET_MODE (op2) != VOIDmode
736                           ? GET_MODE (op2)
737                           : mode,
738                           xop2, unsignedp);
739
740   /* Now, if insn's predicates don't allow our operands, put them into
741      pseudo regs.  */
742
743   if (!insn_data[icode].operand[1].predicate (xop0, mode0)
744       && mode0 != VOIDmode)
745     xop0 = copy_to_mode_reg (mode0, xop0);
746
747   if (!insn_data[icode].operand[2].predicate (xop1, mode1)
748       && mode1 != VOIDmode)
749     xop1 = copy_to_mode_reg (mode1, xop1);
750
751   if (!insn_data[icode].operand[3].predicate (xop2, mode2)
752       && mode2 != VOIDmode)
753     xop2 = copy_to_mode_reg (mode2, xop2);
754
755   pat = GEN_FCN (icode) (temp, xop0, xop1, xop2);
756
757   emit_insn (pat);
758   return temp;
759 }
760
761
762 /* Like expand_binop, but return a constant rtx if the result can be
763    calculated at compile time.  The arguments and return value are
764    otherwise the same as for expand_binop.  */
765
766 static rtx
767 simplify_expand_binop (enum machine_mode mode, optab binoptab,
768                        rtx op0, rtx op1, rtx target, int unsignedp,
769                        enum optab_methods methods)
770 {
771   if (CONSTANT_P (op0) && CONSTANT_P (op1))
772     {
773       rtx x = simplify_binary_operation (binoptab->code, mode, op0, op1);
774
775       if (x)
776         return x;
777     }
778
779   return expand_binop (mode, binoptab, op0, op1, target, unsignedp, methods);
780 }
781
782 /* Like simplify_expand_binop, but always put the result in TARGET.
783    Return true if the expansion succeeded.  */
784
785 bool
786 force_expand_binop (enum machine_mode mode, optab binoptab,
787                     rtx op0, rtx op1, rtx target, int unsignedp,
788                     enum optab_methods methods)
789 {
790   rtx x = simplify_expand_binop (mode, binoptab, op0, op1,
791                                  target, unsignedp, methods);
792   if (x == 0)
793     return false;
794   if (x != target)
795     emit_move_insn (target, x);
796   return true;
797 }
798
799 /* Generate insns for VEC_LSHIFT_EXPR, VEC_RSHIFT_EXPR.  */
800
801 rtx
802 expand_vec_shift_expr (tree vec_shift_expr, rtx target)
803 {
804   enum insn_code icode;
805   rtx rtx_op1, rtx_op2;
806   enum machine_mode mode1;
807   enum machine_mode mode2;
808   enum machine_mode mode = TYPE_MODE (TREE_TYPE (vec_shift_expr));
809   tree vec_oprnd = TREE_OPERAND (vec_shift_expr, 0);
810   tree shift_oprnd = TREE_OPERAND (vec_shift_expr, 1);
811   optab shift_optab;
812   rtx pat;
813
814   switch (TREE_CODE (vec_shift_expr))
815     {
816       case VEC_RSHIFT_EXPR:
817         shift_optab = vec_shr_optab;
818         break;
819       case VEC_LSHIFT_EXPR:
820         shift_optab = vec_shl_optab;
821         break;
822       default:
823         gcc_unreachable ();
824     }
825
826   icode = (int) optab_handler (shift_optab, mode)->insn_code;
827   gcc_assert (icode != CODE_FOR_nothing);
828
829   mode1 = insn_data[icode].operand[1].mode;
830   mode2 = insn_data[icode].operand[2].mode;
831
832   rtx_op1 = expand_normal (vec_oprnd);
833   if (!(*insn_data[icode].operand[1].predicate) (rtx_op1, mode1)
834       && mode1 != VOIDmode)
835     rtx_op1 = force_reg (mode1, rtx_op1);
836
837   rtx_op2 = expand_normal (shift_oprnd);
838   if (!(*insn_data[icode].operand[2].predicate) (rtx_op2, mode2)
839       && mode2 != VOIDmode)
840     rtx_op2 = force_reg (mode2, rtx_op2);
841
842   if (!target
843       || ! (*insn_data[icode].operand[0].predicate) (target, mode))
844     target = gen_reg_rtx (mode);
845
846   /* Emit instruction */
847   pat = GEN_FCN (icode) (target, rtx_op1, rtx_op2);
848   gcc_assert (pat);
849   emit_insn (pat);
850
851   return target;
852 }
853
854 /* This subroutine of expand_doubleword_shift handles the cases in which
855    the effective shift value is >= BITS_PER_WORD.  The arguments and return
856    value are the same as for the parent routine, except that SUPERWORD_OP1
857    is the shift count to use when shifting OUTOF_INPUT into INTO_TARGET.
858    INTO_TARGET may be null if the caller has decided to calculate it.  */
859
860 static bool
861 expand_superword_shift (optab binoptab, rtx outof_input, rtx superword_op1,
862                         rtx outof_target, rtx into_target,
863                         int unsignedp, enum optab_methods methods)
864 {
865   if (into_target != 0)
866     if (!force_expand_binop (word_mode, binoptab, outof_input, superword_op1,
867                              into_target, unsignedp, methods))
868       return false;
869
870   if (outof_target != 0)
871     {
872       /* For a signed right shift, we must fill OUTOF_TARGET with copies
873          of the sign bit, otherwise we must fill it with zeros.  */
874       if (binoptab != ashr_optab)
875         emit_move_insn (outof_target, CONST0_RTX (word_mode));
876       else
877         if (!force_expand_binop (word_mode, binoptab,
878                                  outof_input, GEN_INT (BITS_PER_WORD - 1),
879                                  outof_target, unsignedp, methods))
880           return false;
881     }
882   return true;
883 }
884
885 /* This subroutine of expand_doubleword_shift handles the cases in which
886    the effective shift value is < BITS_PER_WORD.  The arguments and return
887    value are the same as for the parent routine.  */
888
889 static bool
890 expand_subword_shift (enum machine_mode op1_mode, optab binoptab,
891                       rtx outof_input, rtx into_input, rtx op1,
892                       rtx outof_target, rtx into_target,
893                       int unsignedp, enum optab_methods methods,
894                       unsigned HOST_WIDE_INT shift_mask)
895 {
896   optab reverse_unsigned_shift, unsigned_shift;
897   rtx tmp, carries;
898
899   reverse_unsigned_shift = (binoptab == ashl_optab ? lshr_optab : ashl_optab);
900   unsigned_shift = (binoptab == ashl_optab ? ashl_optab : lshr_optab);
901
902   /* The low OP1 bits of INTO_TARGET come from the high bits of OUTOF_INPUT.
903      We therefore need to shift OUTOF_INPUT by (BITS_PER_WORD - OP1) bits in
904      the opposite direction to BINOPTAB.  */
905   if (CONSTANT_P (op1) || shift_mask >= BITS_PER_WORD)
906     {
907       carries = outof_input;
908       tmp = immed_double_const (BITS_PER_WORD, 0, op1_mode);
909       tmp = simplify_expand_binop (op1_mode, sub_optab, tmp, op1,
910                                    0, true, methods);
911     }
912   else
913     {
914       /* We must avoid shifting by BITS_PER_WORD bits since that is either
915          the same as a zero shift (if shift_mask == BITS_PER_WORD - 1) or
916          has unknown behavior.  Do a single shift first, then shift by the
917          remainder.  It's OK to use ~OP1 as the remainder if shift counts
918          are truncated to the mode size.  */
919       carries = expand_binop (word_mode, reverse_unsigned_shift,
920                               outof_input, const1_rtx, 0, unsignedp, methods);
921       if (shift_mask == BITS_PER_WORD - 1)
922         {
923           tmp = immed_double_const (-1, -1, op1_mode);
924           tmp = simplify_expand_binop (op1_mode, xor_optab, op1, tmp,
925                                        0, true, methods);
926         }
927       else
928         {
929           tmp = immed_double_const (BITS_PER_WORD - 1, 0, op1_mode);
930           tmp = simplify_expand_binop (op1_mode, sub_optab, tmp, op1,
931                                        0, true, methods);
932         }
933     }
934   if (tmp == 0 || carries == 0)
935     return false;
936   carries = expand_binop (word_mode, reverse_unsigned_shift,
937                           carries, tmp, 0, unsignedp, methods);
938   if (carries == 0)
939     return false;
940
941   /* Shift INTO_INPUT logically by OP1.  This is the last use of INTO_INPUT
942      so the result can go directly into INTO_TARGET if convenient.  */
943   tmp = expand_binop (word_mode, unsigned_shift, into_input, op1,
944                       into_target, unsignedp, methods);
945   if (tmp == 0)
946     return false;
947
948   /* Now OR in the bits carried over from OUTOF_INPUT.  */
949   if (!force_expand_binop (word_mode, ior_optab, tmp, carries,
950                            into_target, unsignedp, methods))
951     return false;
952
953   /* Use a standard word_mode shift for the out-of half.  */
954   if (outof_target != 0)
955     if (!force_expand_binop (word_mode, binoptab, outof_input, op1,
956                              outof_target, unsignedp, methods))
957       return false;
958
959   return true;
960 }
961
962
963 #ifdef HAVE_conditional_move
964 /* Try implementing expand_doubleword_shift using conditional moves.
965    The shift is by < BITS_PER_WORD if (CMP_CODE CMP1 CMP2) is true,
966    otherwise it is by >= BITS_PER_WORD.  SUBWORD_OP1 and SUPERWORD_OP1
967    are the shift counts to use in the former and latter case.  All other
968    arguments are the same as the parent routine.  */
969
970 static bool
971 expand_doubleword_shift_condmove (enum machine_mode op1_mode, optab binoptab,
972                                   enum rtx_code cmp_code, rtx cmp1, rtx cmp2,
973                                   rtx outof_input, rtx into_input,
974                                   rtx subword_op1, rtx superword_op1,
975                                   rtx outof_target, rtx into_target,
976                                   int unsignedp, enum optab_methods methods,
977                                   unsigned HOST_WIDE_INT shift_mask)
978 {
979   rtx outof_superword, into_superword;
980
981   /* Put the superword version of the output into OUTOF_SUPERWORD and
982      INTO_SUPERWORD.  */
983   outof_superword = outof_target != 0 ? gen_reg_rtx (word_mode) : 0;
984   if (outof_target != 0 && subword_op1 == superword_op1)
985     {
986       /* The value INTO_TARGET >> SUBWORD_OP1, which we later store in
987          OUTOF_TARGET, is the same as the value of INTO_SUPERWORD.  */
988       into_superword = outof_target;
989       if (!expand_superword_shift (binoptab, outof_input, superword_op1,
990                                    outof_superword, 0, unsignedp, methods))
991         return false;
992     }
993   else
994     {
995       into_superword = gen_reg_rtx (word_mode);
996       if (!expand_superword_shift (binoptab, outof_input, superword_op1,
997                                    outof_superword, into_superword,
998                                    unsignedp, methods))
999         return false;
1000     }
1001
1002   /* Put the subword version directly in OUTOF_TARGET and INTO_TARGET.  */
1003   if (!expand_subword_shift (op1_mode, binoptab,
1004                              outof_input, into_input, subword_op1,
1005                              outof_target, into_target,
1006                              unsignedp, methods, shift_mask))
1007     return false;
1008
1009   /* Select between them.  Do the INTO half first because INTO_SUPERWORD
1010      might be the current value of OUTOF_TARGET.  */
1011   if (!emit_conditional_move (into_target, cmp_code, cmp1, cmp2, op1_mode,
1012                               into_target, into_superword, word_mode, false))
1013     return false;
1014
1015   if (outof_target != 0)
1016     if (!emit_conditional_move (outof_target, cmp_code, cmp1, cmp2, op1_mode,
1017                                 outof_target, outof_superword,
1018                                 word_mode, false))
1019       return false;
1020
1021   return true;
1022 }
1023 #endif
1024
1025 /* Expand a doubleword shift (ashl, ashr or lshr) using word-mode shifts.
1026    OUTOF_INPUT and INTO_INPUT are the two word-sized halves of the first
1027    input operand; the shift moves bits in the direction OUTOF_INPUT->
1028    INTO_TARGET.  OUTOF_TARGET and INTO_TARGET are the equivalent words
1029    of the target.  OP1 is the shift count and OP1_MODE is its mode.
1030    If OP1 is constant, it will have been truncated as appropriate
1031    and is known to be nonzero.
1032
1033    If SHIFT_MASK is zero, the result of word shifts is undefined when the
1034    shift count is outside the range [0, BITS_PER_WORD).  This routine must
1035    avoid generating such shifts for OP1s in the range [0, BITS_PER_WORD * 2).
1036
1037    If SHIFT_MASK is nonzero, all word-mode shift counts are effectively
1038    masked by it and shifts in the range [BITS_PER_WORD, SHIFT_MASK) will
1039    fill with zeros or sign bits as appropriate.
1040
1041    If SHIFT_MASK is BITS_PER_WORD - 1, this routine will synthesize
1042    a doubleword shift whose equivalent mask is BITS_PER_WORD * 2 - 1.
1043    Doing this preserves semantics required by SHIFT_COUNT_TRUNCATED.
1044    In all other cases, shifts by values outside [0, BITS_PER_UNIT * 2)
1045    are undefined.
1046
1047    BINOPTAB, UNSIGNEDP and METHODS are as for expand_binop.  This function
1048    may not use INTO_INPUT after modifying INTO_TARGET, and similarly for
1049    OUTOF_INPUT and OUTOF_TARGET.  OUTOF_TARGET can be null if the parent
1050    function wants to calculate it itself.
1051
1052    Return true if the shift could be successfully synthesized.  */
1053
1054 static bool
1055 expand_doubleword_shift (enum machine_mode op1_mode, optab binoptab,
1056                          rtx outof_input, rtx into_input, rtx op1,
1057                          rtx outof_target, rtx into_target,
1058                          int unsignedp, enum optab_methods methods,
1059                          unsigned HOST_WIDE_INT shift_mask)
1060 {
1061   rtx superword_op1, tmp, cmp1, cmp2;
1062   rtx subword_label, done_label;
1063   enum rtx_code cmp_code;
1064
1065   /* See if word-mode shifts by BITS_PER_WORD...BITS_PER_WORD * 2 - 1 will
1066      fill the result with sign or zero bits as appropriate.  If so, the value
1067      of OUTOF_TARGET will always be (SHIFT OUTOF_INPUT OP1).   Recursively call
1068      this routine to calculate INTO_TARGET (which depends on both OUTOF_INPUT
1069      and INTO_INPUT), then emit code to set up OUTOF_TARGET.
1070
1071      This isn't worthwhile for constant shifts since the optimizers will
1072      cope better with in-range shift counts.  */
1073   if (shift_mask >= BITS_PER_WORD
1074       && outof_target != 0
1075       && !CONSTANT_P (op1))
1076     {
1077       if (!expand_doubleword_shift (op1_mode, binoptab,
1078                                     outof_input, into_input, op1,
1079                                     0, into_target,
1080                                     unsignedp, methods, shift_mask))
1081         return false;
1082       if (!force_expand_binop (word_mode, binoptab, outof_input, op1,
1083                                outof_target, unsignedp, methods))
1084         return false;
1085       return true;
1086     }
1087
1088   /* Set CMP_CODE, CMP1 and CMP2 so that the rtx (CMP_CODE CMP1 CMP2)
1089      is true when the effective shift value is less than BITS_PER_WORD.
1090      Set SUPERWORD_OP1 to the shift count that should be used to shift
1091      OUTOF_INPUT into INTO_TARGET when the condition is false.  */
1092   tmp = immed_double_const (BITS_PER_WORD, 0, op1_mode);
1093   if (!CONSTANT_P (op1) && shift_mask == BITS_PER_WORD - 1)
1094     {
1095       /* Set CMP1 to OP1 & BITS_PER_WORD.  The result is zero iff OP1
1096          is a subword shift count.  */
1097       cmp1 = simplify_expand_binop (op1_mode, and_optab, op1, tmp,
1098                                     0, true, methods);
1099       cmp2 = CONST0_RTX (op1_mode);
1100       cmp_code = EQ;
1101       superword_op1 = op1;
1102     }
1103   else
1104     {
1105       /* Set CMP1 to OP1 - BITS_PER_WORD.  */
1106       cmp1 = simplify_expand_binop (op1_mode, sub_optab, op1, tmp,
1107                                     0, true, methods);
1108       cmp2 = CONST0_RTX (op1_mode);
1109       cmp_code = LT;
1110       superword_op1 = cmp1;
1111     }
1112   if (cmp1 == 0)
1113     return false;
1114
1115   /* If we can compute the condition at compile time, pick the
1116      appropriate subroutine.  */
1117   tmp = simplify_relational_operation (cmp_code, SImode, op1_mode, cmp1, cmp2);
1118   if (tmp != 0 && GET_CODE (tmp) == CONST_INT)
1119     {
1120       if (tmp == const0_rtx)
1121         return expand_superword_shift (binoptab, outof_input, superword_op1,
1122                                        outof_target, into_target,
1123                                        unsignedp, methods);
1124       else
1125         return expand_subword_shift (op1_mode, binoptab,
1126                                      outof_input, into_input, op1,
1127                                      outof_target, into_target,
1128                                      unsignedp, methods, shift_mask);
1129     }
1130
1131 #ifdef HAVE_conditional_move
1132   /* Try using conditional moves to generate straight-line code.  */
1133   {
1134     rtx start = get_last_insn ();
1135     if (expand_doubleword_shift_condmove (op1_mode, binoptab,
1136                                           cmp_code, cmp1, cmp2,
1137                                           outof_input, into_input,
1138                                           op1, superword_op1,
1139                                           outof_target, into_target,
1140                                           unsignedp, methods, shift_mask))
1141       return true;
1142     delete_insns_since (start);
1143   }
1144 #endif
1145
1146   /* As a last resort, use branches to select the correct alternative.  */
1147   subword_label = gen_label_rtx ();
1148   done_label = gen_label_rtx ();
1149
1150   NO_DEFER_POP;
1151   do_compare_rtx_and_jump (cmp1, cmp2, cmp_code, false, op1_mode,
1152                            0, 0, subword_label, -1);
1153   OK_DEFER_POP;
1154
1155   if (!expand_superword_shift (binoptab, outof_input, superword_op1,
1156                                outof_target, into_target,
1157                                unsignedp, methods))
1158     return false;
1159
1160   emit_jump_insn (gen_jump (done_label));
1161   emit_barrier ();
1162   emit_label (subword_label);
1163
1164   if (!expand_subword_shift (op1_mode, binoptab,
1165                              outof_input, into_input, op1,
1166                              outof_target, into_target,
1167                              unsignedp, methods, shift_mask))
1168     return false;
1169
1170   emit_label (done_label);
1171   return true;
1172 }
1173 \f
1174 /* Subroutine of expand_binop.  Perform a double word multiplication of
1175    operands OP0 and OP1 both of mode MODE, which is exactly twice as wide
1176    as the target's word_mode.  This function return NULL_RTX if anything
1177    goes wrong, in which case it may have already emitted instructions
1178    which need to be deleted.
1179
1180    If we want to multiply two two-word values and have normal and widening
1181    multiplies of single-word values, we can do this with three smaller
1182    multiplications.
1183
1184    The multiplication proceeds as follows:
1185                                  _______________________
1186                                 [__op0_high_|__op0_low__]
1187                                  _______________________
1188         *                       [__op1_high_|__op1_low__]
1189         _______________________________________________
1190                                  _______________________
1191     (1)                         [__op0_low__*__op1_low__]
1192                      _______________________
1193     (2a)            [__op0_low__*__op1_high_]
1194                      _______________________
1195     (2b)            [__op0_high_*__op1_low__]
1196          _______________________
1197     (3) [__op0_high_*__op1_high_]
1198
1199
1200   This gives a 4-word result.  Since we are only interested in the
1201   lower 2 words, partial result (3) and the upper words of (2a) and
1202   (2b) don't need to be calculated.  Hence (2a) and (2b) can be
1203   calculated using non-widening multiplication.
1204
1205   (1), however, needs to be calculated with an unsigned widening
1206   multiplication.  If this operation is not directly supported we
1207   try using a signed widening multiplication and adjust the result.
1208   This adjustment works as follows:
1209
1210       If both operands are positive then no adjustment is needed.
1211
1212       If the operands have different signs, for example op0_low < 0 and
1213       op1_low >= 0, the instruction treats the most significant bit of
1214       op0_low as a sign bit instead of a bit with significance
1215       2**(BITS_PER_WORD-1), i.e. the instruction multiplies op1_low
1216       with 2**BITS_PER_WORD - op0_low, and two's complements the
1217       result.  Conclusion: We need to add op1_low * 2**BITS_PER_WORD to
1218       the result.
1219
1220       Similarly, if both operands are negative, we need to add
1221       (op0_low + op1_low) * 2**BITS_PER_WORD.
1222
1223       We use a trick to adjust quickly.  We logically shift op0_low right
1224       (op1_low) BITS_PER_WORD-1 steps to get 0 or 1, and add this to
1225       op0_high (op1_high) before it is used to calculate 2b (2a).  If no
1226       logical shift exists, we do an arithmetic right shift and subtract
1227       the 0 or -1.  */
1228
1229 static rtx
1230 expand_doubleword_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
1231                        bool umulp, enum optab_methods methods)
1232 {
1233   int low = (WORDS_BIG_ENDIAN ? 1 : 0);
1234   int high = (WORDS_BIG_ENDIAN ? 0 : 1);
1235   rtx wordm1 = umulp ? NULL_RTX : GEN_INT (BITS_PER_WORD - 1);
1236   rtx product, adjust, product_high, temp;
1237
1238   rtx op0_high = operand_subword_force (op0, high, mode);
1239   rtx op0_low = operand_subword_force (op0, low, mode);
1240   rtx op1_high = operand_subword_force (op1, high, mode);
1241   rtx op1_low = operand_subword_force (op1, low, mode);
1242
1243   /* If we're using an unsigned multiply to directly compute the product
1244      of the low-order words of the operands and perform any required
1245      adjustments of the operands, we begin by trying two more multiplications
1246      and then computing the appropriate sum.
1247
1248      We have checked above that the required addition is provided.
1249      Full-word addition will normally always succeed, especially if
1250      it is provided at all, so we don't worry about its failure.  The
1251      multiplication may well fail, however, so we do handle that.  */
1252
1253   if (!umulp)
1254     {
1255       /* ??? This could be done with emit_store_flag where available.  */
1256       temp = expand_binop (word_mode, lshr_optab, op0_low, wordm1,
1257                            NULL_RTX, 1, methods);
1258       if (temp)
1259         op0_high = expand_binop (word_mode, add_optab, op0_high, temp,
1260                                  NULL_RTX, 0, OPTAB_DIRECT);
1261       else
1262         {
1263           temp = expand_binop (word_mode, ashr_optab, op0_low, wordm1,
1264                                NULL_RTX, 0, methods);
1265           if (!temp)
1266             return NULL_RTX;
1267           op0_high = expand_binop (word_mode, sub_optab, op0_high, temp,
1268                                    NULL_RTX, 0, OPTAB_DIRECT);
1269         }
1270
1271       if (!op0_high)
1272         return NULL_RTX;
1273     }
1274
1275   adjust = expand_binop (word_mode, smul_optab, op0_high, op1_low,
1276                          NULL_RTX, 0, OPTAB_DIRECT);
1277   if (!adjust)
1278     return NULL_RTX;
1279
1280   /* OP0_HIGH should now be dead.  */
1281
1282   if (!umulp)
1283     {
1284       /* ??? This could be done with emit_store_flag where available.  */
1285       temp = expand_binop (word_mode, lshr_optab, op1_low, wordm1,
1286                            NULL_RTX, 1, methods);
1287       if (temp)
1288         op1_high = expand_binop (word_mode, add_optab, op1_high, temp,
1289                                  NULL_RTX, 0, OPTAB_DIRECT);
1290       else
1291         {
1292           temp = expand_binop (word_mode, ashr_optab, op1_low, wordm1,
1293                                NULL_RTX, 0, methods);
1294           if (!temp)
1295             return NULL_RTX;
1296           op1_high = expand_binop (word_mode, sub_optab, op1_high, temp,
1297                                    NULL_RTX, 0, OPTAB_DIRECT);
1298         }
1299
1300       if (!op1_high)
1301         return NULL_RTX;
1302     }
1303
1304   temp = expand_binop (word_mode, smul_optab, op1_high, op0_low,
1305                        NULL_RTX, 0, OPTAB_DIRECT);
1306   if (!temp)
1307     return NULL_RTX;
1308
1309   /* OP1_HIGH should now be dead.  */
1310
1311   adjust = expand_binop (word_mode, add_optab, adjust, temp,
1312                          adjust, 0, OPTAB_DIRECT);
1313
1314   if (target && !REG_P (target))
1315     target = NULL_RTX;
1316
1317   if (umulp)
1318     product = expand_binop (mode, umul_widen_optab, op0_low, op1_low,
1319                             target, 1, OPTAB_DIRECT);
1320   else
1321     product = expand_binop (mode, smul_widen_optab, op0_low, op1_low,
1322                             target, 1, OPTAB_DIRECT);
1323
1324   if (!product)
1325     return NULL_RTX;
1326
1327   product_high = operand_subword (product, high, 1, mode);
1328   adjust = expand_binop (word_mode, add_optab, product_high, adjust,
1329                          REG_P (product_high) ? product_high : adjust,
1330                          0, OPTAB_DIRECT);
1331   emit_move_insn (product_high, adjust);
1332   return product;
1333 }
1334 \f
1335 /* Wrapper around expand_binop which takes an rtx code to specify
1336    the operation to perform, not an optab pointer.  All other
1337    arguments are the same.  */
1338 rtx
1339 expand_simple_binop (enum machine_mode mode, enum rtx_code code, rtx op0,
1340                      rtx op1, rtx target, int unsignedp,
1341                      enum optab_methods methods)
1342 {
1343   optab binop = code_to_optab[(int) code];
1344   gcc_assert (binop);
1345
1346   return expand_binop (mode, binop, op0, op1, target, unsignedp, methods);
1347 }
1348
1349 /* Return whether OP0 and OP1 should be swapped when expanding a commutative
1350    binop.  Order them according to commutative_operand_precedence and, if
1351    possible, try to put TARGET or a pseudo first.  */
1352 static bool
1353 swap_commutative_operands_with_target (rtx target, rtx op0, rtx op1)
1354 {
1355   int op0_prec = commutative_operand_precedence (op0);
1356   int op1_prec = commutative_operand_precedence (op1);
1357
1358   if (op0_prec < op1_prec)
1359     return true;
1360
1361   if (op0_prec > op1_prec)
1362     return false;
1363
1364   /* With equal precedence, both orders are ok, but it is better if the
1365      first operand is TARGET, or if both TARGET and OP0 are pseudos.  */
1366   if (target == 0 || REG_P (target))
1367     return (REG_P (op1) && !REG_P (op0)) || target == op1;
1368   else
1369     return rtx_equal_p (op1, target);
1370 }
1371
1372 /* Return true if BINOPTAB implements a shift operation.  */
1373
1374 static bool
1375 shift_optab_p (optab binoptab)
1376 {
1377   switch (binoptab->code)
1378     {
1379     case ASHIFT:
1380     case SS_ASHIFT:
1381     case US_ASHIFT:
1382     case ASHIFTRT:
1383     case LSHIFTRT:
1384     case ROTATE:
1385     case ROTATERT:
1386       return true;
1387
1388     default:
1389       return false;
1390     }
1391 }
1392
1393 /* Return true if BINOPTAB implements a commutative binary operation.  */
1394
1395 static bool
1396 commutative_optab_p (optab binoptab)
1397 {
1398   return (GET_RTX_CLASS (binoptab->code) == RTX_COMM_ARITH
1399           || binoptab == smul_widen_optab
1400           || binoptab == umul_widen_optab
1401           || binoptab == smul_highpart_optab
1402           || binoptab == umul_highpart_optab);
1403 }
1404
1405 /* X is to be used in mode MODE as an operand to BINOPTAB.  If we're
1406    optimizing, and if the operand is a constant that costs more than
1407    1 instruction, force the constant into a register and return that
1408    register.  Return X otherwise.  UNSIGNEDP says whether X is unsigned.  */
1409
1410 static rtx
1411 avoid_expensive_constant (enum machine_mode mode, optab binoptab,
1412                           rtx x, bool unsignedp)
1413 {
1414   if (mode != VOIDmode
1415       && optimize
1416       && CONSTANT_P (x)
1417       && rtx_cost (x, binoptab->code, optimize_insn_for_speed_p ())
1418                    > COSTS_N_INSNS (1))
1419     {
1420       if (GET_CODE (x) == CONST_INT)
1421         {
1422           HOST_WIDE_INT intval = trunc_int_for_mode (INTVAL (x), mode);
1423           if (intval != INTVAL (x))
1424             x = GEN_INT (intval);
1425         }
1426       else
1427         x = convert_modes (mode, VOIDmode, x, unsignedp);
1428       x = force_reg (mode, x);
1429     }
1430   return x;
1431 }
1432
1433 /* Helper function for expand_binop: handle the case where there
1434    is an insn that directly implements the indicated operation.
1435    Returns null if this is not possible.  */
1436 static rtx
1437 expand_binop_directly (enum machine_mode mode, optab binoptab,
1438                        rtx op0, rtx op1,
1439                        rtx target, int unsignedp, enum optab_methods methods,
1440                        rtx last)
1441 {
1442   int icode = (int) optab_handler (binoptab, mode)->insn_code;
1443   enum machine_mode mode0 = insn_data[icode].operand[1].mode;
1444   enum machine_mode mode1 = insn_data[icode].operand[2].mode;
1445   enum machine_mode tmp_mode;
1446   bool commutative_p;
1447   rtx pat;
1448   rtx xop0 = op0, xop1 = op1;
1449   rtx temp;
1450   rtx swap;
1451   
1452   if (target)
1453     temp = target;
1454   else
1455     temp = gen_reg_rtx (mode);
1456
1457   /* If it is a commutative operator and the modes would match
1458      if we would swap the operands, we can save the conversions.  */
1459   commutative_p = commutative_optab_p (binoptab);
1460   if (commutative_p
1461       && GET_MODE (xop0) != mode0 && GET_MODE (xop1) != mode1
1462       && GET_MODE (xop0) == mode1 && GET_MODE (xop1) == mode1)
1463     {
1464       swap = xop0;
1465       xop0 = xop1;
1466       xop1 = swap;
1467     }
1468   
1469   /* If we are optimizing, force expensive constants into a register.  */
1470   xop0 = avoid_expensive_constant (mode0, binoptab, xop0, unsignedp);
1471   if (!shift_optab_p (binoptab))
1472     xop1 = avoid_expensive_constant (mode1, binoptab, xop1, unsignedp);
1473
1474   /* In case the insn wants input operands in modes different from
1475      those of the actual operands, convert the operands.  It would
1476      seem that we don't need to convert CONST_INTs, but we do, so
1477      that they're properly zero-extended, sign-extended or truncated
1478      for their mode.  */
1479   
1480   if (GET_MODE (xop0) != mode0 && mode0 != VOIDmode)
1481     xop0 = convert_modes (mode0,
1482                           GET_MODE (xop0) != VOIDmode
1483                           ? GET_MODE (xop0)
1484                           : mode,
1485                           xop0, unsignedp);
1486   
1487   if (GET_MODE (xop1) != mode1 && mode1 != VOIDmode)
1488     xop1 = convert_modes (mode1,
1489                           GET_MODE (xop1) != VOIDmode
1490                           ? GET_MODE (xop1)
1491                           : mode,
1492                           xop1, unsignedp);
1493   
1494   /* If operation is commutative,
1495      try to make the first operand a register.
1496      Even better, try to make it the same as the target.
1497      Also try to make the last operand a constant.  */
1498   if (commutative_p
1499       && swap_commutative_operands_with_target (target, xop0, xop1))
1500     {
1501       swap = xop1;
1502       xop1 = xop0;
1503       xop0 = swap;
1504     }
1505
1506   /* Now, if insn's predicates don't allow our operands, put them into
1507      pseudo regs.  */
1508   
1509   if (!insn_data[icode].operand[1].predicate (xop0, mode0)
1510       && mode0 != VOIDmode)
1511     xop0 = copy_to_mode_reg (mode0, xop0);
1512   
1513   if (!insn_data[icode].operand[2].predicate (xop1, mode1)
1514       && mode1 != VOIDmode)
1515     xop1 = copy_to_mode_reg (mode1, xop1);
1516   
1517   if (binoptab == vec_pack_trunc_optab 
1518       || binoptab == vec_pack_usat_optab
1519       || binoptab == vec_pack_ssat_optab
1520       || binoptab == vec_pack_ufix_trunc_optab
1521       || binoptab == vec_pack_sfix_trunc_optab)
1522     {
1523       /* The mode of the result is different then the mode of the
1524          arguments.  */
1525       tmp_mode = insn_data[icode].operand[0].mode;
1526       if (GET_MODE_NUNITS (tmp_mode) != 2 * GET_MODE_NUNITS (mode))
1527         return 0;
1528     }
1529   else
1530     tmp_mode = mode;
1531
1532   if (!insn_data[icode].operand[0].predicate (temp, tmp_mode))
1533     temp = gen_reg_rtx (tmp_mode);
1534   
1535   pat = GEN_FCN (icode) (temp, xop0, xop1);
1536   if (pat)
1537     {
1538       /* If PAT is composed of more than one insn, try to add an appropriate
1539          REG_EQUAL note to it.  If we can't because TEMP conflicts with an
1540          operand, call expand_binop again, this time without a target.  */
1541       if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX
1542           && ! add_equal_note (pat, temp, binoptab->code, xop0, xop1))
1543         {
1544           delete_insns_since (last);
1545           return expand_binop (mode, binoptab, op0, op1, NULL_RTX,
1546                                unsignedp, methods);
1547         }
1548       
1549       emit_insn (pat);
1550       return temp;
1551     }
1552
1553   delete_insns_since (last);
1554   return NULL_RTX;
1555 }
1556
1557 /* Generate code to perform an operation specified by BINOPTAB
1558    on operands OP0 and OP1, with result having machine-mode MODE.
1559
1560    UNSIGNEDP is for the case where we have to widen the operands
1561    to perform the operation.  It says to use zero-extension.
1562
1563    If TARGET is nonzero, the value
1564    is generated there, if it is convenient to do so.
1565    In all cases an rtx is returned for the locus of the value;
1566    this may or may not be TARGET.  */
1567
1568 rtx
1569 expand_binop (enum machine_mode mode, optab binoptab, rtx op0, rtx op1,
1570               rtx target, int unsignedp, enum optab_methods methods)
1571 {
1572   enum optab_methods next_methods
1573     = (methods == OPTAB_LIB || methods == OPTAB_LIB_WIDEN
1574        ? OPTAB_WIDEN : methods);
1575   enum mode_class mclass;
1576   enum machine_mode wider_mode;
1577   rtx libfunc;
1578   rtx temp;
1579   rtx entry_last = get_last_insn ();
1580   rtx last;
1581
1582   mclass = GET_MODE_CLASS (mode);
1583
1584   /* If subtracting an integer constant, convert this into an addition of
1585      the negated constant.  */
1586
1587   if (binoptab == sub_optab && GET_CODE (op1) == CONST_INT)
1588     {
1589       op1 = negate_rtx (mode, op1);
1590       binoptab = add_optab;
1591     }
1592
1593   /* Record where to delete back to if we backtrack.  */
1594   last = get_last_insn ();
1595
1596   /* If we can do it with a three-operand insn, do so.  */
1597
1598   if (methods != OPTAB_MUST_WIDEN
1599       && optab_handler (binoptab, mode)->insn_code != CODE_FOR_nothing)
1600     {
1601       temp = expand_binop_directly (mode, binoptab, op0, op1, target,
1602                                     unsignedp, methods, last);
1603       if (temp)
1604         return temp;
1605     }
1606
1607   /* If we were trying to rotate, and that didn't work, try rotating
1608      the other direction before falling back to shifts and bitwise-or.  */
1609   if (((binoptab == rotl_optab
1610         && optab_handler (rotr_optab, mode)->insn_code != CODE_FOR_nothing)
1611        || (binoptab == rotr_optab
1612            && optab_handler (rotl_optab, mode)->insn_code != CODE_FOR_nothing))
1613       && mclass == MODE_INT)
1614     {
1615       optab otheroptab = (binoptab == rotl_optab ? rotr_optab : rotl_optab);
1616       rtx newop1;
1617       unsigned int bits = GET_MODE_BITSIZE (mode);
1618
1619       if (GET_CODE (op1) == CONST_INT)
1620         newop1 = GEN_INT (bits - INTVAL (op1));
1621       else if (targetm.shift_truncation_mask (mode) == bits - 1)
1622         newop1 = negate_rtx (mode, op1);
1623       else
1624         newop1 = expand_binop (mode, sub_optab,
1625                                GEN_INT (bits), op1,
1626                                NULL_RTX, unsignedp, OPTAB_DIRECT);
1627                                    
1628       temp = expand_binop_directly (mode, otheroptab, op0, newop1,
1629                                     target, unsignedp, methods, last);
1630       if (temp)
1631         return temp;
1632     }
1633
1634   /* If this is a multiply, see if we can do a widening operation that
1635      takes operands of this mode and makes a wider mode.  */
1636
1637   if (binoptab == smul_optab
1638       && GET_MODE_WIDER_MODE (mode) != VOIDmode
1639       && ((optab_handler ((unsignedp ? umul_widen_optab : smul_widen_optab),
1640                           GET_MODE_WIDER_MODE (mode))->insn_code)
1641           != CODE_FOR_nothing))
1642     {
1643       temp = expand_binop (GET_MODE_WIDER_MODE (mode),
1644                            unsignedp ? umul_widen_optab : smul_widen_optab,
1645                            op0, op1, NULL_RTX, unsignedp, OPTAB_DIRECT);
1646
1647       if (temp != 0)
1648         {
1649           if (GET_MODE_CLASS (mode) == MODE_INT
1650               && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1651                                         GET_MODE_BITSIZE (GET_MODE (temp))))
1652             return gen_lowpart (mode, temp);
1653           else
1654             return convert_to_mode (mode, temp, unsignedp);
1655         }
1656     }
1657
1658   /* Look for a wider mode of the same class for which we think we
1659      can open-code the operation.  Check for a widening multiply at the
1660      wider mode as well.  */
1661
1662   if (CLASS_HAS_WIDER_MODES_P (mclass)
1663       && methods != OPTAB_DIRECT && methods != OPTAB_LIB)
1664     for (wider_mode = GET_MODE_WIDER_MODE (mode);
1665          wider_mode != VOIDmode;
1666          wider_mode = GET_MODE_WIDER_MODE (wider_mode))
1667       {
1668         if (optab_handler (binoptab, wider_mode)->insn_code != CODE_FOR_nothing
1669             || (binoptab == smul_optab
1670                 && GET_MODE_WIDER_MODE (wider_mode) != VOIDmode
1671                 && ((optab_handler ((unsignedp ? umul_widen_optab
1672                                      : smul_widen_optab),
1673                                      GET_MODE_WIDER_MODE (wider_mode))->insn_code)
1674                     != CODE_FOR_nothing)))
1675           {
1676             rtx xop0 = op0, xop1 = op1;
1677             int no_extend = 0;
1678
1679             /* For certain integer operations, we need not actually extend
1680                the narrow operands, as long as we will truncate
1681                the results to the same narrowness.  */
1682
1683             if ((binoptab == ior_optab || binoptab == and_optab
1684                  || binoptab == xor_optab
1685                  || binoptab == add_optab || binoptab == sub_optab
1686                  || binoptab == smul_optab || binoptab == ashl_optab)
1687                 && mclass == MODE_INT)
1688               {
1689                 no_extend = 1;
1690                 xop0 = avoid_expensive_constant (mode, binoptab,
1691                                                  xop0, unsignedp);
1692                 if (binoptab != ashl_optab)
1693                   xop1 = avoid_expensive_constant (mode, binoptab,
1694                                                    xop1, unsignedp);
1695               }
1696
1697             xop0 = widen_operand (xop0, wider_mode, mode, unsignedp, no_extend);
1698
1699             /* The second operand of a shift must always be extended.  */
1700             xop1 = widen_operand (xop1, wider_mode, mode, unsignedp,
1701                                   no_extend && binoptab != ashl_optab);
1702
1703             temp = expand_binop (wider_mode, binoptab, xop0, xop1, NULL_RTX,
1704                                  unsignedp, OPTAB_DIRECT);
1705             if (temp)
1706               {
1707                 if (mclass != MODE_INT
1708                     || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1709                                                GET_MODE_BITSIZE (wider_mode)))
1710                   {
1711                     if (target == 0)
1712                       target = gen_reg_rtx (mode);
1713                     convert_move (target, temp, 0);
1714                     return target;
1715                   }
1716                 else
1717                   return gen_lowpart (mode, temp);
1718               }
1719             else
1720               delete_insns_since (last);
1721           }
1722       }
1723
1724   /* If operation is commutative,
1725      try to make the first operand a register.
1726      Even better, try to make it the same as the target.
1727      Also try to make the last operand a constant.  */
1728   if (commutative_optab_p (binoptab)
1729       && swap_commutative_operands_with_target (target, op0, op1))
1730     {
1731       temp = op1;
1732       op1 = op0;
1733       op0 = temp;
1734     }
1735
1736   /* These can be done a word at a time.  */
1737   if ((binoptab == and_optab || binoptab == ior_optab || binoptab == xor_optab)
1738       && mclass == MODE_INT
1739       && GET_MODE_SIZE (mode) > UNITS_PER_WORD
1740       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing)
1741     {
1742       int i;
1743       rtx insns;
1744       rtx equiv_value;
1745
1746       /* If TARGET is the same as one of the operands, the REG_EQUAL note
1747          won't be accurate, so use a new target.  */
1748       if (target == 0 || target == op0 || target == op1)
1749         target = gen_reg_rtx (mode);
1750
1751       start_sequence ();
1752
1753       /* Do the actual arithmetic.  */
1754       for (i = 0; i < GET_MODE_BITSIZE (mode) / BITS_PER_WORD; i++)
1755         {
1756           rtx target_piece = operand_subword (target, i, 1, mode);
1757           rtx x = expand_binop (word_mode, binoptab,
1758                                 operand_subword_force (op0, i, mode),
1759                                 operand_subword_force (op1, i, mode),
1760                                 target_piece, unsignedp, next_methods);
1761
1762           if (x == 0)
1763             break;
1764
1765           if (target_piece != x)
1766             emit_move_insn (target_piece, x);
1767         }
1768
1769       insns = get_insns ();
1770       end_sequence ();
1771
1772       if (i == GET_MODE_BITSIZE (mode) / BITS_PER_WORD)
1773         {
1774           if (binoptab->code != UNKNOWN)
1775             equiv_value
1776               = gen_rtx_fmt_ee (binoptab->code, mode,
1777                                 copy_rtx (op0), copy_rtx (op1));
1778           else
1779             equiv_value = 0;
1780
1781           emit_insn (insns);
1782           return target;
1783         }
1784     }
1785
1786   /* Synthesize double word shifts from single word shifts.  */
1787   if ((binoptab == lshr_optab || binoptab == ashl_optab
1788        || binoptab == ashr_optab)
1789       && mclass == MODE_INT
1790       && (GET_CODE (op1) == CONST_INT || optimize_insn_for_speed_p ())
1791       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
1792       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing
1793       && optab_handler (ashl_optab, word_mode)->insn_code != CODE_FOR_nothing
1794       && optab_handler (lshr_optab, word_mode)->insn_code != CODE_FOR_nothing)
1795     {
1796       unsigned HOST_WIDE_INT shift_mask, double_shift_mask;
1797       enum machine_mode op1_mode;
1798
1799       double_shift_mask = targetm.shift_truncation_mask (mode);
1800       shift_mask = targetm.shift_truncation_mask (word_mode);
1801       op1_mode = GET_MODE (op1) != VOIDmode ? GET_MODE (op1) : word_mode;
1802
1803       /* Apply the truncation to constant shifts.  */
1804       if (double_shift_mask > 0 && GET_CODE (op1) == CONST_INT)
1805         op1 = GEN_INT (INTVAL (op1) & double_shift_mask);
1806
1807       if (op1 == CONST0_RTX (op1_mode))
1808         return op0;
1809
1810       /* Make sure that this is a combination that expand_doubleword_shift
1811          can handle.  See the comments there for details.  */
1812       if (double_shift_mask == 0
1813           || (shift_mask == BITS_PER_WORD - 1
1814               && double_shift_mask == BITS_PER_WORD * 2 - 1))
1815         {
1816           rtx insns;
1817           rtx into_target, outof_target;
1818           rtx into_input, outof_input;
1819           int left_shift, outof_word;
1820
1821           /* If TARGET is the same as one of the operands, the REG_EQUAL note
1822              won't be accurate, so use a new target.  */
1823           if (target == 0 || target == op0 || target == op1)
1824             target = gen_reg_rtx (mode);
1825
1826           start_sequence ();
1827
1828           /* OUTOF_* is the word we are shifting bits away from, and
1829              INTO_* is the word that we are shifting bits towards, thus
1830              they differ depending on the direction of the shift and
1831              WORDS_BIG_ENDIAN.  */
1832
1833           left_shift = binoptab == ashl_optab;
1834           outof_word = left_shift ^ ! WORDS_BIG_ENDIAN;
1835
1836           outof_target = operand_subword (target, outof_word, 1, mode);
1837           into_target = operand_subword (target, 1 - outof_word, 1, mode);
1838
1839           outof_input = operand_subword_force (op0, outof_word, mode);
1840           into_input = operand_subword_force (op0, 1 - outof_word, mode);
1841
1842           if (expand_doubleword_shift (op1_mode, binoptab,
1843                                        outof_input, into_input, op1,
1844                                        outof_target, into_target,
1845                                        unsignedp, next_methods, shift_mask))
1846             {
1847               insns = get_insns ();
1848               end_sequence ();
1849
1850               emit_insn (insns);
1851               return target;
1852             }
1853           end_sequence ();
1854         }
1855     }
1856
1857   /* Synthesize double word rotates from single word shifts.  */
1858   if ((binoptab == rotl_optab || binoptab == rotr_optab)
1859       && mclass == MODE_INT
1860       && GET_CODE (op1) == CONST_INT
1861       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
1862       && optab_handler (ashl_optab, word_mode)->insn_code != CODE_FOR_nothing
1863       && optab_handler (lshr_optab, word_mode)->insn_code != CODE_FOR_nothing)
1864     {
1865       rtx insns;
1866       rtx into_target, outof_target;
1867       rtx into_input, outof_input;
1868       rtx inter;
1869       int shift_count, left_shift, outof_word;
1870
1871       /* If TARGET is the same as one of the operands, the REG_EQUAL note
1872          won't be accurate, so use a new target. Do this also if target is not
1873          a REG, first because having a register instead may open optimization
1874          opportunities, and second because if target and op0 happen to be MEMs
1875          designating the same location, we would risk clobbering it too early
1876          in the code sequence we generate below.  */
1877       if (target == 0 || target == op0 || target == op1 || ! REG_P (target))
1878         target = gen_reg_rtx (mode);
1879
1880       start_sequence ();
1881
1882       shift_count = INTVAL (op1);
1883
1884       /* OUTOF_* is the word we are shifting bits away from, and
1885          INTO_* is the word that we are shifting bits towards, thus
1886          they differ depending on the direction of the shift and
1887          WORDS_BIG_ENDIAN.  */
1888
1889       left_shift = (binoptab == rotl_optab);
1890       outof_word = left_shift ^ ! WORDS_BIG_ENDIAN;
1891
1892       outof_target = operand_subword (target, outof_word, 1, mode);
1893       into_target = operand_subword (target, 1 - outof_word, 1, mode);
1894
1895       outof_input = operand_subword_force (op0, outof_word, mode);
1896       into_input = operand_subword_force (op0, 1 - outof_word, mode);
1897
1898       if (shift_count == BITS_PER_WORD)
1899         {
1900           /* This is just a word swap.  */
1901           emit_move_insn (outof_target, into_input);
1902           emit_move_insn (into_target, outof_input);
1903           inter = const0_rtx;
1904         }
1905       else
1906         {
1907           rtx into_temp1, into_temp2, outof_temp1, outof_temp2;
1908           rtx first_shift_count, second_shift_count;
1909           optab reverse_unsigned_shift, unsigned_shift;
1910
1911           reverse_unsigned_shift = (left_shift ^ (shift_count < BITS_PER_WORD)
1912                                     ? lshr_optab : ashl_optab);
1913
1914           unsigned_shift = (left_shift ^ (shift_count < BITS_PER_WORD)
1915                             ? ashl_optab : lshr_optab);
1916
1917           if (shift_count > BITS_PER_WORD)
1918             {
1919               first_shift_count = GEN_INT (shift_count - BITS_PER_WORD);
1920               second_shift_count = GEN_INT (2 * BITS_PER_WORD - shift_count);
1921             }
1922           else
1923             {
1924               first_shift_count = GEN_INT (BITS_PER_WORD - shift_count);
1925               second_shift_count = GEN_INT (shift_count);
1926             }
1927
1928           into_temp1 = expand_binop (word_mode, unsigned_shift,
1929                                      outof_input, first_shift_count,
1930                                      NULL_RTX, unsignedp, next_methods);
1931           into_temp2 = expand_binop (word_mode, reverse_unsigned_shift,
1932                                      into_input, second_shift_count,
1933                                      NULL_RTX, unsignedp, next_methods);
1934
1935           if (into_temp1 != 0 && into_temp2 != 0)
1936             inter = expand_binop (word_mode, ior_optab, into_temp1, into_temp2,
1937                                   into_target, unsignedp, next_methods);
1938           else
1939             inter = 0;
1940
1941           if (inter != 0 && inter != into_target)
1942             emit_move_insn (into_target, inter);
1943
1944           outof_temp1 = expand_binop (word_mode, unsigned_shift,
1945                                       into_input, first_shift_count,
1946                                       NULL_RTX, unsignedp, next_methods);
1947           outof_temp2 = expand_binop (word_mode, reverse_unsigned_shift,
1948                                       outof_input, second_shift_count,
1949                                       NULL_RTX, unsignedp, next_methods);
1950
1951           if (inter != 0 && outof_temp1 != 0 && outof_temp2 != 0)
1952             inter = expand_binop (word_mode, ior_optab,
1953                                   outof_temp1, outof_temp2,
1954                                   outof_target, unsignedp, next_methods);
1955
1956           if (inter != 0 && inter != outof_target)
1957             emit_move_insn (outof_target, inter);
1958         }
1959
1960       insns = get_insns ();
1961       end_sequence ();
1962
1963       if (inter != 0)
1964         {
1965           emit_insn (insns);
1966           return target;
1967         }
1968     }
1969
1970   /* These can be done a word at a time by propagating carries.  */
1971   if ((binoptab == add_optab || binoptab == sub_optab)
1972       && mclass == MODE_INT
1973       && GET_MODE_SIZE (mode) >= 2 * UNITS_PER_WORD
1974       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing)
1975     {
1976       unsigned int i;
1977       optab otheroptab = binoptab == add_optab ? sub_optab : add_optab;
1978       const unsigned int nwords = GET_MODE_BITSIZE (mode) / BITS_PER_WORD;
1979       rtx carry_in = NULL_RTX, carry_out = NULL_RTX;
1980       rtx xop0, xop1, xtarget;
1981
1982       /* We can handle either a 1 or -1 value for the carry.  If STORE_FLAG
1983          value is one of those, use it.  Otherwise, use 1 since it is the
1984          one easiest to get.  */
1985 #if STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1
1986       int normalizep = STORE_FLAG_VALUE;
1987 #else
1988       int normalizep = 1;
1989 #endif
1990
1991       /* Prepare the operands.  */
1992       xop0 = force_reg (mode, op0);
1993       xop1 = force_reg (mode, op1);
1994
1995       xtarget = gen_reg_rtx (mode);
1996
1997       if (target == 0 || !REG_P (target))
1998         target = xtarget;
1999
2000       /* Indicate for flow that the entire target reg is being set.  */
2001       if (REG_P (target))
2002         emit_clobber (xtarget);
2003
2004       /* Do the actual arithmetic.  */
2005       for (i = 0; i < nwords; i++)
2006         {
2007           int index = (WORDS_BIG_ENDIAN ? nwords - i - 1 : i);
2008           rtx target_piece = operand_subword (xtarget, index, 1, mode);
2009           rtx op0_piece = operand_subword_force (xop0, index, mode);
2010           rtx op1_piece = operand_subword_force (xop1, index, mode);
2011           rtx x;
2012
2013           /* Main add/subtract of the input operands.  */
2014           x = expand_binop (word_mode, binoptab,
2015                             op0_piece, op1_piece,
2016                             target_piece, unsignedp, next_methods);
2017           if (x == 0)
2018             break;
2019
2020           if (i + 1 < nwords)
2021             {
2022               /* Store carry from main add/subtract.  */
2023               carry_out = gen_reg_rtx (word_mode);
2024               carry_out = emit_store_flag_force (carry_out,
2025                                                  (binoptab == add_optab
2026                                                   ? LT : GT),
2027                                                  x, op0_piece,
2028                                                  word_mode, 1, normalizep);
2029             }
2030
2031           if (i > 0)
2032             {
2033               rtx newx;
2034
2035               /* Add/subtract previous carry to main result.  */
2036               newx = expand_binop (word_mode,
2037                                    normalizep == 1 ? binoptab : otheroptab,
2038                                    x, carry_in,
2039                                    NULL_RTX, 1, next_methods);
2040
2041               if (i + 1 < nwords)
2042                 {
2043                   /* Get out carry from adding/subtracting carry in.  */
2044                   rtx carry_tmp = gen_reg_rtx (word_mode);
2045                   carry_tmp = emit_store_flag_force (carry_tmp,
2046                                                      (binoptab == add_optab
2047                                                       ? LT : GT),
2048                                                      newx, x,
2049                                                      word_mode, 1, normalizep);
2050
2051                   /* Logical-ior the two poss. carry together.  */
2052                   carry_out = expand_binop (word_mode, ior_optab,
2053                                             carry_out, carry_tmp,
2054                                             carry_out, 0, next_methods);
2055                   if (carry_out == 0)
2056                     break;
2057                 }
2058               emit_move_insn (target_piece, newx);
2059             }
2060           else
2061             {
2062               if (x != target_piece)
2063                 emit_move_insn (target_piece, x);
2064             }
2065
2066           carry_in = carry_out;
2067         }
2068
2069       if (i == GET_MODE_BITSIZE (mode) / (unsigned) BITS_PER_WORD)
2070         {
2071           if (optab_handler (mov_optab, mode)->insn_code != CODE_FOR_nothing
2072               || ! rtx_equal_p (target, xtarget))
2073             {
2074               rtx temp = emit_move_insn (target, xtarget);
2075
2076               set_unique_reg_note (temp,
2077                                    REG_EQUAL,
2078                                    gen_rtx_fmt_ee (binoptab->code, mode,
2079                                                    copy_rtx (xop0),
2080                                                    copy_rtx (xop1)));
2081             }
2082           else
2083             target = xtarget;
2084
2085           return target;
2086         }
2087
2088       else
2089         delete_insns_since (last);
2090     }
2091
2092   /* Attempt to synthesize double word multiplies using a sequence of word
2093      mode multiplications.  We first attempt to generate a sequence using a
2094      more efficient unsigned widening multiply, and if that fails we then
2095      try using a signed widening multiply.  */
2096
2097   if (binoptab == smul_optab
2098       && mclass == MODE_INT
2099       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
2100       && optab_handler (smul_optab, word_mode)->insn_code != CODE_FOR_nothing
2101       && optab_handler (add_optab, word_mode)->insn_code != CODE_FOR_nothing)
2102     {
2103       rtx product = NULL_RTX;
2104
2105       if (optab_handler (umul_widen_optab, mode)->insn_code
2106           != CODE_FOR_nothing)
2107         {
2108           product = expand_doubleword_mult (mode, op0, op1, target,
2109                                             true, methods);
2110           if (!product)
2111             delete_insns_since (last);
2112         }
2113
2114       if (product == NULL_RTX
2115           && optab_handler (smul_widen_optab, mode)->insn_code
2116              != CODE_FOR_nothing)
2117         {
2118           product = expand_doubleword_mult (mode, op0, op1, target,
2119                                             false, methods);
2120           if (!product)
2121             delete_insns_since (last);
2122         }
2123
2124       if (product != NULL_RTX)
2125         {
2126           if (optab_handler (mov_optab, mode)->insn_code != CODE_FOR_nothing)
2127             {
2128               temp = emit_move_insn (target ? target : product, product);
2129               set_unique_reg_note (temp,
2130                                    REG_EQUAL,
2131                                    gen_rtx_fmt_ee (MULT, mode,
2132                                                    copy_rtx (op0),
2133                                                    copy_rtx (op1)));
2134             }
2135           return product;
2136         }
2137     }
2138
2139   /* It can't be open-coded in this mode.
2140      Use a library call if one is available and caller says that's ok.  */
2141
2142   libfunc = optab_libfunc (binoptab, mode);
2143   if (libfunc
2144       && (methods == OPTAB_LIB || methods == OPTAB_LIB_WIDEN))
2145     {
2146       rtx insns;
2147       rtx op1x = op1;
2148       enum machine_mode op1_mode = mode;
2149       rtx value;
2150
2151       start_sequence ();
2152
2153       if (shift_optab_p (binoptab))
2154         {
2155           op1_mode = targetm.libgcc_shift_count_mode ();
2156           /* Specify unsigned here,
2157              since negative shift counts are meaningless.  */
2158           op1x = convert_to_mode (op1_mode, op1, 1);
2159         }
2160
2161       if (GET_MODE (op0) != VOIDmode
2162           && GET_MODE (op0) != mode)
2163         op0 = convert_to_mode (mode, op0, unsignedp);
2164
2165       /* Pass 1 for NO_QUEUE so we don't lose any increments
2166          if the libcall is cse'd or moved.  */
2167       value = emit_library_call_value (libfunc,
2168                                        NULL_RTX, LCT_CONST, mode, 2,
2169                                        op0, mode, op1x, op1_mode);
2170
2171       insns = get_insns ();
2172       end_sequence ();
2173
2174       target = gen_reg_rtx (mode);
2175       emit_libcall_block (insns, target, value,
2176                           gen_rtx_fmt_ee (binoptab->code, mode, op0, op1));
2177
2178       return target;
2179     }
2180
2181   delete_insns_since (last);
2182
2183   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2184
2185   if (! (methods == OPTAB_WIDEN || methods == OPTAB_LIB_WIDEN
2186          || methods == OPTAB_MUST_WIDEN))
2187     {
2188       /* Caller says, don't even try.  */
2189       delete_insns_since (entry_last);
2190       return 0;
2191     }
2192
2193   /* Compute the value of METHODS to pass to recursive calls.
2194      Don't allow widening to be tried recursively.  */
2195
2196   methods = (methods == OPTAB_LIB_WIDEN ? OPTAB_LIB : OPTAB_DIRECT);
2197
2198   /* Look for a wider mode of the same class for which it appears we can do
2199      the operation.  */
2200
2201   if (CLASS_HAS_WIDER_MODES_P (mclass))
2202     {
2203       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2204            wider_mode != VOIDmode;
2205            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2206         {
2207           if ((optab_handler (binoptab, wider_mode)->insn_code
2208                != CODE_FOR_nothing)
2209               || (methods == OPTAB_LIB
2210                   && optab_libfunc (binoptab, wider_mode)))
2211             {
2212               rtx xop0 = op0, xop1 = op1;
2213               int no_extend = 0;
2214
2215               /* For certain integer operations, we need not actually extend
2216                  the narrow operands, as long as we will truncate
2217                  the results to the same narrowness.  */
2218
2219               if ((binoptab == ior_optab || binoptab == and_optab
2220                    || binoptab == xor_optab
2221                    || binoptab == add_optab || binoptab == sub_optab
2222                    || binoptab == smul_optab || binoptab == ashl_optab)
2223                   && mclass == MODE_INT)
2224                 no_extend = 1;
2225
2226               xop0 = widen_operand (xop0, wider_mode, mode,
2227                                     unsignedp, no_extend);
2228
2229               /* The second operand of a shift must always be extended.  */
2230               xop1 = widen_operand (xop1, wider_mode, mode, unsignedp,
2231                                     no_extend && binoptab != ashl_optab);
2232
2233               temp = expand_binop (wider_mode, binoptab, xop0, xop1, NULL_RTX,
2234                                    unsignedp, methods);
2235               if (temp)
2236                 {
2237                   if (mclass != MODE_INT
2238                       || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
2239                                                  GET_MODE_BITSIZE (wider_mode)))
2240                     {
2241                       if (target == 0)
2242                         target = gen_reg_rtx (mode);
2243                       convert_move (target, temp, 0);
2244                       return target;
2245                     }
2246                   else
2247                     return gen_lowpart (mode, temp);
2248                 }
2249               else
2250                 delete_insns_since (last);
2251             }
2252         }
2253     }
2254
2255   delete_insns_since (entry_last);
2256   return 0;
2257 }
2258 \f
2259 /* Expand a binary operator which has both signed and unsigned forms.
2260    UOPTAB is the optab for unsigned operations, and SOPTAB is for
2261    signed operations.
2262
2263    If we widen unsigned operands, we may use a signed wider operation instead
2264    of an unsigned wider operation, since the result would be the same.  */
2265
2266 rtx
2267 sign_expand_binop (enum machine_mode mode, optab uoptab, optab soptab,
2268                    rtx op0, rtx op1, rtx target, int unsignedp,
2269                    enum optab_methods methods)
2270 {
2271   rtx temp;
2272   optab direct_optab = unsignedp ? uoptab : soptab;
2273   struct optab wide_soptab;
2274
2275   /* Do it without widening, if possible.  */
2276   temp = expand_binop (mode, direct_optab, op0, op1, target,
2277                        unsignedp, OPTAB_DIRECT);
2278   if (temp || methods == OPTAB_DIRECT)
2279     return temp;
2280
2281   /* Try widening to a signed int.  Make a fake signed optab that
2282      hides any signed insn for direct use.  */
2283   wide_soptab = *soptab;
2284   optab_handler (&wide_soptab, mode)->insn_code = CODE_FOR_nothing;
2285   /* We don't want to generate new hash table entries from this fake
2286      optab.  */
2287   wide_soptab.libcall_gen = NULL;
2288
2289   temp = expand_binop (mode, &wide_soptab, op0, op1, target,
2290                        unsignedp, OPTAB_WIDEN);
2291
2292   /* For unsigned operands, try widening to an unsigned int.  */
2293   if (temp == 0 && unsignedp)
2294     temp = expand_binop (mode, uoptab, op0, op1, target,
2295                          unsignedp, OPTAB_WIDEN);
2296   if (temp || methods == OPTAB_WIDEN)
2297     return temp;
2298
2299   /* Use the right width lib call if that exists.  */
2300   temp = expand_binop (mode, direct_optab, op0, op1, target, unsignedp, OPTAB_LIB);
2301   if (temp || methods == OPTAB_LIB)
2302     return temp;
2303
2304   /* Must widen and use a lib call, use either signed or unsigned.  */
2305   temp = expand_binop (mode, &wide_soptab, op0, op1, target,
2306                        unsignedp, methods);
2307   if (temp != 0)
2308     return temp;
2309   if (unsignedp)
2310     return expand_binop (mode, uoptab, op0, op1, target,
2311                          unsignedp, methods);
2312   return 0;
2313 }
2314 \f
2315 /* Generate code to perform an operation specified by UNOPPTAB
2316    on operand OP0, with two results to TARG0 and TARG1.
2317    We assume that the order of the operands for the instruction
2318    is TARG0, TARG1, OP0.
2319
2320    Either TARG0 or TARG1 may be zero, but what that means is that
2321    the result is not actually wanted.  We will generate it into
2322    a dummy pseudo-reg and discard it.  They may not both be zero.
2323
2324    Returns 1 if this operation can be performed; 0 if not.  */
2325
2326 int
2327 expand_twoval_unop (optab unoptab, rtx op0, rtx targ0, rtx targ1,
2328                     int unsignedp)
2329 {
2330   enum machine_mode mode = GET_MODE (targ0 ? targ0 : targ1);
2331   enum mode_class mclass;
2332   enum machine_mode wider_mode;
2333   rtx entry_last = get_last_insn ();
2334   rtx last;
2335
2336   mclass = GET_MODE_CLASS (mode);
2337
2338   if (!targ0)
2339     targ0 = gen_reg_rtx (mode);
2340   if (!targ1)
2341     targ1 = gen_reg_rtx (mode);
2342
2343   /* Record where to go back to if we fail.  */
2344   last = get_last_insn ();
2345
2346   if (optab_handler (unoptab, mode)->insn_code != CODE_FOR_nothing)
2347     {
2348       int icode = (int) optab_handler (unoptab, mode)->insn_code;
2349       enum machine_mode mode0 = insn_data[icode].operand[2].mode;
2350       rtx pat;
2351       rtx xop0 = op0;
2352
2353       if (GET_MODE (xop0) != VOIDmode
2354           && GET_MODE (xop0) != mode0)
2355         xop0 = convert_to_mode (mode0, xop0, unsignedp);
2356
2357       /* Now, if insn doesn't accept these operands, put them into pseudos.  */
2358       if (!insn_data[icode].operand[2].predicate (xop0, mode0))
2359         xop0 = copy_to_mode_reg (mode0, xop0);
2360
2361       /* We could handle this, but we should always be called with a pseudo
2362          for our targets and all insns should take them as outputs.  */
2363       gcc_assert (insn_data[icode].operand[0].predicate (targ0, mode));
2364       gcc_assert (insn_data[icode].operand[1].predicate (targ1, mode));
2365
2366       pat = GEN_FCN (icode) (targ0, targ1, xop0);
2367       if (pat)
2368         {
2369           emit_insn (pat);
2370           return 1;
2371         }
2372       else
2373         delete_insns_since (last);
2374     }
2375
2376   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2377
2378   if (CLASS_HAS_WIDER_MODES_P (mclass))
2379     {
2380       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2381            wider_mode != VOIDmode;
2382            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2383         {
2384           if (optab_handler (unoptab, wider_mode)->insn_code
2385               != CODE_FOR_nothing)
2386             {
2387               rtx t0 = gen_reg_rtx (wider_mode);
2388               rtx t1 = gen_reg_rtx (wider_mode);
2389               rtx cop0 = convert_modes (wider_mode, mode, op0, unsignedp);
2390
2391               if (expand_twoval_unop (unoptab, cop0, t0, t1, unsignedp))
2392                 {
2393                   convert_move (targ0, t0, unsignedp);
2394                   convert_move (targ1, t1, unsignedp);
2395                   return 1;
2396                 }
2397               else
2398                 delete_insns_since (last);
2399             }
2400         }
2401     }
2402
2403   delete_insns_since (entry_last);
2404   return 0;
2405 }
2406 \f
2407 /* Generate code to perform an operation specified by BINOPTAB
2408    on operands OP0 and OP1, with two results to TARG1 and TARG2.
2409    We assume that the order of the operands for the instruction
2410    is TARG0, OP0, OP1, TARG1, which would fit a pattern like
2411    [(set TARG0 (operate OP0 OP1)) (set TARG1 (operate ...))].
2412
2413    Either TARG0 or TARG1 may be zero, but what that means is that
2414    the result is not actually wanted.  We will generate it into
2415    a dummy pseudo-reg and discard it.  They may not both be zero.
2416
2417    Returns 1 if this operation can be performed; 0 if not.  */
2418
2419 int
2420 expand_twoval_binop (optab binoptab, rtx op0, rtx op1, rtx targ0, rtx targ1,
2421                      int unsignedp)
2422 {
2423   enum machine_mode mode = GET_MODE (targ0 ? targ0 : targ1);
2424   enum mode_class mclass;
2425   enum machine_mode wider_mode;
2426   rtx entry_last = get_last_insn ();
2427   rtx last;
2428
2429   mclass = GET_MODE_CLASS (mode);
2430
2431   if (!targ0)
2432     targ0 = gen_reg_rtx (mode);
2433   if (!targ1)
2434     targ1 = gen_reg_rtx (mode);
2435
2436   /* Record where to go back to if we fail.  */
2437   last = get_last_insn ();
2438
2439   if (optab_handler (binoptab, mode)->insn_code != CODE_FOR_nothing)
2440     {
2441       int icode = (int) optab_handler (binoptab, mode)->insn_code;
2442       enum machine_mode mode0 = insn_data[icode].operand[1].mode;
2443       enum machine_mode mode1 = insn_data[icode].operand[2].mode;
2444       rtx pat;
2445       rtx xop0 = op0, xop1 = op1;
2446
2447       /* If we are optimizing, force expensive constants into a register.  */
2448       xop0 = avoid_expensive_constant (mode0, binoptab, xop0, unsignedp);
2449       xop1 = avoid_expensive_constant (mode1, binoptab, xop1, unsignedp);
2450
2451       /* In case the insn wants input operands in modes different from
2452          those of the actual operands, convert the operands.  It would
2453          seem that we don't need to convert CONST_INTs, but we do, so
2454          that they're properly zero-extended, sign-extended or truncated
2455          for their mode.  */
2456
2457       if (GET_MODE (op0) != mode0 && mode0 != VOIDmode)
2458         xop0 = convert_modes (mode0,
2459                               GET_MODE (op0) != VOIDmode
2460                               ? GET_MODE (op0)
2461                               : mode,
2462                               xop0, unsignedp);
2463
2464       if (GET_MODE (op1) != mode1 && mode1 != VOIDmode)
2465         xop1 = convert_modes (mode1,
2466                               GET_MODE (op1) != VOIDmode
2467                               ? GET_MODE (op1)
2468                               : mode,
2469                               xop1, unsignedp);
2470
2471       /* Now, if insn doesn't accept these operands, put them into pseudos.  */
2472       if (!insn_data[icode].operand[1].predicate (xop0, mode0))
2473         xop0 = copy_to_mode_reg (mode0, xop0);
2474
2475       if (!insn_data[icode].operand[2].predicate (xop1, mode1))
2476         xop1 = copy_to_mode_reg (mode1, xop1);
2477
2478       /* We could handle this, but we should always be called with a pseudo
2479          for our targets and all insns should take them as outputs.  */
2480       gcc_assert (insn_data[icode].operand[0].predicate (targ0, mode));
2481       gcc_assert (insn_data[icode].operand[3].predicate (targ1, mode));
2482
2483       pat = GEN_FCN (icode) (targ0, xop0, xop1, targ1);
2484       if (pat)
2485         {
2486           emit_insn (pat);
2487           return 1;
2488         }
2489       else
2490         delete_insns_since (last);
2491     }
2492
2493   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2494
2495   if (CLASS_HAS_WIDER_MODES_P (mclass))
2496     {
2497       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2498            wider_mode != VOIDmode;
2499            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2500         {
2501           if (optab_handler (binoptab, wider_mode)->insn_code
2502               != CODE_FOR_nothing)
2503             {
2504               rtx t0 = gen_reg_rtx (wider_mode);
2505               rtx t1 = gen_reg_rtx (wider_mode);
2506               rtx cop0 = convert_modes (wider_mode, mode, op0, unsignedp);
2507               rtx cop1 = convert_modes (wider_mode, mode, op1, unsignedp);
2508
2509               if (expand_twoval_binop (binoptab, cop0, cop1,
2510                                        t0, t1, unsignedp))
2511                 {
2512                   convert_move (targ0, t0, unsignedp);
2513                   convert_move (targ1, t1, unsignedp);
2514                   return 1;
2515                 }
2516               else
2517                 delete_insns_since (last);
2518             }
2519         }
2520     }
2521
2522   delete_insns_since (entry_last);
2523   return 0;
2524 }
2525
2526 /* Expand the two-valued library call indicated by BINOPTAB, but
2527    preserve only one of the values.  If TARG0 is non-NULL, the first
2528    value is placed into TARG0; otherwise the second value is placed
2529    into TARG1.  Exactly one of TARG0 and TARG1 must be non-NULL.  The
2530    value stored into TARG0 or TARG1 is equivalent to (CODE OP0 OP1).
2531    This routine assumes that the value returned by the library call is
2532    as if the return value was of an integral mode twice as wide as the
2533    mode of OP0.  Returns 1 if the call was successful.  */
2534
2535 bool
2536 expand_twoval_binop_libfunc (optab binoptab, rtx op0, rtx op1,
2537                              rtx targ0, rtx targ1, enum rtx_code code)
2538 {
2539   enum machine_mode mode;
2540   enum machine_mode libval_mode;
2541   rtx libval;
2542   rtx insns;
2543   rtx libfunc;
2544
2545   /* Exactly one of TARG0 or TARG1 should be non-NULL.  */
2546   gcc_assert (!targ0 != !targ1);
2547
2548   mode = GET_MODE (op0);
2549   libfunc = optab_libfunc (binoptab, mode);
2550   if (!libfunc)
2551     return false;
2552
2553   /* The value returned by the library function will have twice as
2554      many bits as the nominal MODE.  */
2555   libval_mode = smallest_mode_for_size (2 * GET_MODE_BITSIZE (mode),
2556                                         MODE_INT);
2557   start_sequence ();
2558   libval = emit_library_call_value (libfunc, NULL_RTX, LCT_CONST,
2559                                     libval_mode, 2,
2560                                     op0, mode,
2561                                     op1, mode);
2562   /* Get the part of VAL containing the value that we want.  */
2563   libval = simplify_gen_subreg (mode, libval, libval_mode,
2564                                 targ0 ? 0 : GET_MODE_SIZE (mode));
2565   insns = get_insns ();
2566   end_sequence ();
2567   /* Move the into the desired location.  */
2568   emit_libcall_block (insns, targ0 ? targ0 : targ1, libval,
2569                       gen_rtx_fmt_ee (code, mode, op0, op1));
2570
2571   return true;
2572 }
2573
2574 \f
2575 /* Wrapper around expand_unop which takes an rtx code to specify
2576    the operation to perform, not an optab pointer.  All other
2577    arguments are the same.  */
2578 rtx
2579 expand_simple_unop (enum machine_mode mode, enum rtx_code code, rtx op0,
2580                     rtx target, int unsignedp)
2581 {
2582   optab unop = code_to_optab[(int) code];
2583   gcc_assert (unop);
2584
2585   return expand_unop (mode, unop, op0, target, unsignedp);
2586 }
2587
2588 /* Try calculating
2589         (clz:narrow x)
2590    as
2591         (clz:wide (zero_extend:wide x)) - ((width wide) - (width narrow)).  */
2592 static rtx
2593 widen_clz (enum machine_mode mode, rtx op0, rtx target)
2594 {
2595   enum mode_class mclass = GET_MODE_CLASS (mode);
2596   if (CLASS_HAS_WIDER_MODES_P (mclass))
2597     {
2598       enum machine_mode wider_mode;
2599       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2600            wider_mode != VOIDmode;
2601            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2602         {
2603           if (optab_handler (clz_optab, wider_mode)->insn_code
2604               != CODE_FOR_nothing)
2605             {
2606               rtx xop0, temp, last;
2607
2608               last = get_last_insn ();
2609
2610               if (target == 0)
2611                 target = gen_reg_rtx (mode);
2612               xop0 = widen_operand (op0, wider_mode, mode, true, false);
2613               temp = expand_unop (wider_mode, clz_optab, xop0, NULL_RTX, true);
2614               if (temp != 0)
2615                 temp = expand_binop (wider_mode, sub_optab, temp,
2616                                      GEN_INT (GET_MODE_BITSIZE (wider_mode)
2617                                               - GET_MODE_BITSIZE (mode)),
2618                                      target, true, OPTAB_DIRECT);
2619               if (temp == 0)
2620                 delete_insns_since (last);
2621
2622               return temp;
2623             }
2624         }
2625     }
2626   return 0;
2627 }
2628
2629 /* Try calculating clz of a double-word quantity as two clz's of word-sized
2630    quantities, choosing which based on whether the high word is nonzero.  */
2631 static rtx
2632 expand_doubleword_clz (enum machine_mode mode, rtx op0, rtx target)
2633 {
2634   rtx xop0 = force_reg (mode, op0);
2635   rtx subhi = gen_highpart (word_mode, xop0);
2636   rtx sublo = gen_lowpart (word_mode, xop0);
2637   rtx hi0_label = gen_label_rtx ();
2638   rtx after_label = gen_label_rtx ();
2639   rtx seq, temp, result;
2640
2641   /* If we were not given a target, use a word_mode register, not a
2642      'mode' register.  The result will fit, and nobody is expecting
2643      anything bigger (the return type of __builtin_clz* is int).  */
2644   if (!target)
2645     target = gen_reg_rtx (word_mode);
2646
2647   /* In any case, write to a word_mode scratch in both branches of the
2648      conditional, so we can ensure there is a single move insn setting
2649      'target' to tag a REG_EQUAL note on.  */
2650   result = gen_reg_rtx (word_mode);
2651
2652   start_sequence ();
2653
2654   /* If the high word is not equal to zero,
2655      then clz of the full value is clz of the high word.  */
2656   emit_cmp_and_jump_insns (subhi, CONST0_RTX (word_mode), EQ, 0,
2657                            word_mode, true, hi0_label);
2658
2659   temp = expand_unop_direct (word_mode, clz_optab, subhi, result, true);
2660   if (!temp)
2661     goto fail;
2662
2663   if (temp != result)
2664     convert_move (result, temp, true);
2665
2666   emit_jump_insn (gen_jump (after_label));
2667   emit_barrier ();
2668
2669   /* Else clz of the full value is clz of the low word plus the number
2670      of bits in the high word.  */
2671   emit_label (hi0_label);
2672
2673   temp = expand_unop_direct (word_mode, clz_optab, sublo, 0, true);
2674   if (!temp)
2675     goto fail;
2676   temp = expand_binop (word_mode, add_optab, temp,
2677                        GEN_INT (GET_MODE_BITSIZE (word_mode)),
2678                        result, true, OPTAB_DIRECT);
2679   if (!temp)
2680     goto fail;
2681   if (temp != result)
2682     convert_move (result, temp, true);
2683
2684   emit_label (after_label);
2685   convert_move (target, result, true);
2686
2687   seq = get_insns ();
2688   end_sequence ();
2689
2690   add_equal_note (seq, target, CLZ, xop0, 0);
2691   emit_insn (seq);
2692   return target;
2693
2694  fail:
2695   end_sequence ();
2696   return 0;
2697 }
2698
2699 /* Try calculating
2700         (bswap:narrow x)
2701    as
2702         (lshiftrt:wide (bswap:wide x) ((width wide) - (width narrow))).  */
2703 static rtx
2704 widen_bswap (enum machine_mode mode, rtx op0, rtx target)
2705 {
2706   enum mode_class mclass = GET_MODE_CLASS (mode);
2707   enum machine_mode wider_mode;
2708   rtx x, last;
2709
2710   if (!CLASS_HAS_WIDER_MODES_P (mclass))
2711     return NULL_RTX;
2712
2713   for (wider_mode = GET_MODE_WIDER_MODE (mode);
2714        wider_mode != VOIDmode;
2715        wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2716     if (optab_handler (bswap_optab, wider_mode)->insn_code != CODE_FOR_nothing)
2717       goto found;
2718   return NULL_RTX;
2719
2720  found:
2721   last = get_last_insn ();
2722
2723   x = widen_operand (op0, wider_mode, mode, true, true);
2724   x = expand_unop (wider_mode, bswap_optab, x, NULL_RTX, true);
2725
2726   if (x != 0)
2727     x = expand_shift (RSHIFT_EXPR, wider_mode, x,
2728                       size_int (GET_MODE_BITSIZE (wider_mode)
2729                                 - GET_MODE_BITSIZE (mode)),
2730                       NULL_RTX, true);
2731
2732   if (x != 0)
2733     {
2734       if (target == 0)
2735         target = gen_reg_rtx (mode);
2736       emit_move_insn (target, gen_lowpart (mode, x));
2737     }
2738   else
2739     delete_insns_since (last);
2740
2741   return target;
2742 }
2743
2744 /* Try calculating bswap as two bswaps of two word-sized operands.  */
2745
2746 static rtx
2747 expand_doubleword_bswap (enum machine_mode mode, rtx op, rtx target)
2748 {
2749   rtx t0, t1;
2750
2751   t1 = expand_unop (word_mode, bswap_optab,
2752                     operand_subword_force (op, 0, mode), NULL_RTX, true);
2753   t0 = expand_unop (word_mode, bswap_optab,
2754                     operand_subword_force (op, 1, mode), NULL_RTX, true);
2755
2756   if (target == 0)
2757     target = gen_reg_rtx (mode);
2758   if (REG_P (target))
2759     emit_clobber (target);
2760   emit_move_insn (operand_subword (target, 0, 1, mode), t0);
2761   emit_move_insn (operand_subword (target, 1, 1, mode), t1);
2762
2763   return target;
2764 }
2765
2766 /* Try calculating (parity x) as (and (popcount x) 1), where
2767    popcount can also be done in a wider mode.  */
2768 static rtx
2769 expand_parity (enum machine_mode mode, rtx op0, rtx target)
2770 {
2771   enum mode_class mclass = GET_MODE_CLASS (mode);
2772   if (CLASS_HAS_WIDER_MODES_P (mclass))
2773     {
2774       enum machine_mode wider_mode;
2775       for (wider_mode = mode; wider_mode != VOIDmode;
2776            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2777         {
2778           if (optab_handler (popcount_optab, wider_mode)->insn_code
2779               != CODE_FOR_nothing)
2780             {
2781               rtx xop0, temp, last;
2782
2783               last = get_last_insn ();
2784
2785               if (target == 0)
2786                 target = gen_reg_rtx (mode);
2787               xop0 = widen_operand (op0, wider_mode, mode, true, false);
2788               temp = expand_unop (wider_mode, popcount_optab, xop0, NULL_RTX,
2789                                   true);
2790               if (temp != 0)
2791                 temp = expand_binop (wider_mode, and_optab, temp, const1_rtx,
2792                                      target, true, OPTAB_DIRECT);
2793               if (temp == 0)
2794                 delete_insns_since (last);
2795
2796               return temp;
2797             }
2798         }
2799     }
2800   return 0;
2801 }
2802
2803 /* Try calculating ctz(x) as K - clz(x & -x) ,
2804    where K is GET_MODE_BITSIZE(mode) - 1.
2805
2806    Both __builtin_ctz and __builtin_clz are undefined at zero, so we
2807    don't have to worry about what the hardware does in that case.  (If
2808    the clz instruction produces the usual value at 0, which is K, the
2809    result of this code sequence will be -1; expand_ffs, below, relies
2810    on this.  It might be nice to have it be K instead, for consistency
2811    with the (very few) processors that provide a ctz with a defined
2812    value, but that would take one more instruction, and it would be
2813    less convenient for expand_ffs anyway.  */
2814
2815 static rtx
2816 expand_ctz (enum machine_mode mode, rtx op0, rtx target)
2817 {
2818   rtx seq, temp;
2819   
2820   if (optab_handler (clz_optab, mode)->insn_code == CODE_FOR_nothing)
2821     return 0;
2822   
2823   start_sequence ();
2824
2825   temp = expand_unop_direct (mode, neg_optab, op0, NULL_RTX, true);
2826   if (temp)
2827     temp = expand_binop (mode, and_optab, op0, temp, NULL_RTX,
2828                          true, OPTAB_DIRECT);
2829   if (temp)
2830     temp = expand_unop_direct (mode, clz_optab, temp, NULL_RTX, true);
2831   if (temp)
2832     temp = expand_binop (mode, sub_optab, GEN_INT (GET_MODE_BITSIZE (mode) - 1),
2833                          temp, target,
2834                          true, OPTAB_DIRECT);
2835   if (temp == 0)
2836     {
2837       end_sequence ();
2838       return 0;
2839     }
2840
2841   seq = get_insns ();
2842   end_sequence ();
2843
2844   add_equal_note (seq, temp, CTZ, op0, 0);
2845   emit_insn (seq);
2846   return temp;
2847 }
2848
2849
2850 /* Try calculating ffs(x) using ctz(x) if we have that instruction, or
2851    else with the sequence used by expand_clz.
2852    
2853    The ffs builtin promises to return zero for a zero value and ctz/clz
2854    may have an undefined value in that case.  If they do not give us a
2855    convenient value, we have to generate a test and branch.  */
2856 static rtx
2857 expand_ffs (enum machine_mode mode, rtx op0, rtx target)
2858 {
2859   HOST_WIDE_INT val = 0;
2860   bool defined_at_zero = false;
2861   rtx temp, seq;
2862
2863   if (optab_handler (ctz_optab, mode)->insn_code != CODE_FOR_nothing)
2864     {
2865       start_sequence ();
2866
2867       temp = expand_unop_direct (mode, ctz_optab, op0, 0, true);
2868       if (!temp)
2869         goto fail;
2870
2871       defined_at_zero = (CTZ_DEFINED_VALUE_AT_ZERO (mode, val) == 2);
2872     }
2873   else if (optab_handler (clz_optab, mode)->insn_code != CODE_FOR_nothing)
2874     {
2875       start_sequence ();
2876       temp = expand_ctz (mode, op0, 0);
2877       if (!temp)
2878         goto fail;
2879
2880       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, val) == 2)
2881         {
2882           defined_at_zero = true;
2883           val = (GET_MODE_BITSIZE (mode) - 1) - val;
2884         }
2885     }
2886   else
2887     return 0;
2888
2889   if (defined_at_zero && val == -1)
2890     /* No correction needed at zero.  */;
2891   else 
2892     {
2893       /* We don't try to do anything clever with the situation found
2894          on some processors (eg Alpha) where ctz(0:mode) ==
2895          bitsize(mode).  If someone can think of a way to send N to -1
2896          and leave alone all values in the range 0..N-1 (where N is a
2897          power of two), cheaper than this test-and-branch, please add it.
2898
2899          The test-and-branch is done after the operation itself, in case
2900          the operation sets condition codes that can be recycled for this.
2901          (This is true on i386, for instance.)  */
2902
2903       rtx nonzero_label = gen_label_rtx ();
2904       emit_cmp_and_jump_insns (op0, CONST0_RTX (mode), NE, 0,
2905                                mode, true, nonzero_label);
2906
2907       convert_move (temp, GEN_INT (-1), false);
2908       emit_label (nonzero_label);
2909     }
2910
2911   /* temp now has a value in the range -1..bitsize-1.  ffs is supposed
2912      to produce a value in the range 0..bitsize.  */
2913   temp = expand_binop (mode, add_optab, temp, GEN_INT (1),
2914                        target, false, OPTAB_DIRECT);
2915   if (!temp)
2916     goto fail;
2917
2918   seq = get_insns ();
2919   end_sequence ();
2920
2921   add_equal_note (seq, temp, FFS, op0, 0);
2922   emit_insn (seq);
2923   return temp;
2924
2925  fail:
2926   end_sequence ();
2927   return 0;
2928 }
2929
2930 /* Extract the OMODE lowpart from VAL, which has IMODE.  Under certain
2931    conditions, VAL may already be a SUBREG against which we cannot generate
2932    a further SUBREG.  In this case, we expect forcing the value into a
2933    register will work around the situation.  */
2934
2935 static rtx
2936 lowpart_subreg_maybe_copy (enum machine_mode omode, rtx val,
2937                            enum machine_mode imode)
2938 {
2939   rtx ret;
2940   ret = lowpart_subreg (omode, val, imode);
2941   if (ret == NULL)
2942     {
2943       val = force_reg (imode, val);
2944       ret = lowpart_subreg (omode, val, imode);
2945       gcc_assert (ret != NULL);
2946     }
2947   return ret;
2948 }
2949
2950 /* Expand a floating point absolute value or negation operation via a
2951    logical operation on the sign bit.  */
2952
2953 static rtx
2954 expand_absneg_bit (enum rtx_code code, enum machine_mode mode,
2955                    rtx op0, rtx target)
2956 {
2957   const struct real_format *fmt;
2958   int bitpos, word, nwords, i;
2959   enum machine_mode imode;
2960   HOST_WIDE_INT hi, lo;
2961   rtx temp, insns;
2962
2963   /* The format has to have a simple sign bit.  */
2964   fmt = REAL_MODE_FORMAT (mode);
2965   if (fmt == NULL)
2966     return NULL_RTX;
2967
2968   bitpos = fmt->signbit_rw;
2969   if (bitpos < 0)
2970     return NULL_RTX;
2971
2972   /* Don't create negative zeros if the format doesn't support them.  */
2973   if (code == NEG && !fmt->has_signed_zero)
2974     return NULL_RTX;
2975
2976   if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
2977     {
2978       imode = int_mode_for_mode (mode);
2979       if (imode == BLKmode)
2980         return NULL_RTX;
2981       word = 0;
2982       nwords = 1;
2983     }
2984   else
2985     {
2986       imode = word_mode;
2987
2988       if (FLOAT_WORDS_BIG_ENDIAN)
2989         word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
2990       else
2991         word = bitpos / BITS_PER_WORD;
2992       bitpos = bitpos % BITS_PER_WORD;
2993       nwords = (GET_MODE_BITSIZE (mode) + BITS_PER_WORD - 1) / BITS_PER_WORD;
2994     }
2995
2996   if (bitpos < HOST_BITS_PER_WIDE_INT)
2997     {
2998       hi = 0;
2999       lo = (HOST_WIDE_INT) 1 << bitpos;
3000     }
3001   else
3002     {
3003       hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
3004       lo = 0;
3005     }
3006   if (code == ABS)
3007     lo = ~lo, hi = ~hi;
3008
3009   if (target == 0 || target == op0)
3010     target = gen_reg_rtx (mode);
3011
3012   if (nwords > 1)
3013     {
3014       start_sequence ();
3015
3016       for (i = 0; i < nwords; ++i)
3017         {
3018           rtx targ_piece = operand_subword (target, i, 1, mode);
3019           rtx op0_piece = operand_subword_force (op0, i, mode);
3020
3021           if (i == word)
3022             {
3023               temp = expand_binop (imode, code == ABS ? and_optab : xor_optab,
3024                                    op0_piece,
3025                                    immed_double_const (lo, hi, imode),
3026                                    targ_piece, 1, OPTAB_LIB_WIDEN);
3027               if (temp != targ_piece)
3028                 emit_move_insn (targ_piece, temp);
3029             }
3030           else
3031             emit_move_insn (targ_piece, op0_piece);
3032         }
3033
3034       insns = get_insns ();
3035       end_sequence ();
3036
3037       emit_insn (insns);
3038     }
3039   else
3040     {
3041       temp = expand_binop (imode, code == ABS ? and_optab : xor_optab,
3042                            gen_lowpart (imode, op0),
3043                            immed_double_const (lo, hi, imode),
3044                            gen_lowpart (imode, target), 1, OPTAB_LIB_WIDEN);
3045       target = lowpart_subreg_maybe_copy (mode, temp, imode);
3046
3047       set_unique_reg_note (get_last_insn (), REG_EQUAL,
3048                            gen_rtx_fmt_e (code, mode, copy_rtx (op0)));
3049     }
3050
3051   return target;
3052 }
3053
3054 /* As expand_unop, but will fail rather than attempt the operation in a
3055    different mode or with a libcall.  */
3056 static rtx
3057 expand_unop_direct (enum machine_mode mode, optab unoptab, rtx op0, rtx target,
3058              int unsignedp)
3059 {
3060   if (optab_handler (unoptab, mode)->insn_code != CODE_FOR_nothing)
3061     {
3062       int icode = (int) optab_handler (unoptab, mode)->insn_code;
3063       enum machine_mode mode0 = insn_data[icode].operand[1].mode;
3064       rtx xop0 = op0;
3065       rtx last = get_last_insn ();
3066       rtx pat, temp;
3067
3068       if (target)
3069         temp = target;
3070       else
3071         temp = gen_reg_rtx (mode);
3072
3073       if (GET_MODE (xop0) != VOIDmode
3074           && GET_MODE (xop0) != mode0)
3075         xop0 = convert_to_mode (mode0, xop0, unsignedp);
3076
3077       /* Now, if insn doesn't accept our operand, put it into a pseudo.  */
3078
3079       if (!insn_data[icode].operand[1].predicate (xop0, mode0))
3080         xop0 = copy_to_mode_reg (mode0, xop0);
3081
3082       if (!insn_data[icode].operand[0].predicate (temp, mode))
3083         temp = gen_reg_rtx (mode);
3084
3085       pat = GEN_FCN (icode) (temp, xop0);
3086       if (pat)
3087         {
3088           if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX
3089               && ! add_equal_note (pat, temp, unoptab->code, xop0, NULL_RTX))
3090             {
3091               delete_insns_since (last);
3092               return expand_unop (mode, unoptab, op0, NULL_RTX, unsignedp);
3093             }
3094
3095           emit_insn (pat);
3096
3097           return temp;
3098         }
3099       else
3100         delete_insns_since (last);
3101     }
3102   return 0;
3103 }
3104
3105 /* Generate code to perform an operation specified by UNOPTAB
3106    on operand OP0, with result having machine-mode MODE.
3107
3108    UNSIGNEDP is for the case where we have to widen the operands
3109    to perform the operation.  It says to use zero-extension.
3110
3111    If TARGET is nonzero, the value
3112    is generated there, if it is convenient to do so.
3113    In all cases an rtx is returned for the locus of the value;
3114    this may or may not be TARGET.  */
3115
3116 rtx
3117 expand_unop (enum machine_mode mode, optab unoptab, rtx op0, rtx target,
3118              int unsignedp)
3119 {
3120   enum mode_class mclass = GET_MODE_CLASS (mode);
3121   enum machine_mode wider_mode;
3122   rtx temp;
3123   rtx libfunc;
3124
3125   temp = expand_unop_direct (mode, unoptab, op0, target, unsignedp);
3126   if (temp)
3127     return temp;
3128
3129   /* It can't be done in this mode.  Can we open-code it in a wider mode?  */
3130
3131   /* Widening (or narrowing) clz needs special treatment.  */
3132   if (unoptab == clz_optab)
3133     {
3134       temp = widen_clz (mode, op0, target);
3135       if (temp)
3136         return temp;
3137
3138       if (GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
3139           && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3140         {
3141           temp = expand_doubleword_clz (mode, op0, target);
3142           if (temp)
3143             return temp;
3144         }
3145
3146         goto try_libcall;
3147     }
3148
3149   /* Widening (or narrowing) bswap needs special treatment.  */
3150   if (unoptab == bswap_optab)
3151     {
3152       temp = widen_bswap (mode, op0, target);
3153       if (temp)
3154         return temp;
3155
3156       if (GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
3157           && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3158         {
3159           temp = expand_doubleword_bswap (mode, op0, target);
3160           if (temp)
3161             return temp;
3162         }
3163
3164       goto try_libcall;
3165     }
3166
3167   if (CLASS_HAS_WIDER_MODES_P (mclass))
3168     for (wider_mode = GET_MODE_WIDER_MODE (mode);
3169          wider_mode != VOIDmode;
3170          wider_mode = GET_MODE_WIDER_MODE (wider_mode))
3171       {
3172         if (optab_handler (unoptab, wider_mode)->insn_code != CODE_FOR_nothing)
3173           {
3174             rtx xop0 = op0;
3175             rtx last = get_last_insn ();
3176
3177             /* For certain operations, we need not actually extend
3178                the narrow operand, as long as we will truncate the
3179                results to the same narrowness.  */
3180
3181             xop0 = widen_operand (xop0, wider_mode, mode, unsignedp,
3182                                   (unoptab == neg_optab
3183                                    || unoptab == one_cmpl_optab)
3184                                   && mclass == MODE_INT);
3185
3186             temp = expand_unop (wider_mode, unoptab, xop0, NULL_RTX,
3187                                 unsignedp);
3188
3189             if (temp)
3190               {
3191                 if (mclass != MODE_INT
3192                     || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
3193                                                GET_MODE_BITSIZE (wider_mode)))
3194                   {
3195                     if (target == 0)
3196                       target = gen_reg_rtx (mode);
3197                     convert_move (target, temp, 0);
3198                     return target;
3199                   }
3200                 else
3201                   return gen_lowpart (mode, temp);
3202               }
3203             else
3204               delete_insns_since (last);
3205           }
3206       }
3207
3208   /* These can be done a word at a time.  */
3209   if (unoptab == one_cmpl_optab
3210       && mclass == MODE_INT
3211       && GET_MODE_SIZE (mode) > UNITS_PER_WORD
3212       && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3213     {
3214       int i;
3215       rtx insns;
3216
3217       if (target == 0 || target == op0)
3218         target = gen_reg_rtx (mode);
3219
3220       start_sequence ();
3221
3222       /* Do the actual arithmetic.  */
3223       for (i = 0; i < GET_MODE_BITSIZE (mode) / BITS_PER_WORD; i++)
3224         {
3225           rtx target_piece = operand_subword (target, i, 1, mode);
3226           rtx x = expand_unop (word_mode, unoptab,
3227                                operand_subword_force (op0, i, mode),
3228                                target_piece, unsignedp);
3229
3230           if (target_piece != x)
3231             emit_move_insn (target_piece, x);
3232         }
3233
3234       insns = get_insns ();
3235       end_sequence ();
3236
3237       emit_insn (insns);
3238       return target;
3239     }
3240
3241   if (unoptab->code == NEG)
3242     {
3243       /* Try negating floating point values by flipping the sign bit.  */
3244       if (SCALAR_FLOAT_MODE_P (mode))
3245         {
3246           temp = expand_absneg_bit (NEG, mode, op0, target);
3247           if (temp)
3248             return temp;
3249         }
3250
3251       /* If there is no negation pattern, and we have no negative zero,
3252          try subtracting from zero.  */
3253       if (!HONOR_SIGNED_ZEROS (mode))
3254         {
3255           temp = expand_binop (mode, (unoptab == negv_optab
3256                                       ? subv_optab : sub_optab),
3257                                CONST0_RTX (mode), op0, target,
3258                                unsignedp, OPTAB_DIRECT);
3259           if (temp)
3260             return temp;
3261         }
3262     }
3263
3264   /* Try calculating parity (x) as popcount (x) % 2.  */
3265   if (unoptab == parity_optab)
3266     {
3267       temp = expand_parity (mode, op0, target);
3268       if (temp)
3269         return temp;
3270     }
3271
3272   /* Try implementing ffs (x) in terms of clz (x).  */
3273   if (unoptab == ffs_optab)
3274     {
3275       temp = expand_ffs (mode, op0, target);
3276       if (temp)
3277         return temp;
3278     }
3279
3280   /* Try implementing ctz (x) in terms of clz (x).  */
3281   if (unoptab == ctz_optab)
3282     {
3283       temp = expand_ctz (mode, op0, target);
3284       if (temp)
3285         return temp;
3286     }
3287
3288  try_libcall:
3289   /* Now try a library call in this mode.  */
3290   libfunc = optab_libfunc (unoptab, mode);
3291   if (libfunc)
3292     {
3293       rtx insns;
3294       rtx value;
3295       rtx eq_value;
3296       enum machine_mode outmode = mode;
3297
3298       /* All of these functions return small values.  Thus we choose to
3299          have them return something that isn't a double-word.  */
3300       if (unoptab == ffs_optab || unoptab == clz_optab || unoptab == ctz_optab
3301           || unoptab == popcount_optab || unoptab == parity_optab)
3302         outmode
3303             = GET_MODE (hard_libcall_value (TYPE_MODE (integer_type_node)));
3304
3305       start_sequence ();
3306
3307       /* Pass 1 for NO_QUEUE so we don't lose any increments
3308          if the libcall is cse'd or moved.  */
3309       value = emit_library_call_value (libfunc, NULL_RTX, LCT_CONST, outmode,
3310                                        1, op0, mode);
3311       insns = get_insns ();
3312       end_sequence ();
3313
3314       target = gen_reg_rtx (outmode);
3315       eq_value = gen_rtx_fmt_e (unoptab->code, mode, op0);
3316       if (GET_MODE_SIZE (outmode) < GET_MODE_SIZE (mode))
3317         eq_value = simplify_gen_unary (TRUNCATE, outmode, eq_value, mode);
3318       else if (GET_MODE_SIZE (outmode) > GET_MODE_SIZE (mode))
3319         eq_value = simplify_gen_unary (ZERO_EXTEND, outmode, eq_value, mode);
3320       emit_libcall_block (insns, target, value, eq_value);
3321
3322       return target;
3323     }
3324
3325   /* It can't be done in this mode.  Can we do it in a wider mode?  */
3326
3327   if (CLASS_HAS_WIDER_MODES_P (mclass))
3328     {
3329       for (wider_mode = GET_MODE_WIDER_MODE (mode);
3330            wider_mode != VOIDmode;
3331            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
3332         {
3333           if ((optab_handler (unoptab, wider_mode)->insn_code
3334                != CODE_FOR_nothing)
3335               || optab_libfunc (unoptab, wider_mode))
3336             {
3337               rtx xop0 = op0;
3338               rtx last = get_last_insn ();
3339
3340               /* For certain operations, we need not actually extend
3341                  the narrow operand, as long as we will truncate the
3342                  results to the same narrowness.  */
3343
3344               xop0 = widen_operand (xop0, wider_mode, mode, unsignedp,
3345                                     (unoptab == neg_optab
3346                                      || unoptab == one_cmpl_optab)
3347                                     && mclass == MODE_INT);
3348
3349               temp = expand_unop (wider_mode, unoptab, xop0, NULL_RTX,
3350                                   unsignedp);
3351
3352               /* If we are generating clz using wider mode, adjust the
3353                  result.  */
3354               if (unoptab == clz_optab && temp != 0)
3355                 temp = expand_binop (wider_mode, sub_optab, temp,
3356                                      GEN_INT (GET_MODE_BITSIZE (wider_mode)
3357                                               - GET_MODE_BITSIZE (mode)),
3358                                      target, true, OPTAB_DIRECT);
3359
3360               if (temp)
3361                 {
3362                   if (mclass != MODE_INT)
3363                     {
3364                       if (target == 0)
3365                         target = gen_reg_rtx (mode);
3366                       convert_move (target, temp, 0);
3367                       return target;
3368                     }
3369                   else
3370                     return gen_lowpart (mode, temp);
3371                 }
3372               else
3373                 delete_insns_since (last);
3374             }
3375         }
3376     }
3377
3378   /* One final attempt at implementing negation via subtraction,
3379      this time allowing widening of the operand.  */
3380   if (unoptab->code == NEG && !HONOR_SIGNED_ZEROS (mode))
3381     {
3382       rtx temp;
3383       temp = expand_binop (mode,
3384                            unoptab == negv_optab ? subv_optab : sub_optab,
3385                            CONST0_RTX (mode), op0,
3386                            target, unsignedp, OPTAB_LIB_WIDEN);
3387       if (temp)
3388         return temp;
3389     }
3390
3391   return 0;
3392 }
3393 \f
3394 /* Emit code to compute the absolute value of OP0, with result to
3395    TARGET if convenient.  (TARGET may be 0.)  The return value says
3396    where the result actually is to be found.
3397
3398    MODE is the mode of the operand; the mode of the result is
3399    different but can be deduced from MODE.
3400
3401  */
3402
3403 rtx
3404 expand_abs_nojump (enum machine_mode mode, rtx op0, rtx target,
3405                    int result_unsignedp)
3406 {
3407   rtx temp;
3408
3409   if (! flag_trapv)
3410     result_unsignedp = 1;
3411
3412   /* First try to do it with a special abs instruction.  */
3413   temp = expand_unop (mode, result_unsignedp ? abs_optab : absv_optab,
3414                       op0, target, 0);
3415   if (temp != 0)
3416     return temp;
3417
3418   /* For floating point modes, try clearing the sign bit.  */
3419   if (SCALAR_FLOAT_MODE_P (mode))
3420     {
3421       temp = expand_absneg_bit (ABS, mode, op0, target);
3422       if (temp)
3423         return temp;
3424     }
3425
3426   /* If we have a MAX insn, we can do this as MAX (x, -x).  */
3427   if (optab_handler (smax_optab, mode)->insn_code != CODE_FOR_nothing
3428       && !HONOR_SIGNED_ZEROS (mode))
3429     {
3430       rtx last = get_last_insn ();
3431
3432       temp = expand_unop (mode, neg_optab, op0, NULL_RTX, 0);
3433       if (temp != 0)
3434         temp = expand_binop (mode, smax_optab, op0, temp, target, 0,
3435                              OPTAB_WIDEN);
3436
3437       if (temp != 0)
3438         return temp;
3439
3440       delete_insns_since (last);
3441     }
3442
3443   /* If this machine has expensive jumps, we can do integer absolute
3444      value of X as (((signed) x >> (W-1)) ^ x) - ((signed) x >> (W-1)),
3445      where W is the width of MODE.  */
3446
3447   if (GET_MODE_CLASS (mode) == MODE_INT
3448       && BRANCH_COST (optimize_insn_for_speed_p (),
3449                       false) >= 2)
3450     {
3451       rtx extended = expand_shift (RSHIFT_EXPR, mode, op0,
3452                                    size_int (GET_MODE_BITSIZE (mode) - 1),
3453                                    NULL_RTX, 0);
3454
3455       temp = expand_binop (mode, xor_optab, extended, op0, target, 0,
3456                            OPTAB_LIB_WIDEN);
3457       if (temp != 0)
3458         temp = expand_binop (mode, result_unsignedp ? sub_optab : subv_optab,
3459                              temp, extended, target, 0, OPTAB_LIB_WIDEN);
3460
3461       if (temp != 0)
3462         return temp;
3463     }
3464
3465   return NULL_RTX;
3466 }
3467
3468 rtx
3469 expand_abs (enum machine_mode mode, rtx op0, rtx target,
3470             int result_unsignedp, int safe)
3471 {
3472   rtx temp, op1;
3473
3474   if (! flag_trapv)
3475     result_unsignedp = 1;
3476
3477   temp = expand_abs_nojump (mode, op0, target, result_unsignedp);
3478   if (temp != 0)
3479     return temp;
3480
3481   /* If that does not win, use conditional jump and negate.  */
3482
3483   /* It is safe to use the target if it is the same
3484      as the source if this is also a pseudo register */
3485   if (op0 == target && REG_P (op0)
3486       && REGNO (op0) >= FIRST_PSEUDO_REGISTER)
3487     safe = 1;
3488
3489   op1 = gen_label_rtx ();
3490   if (target == 0 || ! safe
3491       || GET_MODE (target) != mode
3492       || (MEM_P (target) && MEM_VOLATILE_P (target))
3493       || (REG_P (target)
3494           && REGNO (target) < FIRST_PSEUDO_REGISTER))
3495     target = gen_reg_rtx (mode);
3496
3497   emit_move_insn (target, op0);
3498   NO_DEFER_POP;
3499
3500   do_compare_rtx_and_jump (target, CONST0_RTX (mode), GE, 0, mode,
3501                            NULL_RTX, NULL_RTX, op1, -1);
3502
3503   op0 = expand_unop (mode, result_unsignedp ? neg_optab : negv_optab,
3504                      target, target, 0);
3505   if (op0 != target)
3506     emit_move_insn (target, op0);
3507   emit_label (op1);
3508   OK_DEFER_POP;
3509   return target;
3510 }
3511
3512 /* A subroutine of expand_copysign, perform the copysign operation using the
3513    abs and neg primitives advertised to exist on the target.  The assumption
3514    is that we have a split register file, and leaving op0 in fp registers,
3515    and not playing with subregs so much, will help the register allocator.  */
3516
3517 static rtx
3518 expand_copysign_absneg (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3519                         int bitpos, bool op0_is_abs)
3520 {
3521   enum machine_mode imode;
3522   int icode;
3523   rtx sign, label;
3524
3525   if (target == op1)
3526     target = NULL_RTX;
3527
3528   /* Check if the back end provides an insn that handles signbit for the
3529      argument's mode. */
3530   icode = (int) signbit_optab->handlers [(int) mode].insn_code;
3531   if (icode != CODE_FOR_nothing)
3532     {
3533       imode = insn_data[icode].operand[0].mode;
3534       sign = gen_reg_rtx (imode);
3535       emit_unop_insn (icode, sign, op1, UNKNOWN);
3536     }
3537   else
3538     {
3539       HOST_WIDE_INT hi, lo;
3540
3541       if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
3542         {
3543           imode = int_mode_for_mode (mode);
3544           if (imode == BLKmode)
3545             return NULL_RTX;
3546           op1 = gen_lowpart (imode, op1);
3547         }
3548       else
3549         {
3550           int word;
3551
3552           imode = word_mode;
3553           if (FLOAT_WORDS_BIG_ENDIAN)
3554             word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
3555           else
3556             word = bitpos / BITS_PER_WORD;
3557           bitpos = bitpos % BITS_PER_WORD;
3558           op1 = operand_subword_force (op1, word, mode);
3559         }
3560
3561       if (bitpos < HOST_BITS_PER_WIDE_INT)
3562         {
3563           hi = 0;
3564           lo = (HOST_WIDE_INT) 1 << bitpos;
3565         }
3566       else
3567         {
3568           hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
3569           lo = 0;
3570         }
3571
3572       sign = gen_reg_rtx (imode);
3573       sign = expand_binop (imode, and_optab, op1,
3574                            immed_double_const (lo, hi, imode),
3575                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
3576     }
3577
3578   if (!op0_is_abs)
3579     {
3580       op0 = expand_unop (mode, abs_optab, op0, target, 0);
3581       if (op0 == NULL)
3582         return NULL_RTX;
3583       target = op0;
3584     }
3585   else
3586     {
3587       if (target == NULL_RTX)
3588         target = copy_to_reg (op0);
3589       else
3590         emit_move_insn (target, op0);
3591     }
3592
3593   label = gen_label_rtx ();
3594   emit_cmp_and_jump_insns (sign, const0_rtx, EQ, NULL_RTX, imode, 1, label);
3595
3596   if (GET_CODE (op0) == CONST_DOUBLE)
3597     op0 = simplify_unary_operation (NEG, mode, op0, mode);
3598   else
3599     op0 = expand_unop (mode, neg_optab, op0, target, 0);
3600   if (op0 != target)
3601     emit_move_insn (target, op0);
3602
3603   emit_label (label);
3604
3605   return target;
3606 }
3607
3608
3609 /* A subroutine of expand_copysign, perform the entire copysign operation
3610    with integer bitmasks.  BITPOS is the position of the sign bit; OP0_IS_ABS
3611    is true if op0 is known to have its sign bit clear.  */
3612
3613 static rtx
3614 expand_copysign_bit (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3615                      int bitpos, bool op0_is_abs)
3616 {
3617   enum machine_mode imode;
3618   HOST_WIDE_INT hi, lo;
3619   int word, nwords, i;
3620   rtx temp, insns;
3621
3622   if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
3623     {
3624       imode = int_mode_for_mode (mode);
3625       if (imode == BLKmode)
3626         return NULL_RTX;
3627       word = 0;
3628       nwords = 1;
3629     }
3630   else
3631     {
3632       imode = word_mode;
3633
3634       if (FLOAT_WORDS_BIG_ENDIAN)
3635         word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
3636       else
3637         word = bitpos / BITS_PER_WORD;
3638       bitpos = bitpos % BITS_PER_WORD;
3639       nwords = (GET_MODE_BITSIZE (mode) + BITS_PER_WORD - 1) / BITS_PER_WORD;
3640     }
3641
3642   if (bitpos < HOST_BITS_PER_WIDE_INT)
3643     {
3644       hi = 0;
3645       lo = (HOST_WIDE_INT) 1 << bitpos;
3646     }
3647   else
3648     {
3649       hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
3650       lo = 0;
3651     }
3652
3653   if (target == 0 || target == op0 || target == op1)
3654     target = gen_reg_rtx (mode);
3655
3656   if (nwords > 1)
3657     {
3658       start_sequence ();
3659
3660       for (i = 0; i < nwords; ++i)
3661         {
3662           rtx targ_piece = operand_subword (target, i, 1, mode);
3663           rtx op0_piece = operand_subword_force (op0, i, mode);
3664
3665           if (i == word)
3666             {
3667               if (!op0_is_abs)
3668                 op0_piece = expand_binop (imode, and_optab, op0_piece,
3669                                           immed_double_const (~lo, ~hi, imode),
3670                                           NULL_RTX, 1, OPTAB_LIB_WIDEN);
3671
3672               op1 = expand_binop (imode, and_optab,
3673                                   operand_subword_force (op1, i, mode),
3674                                   immed_double_const (lo, hi, imode),
3675                                   NULL_RTX, 1, OPTAB_LIB_WIDEN);
3676
3677               temp = expand_binop (imode, ior_optab, op0_piece, op1,
3678                                    targ_piece, 1, OPTAB_LIB_WIDEN);
3679               if (temp != targ_piece)
3680                 emit_move_insn (targ_piece, temp);
3681             }
3682           else
3683             emit_move_insn (targ_piece, op0_piece);
3684         }
3685
3686       insns = get_insns ();
3687       end_sequence ();
3688
3689       emit_insn (insns);
3690     }
3691   else
3692     {
3693       op1 = expand_binop (imode, and_optab, gen_lowpart (imode, op1),
3694                           immed_double_const (lo, hi, imode),
3695                           NULL_RTX, 1, OPTAB_LIB_WIDEN);
3696
3697       op0 = gen_lowpart (imode, op0);
3698       if (!op0_is_abs)
3699         op0 = expand_binop (imode, and_optab, op0,
3700                             immed_double_const (~lo, ~hi, imode),
3701                             NULL_RTX, 1, OPTAB_LIB_WIDEN);
3702
3703       temp = expand_binop (imode, ior_optab, op0, op1,
3704                            gen_lowpart (imode, target), 1, OPTAB_LIB_WIDEN);
3705       target = lowpart_subreg_maybe_copy (mode, temp, imode);
3706     }
3707
3708   return target;
3709 }
3710
3711 /* Expand the C99 copysign operation.  OP0 and OP1 must be the same
3712    scalar floating point mode.  Return NULL if we do not know how to
3713    expand the operation inline.  */
3714
3715 rtx
3716 expand_copysign (rtx op0, rtx op1, rtx target)
3717 {
3718   enum machine_mode mode = GET_MODE (op0);
3719   const struct real_format *fmt;
3720   bool op0_is_abs;
3721   rtx temp;
3722
3723   gcc_assert (SCALAR_FLOAT_MODE_P (mode));
3724   gcc_assert (GET_MODE (op1) == mode);
3725
3726   /* First try to do it with a special instruction.  */
3727   temp = expand_binop (mode, copysign_optab, op0, op1,
3728                        target, 0, OPTAB_DIRECT);
3729   if (temp)
3730     return temp;
3731
3732   fmt = REAL_MODE_FORMAT (mode);
3733   if (fmt == NULL || !fmt->has_signed_zero)
3734     return NULL_RTX;
3735
3736   op0_is_abs = false;
3737   if (GET_CODE (op0) == CONST_DOUBLE)
3738     {
3739       if (real_isneg (CONST_DOUBLE_REAL_VALUE (op0)))
3740         op0 = simplify_unary_operation (ABS, mode, op0, mode);
3741       op0_is_abs = true;
3742     }
3743
3744   if (fmt->signbit_ro >= 0
3745       && (GET_CODE (op0) == CONST_DOUBLE
3746           || (optab_handler (neg_optab, mode)->insn_code != CODE_FOR_nothing
3747               && optab_handler (abs_optab, mode)->insn_code != CODE_FOR_nothing)))
3748     {
3749       temp = expand_copysign_absneg (mode, op0, op1, target,
3750                                      fmt->signbit_ro, op0_is_abs);
3751       if (temp)
3752         return temp;
3753     }
3754
3755   if (fmt->signbit_rw < 0)
3756     return NULL_RTX;
3757   return expand_copysign_bit (mode, op0, op1, target,
3758                               fmt->signbit_rw, op0_is_abs);
3759 }
3760 \f
3761 /* Generate an instruction whose insn-code is INSN_CODE,
3762    with two operands: an output TARGET and an input OP0.
3763    TARGET *must* be nonzero, and the output is always stored there.
3764    CODE is an rtx code such that (CODE OP0) is an rtx that describes
3765    the value that is stored into TARGET. 
3766
3767    Return false if expansion failed.  */
3768
3769 bool
3770 maybe_emit_unop_insn (int icode, rtx target, rtx op0, enum rtx_code code)
3771 {
3772   rtx temp;
3773   enum machine_mode mode0 = insn_data[icode].operand[1].mode;
3774   rtx pat;
3775   rtx last = get_last_insn ();
3776
3777   temp = target;
3778
3779   /* Now, if insn does not accept our operands, put them into pseudos.  */
3780
3781   if (!insn_data[icode].operand[1].predicate (op0, mode0))
3782     op0 = copy_to_mode_reg (mode0, op0);
3783
3784   if (!insn_data[icode].operand[0].predicate (temp, GET_MODE (temp)))
3785     temp = gen_reg_rtx (GET_MODE (temp));
3786
3787   pat = GEN_FCN (icode) (temp, op0);
3788   if (!pat)
3789     {
3790       delete_insns_since (last);
3791       return false;
3792     }
3793
3794   if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX && code != UNKNOWN)
3795     add_equal_note (pat, temp, code, op0, NULL_RTX);
3796
3797   emit_insn (pat);
3798
3799   if (temp != target)
3800     emit_move_insn (target, temp);
3801   return true;
3802 }
3803 /* Generate an instruction whose insn-code is INSN_CODE,
3804    with two operands: an output TARGET and an input OP0.
3805    TARGET *must* be nonzero, and the output is always stored there.
3806    CODE is an rtx code such that (CODE OP0) is an rtx that describes
3807    the value that is stored into TARGET.  */
3808
3809 void
3810 emit_unop_insn (int icode, rtx target, rtx op0, enum rtx_code code)
3811 {
3812   bool ok = maybe_emit_unop_insn (icode, target, op0, code);
3813   gcc_assert (ok);
3814 }
3815 \f
3816 struct no_conflict_data
3817 {
3818   rtx target, first, insn;
3819   bool must_stay;
3820 };
3821
3822 /* Called via note_stores by emit_libcall_block.  Set P->must_stay if
3823    the currently examined clobber / store has to stay in the list of
3824    insns that constitute the actual libcall block.  */
3825 static void
3826 no_conflict_move_test (rtx dest, const_rtx set, void *p0)
3827 {
3828   struct no_conflict_data *p= (struct no_conflict_data *) p0;
3829
3830   /* If this inns directly contributes to setting the target, it must stay.  */
3831   if (reg_overlap_mentioned_p (p->target, dest))
3832     p->must_stay = true;
3833   /* If we haven't committed to keeping any other insns in the list yet,
3834      there is nothing more to check.  */
3835   else if (p->insn == p->first)
3836     return;
3837   /* If this insn sets / clobbers a register that feeds one of the insns
3838      already in the list, this insn has to stay too.  */
3839   else if (reg_overlap_mentioned_p (dest, PATTERN (p->first))
3840            || (CALL_P (p->first) && (find_reg_fusage (p->first, USE, dest)))
3841            || reg_used_between_p (dest, p->first, p->insn)
3842            /* Likewise if this insn depends on a register set by a previous
3843               insn in the list, or if it sets a result (presumably a hard
3844               register) that is set or clobbered by a previous insn.
3845               N.B. the modified_*_p (SET_DEST...) tests applied to a MEM
3846               SET_DEST perform the former check on the address, and the latter
3847               check on the MEM.  */
3848            || (GET_CODE (set) == SET
3849                && (modified_in_p (SET_SRC (set), p->first)
3850                    || modified_in_p (SET_DEST (set), p->first)
3851                    || modified_between_p (SET_SRC (set), p->first, p->insn)
3852                    || modified_between_p (SET_DEST (set), p->first, p->insn))))
3853     p->must_stay = true;
3854 }
3855
3856 \f
3857 /* Emit code to make a call to a constant function or a library call.
3858
3859    INSNS is a list containing all insns emitted in the call.
3860    These insns leave the result in RESULT.  Our block is to copy RESULT
3861    to TARGET, which is logically equivalent to EQUIV.
3862
3863    We first emit any insns that set a pseudo on the assumption that these are
3864    loading constants into registers; doing so allows them to be safely cse'ed
3865    between blocks.  Then we emit all the other insns in the block, followed by
3866    an insn to move RESULT to TARGET.  This last insn will have a REQ_EQUAL
3867    note with an operand of EQUIV.  */
3868
3869 void
3870 emit_libcall_block (rtx insns, rtx target, rtx result, rtx equiv)
3871 {
3872   rtx final_dest = target;
3873   rtx prev, next, last, insn;
3874
3875   /* If this is a reg with REG_USERVAR_P set, then it could possibly turn
3876      into a MEM later.  Protect the libcall block from this change.  */
3877   if (! REG_P (target) || REG_USERVAR_P (target))
3878     target = gen_reg_rtx (GET_MODE (target));
3879
3880   /* If we're using non-call exceptions, a libcall corresponding to an
3881      operation that may trap may also trap.  */
3882   if (flag_non_call_exceptions && may_trap_p (equiv))
3883     {
3884       for (insn = insns; insn; insn = NEXT_INSN (insn))
3885         if (CALL_P (insn))
3886           {
3887             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
3888
3889             if (note != 0 && INTVAL (XEXP (note, 0)) <= 0)
3890               remove_note (insn, note);
3891           }
3892     }
3893   else
3894   /* look for any CALL_INSNs in this sequence, and attach a REG_EH_REGION
3895      reg note to indicate that this call cannot throw or execute a nonlocal
3896      goto (unless there is already a REG_EH_REGION note, in which case
3897      we update it).  */
3898     for (insn = insns; insn; insn = NEXT_INSN (insn))
3899       if (CALL_P (insn))
3900         {
3901           rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
3902
3903           if (note != 0)
3904             XEXP (note, 0) = constm1_rtx;
3905           else
3906             add_reg_note (insn, REG_EH_REGION, constm1_rtx);
3907         }
3908
3909   /* First emit all insns that set pseudos.  Remove them from the list as
3910      we go.  Avoid insns that set pseudos which were referenced in previous
3911      insns.  These can be generated by move_by_pieces, for example,
3912      to update an address.  Similarly, avoid insns that reference things
3913      set in previous insns.  */
3914
3915   for (insn = insns; insn; insn = next)
3916     {
3917       rtx set = single_set (insn);
3918
3919       next = NEXT_INSN (insn);
3920
3921       if (set != 0 && REG_P (SET_DEST (set))
3922           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3923         {
3924           struct no_conflict_data data;
3925
3926           data.target = const0_rtx;
3927           data.first = insns;
3928           data.insn = insn;
3929           data.must_stay = 0;
3930           note_stores (PATTERN (insn), no_conflict_move_test, &data);
3931           if (! data.must_stay)
3932             {
3933               if (PREV_INSN (insn))
3934                 NEXT_INSN (PREV_INSN (insn)) = next;
3935               else
3936                 insns = next;
3937
3938               if (next)
3939                 PREV_INSN (next) = PREV_INSN (insn);
3940
3941               add_insn (insn);
3942             }
3943         }
3944
3945       /* Some ports use a loop to copy large arguments onto the stack.
3946          Don't move anything outside such a loop.  */
3947       if (LABEL_P (insn))
3948         break;
3949     }
3950
3951   prev = get_last_insn ();
3952
3953   /* Write the remaining insns followed by the final copy.  */
3954
3955   for (insn = insns; insn; insn = next)
3956     {
3957       next = NEXT_INSN (insn);
3958
3959       add_insn (insn);
3960     }
3961
3962   last = emit_move_insn (target, result);
3963   if (optab_handler (mov_optab, GET_MODE (target))->insn_code
3964       != CODE_FOR_nothing)
3965     set_unique_reg_note (last, REG_EQUAL, copy_rtx (equiv));
3966
3967   if (final_dest != target)
3968     emit_move_insn (final_dest, target);
3969 }
3970 \f
3971 /* Nonzero if we can perform a comparison of mode MODE straightforwardly.
3972    PURPOSE describes how this comparison will be used.  CODE is the rtx
3973    comparison code we will be using.
3974
3975    ??? Actually, CODE is slightly weaker than that.  A target is still
3976    required to implement all of the normal bcc operations, but not
3977    required to implement all (or any) of the unordered bcc operations.  */
3978
3979 int
3980 can_compare_p (enum rtx_code code, enum machine_mode mode,
3981                enum can_compare_purpose purpose)
3982 {
3983   do
3984     {
3985       if (optab_handler (cmp_optab, mode)->insn_code != CODE_FOR_nothing)
3986         {
3987           if (purpose == ccp_jump)
3988             return bcc_gen_fctn[(int) code] != NULL;
3989           else if (purpose == ccp_store_flag)
3990             return setcc_gen_code[(int) code] != CODE_FOR_nothing;
3991           else
3992             /* There's only one cmov entry point, and it's allowed to fail.  */
3993             return 1;
3994         }
3995       if (purpose == ccp_jump
3996           && optab_handler (cbranch_optab, mode)->insn_code != CODE_FOR_nothing)
3997         return 1;
3998       if (purpose == ccp_cmov
3999           && optab_handler (cmov_optab, mode)->insn_code != CODE_FOR_nothing)
4000         return 1;
4001       if (purpose == ccp_store_flag
4002           && optab_handler (cstore_optab, mode)->insn_code != CODE_FOR_nothing)
4003         return 1;
4004       mode = GET_MODE_WIDER_MODE (mode);
4005     }
4006   while (mode != VOIDmode);
4007
4008   return 0;
4009 }
4010
4011 /* This function is called when we are going to emit a compare instruction that
4012    compares the values found in *PX and *PY, using the rtl operator COMPARISON.
4013
4014    *PMODE is the mode of the inputs (in case they are const_int).
4015    *PUNSIGNEDP nonzero says that the operands are unsigned;
4016    this matters if they need to be widened.
4017
4018    If they have mode BLKmode, then SIZE specifies the size of both operands.
4019
4020    This function performs all the setup necessary so that the caller only has
4021    to emit a single comparison insn.  This setup can involve doing a BLKmode
4022    comparison or emitting a library call to perform the comparison if no insn
4023    is available to handle it.
4024    The values which are passed in through pointers can be modified; the caller
4025    should perform the comparison on the modified values.  Constant
4026    comparisons must have already been folded.  */
4027
4028 static void
4029 prepare_cmp_insn (rtx *px, rtx *py, enum rtx_code *pcomparison, rtx size,
4030                   enum machine_mode *pmode, int *punsignedp,
4031                   enum can_compare_purpose purpose)
4032 {
4033   enum machine_mode mode = *pmode;
4034   rtx x = *px, y = *py;
4035   int unsignedp = *punsignedp;
4036   rtx libfunc;
4037
4038   /* If we are inside an appropriately-short loop and we are optimizing,
4039      force expensive constants into a register.  */
4040   if (CONSTANT_P (x) && optimize
4041       && (rtx_cost (x, COMPARE, optimize_insn_for_speed_p ())
4042           > COSTS_N_INSNS (1)))
4043     x = force_reg (mode, x);
4044
4045   if (CONSTANT_P (y) && optimize
4046       && (rtx_cost (y, COMPARE, optimize_insn_for_speed_p ())
4047           > COSTS_N_INSNS (1)))
4048     y = force_reg (mode, y);
4049
4050 #ifdef HAVE_cc0
4051   /* Make sure if we have a canonical comparison.  The RTL
4052      documentation states that canonical comparisons are required only
4053      for targets which have cc0.  */
4054   gcc_assert (!CONSTANT_P (x) || CONSTANT_P (y));
4055 #endif
4056
4057   /* Don't let both operands fail to indicate the mode.  */
4058   if (GET_MODE (x) == VOIDmode && GET_MODE (y) == VOIDmode)
4059     x = force_reg (mode, x);
4060
4061   /* Handle all BLKmode compares.  */
4062
4063   if (mode == BLKmode)
4064     {
4065       enum machine_mode cmp_mode, result_mode;
4066       enum insn_code cmp_code;
4067       tree length_type;
4068       rtx libfunc;
4069       rtx result;
4070       rtx opalign
4071         = GEN_INT (MIN (MEM_ALIGN (x), MEM_ALIGN (y)) / BITS_PER_UNIT);
4072
4073       gcc_assert (size);
4074
4075       /* Try to use a memory block compare insn - either cmpstr
4076          or cmpmem will do.  */
4077       for (cmp_mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
4078            cmp_mode != VOIDmode;
4079            cmp_mode = GET_MODE_WIDER_MODE (cmp_mode))
4080         {
4081           cmp_code = cmpmem_optab[cmp_mode];
4082           if (cmp_code == CODE_FOR_nothing)
4083             cmp_code = cmpstr_optab[cmp_mode];
4084           if (cmp_code == CODE_FOR_nothing)
4085             cmp_code = cmpstrn_optab[cmp_mode];
4086           if (cmp_code == CODE_FOR_nothing)
4087             continue;
4088
4089           /* Must make sure the size fits the insn's mode.  */
4090           if ((GET_CODE (size) == CONST_INT
4091                && INTVAL (size) >= (1 << GET_MODE_BITSIZE (cmp_mode)))
4092               || (GET_MODE_BITSIZE (GET_MODE (size))
4093                   > GET_MODE_BITSIZE (cmp_mode)))
4094             continue;
4095
4096           result_mode = insn_data[cmp_code].operand[0].mode;
4097           result = gen_reg_rtx (result_mode);
4098           size = convert_to_mode (cmp_mode, size, 1);
4099           emit_insn (GEN_FCN (cmp_code) (result, x, y, size, opalign));
4100
4101           *px = result;
4102           *py = const0_rtx;
4103           *pmode = result_mode;
4104           return;
4105         }
4106
4107       /* Otherwise call a library function, memcmp.  */
4108       libfunc = memcmp_libfunc;
4109       length_type = sizetype;
4110       result_mode = TYPE_MODE (integer_type_node);
4111       cmp_mode = TYPE_MODE (length_type);
4112       size = convert_to_mode (TYPE_MODE (length_type), size,
4113                               TYPE_UNSIGNED (length_type));
4114
4115       result = emit_library_call_value (libfunc, 0, LCT_PURE,
4116                                         result_mode, 3,
4117                                         XEXP (x, 0), Pmode,
4118                                         XEXP (y, 0), Pmode,
4119