OSDN Git Service

5ed810176e13eb08f9762721826351ae3e567498
[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 (optimize
1363       && CONSTANT_P (x)
1364       && rtx_cost (x, binoptab->code) > COSTS_N_INSNS (1))
1365     {
1366       if (GET_CODE (x) == CONST_INT)
1367         {
1368           HOST_WIDE_INT intval = trunc_int_for_mode (INTVAL (x), mode);
1369           if (intval != INTVAL (x))
1370             x = GEN_INT (intval);
1371         }
1372       else
1373         x = convert_modes (mode, VOIDmode, x, unsignedp);
1374       x = force_reg (mode, x);
1375     }
1376   return x;
1377 }
1378
1379 /* Helper function for expand_binop: handle the case where there
1380    is an insn that directly implements the indicated operation.
1381    Returns null if this is not possible.  */
1382 static rtx
1383 expand_binop_directly (enum machine_mode mode, optab binoptab,
1384                        rtx op0, rtx op1,
1385                        rtx target, int unsignedp, enum optab_methods methods,
1386                        rtx last)
1387 {
1388   int icode = (int) optab_handler (binoptab, mode)->insn_code;
1389   enum machine_mode mode0 = insn_data[icode].operand[1].mode;
1390   enum machine_mode mode1 = insn_data[icode].operand[2].mode;
1391   enum machine_mode tmp_mode;
1392   bool commutative_p;
1393   rtx pat;
1394   rtx xop0 = op0, xop1 = op1;
1395   rtx temp;
1396   rtx swap;
1397   
1398   if (target)
1399     temp = target;
1400   else
1401     temp = gen_reg_rtx (mode);
1402
1403   /* If it is a commutative operator and the modes would match
1404      if we would swap the operands, we can save the conversions.  */
1405   commutative_p = commutative_optab_p (binoptab);
1406   if (commutative_p
1407       && GET_MODE (xop0) != mode0 && GET_MODE (xop1) != mode1
1408       && GET_MODE (xop0) == mode1 && GET_MODE (xop1) == mode1)
1409     {
1410       swap = xop0;
1411       xop0 = xop1;
1412       xop1 = swap;
1413     }
1414   
1415   /* If we are optimizing, force expensive constants into a register.  */
1416   xop0 = avoid_expensive_constant (mode0, binoptab, xop0, unsignedp);
1417   if (!shift_optab_p (binoptab))
1418     xop1 = avoid_expensive_constant (mode1, binoptab, xop1, unsignedp);
1419
1420   /* In case the insn wants input operands in modes different from
1421      those of the actual operands, convert the operands.  It would
1422      seem that we don't need to convert CONST_INTs, but we do, so
1423      that they're properly zero-extended, sign-extended or truncated
1424      for their mode.  */
1425   
1426   if (GET_MODE (xop0) != mode0 && mode0 != VOIDmode)
1427     xop0 = convert_modes (mode0,
1428                           GET_MODE (xop0) != VOIDmode
1429                           ? GET_MODE (xop0)
1430                           : mode,
1431                           xop0, unsignedp);
1432   
1433   if (GET_MODE (xop1) != mode1 && mode1 != VOIDmode)
1434     xop1 = convert_modes (mode1,
1435                           GET_MODE (xop1) != VOIDmode
1436                           ? GET_MODE (xop1)
1437                           : mode,
1438                           xop1, unsignedp);
1439   
1440   /* If operation is commutative,
1441      try to make the first operand a register.
1442      Even better, try to make it the same as the target.
1443      Also try to make the last operand a constant.  */
1444   if (commutative_p
1445       && swap_commutative_operands_with_target (target, xop0, xop1))
1446     {
1447       swap = xop1;
1448       xop1 = xop0;
1449       xop0 = swap;
1450     }
1451
1452   /* Now, if insn's predicates don't allow our operands, put them into
1453      pseudo regs.  */
1454   
1455   if (!insn_data[icode].operand[1].predicate (xop0, mode0)
1456       && mode0 != VOIDmode)
1457     xop0 = copy_to_mode_reg (mode0, xop0);
1458   
1459   if (!insn_data[icode].operand[2].predicate (xop1, mode1)
1460       && mode1 != VOIDmode)
1461     xop1 = copy_to_mode_reg (mode1, xop1);
1462   
1463   if (binoptab == vec_pack_trunc_optab 
1464       || binoptab == vec_pack_usat_optab
1465       || binoptab == vec_pack_ssat_optab
1466       || binoptab == vec_pack_ufix_trunc_optab
1467       || binoptab == vec_pack_sfix_trunc_optab)
1468     {
1469       /* The mode of the result is different then the mode of the
1470          arguments.  */
1471       tmp_mode = insn_data[icode].operand[0].mode;
1472       if (GET_MODE_NUNITS (tmp_mode) != 2 * GET_MODE_NUNITS (mode))
1473         return 0;
1474     }
1475   else
1476     tmp_mode = mode;
1477
1478   if (!insn_data[icode].operand[0].predicate (temp, tmp_mode))
1479     temp = gen_reg_rtx (tmp_mode);
1480   
1481   pat = GEN_FCN (icode) (temp, xop0, xop1);
1482   if (pat)
1483     {
1484       /* If PAT is composed of more than one insn, try to add an appropriate
1485          REG_EQUAL note to it.  If we can't because TEMP conflicts with an
1486          operand, call expand_binop again, this time without a target.  */
1487       if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX
1488           && ! add_equal_note (pat, temp, binoptab->code, xop0, xop1))
1489         {
1490           delete_insns_since (last);
1491           return expand_binop (mode, binoptab, op0, op1, NULL_RTX,
1492                                unsignedp, methods);
1493         }
1494       
1495       emit_insn (pat);
1496       return temp;
1497     }
1498
1499   delete_insns_since (last);
1500   return NULL_RTX;
1501 }
1502
1503 /* Generate code to perform an operation specified by BINOPTAB
1504    on operands OP0 and OP1, with result having machine-mode MODE.
1505
1506    UNSIGNEDP is for the case where we have to widen the operands
1507    to perform the operation.  It says to use zero-extension.
1508
1509    If TARGET is nonzero, the value
1510    is generated there, if it is convenient to do so.
1511    In all cases an rtx is returned for the locus of the value;
1512    this may or may not be TARGET.  */
1513
1514 rtx
1515 expand_binop (enum machine_mode mode, optab binoptab, rtx op0, rtx op1,
1516               rtx target, int unsignedp, enum optab_methods methods)
1517 {
1518   enum optab_methods next_methods
1519     = (methods == OPTAB_LIB || methods == OPTAB_LIB_WIDEN
1520        ? OPTAB_WIDEN : methods);
1521   enum mode_class class;
1522   enum machine_mode wider_mode;
1523   rtx libfunc;
1524   rtx temp;
1525   rtx entry_last = get_last_insn ();
1526   rtx last;
1527
1528   class = GET_MODE_CLASS (mode);
1529
1530   /* If subtracting an integer constant, convert this into an addition of
1531      the negated constant.  */
1532
1533   if (binoptab == sub_optab && GET_CODE (op1) == CONST_INT)
1534     {
1535       op1 = negate_rtx (mode, op1);
1536       binoptab = add_optab;
1537     }
1538
1539   /* Record where to delete back to if we backtrack.  */
1540   last = get_last_insn ();
1541
1542   /* If we can do it with a three-operand insn, do so.  */
1543
1544   if (methods != OPTAB_MUST_WIDEN
1545       && optab_handler (binoptab, mode)->insn_code != CODE_FOR_nothing)
1546     {
1547       temp = expand_binop_directly (mode, binoptab, op0, op1, target,
1548                                     unsignedp, methods, last);
1549       if (temp)
1550         return temp;
1551     }
1552
1553   /* If we were trying to rotate, and that didn't work, try rotating
1554      the other direction before falling back to shifts and bitwise-or.  */
1555   if (((binoptab == rotl_optab
1556         && optab_handler (rotr_optab, mode)->insn_code != CODE_FOR_nothing)
1557        || (binoptab == rotr_optab
1558            && optab_handler (rotl_optab, mode)->insn_code != CODE_FOR_nothing))
1559       && class == MODE_INT)
1560     {
1561       optab otheroptab = (binoptab == rotl_optab ? rotr_optab : rotl_optab);
1562       rtx newop1;
1563       unsigned int bits = GET_MODE_BITSIZE (mode);
1564
1565       if (GET_CODE (op1) == CONST_INT)
1566         newop1 = GEN_INT (bits - INTVAL (op1));
1567       else if (targetm.shift_truncation_mask (mode) == bits - 1)
1568         newop1 = negate_rtx (mode, op1);
1569       else
1570         newop1 = expand_binop (mode, sub_optab,
1571                                GEN_INT (bits), op1,
1572                                NULL_RTX, unsignedp, OPTAB_DIRECT);
1573                                    
1574       temp = expand_binop_directly (mode, otheroptab, op0, newop1,
1575                                     target, unsignedp, methods, last);
1576       if (temp)
1577         return temp;
1578     }
1579
1580   /* If this is a multiply, see if we can do a widening operation that
1581      takes operands of this mode and makes a wider mode.  */
1582
1583   if (binoptab == smul_optab
1584       && GET_MODE_WIDER_MODE (mode) != VOIDmode
1585       && ((optab_handler ((unsignedp ? umul_widen_optab : smul_widen_optab),
1586                           GET_MODE_WIDER_MODE (mode))->insn_code)
1587           != CODE_FOR_nothing))
1588     {
1589       temp = expand_binop (GET_MODE_WIDER_MODE (mode),
1590                            unsignedp ? umul_widen_optab : smul_widen_optab,
1591                            op0, op1, NULL_RTX, unsignedp, OPTAB_DIRECT);
1592
1593       if (temp != 0)
1594         {
1595           if (GET_MODE_CLASS (mode) == MODE_INT
1596               && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1597                                         GET_MODE_BITSIZE (GET_MODE (temp))))
1598             return gen_lowpart (mode, temp);
1599           else
1600             return convert_to_mode (mode, temp, unsignedp);
1601         }
1602     }
1603
1604   /* Look for a wider mode of the same class for which we think we
1605      can open-code the operation.  Check for a widening multiply at the
1606      wider mode as well.  */
1607
1608   if (CLASS_HAS_WIDER_MODES_P (class)
1609       && methods != OPTAB_DIRECT && methods != OPTAB_LIB)
1610     for (wider_mode = GET_MODE_WIDER_MODE (mode);
1611          wider_mode != VOIDmode;
1612          wider_mode = GET_MODE_WIDER_MODE (wider_mode))
1613       {
1614         if (optab_handler (binoptab, wider_mode)->insn_code != CODE_FOR_nothing
1615             || (binoptab == smul_optab
1616                 && GET_MODE_WIDER_MODE (wider_mode) != VOIDmode
1617                 && ((optab_handler ((unsignedp ? umul_widen_optab
1618                                      : smul_widen_optab),
1619                                      GET_MODE_WIDER_MODE (wider_mode))->insn_code)
1620                     != CODE_FOR_nothing)))
1621           {
1622             rtx xop0 = op0, xop1 = op1;
1623             int no_extend = 0;
1624
1625             /* For certain integer operations, we need not actually extend
1626                the narrow operands, as long as we will truncate
1627                the results to the same narrowness.  */
1628
1629             if ((binoptab == ior_optab || binoptab == and_optab
1630                  || binoptab == xor_optab
1631                  || binoptab == add_optab || binoptab == sub_optab
1632                  || binoptab == smul_optab || binoptab == ashl_optab)
1633                 && class == MODE_INT)
1634               {
1635                 no_extend = 1;
1636                 xop0 = avoid_expensive_constant (mode, binoptab,
1637                                                  xop0, unsignedp);
1638                 if (binoptab != ashl_optab)
1639                   xop1 = avoid_expensive_constant (mode, binoptab,
1640                                                    xop1, unsignedp);
1641               }
1642
1643             xop0 = widen_operand (xop0, wider_mode, mode, unsignedp, no_extend);
1644
1645             /* The second operand of a shift must always be extended.  */
1646             xop1 = widen_operand (xop1, wider_mode, mode, unsignedp,
1647                                   no_extend && binoptab != ashl_optab);
1648
1649             temp = expand_binop (wider_mode, binoptab, xop0, xop1, NULL_RTX,
1650                                  unsignedp, OPTAB_DIRECT);
1651             if (temp)
1652               {
1653                 if (class != MODE_INT
1654                     || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1655                                                GET_MODE_BITSIZE (wider_mode)))
1656                   {
1657                     if (target == 0)
1658                       target = gen_reg_rtx (mode);
1659                     convert_move (target, temp, 0);
1660                     return target;
1661                   }
1662                 else
1663                   return gen_lowpart (mode, temp);
1664               }
1665             else
1666               delete_insns_since (last);
1667           }
1668       }
1669
1670   /* If operation is commutative,
1671      try to make the first operand a register.
1672      Even better, try to make it the same as the target.
1673      Also try to make the last operand a constant.  */
1674   if (commutative_optab_p (binoptab)
1675       && swap_commutative_operands_with_target (target, op0, op1))
1676     {
1677       temp = op1;
1678       op1 = op0;
1679       op0 = temp;
1680     }
1681
1682   /* These can be done a word at a time.  */
1683   if ((binoptab == and_optab || binoptab == ior_optab || binoptab == xor_optab)
1684       && class == MODE_INT
1685       && GET_MODE_SIZE (mode) > UNITS_PER_WORD
1686       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing)
1687     {
1688       int i;
1689       rtx insns;
1690       rtx equiv_value;
1691
1692       /* If TARGET is the same as one of the operands, the REG_EQUAL note
1693          won't be accurate, so use a new target.  */
1694       if (target == 0 || target == op0 || target == op1)
1695         target = gen_reg_rtx (mode);
1696
1697       start_sequence ();
1698
1699       /* Do the actual arithmetic.  */
1700       for (i = 0; i < GET_MODE_BITSIZE (mode) / BITS_PER_WORD; i++)
1701         {
1702           rtx target_piece = operand_subword (target, i, 1, mode);
1703           rtx x = expand_binop (word_mode, binoptab,
1704                                 operand_subword_force (op0, i, mode),
1705                                 operand_subword_force (op1, i, mode),
1706                                 target_piece, unsignedp, next_methods);
1707
1708           if (x == 0)
1709             break;
1710
1711           if (target_piece != x)
1712             emit_move_insn (target_piece, x);
1713         }
1714
1715       insns = get_insns ();
1716       end_sequence ();
1717
1718       if (i == GET_MODE_BITSIZE (mode) / BITS_PER_WORD)
1719         {
1720           if (binoptab->code != UNKNOWN)
1721             equiv_value
1722               = gen_rtx_fmt_ee (binoptab->code, mode,
1723                                 copy_rtx (op0), copy_rtx (op1));
1724           else
1725             equiv_value = 0;
1726
1727           emit_no_conflict_block (insns, target, op0, op1, equiv_value);
1728           return target;
1729         }
1730     }
1731
1732   /* Synthesize double word shifts from single word shifts.  */
1733   if ((binoptab == lshr_optab || binoptab == ashl_optab
1734        || binoptab == ashr_optab)
1735       && class == MODE_INT
1736       && (GET_CODE (op1) == CONST_INT || !optimize_size)
1737       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
1738       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing
1739       && optab_handler (ashl_optab, word_mode)->insn_code != CODE_FOR_nothing
1740       && optab_handler (lshr_optab, word_mode)->insn_code != CODE_FOR_nothing)
1741     {
1742       unsigned HOST_WIDE_INT shift_mask, double_shift_mask;
1743       enum machine_mode op1_mode;
1744
1745       double_shift_mask = targetm.shift_truncation_mask (mode);
1746       shift_mask = targetm.shift_truncation_mask (word_mode);
1747       op1_mode = GET_MODE (op1) != VOIDmode ? GET_MODE (op1) : word_mode;
1748
1749       /* Apply the truncation to constant shifts.  */
1750       if (double_shift_mask > 0 && GET_CODE (op1) == CONST_INT)
1751         op1 = GEN_INT (INTVAL (op1) & double_shift_mask);
1752
1753       if (op1 == CONST0_RTX (op1_mode))
1754         return op0;
1755
1756       /* Make sure that this is a combination that expand_doubleword_shift
1757          can handle.  See the comments there for details.  */
1758       if (double_shift_mask == 0
1759           || (shift_mask == BITS_PER_WORD - 1
1760               && double_shift_mask == BITS_PER_WORD * 2 - 1))
1761         {
1762           rtx insns, equiv_value;
1763           rtx into_target, outof_target;
1764           rtx into_input, outof_input;
1765           int left_shift, outof_word;
1766
1767           /* If TARGET is the same as one of the operands, the REG_EQUAL note
1768              won't be accurate, so use a new target.  */
1769           if (target == 0 || target == op0 || target == op1)
1770             target = gen_reg_rtx (mode);
1771
1772           start_sequence ();
1773
1774           /* OUTOF_* is the word we are shifting bits away from, and
1775              INTO_* is the word that we are shifting bits towards, thus
1776              they differ depending on the direction of the shift and
1777              WORDS_BIG_ENDIAN.  */
1778
1779           left_shift = binoptab == ashl_optab;
1780           outof_word = left_shift ^ ! WORDS_BIG_ENDIAN;
1781
1782           outof_target = operand_subword (target, outof_word, 1, mode);
1783           into_target = operand_subword (target, 1 - outof_word, 1, mode);
1784
1785           outof_input = operand_subword_force (op0, outof_word, mode);
1786           into_input = operand_subword_force (op0, 1 - outof_word, mode);
1787
1788           if (expand_doubleword_shift (op1_mode, binoptab,
1789                                        outof_input, into_input, op1,
1790                                        outof_target, into_target,
1791                                        unsignedp, next_methods, shift_mask))
1792             {
1793               insns = get_insns ();
1794               end_sequence ();
1795
1796               equiv_value = gen_rtx_fmt_ee (binoptab->code, mode, op0, op1);
1797               emit_no_conflict_block (insns, target, op0, op1, equiv_value);
1798               return target;
1799             }
1800           end_sequence ();
1801         }
1802     }
1803
1804   /* Synthesize double word rotates from single word shifts.  */
1805   if ((binoptab == rotl_optab || binoptab == rotr_optab)
1806       && class == MODE_INT
1807       && GET_CODE (op1) == CONST_INT
1808       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
1809       && optab_handler (ashl_optab, word_mode)->insn_code != CODE_FOR_nothing
1810       && optab_handler (lshr_optab, word_mode)->insn_code != CODE_FOR_nothing)
1811     {
1812       rtx insns;
1813       rtx into_target, outof_target;
1814       rtx into_input, outof_input;
1815       rtx inter;
1816       int shift_count, left_shift, outof_word;
1817
1818       /* If TARGET is the same as one of the operands, the REG_EQUAL note
1819          won't be accurate, so use a new target. Do this also if target is not
1820          a REG, first because having a register instead may open optimization
1821          opportunities, and second because if target and op0 happen to be MEMs
1822          designating the same location, we would risk clobbering it too early
1823          in the code sequence we generate below.  */
1824       if (target == 0 || target == op0 || target == op1 || ! REG_P (target))
1825         target = gen_reg_rtx (mode);
1826
1827       start_sequence ();
1828
1829       shift_count = INTVAL (op1);
1830
1831       /* OUTOF_* is the word we are shifting bits away from, and
1832          INTO_* is the word that we are shifting bits towards, thus
1833          they differ depending on the direction of the shift and
1834          WORDS_BIG_ENDIAN.  */
1835
1836       left_shift = (binoptab == rotl_optab);
1837       outof_word = left_shift ^ ! WORDS_BIG_ENDIAN;
1838
1839       outof_target = operand_subword (target, outof_word, 1, mode);
1840       into_target = operand_subword (target, 1 - outof_word, 1, mode);
1841
1842       outof_input = operand_subword_force (op0, outof_word, mode);
1843       into_input = operand_subword_force (op0, 1 - outof_word, mode);
1844
1845       if (shift_count == BITS_PER_WORD)
1846         {
1847           /* This is just a word swap.  */
1848           emit_move_insn (outof_target, into_input);
1849           emit_move_insn (into_target, outof_input);
1850           inter = const0_rtx;
1851         }
1852       else
1853         {
1854           rtx into_temp1, into_temp2, outof_temp1, outof_temp2;
1855           rtx first_shift_count, second_shift_count;
1856           optab reverse_unsigned_shift, unsigned_shift;
1857
1858           reverse_unsigned_shift = (left_shift ^ (shift_count < BITS_PER_WORD)
1859                                     ? lshr_optab : ashl_optab);
1860
1861           unsigned_shift = (left_shift ^ (shift_count < BITS_PER_WORD)
1862                             ? ashl_optab : lshr_optab);
1863
1864           if (shift_count > BITS_PER_WORD)
1865             {
1866               first_shift_count = GEN_INT (shift_count - BITS_PER_WORD);
1867               second_shift_count = GEN_INT (2 * BITS_PER_WORD - shift_count);
1868             }
1869           else
1870             {
1871               first_shift_count = GEN_INT (BITS_PER_WORD - shift_count);
1872               second_shift_count = GEN_INT (shift_count);
1873             }
1874
1875           into_temp1 = expand_binop (word_mode, unsigned_shift,
1876                                      outof_input, first_shift_count,
1877                                      NULL_RTX, unsignedp, next_methods);
1878           into_temp2 = expand_binop (word_mode, reverse_unsigned_shift,
1879                                      into_input, second_shift_count,
1880                                      NULL_RTX, unsignedp, next_methods);
1881
1882           if (into_temp1 != 0 && into_temp2 != 0)
1883             inter = expand_binop (word_mode, ior_optab, into_temp1, into_temp2,
1884                                   into_target, unsignedp, next_methods);
1885           else
1886             inter = 0;
1887
1888           if (inter != 0 && inter != into_target)
1889             emit_move_insn (into_target, inter);
1890
1891           outof_temp1 = expand_binop (word_mode, unsigned_shift,
1892                                       into_input, first_shift_count,
1893                                       NULL_RTX, unsignedp, next_methods);
1894           outof_temp2 = expand_binop (word_mode, reverse_unsigned_shift,
1895                                       outof_input, second_shift_count,
1896                                       NULL_RTX, unsignedp, next_methods);
1897
1898           if (inter != 0 && outof_temp1 != 0 && outof_temp2 != 0)
1899             inter = expand_binop (word_mode, ior_optab,
1900                                   outof_temp1, outof_temp2,
1901                                   outof_target, unsignedp, next_methods);
1902
1903           if (inter != 0 && inter != outof_target)
1904             emit_move_insn (outof_target, inter);
1905         }
1906
1907       insns = get_insns ();
1908       end_sequence ();
1909
1910       if (inter != 0)
1911         {
1912           /* One may be tempted to wrap the insns in a REG_NO_CONFLICT
1913              block to help the register allocator a bit.  But a multi-word
1914              rotate will need all the input bits when setting the output
1915              bits, so there clearly is a conflict between the input and
1916              output registers.  So we can't use a no-conflict block here.  */
1917           emit_insn (insns);
1918           return target;
1919         }
1920     }
1921
1922   /* These can be done a word at a time by propagating carries.  */
1923   if ((binoptab == add_optab || binoptab == sub_optab)
1924       && class == MODE_INT
1925       && GET_MODE_SIZE (mode) >= 2 * UNITS_PER_WORD
1926       && optab_handler (binoptab, word_mode)->insn_code != CODE_FOR_nothing)
1927     {
1928       unsigned int i;
1929       optab otheroptab = binoptab == add_optab ? sub_optab : add_optab;
1930       const unsigned int nwords = GET_MODE_BITSIZE (mode) / BITS_PER_WORD;
1931       rtx carry_in = NULL_RTX, carry_out = NULL_RTX;
1932       rtx xop0, xop1, xtarget;
1933
1934       /* We can handle either a 1 or -1 value for the carry.  If STORE_FLAG
1935          value is one of those, use it.  Otherwise, use 1 since it is the
1936          one easiest to get.  */
1937 #if STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1
1938       int normalizep = STORE_FLAG_VALUE;
1939 #else
1940       int normalizep = 1;
1941 #endif
1942
1943       /* Prepare the operands.  */
1944       xop0 = force_reg (mode, op0);
1945       xop1 = force_reg (mode, op1);
1946
1947       xtarget = gen_reg_rtx (mode);
1948
1949       if (target == 0 || !REG_P (target))
1950         target = xtarget;
1951
1952       /* Indicate for flow that the entire target reg is being set.  */
1953       if (REG_P (target))
1954         emit_insn (gen_rtx_CLOBBER (VOIDmode, xtarget));
1955
1956       /* Do the actual arithmetic.  */
1957       for (i = 0; i < nwords; i++)
1958         {
1959           int index = (WORDS_BIG_ENDIAN ? nwords - i - 1 : i);
1960           rtx target_piece = operand_subword (xtarget, index, 1, mode);
1961           rtx op0_piece = operand_subword_force (xop0, index, mode);
1962           rtx op1_piece = operand_subword_force (xop1, index, mode);
1963           rtx x;
1964
1965           /* Main add/subtract of the input operands.  */
1966           x = expand_binop (word_mode, binoptab,
1967                             op0_piece, op1_piece,
1968                             target_piece, unsignedp, next_methods);
1969           if (x == 0)
1970             break;
1971
1972           if (i + 1 < nwords)
1973             {
1974               /* Store carry from main add/subtract.  */
1975               carry_out = gen_reg_rtx (word_mode);
1976               carry_out = emit_store_flag_force (carry_out,
1977                                                  (binoptab == add_optab
1978                                                   ? LT : GT),
1979                                                  x, op0_piece,
1980                                                  word_mode, 1, normalizep);
1981             }
1982
1983           if (i > 0)
1984             {
1985               rtx newx;
1986
1987               /* Add/subtract previous carry to main result.  */
1988               newx = expand_binop (word_mode,
1989                                    normalizep == 1 ? binoptab : otheroptab,
1990                                    x, carry_in,
1991                                    NULL_RTX, 1, next_methods);
1992
1993               if (i + 1 < nwords)
1994                 {
1995                   /* Get out carry from adding/subtracting carry in.  */
1996                   rtx carry_tmp = gen_reg_rtx (word_mode);
1997                   carry_tmp = emit_store_flag_force (carry_tmp,
1998                                                      (binoptab == add_optab
1999                                                       ? LT : GT),
2000                                                      newx, x,
2001                                                      word_mode, 1, normalizep);
2002
2003                   /* Logical-ior the two poss. carry together.  */
2004                   carry_out = expand_binop (word_mode, ior_optab,
2005                                             carry_out, carry_tmp,
2006                                             carry_out, 0, next_methods);
2007                   if (carry_out == 0)
2008                     break;
2009                 }
2010               emit_move_insn (target_piece, newx);
2011             }
2012           else
2013             {
2014               if (x != target_piece)
2015                 emit_move_insn (target_piece, x);
2016             }
2017
2018           carry_in = carry_out;
2019         }
2020
2021       if (i == GET_MODE_BITSIZE (mode) / (unsigned) BITS_PER_WORD)
2022         {
2023           if (optab_handler (mov_optab, mode)->insn_code != CODE_FOR_nothing
2024               || ! rtx_equal_p (target, xtarget))
2025             {
2026               rtx temp = emit_move_insn (target, xtarget);
2027
2028               set_unique_reg_note (temp,
2029                                    REG_EQUAL,
2030                                    gen_rtx_fmt_ee (binoptab->code, mode,
2031                                                    copy_rtx (xop0),
2032                                                    copy_rtx (xop1)));
2033             }
2034           else
2035             target = xtarget;
2036
2037           return target;
2038         }
2039
2040       else
2041         delete_insns_since (last);
2042     }
2043
2044   /* Attempt to synthesize double word multiplies using a sequence of word
2045      mode multiplications.  We first attempt to generate a sequence using a
2046      more efficient unsigned widening multiply, and if that fails we then
2047      try using a signed widening multiply.  */
2048
2049   if (binoptab == smul_optab
2050       && class == MODE_INT
2051       && GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
2052       && optab_handler (smul_optab, word_mode)->insn_code != CODE_FOR_nothing
2053       && optab_handler (add_optab, word_mode)->insn_code != CODE_FOR_nothing)
2054     {
2055       rtx product = NULL_RTX;
2056
2057       if (optab_handler (umul_widen_optab, mode)->insn_code
2058           != CODE_FOR_nothing)
2059         {
2060           product = expand_doubleword_mult (mode, op0, op1, target,
2061                                             true, methods);
2062           if (!product)
2063             delete_insns_since (last);
2064         }
2065
2066       if (product == NULL_RTX
2067           && optab_handler (smul_widen_optab, mode)->insn_code
2068              != CODE_FOR_nothing)
2069         {
2070           product = expand_doubleword_mult (mode, op0, op1, target,
2071                                             false, methods);
2072           if (!product)
2073             delete_insns_since (last);
2074         }
2075
2076       if (product != NULL_RTX)
2077         {
2078           if (optab_handler (mov_optab, mode)->insn_code != CODE_FOR_nothing)
2079             {
2080               temp = emit_move_insn (target ? target : product, product);
2081               set_unique_reg_note (temp,
2082                                    REG_EQUAL,
2083                                    gen_rtx_fmt_ee (MULT, mode,
2084                                                    copy_rtx (op0),
2085                                                    copy_rtx (op1)));
2086             }
2087           return product;
2088         }
2089     }
2090
2091   /* It can't be open-coded in this mode.
2092      Use a library call if one is available and caller says that's ok.  */
2093
2094   libfunc = optab_libfunc (binoptab, mode);
2095   if (libfunc
2096       && (methods == OPTAB_LIB || methods == OPTAB_LIB_WIDEN))
2097     {
2098       rtx insns;
2099       rtx op1x = op1;
2100       enum machine_mode op1_mode = mode;
2101       rtx value;
2102
2103       start_sequence ();
2104
2105       if (shift_optab_p (binoptab))
2106         {
2107           op1_mode = targetm.libgcc_shift_count_mode ();
2108           /* Specify unsigned here,
2109              since negative shift counts are meaningless.  */
2110           op1x = convert_to_mode (op1_mode, op1, 1);
2111         }
2112
2113       if (GET_MODE (op0) != VOIDmode
2114           && GET_MODE (op0) != mode)
2115         op0 = convert_to_mode (mode, op0, unsignedp);
2116
2117       /* Pass 1 for NO_QUEUE so we don't lose any increments
2118          if the libcall is cse'd or moved.  */
2119       value = emit_library_call_value (libfunc,
2120                                        NULL_RTX, LCT_CONST, mode, 2,
2121                                        op0, mode, op1x, op1_mode);
2122
2123       insns = get_insns ();
2124       end_sequence ();
2125
2126       target = gen_reg_rtx (mode);
2127       emit_libcall_block (insns, target, value,
2128                           gen_rtx_fmt_ee (binoptab->code, mode, op0, op1));
2129
2130       return target;
2131     }
2132
2133   delete_insns_since (last);
2134
2135   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2136
2137   if (! (methods == OPTAB_WIDEN || methods == OPTAB_LIB_WIDEN
2138          || methods == OPTAB_MUST_WIDEN))
2139     {
2140       /* Caller says, don't even try.  */
2141       delete_insns_since (entry_last);
2142       return 0;
2143     }
2144
2145   /* Compute the value of METHODS to pass to recursive calls.
2146      Don't allow widening to be tried recursively.  */
2147
2148   methods = (methods == OPTAB_LIB_WIDEN ? OPTAB_LIB : OPTAB_DIRECT);
2149
2150   /* Look for a wider mode of the same class for which it appears we can do
2151      the operation.  */
2152
2153   if (CLASS_HAS_WIDER_MODES_P (class))
2154     {
2155       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2156            wider_mode != VOIDmode;
2157            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2158         {
2159           if ((optab_handler (binoptab, wider_mode)->insn_code
2160                != CODE_FOR_nothing)
2161               || (methods == OPTAB_LIB
2162                   && optab_libfunc (binoptab, wider_mode)))
2163             {
2164               rtx xop0 = op0, xop1 = op1;
2165               int no_extend = 0;
2166
2167               /* For certain integer operations, we need not actually extend
2168                  the narrow operands, as long as we will truncate
2169                  the results to the same narrowness.  */
2170
2171               if ((binoptab == ior_optab || binoptab == and_optab
2172                    || binoptab == xor_optab
2173                    || binoptab == add_optab || binoptab == sub_optab
2174                    || binoptab == smul_optab || binoptab == ashl_optab)
2175                   && class == MODE_INT)
2176                 no_extend = 1;
2177
2178               xop0 = widen_operand (xop0, wider_mode, mode,
2179                                     unsignedp, no_extend);
2180
2181               /* The second operand of a shift must always be extended.  */
2182               xop1 = widen_operand (xop1, wider_mode, mode, unsignedp,
2183                                     no_extend && binoptab != ashl_optab);
2184
2185               temp = expand_binop (wider_mode, binoptab, xop0, xop1, NULL_RTX,
2186                                    unsignedp, methods);
2187               if (temp)
2188                 {
2189                   if (class != MODE_INT
2190                       || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
2191                                                  GET_MODE_BITSIZE (wider_mode)))
2192                     {
2193                       if (target == 0)
2194                         target = gen_reg_rtx (mode);
2195                       convert_move (target, temp, 0);
2196                       return target;
2197                     }
2198                   else
2199                     return gen_lowpart (mode, temp);
2200                 }
2201               else
2202                 delete_insns_since (last);
2203             }
2204         }
2205     }
2206
2207   delete_insns_since (entry_last);
2208   return 0;
2209 }
2210 \f
2211 /* Expand a binary operator which has both signed and unsigned forms.
2212    UOPTAB is the optab for unsigned operations, and SOPTAB is for
2213    signed operations.
2214
2215    If we widen unsigned operands, we may use a signed wider operation instead
2216    of an unsigned wider operation, since the result would be the same.  */
2217
2218 rtx
2219 sign_expand_binop (enum machine_mode mode, optab uoptab, optab soptab,
2220                    rtx op0, rtx op1, rtx target, int unsignedp,
2221                    enum optab_methods methods)
2222 {
2223   rtx temp;
2224   optab direct_optab = unsignedp ? uoptab : soptab;
2225   struct optab wide_soptab;
2226
2227   /* Do it without widening, if possible.  */
2228   temp = expand_binop (mode, direct_optab, op0, op1, target,
2229                        unsignedp, OPTAB_DIRECT);
2230   if (temp || methods == OPTAB_DIRECT)
2231     return temp;
2232
2233   /* Try widening to a signed int.  Make a fake signed optab that
2234      hides any signed insn for direct use.  */
2235   wide_soptab = *soptab;
2236   optab_handler (&wide_soptab, mode)->insn_code = CODE_FOR_nothing;
2237
2238   temp = expand_binop (mode, &wide_soptab, op0, op1, target,
2239                        unsignedp, OPTAB_WIDEN);
2240
2241   /* For unsigned operands, try widening to an unsigned int.  */
2242   if (temp == 0 && unsignedp)
2243     temp = expand_binop (mode, uoptab, op0, op1, target,
2244                          unsignedp, OPTAB_WIDEN);
2245   if (temp || methods == OPTAB_WIDEN)
2246     return temp;
2247
2248   /* Use the right width lib call if that exists.  */
2249   temp = expand_binop (mode, direct_optab, op0, op1, target, unsignedp, OPTAB_LIB);
2250   if (temp || methods == OPTAB_LIB)
2251     return temp;
2252
2253   /* Must widen and use a lib call, use either signed or unsigned.  */
2254   temp = expand_binop (mode, &wide_soptab, op0, op1, target,
2255                        unsignedp, methods);
2256   if (temp != 0)
2257     return temp;
2258   if (unsignedp)
2259     return expand_binop (mode, uoptab, op0, op1, target,
2260                          unsignedp, methods);
2261   return 0;
2262 }
2263 \f
2264 /* Generate code to perform an operation specified by UNOPPTAB
2265    on operand OP0, with two results to TARG0 and TARG1.
2266    We assume that the order of the operands for the instruction
2267    is TARG0, TARG1, OP0.
2268
2269    Either TARG0 or TARG1 may be zero, but what that means is that
2270    the result is not actually wanted.  We will generate it into
2271    a dummy pseudo-reg and discard it.  They may not both be zero.
2272
2273    Returns 1 if this operation can be performed; 0 if not.  */
2274
2275 int
2276 expand_twoval_unop (optab unoptab, rtx op0, rtx targ0, rtx targ1,
2277                     int unsignedp)
2278 {
2279   enum machine_mode mode = GET_MODE (targ0 ? targ0 : targ1);
2280   enum mode_class class;
2281   enum machine_mode wider_mode;
2282   rtx entry_last = get_last_insn ();
2283   rtx last;
2284
2285   class = GET_MODE_CLASS (mode);
2286
2287   if (!targ0)
2288     targ0 = gen_reg_rtx (mode);
2289   if (!targ1)
2290     targ1 = gen_reg_rtx (mode);
2291
2292   /* Record where to go back to if we fail.  */
2293   last = get_last_insn ();
2294
2295   if (optab_handler (unoptab, mode)->insn_code != CODE_FOR_nothing)
2296     {
2297       int icode = (int) optab_handler (unoptab, mode)->insn_code;
2298       enum machine_mode mode0 = insn_data[icode].operand[2].mode;
2299       rtx pat;
2300       rtx xop0 = op0;
2301
2302       if (GET_MODE (xop0) != VOIDmode
2303           && GET_MODE (xop0) != mode0)
2304         xop0 = convert_to_mode (mode0, xop0, unsignedp);
2305
2306       /* Now, if insn doesn't accept these operands, put them into pseudos.  */
2307       if (!insn_data[icode].operand[2].predicate (xop0, mode0))
2308         xop0 = copy_to_mode_reg (mode0, xop0);
2309
2310       /* We could handle this, but we should always be called with a pseudo
2311          for our targets and all insns should take them as outputs.  */
2312       gcc_assert (insn_data[icode].operand[0].predicate (targ0, mode));
2313       gcc_assert (insn_data[icode].operand[1].predicate (targ1, mode));
2314
2315       pat = GEN_FCN (icode) (targ0, targ1, xop0);
2316       if (pat)
2317         {
2318           emit_insn (pat);
2319           return 1;
2320         }
2321       else
2322         delete_insns_since (last);
2323     }
2324
2325   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2326
2327   if (CLASS_HAS_WIDER_MODES_P (class))
2328     {
2329       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2330            wider_mode != VOIDmode;
2331            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2332         {
2333           if (optab_handler (unoptab, wider_mode)->insn_code
2334               != CODE_FOR_nothing)
2335             {
2336               rtx t0 = gen_reg_rtx (wider_mode);
2337               rtx t1 = gen_reg_rtx (wider_mode);
2338               rtx cop0 = convert_modes (wider_mode, mode, op0, unsignedp);
2339
2340               if (expand_twoval_unop (unoptab, cop0, t0, t1, unsignedp))
2341                 {
2342                   convert_move (targ0, t0, unsignedp);
2343                   convert_move (targ1, t1, unsignedp);
2344                   return 1;
2345                 }
2346               else
2347                 delete_insns_since (last);
2348             }
2349         }
2350     }
2351
2352   delete_insns_since (entry_last);
2353   return 0;
2354 }
2355 \f
2356 /* Generate code to perform an operation specified by BINOPTAB
2357    on operands OP0 and OP1, with two results to TARG1 and TARG2.
2358    We assume that the order of the operands for the instruction
2359    is TARG0, OP0, OP1, TARG1, which would fit a pattern like
2360    [(set TARG0 (operate OP0 OP1)) (set TARG1 (operate ...))].
2361
2362    Either TARG0 or TARG1 may be zero, but what that means is that
2363    the result is not actually wanted.  We will generate it into
2364    a dummy pseudo-reg and discard it.  They may not both be zero.
2365
2366    Returns 1 if this operation can be performed; 0 if not.  */
2367
2368 int
2369 expand_twoval_binop (optab binoptab, rtx op0, rtx op1, rtx targ0, rtx targ1,
2370                      int unsignedp)
2371 {
2372   enum machine_mode mode = GET_MODE (targ0 ? targ0 : targ1);
2373   enum mode_class class;
2374   enum machine_mode wider_mode;
2375   rtx entry_last = get_last_insn ();
2376   rtx last;
2377
2378   class = GET_MODE_CLASS (mode);
2379
2380   if (!targ0)
2381     targ0 = gen_reg_rtx (mode);
2382   if (!targ1)
2383     targ1 = gen_reg_rtx (mode);
2384
2385   /* Record where to go back to if we fail.  */
2386   last = get_last_insn ();
2387
2388   if (optab_handler (binoptab, mode)->insn_code != CODE_FOR_nothing)
2389     {
2390       int icode = (int) optab_handler (binoptab, mode)->insn_code;
2391       enum machine_mode mode0 = insn_data[icode].operand[1].mode;
2392       enum machine_mode mode1 = insn_data[icode].operand[2].mode;
2393       rtx pat;
2394       rtx xop0 = op0, xop1 = op1;
2395
2396       /* If we are optimizing, force expensive constants into a register.  */
2397       xop0 = avoid_expensive_constant (mode0, binoptab, xop0, unsignedp);
2398       xop1 = avoid_expensive_constant (mode1, binoptab, xop1, unsignedp);
2399
2400       /* In case the insn wants input operands in modes different from
2401          those of the actual operands, convert the operands.  It would
2402          seem that we don't need to convert CONST_INTs, but we do, so
2403          that they're properly zero-extended, sign-extended or truncated
2404          for their mode.  */
2405
2406       if (GET_MODE (op0) != mode0 && mode0 != VOIDmode)
2407         xop0 = convert_modes (mode0,
2408                               GET_MODE (op0) != VOIDmode
2409                               ? GET_MODE (op0)
2410                               : mode,
2411                               xop0, unsignedp);
2412
2413       if (GET_MODE (op1) != mode1 && mode1 != VOIDmode)
2414         xop1 = convert_modes (mode1,
2415                               GET_MODE (op1) != VOIDmode
2416                               ? GET_MODE (op1)
2417                               : mode,
2418                               xop1, unsignedp);
2419
2420       /* Now, if insn doesn't accept these operands, put them into pseudos.  */
2421       if (!insn_data[icode].operand[1].predicate (xop0, mode0))
2422         xop0 = copy_to_mode_reg (mode0, xop0);
2423
2424       if (!insn_data[icode].operand[2].predicate (xop1, mode1))
2425         xop1 = copy_to_mode_reg (mode1, xop1);
2426
2427       /* We could handle this, but we should always be called with a pseudo
2428          for our targets and all insns should take them as outputs.  */
2429       gcc_assert (insn_data[icode].operand[0].predicate (targ0, mode));
2430       gcc_assert (insn_data[icode].operand[3].predicate (targ1, mode));
2431
2432       pat = GEN_FCN (icode) (targ0, xop0, xop1, targ1);
2433       if (pat)
2434         {
2435           emit_insn (pat);
2436           return 1;
2437         }
2438       else
2439         delete_insns_since (last);
2440     }
2441
2442   /* It can't be done in this mode.  Can we do it in a wider mode?  */
2443
2444   if (CLASS_HAS_WIDER_MODES_P (class))
2445     {
2446       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2447            wider_mode != VOIDmode;
2448            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2449         {
2450           if (optab_handler (binoptab, wider_mode)->insn_code
2451               != CODE_FOR_nothing)
2452             {
2453               rtx t0 = gen_reg_rtx (wider_mode);
2454               rtx t1 = gen_reg_rtx (wider_mode);
2455               rtx cop0 = convert_modes (wider_mode, mode, op0, unsignedp);
2456               rtx cop1 = convert_modes (wider_mode, mode, op1, unsignedp);
2457
2458               if (expand_twoval_binop (binoptab, cop0, cop1,
2459                                        t0, t1, unsignedp))
2460                 {
2461                   convert_move (targ0, t0, unsignedp);
2462                   convert_move (targ1, t1, unsignedp);
2463                   return 1;
2464                 }
2465               else
2466                 delete_insns_since (last);
2467             }
2468         }
2469     }
2470
2471   delete_insns_since (entry_last);
2472   return 0;
2473 }
2474
2475 /* Expand the two-valued library call indicated by BINOPTAB, but
2476    preserve only one of the values.  If TARG0 is non-NULL, the first
2477    value is placed into TARG0; otherwise the second value is placed
2478    into TARG1.  Exactly one of TARG0 and TARG1 must be non-NULL.  The
2479    value stored into TARG0 or TARG1 is equivalent to (CODE OP0 OP1).
2480    This routine assumes that the value returned by the library call is
2481    as if the return value was of an integral mode twice as wide as the
2482    mode of OP0.  Returns 1 if the call was successful.  */
2483
2484 bool
2485 expand_twoval_binop_libfunc (optab binoptab, rtx op0, rtx op1,
2486                              rtx targ0, rtx targ1, enum rtx_code code)
2487 {
2488   enum machine_mode mode;
2489   enum machine_mode libval_mode;
2490   rtx libval;
2491   rtx insns;
2492   rtx libfunc;
2493
2494   /* Exactly one of TARG0 or TARG1 should be non-NULL.  */
2495   gcc_assert (!targ0 != !targ1);
2496
2497   mode = GET_MODE (op0);
2498   libfunc = optab_libfunc (binoptab, mode);
2499   if (!libfunc)
2500     return false;
2501
2502   /* The value returned by the library function will have twice as
2503      many bits as the nominal MODE.  */
2504   libval_mode = smallest_mode_for_size (2 * GET_MODE_BITSIZE (mode),
2505                                         MODE_INT);
2506   start_sequence ();
2507   libval = emit_library_call_value (libfunc, NULL_RTX, LCT_CONST,
2508                                     libval_mode, 2,
2509                                     op0, mode,
2510                                     op1, mode);
2511   /* Get the part of VAL containing the value that we want.  */
2512   libval = simplify_gen_subreg (mode, libval, libval_mode,
2513                                 targ0 ? 0 : GET_MODE_SIZE (mode));
2514   insns = get_insns ();
2515   end_sequence ();
2516   /* Move the into the desired location.  */
2517   emit_libcall_block (insns, targ0 ? targ0 : targ1, libval,
2518                       gen_rtx_fmt_ee (code, mode, op0, op1));
2519
2520   return true;
2521 }
2522
2523 \f
2524 /* Wrapper around expand_unop which takes an rtx code to specify
2525    the operation to perform, not an optab pointer.  All other
2526    arguments are the same.  */
2527 rtx
2528 expand_simple_unop (enum machine_mode mode, enum rtx_code code, rtx op0,
2529                     rtx target, int unsignedp)
2530 {
2531   optab unop = code_to_optab[(int) code];
2532   gcc_assert (unop);
2533
2534   return expand_unop (mode, unop, op0, target, unsignedp);
2535 }
2536
2537 /* Try calculating
2538         (clz:narrow x)
2539    as
2540         (clz:wide (zero_extend:wide x)) - ((width wide) - (width narrow)).  */
2541 static rtx
2542 widen_clz (enum machine_mode mode, rtx op0, rtx target)
2543 {
2544   enum mode_class class = GET_MODE_CLASS (mode);
2545   if (CLASS_HAS_WIDER_MODES_P (class))
2546     {
2547       enum machine_mode wider_mode;
2548       for (wider_mode = GET_MODE_WIDER_MODE (mode);
2549            wider_mode != VOIDmode;
2550            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2551         {
2552           if (optab_handler (clz_optab, wider_mode)->insn_code
2553               != CODE_FOR_nothing)
2554             {
2555               rtx xop0, temp, last;
2556
2557               last = get_last_insn ();
2558
2559               if (target == 0)
2560                 target = gen_reg_rtx (mode);
2561               xop0 = widen_operand (op0, wider_mode, mode, true, false);
2562               temp = expand_unop (wider_mode, clz_optab, xop0, NULL_RTX, true);
2563               if (temp != 0)
2564                 temp = expand_binop (wider_mode, sub_optab, temp,
2565                                      GEN_INT (GET_MODE_BITSIZE (wider_mode)
2566                                               - GET_MODE_BITSIZE (mode)),
2567                                      target, true, OPTAB_DIRECT);
2568               if (temp == 0)
2569                 delete_insns_since (last);
2570
2571               return temp;
2572             }
2573         }
2574     }
2575   return 0;
2576 }
2577
2578 /* Try calculating clz of a double-word quantity as two clz's of word-sized
2579    quantities, choosing which based on whether the high word is nonzero.  */
2580 static rtx
2581 expand_doubleword_clz (enum machine_mode mode, rtx op0, rtx target)
2582 {
2583   rtx xop0 = force_reg (mode, op0);
2584   rtx subhi = gen_highpart (word_mode, xop0);
2585   rtx sublo = gen_lowpart (word_mode, xop0);
2586   rtx hi0_label = gen_label_rtx ();
2587   rtx after_label = gen_label_rtx ();
2588   rtx seq, temp, result;
2589
2590   /* If we were not given a target, use a word_mode register, not a
2591      'mode' register.  The result will fit, and nobody is expecting
2592      anything bigger (the return type of __builtin_clz* is int).  */
2593   if (!target)
2594     target = gen_reg_rtx (word_mode);
2595
2596   /* In any case, write to a word_mode scratch in both branches of the
2597      conditional, so we can ensure there is a single move insn setting
2598      'target' to tag a REG_EQUAL note on.  */
2599   result = gen_reg_rtx (word_mode);
2600
2601   start_sequence ();
2602
2603   /* If the high word is not equal to zero,
2604      then clz of the full value is clz of the high word.  */
2605   emit_cmp_and_jump_insns (subhi, CONST0_RTX (word_mode), EQ, 0,
2606                            word_mode, true, hi0_label);
2607
2608   temp = expand_unop_direct (word_mode, clz_optab, subhi, result, true);
2609   if (!temp)
2610     goto fail;
2611
2612   if (temp != result)
2613     convert_move (result, temp, true);
2614
2615   emit_jump_insn (gen_jump (after_label));
2616   emit_barrier ();
2617
2618   /* Else clz of the full value is clz of the low word plus the number
2619      of bits in the high word.  */
2620   emit_label (hi0_label);
2621
2622   temp = expand_unop_direct (word_mode, clz_optab, sublo, 0, true);
2623   if (!temp)
2624     goto fail;
2625   temp = expand_binop (word_mode, add_optab, temp,
2626                        GEN_INT (GET_MODE_BITSIZE (word_mode)),
2627                        result, true, OPTAB_DIRECT);
2628   if (!temp)
2629     goto fail;
2630   if (temp != result)
2631     convert_move (result, temp, true);
2632
2633   emit_label (after_label);
2634   convert_move (target, result, true);
2635
2636   seq = get_insns ();
2637   end_sequence ();
2638
2639   add_equal_note (seq, target, CLZ, xop0, 0);
2640   emit_insn (seq);
2641   return target;
2642
2643  fail:
2644   end_sequence ();
2645   return 0;
2646 }
2647
2648 /* Try calculating
2649         (bswap:narrow x)
2650    as
2651         (lshiftrt:wide (bswap:wide x) ((width wide) - (width narrow))).  */
2652 static rtx
2653 widen_bswap (enum machine_mode mode, rtx op0, rtx target)
2654 {
2655   enum mode_class class = GET_MODE_CLASS (mode);
2656   enum machine_mode wider_mode;
2657   rtx x, last;
2658
2659   if (!CLASS_HAS_WIDER_MODES_P (class))
2660     return NULL_RTX;
2661
2662   for (wider_mode = GET_MODE_WIDER_MODE (mode);
2663        wider_mode != VOIDmode;
2664        wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2665     if (optab_handler (bswap_optab, wider_mode)->insn_code != CODE_FOR_nothing)
2666       goto found;
2667   return NULL_RTX;
2668
2669  found:
2670   last = get_last_insn ();
2671
2672   x = widen_operand (op0, wider_mode, mode, true, true);
2673   x = expand_unop (wider_mode, bswap_optab, x, NULL_RTX, true);
2674
2675   if (x != 0)
2676     x = expand_shift (RSHIFT_EXPR, wider_mode, x,
2677                       size_int (GET_MODE_BITSIZE (wider_mode)
2678                                 - GET_MODE_BITSIZE (mode)),
2679                       NULL_RTX, true);
2680
2681   if (x != 0)
2682     {
2683       if (target == 0)
2684         target = gen_reg_rtx (mode);
2685       emit_move_insn (target, gen_lowpart (mode, x));
2686     }
2687   else
2688     delete_insns_since (last);
2689
2690   return target;
2691 }
2692
2693 /* Try calculating bswap as two bswaps of two word-sized operands.  */
2694
2695 static rtx
2696 expand_doubleword_bswap (enum machine_mode mode, rtx op, rtx target)
2697 {
2698   rtx t0, t1;
2699
2700   t1 = expand_unop (word_mode, bswap_optab,
2701                     operand_subword_force (op, 0, mode), NULL_RTX, true);
2702   t0 = expand_unop (word_mode, bswap_optab,
2703                     operand_subword_force (op, 1, mode), NULL_RTX, true);
2704
2705   if (target == 0)
2706     target = gen_reg_rtx (mode);
2707   if (REG_P (target))
2708     emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
2709   emit_move_insn (operand_subword (target, 0, 1, mode), t0);
2710   emit_move_insn (operand_subword (target, 1, 1, mode), t1);
2711
2712   return target;
2713 }
2714
2715 /* Try calculating (parity x) as (and (popcount x) 1), where
2716    popcount can also be done in a wider mode.  */
2717 static rtx
2718 expand_parity (enum machine_mode mode, rtx op0, rtx target)
2719 {
2720   enum mode_class class = GET_MODE_CLASS (mode);
2721   if (CLASS_HAS_WIDER_MODES_P (class))
2722     {
2723       enum machine_mode wider_mode;
2724       for (wider_mode = mode; wider_mode != VOIDmode;
2725            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
2726         {
2727           if (optab_handler (popcount_optab, wider_mode)->insn_code
2728               != CODE_FOR_nothing)
2729             {
2730               rtx xop0, temp, last;
2731
2732               last = get_last_insn ();
2733
2734               if (target == 0)
2735                 target = gen_reg_rtx (mode);
2736               xop0 = widen_operand (op0, wider_mode, mode, true, false);
2737               temp = expand_unop (wider_mode, popcount_optab, xop0, NULL_RTX,
2738                                   true);
2739               if (temp != 0)
2740                 temp = expand_binop (wider_mode, and_optab, temp, const1_rtx,
2741                                      target, true, OPTAB_DIRECT);
2742               if (temp == 0)
2743                 delete_insns_since (last);
2744
2745               return temp;
2746             }
2747         }
2748     }
2749   return 0;
2750 }
2751
2752 /* Try calculating ctz(x) as K - clz(x & -x) ,
2753    where K is GET_MODE_BITSIZE(mode) - 1.
2754
2755    Both __builtin_ctz and __builtin_clz are undefined at zero, so we
2756    don't have to worry about what the hardware does in that case.  (If
2757    the clz instruction produces the usual value at 0, which is K, the
2758    result of this code sequence will be -1; expand_ffs, below, relies
2759    on this.  It might be nice to have it be K instead, for consistency
2760    with the (very few) processors that provide a ctz with a defined
2761    value, but that would take one more instruction, and it would be
2762    less convenient for expand_ffs anyway.  */
2763
2764 static rtx
2765 expand_ctz (enum machine_mode mode, rtx op0, rtx target)
2766 {
2767   rtx seq, temp;
2768   
2769   if (optab_handler (clz_optab, mode)->insn_code == CODE_FOR_nothing)
2770     return 0;
2771   
2772   start_sequence ();
2773
2774   temp = expand_unop_direct (mode, neg_optab, op0, NULL_RTX, true);
2775   if (temp)
2776     temp = expand_binop (mode, and_optab, op0, temp, NULL_RTX,
2777                          true, OPTAB_DIRECT);
2778   if (temp)
2779     temp = expand_unop_direct (mode, clz_optab, temp, NULL_RTX, true);
2780   if (temp)
2781     temp = expand_binop (mode, sub_optab, GEN_INT (GET_MODE_BITSIZE (mode) - 1),
2782                          temp, target,
2783                          true, OPTAB_DIRECT);
2784   if (temp == 0)
2785     {
2786       end_sequence ();
2787       return 0;
2788     }
2789
2790   seq = get_insns ();
2791   end_sequence ();
2792
2793   add_equal_note (seq, temp, CTZ, op0, 0);
2794   emit_insn (seq);
2795   return temp;
2796 }
2797
2798
2799 /* Try calculating ffs(x) using ctz(x) if we have that instruction, or
2800    else with the sequence used by expand_clz.
2801    
2802    The ffs builtin promises to return zero for a zero value and ctz/clz
2803    may have an undefined value in that case.  If they do not give us a
2804    convenient value, we have to generate a test and branch.  */
2805 static rtx
2806 expand_ffs (enum machine_mode mode, rtx op0, rtx target)
2807 {
2808   HOST_WIDE_INT val = 0;
2809   bool defined_at_zero = false;
2810   rtx temp, seq;
2811
2812   if (optab_handler (ctz_optab, mode)->insn_code != CODE_FOR_nothing)
2813     {
2814       start_sequence ();
2815
2816       temp = expand_unop_direct (mode, ctz_optab, op0, 0, true);
2817       if (!temp)
2818         goto fail;
2819
2820       defined_at_zero = (CTZ_DEFINED_VALUE_AT_ZERO (mode, val) == 2);
2821     }
2822   else if (optab_handler (clz_optab, mode)->insn_code != CODE_FOR_nothing)
2823     {
2824       start_sequence ();
2825       temp = expand_ctz (mode, op0, 0);
2826       if (!temp)
2827         goto fail;
2828
2829       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, val) == 2)
2830         {
2831           defined_at_zero = true;
2832           val = (GET_MODE_BITSIZE (mode) - 1) - val;
2833         }
2834     }
2835   else
2836     return 0;
2837
2838   if (defined_at_zero && val == -1)
2839     /* No correction needed at zero.  */;
2840   else 
2841     {
2842       /* We don't try to do anything clever with the situation found
2843          on some processors (eg Alpha) where ctz(0:mode) ==
2844          bitsize(mode).  If someone can think of a way to send N to -1
2845          and leave alone all values in the range 0..N-1 (where N is a
2846          power of two), cheaper than this test-and-branch, please add it.
2847
2848          The test-and-branch is done after the operation itself, in case
2849          the operation sets condition codes that can be recycled for this.
2850          (This is true on i386, for instance.)  */
2851
2852       rtx nonzero_label = gen_label_rtx ();
2853       emit_cmp_and_jump_insns (op0, CONST0_RTX (mode), NE, 0,
2854                                mode, true, nonzero_label);
2855
2856       convert_move (temp, GEN_INT (-1), false);
2857       emit_label (nonzero_label);
2858     }
2859
2860   /* temp now has a value in the range -1..bitsize-1.  ffs is supposed
2861      to produce a value in the range 0..bitsize.  */
2862   temp = expand_binop (mode, add_optab, temp, GEN_INT (1),
2863                        target, false, OPTAB_DIRECT);
2864   if (!temp)
2865     goto fail;
2866
2867   seq = get_insns ();
2868   end_sequence ();
2869
2870   add_equal_note (seq, temp, FFS, op0, 0);
2871   emit_insn (seq);
2872   return temp;
2873
2874  fail:
2875   end_sequence ();
2876   return 0;
2877 }
2878
2879 /* Extract the OMODE lowpart from VAL, which has IMODE.  Under certain
2880    conditions, VAL may already be a SUBREG against which we cannot generate
2881    a further SUBREG.  In this case, we expect forcing the value into a
2882    register will work around the situation.  */
2883
2884 static rtx
2885 lowpart_subreg_maybe_copy (enum machine_mode omode, rtx val,
2886                            enum machine_mode imode)
2887 {
2888   rtx ret;
2889   ret = lowpart_subreg (omode, val, imode);
2890   if (ret == NULL)
2891     {
2892       val = force_reg (imode, val);
2893       ret = lowpart_subreg (omode, val, imode);
2894       gcc_assert (ret != NULL);
2895     }
2896   return ret;
2897 }
2898
2899 /* Expand a floating point absolute value or negation operation via a
2900    logical operation on the sign bit.  */
2901
2902 static rtx
2903 expand_absneg_bit (enum rtx_code code, enum machine_mode mode,
2904                    rtx op0, rtx target)
2905 {
2906   const struct real_format *fmt;
2907   int bitpos, word, nwords, i;
2908   enum machine_mode imode;
2909   HOST_WIDE_INT hi, lo;
2910   rtx temp, insns;
2911
2912   /* The format has to have a simple sign bit.  */
2913   fmt = REAL_MODE_FORMAT (mode);
2914   if (fmt == NULL)
2915     return NULL_RTX;
2916
2917   bitpos = fmt->signbit_rw;
2918   if (bitpos < 0)
2919     return NULL_RTX;
2920
2921   /* Don't create negative zeros if the format doesn't support them.  */
2922   if (code == NEG && !fmt->has_signed_zero)
2923     return NULL_RTX;
2924
2925   if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
2926     {
2927       imode = int_mode_for_mode (mode);
2928       if (imode == BLKmode)
2929         return NULL_RTX;
2930       word = 0;
2931       nwords = 1;
2932     }
2933   else
2934     {
2935       imode = word_mode;
2936
2937       if (FLOAT_WORDS_BIG_ENDIAN)
2938         word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
2939       else
2940         word = bitpos / BITS_PER_WORD;
2941       bitpos = bitpos % BITS_PER_WORD;
2942       nwords = (GET_MODE_BITSIZE (mode) + BITS_PER_WORD - 1) / BITS_PER_WORD;
2943     }
2944
2945   if (bitpos < HOST_BITS_PER_WIDE_INT)
2946     {
2947       hi = 0;
2948       lo = (HOST_WIDE_INT) 1 << bitpos;
2949     }
2950   else
2951     {
2952       hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
2953       lo = 0;
2954     }
2955   if (code == ABS)
2956     lo = ~lo, hi = ~hi;
2957
2958   if (target == 0 || target == op0)
2959     target = gen_reg_rtx (mode);
2960
2961   if (nwords > 1)
2962     {
2963       start_sequence ();
2964
2965       for (i = 0; i < nwords; ++i)
2966         {
2967           rtx targ_piece = operand_subword (target, i, 1, mode);
2968           rtx op0_piece = operand_subword_force (op0, i, mode);
2969
2970           if (i == word)
2971             {
2972               temp = expand_binop (imode, code == ABS ? and_optab : xor_optab,
2973                                    op0_piece,
2974                                    immed_double_const (lo, hi, imode),
2975                                    targ_piece, 1, OPTAB_LIB_WIDEN);
2976               if (temp != targ_piece)
2977                 emit_move_insn (targ_piece, temp);
2978             }
2979           else
2980             emit_move_insn (targ_piece, op0_piece);
2981         }
2982
2983       insns = get_insns ();
2984       end_sequence ();
2985
2986       temp = gen_rtx_fmt_e (code, mode, copy_rtx (op0));
2987       emit_no_conflict_block (insns, target, op0, NULL_RTX, temp);
2988     }
2989   else
2990     {
2991       temp = expand_binop (imode, code == ABS ? and_optab : xor_optab,
2992                            gen_lowpart (imode, op0),
2993                            immed_double_const (lo, hi, imode),
2994                            gen_lowpart (imode, target), 1, OPTAB_LIB_WIDEN);
2995       target = lowpart_subreg_maybe_copy (mode, temp, imode);
2996
2997       set_unique_reg_note (get_last_insn (), REG_EQUAL,
2998                            gen_rtx_fmt_e (code, mode, copy_rtx (op0)));
2999     }
3000
3001   return target;
3002 }
3003
3004 /* As expand_unop, but will fail rather than attempt the operation in a
3005    different mode or with a libcall.  */
3006 static rtx
3007 expand_unop_direct (enum machine_mode mode, optab unoptab, rtx op0, rtx target,
3008              int unsignedp)
3009 {
3010   if (optab_handler (unoptab, mode)->insn_code != CODE_FOR_nothing)
3011     {
3012       int icode = (int) optab_handler (unoptab, mode)->insn_code;
3013       enum machine_mode mode0 = insn_data[icode].operand[1].mode;
3014       rtx xop0 = op0;
3015       rtx last = get_last_insn ();
3016       rtx pat, temp;
3017
3018       if (target)
3019         temp = target;
3020       else
3021         temp = gen_reg_rtx (mode);
3022
3023       if (GET_MODE (xop0) != VOIDmode
3024           && GET_MODE (xop0) != mode0)
3025         xop0 = convert_to_mode (mode0, xop0, unsignedp);
3026
3027       /* Now, if insn doesn't accept our operand, put it into a pseudo.  */
3028
3029       if (!insn_data[icode].operand[1].predicate (xop0, mode0))
3030         xop0 = copy_to_mode_reg (mode0, xop0);
3031
3032       if (!insn_data[icode].operand[0].predicate (temp, mode))
3033         temp = gen_reg_rtx (mode);
3034
3035       pat = GEN_FCN (icode) (temp, xop0);
3036       if (pat)
3037         {
3038           if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX
3039               && ! add_equal_note (pat, temp, unoptab->code, xop0, NULL_RTX))
3040             {
3041               delete_insns_since (last);
3042               return expand_unop (mode, unoptab, op0, NULL_RTX, unsignedp);
3043             }
3044
3045           emit_insn (pat);
3046
3047           return temp;
3048         }
3049       else
3050         delete_insns_since (last);
3051     }
3052   return 0;
3053 }
3054
3055 /* Generate code to perform an operation specified by UNOPTAB
3056    on operand OP0, with result having machine-mode MODE.
3057
3058    UNSIGNEDP is for the case where we have to widen the operands
3059    to perform the operation.  It says to use zero-extension.
3060
3061    If TARGET is nonzero, the value
3062    is generated there, if it is convenient to do so.
3063    In all cases an rtx is returned for the locus of the value;
3064    this may or may not be TARGET.  */
3065
3066 rtx
3067 expand_unop (enum machine_mode mode, optab unoptab, rtx op0, rtx target,
3068              int unsignedp)
3069 {
3070   enum mode_class class = GET_MODE_CLASS (mode);
3071   enum machine_mode wider_mode;
3072   rtx temp;
3073   rtx libfunc;
3074
3075   temp = expand_unop_direct (mode, unoptab, op0, target, unsignedp);
3076   if (temp)
3077     return temp;
3078
3079   /* It can't be done in this mode.  Can we open-code it in a wider mode?  */
3080
3081   /* Widening (or narrowing) clz needs special treatment.  */
3082   if (unoptab == clz_optab)
3083     {
3084       temp = widen_clz (mode, op0, target);
3085       if (temp)
3086         return temp;
3087
3088       if (GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
3089           && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3090         {
3091           temp = expand_doubleword_clz (mode, op0, target);
3092           if (temp)
3093             return temp;
3094         }
3095
3096         goto try_libcall;
3097     }
3098
3099   /* Widening (or narrowing) bswap needs special treatment.  */
3100   if (unoptab == bswap_optab)
3101     {
3102       temp = widen_bswap (mode, op0, target);
3103       if (temp)
3104         return temp;
3105
3106       if (GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
3107           && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3108         {
3109           temp = expand_doubleword_bswap (mode, op0, target);
3110           if (temp)
3111             return temp;
3112         }
3113
3114       goto try_libcall;
3115     }
3116
3117   if (CLASS_HAS_WIDER_MODES_P (class))
3118     for (wider_mode = GET_MODE_WIDER_MODE (mode);
3119          wider_mode != VOIDmode;
3120          wider_mode = GET_MODE_WIDER_MODE (wider_mode))
3121       {
3122         if (optab_handler (unoptab, wider_mode)->insn_code != CODE_FOR_nothing)
3123           {
3124             rtx xop0 = op0;
3125             rtx last = get_last_insn ();
3126
3127             /* For certain operations, we need not actually extend
3128                the narrow operand, as long as we will truncate the
3129                results to the same narrowness.  */
3130
3131             xop0 = widen_operand (xop0, wider_mode, mode, unsignedp,
3132                                   (unoptab == neg_optab
3133                                    || unoptab == one_cmpl_optab)
3134                                   && class == MODE_INT);
3135
3136             temp = expand_unop (wider_mode, unoptab, xop0, NULL_RTX,
3137                                 unsignedp);
3138
3139             if (temp)
3140               {
3141                 if (class != MODE_INT
3142                     || !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
3143                                                GET_MODE_BITSIZE (wider_mode)))
3144                   {
3145                     if (target == 0)
3146                       target = gen_reg_rtx (mode);
3147                     convert_move (target, temp, 0);
3148                     return target;
3149                   }
3150                 else
3151                   return gen_lowpart (mode, temp);
3152               }
3153             else
3154               delete_insns_since (last);
3155           }
3156       }
3157
3158   /* These can be done a word at a time.  */
3159   if (unoptab == one_cmpl_optab
3160       && class == MODE_INT
3161       && GET_MODE_SIZE (mode) > UNITS_PER_WORD
3162       && optab_handler (unoptab, word_mode)->insn_code != CODE_FOR_nothing)
3163     {
3164       int i;
3165       rtx insns;
3166
3167       if (target == 0 || target == op0)
3168         target = gen_reg_rtx (mode);
3169
3170       start_sequence ();
3171
3172       /* Do the actual arithmetic.  */
3173       for (i = 0; i < GET_MODE_BITSIZE (mode) / BITS_PER_WORD; i++)
3174         {
3175           rtx target_piece = operand_subword (target, i, 1, mode);
3176           rtx x = expand_unop (word_mode, unoptab,
3177                                operand_subword_force (op0, i, mode),
3178                                target_piece, unsignedp);
3179
3180           if (target_piece != x)
3181             emit_move_insn (target_piece, x);
3182         }
3183
3184       insns = get_insns ();
3185       end_sequence ();
3186
3187       emit_no_conflict_block (insns, target, op0, NULL_RTX,
3188                               gen_rtx_fmt_e (unoptab->code, mode,
3189                                              copy_rtx (op0)));
3190       return target;
3191     }
3192
3193   if (unoptab->code == NEG)
3194     {
3195       /* Try negating floating point values by flipping the sign bit.  */
3196       if (SCALAR_FLOAT_MODE_P (mode))
3197         {
3198           temp = expand_absneg_bit (NEG, mode, op0, target);
3199           if (temp)
3200             return temp;
3201         }
3202
3203       /* If there is no negation pattern, and we have no negative zero,
3204          try subtracting from zero.  */
3205       if (!HONOR_SIGNED_ZEROS (mode))
3206         {
3207           temp = expand_binop (mode, (unoptab == negv_optab
3208                                       ? subv_optab : sub_optab),
3209                                CONST0_RTX (mode), op0, target,
3210                                unsignedp, OPTAB_DIRECT);
3211           if (temp)
3212             return temp;
3213         }
3214     }
3215
3216   /* Try calculating parity (x) as popcount (x) % 2.  */
3217   if (unoptab == parity_optab)
3218     {
3219       temp = expand_parity (mode, op0, target);
3220       if (temp)
3221         return temp;
3222     }
3223
3224   /* Try implementing ffs (x) in terms of clz (x).  */
3225   if (unoptab == ffs_optab)
3226     {
3227       temp = expand_ffs (mode, op0, target);
3228       if (temp)
3229         return temp;
3230     }
3231
3232   /* Try implementing ctz (x) in terms of clz (x).  */
3233   if (unoptab == ctz_optab)
3234     {
3235       temp = expand_ctz (mode, op0, target);
3236       if (temp)
3237         return temp;
3238     }
3239
3240  try_libcall:
3241   /* Now try a library call in this mode.  */
3242   libfunc = optab_libfunc (unoptab, mode);
3243   if (libfunc)
3244     {
3245       rtx insns;
3246       rtx value;
3247       enum machine_mode outmode = mode;
3248
3249       /* All of these functions return small values.  Thus we choose to
3250          have them return something that isn't a double-word.  */
3251       if (unoptab == ffs_optab || unoptab == clz_optab || unoptab == ctz_optab
3252           || unoptab == popcount_optab || unoptab == parity_optab)
3253         outmode
3254             = GET_MODE (hard_libcall_value (TYPE_MODE (integer_type_node)));
3255
3256       start_sequence ();
3257
3258       /* Pass 1 for NO_QUEUE so we don't lose any increments
3259          if the libcall is cse'd or moved.  */
3260       value = emit_library_call_value (libfunc, NULL_RTX, LCT_CONST, outmode,
3261                                        1, op0, mode);
3262       insns = get_insns ();
3263       end_sequence ();
3264
3265       target = gen_reg_rtx (outmode);
3266       emit_libcall_block (insns, target, value,
3267                           gen_rtx_fmt_e (unoptab->code, outmode, op0));
3268
3269       return target;
3270     }
3271
3272   /* It can't be done in this mode.  Can we do it in a wider mode?  */
3273
3274   if (CLASS_HAS_WIDER_MODES_P (class))
3275     {
3276       for (wider_mode = GET_MODE_WIDER_MODE (mode);
3277            wider_mode != VOIDmode;
3278            wider_mode = GET_MODE_WIDER_MODE (wider_mode))
3279         {
3280           if ((optab_handler (unoptab, wider_mode)->insn_code
3281                != CODE_FOR_nothing)
3282               || optab_libfunc (unoptab, wider_mode))
3283             {
3284               rtx xop0 = op0;
3285               rtx last = get_last_insn ();
3286
3287               /* For certain operations, we need not actually extend
3288                  the narrow operand, as long as we will truncate the
3289                  results to the same narrowness.  */
3290
3291               xop0 = widen_operand (xop0, wider_mode, mode, unsignedp,
3292                                     (unoptab == neg_optab
3293                                      || unoptab == one_cmpl_optab)
3294                                     && class == MODE_INT);
3295
3296               temp = expand_unop (wider_mode, unoptab, xop0, NULL_RTX,
3297                                   unsignedp);
3298
3299               /* If we are generating clz using wider mode, adjust the
3300                  result.  */
3301               if (unoptab == clz_optab && temp != 0)
3302                 temp = expand_binop (wider_mode, sub_optab, temp,
3303                                      GEN_INT (GET_MODE_BITSIZE (wider_mode)
3304                                               - GET_MODE_BITSIZE (mode)),
3305                                      target, true, OPTAB_DIRECT);
3306
3307               if (temp)
3308                 {
3309                   if (class != MODE_INT)
3310                     {
3311                       if (target == 0)
3312                         target = gen_reg_rtx (mode);
3313                       convert_move (target, temp, 0);
3314                       return target;
3315                     }
3316                   else
3317                     return gen_lowpart (mode, temp);
3318                 }
3319               else
3320                 delete_insns_since (last);
3321             }
3322         }
3323     }
3324
3325   /* One final attempt at implementing negation via subtraction,
3326      this time allowing widening of the operand.  */
3327   if (unoptab->code == NEG && !HONOR_SIGNED_ZEROS (mode))
3328     {
3329       rtx temp;
3330       temp = expand_binop (mode,
3331                            unoptab == negv_optab ? subv_optab : sub_optab,
3332                            CONST0_RTX (mode), op0,
3333                            target, unsignedp, OPTAB_LIB_WIDEN);
3334       if (temp)
3335         return temp;
3336     }
3337
3338   return 0;
3339 }
3340 \f
3341 /* Emit code to compute the absolute value of OP0, with result to
3342    TARGET if convenient.  (TARGET may be 0.)  The return value says
3343    where the result actually is to be found.
3344
3345    MODE is the mode of the operand; the mode of the result is
3346    different but can be deduced from MODE.
3347
3348  */
3349
3350 rtx
3351 expand_abs_nojump (enum machine_mode mode, rtx op0, rtx target,
3352                    int result_unsignedp)
3353 {
3354   rtx temp;
3355
3356   if (! flag_trapv)
3357     result_unsignedp = 1;
3358
3359   /* First try to do it with a special abs instruction.  */
3360   temp = expand_unop (mode, result_unsignedp ? abs_optab : absv_optab,
3361                       op0, target, 0);
3362   if (temp != 0)
3363     return temp;
3364
3365   /* For floating point modes, try clearing the sign bit.  */
3366   if (SCALAR_FLOAT_MODE_P (mode))
3367     {
3368       temp = expand_absneg_bit (ABS, mode, op0, target);
3369       if (temp)
3370         return temp;
3371     }
3372
3373   /* If we have a MAX insn, we can do this as MAX (x, -x).  */
3374   if (optab_handler (smax_optab, mode)->insn_code != CODE_FOR_nothing
3375       && !HONOR_SIGNED_ZEROS (mode))
3376     {
3377       rtx last = get_last_insn ();
3378
3379       temp = expand_unop (mode, neg_optab, op0, NULL_RTX, 0);
3380       if (temp != 0)
3381         temp = expand_binop (mode, smax_optab, op0, temp, target, 0,
3382                              OPTAB_WIDEN);
3383
3384       if (temp != 0)
3385         return temp;
3386
3387       delete_insns_since (last);
3388     }
3389
3390   /* If this machine has expensive jumps, we can do integer absolute
3391      value of X as (((signed) x >> (W-1)) ^ x) - ((signed) x >> (W-1)),
3392      where W is the width of MODE.  */
3393
3394   if (GET_MODE_CLASS (mode) == MODE_INT && BRANCH_COST >= 2)
3395     {
3396       rtx extended = expand_shift (RSHIFT_EXPR, mode, op0,
3397                                    size_int (GET_MODE_BITSIZE (mode) - 1),
3398                                    NULL_RTX, 0);
3399
3400       temp = expand_binop (mode, xor_optab, extended, op0, target, 0,
3401                            OPTAB_LIB_WIDEN);
3402       if (temp != 0)
3403         temp = expand_binop (mode, result_unsignedp ? sub_optab : subv_optab,
3404                              temp, extended, target, 0, OPTAB_LIB_WIDEN);
3405
3406       if (temp != 0)
3407         return temp;
3408     }
3409
3410   return NULL_RTX;
3411 }
3412
3413 rtx
3414 expand_abs (enum machine_mode mode, rtx op0, rtx target,
3415             int result_unsignedp, int safe)
3416 {
3417   rtx temp, op1;
3418
3419   if (! flag_trapv)
3420     result_unsignedp = 1;
3421
3422   temp = expand_abs_nojump (mode, op0, target, result_unsignedp);
3423   if (temp != 0)
3424     return temp;
3425
3426   /* If that does not win, use conditional jump and negate.  */
3427
3428   /* It is safe to use the target if it is the same
3429      as the source if this is also a pseudo register */
3430   if (op0 == target && REG_P (op0)
3431       && REGNO (op0) >= FIRST_PSEUDO_REGISTER)
3432     safe = 1;
3433
3434   op1 = gen_label_rtx ();
3435   if (target == 0 || ! safe
3436       || GET_MODE (target) != mode
3437       || (MEM_P (target) && MEM_VOLATILE_P (target))
3438       || (REG_P (target)
3439           && REGNO (target) < FIRST_PSEUDO_REGISTER))
3440     target = gen_reg_rtx (mode);
3441
3442   emit_move_insn (target, op0);
3443   NO_DEFER_POP;
3444
3445   do_compare_rtx_and_jump (target, CONST0_RTX (mode), GE, 0, mode,
3446                            NULL_RTX, NULL_RTX, op1);
3447
3448   op0 = expand_unop (mode, result_unsignedp ? neg_optab : negv_optab,
3449                      target, target, 0);
3450   if (op0 != target)
3451     emit_move_insn (target, op0);
3452   emit_label (op1);
3453   OK_DEFER_POP;
3454   return target;
3455 }
3456
3457 /* A subroutine of expand_copysign, perform the copysign operation using the
3458    abs and neg primitives advertised to exist on the target.  The assumption
3459    is that we have a split register file, and leaving op0 in fp registers,
3460    and not playing with subregs so much, will help the register allocator.  */
3461
3462 static rtx
3463 expand_copysign_absneg (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3464                         int bitpos, bool op0_is_abs)
3465 {
3466   enum machine_mode imode;
3467   int icode;
3468   rtx sign, label;
3469
3470   if (target == op1)
3471     target = NULL_RTX;
3472
3473   /* Check if the back end provides an insn that handles signbit for the
3474      argument's mode. */
3475   icode = (int) signbit_optab->handlers [(int) mode].insn_code;
3476   if (icode != CODE_FOR_nothing)
3477     {
3478       imode = insn_data[icode].operand[0].mode;
3479       sign = gen_reg_rtx (imode);
3480       emit_unop_insn (icode, sign, op1, UNKNOWN);
3481     }
3482   else
3483     {
3484       HOST_WIDE_INT hi, lo;
3485
3486       if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
3487         {
3488           imode = int_mode_for_mode (mode);
3489           if (imode == BLKmode)
3490             return NULL_RTX;
3491           op1 = gen_lowpart (imode, op1);
3492         }
3493       else
3494         {
3495           int word;
3496
3497           imode = word_mode;
3498           if (FLOAT_WORDS_BIG_ENDIAN)
3499             word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
3500           else
3501             word = bitpos / BITS_PER_WORD;
3502           bitpos = bitpos % BITS_PER_WORD;
3503           op1 = operand_subword_force (op1, word, mode);
3504         }
3505
3506       if (bitpos < HOST_BITS_PER_WIDE_INT)
3507         {
3508           hi = 0;
3509           lo = (HOST_WIDE_INT) 1 << bitpos;
3510         }
3511       else
3512         {
3513           hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
3514           lo = 0;
3515         }
3516
3517       sign = gen_reg_rtx (imode);
3518       sign = expand_binop (imode, and_optab, op1,
3519                            immed_double_const (lo, hi, imode),
3520                            NULL_RTX, 1, OPTAB_LIB_WIDEN);
3521     }
3522
3523   if (!op0_is_abs)
3524     {
3525       op0 = expand_unop (mode, abs_optab, op0, target, 0);
3526       if (op0 == NULL)
3527         return NULL_RTX;
3528       target = op0;
3529     }
3530   else
3531     {
3532       if (target == NULL_RTX)
3533         target = copy_to_reg (op0);
3534       else
3535         emit_move_insn (target, op0);
3536     }
3537
3538   label = gen_label_rtx ();
3539   emit_cmp_and_jump_insns (sign, const0_rtx, EQ, NULL_RTX, imode, 1, label);
3540
3541   if (GET_CODE (op0) == CONST_DOUBLE)
3542     op0 = simplify_unary_operation (NEG, mode, op0, mode);
3543   else
3544     op0 = expand_unop (mode, neg_optab, op0, target, 0);
3545   if (op0 != target)
3546     emit_move_insn (target, op0);
3547
3548   emit_label (label);
3549
3550   return target;
3551 }
3552
3553
3554 /* A subroutine of expand_copysign, perform the entire copysign operation
3555    with integer bitmasks.  BITPOS is the position of the sign bit; OP0_IS_ABS
3556    is true if op0 is known to have its sign bit clear.  */
3557
3558 static rtx
3559 expand_copysign_bit (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3560                      int bitpos, bool op0_is_abs)
3561 {
3562   enum machine_mode imode;
3563   HOST_WIDE_INT hi, lo;
3564   int word, nwords, i;
3565   rtx temp, insns;
3566
3567   if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD)
3568     {
3569       imode = int_mode_for_mode (mode);
3570       if (imode == BLKmode)
3571         return NULL_RTX;
3572       word = 0;
3573       nwords = 1;
3574     }
3575   else
3576     {
3577       imode = word_mode;
3578
3579       if (FLOAT_WORDS_BIG_ENDIAN)
3580         word = (GET_MODE_BITSIZE (mode) - bitpos) / BITS_PER_WORD;
3581       else
3582         word = bitpos / BITS_PER_WORD;
3583       bitpos = bitpos % BITS_PER_WORD;
3584       nwords = (GET_MODE_BITSIZE (mode) + BITS_PER_WORD - 1) / BITS_PER_WORD;
3585     }
3586
3587   if (bitpos < HOST_BITS_PER_WIDE_INT)
3588     {
3589       hi = 0;
3590       lo = (HOST_WIDE_INT) 1 << bitpos;
3591     }
3592   else
3593     {
3594       hi = (HOST_WIDE_INT) 1 << (bitpos - HOST_BITS_PER_WIDE_INT);
3595       lo = 0;
3596     }
3597
3598   if (target == 0 || target == op0 || target == op1)
3599     target = gen_reg_rtx (mode);
3600
3601   if (nwords > 1)
3602     {
3603       start_sequence ();
3604
3605       for (i = 0; i < nwords; ++i)
3606         {
3607           rtx targ_piece = operand_subword (target, i, 1, mode);
3608           rtx op0_piece = operand_subword_force (op0, i, mode);
3609
3610           if (i == word)
3611             {
3612               if (!op0_is_abs)
3613                 op0_piece = expand_binop (imode, and_optab, op0_piece,
3614                                           immed_double_const (~lo, ~hi, imode),
3615                                           NULL_RTX, 1, OPTAB_LIB_WIDEN);
3616
3617               op1 = expand_binop (imode, and_optab,
3618                                   operand_subword_force (op1, i, mode),
3619                                   immed_double_const (lo, hi, imode),
3620                                   NULL_RTX, 1, OPTAB_LIB_WIDEN);
3621
3622               temp = expand_binop (imode, ior_optab, op0_piece, op1,
3623                                    targ_piece, 1, OPTAB_LIB_WIDEN);
3624               if (temp != targ_piece)
3625                 emit_move_insn (targ_piece, temp);
3626             }
3627           else
3628             emit_move_insn (targ_piece, op0_piece);
3629         }
3630
3631       insns = get_insns ();
3632       end_sequence ();
3633
3634       emit_no_conflict_block (insns, target, op0, op1, NULL_RTX);
3635     }
3636   else
3637     {
3638       op1 = expand_binop (imode, and_optab, gen_lowpart (imode, op1),
3639                           immed_double_const (lo, hi, imode),
3640                           NULL_RTX, 1, OPTAB_LIB_WIDEN);
3641
3642       op0 = gen_lowpart (imode, op0);
3643       if (!op0_is_abs)
3644         op0 = expand_binop (imode, and_optab, op0,
3645                             immed_double_const (~lo, ~hi, imode),
3646                             NULL_RTX, 1, OPTAB_LIB_WIDEN);
3647
3648       temp = expand_binop (imode, ior_optab, op0, op1,
3649                            gen_lowpart (imode, target), 1, OPTAB_LIB_WIDEN);
3650       target = lowpart_subreg_maybe_copy (mode, temp, imode);
3651     }
3652
3653   return target;
3654 }
3655
3656 /* Expand the C99 copysign operation.  OP0 and OP1 must be the same
3657    scalar floating point mode.  Return NULL if we do not know how to
3658    expand the operation inline.  */
3659
3660 rtx
3661 expand_copysign (rtx op0, rtx op1, rtx target)
3662 {
3663   enum machine_mode mode = GET_MODE (op0);
3664   const struct real_format *fmt;
3665   bool op0_is_abs;
3666   rtx temp;
3667
3668   gcc_assert (SCALAR_FLOAT_MODE_P (mode));
3669   gcc_assert (GET_MODE (op1) == mode);
3670
3671   /* First try to do it with a special instruction.  */
3672   temp = expand_binop (mode, copysign_optab, op0, op1,
3673                        target, 0, OPTAB_DIRECT);
3674   if (temp)
3675     return temp;
3676
3677   fmt = REAL_MODE_FORMAT (mode);
3678   if (fmt == NULL || !fmt->has_signed_zero)
3679     return NULL_RTX;
3680
3681   op0_is_abs = false;
3682   if (GET_CODE (op0) == CONST_DOUBLE)
3683     {
3684       if (real_isneg (CONST_DOUBLE_REAL_VALUE (op0)))
3685         op0 = simplify_unary_operation (ABS, mode, op0, mode);
3686       op0_is_abs = true;
3687     }
3688
3689   if (fmt->signbit_ro >= 0
3690       && (GET_CODE (op0) == CONST_DOUBLE
3691           || (optab_handler (neg_optab, mode)->insn_code != CODE_FOR_nothing
3692               && optab_handler (abs_optab, mode)->insn_code != CODE_FOR_nothing)))
3693     {
3694       temp = expand_copysign_absneg (mode, op0, op1, target,
3695                                      fmt->signbit_ro, op0_is_abs);
3696       if (temp)
3697         return temp;
3698     }
3699
3700   if (fmt->signbit_rw < 0)
3701     return NULL_RTX;
3702   return expand_copysign_bit (mode, op0, op1, target,
3703                               fmt->signbit_rw, op0_is_abs);
3704 }
3705 \f
3706 /* Generate an instruction whose insn-code is INSN_CODE,
3707    with two operands: an output TARGET and an input OP0.
3708    TARGET *must* be nonzero, and the output is always stored there.
3709    CODE is an rtx code such that (CODE OP0) is an rtx that describes
3710    the value that is stored into TARGET.  */
3711
3712 void
3713 emit_unop_insn (int icode, rtx target, rtx op0, enum rtx_code code)
3714 {
3715   rtx temp;
3716   enum machine_mode mode0 = insn_data[icode].operand[1].mode;
3717   rtx pat;
3718
3719   temp = target;
3720
3721   /* Now, if insn does not accept our operands, put them into pseudos.  */
3722
3723   if (!insn_data[icode].operand[1].predicate (op0, mode0))
3724     op0 = copy_to_mode_reg (mode0, op0);
3725
3726   if (!insn_data[icode].operand[0].predicate (temp, GET_MODE (temp)))
3727     temp = gen_reg_rtx (GET_MODE (temp));
3728
3729   pat = GEN_FCN (icode) (temp, op0);
3730
3731   if (INSN_P (pat) && NEXT_INSN (pat) != NULL_RTX && code != UNKNOWN)
3732     add_equal_note (pat, temp, code, op0, NULL_RTX);
3733
3734   emit_insn (pat);
3735
3736   if (temp != target)
3737     emit_move_insn (target, temp);
3738 }
3739 \f
3740 struct no_conflict_data
3741 {
3742   rtx target, first, insn;
3743   bool must_stay;
3744 };
3745
3746 /* Called via note_stores by emit_no_conflict_block and emit_libcall_block.
3747    Set P->must_stay if the currently examined clobber / store has to stay
3748    in the list of insns that constitute the actual no_conflict block /
3749    libcall block.  */
3750 static void
3751 no_conflict_move_test (rtx dest, const_rtx set, void *p0)
3752 {
3753   struct no_conflict_data *p= p0;
3754
3755   /* If this inns directly contributes to setting the target, it must stay.  */
3756   if (reg_overlap_mentioned_p (p->target, dest))
3757     p->must_stay = true;
3758   /* If we haven't committed to keeping any other insns in the list yet,
3759      there is nothing more to check.  */
3760   else if (p->insn == p->first)
3761     return;
3762   /* If this insn sets / clobbers a register that feeds one of the insns
3763      already in the list, this insn has to stay too.  */
3764   else if (reg_overlap_mentioned_p (dest, PATTERN (p->first))
3765            || (CALL_P (p->first) && (find_reg_fusage (p->first, USE, dest)))
3766            || reg_used_between_p (dest, p->first, p->insn)
3767            /* Likewise if this insn depends on a register set by a previous
3768               insn in the list, or if it sets a result (presumably a hard
3769               register) that is set or clobbered by a previous insn.
3770               N.B. the modified_*_p (SET_DEST...) tests applied to a MEM
3771               SET_DEST perform the former check on the address, and the latter
3772               check on the MEM.  */
3773            || (GET_CODE (set) == SET
3774                && (modified_in_p (SET_SRC (set), p->first)
3775                    || modified_in_p (SET_DEST (set), p->first)
3776                    || modified_between_p (SET_SRC (set), p->first, p->insn)
3777                    || modified_between_p (SET_DEST (set), p->first, p->insn))))
3778     p->must_stay = true;
3779 }
3780
3781 /* Encapsulate the block starting at FIRST and ending with LAST, which is
3782    logically equivalent to EQUIV, so it gets manipulated as a unit if it
3783    is possible to do so.  */
3784
3785 void
3786 maybe_encapsulate_block (rtx first, rtx last, rtx equiv)
3787 {
3788   if (!flag_non_call_exceptions || !may_trap_p (equiv))
3789     {
3790       /* We can't attach the REG_LIBCALL and REG_RETVAL notes when the
3791          encapsulated region would not be in one basic block, i.e. when
3792          there is a control_flow_insn_p insn between FIRST and LAST.  */
3793       bool attach_libcall_retval_notes = true;
3794       rtx insn, next = NEXT_INSN (last);
3795
3796       for (insn = first; insn != next; insn = NEXT_INSN (insn))
3797         if (control_flow_insn_p (insn))
3798           {
3799             attach_libcall_retval_notes = false;
3800             break;
3801           }
3802
3803       if (attach_libcall_retval_notes)
3804         {
3805           REG_NOTES (first) = gen_rtx_INSN_LIST (REG_LIBCALL, last,
3806                                                  REG_NOTES (first));
3807           REG_NOTES (last) = gen_rtx_INSN_LIST (REG_RETVAL, first,
3808                                                 REG_NOTES (last));
3809           next = NEXT_INSN (last);
3810           for (insn = first; insn != next; insn = NEXT_INSN (insn))
3811             REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LIBCALL_ID,
3812                                                   GEN_INT (libcall_id),
3813                                                   REG_NOTES (insn));
3814           libcall_id++;
3815         }
3816     }
3817 }
3818
3819 /* Emit code to perform a series of operations on a multi-word quantity, one
3820    word at a time.
3821
3822    Such a block is preceded by a CLOBBER of the output, consists of multiple
3823    insns, each setting one word of the output, and followed by a SET copying
3824    the output to itself.
3825
3826    Each of the insns setting words of the output receives a REG_NO_CONFLICT
3827    note indicating that it doesn't conflict with the (also multi-word)
3828    inputs.  The entire block is surrounded by REG_LIBCALL and REG_RETVAL
3829    notes.
3830
3831    INSNS is a block of code generated to perform the operation, not including
3832    the CLOBBER and final copy.  All insns that compute intermediate values
3833    are first emitted, followed by the block as described above.
3834
3835    TARGET, OP0, and OP1 are the output and inputs of the operations,
3836    respectively.  OP1 may be zero for a unary operation.
3837
3838    EQUIV, if nonzero, is an expression to be placed into a REG_EQUAL note
3839    on the last insn.
3840
3841    If TARGET is not a register, INSNS is simply emitted with no special
3842    processing.  Likewise if anything in INSNS is not an INSN or if
3843    there is a libcall block inside INSNS.
3844
3845    The final insn emitted is returned.  */
3846
3847 rtx
3848 emit_no_conflict_block (rtx insns, rtx target, rtx op0, rtx op1, rtx equiv)
3849 {
3850   rtx prev, next, first, last, insn;
3851
3852   if (!REG_P (target) || reload_in_progress)
3853     return emit_insn (insns);
3854   else
3855     for (insn = insns; insn; insn = NEXT_INSN (insn))
3856       if (!NONJUMP_INSN_P (insn)
3857           || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
3858         return emit_insn (insns);
3859
3860   /* First emit all insns that do not store into words of the output and remove
3861      these from the list.  */
3862   for (insn = insns; insn; insn = next)
3863     {
3864       rtx note;
3865       struct no_conflict_data data;
3866
3867       next = NEXT_INSN (insn);
3868
3869       /* Some ports (cris) create a libcall regions at their own.  We must
3870          avoid any potential nesting of LIBCALLs.  */
3871       if ((note = find_reg_note (insn, REG_LIBCALL, NULL)) != NULL)
3872         remove_note (insn, note);
3873       if ((note = find_reg_note (insn, REG_RETVAL, NULL)) != NULL)
3874         remove_note (insn, note);
3875       if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL)) != NULL)
3876         remove_note (insn, note);
3877
3878       data.target = target;
3879       data.first = insns;
3880       data.insn = insn;
3881       data.must_stay = 0;
3882       note_stores (PATTERN (insn), no_conflict_move_test, &data);
3883       if (! data.must_stay)
3884         {
3885           if (PREV_INSN (insn))
3886             NEXT_INSN (PREV_INSN (insn)) = next;
3887           else
3888             insns = next;
3889
3890           if (next)
3891             PREV_INSN (next) = PREV_INSN (insn);
3892
3893           add_insn (insn);
3894         }
3895     }
3896
3897   prev = get_last_insn ();
3898
3899   /* Now write the CLOBBER of the output, followed by the setting of each
3900      of the words, followed by the final copy.  */
3901   if (target != op0 && target != op1)
3902     emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
3903
3904   for (insn = insns; insn; insn = next)
3905     {
3906       next = NEXT_INSN (insn);
3907       add_insn (insn);
3908
3909       if (op1 && REG_P (op1))
3910         REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_NO_CONFLICT, op1,
3911                                               REG_NOTES (insn));
3912
3913       if (op0 && REG_P (op0))
3914         REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_NO_CONFLICT, op0,
3915                                               REG_NOTES (insn));
3916     }
3917
3918   if (optab_handler (mov_optab, GET_MODE (target))->insn_code
3919       != CODE_FOR_nothing)
3920     {
3921       last = emit_move_insn (target, target);
3922       if (equiv)
3923         set_unique_reg_note (last, REG_EQUAL, equiv);
3924     }
3925   else
3926     {
3927       last = get_last_insn ();
3928
3929       /* Remove any existing REG_EQUAL note from "last", or else it will
3930          be mistaken for a note referring to the full contents of the
3931          alleged libcall value when found together with the REG_RETVAL
3932          note added below.  An existing note can come from an insn
3933          expansion at "last".  */
3934       remove_note (last, find_reg_note (last, REG_EQUAL, NULL_RTX));
3935     }
3936
3937   if (prev == 0)
3938     first = get_insns ();
3939   else
3940     first = NEXT_INSN (prev);
3941
3942   maybe_encapsulate_block (first, last, equiv);
3943
3944   return last;
3945 }
3946 \f
3947 /* Emit code to make a call to a constant function or a library call.
3948
3949    INSNS is a list containing all insns emitted in the call.
3950    These insns leave the result in RESULT.  Our block is to copy RESULT
3951    to TARGET, which is logically equivalent to EQUIV.
3952
3953    We first emit any insns that set a pseudo on the assumption that these are
3954    loading constants into registers; doing so allows them to be safely cse'ed
3955    between blocks.  Then we emit all the other insns in the block, followed by
3956    an insn to move RESULT to TARGET.  This last insn will have a REQ_EQUAL
3957    note with an operand of EQUIV.
3958
3959    Moving assignments to pseudos outside of the block is done to improve
3960    the generated code, but is not required to generate correct code,
3961    hence being unable to move an assignment is not grounds for not making
3962    a libcall block.  There are two reasons why it is safe to leave these
3963    insns inside the block: First, we know that these pseudos cannot be
3964    used in generated RTL outside the block since they are created for
3965    temporary purposes within the block.  Second, CSE will not record the
3966    values of anything set inside a libcall block, so we know they must
3967    be dead at the end of the block.
3968
3969    Except for the first group of insns (the ones setting pseudos), the
3970    block is delimited by REG_RETVAL and REG_LIBCALL notes.  */
3971 void
3972 emit_libcall_block (rtx insns, rtx target, rtx result, rtx equiv)
3973 {
3974   rtx final_dest = target;
3975   rtx prev, next, first, last, insn;
3976
3977   /* If this is a reg with REG_USERVAR_P set, then it could possibly turn
3978      into a MEM later.  Protect the libcall block from this change.  */
3979   if (! REG_P (target) || REG_USERVAR_P (target))
3980     target = gen_reg_rtx (GET_MODE (target));
3981
3982   /* If we're using non-call exceptions, a libcall corresponding to an
3983      operation that may trap may also trap.  */
3984   if (flag_non_call_exceptions && may_trap_p (equiv))
3985     {
3986       for (insn = insns; insn; insn = NEXT_INSN (insn))
3987         if (CALL_P (insn))
3988           {
3989             rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
3990
3991             if (note != 0 && INTVAL (XEXP (note, 0)) <= 0)
3992               remove_note (insn, note);
3993           }
3994     }
3995   else
3996   /* look for any CALL_INSNs in this sequence, and attach a REG_EH_REGION
3997      reg note to indicate that this call cannot throw or execute a nonlocal
3998      goto (unless there is already a REG_EH_REGION note, in which case
3999      we update it).  */
4000     for (insn = insns; insn; insn = NEXT_INSN (insn))
4001       if (CALL_P (insn))
4002         {
4003           rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
4004
4005           if (note != 0)
4006             XEXP (note, 0) = constm1_rtx;
4007           else
4008             REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_EH_REGION, constm1_rtx,
4009                                                   REG_NOTES (insn));
4010         }
4011
4012   /* First emit all insns that set pseudos.  Remove them from the list as
4013      we go.  Avoid insns that set pseudos which were referenced in previous
4014      insns.  These can be generated by move_by_pieces, for example,
4015      to update an address.  Similarly, avoid insns that reference things
4016      set in previous insns.  */
4017
4018   for (insn = insns; insn; insn = next)
4019     {
4020       rtx set = single_set (insn);
4021       rtx note;
4022
4023       /* Some ports (cris) create a libcall regions at their own.  We must
4024          avoid any potential nesting of LIBCALLs.  */
4025       if ((note = find_reg_note (insn, REG_LIBCALL, NULL)) != NULL)
4026         remove_note (insn, note);
4027       if ((note = find_reg_note (insn, REG_RETVAL, NULL)) != NULL)
4028         remove_note (insn, note);
4029       if ((note = find_reg_note (insn, REG_LIBCALL_ID, NULL)) != NULL)
4030         remove_note (insn, note);
4031
4032       next = NEXT_INSN (insn);
4033
4034       if (set != 0 && REG_P (SET_DEST (set))
4035           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
4036         {
4037           struct no_conflict_data data;
4038
4039           data.target = const0_rtx;
4040           data.first = insns;
4041           data.insn = insn;
4042           data.must_stay = 0;
4043           note_stores (PATTERN (insn), no_conflict_move_test, &data);
4044           if (! data.must_stay)
4045             {
4046               if (PREV_INSN (insn))
4047                 NEXT_INSN (PREV_INSN (insn)) = next;
4048               else
4049                 insns = next;
4050
4051               if (next)
4052                 PREV_INSN (next) = PREV_INSN (insn);
4053
4054               add_insn (insn);
4055             }
4056         }
4057
4058       /* Some ports use a loop to copy large arguments onto the stack.
4059          Don't move anything outside such a loop.  */
4060       if (LABEL_P (insn))
4061         break;
4062     }
4063
4064   prev = get_last_insn ();
4065
4066   /* Write the remaining insns followed by the final copy.  */
4067
4068   for (insn = insns; insn; insn = next)
4069     {
4070       next = NEXT_INSN (insn);
4071
4072       add_insn (insn);
4073     }
4074
4075   last = emit_move_insn (target, result);
4076   if (optab_handler (mov_optab, GET_MODE (target))->insn_code
4077       != CODE_FOR_nothing)
4078     set_unique_reg_note (last, REG_EQUAL, copy_rtx (equiv));
4079   else
4080     {
4081       /* Remove any existing REG_EQUAL note from "last", or else it will