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