gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  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 "real.h"
  96 #include "timevar.h"
  97 #include "tree-pass.h"
  98 #include "alloc-pool.h"
  99 #include "basic-block.h"
 100 #include "target.h"
 101
 102
 103 /* This structure represents one basic block that either computes a
 104    division, or is a common dominator for basic block that compute a
 105    division.  */
 106 struct occurrence {
 107   /* The basic block represented by this structure.  */
 108   basic_block bb;
 109
 110   /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
 111      inserted in BB.  */
 112   tree recip_def;
 113
 114   /* If non-NULL, the GIMPLE_MODIFY_STMT for a reciprocal computation that
 115      was inserted in BB.  */
 116   tree recip_def_stmt;
 117
 118   /* Pointer to a list of "struct occurrence"s for blocks dominated
 119      by BB.  */
 120   struct occurrence *children;
 121
 122   /* Pointer to the next "struct occurrence"s in the list of blocks
 123      sharing a common dominator.  */
 124   struct occurrence *next;
 125
 126   /* The number of divisions that are in BB before compute_merit.  The
 127      number of divisions that are in BB or post-dominate it after
 128      compute_merit.  */
 129   int num_divisions;
 130
 131   /* True if the basic block has a division, false if it is a common
 132      dominator for basic blocks that do.  If it is false and trapping
 133      math is active, BB is not a candidate for inserting a reciprocal.  */
 134   bool bb_has_division;
 135 };
 136
 137
 138 /* The instance of "struct occurrence" representing the highest
 139    interesting block in the dominator tree.  */
 140 static struct occurrence *occ_head;
 141
 142 /* Allocation pool for getting instances of "struct occurrence".  */
 143 static alloc_pool occ_pool;
 144
 145
 146
 147 /* Allocate and return a new struct occurrence for basic block BB, and
 148    whose children list is headed by CHILDREN.  */
 149 static struct occurrence *
 150 occ_new (basic_block bb, struct occurrence *children)
 151 {
 152   struct occurrence *occ;
 153
 154   bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
 155   memset (occ, 0, sizeof (struct occurrence));
 156
 157   occ->bb = bb;
 158   occ->children = children;
 159   return occ;
 160 }
 161
 162
 163 /* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
 164    list of "struct occurrence"s, one per basic block, having IDOM as
 165    their common dominator.
 166
 167    We try to insert NEW_OCC as deep as possible in the tree, and we also
 168    insert any other block that is a common dominator for BB and one
 169    block already in the tree.  */
 170
 171 static void
 172 insert_bb (struct occurrence *new_occ, basic_block idom,
 173            struct occurrence **p_head)
 174 {
 175   struct occurrence *occ, **p_occ;
 176
 177   for (p_occ = p_head; (occ = *p_occ) != NULL; )
 178     {
 179       basic_block bb = new_occ->bb, occ_bb = occ->bb;
 180       basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
 181       if (dom == bb)
 182         {
 183           /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
 184              from its list.  */
 185           *p_occ = occ->next;
 186           occ->next = new_occ->children;
 187           new_occ->children = occ;
 188
 189           /* Try the next block (it may as well be dominated by BB).  */
 190         }
 191
 192       else if (dom == occ_bb)
 193         {
 194           /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
 195           insert_bb (new_occ, dom, &occ->children);
 196           return;
 197         }
 198
 199       else if (dom != idom)
 200         {
 201           gcc_assert (!dom->aux);
 202
 203           /* There is a dominator between IDOM and BB, add it and make
 204              two children out of NEW_OCC and OCC.  First, remove OCC from
 205              its list.  */
 206           *p_occ = occ->next;
 207           new_occ->next = occ;
 208           occ->next = NULL;
 209
 210           /* None of the previous blocks has DOM as a dominator: if we tail
 211              recursed, we would reexamine them uselessly. Just switch BB with
 212              DOM, and go on looking for blocks dominated by DOM.  */
 213           new_occ = occ_new (dom, new_occ);
 214         }
 215
 216       else
 217         {
 218           /* Nothing special, go on with the next element.  */
 219           p_occ = &occ->next;
 220         }
 221     }
 222
 223   /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
 224   new_occ->next = *p_head;
 225   *p_head = new_occ;
 226 }
 227
 228 /* Register that we found a division in BB.  */
 229
 230 static inline void
 231 register_division_in (basic_block bb)
 232 {
 233   struct occurrence *occ;
 234
 235   occ = (struct occurrence *) bb->aux;
 236   if (!occ)
 237     {
 238       occ = occ_new (bb, NULL);
 239       insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
 240     }
 241
 242   occ->bb_has_division = true;
 243   occ->num_divisions++;
 244 }
 245
 246
 247 /* Compute the number of divisions that postdominate each block in OCC and
 248    its children.  */
 249
 250 static void
 251 compute_merit (struct occurrence *occ)
 252 {
 253   struct occurrence *occ_child;
 254   basic_block dom = occ->bb;
 255
 256   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 257     {
 258       basic_block bb;
 259       if (occ_child->children)
 260         compute_merit (occ_child);
 261
 262       if (flag_exceptions)
 263         bb = single_noncomplex_succ (dom);
 264       else
 265         bb = dom;
 266
 267       if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
 268         occ->num_divisions += occ_child->num_divisions;
 269     }
 270 }
 271
 272
 273 /* Return whether USE_STMT is a floating-point division by DEF.  */
 274 static inline bool
 275 is_division_by (tree use_stmt, tree def)
 276 {
 277   return TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
 278          && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == RDIV_EXPR
 279          && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 1) == def;
 280 }
 281
 282 /* Walk the subset of the dominator tree rooted at OCC, setting the
 283    RECIP_DEF field to a definition of 1.0 / DEF that can be used in
 284    the given basic block.  The field may be left NULL, of course,
 285    if it is not possible or profitable to do the optimization.
 286
 287    DEF_BSI is an iterator pointing at the statement defining DEF.
 288    If RECIP_DEF is set, a dominator already has a computation that can
 289    be used.  */
 290
 291 static void
 292 insert_reciprocals (block_stmt_iterator *def_bsi, struct occurrence *occ,
 293                     tree def, tree recip_def, int threshold)
 294 {
 295   tree type, new_stmt;
 296   block_stmt_iterator bsi;
 297   struct occurrence *occ_child;
 298
 299   if (!recip_def
 300       && (occ->bb_has_division || !flag_trapping_math)
 301       && occ->num_divisions >= threshold)
 302     {
 303       /* Make a variable with the replacement and substitute it.  */
 304       type = TREE_TYPE (def);
 305       recip_def = make_rename_temp (type, "reciptmp");
 306       new_stmt = build_gimple_modify_stmt (recip_def,
 307                                            fold_build2 (RDIV_EXPR, type,
 308                                                         build_one_cst (type),
 309                                                         def));
 310
 311
 312       if (occ->bb_has_division)
 313         {
 314           /* Case 1: insert before an existing division.  */
 315           bsi = bsi_after_labels (occ->bb);
 316           while (!bsi_end_p (bsi) && !is_division_by (bsi_stmt (bsi), def))
 317             bsi_next (&bsi);
 318
 319           bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
 320         }
 321       else if (def_bsi && occ->bb == def_bsi->bb)
 322         {
 323           /* Case 2: insert right after the definition.  Note that this will
 324              never happen if the definition statement can throw, because in
 325              that case the sole successor of the statement's basic block will
 326              dominate all the uses as well.  */
 327           bsi_insert_after (def_bsi, new_stmt, BSI_NEW_STMT);
 328         }
 329       else
 330         {
 331           /* Case 3: insert in a basic block not containing defs/uses.  */
 332           bsi = bsi_after_labels (occ->bb);
 333           bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
 334         }
 335
 336       occ->recip_def_stmt = new_stmt;
 337     }
 338
 339   occ->recip_def = recip_def;
 340   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 341     insert_reciprocals (def_bsi, occ_child, def, recip_def, threshold);
 342 }
 343
 344
 345 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 346    possible.  */
 347
 348 static inline void
 349 replace_reciprocal (use_operand_p use_p)
 350 {
 351   tree use_stmt = USE_STMT (use_p);
 352   basic_block bb = bb_for_stmt (use_stmt);
 353   struct occurrence *occ = (struct occurrence *) bb->aux;
 354
 355   if (occ->recip_def && use_stmt != occ->recip_def_stmt)
 356     {
 357       TREE_SET_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1), MULT_EXPR);
 358       SET_USE (use_p, occ->recip_def);
 359       fold_stmt_inplace (use_stmt);
 360       update_stmt (use_stmt);
 361     }
 362 }
 363
 364
 365 /* Free OCC and return one more "struct occurrence" to be freed.  */
 366
 367 static struct occurrence *
 368 free_bb (struct occurrence *occ)
 369 {
 370   struct occurrence *child, *next;
 371
 372   /* First get the two pointers hanging off OCC.  */
 373   next = occ->next;
 374   child = occ->children;
 375   occ->bb->aux = NULL;
 376   pool_free (occ_pool, occ);
 377
 378   /* Now ensure that we don't recurse unless it is necessary.  */
 379   if (!child)
 380     return next;
 381   else
 382     {
 383       while (next)
 384         next = free_bb (next);
 385
 386       return child;
 387     }
 388 }
 389
 390
 391 /* Look for floating-point divisions among DEF's uses, and try to
 392    replace them by multiplications with the reciprocal.  Add
 393    as many statements computing the reciprocal as needed.
 394
 395    DEF must be a GIMPLE register of a floating-point type.  */
 396
 397 static void
 398 execute_cse_reciprocals_1 (block_stmt_iterator *def_bsi, tree def)
 399 {
 400   use_operand_p use_p;
 401   imm_use_iterator use_iter;
 402   struct occurrence *occ;
 403   int count = 0, threshold;
 404
 405   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 406
 407   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 408     {
 409       tree use_stmt = USE_STMT (use_p);
 410       if (is_division_by (use_stmt, def))
 411         {
 412           register_division_in (bb_for_stmt (use_stmt));
 413           count++;
 414         }
 415     }
 416
 417   /* Do the expensive part only if we can hope to optimize something.  */
 418   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 419   if (count >= threshold)
 420     {
 421       tree use_stmt;
 422       for (occ = occ_head; occ; occ = occ->next)
 423         {
 424           compute_merit (occ);
 425           insert_reciprocals (def_bsi, occ, def, NULL, threshold);
 426         }
 427
 428       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 429         {
 430           if (is_division_by (use_stmt, def))
 431             {
 432               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 433                 replace_reciprocal (use_p);
 434             }
 435         }
 436     }
 437
 438   for (occ = occ_head; occ; )
 439     occ = free_bb (occ);
 440
 441   occ_head = NULL;
 442 }
 443
 444 static bool
 445 gate_cse_reciprocals (void)
 446 {
 447   return optimize && !optimize_size && flag_unsafe_math_optimizations;
 448 }
 449
 450 /* Go through all the floating-point SSA_NAMEs, and call
 451    execute_cse_reciprocals_1 on each of them.  */
 452 static unsigned int
 453 execute_cse_reciprocals (void)
 454 {
 455   basic_block bb;
 456   tree arg;
 457
 458   occ_pool = create_alloc_pool ("dominators for recip",
 459                                 sizeof (struct occurrence),
 460                                 n_basic_blocks / 3 + 1);
 461
 462   calculate_dominance_info (CDI_DOMINATORS);
 463   calculate_dominance_info (CDI_POST_DOMINATORS);
 464
 465 #ifdef ENABLE_CHECKING
 466   FOR_EACH_BB (bb)
 467     gcc_assert (!bb->aux);
 468 #endif
 469
 470   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 471     if (gimple_default_def (cfun, arg)
 472         && FLOAT_TYPE_P (TREE_TYPE (arg))
 473         && is_gimple_reg (arg))
 474       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 475
 476   FOR_EACH_BB (bb)
 477     {
 478       block_stmt_iterator bsi;
 479       tree phi, def;
 480
 481       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 482         {
 483           def = PHI_RESULT (phi);
 484           if (FLOAT_TYPE_P (TREE_TYPE (def))
 485               && is_gimple_reg (def))
 486             execute_cse_reciprocals_1 (NULL, def);
 487         }
 488
 489       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 490         {
 491           tree stmt = bsi_stmt (bsi);
 492
 493           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 494               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 495               && FLOAT_TYPE_P (TREE_TYPE (def))
 496               && TREE_CODE (def) == SSA_NAME)
 497             execute_cse_reciprocals_1 (&bsi, def);
 498         }
 499
 500       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 501       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 502         {
 503           tree stmt = bsi_stmt (bsi);
 504           tree fndecl;
 505
 506           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 507               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == RDIV_EXPR)
 508             {
 509               tree arg1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 1);
 510               tree stmt1;
 511
 512               if (TREE_CODE (arg1) != SSA_NAME)
 513                 continue;
 514
 515               stmt1 = SSA_NAME_DEF_STMT (arg1);
 516
 517               if (TREE_CODE (stmt1) == GIMPLE_MODIFY_STMT
 518                   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1)) == CALL_EXPR
 519                   && (fndecl
 520                       = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt1, 1)))
 521                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 522                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 523                 {
 524                   enum built_in_function code;
 525                   bool md_code;
 526                   tree arg10;
 527                   tree tmp;
 528
 529                   code = DECL_FUNCTION_CODE (fndecl);
 530                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 531
 532                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 533                   if (!fndecl)
 534                     continue;
 535
 536                   arg10 = CALL_EXPR_ARG (GIMPLE_STMT_OPERAND (stmt1, 1), 0);
 537                   tmp = build_call_expr (fndecl, 1, arg10);
 538                   GIMPLE_STMT_OPERAND (stmt1, 1) = tmp;
 539                   update_stmt (stmt1);
 540
 541                   TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt, 1), MULT_EXPR);
 542                   fold_stmt_inplace (stmt);
 543                   update_stmt (stmt);
 544                 }
 545             }
 546         }
 547     }
 548
 549   free_dominance_info (CDI_DOMINATORS);
 550   free_dominance_info (CDI_POST_DOMINATORS);
 551   free_alloc_pool (occ_pool);
 552   return 0;
 553 }
 554
 555 struct tree_opt_pass pass_cse_reciprocals =
 556 {
 557   "recip",                              /* name */
 558   gate_cse_reciprocals,                 /* gate */
 559   execute_cse_reciprocals,              /* execute */
 560   NULL,                                 /* sub */
 561   NULL,                                 /* next */
 562   0,                                    /* static_pass_number */
 563   0,                                    /* tv_id */
 564   PROP_ssa,                             /* properties_required */
 565   0,                                    /* properties_provided */
 566   0,                                    /* properties_destroyed */
 567   0,                                    /* todo_flags_start */
 568   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 569     | TODO_verify_stmts,                /* todo_flags_finish */
 570   0                                     /* letter */
 571 };
 572
 573 /* Records an occurrence at statement USE_STMT in the vector of trees
 574    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 575    is not yet initialized.  Returns true if the occurrence was pushed on
 576    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 577    statements in the vector.  */
 578
 579 static bool
 580 maybe_record_sincos (VEC(tree, heap) **stmts,
 581                      basic_block *top_bb, tree use_stmt)
 582 {
 583   basic_block use_bb = bb_for_stmt (use_stmt);
 584   if (*top_bb
 585       && (*top_bb == use_bb
 586           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 587     VEC_safe_push (tree, heap, *stmts, use_stmt);
 588   else if (!*top_bb
 589            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 590     {
 591       VEC_safe_push (tree, heap, *stmts, use_stmt);
 592       *top_bb = use_bb;
 593     }
 594   else
 595     return false;
 596
 597   return true;
 598 }
 599
 600 /* Look for sin, cos and cexpi calls with the same argument NAME and
 601    create a single call to cexpi CSEing the result in this case.
 602    We first walk over all immediate uses of the argument collecting
 603    statements that we can CSE in a vector and in a second pass replace
 604    the statement rhs with a REALPART or IMAGPART expression on the
 605    result of the cexpi call we insert before the use statement that
 606    dominates all other candidates.  */
 607
 608 static void
 609 execute_cse_sincos_1 (tree name)
 610 {
 611   block_stmt_iterator bsi;
 612   imm_use_iterator use_iter;
 613   tree def_stmt, use_stmt, fndecl, res, call, stmt, type;
 614   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 615   VEC(tree, heap) *stmts = NULL;
 616   basic_block top_bb = NULL;
 617   int i;
 618
 619   type = TREE_TYPE (name);
 620   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 621     {
 622       if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT
 623           || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) != CALL_EXPR
 624           || !(fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1)))
 625           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 626         continue;
 627
 628       switch (DECL_FUNCTION_CODE (fndecl))
 629         {
 630         CASE_FLT_FN (BUILT_IN_COS):
 631           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 632           break;
 633
 634         CASE_FLT_FN (BUILT_IN_SIN):
 635           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 636           break;
 637
 638         CASE_FLT_FN (BUILT_IN_CEXPI):
 639           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 640           break;
 641
 642         default:;
 643         }
 644     }
 645
 646   if (seen_cos + seen_sin + seen_cexpi <= 1)
 647     {
 648       VEC_free(tree, heap, stmts);
 649       return;
 650     }
 651
 652   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 653      the name def statement.  */
 654   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 655   if (!fndecl)
 656     return;
 657   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 658   call = build_call_expr (fndecl, 1, name);
 659   stmt = build_gimple_modify_stmt (res, call);
 660   def_stmt = SSA_NAME_DEF_STMT (name);
 661   if (bb_for_stmt (def_stmt) == top_bb
 662       && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
 663     {
 664       bsi = bsi_for_stmt (def_stmt);
 665       bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
 666     }
 667   else
 668     {
 669       bsi = bsi_after_labels (top_bb);
 670       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 671     }
 672   update_stmt (stmt);
 673
 674   /* And adjust the recorded old call sites.  */
 675   for (i = 0; VEC_iterate(tree, stmts, i, use_stmt); ++i)
 676     {
 677       fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1));
 678       switch (DECL_FUNCTION_CODE (fndecl))
 679         {
 680         CASE_FLT_FN (BUILT_IN_COS):
 681           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (REALPART_EXPR,
 682                                                            type, res);
 683           break;
 684
 685         CASE_FLT_FN (BUILT_IN_SIN):
 686           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (IMAGPART_EXPR,
 687                                                            type, res);
 688           break;
 689
 690         CASE_FLT_FN (BUILT_IN_CEXPI):
 691           GIMPLE_STMT_OPERAND (use_stmt, 1) = res;
 692           break;
 693
 694         default:;
 695           gcc_unreachable ();
 696         }
 697
 698         update_stmt (use_stmt);
 699     }
 700
 701   VEC_free(tree, heap, stmts);
 702 }
 703
 704 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 705    on the SSA_NAME argument of each of them.  */
 706
 707 static unsigned int
 708 execute_cse_sincos (void)
 709 {
 710   basic_block bb;
 711
 712   calculate_dominance_info (CDI_DOMINATORS);
 713
 714   FOR_EACH_BB (bb)
 715     {
 716       block_stmt_iterator bsi;
 717
 718       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 719         {
 720           tree stmt = bsi_stmt (bsi);
 721           tree fndecl;
 722
 723           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 724               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 725               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 726               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 727             {
 728               tree arg;
 729
 730               switch (DECL_FUNCTION_CODE (fndecl))
 731                 {
 732                 CASE_FLT_FN (BUILT_IN_COS):
 733                 CASE_FLT_FN (BUILT_IN_SIN):
 734                 CASE_FLT_FN (BUILT_IN_CEXPI):
 735                   arg = GIMPLE_STMT_OPERAND (stmt, 1);
 736                   arg = CALL_EXPR_ARG (arg, 0);
 737                   if (TREE_CODE (arg) == SSA_NAME)
 738                     execute_cse_sincos_1 (arg);
 739                   break;
 740
 741                 default:;
 742                 }
 743             }
 744         }
 745     }
 746
 747   free_dominance_info (CDI_DOMINATORS);
 748   return 0;
 749 }
 750
 751 static bool
 752 gate_cse_sincos (void)
 753 {
 754   /* Make sure we have either sincos or cexp.  */
 755   return (TARGET_HAS_SINCOS
 756           || TARGET_C99_FUNCTIONS)
 757          && optimize;
 758 }
 759
 760 struct tree_opt_pass pass_cse_sincos =
 761 {
 762   "sincos",                             /* name */
 763   gate_cse_sincos,                      /* gate */
 764   execute_cse_sincos,                   /* execute */
 765   NULL,                                 /* sub */
 766   NULL,                                 /* next */
 767   0,                                    /* static_pass_number */
 768   0,                                    /* tv_id */
 769   PROP_ssa,                             /* properties_required */
 770   0,                                    /* properties_provided */
 771   0,                                    /* properties_destroyed */
 772   0,                                    /* todo_flags_start */
 773   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 774     | TODO_verify_stmts,                /* todo_flags_finish */
 775   0                                     /* letter */
 776 };
 777
 778 /* Find all expressions in the form of sqrt(a/b) and
 779    convert them to rsqrt(b/a).  */
 780
 781 static unsigned int
 782 execute_convert_to_rsqrt (void)
 783 {
 784   basic_block bb;
 785
 786   FOR_EACH_BB (bb)
 787     {
 788       block_stmt_iterator bsi;
 789
 790       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 791         {
 792           tree stmt = bsi_stmt (bsi);
 793           tree fndecl;
 794
 795           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 796               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 797               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 798               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 799                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 800             {
 801               enum built_in_function code;
 802               bool md_code;
 803               tree arg1;
 804               tree stmt1;
 805
 806               code = DECL_FUNCTION_CODE (fndecl);
 807               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 808
 809               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 810               if (!fndecl)
 811                 continue;
 812
 813               arg1 = CALL_EXPR_ARG (GIMPLE_STMT_OPERAND (stmt, 1), 0);
 814
 815               if (TREE_CODE (arg1) != SSA_NAME)
 816                 continue;
 817
 818               stmt1 = SSA_NAME_DEF_STMT (arg1);
 819
 820               if (TREE_CODE (stmt1) == GIMPLE_MODIFY_STMT
 821                   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1)) == RDIV_EXPR)
 822                 {
 823                   tree arg10, arg11;
 824                   tree tmp;
 825
 826                   arg10 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0);
 827                   arg11 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1);
 828
 829                   /* Swap operands of RDIV_EXPR.  */
 830                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0) = arg11;
 831                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1) = arg10;
 832                   fold_stmt_inplace (stmt1);
 833                   update_stmt (stmt1);
 834
 835                   tmp = build_call_expr (fndecl, 1, arg1);
 836                   GIMPLE_STMT_OPERAND (stmt, 1) = tmp;
 837                   update_stmt (stmt);
 838                 }
 839             }
 840         }
 841     }
 842
 843   return 0;
 844 }
 845
 846 static bool
 847 gate_convert_to_rsqrt (void)
 848 {
 849   return flag_unsafe_math_optimizations && optimize;
 850 }
 851
 852 struct tree_opt_pass pass_convert_to_rsqrt =
 853 {
 854   "rsqrt",                              /* name */
 855   gate_convert_to_rsqrt,                /* gate */
 856   execute_convert_to_rsqrt,             /* execute */
 857   NULL,                                 /* sub */
 858   NULL,                                 /* next */
 859   0,                                    /* static_pass_number */
 860   0,                                    /* tv_id */
 861   PROP_ssa,                             /* properties_required */
 862   0,                                    /* properties_provided */
 863   0,                                    /* properties_destroyed */
 864   0,                                    /* todo_flags_start */
 865   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 866     | TODO_verify_stmts,                /* todo_flags_finish */
 867   0                                     /* letter */
 868 };