gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Currently, the only mini-pass in this file tries to CSE reciprocal
  22    operations.  These are common in sequences such as this one:
  23
  24         modulus = sqrt(x*x + y*y + z*z);
  25         x = x / modulus;
  26         y = y / modulus;
  27         z = z / modulus;
  28
  29    that can be optimized to
  30
  31         modulus = sqrt(x*x + y*y + z*z);
  32         rmodulus = 1.0 / modulus;
  33         x = x * rmodulus;
  34         y = y * rmodulus;
  35         z = z * rmodulus;
  36
  37    We do this for loop invariant divisors, and with this pass whenever
  38    we notice that a division has the same divisor multiple times.
  39
  40    Of course, like in PRE, we don't insert a division if a dominator
  41    already has one.  However, this cannot be done as an extension of
  42    PRE for several reasons.
  43
  44    First of all, with some experiments it was found out that the
  45    transformation is not always useful if there are only two divisions
  46    hy the same divisor.  This is probably because modern processors
  47    can pipeline the divisions; on older, in-order processors it should
  48    still be effective to optimize two divisions by the same number.
  49    We make this a param, and it shall be called N in the remainder of
  50    this comment.
  51
  52    Second, if trapping math is active, we have less freedom on where
  53    to insert divisions: we can only do so in basic blocks that already
  54    contain one.  (If divisions don't trap, instead, we can insert
  55    divisions elsewhere, which will be in blocks that are common dominators
  56    of those that have the division).
  57
  58    We really don't want to compute the reciprocal unless a division will
  59    be found.  To do this, we won't insert the division in a basic block
  60    that has less than N divisions *post-dominating* it.
  61
  62    The algorithm constructs a subset of the dominator tree, holding the
  63    blocks containing the divisions and the common dominators to them,
  64    and walk it twice.  The first walk is in post-order, and it annotates
  65    each block with the number of divisions that post-dominate it: this
  66    gives information on where divisions can be inserted profitably.
  67    The second walk is in pre-order, and it inserts divisions as explained
  68    above, and replaces divisions by multiplications.
  69
  70    In the best case, the cost of the pass is O(n_statements).  In the
  71    worst-case, the cost is due to creating the dominator tree subset,
  72    with a cost of O(n_basic_blocks ^ 2); however this can only happen
  73    for n_statements / n_basic_blocks statements.  So, the amortized cost
  74    of creating the dominator tree subset is O(n_basic_blocks) and the
  75    worst-case cost of the pass is O(n_statements * n_basic_blocks).
  76
  77    More practically, the cost will be small because there are few
  78    divisions, and they tend to be in the same basic block, so insert_bb
  79    is called very few times.
  80
  81    If we did this using domwalk.c, an efficient implementation would have
  82    to work on all the variables in a single pass, because we could not
  83    work on just a subset of the dominator tree, as we do now, and the
  84    cost would also be something like O(n_statements * n_basic_blocks).
  85    The data structures would be more complex in order to work on all the
  86    variables in a single pass.  */
  87
  88 #include "config.h"
  89 #include "system.h"
  90 #include "coretypes.h"
  91 #include "tm.h"
  92 #include "flags.h"
  93 #include "tree.h"
  94 #include "tree-flow.h"
  95 #include "timevar.h"
  96 #include "tree-pass.h"
  97 #include "alloc-pool.h"
  98 #include "basic-block.h"
  99 #include "target.h"
 100 #include "gimple-pretty-print.h"
 101
 102 /* FIXME: RTL headers have to be included here for optabs.  */
 103 #include "rtl.h"                /* Because optabs.h wants enum rtx_code.  */
 104 #include "expr.h"               /* Because optabs.h wants sepops.  */
 105 #include "optabs.h"
 106
 107 /* This structure represents one basic block that either computes a
 108    division, or is a common dominator for basic block that compute a
 109    division.  */
 110 struct occurrence {
 111   /* The basic block represented by this structure.  */
 112   basic_block bb;
 113
 114   /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
 115      inserted in BB.  */
 116   tree recip_def;
 117
 118   /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
 119      was inserted in BB.  */
 120   gimple recip_def_stmt;
 121
 122   /* Pointer to a list of "struct occurrence"s for blocks dominated
 123      by BB.  */
 124   struct occurrence *children;
 125
 126   /* Pointer to the next "struct occurrence"s in the list of blocks
 127      sharing a common dominator.  */
 128   struct occurrence *next;
 129
 130   /* The number of divisions that are in BB before compute_merit.  The
 131      number of divisions that are in BB or post-dominate it after
 132      compute_merit.  */
 133   int num_divisions;
 134
 135   /* True if the basic block has a division, false if it is a common
 136      dominator for basic blocks that do.  If it is false and trapping
 137      math is active, BB is not a candidate for inserting a reciprocal.  */
 138   bool bb_has_division;
 139 };
 140
 141 static struct
 142 {
 143   /* Number of 1.0/X ops inserted.  */
 144   int rdivs_inserted;
 145
 146   /* Number of 1.0/FUNC ops inserted.  */
 147   int rfuncs_inserted;
 148 } reciprocal_stats;
 149
 150 static struct
 151 {
 152   /* Number of cexpi calls inserted.  */
 153   int inserted;
 154 } sincos_stats;
 155
 156 static struct
 157 {
 158   /* Number of hand-written 32-bit bswaps found.  */
 159   int found_32bit;
 160
 161   /* Number of hand-written 64-bit bswaps found.  */
 162   int found_64bit;
 163 } bswap_stats;
 164
 165 static struct
 166 {
 167   /* Number of widening multiplication ops inserted.  */
 168   int widen_mults_inserted;
 169
 170   /* Number of integer multiply-and-accumulate ops inserted.  */
 171   int maccs_inserted;
 172
 173   /* Number of fp fused multiply-add ops inserted.  */
 174   int fmas_inserted;
 175 } widen_mul_stats;
 176
 177 /* The instance of "struct occurrence" representing the highest
 178    interesting block in the dominator tree.  */
 179 static struct occurrence *occ_head;
 180
 181 /* Allocation pool for getting instances of "struct occurrence".  */
 182 static alloc_pool occ_pool;
 183
 184
 185
 186 /* Allocate and return a new struct occurrence for basic block BB, and
 187    whose children list is headed by CHILDREN.  */
 188 static struct occurrence *
 189 occ_new (basic_block bb, struct occurrence *children)
 190 {
 191   struct occurrence *occ;
 192
 193   bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
 194   memset (occ, 0, sizeof (struct occurrence));
 195
 196   occ->bb = bb;
 197   occ->children = children;
 198   return occ;
 199 }
 200
 201
 202 /* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
 203    list of "struct occurrence"s, one per basic block, having IDOM as
 204    their common dominator.
 205
 206    We try to insert NEW_OCC as deep as possible in the tree, and we also
 207    insert any other block that is a common dominator for BB and one
 208    block already in the tree.  */
 209
 210 static void
 211 insert_bb (struct occurrence *new_occ, basic_block idom,
 212            struct occurrence **p_head)
 213 {
 214   struct occurrence *occ, **p_occ;
 215
 216   for (p_occ = p_head; (occ = *p_occ) != NULL; )
 217     {
 218       basic_block bb = new_occ->bb, occ_bb = occ->bb;
 219       basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
 220       if (dom == bb)
 221         {
 222           /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
 223              from its list.  */
 224           *p_occ = occ->next;
 225           occ->next = new_occ->children;
 226           new_occ->children = occ;
 227
 228           /* Try the next block (it may as well be dominated by BB).  */
 229         }
 230
 231       else if (dom == occ_bb)
 232         {
 233           /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
 234           insert_bb (new_occ, dom, &occ->children);
 235           return;
 236         }
 237
 238       else if (dom != idom)
 239         {
 240           gcc_assert (!dom->aux);
 241
 242           /* There is a dominator between IDOM and BB, add it and make
 243              two children out of NEW_OCC and OCC.  First, remove OCC from
 244              its list.  */
 245           *p_occ = occ->next;
 246           new_occ->next = occ;
 247           occ->next = NULL;
 248
 249           /* None of the previous blocks has DOM as a dominator: if we tail
 250              recursed, we would reexamine them uselessly. Just switch BB with
 251              DOM, and go on looking for blocks dominated by DOM.  */
 252           new_occ = occ_new (dom, new_occ);
 253         }
 254
 255       else
 256         {
 257           /* Nothing special, go on with the next element.  */
 258           p_occ = &occ->next;
 259         }
 260     }
 261
 262   /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
 263   new_occ->next = *p_head;
 264   *p_head = new_occ;
 265 }
 266
 267 /* Register that we found a division in BB.  */
 268
 269 static inline void
 270 register_division_in (basic_block bb)
 271 {
 272   struct occurrence *occ;
 273
 274   occ = (struct occurrence *) bb->aux;
 275   if (!occ)
 276     {
 277       occ = occ_new (bb, NULL);
 278       insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
 279     }
 280
 281   occ->bb_has_division = true;
 282   occ->num_divisions++;
 283 }
 284
 285
 286 /* Compute the number of divisions that postdominate each block in OCC and
 287    its children.  */
 288
 289 static void
 290 compute_merit (struct occurrence *occ)
 291 {
 292   struct occurrence *occ_child;
 293   basic_block dom = occ->bb;
 294
 295   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 296     {
 297       basic_block bb;
 298       if (occ_child->children)
 299         compute_merit (occ_child);
 300
 301       if (flag_exceptions)
 302         bb = single_noncomplex_succ (dom);
 303       else
 304         bb = dom;
 305
 306       if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
 307         occ->num_divisions += occ_child->num_divisions;
 308     }
 309 }
 310
 311
 312 /* Return whether USE_STMT is a floating-point division by DEF.  */
 313 static inline bool
 314 is_division_by (gimple use_stmt, tree def)
 315 {
 316   return is_gimple_assign (use_stmt)
 317          && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
 318          && gimple_assign_rhs2 (use_stmt) == def
 319          /* Do not recognize x / x as valid division, as we are getting
 320             confused later by replacing all immediate uses x in such
 321             a stmt.  */
 322          && gimple_assign_rhs1 (use_stmt) != def;
 323 }
 324
 325 /* Walk the subset of the dominator tree rooted at OCC, setting the
 326    RECIP_DEF field to a definition of 1.0 / DEF that can be used in
 327    the given basic block.  The field may be left NULL, of course,
 328    if it is not possible or profitable to do the optimization.
 329
 330    DEF_BSI is an iterator pointing at the statement defining DEF.
 331    If RECIP_DEF is set, a dominator already has a computation that can
 332    be used.  */
 333
 334 static void
 335 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
 336                     tree def, tree recip_def, int threshold)
 337 {
 338   tree type;
 339   gimple new_stmt;
 340   gimple_stmt_iterator gsi;
 341   struct occurrence *occ_child;
 342
 343   if (!recip_def
 344       && (occ->bb_has_division || !flag_trapping_math)
 345       && occ->num_divisions >= threshold)
 346     {
 347       /* Make a variable with the replacement and substitute it.  */
 348       type = TREE_TYPE (def);
 349       recip_def = make_rename_temp (type, "reciptmp");
 350       new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
 351                                                build_one_cst (type), def);
 352
 353       if (occ->bb_has_division)
 354         {
 355           /* Case 1: insert before an existing division.  */
 356           gsi = gsi_after_labels (occ->bb);
 357           while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
 358             gsi_next (&gsi);
 359
 360           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 361         }
 362       else if (def_gsi && occ->bb == def_gsi->bb)
 363         {
 364           /* Case 2: insert right after the definition.  Note that this will
 365              never happen if the definition statement can throw, because in
 366              that case the sole successor of the statement's basic block will
 367              dominate all the uses as well.  */
 368           gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
 369         }
 370       else
 371         {
 372           /* Case 3: insert in a basic block not containing defs/uses.  */
 373           gsi = gsi_after_labels (occ->bb);
 374           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 375         }
 376
 377       reciprocal_stats.rdivs_inserted++;
 378
 379       occ->recip_def_stmt = new_stmt;
 380     }
 381
 382   occ->recip_def = recip_def;
 383   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 384     insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
 385 }
 386
 387
 388 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 389    possible.  */
 390
 391 static inline void
 392 replace_reciprocal (use_operand_p use_p)
 393 {
 394   gimple use_stmt = USE_STMT (use_p);
 395   basic_block bb = gimple_bb (use_stmt);
 396   struct occurrence *occ = (struct occurrence *) bb->aux;
 397
 398   if (optimize_bb_for_speed_p (bb)
 399       && occ->recip_def && use_stmt != occ->recip_def_stmt)
 400     {
 401       gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
 402       SET_USE (use_p, occ->recip_def);
 403       fold_stmt_inplace (use_stmt);
 404       update_stmt (use_stmt);
 405     }
 406 }
 407
 408
 409 /* Free OCC and return one more "struct occurrence" to be freed.  */
 410
 411 static struct occurrence *
 412 free_bb (struct occurrence *occ)
 413 {
 414   struct occurrence *child, *next;
 415
 416   /* First get the two pointers hanging off OCC.  */
 417   next = occ->next;
 418   child = occ->children;
 419   occ->bb->aux = NULL;
 420   pool_free (occ_pool, occ);
 421
 422   /* Now ensure that we don't recurse unless it is necessary.  */
 423   if (!child)
 424     return next;
 425   else
 426     {
 427       while (next)
 428         next = free_bb (next);
 429
 430       return child;
 431     }
 432 }
 433
 434
 435 /* Look for floating-point divisions among DEF's uses, and try to
 436    replace them by multiplications with the reciprocal.  Add
 437    as many statements computing the reciprocal as needed.
 438
 439    DEF must be a GIMPLE register of a floating-point type.  */
 440
 441 static void
 442 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
 443 {
 444   use_operand_p use_p;
 445   imm_use_iterator use_iter;
 446   struct occurrence *occ;
 447   int count = 0, threshold;
 448
 449   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 450
 451   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 452     {
 453       gimple use_stmt = USE_STMT (use_p);
 454       if (is_division_by (use_stmt, def))
 455         {
 456           register_division_in (gimple_bb (use_stmt));
 457           count++;
 458         }
 459     }
 460
 461   /* Do the expensive part only if we can hope to optimize something.  */
 462   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 463   if (count >= threshold)
 464     {
 465       gimple use_stmt;
 466       for (occ = occ_head; occ; occ = occ->next)
 467         {
 468           compute_merit (occ);
 469           insert_reciprocals (def_gsi, occ, def, NULL, threshold);
 470         }
 471
 472       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 473         {
 474           if (is_division_by (use_stmt, def))
 475             {
 476               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 477                 replace_reciprocal (use_p);
 478             }
 479         }
 480     }
 481
 482   for (occ = occ_head; occ; )
 483     occ = free_bb (occ);
 484
 485   occ_head = NULL;
 486 }
 487
 488 static bool
 489 gate_cse_reciprocals (void)
 490 {
 491   return optimize && flag_reciprocal_math;
 492 }
 493
 494 /* Go through all the floating-point SSA_NAMEs, and call
 495    execute_cse_reciprocals_1 on each of them.  */
 496 static unsigned int
 497 execute_cse_reciprocals (void)
 498 {
 499   basic_block bb;
 500   tree arg;
 501
 502   occ_pool = create_alloc_pool ("dominators for recip",
 503                                 sizeof (struct occurrence),
 504                                 n_basic_blocks / 3 + 1);
 505
 506   memset (&reciprocal_stats, 0, sizeof (reciprocal_stats));
 507   calculate_dominance_info (CDI_DOMINATORS);
 508   calculate_dominance_info (CDI_POST_DOMINATORS);
 509
 510 #ifdef ENABLE_CHECKING
 511   FOR_EACH_BB (bb)
 512     gcc_assert (!bb->aux);
 513 #endif
 514
 515   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = DECL_CHAIN (arg))
 516     if (gimple_default_def (cfun, arg)
 517         && FLOAT_TYPE_P (TREE_TYPE (arg))
 518         && is_gimple_reg (arg))
 519       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 520
 521   FOR_EACH_BB (bb)
 522     {
 523       gimple_stmt_iterator gsi;
 524       gimple phi;
 525       tree def;
 526
 527       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 528         {
 529           phi = gsi_stmt (gsi);
 530           def = PHI_RESULT (phi);
 531           if (FLOAT_TYPE_P (TREE_TYPE (def))
 532               && is_gimple_reg (def))
 533             execute_cse_reciprocals_1 (NULL, def);
 534         }
 535
 536       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 537         {
 538           gimple stmt = gsi_stmt (gsi);
 539
 540           if (gimple_has_lhs (stmt)
 541               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 542               && FLOAT_TYPE_P (TREE_TYPE (def))
 543               && TREE_CODE (def) == SSA_NAME)
 544             execute_cse_reciprocals_1 (&gsi, def);
 545         }
 546
 547       if (optimize_bb_for_size_p (bb))
 548         continue;
 549
 550       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 551       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 552         {
 553           gimple stmt = gsi_stmt (gsi);
 554           tree fndecl;
 555
 556           if (is_gimple_assign (stmt)
 557               && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
 558             {
 559               tree arg1 = gimple_assign_rhs2 (stmt);
 560               gimple stmt1;
 561
 562               if (TREE_CODE (arg1) != SSA_NAME)
 563                 continue;
 564
 565               stmt1 = SSA_NAME_DEF_STMT (arg1);
 566
 567               if (is_gimple_call (stmt1)
 568                   && gimple_call_lhs (stmt1)
 569                   && (fndecl = gimple_call_fndecl (stmt1))
 570                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 571                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 572                 {
 573                   enum built_in_function code;
 574                   bool md_code, fail;
 575                   imm_use_iterator ui;
 576                   use_operand_p use_p;
 577
 578                   code = DECL_FUNCTION_CODE (fndecl);
 579                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 580
 581                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 582                   if (!fndecl)
 583                     continue;
 584
 585                   /* Check that all uses of the SSA name are divisions,
 586                      otherwise replacing the defining statement will do
 587                      the wrong thing.  */
 588                   fail = false;
 589                   FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
 590                     {
 591                       gimple stmt2 = USE_STMT (use_p);
 592                       if (is_gimple_debug (stmt2))
 593                         continue;
 594                       if (!is_gimple_assign (stmt2)
 595                           || gimple_assign_rhs_code (stmt2) != RDIV_EXPR
 596                           || gimple_assign_rhs1 (stmt2) == arg1
 597                           || gimple_assign_rhs2 (stmt2) != arg1)
 598                         {
 599                           fail = true;
 600                           break;
 601                         }
 602                     }
 603                   if (fail)
 604                     continue;
 605
 606                   gimple_replace_lhs (stmt1, arg1);
 607                   gimple_call_set_fndecl (stmt1, fndecl);
 608                   update_stmt (stmt1);
 609                   reciprocal_stats.rfuncs_inserted++;
 610
 611                   FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
 612                     {
 613                       gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 614                       fold_stmt_inplace (stmt);
 615                       update_stmt (stmt);
 616                     }
 617                 }
 618             }
 619         }
 620     }
 621
 622   statistics_counter_event (cfun, "reciprocal divs inserted",
 623                             reciprocal_stats.rdivs_inserted);
 624   statistics_counter_event (cfun, "reciprocal functions inserted",
 625                             reciprocal_stats.rfuncs_inserted);
 626
 627   free_dominance_info (CDI_DOMINATORS);
 628   free_dominance_info (CDI_POST_DOMINATORS);
 629   free_alloc_pool (occ_pool);
 630   return 0;
 631 }
 632
 633 struct gimple_opt_pass pass_cse_reciprocals =
 634 {
 635  {
 636   GIMPLE_PASS,
 637   "recip",                              /* name */
 638   gate_cse_reciprocals,                 /* gate */
 639   execute_cse_reciprocals,              /* execute */
 640   NULL,                                 /* sub */
 641   NULL,                                 /* next */
 642   0,                                    /* static_pass_number */
 643   TV_NONE,                              /* tv_id */
 644   PROP_ssa,                             /* properties_required */
 645   0,                                    /* properties_provided */
 646   0,                                    /* properties_destroyed */
 647   0,                                    /* todo_flags_start */
 648   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 649     | TODO_verify_stmts                /* todo_flags_finish */
 650  }
 651 };
 652
 653 /* Records an occurrence at statement USE_STMT in the vector of trees
 654    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 655    is not yet initialized.  Returns true if the occurrence was pushed on
 656    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 657    statements in the vector.  */
 658
 659 static bool
 660 maybe_record_sincos (VEC(gimple, heap) **stmts,
 661                      basic_block *top_bb, gimple use_stmt)
 662 {
 663   basic_block use_bb = gimple_bb (use_stmt);
 664   if (*top_bb
 665       && (*top_bb == use_bb
 666           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 667     VEC_safe_push (gimple, heap, *stmts, use_stmt);
 668   else if (!*top_bb
 669            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 670     {
 671       VEC_safe_push (gimple, heap, *stmts, use_stmt);
 672       *top_bb = use_bb;
 673     }
 674   else
 675     return false;
 676
 677   return true;
 678 }
 679
 680 /* Look for sin, cos and cexpi calls with the same argument NAME and
 681    create a single call to cexpi CSEing the result in this case.
 682    We first walk over all immediate uses of the argument collecting
 683    statements that we can CSE in a vector and in a second pass replace
 684    the statement rhs with a REALPART or IMAGPART expression on the
 685    result of the cexpi call we insert before the use statement that
 686    dominates all other candidates.  */
 687
 688 static bool
 689 execute_cse_sincos_1 (tree name)
 690 {
 691   gimple_stmt_iterator gsi;
 692   imm_use_iterator use_iter;
 693   tree fndecl, res, type;
 694   gimple def_stmt, use_stmt, stmt;
 695   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 696   VEC(gimple, heap) *stmts = NULL;
 697   basic_block top_bb = NULL;
 698   int i;
 699   bool cfg_changed = false;
 700
 701   type = TREE_TYPE (name);
 702   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 703     {
 704       if (gimple_code (use_stmt) != GIMPLE_CALL
 705           || !gimple_call_lhs (use_stmt)
 706           || !(fndecl = gimple_call_fndecl (use_stmt))
 707           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 708         continue;
 709
 710       switch (DECL_FUNCTION_CODE (fndecl))
 711         {
 712         CASE_FLT_FN (BUILT_IN_COS):
 713           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 714           break;
 715
 716         CASE_FLT_FN (BUILT_IN_SIN):
 717           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 718           break;
 719
 720         CASE_FLT_FN (BUILT_IN_CEXPI):
 721           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 722           break;
 723
 724         default:;
 725         }
 726     }
 727
 728   if (seen_cos + seen_sin + seen_cexpi <= 1)
 729     {
 730       VEC_free(gimple, heap, stmts);
 731       return false;
 732     }
 733
 734   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 735      the name def statement.  */
 736   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 737   if (!fndecl)
 738     return false;
 739   res = create_tmp_reg (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 740   stmt = gimple_build_call (fndecl, 1, name);
 741   res = make_ssa_name (res, stmt);
 742   gimple_call_set_lhs (stmt, res);
 743
 744   def_stmt = SSA_NAME_DEF_STMT (name);
 745   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 746       && gimple_code (def_stmt) != GIMPLE_PHI
 747       && gimple_bb (def_stmt) == top_bb)
 748     {
 749       gsi = gsi_for_stmt (def_stmt);
 750       gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 751     }
 752   else
 753     {
 754       gsi = gsi_after_labels (top_bb);
 755       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 756     }
 757   update_stmt (stmt);
 758   sincos_stats.inserted++;
 759
 760   /* And adjust the recorded old call sites.  */
 761   for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
 762     {
 763       tree rhs = NULL;
 764       fndecl = gimple_call_fndecl (use_stmt);
 765
 766       switch (DECL_FUNCTION_CODE (fndecl))
 767         {
 768         CASE_FLT_FN (BUILT_IN_COS):
 769           rhs = fold_build1 (REALPART_EXPR, type, res);
 770           break;
 771
 772         CASE_FLT_FN (BUILT_IN_SIN):
 773           rhs = fold_build1 (IMAGPART_EXPR, type, res);
 774           break;
 775
 776         CASE_FLT_FN (BUILT_IN_CEXPI):
 777           rhs = res;
 778           break;
 779
 780         default:;
 781           gcc_unreachable ();
 782         }
 783
 784         /* Replace call with a copy.  */
 785         stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
 786
 787         gsi = gsi_for_stmt (use_stmt);
 788         gsi_replace (&gsi, stmt, true);
 789         if (gimple_purge_dead_eh_edges (gimple_bb (stmt)))
 790           cfg_changed = true;
 791     }
 792
 793   VEC_free(gimple, heap, stmts);
 794
 795   return cfg_changed;
 796 }
 797
 798 /* To evaluate powi(x,n), the floating point value x raised to the
 799    constant integer exponent n, we use a hybrid algorithm that
 800    combines the "window method" with look-up tables.  For an
 801    introduction to exponentiation algorithms and "addition chains",
 802    see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
 803    "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
 804    3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
 805    Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998.  */
 806
 807 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
 808    multiplications to inline before calling the system library's pow
 809    function.  powi(x,n) requires at worst 2*bits(n)-2 multiplications,
 810    so this default never requires calling pow, powf or powl.  */
 811
 812 #ifndef POWI_MAX_MULTS
 813 #define POWI_MAX_MULTS  (2*HOST_BITS_PER_WIDE_INT-2)
 814 #endif
 815
 816 /* The size of the "optimal power tree" lookup table.  All
 817    exponents less than this value are simply looked up in the
 818    powi_table below.  This threshold is also used to size the
 819    cache of pseudo registers that hold intermediate results.  */
 820 #define POWI_TABLE_SIZE 256
 821
 822 /* The size, in bits of the window, used in the "window method"
 823    exponentiation algorithm.  This is equivalent to a radix of
 824    (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method".  */
 825 #define POWI_WINDOW_SIZE 3
 826
 827 /* The following table is an efficient representation of an
 828    "optimal power tree".  For each value, i, the corresponding
 829    value, j, in the table states than an optimal evaluation
 830    sequence for calculating pow(x,i) can be found by evaluating
 831    pow(x,j)*pow(x,i-j).  An optimal power tree for the first
 832    100 integers is given in Knuth's "Seminumerical algorithms".  */
 833
 834 static const unsigned char powi_table[POWI_TABLE_SIZE] =
 835   {
 836       0,   1,   1,   2,   2,   3,   3,   4,  /*   0 -   7 */
 837       4,   6,   5,   6,   6,  10,   7,   9,  /*   8 -  15 */
 838       8,  16,   9,  16,  10,  12,  11,  13,  /*  16 -  23 */
 839      12,  17,  13,  18,  14,  24,  15,  26,  /*  24 -  31 */
 840      16,  17,  17,  19,  18,  33,  19,  26,  /*  32 -  39 */
 841      20,  25,  21,  40,  22,  27,  23,  44,  /*  40 -  47 */
 842      24,  32,  25,  34,  26,  29,  27,  44,  /*  48 -  55 */
 843      28,  31,  29,  34,  30,  60,  31,  36,  /*  56 -  63 */
 844      32,  64,  33,  34,  34,  46,  35,  37,  /*  64 -  71 */
 845      36,  65,  37,  50,  38,  48,  39,  69,  /*  72 -  79 */
 846      40,  49,  41,  43,  42,  51,  43,  58,  /*  80 -  87 */
 847      44,  64,  45,  47,  46,  59,  47,  76,  /*  88 -  95 */
 848      48,  65,  49,  66,  50,  67,  51,  66,  /*  96 - 103 */
 849      52,  70,  53,  74,  54, 104,  55,  74,  /* 104 - 111 */
 850      56,  64,  57,  69,  58,  78,  59,  68,  /* 112 - 119 */
 851      60,  61,  61,  80,  62,  75,  63,  68,  /* 120 - 127 */
 852      64,  65,  65, 128,  66, 129,  67,  90,  /* 128 - 135 */
 853      68,  73,  69, 131,  70,  94,  71,  88,  /* 136 - 143 */
 854      72, 128,  73,  98,  74, 132,  75, 121,  /* 144 - 151 */
 855      76, 102,  77, 124,  78, 132,  79, 106,  /* 152 - 159 */
 856      80,  97,  81, 160,  82,  99,  83, 134,  /* 160 - 167 */
 857      84,  86,  85,  95,  86, 160,  87, 100,  /* 168 - 175 */
 858      88, 113,  89,  98,  90, 107,  91, 122,  /* 176 - 183 */
 859      92, 111,  93, 102,  94, 126,  95, 150,  /* 184 - 191 */
 860      96, 128,  97, 130,  98, 133,  99, 195,  /* 192 - 199 */
 861     100, 128, 101, 123, 102, 164, 103, 138,  /* 200 - 207 */
 862     104, 145, 105, 146, 106, 109, 107, 149,  /* 208 - 215 */
 863     108, 200, 109, 146, 110, 170, 111, 157,  /* 216 - 223 */
 864     112, 128, 113, 130, 114, 182, 115, 132,  /* 224 - 231 */
 865     116, 200, 117, 132, 118, 158, 119, 206,  /* 232 - 239 */
 866     120, 240, 121, 162, 122, 147, 123, 152,  /* 240 - 247 */
 867     124, 166, 125, 214, 126, 138, 127, 153,  /* 248 - 255 */
 868   };
 869
 870
 871 /* Return the number of multiplications required to calculate
 872    powi(x,n) where n is less than POWI_TABLE_SIZE.  This is a
 873    subroutine of powi_cost.  CACHE is an array indicating
 874    which exponents have already been calculated.  */
 875
 876 static int
 877 powi_lookup_cost (unsigned HOST_WIDE_INT n, bool *cache)
 878 {
 879   /* If we've already calculated this exponent, then this evaluation
 880      doesn't require any additional multiplications.  */
 881   if (cache[n])
 882     return 0;
 883
 884   cache[n] = true;
 885   return powi_lookup_cost (n - powi_table[n], cache)
 886          + powi_lookup_cost (powi_table[n], cache) + 1;
 887 }
 888
 889 /* Return the number of multiplications required to calculate
 890    powi(x,n) for an arbitrary x, given the exponent N.  This
 891    function needs to be kept in sync with powi_as_mults below.  */
 892
 893 static int
 894 powi_cost (HOST_WIDE_INT n)
 895 {
 896   bool cache[POWI_TABLE_SIZE];
 897   unsigned HOST_WIDE_INT digit;
 898   unsigned HOST_WIDE_INT val;
 899   int result;
 900
 901   if (n == 0)
 902     return 0;
 903
 904   /* Ignore the reciprocal when calculating the cost.  */
 905   val = (n < 0) ? -n : n;
 906
 907   /* Initialize the exponent cache.  */
 908   memset (cache, 0, POWI_TABLE_SIZE * sizeof (bool));
 909   cache[1] = true;
 910
 911   result = 0;
 912
 913   while (val >= POWI_TABLE_SIZE)
 914     {
 915       if (val & 1)
 916         {
 917           digit = val & ((1 << POWI_WINDOW_SIZE) - 1);
 918           result += powi_lookup_cost (digit, cache)
 919                     + POWI_WINDOW_SIZE + 1;
 920           val >>= POWI_WINDOW_SIZE;
 921         }
 922       else
 923         {
 924           val >>= 1;
 925           result++;
 926         }
 927     }
 928
 929   return result + powi_lookup_cost (val, cache);
 930 }
 931
 932 /* Recursive subroutine of powi_as_mults.  This function takes the
 933    array, CACHE, of already calculated exponents and an exponent N and
 934    returns a tree that corresponds to CACHE[1]**N, with type TYPE.  */
 935
 936 static tree
 937 powi_as_mults_1 (gimple_stmt_iterator *gsi, location_t loc, tree type,
 938                  HOST_WIDE_INT n, tree *cache, tree target)
 939 {
 940   tree op0, op1, ssa_target;
 941   unsigned HOST_WIDE_INT digit;
 942   gimple mult_stmt;
 943
 944   if (n < POWI_TABLE_SIZE && cache[n])
 945     return cache[n];
 946
 947   ssa_target = make_ssa_name (target, NULL);
 948
 949   if (n < POWI_TABLE_SIZE)
 950     {
 951       cache[n] = ssa_target;
 952       op0 = powi_as_mults_1 (gsi, loc, type, n - powi_table[n], cache, target);
 953       op1 = powi_as_mults_1 (gsi, loc, type, powi_table[n], cache, target);
 954     }
 955   else if (n & 1)
 956     {
 957       digit = n & ((1 << POWI_WINDOW_SIZE) - 1);
 958       op0 = powi_as_mults_1 (gsi, loc, type, n - digit, cache, target);
 959       op1 = powi_as_mults_1 (gsi, loc, type, digit, cache, target);
 960     }
 961   else
 962     {
 963       op0 = powi_as_mults_1 (gsi, loc, type, n >> 1, cache, target);
 964       op1 = op0;
 965     }
 966
 967   mult_stmt = gimple_build_assign_with_ops (MULT_EXPR, ssa_target, op0, op1);
 968   gimple_set_location (mult_stmt, loc);
 969   gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT);
 970
 971   return ssa_target;
 972 }
 973
 974 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
 975    This function needs to be kept in sync with powi_cost above.  */
 976
 977 static tree
 978 powi_as_mults (gimple_stmt_iterator *gsi, location_t loc,
 979                tree arg0, HOST_WIDE_INT n)
 980 {
 981   tree cache[POWI_TABLE_SIZE], result, type = TREE_TYPE (arg0), target;
 982   gimple div_stmt;
 983
 984   if (n == 0)
 985     return build_real (type, dconst1);
 986
 987   memset (cache, 0,  sizeof (cache));
 988   cache[1] = arg0;
 989
 990   target = create_tmp_var (type, "powmult");
 991   add_referenced_var (target);
 992
 993   result = powi_as_mults_1 (gsi, loc, type, (n < 0) ? -n : n, cache, target);
 994
 995   if (n >= 0)
 996     return result;
 997
 998   /* If the original exponent was negative, reciprocate the result.  */
 999   target = make_ssa_name (target, NULL);
1000   div_stmt = gimple_build_assign_with_ops (RDIV_EXPR, target,
1001                                            build_real (type, dconst1),
1002                                            result);
1003   gimple_set_location (div_stmt, loc);
1004   gsi_insert_before (gsi, div_stmt, GSI_SAME_STMT);
1005
1006   return target;
1007 }
1008
1009 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1010    location info LOC.  If the arguments are appropriate, create an
1011    equivalent sequence of statements prior to GSI using an optimal
1012    number of multiplications, and return an expession holding the
1013    result.  */
1014
1015 static tree
1016 gimple_expand_builtin_powi (gimple_stmt_iterator *gsi, location_t loc,
1017                             tree arg0, HOST_WIDE_INT n)
1018 {
1019   /* Avoid largest negative number.  */
1020   if (n != -n
1021       && ((n >= -1 && n <= 2)
1022           || (optimize_function_for_speed_p (cfun)
1023               && powi_cost (n) <= POWI_MAX_MULTS)))
1024     return powi_as_mults (gsi, loc, arg0, n);
1025
1026   return NULL_TREE;
1027 }
1028
1029 /* Build a gimple call statement that calls FN with argument ARG.
1030    Set the lhs of the call statement to a fresh SSA name for
1031    variable VAR.  If VAR is NULL, first allocate it.  Insert the
1032    statement prior to GSI's current position, and return the fresh
1033    SSA name.  */
1034
1035 static tree
1036 build_and_insert_call (gimple_stmt_iterator *gsi, tree fn, tree arg,
1037                        tree *var, location_t loc)
1038 {
1039   gimple call_stmt;
1040   tree ssa_target;
1041
1042   if (!*var)
1043     {
1044       *var = create_tmp_var (TREE_TYPE (arg), "powroot");
1045       add_referenced_var (*var);
1046     }
1047
1048   call_stmt = gimple_build_call (fn, 1, arg);
1049   ssa_target = make_ssa_name (*var, NULL);
1050   gimple_set_lhs (call_stmt, ssa_target);
1051   gimple_set_location (call_stmt, loc);
1052   gsi_insert_before (gsi, call_stmt, GSI_SAME_STMT);
1053
1054   return ssa_target;
1055 }
1056
1057 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1058    with location info LOC.  If possible, create an equivalent and
1059    less expensive sequence of statements prior to GSI, and return an
1060    expession holding the result.  */
1061
1062 static tree
1063 gimple_expand_builtin_pow (gimple_stmt_iterator *gsi, location_t loc,
1064                            tree arg0, tree arg1)
1065 {
1066   REAL_VALUE_TYPE c, cint, dconst1_4, dconst3_4, dconst1_3, dconst1_6;
1067   HOST_WIDE_INT n;
1068   tree type, sqrtfn, cbrtfn, sqrt_arg0, sqrt_sqrt, ssa_target;
1069   tree target = NULL_TREE;
1070   enum machine_mode mode;
1071   bool hw_sqrt_exists;
1072   gimple mult_stmt;
1073
1074   /* If the exponent isn't a constant, there's nothing of interest
1075      to be done.  */
1076   if (TREE_CODE (arg1) != REAL_CST)
1077     return NULL_TREE;
1078
1079   /* If the exponent is equivalent to an integer, expand to an optimal
1080      multiplication sequence when profitable.  */
1081   c = TREE_REAL_CST (arg1);
1082   n = real_to_integer (&c);
1083   real_from_integer (&cint, VOIDmode, n, n < 0 ? -1 : 0, 0);
1084
1085   if (real_identical (&c, &cint)
1086       && ((n >= -1 && n <= 2)
1087           || (flag_unsafe_math_optimizations
1088               && optimize_insn_for_speed_p ()
1089               && powi_cost (n) <= POWI_MAX_MULTS)))
1090     return gimple_expand_builtin_powi (gsi, loc, arg0, n);
1091
1092   /* Attempt various optimizations using sqrt and cbrt.  */
1093   type = TREE_TYPE (arg0);
1094   mode = TYPE_MODE (type);
1095   sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT);
1096
1097   /* Optimize pow(x,0.5) = sqrt(x).  This replacement is always safe
1098      unless signed zeros must be maintained.  pow(-0,0.5) = +0, while
1099      sqrt(-0) = -0.  */
1100   if (sqrtfn
1101       && REAL_VALUES_EQUAL (c, dconsthalf)
1102       && !HONOR_SIGNED_ZEROS (mode))
1103     return build_and_insert_call (gsi, sqrtfn, arg0, &target, loc);
1104
1105   /* Optimize pow(x,0.25) = sqrt(sqrt(x)).  Assume on most machines that
1106      a builtin sqrt instruction is smaller than a call to pow with 0.25,
1107      so do this optimization even if -Os.  Don't do this optimization
1108      if we don't have a hardware sqrt insn.  */
1109   dconst1_4 = dconst1;
1110   SET_REAL_EXP (&dconst1_4, REAL_EXP (&dconst1_4) - 2);
1111   hw_sqrt_exists = optab_handler(sqrt_optab, mode) != CODE_FOR_nothing;
1112
1113   if (flag_unsafe_math_optimizations
1114       && sqrtfn
1115       && REAL_VALUES_EQUAL (c, dconst1_4)
1116       && hw_sqrt_exists)
1117     {
1118       /* sqrt(x)  */
1119       sqrt_arg0 = build_and_insert_call (gsi, sqrtfn, arg0, &target, loc);
1120
1121       /* sqrt(sqrt(x))  */
1122       return build_and_insert_call (gsi, sqrtfn, sqrt_arg0, &target, loc);
1123     }
1124
1125   /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1126      optimizing for space.  Don't do this optimization if we don't have
1127      a hardware sqrt insn.  */
1128   real_from_integer (&dconst3_4, VOIDmode, 3, 0, 0);
1129   SET_REAL_EXP (&dconst3_4, REAL_EXP (&dconst3_4) - 2);
1130
1131   if (flag_unsafe_math_optimizations
1132       && sqrtfn
1133       && optimize_function_for_speed_p (cfun)
1134       && REAL_VALUES_EQUAL (c, dconst3_4)
1135       && hw_sqrt_exists)
1136     {
1137       /* sqrt(x)  */
1138       sqrt_arg0 = build_and_insert_call (gsi, sqrtfn, arg0, &target, loc);
1139
1140       /* sqrt(sqrt(x))  */
1141       sqrt_sqrt = build_and_insert_call (gsi, sqrtfn, sqrt_arg0, &target, loc);
1142
1143       /* sqrt(x) * sqrt(sqrt(x))  */
1144       ssa_target = make_ssa_name (target, NULL);
1145       mult_stmt = gimple_build_assign_with_ops (MULT_EXPR, ssa_target,
1146                                                 sqrt_arg0, sqrt_sqrt);
1147       gimple_set_location (mult_stmt, loc);
1148       gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT);
1149
1150       return ssa_target;
1151     }
1152
1153   /* Optimize pow(x,1./3.) = cbrt(x).  This requires unsafe math
1154      optimizations since 1./3. is not exactly representable.  If x
1155      is negative and finite, the correct value of pow(x,1./3.) is
1156      a NaN with the "invalid" exception raised, because the value
1157      of 1./3. actually has an even denominator.  The correct value
1158      of cbrt(x) is a negative real value.  */
1159   cbrtfn = mathfn_built_in (type, BUILT_IN_CBRT);
1160   dconst1_3 = real_value_truncate (mode, dconst_third ());
1161
1162   if (flag_unsafe_math_optimizations
1163       && cbrtfn
1164       /* FIXME: The following line was originally
1165          && (tree_expr_nonnegative_p (arg0) || !HONOR_NANS (mode)),
1166          but since arg0 is a gimple value, the first predicate
1167          will always return false.  It needs to be replaced with a
1168          call to a similar gimple_val_nonnegative_p function to be
1169          added in gimple-fold.c.  */
1170       && !HONOR_NANS (mode)
1171       && REAL_VALUES_EQUAL (c, dconst1_3))
1172     return build_and_insert_call (gsi, cbrtfn, arg0, &target, loc);
1173
1174   /* Optimize pow(x,1./6.) = cbrt(sqrt(x)).  Don't do this optimization
1175      if we don't have a hardware sqrt insn.  */
1176   dconst1_6 = dconst1_3;
1177   SET_REAL_EXP (&dconst1_6, REAL_EXP (&dconst1_6) - 1);
1178
1179   if (flag_unsafe_math_optimizations
1180       && sqrtfn
1181       && cbrtfn
1182       /* FIXME: The following line was originally
1183          && (tree_expr_nonnegative_p (arg0) || !HONOR_NANS (mode)),
1184          but since arg0 is a gimple value, the first predicate
1185          will always return false.  It needs to be replaced with a
1186          call to a similar gimple_val_nonnegative_p function to be
1187          added in gimple-fold.c.  */
1188       && !HONOR_NANS (mode)
1189       && optimize_function_for_speed_p (cfun)
1190       && hw_sqrt_exists
1191       && REAL_VALUES_EQUAL (c, dconst1_6))
1192     {
1193       /* sqrt(x)  */
1194       sqrt_arg0 = build_and_insert_call (gsi, sqrtfn, arg0, &target, loc);
1195
1196       /* cbrt(sqrt(x))  */
1197       return build_and_insert_call (gsi, cbrtfn, sqrt_arg0, &target, loc);
1198     }
1199
1200   return NULL_TREE;
1201 }
1202
1203 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1204    on the SSA_NAME argument of each of them.  Also expand powi(x,n) into
1205    an optimal number of multiplies, when n is a constant.  */
1206
1207 static unsigned int
1208 execute_cse_sincos (void)
1209 {
1210   basic_block bb;
1211   bool cfg_changed = false;
1212
1213   calculate_dominance_info (CDI_DOMINATORS);
1214   memset (&sincos_stats, 0, sizeof (sincos_stats));
1215
1216   FOR_EACH_BB (bb)
1217     {
1218       gimple_stmt_iterator gsi;
1219
1220       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1221         {
1222           gimple stmt = gsi_stmt (gsi);
1223           tree fndecl;
1224
1225           if (is_gimple_call (stmt)
1226               && gimple_call_lhs (stmt)
1227               && (fndecl = gimple_call_fndecl (stmt))
1228               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
1229             {
1230               tree arg, arg0, arg1, result;
1231               HOST_WIDE_INT n;
1232               location_t loc;
1233
1234               switch (DECL_FUNCTION_CODE (fndecl))
1235                 {
1236                 CASE_FLT_FN (BUILT_IN_COS):
1237                 CASE_FLT_FN (BUILT_IN_SIN):
1238                 CASE_FLT_FN (BUILT_IN_CEXPI):
1239                   /* Make sure we have either sincos or cexp.  */
1240                   if (!TARGET_HAS_SINCOS && !TARGET_C99_FUNCTIONS)
1241                     break;
1242
1243                   arg = gimple_call_arg (stmt, 0);
1244                   if (TREE_CODE (arg) == SSA_NAME)
1245                     cfg_changed |= execute_cse_sincos_1 (arg);
1246                   break;
1247
1248                 CASE_FLT_FN (BUILT_IN_POW):
1249                   arg0 = gimple_call_arg (stmt, 0);
1250                   arg1 = gimple_call_arg (stmt, 1);
1251
1252                   loc = gimple_location (stmt);
1253                   result = gimple_expand_builtin_pow (&gsi, loc, arg0, arg1);
1254
1255                   if (result)
1256                     {
1257                       tree lhs = gimple_get_lhs (stmt);
1258                       gimple new_stmt = gimple_build_assign (lhs, result);
1259                       gimple_set_location (new_stmt, loc);
1260                       unlink_stmt_vdef (stmt);
1261                       gsi_replace (&gsi, new_stmt, true);
1262                     }
1263                   break;
1264
1265                 CASE_FLT_FN (BUILT_IN_POWI):
1266                   arg0 = gimple_call_arg (stmt, 0);
1267                   arg1 = gimple_call_arg (stmt, 1);
1268                   if (!host_integerp (arg1, 0))
1269                     break;
1270
1271                   n = TREE_INT_CST_LOW (arg1);
1272                   loc = gimple_location (stmt);
1273                   result = gimple_expand_builtin_powi (&gsi, loc, arg0, n);
1274
1275                   if (result)
1276                     {
1277                       tree lhs = gimple_get_lhs (stmt);
1278                       gimple new_stmt = gimple_build_assign (lhs, result);
1279                       gimple_set_location (new_stmt, loc);
1280                       unlink_stmt_vdef (stmt);
1281                       gsi_replace (&gsi, new_stmt, true);
1282                     }
1283                   break;
1284
1285                 default:;
1286                 }
1287             }
1288         }
1289     }
1290
1291   statistics_counter_event (cfun, "sincos statements inserted",
1292                             sincos_stats.inserted);
1293
1294   free_dominance_info (CDI_DOMINATORS);
1295   return cfg_changed ? TODO_cleanup_cfg : 0;
1296 }
1297
1298 static bool
1299 gate_cse_sincos (void)
1300 {
1301   /* We no longer require either sincos or cexp, since powi expansion
1302      piggybacks on this pass.  */
1303   return optimize;
1304 }
1305
1306 struct gimple_opt_pass pass_cse_sincos =
1307 {
1308  {
1309   GIMPLE_PASS,
1310   "sincos",                             /* name */
1311   gate_cse_sincos,                      /* gate */
1312   execute_cse_sincos,                   /* execute */
1313   NULL,                                 /* sub */
1314   NULL,                                 /* next */
1315   0,                                    /* static_pass_number */
1316   TV_NONE,                              /* tv_id */
1317   PROP_ssa,                             /* properties_required */
1318   0,                                    /* properties_provided */
1319   0,                                    /* properties_destroyed */
1320   0,                                    /* todo_flags_start */
1321   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
1322     | TODO_verify_stmts                 /* todo_flags_finish */
1323  }
1324 };
1325
1326 /* A symbolic number is used to detect byte permutation and selection
1327    patterns.  Therefore the field N contains an artificial number
1328    consisting of byte size markers:
1329
1330    0    - byte has the value 0
1331    1..size - byte contains the content of the byte
1332    number indexed with that value minus one  */
1333
1334 struct symbolic_number {
1335   unsigned HOST_WIDEST_INT n;
1336   int size;
1337 };
1338
1339 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1340    number N.  Return false if the requested operation is not permitted
1341    on a symbolic number.  */
1342
1343 static inline bool
1344 do_shift_rotate (enum tree_code code,
1345                  struct symbolic_number *n,
1346                  int count)
1347 {
1348   if (count % 8 != 0)
1349     return false;
1350
1351   /* Zero out the extra bits of N in order to avoid them being shifted
1352      into the significant bits.  */
1353   if (n->size < (int)sizeof (HOST_WIDEST_INT))
1354     n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
1355
1356   switch (code)
1357     {
1358     case LSHIFT_EXPR:
1359       n->n <<= count;
1360       break;
1361     case RSHIFT_EXPR:
1362       n->n >>= count;
1363       break;
1364     case LROTATE_EXPR:
1365       n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
1366       break;
1367     case RROTATE_EXPR:
1368       n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
1369       break;
1370     default:
1371       return false;
1372     }
1373   return true;
1374 }
1375
1376 /* Perform sanity checking for the symbolic number N and the gimple
1377    statement STMT.  */
1378
1379 static inline bool
1380 verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
1381 {
1382   tree lhs_type;
1383
1384   lhs_type = gimple_expr_type (stmt);
1385
1386   if (TREE_CODE (lhs_type) != INTEGER_TYPE)
1387     return false;
1388
1389   if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
1390     return false;
1391
1392   return true;
1393 }
1394
1395 /* find_bswap_1 invokes itself recursively with N and tries to perform
1396    the operation given by the rhs of STMT on the result.  If the
1397    operation could successfully be executed the function returns the
1398    tree expression of the source operand and NULL otherwise.  */
1399
1400 static tree
1401 find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
1402 {
1403   enum tree_code code;
1404   tree rhs1, rhs2 = NULL;
1405   gimple rhs1_stmt, rhs2_stmt;
1406   tree source_expr1;
1407   enum gimple_rhs_class rhs_class;
1408
1409   if (!limit || !is_gimple_assign (stmt))
1410     return NULL_TREE;
1411
1412   rhs1 = gimple_assign_rhs1 (stmt);
1413
1414   if (TREE_CODE (rhs1) != SSA_NAME)
1415     return NULL_TREE;
1416
1417   code = gimple_assign_rhs_code (stmt);
1418   rhs_class = gimple_assign_rhs_class (stmt);
1419   rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
1420
1421   if (rhs_class == GIMPLE_BINARY_RHS)
1422     rhs2 = gimple_assign_rhs2 (stmt);
1423
1424   /* Handle unary rhs and binary rhs with integer constants as second
1425      operand.  */
1426
1427   if (rhs_class == GIMPLE_UNARY_RHS
1428       || (rhs_class == GIMPLE_BINARY_RHS
1429           && TREE_CODE (rhs2) == INTEGER_CST))
1430     {
1431       if (code != BIT_AND_EXPR
1432           && code != LSHIFT_EXPR
1433           && code != RSHIFT_EXPR
1434           && code != LROTATE_EXPR
1435           && code != RROTATE_EXPR
1436           && code != NOP_EXPR
1437           && code != CONVERT_EXPR)
1438         return NULL_TREE;
1439
1440       source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
1441
1442       /* If find_bswap_1 returned NULL STMT is a leaf node and we have
1443          to initialize the symbolic number.  */
1444       if (!source_expr1)
1445         {
1446           /* Set up the symbolic number N by setting each byte to a
1447              value between 1 and the byte size of rhs1.  The highest
1448              order byte is set to n->size and the lowest order
1449              byte to 1.  */
1450           n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
1451           if (n->size % BITS_PER_UNIT != 0)
1452             return NULL_TREE;
1453           n->size /= BITS_PER_UNIT;
1454           n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
1455                   (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201);
1456
1457           if (n->size < (int)sizeof (HOST_WIDEST_INT))
1458             n->n &= ((unsigned HOST_WIDEST_INT)1 <<
1459                      (n->size * BITS_PER_UNIT)) - 1;
1460
1461           source_expr1 = rhs1;
1462         }
1463
1464       switch (code)
1465         {
1466         case BIT_AND_EXPR:
1467           {
1468             int i;
1469             unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
1470             unsigned HOST_WIDEST_INT tmp = val;
1471
1472             /* Only constants masking full bytes are allowed.  */
1473             for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
1474               if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
1475                 return NULL_TREE;
1476
1477             n->n &= val;
1478           }
1479           break;
1480         case LSHIFT_EXPR:
1481         case RSHIFT_EXPR:
1482         case LROTATE_EXPR:
1483         case RROTATE_EXPR:
1484           if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
1485             return NULL_TREE;
1486           break;
1487         CASE_CONVERT:
1488           {
1489             int type_size;
1490
1491             type_size = TYPE_PRECISION (gimple_expr_type (stmt));
1492             if (type_size % BITS_PER_UNIT != 0)
1493               return NULL_TREE;
1494
1495             if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
1496               {
1497                 /* If STMT casts to a smaller type mask out the bits not
1498                    belonging to the target type.  */
1499                 n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
1500               }
1501             n->size = type_size / BITS_PER_UNIT;
1502           }
1503           break;
1504         default:
1505           return NULL_TREE;
1506         };
1507       return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
1508     }
1509
1510   /* Handle binary rhs.  */
1511
1512   if (rhs_class == GIMPLE_BINARY_RHS)
1513     {
1514       struct symbolic_number n1, n2;
1515       tree source_expr2;
1516
1517       if (code != BIT_IOR_EXPR)
1518         return NULL_TREE;
1519
1520       if (TREE_CODE (rhs2) != SSA_NAME)
1521         return NULL_TREE;
1522
1523       rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
1524
1525       switch (code)
1526         {
1527         case BIT_IOR_EXPR:
1528           source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
1529
1530           if (!source_expr1)
1531             return NULL_TREE;
1532
1533           source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
1534
1535           if (source_expr1 != source_expr2
1536               || n1.size != n2.size)
1537             return NULL_TREE;
1538
1539           n->size = n1.size;
1540           n->n = n1.n | n2.n;
1541
1542           if (!verify_symbolic_number_p (n, stmt))
1543             return NULL_TREE;
1544
1545           break;
1546         default:
1547           return NULL_TREE;
1548         }
1549       return source_expr1;
1550     }
1551   return NULL_TREE;
1552 }
1553
1554 /* Check if STMT completes a bswap implementation consisting of ORs,
1555    SHIFTs and ANDs.  Return the source tree expression on which the
1556    byte swap is performed and NULL if no bswap was found.  */
1557
1558 static tree
1559 find_bswap (gimple stmt)
1560 {
1561 /* The number which the find_bswap result should match in order to
1562    have a full byte swap.  The number is shifted to the left according
1563    to the size of the symbolic number before using it.  */
1564   unsigned HOST_WIDEST_INT cmp =
1565     sizeof (HOST_WIDEST_INT) < 8 ? 0 :
1566     (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708;
1567
1568   struct symbolic_number n;
1569   tree source_expr;
1570
1571   /* The last parameter determines the depth search limit.  It usually
1572      correlates directly to the number of bytes to be touched.  We
1573      increase that number by one here in order to also cover signed ->
1574      unsigned conversions of the src operand as can be seen in
1575      libgcc.  */
1576   source_expr =  find_bswap_1 (stmt, &n,
1577                                TREE_INT_CST_LOW (
1578                                  TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
1579
1580   if (!source_expr)
1581     return NULL_TREE;
1582
1583   /* Zero out the extra bits of N and CMP.  */
1584   if (n.size < (int)sizeof (HOST_WIDEST_INT))
1585     {
1586       unsigned HOST_WIDEST_INT mask =
1587         ((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
1588
1589       n.n &= mask;
1590       cmp >>= (sizeof (HOST_WIDEST_INT) - n.size) * BITS_PER_UNIT;
1591     }
1592
1593   /* A complete byte swap should make the symbolic number to start
1594      with the largest digit in the highest order byte.  */
1595   if (cmp != n.n)
1596     return NULL_TREE;
1597
1598   return source_expr;
1599 }
1600
1601 /* Find manual byte swap implementations and turn them into a bswap
1602    builtin invokation.  */
1603
1604 static unsigned int
1605 execute_optimize_bswap (void)
1606 {
1607   basic_block bb;
1608   bool bswap32_p, bswap64_p;
1609   bool changed = false;
1610   tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1611
1612   if (BITS_PER_UNIT != 8)
1613     return 0;
1614
1615   if (sizeof (HOST_WIDEST_INT) < 8)
1616     return 0;
1617
1618   bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
1619                && optab_handler (bswap_optab, SImode) != CODE_FOR_nothing);
1620   bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
1621                && (optab_handler (bswap_optab, DImode) != CODE_FOR_nothing
1622                    || (bswap32_p && word_mode == SImode)));
1623
1624   if (!bswap32_p && !bswap64_p)
1625     return 0;
1626
1627   /* Determine the argument type of the builtins.  The code later on
1628      assumes that the return and argument type are the same.  */
1629   if (bswap32_p)
1630     {
1631       tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
1632       bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1633     }
1634
1635   if (bswap64_p)
1636     {
1637       tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
1638       bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1639     }
1640
1641   memset (&bswap_stats, 0, sizeof (bswap_stats));
1642
1643   FOR_EACH_BB (bb)
1644     {
1645       gimple_stmt_iterator gsi;
1646
1647       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1648         {
1649           gimple stmt = gsi_stmt (gsi);
1650           tree bswap_src, bswap_type;
1651           tree bswap_tmp;
1652           tree fndecl = NULL_TREE;
1653           int type_size;
1654           gimple call;
1655
1656           if (!is_gimple_assign (stmt)
1657               || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
1658             continue;
1659
1660           type_size = TYPE_PRECISION (gimple_expr_type (stmt));
1661
1662           switch (type_size)
1663             {
1664             case 32:
1665               if (bswap32_p)
1666                 {
1667                   fndecl = built_in_decls[BUILT_IN_BSWAP32];
1668                   bswap_type = bswap32_type;
1669                 }
1670               break;
1671             case 64:
1672               if (bswap64_p)
1673                 {
1674                   fndecl = built_in_decls[BUILT_IN_BSWAP64];
1675                   bswap_type = bswap64_type;
1676                 }
1677               break;
1678             default:
1679               continue;
1680             }
1681
1682           if (!fndecl)
1683             continue;
1684
1685           bswap_src = find_bswap (stmt);
1686
1687           if (!bswap_src)
1688             continue;
1689
1690           changed = true;
1691           if (type_size == 32)
1692             bswap_stats.found_32bit++;
1693           else
1694             bswap_stats.found_64bit++;
1695
1696           bswap_tmp = bswap_src;
1697
1698           /* Convert the src expression if necessary.  */
1699           if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1700             {
1701               gimple convert_stmt;
1702
1703               bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
1704               add_referenced_var (bswap_tmp);
1705               bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1706
1707               convert_stmt = gimple_build_assign_with_ops (
1708                                CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
1709               gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
1710             }
1711
1712           call = gimple_build_call (fndecl, 1, bswap_tmp);
1713
1714           bswap_tmp = gimple_assign_lhs (stmt);
1715
1716           /* Convert the result if necessary.  */
1717           if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1718             {
1719               gimple convert_stmt;
1720
1721               bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
1722               add_referenced_var (bswap_tmp);
1723               bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1724               convert_stmt = gimple_build_assign_with_ops (
1725                                CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
1726               gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
1727             }
1728
1729           gimple_call_set_lhs (call, bswap_tmp);
1730
1731           if (dump_file)
1732             {
1733               fprintf (dump_file, "%d bit bswap implementation found at: ",
1734                        (int)type_size);
1735               print_gimple_stmt (dump_file, stmt, 0, 0);
1736             }
1737
1738           gsi_insert_after (&gsi, call, GSI_SAME_STMT);
1739           gsi_remove (&gsi, true);
1740         }
1741     }
1742
1743   statistics_counter_event (cfun, "32-bit bswap implementations found",
1744                             bswap_stats.found_32bit);
1745   statistics_counter_event (cfun, "64-bit bswap implementations found",
1746                             bswap_stats.found_64bit);
1747
1748   return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
1749           | TODO_verify_stmts : 0);
1750 }
1751
1752 static bool
1753 gate_optimize_bswap (void)
1754 {
1755   return flag_expensive_optimizations && optimize;
1756 }
1757
1758 struct gimple_opt_pass pass_optimize_bswap =
1759 {
1760  {
1761   GIMPLE_PASS,
1762   "bswap",                              /* name */
1763   gate_optimize_bswap,                  /* gate */
1764   execute_optimize_bswap,               /* execute */
1765   NULL,                                 /* sub */
1766   NULL,                                 /* next */
1767   0,                                    /* static_pass_number */
1768   TV_NONE,                              /* tv_id */
1769   PROP_ssa,                             /* properties_required */
1770   0,                                    /* properties_provided */
1771   0,                                    /* properties_destroyed */
1772   0,                                    /* todo_flags_start */
1773   0                                     /* todo_flags_finish */
1774  }
1775 };
1776
1777 /* Return true if RHS is a suitable operand for a widening multiplication.
1778    There are two cases:
1779
1780      - RHS makes some value twice as wide.  Store that value in *NEW_RHS_OUT
1781        if so, and store its type in *TYPE_OUT.
1782
1783      - RHS is an integer constant.  Store that value in *NEW_RHS_OUT if so,
1784        but leave *TYPE_OUT untouched.  */
1785
1786 static bool
1787 is_widening_mult_rhs_p (tree rhs, tree *type_out, tree *new_rhs_out)
1788 {
1789   gimple stmt;
1790   tree type, type1, rhs1;
1791   enum tree_code rhs_code;
1792
1793   if (TREE_CODE (rhs) == SSA_NAME)
1794     {
1795       type = TREE_TYPE (rhs);
1796       stmt = SSA_NAME_DEF_STMT (rhs);
1797       if (!is_gimple_assign (stmt))
1798         return false;
1799
1800       rhs_code = gimple_assign_rhs_code (stmt);
1801       if (TREE_CODE (type) == INTEGER_TYPE
1802           ? !CONVERT_EXPR_CODE_P (rhs_code)
1803           : rhs_code != FIXED_CONVERT_EXPR)
1804         return false;
1805
1806       rhs1 = gimple_assign_rhs1 (stmt);
1807       type1 = TREE_TYPE (rhs1);
1808       if (TREE_CODE (type1) != TREE_CODE (type)
1809           || TYPE_PRECISION (type1) * 2 != TYPE_PRECISION (type))
1810         return false;
1811
1812       *new_rhs_out = rhs1;
1813       *type_out = type1;
1814       return true;
1815     }
1816
1817   if (TREE_CODE (rhs) == INTEGER_CST)
1818     {
1819       *new_rhs_out = rhs;
1820       *type_out = NULL;
1821       return true;
1822     }
1823
1824   return false;
1825 }
1826
1827 /* Return true if STMT performs a widening multiplication.  If so,
1828    store the unwidened types of the operands in *TYPE1_OUT and *TYPE2_OUT
1829    respectively.  Also fill *RHS1_OUT and *RHS2_OUT such that converting
1830    those operands to types *TYPE1_OUT and *TYPE2_OUT would give the
1831    operands of the multiplication.  */
1832
1833 static bool
1834 is_widening_mult_p (gimple stmt,
1835                     tree *type1_out, tree *rhs1_out,
1836                     tree *type2_out, tree *rhs2_out)
1837 {
1838   tree type;
1839
1840   type = TREE_TYPE (gimple_assign_lhs (stmt));
1841   if (TREE_CODE (type) != INTEGER_TYPE
1842       && TREE_CODE (type) != FIXED_POINT_TYPE)
1843     return false;
1844
1845   if (!is_widening_mult_rhs_p (gimple_assign_rhs1 (stmt), type1_out, rhs1_out))
1846     return false;
1847
1848   if (!is_widening_mult_rhs_p (gimple_assign_rhs2 (stmt), type2_out, rhs2_out))
1849     return false;
1850
1851   if (*type1_out == NULL)
1852     {
1853       if (*type2_out == NULL || !int_fits_type_p (*rhs1_out, *type2_out))
1854         return false;
1855       *type1_out = *type2_out;
1856     }
1857
1858   if (*type2_out == NULL)
1859     {
1860       if (!int_fits_type_p (*rhs2_out, *type1_out))
1861         return false;
1862       *type2_out = *type1_out;
1863     }
1864
1865   return true;
1866 }
1867
1868 /* Process a single gimple statement STMT, which has a MULT_EXPR as
1869    its rhs, and try to convert it into a WIDEN_MULT_EXPR.  The return
1870    value is true iff we converted the statement.  */
1871
1872 static bool
1873 convert_mult_to_widen (gimple stmt)
1874 {
1875   tree lhs, rhs1, rhs2, type, type1, type2;
1876   enum insn_code handler;
1877
1878   lhs = gimple_assign_lhs (stmt);
1879   type = TREE_TYPE (lhs);
1880   if (TREE_CODE (type) != INTEGER_TYPE)
1881     return false;
1882
1883   if (!is_widening_mult_p (stmt, &type1, &rhs1, &type2, &rhs2))
1884     return false;
1885
1886   if (TYPE_UNSIGNED (type1) && TYPE_UNSIGNED (type2))
1887     handler = optab_handler (umul_widen_optab, TYPE_MODE (type));
1888   else if (!TYPE_UNSIGNED (type1) && !TYPE_UNSIGNED (type2))
1889     handler = optab_handler (smul_widen_optab, TYPE_MODE (type));
1890   else
1891     handler = optab_handler (usmul_widen_optab, TYPE_MODE (type));
1892
1893   if (handler == CODE_FOR_nothing)
1894     return false;
1895
1896   gimple_assign_set_rhs1 (stmt, fold_convert (type1, rhs1));
1897   gimple_assign_set_rhs2 (stmt, fold_convert (type2, rhs2));
1898   gimple_assign_set_rhs_code (stmt, WIDEN_MULT_EXPR);
1899   update_stmt (stmt);
1900   widen_mul_stats.widen_mults_inserted++;
1901   return true;
1902 }
1903
1904 /* Process a single gimple statement STMT, which is found at the
1905    iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
1906    rhs (given by CODE), and try to convert it into a
1907    WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR.  The return value
1908    is true iff we converted the statement.  */
1909
1910 static bool
1911 convert_plusminus_to_widen (gimple_stmt_iterator *gsi, gimple stmt,
1912                             enum tree_code code)
1913 {
1914   gimple rhs1_stmt = NULL, rhs2_stmt = NULL;
1915   tree type, type1, type2;
1916   tree lhs, rhs1, rhs2, mult_rhs1, mult_rhs2, add_rhs;
1917   enum tree_code rhs1_code = ERROR_MARK, rhs2_code = ERROR_MARK;
1918   optab this_optab;
1919   enum tree_code wmult_code;
1920
1921   lhs = gimple_assign_lhs (stmt);
1922   type = TREE_TYPE (lhs);
1923   if (TREE_CODE (type) != INTEGER_TYPE
1924       && TREE_CODE (type) != FIXED_POINT_TYPE)
1925     return false;
1926
1927   if (code == MINUS_EXPR)
1928     wmult_code = WIDEN_MULT_MINUS_EXPR;
1929   else
1930     wmult_code = WIDEN_MULT_PLUS_EXPR;
1931
1932   rhs1 = gimple_assign_rhs1 (stmt);
1933   rhs2 = gimple_assign_rhs2 (stmt);
1934
1935   if (TREE_CODE (rhs1) == SSA_NAME)
1936     {
1937       rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
1938       if (is_gimple_assign (rhs1_stmt))
1939         rhs1_code = gimple_assign_rhs_code (rhs1_stmt);
1940     }
1941   else
1942     return false;
1943
1944   if (TREE_CODE (rhs2) == SSA_NAME)
1945     {
1946       rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
1947       if (is_gimple_assign (rhs2_stmt))
1948         rhs2_code = gimple_assign_rhs_code (rhs2_stmt);
1949     }
1950   else
1951     return false;
1952
1953   if (code == PLUS_EXPR && rhs1_code == MULT_EXPR)
1954     {
1955       if (!is_widening_mult_p (rhs1_stmt, &type1, &mult_rhs1,
1956                                &type2, &mult_rhs2))
1957         return false;
1958       add_rhs = rhs2;
1959     }
1960   else if (rhs2_code == MULT_EXPR)
1961     {
1962       if (!is_widening_mult_p (rhs2_stmt, &type1, &mult_rhs1,
1963                                &type2, &mult_rhs2))
1964         return false;
1965       add_rhs = rhs1;
1966     }
1967   else if (code == PLUS_EXPR && rhs1_code == WIDEN_MULT_EXPR)
1968     {
1969       mult_rhs1 = gimple_assign_rhs1 (rhs1_stmt);
1970       mult_rhs2 = gimple_assign_rhs2 (rhs1_stmt);
1971       type1 = TREE_TYPE (mult_rhs1);
1972       type2 = TREE_TYPE (mult_rhs2);
1973       add_rhs = rhs2;
1974     }
1975   else if (rhs2_code == WIDEN_MULT_EXPR)
1976     {
1977       mult_rhs1 = gimple_assign_rhs1 (rhs2_stmt);
1978       mult_rhs2 = gimple_assign_rhs2 (rhs2_stmt);
1979       type1 = TREE_TYPE (mult_rhs1);
1980       type2 = TREE_TYPE (mult_rhs2);
1981       add_rhs = rhs1;
1982     }
1983   else
1984     return false;
1985
1986   if (TYPE_UNSIGNED (type1) != TYPE_UNSIGNED (type2))
1987     return false;
1988
1989   /* Verify that the machine can perform a widening multiply
1990      accumulate in this mode/signedness combination, otherwise
1991      this transformation is likely to pessimize code.  */
1992   this_optab = optab_for_tree_code (wmult_code, type1, optab_default);
1993   if (optab_handler (this_optab, TYPE_MODE (type)) == CODE_FOR_nothing)
1994     return false;
1995
1996   /* ??? May need some type verification here?  */
1997
1998   gimple_assign_set_rhs_with_ops_1 (gsi, wmult_code,
1999                                     fold_convert (type1, mult_rhs1),
2000                                     fold_convert (type2, mult_rhs2),
2001                                     add_rhs);
2002   update_stmt (gsi_stmt (*gsi));
2003   widen_mul_stats.maccs_inserted++;
2004   return true;
2005 }
2006
2007 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2008    with uses in additions and subtractions to form fused multiply-add
2009    operations.  Returns true if successful and MUL_STMT should be removed.  */
2010
2011 static bool
2012 convert_mult_to_fma (gimple mul_stmt, tree op1, tree op2)
2013 {
2014   tree mul_result = gimple_get_lhs (mul_stmt);
2015   tree type = TREE_TYPE (mul_result);
2016   gimple use_stmt, neguse_stmt, fma_stmt;
2017   use_operand_p use_p;
2018   imm_use_iterator imm_iter;
2019
2020   if (FLOAT_TYPE_P (type)
2021       && flag_fp_contract_mode == FP_CONTRACT_OFF)
2022     return false;
2023
2024   /* We don't want to do bitfield reduction ops.  */
2025   if (INTEGRAL_TYPE_P (type)
2026       && (TYPE_PRECISION (type)
2027           != GET_MODE_PRECISION (TYPE_MODE (type))))
2028     return false;
2029
2030   /* If the target doesn't support it, don't generate it.  We assume that
2031      if fma isn't available then fms, fnma or fnms are not either.  */
2032   if (optab_handler (fma_optab, TYPE_MODE (type)) == CODE_FOR_nothing)
2033     return false;
2034
2035   /* Make sure that the multiplication statement becomes dead after
2036      the transformation, thus that all uses are transformed to FMAs.
2037      This means we assume that an FMA operation has the same cost
2038      as an addition.  */
2039   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, mul_result)
2040     {
2041       enum tree_code use_code;
2042       tree result = mul_result;
2043       bool negate_p = false;
2044
2045       use_stmt = USE_STMT (use_p);
2046
2047       if (is_gimple_debug (use_stmt))
2048         continue;
2049
2050       /* For now restrict this operations to single basic blocks.  In theory
2051          we would want to support sinking the multiplication in
2052          m = a*b;
2053          if ()
2054            ma = m + c;
2055          else
2056            d = m;
2057          to form a fma in the then block and sink the multiplication to the
2058          else block.  */
2059       if (gimple_bb (use_stmt) != gimple_bb (mul_stmt))
2060         return false;
2061
2062       if (!is_gimple_assign (use_stmt))
2063         return false;
2064
2065       use_code = gimple_assign_rhs_code (use_stmt);
2066
2067       /* A negate on the multiplication leads to FNMA.  */
2068       if (use_code == NEGATE_EXPR)
2069         {
2070           ssa_op_iter iter;
2071           tree use;
2072
2073           result = gimple_assign_lhs (use_stmt);
2074
2075           /* Make sure the negate statement becomes dead with this
2076              single transformation.  */
2077           if (!single_imm_use (gimple_assign_lhs (use_stmt),
2078                                &use_p, &neguse_stmt))
2079             return false;
2080
2081           /* Make sure the multiplication isn't also used on that stmt.  */
2082           FOR_EACH_SSA_TREE_OPERAND (use, neguse_stmt, iter, SSA_OP_USE)
2083             if (use == mul_result)
2084               return false;
2085
2086           /* Re-validate.  */
2087           use_stmt = neguse_stmt;
2088           if (gimple_bb (use_stmt) != gimple_bb (mul_stmt))
2089             return false;
2090           if (!is_gimple_assign (use_stmt))
2091             return false;
2092
2093           use_code = gimple_assign_rhs_code (use_stmt);
2094           negate_p = true;
2095         }
2096
2097       switch (use_code)
2098         {
2099         case MINUS_EXPR:
2100           if (gimple_assign_rhs2 (use_stmt) == result)
2101             negate_p = !negate_p;
2102           break;
2103         case PLUS_EXPR:
2104           break;
2105         default:
2106           /* FMA can only be formed from PLUS and MINUS.  */
2107           return false;
2108         }
2109
2110       /* We can't handle a * b + a * b.  */
2111       if (gimple_assign_rhs1 (use_stmt) == gimple_assign_rhs2 (use_stmt))
2112         return false;
2113
2114       /* While it is possible to validate whether or not the exact form
2115          that we've recognized is available in the backend, the assumption
2116          is that the transformation is never a loss.  For instance, suppose
2117          the target only has the plain FMA pattern available.  Consider
2118          a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
2119          is still two operations.  Consider -(a*b)-c -> fma(-a,b,-c): we
2120          still have 3 operations, but in the FMA form the two NEGs are
2121          independant and could be run in parallel.  */
2122     }
2123
2124   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, mul_result)
2125     {
2126       gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2127       enum tree_code use_code;
2128       tree addop, mulop1 = op1, result = mul_result;
2129       bool negate_p = false;
2130
2131       if (is_gimple_debug (use_stmt))
2132         continue;
2133
2134       use_code = gimple_assign_rhs_code (use_stmt);
2135       if (use_code == NEGATE_EXPR)
2136         {
2137           result = gimple_assign_lhs (use_stmt);
2138           single_imm_use (gimple_assign_lhs (use_stmt), &use_p, &neguse_stmt);
2139           gsi_remove (&gsi, true);
2140           release_defs (use_stmt);
2141
2142           use_stmt = neguse_stmt;
2143           gsi = gsi_for_stmt (use_stmt);
2144           use_code = gimple_assign_rhs_code (use_stmt);
2145           negate_p = true;
2146         }
2147
2148       if (gimple_assign_rhs1 (use_stmt) == result)
2149         {
2150           addop = gimple_assign_rhs2 (use_stmt);
2151           /* a * b - c -> a * b + (-c)  */
2152           if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
2153             addop = force_gimple_operand_gsi (&gsi,
2154                                               build1 (NEGATE_EXPR,
2155                                                       type, addop),
2156                                               true, NULL_TREE, true,
2157                                               GSI_SAME_STMT);
2158         }
2159       else
2160         {
2161           addop = gimple_assign_rhs1 (use_stmt);
2162           /* a - b * c -> (-b) * c + a */
2163           if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
2164             negate_p = !negate_p;
2165         }
2166
2167       if (negate_p)
2168         mulop1 = force_gimple_operand_gsi (&gsi,
2169                                            build1 (NEGATE_EXPR,
2170                                                    type, mulop1),
2171                                            true, NULL_TREE, true,
2172                                            GSI_SAME_STMT);
2173
2174       fma_stmt = gimple_build_assign_with_ops3 (FMA_EXPR,
2175                                                 gimple_assign_lhs (use_stmt),
2176                                                 mulop1, op2,
2177                                                 addop);
2178       gsi_replace (&gsi, fma_stmt, true);
2179       widen_mul_stats.fmas_inserted++;
2180     }
2181
2182   return true;
2183 }
2184
2185 /* Find integer multiplications where the operands are extended from
2186    smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
2187    where appropriate.  */
2188
2189 static unsigned int
2190 execute_optimize_widening_mul (void)
2191 {
2192   basic_block bb;
2193   bool cfg_changed = false;
2194
2195   memset (&widen_mul_stats, 0, sizeof (widen_mul_stats));
2196
2197   FOR_EACH_BB (bb)
2198     {
2199       gimple_stmt_iterator gsi;
2200
2201       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
2202         {
2203           gimple stmt = gsi_stmt (gsi);
2204           enum tree_code code;
2205
2206           if (is_gimple_assign (stmt))
2207             {
2208               code = gimple_assign_rhs_code (stmt);
2209               switch (code)
2210                 {
2211                 case MULT_EXPR:
2212                   if (!convert_mult_to_widen (stmt)
2213                       && convert_mult_to_fma (stmt,
2214                                               gimple_assign_rhs1 (stmt),
2215                                               gimple_assign_rhs2 (stmt)))
2216                     {
2217                       gsi_remove (&gsi, true);
2218                       release_defs (stmt);
2219                       continue;
2220                     }
2221                   break;
2222
2223                 case PLUS_EXPR:
2224                 case MINUS_EXPR:
2225                   convert_plusminus_to_widen (&gsi, stmt, code);
2226                   break;
2227
2228                 default:;
2229                 }
2230             }
2231           else if (is_gimple_call (stmt)
2232                    && gimple_call_lhs (stmt))
2233             {
2234               tree fndecl = gimple_call_fndecl (stmt);
2235               if (fndecl
2236                   && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
2237                 {
2238                   switch (DECL_FUNCTION_CODE (fndecl))
2239                     {
2240                       case BUILT_IN_POWF:
2241                       case BUILT_IN_POW:
2242                       case BUILT_IN_POWL:
2243                         if (TREE_CODE (gimple_call_arg (stmt, 1)) == REAL_CST
2244                             && REAL_VALUES_EQUAL
2245                                  (TREE_REAL_CST (gimple_call_arg (stmt, 1)),
2246                                   dconst2)
2247                             && convert_mult_to_fma (stmt,
2248                                                     gimple_call_arg (stmt, 0),
2249                                                     gimple_call_arg (stmt, 0)))
2250                           {
2251                             unlink_stmt_vdef (stmt);
2252                             gsi_remove (&gsi, true);
2253                             release_defs (stmt);
2254                             if (gimple_purge_dead_eh_edges (bb))
2255                               cfg_changed = true;
2256                             continue;
2257                           }
2258                           break;
2259
2260                       default:;
2261                     }
2262                 }
2263             }
2264           gsi_next (&gsi);
2265         }
2266     }
2267
2268   statistics_counter_event (cfun, "widening multiplications inserted",
2269                             widen_mul_stats.widen_mults_inserted);
2270   statistics_counter_event (cfun, "widening maccs inserted",
2271                             widen_mul_stats.maccs_inserted);
2272   statistics_counter_event (cfun, "fused multiply-adds inserted",
2273                             widen_mul_stats.fmas_inserted);
2274
2275   return cfg_changed ? TODO_cleanup_cfg : 0;
2276 }
2277
2278 static bool
2279 gate_optimize_widening_mul (void)
2280 {
2281   return flag_expensive_optimizations && optimize;
2282 }
2283
2284 struct gimple_opt_pass pass_optimize_widening_mul =
2285 {
2286  {
2287   GIMPLE_PASS,
2288   "widening_mul",                       /* name */
2289   gate_optimize_widening_mul,           /* gate */
2290   execute_optimize_widening_mul,        /* execute */
2291   NULL,                                 /* sub */
2292   NULL,                                 /* next */
2293   0,                                    /* static_pass_number */
2294   TV_NONE,                              /* tv_id */
2295   PROP_ssa,                             /* properties_required */
2296   0,                                    /* properties_provided */
2297   0,                                    /* properties_destroyed */
2298   0,                                    /* todo_flags_start */
2299   TODO_verify_ssa
2300   | TODO_verify_stmts
2301   | TODO_dump_func
2302   | TODO_update_ssa                     /* todo_flags_finish */
2303  }
2304 };