OSDN Git Service

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