OSDN Git Service

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