OSDN Git Service

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