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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* Currently, the only mini-pass in this file tries to CSE reciprocal
  21    operations.  These are common in sequences such as this one:
  22
  23         modulus = sqrt(x*x + y*y + z*z);
  24         x = x / modulus;
  25         y = y / modulus;
  26         z = z / modulus;
  27
  28    that can be optimized to
  29
  30         modulus = sqrt(x*x + y*y + z*z);
  31         rmodulus = 1.0 / modulus;
  32         x = x * rmodulus;
  33         y = y * rmodulus;
  34         z = z * rmodulus;
  35
  36    We do this for loop invariant divisors, and with this pass whenever
  37    we notice that a division has the same divisor multiple times.
  38
  39    Of course, like in PRE, we don't insert a division if a dominator
  40    already has one.  However, this cannot be done as an extension of
  41    PRE for several reasons.
  42
  43    First of all, with some experiments it was found out that the
  44    transformation is not always useful if there are only two divisions
  45    hy the same divisor.  This is probably because modern processors
  46    can pipeline the divisions; on older, in-order processors it should
  47    still be effective to optimize two divisions by the same number.
  48    We make this a param, and it shall be called N in the remainder of
  49    this comment.
  50
  51    Second, if trapping math is active, we have less freedom on where
  52    to insert divisions: we can only do so in basic blocks that already
  53    contain one.  (If divisions don't trap, instead, we can insert
  54    divisions elsewhere, which will be in blocks that are common dominators
  55    of those that have the division).
  56
  57    We really don't want to compute the reciprocal unless a division will
  58    be found.  To do this, we won't insert the division in a basic block
  59    that has less than N divisions *post-dominating* it.
  60
  61    The algorithm constructs a subset of the dominator tree, holding the
  62    blocks containing the divisions and the common dominators to them,
  63    and walk it twice.  The first walk is in post-order, and it annotates
  64    each block with the number of divisions that post-dominate it: this
  65    gives information on where divisions can be inserted profitably.
  66    The second walk is in pre-order, and it inserts divisions as explained
  67    above, and replaces divisions by multiplications.
  68
  69    In the best case, the cost of the pass is O(n_statements).  In the
  70    worst-case, the cost is due to creating the dominator tree subset,
  71    with a cost of O(n_basic_blocks ^ 2); however this can only happen
  72    for n_statements / n_basic_blocks statements.  So, the amortized cost
  73    of creating the dominator tree subset is O(n_basic_blocks) and the
  74    worst-case cost of the pass is O(n_statements * n_basic_blocks).
  75
  76    More practically, the cost will be small because there are few
  77    divisions, and they tend to be in the same basic block, so insert_bb
  78    is called very few times.
  79
  80    If we did this using domwalk.c, an efficient implementation would have
  81    to work on all the variables in a single pass, because we could not
  82    work on just a subset of the dominator tree, as we do now, and the
  83    cost would also be something like O(n_statements * n_basic_blocks).
  84    The data structures would be more complex in order to work on all the
  85    variables in a single pass.  */
  86
  87 #include "config.h"
  88 #include "system.h"
  89 #include "coretypes.h"
  90 #include "tm.h"
  91 #include "flags.h"
  92 #include "tree.h"
  93 #include "tree-flow.h"
  94 #include "real.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
 101
 102 /* This structure represents one basic block that either computes a
 103    division, or is a common dominator for basic block that compute a
 104    division.  */
 105 struct occurrence {
 106   /* The basic block represented by this structure.  */
 107   basic_block bb;
 108
 109   /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
 110      inserted in BB.  */
 111   tree recip_def;
 112
 113   /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
 114      was inserted in BB.  */
 115   gimple recip_def_stmt;
 116
 117   /* Pointer to a list of "struct occurrence"s for blocks dominated
 118      by BB.  */
 119   struct occurrence *children;
 120
 121   /* Pointer to the next "struct occurrence"s in the list of blocks
 122      sharing a common dominator.  */
 123   struct occurrence *next;
 124
 125   /* The number of divisions that are in BB before compute_merit.  The
 126      number of divisions that are in BB or post-dominate it after
 127      compute_merit.  */
 128   int num_divisions;
 129
 130   /* True if the basic block has a division, false if it is a common
 131      dominator for basic blocks that do.  If it is false and trapping
 132      math is active, BB is not a candidate for inserting a reciprocal.  */
 133   bool bb_has_division;
 134 };
 135
 136
 137 /* The instance of "struct occurrence" representing the highest
 138    interesting block in the dominator tree.  */
 139 static struct occurrence *occ_head;
 140
 141 /* Allocation pool for getting instances of "struct occurrence".  */
 142 static alloc_pool occ_pool;
 143
 144
 145
 146 /* Allocate and return a new struct occurrence for basic block BB, and
 147    whose children list is headed by CHILDREN.  */
 148 static struct occurrence *
 149 occ_new (basic_block bb, struct occurrence *children)
 150 {
 151   struct occurrence *occ;
 152
 153   bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
 154   memset (occ, 0, sizeof (struct occurrence));
 155
 156   occ->bb = bb;
 157   occ->children = children;
 158   return occ;
 159 }
 160
 161
 162 /* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
 163    list of "struct occurrence"s, one per basic block, having IDOM as
 164    their common dominator.
 165
 166    We try to insert NEW_OCC as deep as possible in the tree, and we also
 167    insert any other block that is a common dominator for BB and one
 168    block already in the tree.  */
 169
 170 static void
 171 insert_bb (struct occurrence *new_occ, basic_block idom,
 172            struct occurrence **p_head)
 173 {
 174   struct occurrence *occ, **p_occ;
 175
 176   for (p_occ = p_head; (occ = *p_occ) != NULL; )
 177     {
 178       basic_block bb = new_occ->bb, occ_bb = occ->bb;
 179       basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
 180       if (dom == bb)
 181         {
 182           /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
 183              from its list.  */
 184           *p_occ = occ->next;
 185           occ->next = new_occ->children;
 186           new_occ->children = occ;
 187
 188           /* Try the next block (it may as well be dominated by BB).  */
 189         }
 190
 191       else if (dom == occ_bb)
 192         {
 193           /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
 194           insert_bb (new_occ, dom, &occ->children);
 195           return;
 196         }
 197
 198       else if (dom != idom)
 199         {
 200           gcc_assert (!dom->aux);
 201
 202           /* There is a dominator between IDOM and BB, add it and make
 203              two children out of NEW_OCC and OCC.  First, remove OCC from
 204              its list.  */
 205           *p_occ = occ->next;
 206           new_occ->next = occ;
 207           occ->next = NULL;
 208
 209           /* None of the previous blocks has DOM as a dominator: if we tail
 210              recursed, we would reexamine them uselessly. Just switch BB with
 211              DOM, and go on looking for blocks dominated by DOM.  */
 212           new_occ = occ_new (dom, new_occ);
 213         }
 214
 215       else
 216         {
 217           /* Nothing special, go on with the next element.  */
 218           p_occ = &occ->next;
 219         }
 220     }
 221
 222   /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
 223   new_occ->next = *p_head;
 224   *p_head = new_occ;
 225 }
 226
 227 /* Register that we found a division in BB.  */
 228
 229 static inline void
 230 register_division_in (basic_block bb)
 231 {
 232   struct occurrence *occ;
 233
 234   occ = (struct occurrence *) bb->aux;
 235   if (!occ)
 236     {
 237       occ = occ_new (bb, NULL);
 238       insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
 239     }
 240
 241   occ->bb_has_division = true;
 242   occ->num_divisions++;
 243 }
 244
 245
 246 /* Compute the number of divisions that postdominate each block in OCC and
 247    its children.  */
 248
 249 static void
 250 compute_merit (struct occurrence *occ)
 251 {
 252   struct occurrence *occ_child;
 253   basic_block dom = occ->bb;
 254
 255   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 256     {
 257       basic_block bb;
 258       if (occ_child->children)
 259         compute_merit (occ_child);
 260
 261       if (flag_exceptions)
 262         bb = single_noncomplex_succ (dom);
 263       else
 264         bb = dom;
 265
 266       if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
 267         occ->num_divisions += occ_child->num_divisions;
 268     }
 269 }
 270
 271
 272 /* Return whether USE_STMT is a floating-point division by DEF.  */
 273 static inline bool
 274 is_division_by (gimple use_stmt, tree def)
 275 {
 276   return is_gimple_assign (use_stmt)
 277          && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
 278          && gimple_assign_rhs2 (use_stmt) == def
 279          /* Do not recognize x / x as valid division, as we are getting
 280             confused later by replacing all immediate uses x in such
 281             a stmt.  */
 282          && gimple_assign_rhs1 (use_stmt) != def;
 283 }
 284
 285 /* Walk the subset of the dominator tree rooted at OCC, setting the
 286    RECIP_DEF field to a definition of 1.0 / DEF that can be used in
 287    the given basic block.  The field may be left NULL, of course,
 288    if it is not possible or profitable to do the optimization.
 289
 290    DEF_BSI is an iterator pointing at the statement defining DEF.
 291    If RECIP_DEF is set, a dominator already has a computation that can
 292    be used.  */
 293
 294 static void
 295 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
 296                     tree def, tree recip_def, int threshold)
 297 {
 298   tree type;
 299   gimple new_stmt;
 300   gimple_stmt_iterator gsi;
 301   struct occurrence *occ_child;
 302
 303   if (!recip_def
 304       && (occ->bb_has_division || !flag_trapping_math)
 305       && occ->num_divisions >= threshold)
 306     {
 307       /* Make a variable with the replacement and substitute it.  */
 308       type = TREE_TYPE (def);
 309       recip_def = make_rename_temp (type, "reciptmp");
 310       new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
 311                                                build_one_cst (type), def);
 312
 313       if (occ->bb_has_division)
 314         {
 315           /* Case 1: insert before an existing division.  */
 316           gsi = gsi_after_labels (occ->bb);
 317           while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
 318             gsi_next (&gsi);
 319
 320           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 321         }
 322       else if (def_gsi && occ->bb == def_gsi->bb)
 323         {
 324           /* Case 2: insert right after the definition.  Note that this will
 325              never happen if the definition statement can throw, because in
 326              that case the sole successor of the statement's basic block will
 327              dominate all the uses as well.  */
 328           gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
 329         }
 330       else
 331         {
 332           /* Case 3: insert in a basic block not containing defs/uses.  */
 333           gsi = gsi_after_labels (occ->bb);
 334           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 335         }
 336
 337       occ->recip_def_stmt = new_stmt;
 338     }
 339
 340   occ->recip_def = recip_def;
 341   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 342     insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
 343 }
 344
 345
 346 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 347    possible.  */
 348
 349 static inline void
 350 replace_reciprocal (use_operand_p use_p)
 351 {
 352   gimple use_stmt = USE_STMT (use_p);
 353   basic_block bb = gimple_bb (use_stmt);
 354   struct occurrence *occ = (struct occurrence *) bb->aux;
 355
 356   if (occ->recip_def && use_stmt != occ->recip_def_stmt)
 357     {
 358       gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
 359       SET_USE (use_p, occ->recip_def);
 360       fold_stmt_inplace (use_stmt);
 361       update_stmt (use_stmt);
 362     }
 363 }
 364
 365
 366 /* Free OCC and return one more "struct occurrence" to be freed.  */
 367
 368 static struct occurrence *
 369 free_bb (struct occurrence *occ)
 370 {
 371   struct occurrence *child, *next;
 372
 373   /* First get the two pointers hanging off OCC.  */
 374   next = occ->next;
 375   child = occ->children;
 376   occ->bb->aux = NULL;
 377   pool_free (occ_pool, occ);
 378
 379   /* Now ensure that we don't recurse unless it is necessary.  */
 380   if (!child)
 381     return next;
 382   else
 383     {
 384       while (next)
 385         next = free_bb (next);
 386
 387       return child;
 388     }
 389 }
 390
 391
 392 /* Look for floating-point divisions among DEF's uses, and try to
 393    replace them by multiplications with the reciprocal.  Add
 394    as many statements computing the reciprocal as needed.
 395
 396    DEF must be a GIMPLE register of a floating-point type.  */
 397
 398 static void
 399 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
 400 {
 401   use_operand_p use_p;
 402   imm_use_iterator use_iter;
 403   struct occurrence *occ;
 404   int count = 0, threshold;
 405
 406   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 407
 408   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 409     {
 410       gimple use_stmt = USE_STMT (use_p);
 411       if (is_division_by (use_stmt, def))
 412         {
 413           register_division_in (gimple_bb (use_stmt));
 414           count++;
 415         }
 416     }
 417
 418   /* Do the expensive part only if we can hope to optimize something.  */
 419   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 420   if (count >= threshold)
 421     {
 422       gimple use_stmt;
 423       for (occ = occ_head; occ; occ = occ->next)
 424         {
 425           compute_merit (occ);
 426           insert_reciprocals (def_gsi, occ, def, NULL, threshold);
 427         }
 428
 429       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 430         {
 431           if (is_division_by (use_stmt, def))
 432             {
 433               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 434                 replace_reciprocal (use_p);
 435             }
 436         }
 437     }
 438
 439   for (occ = occ_head; occ; )
 440     occ = free_bb (occ);
 441
 442   occ_head = NULL;
 443 }
 444
 445 static bool
 446 gate_cse_reciprocals (void)
 447 {
 448   return optimize && !optimize_size && flag_reciprocal_math;
 449 }
 450
 451 /* Go through all the floating-point SSA_NAMEs, and call
 452    execute_cse_reciprocals_1 on each of them.  */
 453 static unsigned int
 454 execute_cse_reciprocals (void)
 455 {
 456   basic_block bb;
 457   tree arg;
 458
 459   occ_pool = create_alloc_pool ("dominators for recip",
 460                                 sizeof (struct occurrence),
 461                                 n_basic_blocks / 3 + 1);
 462
 463   calculate_dominance_info (CDI_DOMINATORS);
 464   calculate_dominance_info (CDI_POST_DOMINATORS);
 465
 466 #ifdef ENABLE_CHECKING
 467   FOR_EACH_BB (bb)
 468     gcc_assert (!bb->aux);
 469 #endif
 470
 471   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 472     if (gimple_default_def (cfun, arg)
 473         && FLOAT_TYPE_P (TREE_TYPE (arg))
 474         && is_gimple_reg (arg))
 475       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 476
 477   FOR_EACH_BB (bb)
 478     {
 479       gimple_stmt_iterator gsi;
 480       gimple phi;
 481       tree def;
 482
 483       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 484         {
 485           phi = gsi_stmt (gsi);
 486           def = PHI_RESULT (phi);
 487           if (FLOAT_TYPE_P (TREE_TYPE (def))
 488               && is_gimple_reg (def))
 489             execute_cse_reciprocals_1 (NULL, def);
 490         }
 491
 492       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 493         {
 494           gimple stmt = gsi_stmt (gsi);
 495
 496           if (gimple_has_lhs (stmt)
 497               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 498               && FLOAT_TYPE_P (TREE_TYPE (def))
 499               && TREE_CODE (def) == SSA_NAME)
 500             execute_cse_reciprocals_1 (&gsi, def);
 501         }
 502
 503       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 504       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 505         {
 506           gimple stmt = gsi_stmt (gsi);
 507           tree fndecl;
 508
 509           if (is_gimple_assign (stmt)
 510               && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
 511             {
 512               tree arg1 = gimple_assign_rhs2 (stmt);
 513               gimple stmt1;
 514
 515               if (TREE_CODE (arg1) != SSA_NAME)
 516                 continue;
 517
 518               stmt1 = SSA_NAME_DEF_STMT (arg1);
 519
 520               if (is_gimple_call (stmt1)
 521                   && gimple_call_lhs (stmt1)
 522                   && (fndecl = gimple_call_fndecl (stmt1))
 523                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 524                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 525                 {
 526                   enum built_in_function code;
 527                   bool md_code;
 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                   gimple_call_set_fndecl (stmt1, fndecl);
 537                   update_stmt (stmt1);
 538
 539                   gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 540                   fold_stmt_inplace (stmt);
 541                   update_stmt (stmt);
 542                 }
 543             }
 544         }
 545     }
 546
 547   free_dominance_info (CDI_DOMINATORS);
 548   free_dominance_info (CDI_POST_DOMINATORS);
 549   free_alloc_pool (occ_pool);
 550   return 0;
 551 }
 552
 553 struct gimple_opt_pass pass_cse_reciprocals =
 554 {
 555  {
 556   GIMPLE_PASS,
 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  }
 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(gimple, heap) **stmts,
 581                      basic_block *top_bb, gimple use_stmt)
 582 {
 583   basic_block use_bb = gimple_bb (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 (gimple, heap, *stmts, use_stmt);
 588   else if (!*top_bb
 589            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 590     {
 591       VEC_safe_push (gimple, 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   gimple_stmt_iterator gsi;
 612   imm_use_iterator use_iter;
 613   tree fndecl, res, type;
 614   gimple def_stmt, use_stmt, stmt;
 615   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 616   VEC(gimple, heap) *stmts = NULL;
 617   basic_block top_bb = NULL;
 618   int i;
 619
 620   type = TREE_TYPE (name);
 621   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 622     {
 623       if (gimple_code (use_stmt) != GIMPLE_CALL
 624           || !gimple_call_lhs (use_stmt)
 625           || !(fndecl = gimple_call_fndecl (use_stmt))
 626           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 627         continue;
 628
 629       switch (DECL_FUNCTION_CODE (fndecl))
 630         {
 631         CASE_FLT_FN (BUILT_IN_COS):
 632           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 633           break;
 634
 635         CASE_FLT_FN (BUILT_IN_SIN):
 636           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 637           break;
 638
 639         CASE_FLT_FN (BUILT_IN_CEXPI):
 640           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 641           break;
 642
 643         default:;
 644         }
 645     }
 646
 647   if (seen_cos + seen_sin + seen_cexpi <= 1)
 648     {
 649       VEC_free(gimple, heap, stmts);
 650       return;
 651     }
 652
 653   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 654      the name def statement.  */
 655   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 656   if (!fndecl)
 657     return;
 658   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 659   stmt = gimple_build_call (fndecl, 1, name);
 660   gimple_call_set_lhs (stmt, res);
 661
 662   def_stmt = SSA_NAME_DEF_STMT (name);
 663   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 664       && gimple_code (def_stmt) != GIMPLE_PHI
 665       && gimple_bb (def_stmt) == top_bb)
 666     {
 667       gsi = gsi_for_stmt (def_stmt);
 668       gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 669     }
 670   else
 671     {
 672       gsi = gsi_after_labels (top_bb);
 673       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 674     }
 675   update_stmt (stmt);
 676
 677   /* And adjust the recorded old call sites.  */
 678   for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
 679     {
 680       tree rhs = NULL;
 681       fndecl = gimple_call_fndecl (use_stmt);
 682
 683       switch (DECL_FUNCTION_CODE (fndecl))
 684         {
 685         CASE_FLT_FN (BUILT_IN_COS):
 686           rhs = fold_build1 (REALPART_EXPR, type, res);
 687           break;
 688
 689         CASE_FLT_FN (BUILT_IN_SIN):
 690           rhs = fold_build1 (IMAGPART_EXPR, type, res);
 691           break;
 692
 693         CASE_FLT_FN (BUILT_IN_CEXPI):
 694           rhs = res;
 695           break;
 696
 697         default:;
 698           gcc_unreachable ();
 699         }
 700
 701         /* Replace call with a copy.  */
 702         stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
 703
 704         gsi = gsi_for_stmt (use_stmt);
 705         gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 706         gsi_remove (&gsi, true);
 707     }
 708
 709   VEC_free(gimple, heap, stmts);
 710 }
 711
 712 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 713    on the SSA_NAME argument of each of them.  */
 714
 715 static unsigned int
 716 execute_cse_sincos (void)
 717 {
 718   basic_block bb;
 719
 720   calculate_dominance_info (CDI_DOMINATORS);
 721
 722   FOR_EACH_BB (bb)
 723     {
 724       gimple_stmt_iterator gsi;
 725
 726       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 727         {
 728           gimple stmt = gsi_stmt (gsi);
 729           tree fndecl;
 730
 731           if (is_gimple_call (stmt)
 732               && gimple_call_lhs (stmt)
 733               && (fndecl = gimple_call_fndecl (stmt))
 734               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 735             {
 736               tree arg;
 737
 738               switch (DECL_FUNCTION_CODE (fndecl))
 739                 {
 740                 CASE_FLT_FN (BUILT_IN_COS):
 741                 CASE_FLT_FN (BUILT_IN_SIN):
 742                 CASE_FLT_FN (BUILT_IN_CEXPI):
 743                   arg = gimple_call_arg (stmt, 0);
 744                   if (TREE_CODE (arg) == SSA_NAME)
 745                     execute_cse_sincos_1 (arg);
 746                   break;
 747
 748                 default:;
 749                 }
 750             }
 751         }
 752     }
 753
 754   free_dominance_info (CDI_DOMINATORS);
 755   return 0;
 756 }
 757
 758 static bool
 759 gate_cse_sincos (void)
 760 {
 761   /* Make sure we have either sincos or cexp.  */
 762   return (TARGET_HAS_SINCOS
 763           || TARGET_C99_FUNCTIONS)
 764          && optimize;
 765 }
 766
 767 struct gimple_opt_pass pass_cse_sincos =
 768 {
 769  {
 770   GIMPLE_PASS,
 771   "sincos",                             /* name */
 772   gate_cse_sincos,                      /* gate */
 773   execute_cse_sincos,                   /* execute */
 774   NULL,                                 /* sub */
 775   NULL,                                 /* next */
 776   0,                                    /* static_pass_number */
 777   0,                                    /* tv_id */
 778   PROP_ssa,                             /* properties_required */
 779   0,                                    /* properties_provided */
 780   0,                                    /* properties_destroyed */
 781   0,                                    /* todo_flags_start */
 782   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 783     | TODO_verify_stmts                 /* todo_flags_finish */
 784  }
 785 };
 786
 787 /* Find all expressions in the form of sqrt(a/b) and
 788    convert them to rsqrt(b/a).  */
 789
 790 static unsigned int
 791 execute_convert_to_rsqrt (void)
 792 {
 793   basic_block bb;
 794
 795   FOR_EACH_BB (bb)
 796     {
 797       gimple_stmt_iterator gsi;
 798
 799       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 800         {
 801           gimple stmt = gsi_stmt (gsi);
 802           tree fndecl;
 803
 804           if (is_gimple_call (stmt)
 805               && gimple_call_lhs (stmt)
 806               && (fndecl = gimple_call_fndecl (stmt))
 807               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 808                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 809             {
 810               enum built_in_function code;
 811               bool md_code;
 812               tree arg1;
 813               gimple stmt1;
 814
 815               code = DECL_FUNCTION_CODE (fndecl);
 816               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 817
 818               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 819               if (!fndecl)
 820                 continue;
 821
 822               arg1 = gimple_call_arg (stmt, 0);
 823
 824               if (TREE_CODE (arg1) != SSA_NAME)
 825                 continue;
 826
 827               stmt1 = SSA_NAME_DEF_STMT (arg1);
 828
 829               if (is_gimple_assign (stmt1)
 830                   && gimple_assign_rhs_code (stmt1) == RDIV_EXPR)
 831                 {
 832                   tree arg10, arg11;
 833
 834                   arg10 = gimple_assign_rhs1 (stmt1);
 835                   arg11 = gimple_assign_rhs2 (stmt1);
 836
 837                   /* Swap operands of RDIV_EXPR.  */
 838                   gimple_assign_set_rhs1 (stmt1, arg11);
 839                   gimple_assign_set_rhs2 (stmt1, arg10);
 840                   fold_stmt_inplace (stmt1);
 841                   update_stmt (stmt1);
 842
 843                   gimple_call_set_fndecl (stmt, fndecl);
 844                   update_stmt (stmt);
 845                 }
 846             }
 847         }
 848     }
 849
 850   return 0;
 851 }
 852
 853 static bool
 854 gate_convert_to_rsqrt (void)
 855 {
 856   return flag_unsafe_math_optimizations && optimize;
 857 }
 858
 859 struct gimple_opt_pass pass_convert_to_rsqrt =
 860 {
 861  {
 862   GIMPLE_PASS,
 863   "rsqrt",                              /* name */
 864   gate_convert_to_rsqrt,                /* gate */
 865   execute_convert_to_rsqrt,             /* execute */
 866   NULL,                                 /* sub */
 867   NULL,                                 /* next */
 868   0,                                    /* static_pass_number */
 869   0,                                    /* tv_id */
 870   PROP_ssa,                             /* properties_required */
 871   0,                                    /* properties_provided */
 872   0,                                    /* properties_destroyed */
 873   0,                                    /* todo_flags_start */
 874   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 875     | TODO_verify_stmts                 /* todo_flags_finish */
 876  }
 877 };