OSDN Git Service

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