contrib/gcc-4.4/gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005, 2006, 2007, 2008 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 (optimize_bb_for_speed_p (bb)
 357       && occ->recip_def && use_stmt != occ->recip_def_stmt)
 358     {
 359       gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
 360       SET_USE (use_p, occ->recip_def);
 361       fold_stmt_inplace (use_stmt);
 362       update_stmt (use_stmt);
 363     }
 364 }
 365
 366
 367 /* Free OCC and return one more "struct occurrence" to be freed.  */
 368
 369 static struct occurrence *
 370 free_bb (struct occurrence *occ)
 371 {
 372   struct occurrence *child, *next;
 373
 374   /* First get the two pointers hanging off OCC.  */
 375   next = occ->next;
 376   child = occ->children;
 377   occ->bb->aux = NULL;
 378   pool_free (occ_pool, occ);
 379
 380   /* Now ensure that we don't recurse unless it is necessary.  */
 381   if (!child)
 382     return next;
 383   else
 384     {
 385       while (next)
 386         next = free_bb (next);
 387
 388       return child;
 389     }
 390 }
 391
 392
 393 /* Look for floating-point divisions among DEF's uses, and try to
 394    replace them by multiplications with the reciprocal.  Add
 395    as many statements computing the reciprocal as needed.
 396
 397    DEF must be a GIMPLE register of a floating-point type.  */
 398
 399 static void
 400 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
 401 {
 402   use_operand_p use_p;
 403   imm_use_iterator use_iter;
 404   struct occurrence *occ;
 405   int count = 0, threshold;
 406
 407   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 408
 409   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 410     {
 411       gimple use_stmt = USE_STMT (use_p);
 412       if (is_division_by (use_stmt, def))
 413         {
 414           register_division_in (gimple_bb (use_stmt));
 415           count++;
 416         }
 417     }
 418
 419   /* Do the expensive part only if we can hope to optimize something.  */
 420   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 421   if (count >= threshold)
 422     {
 423       gimple use_stmt;
 424       for (occ = occ_head; occ; occ = occ->next)
 425         {
 426           compute_merit (occ);
 427           insert_reciprocals (def_gsi, occ, def, NULL, threshold);
 428         }
 429
 430       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 431         {
 432           if (is_division_by (use_stmt, def))
 433             {
 434               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 435                 replace_reciprocal (use_p);
 436             }
 437         }
 438     }
 439
 440   for (occ = occ_head; occ; )
 441     occ = free_bb (occ);
 442
 443   occ_head = NULL;
 444 }
 445
 446 static bool
 447 gate_cse_reciprocals (void)
 448 {
 449   return optimize && flag_reciprocal_math;
 450 }
 451
 452 /* Go through all the floating-point SSA_NAMEs, and call
 453    execute_cse_reciprocals_1 on each of them.  */
 454 static unsigned int
 455 execute_cse_reciprocals (void)
 456 {
 457   basic_block bb;
 458   tree arg;
 459
 460   occ_pool = create_alloc_pool ("dominators for recip",
 461                                 sizeof (struct occurrence),
 462                                 n_basic_blocks / 3 + 1);
 463
 464   calculate_dominance_info (CDI_DOMINATORS);
 465   calculate_dominance_info (CDI_POST_DOMINATORS);
 466
 467 #ifdef ENABLE_CHECKING
 468   FOR_EACH_BB (bb)
 469     gcc_assert (!bb->aux);
 470 #endif
 471
 472   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 473     if (gimple_default_def (cfun, arg)
 474         && FLOAT_TYPE_P (TREE_TYPE (arg))
 475         && is_gimple_reg (arg))
 476       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 477
 478   FOR_EACH_BB (bb)
 479     {
 480       gimple_stmt_iterator gsi;
 481       gimple phi;
 482       tree def;
 483
 484       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 485         {
 486           phi = gsi_stmt (gsi);
 487           def = PHI_RESULT (phi);
 488           if (FLOAT_TYPE_P (TREE_TYPE (def))
 489               && is_gimple_reg (def))
 490             execute_cse_reciprocals_1 (NULL, def);
 491         }
 492
 493       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 494         {
 495           gimple stmt = gsi_stmt (gsi);
 496
 497           if (gimple_has_lhs (stmt)
 498               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 499               && FLOAT_TYPE_P (TREE_TYPE (def))
 500               && TREE_CODE (def) == SSA_NAME)
 501             execute_cse_reciprocals_1 (&gsi, def);
 502         }
 503
 504       if (optimize_bb_for_size_p (bb))
 505         continue;
 506
 507       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 508       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 509         {
 510           gimple stmt = gsi_stmt (gsi);
 511           tree fndecl;
 512
 513           if (is_gimple_assign (stmt)
 514               && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
 515             {
 516               tree arg1 = gimple_assign_rhs2 (stmt);
 517               gimple stmt1;
 518
 519               if (TREE_CODE (arg1) != SSA_NAME)
 520                 continue;
 521
 522               stmt1 = SSA_NAME_DEF_STMT (arg1);
 523
 524               if (is_gimple_call (stmt1)
 525                   && gimple_call_lhs (stmt1)
 526                   && (fndecl = gimple_call_fndecl (stmt1))
 527                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 528                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 529                 {
 530                   enum built_in_function code;
 531                   bool md_code, fail;
 532                   imm_use_iterator ui;
 533                   use_operand_p use_p;
 534
 535                   code = DECL_FUNCTION_CODE (fndecl);
 536                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 537
 538                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 539                   if (!fndecl)
 540                     continue;
 541
 542                   /* Check that all uses of the SSA name are divisions,
 543                      otherwise replacing the defining statement will do
 544                      the wrong thing.  */
 545                   fail = false;
 546                   FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
 547                     {
 548                       gimple stmt2 = USE_STMT (use_p);
 549                       if (!is_gimple_assign (stmt2)
 550                           || gimple_assign_rhs_code (stmt2) != RDIV_EXPR
 551                           || gimple_assign_rhs1 (stmt2) == arg1
 552                           || gimple_assign_rhs2 (stmt2) != arg1)
 553                         {
 554                           fail = true;
 555                           break;
 556                         }
 557                     }
 558                   if (fail)
 559                     continue;
 560
 561                   gimple_call_set_fndecl (stmt1, fndecl);
 562                   update_stmt (stmt1);
 563
 564                   FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
 565                     {
 566                       gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 567                       fold_stmt_inplace (stmt);
 568                       update_stmt (stmt);
 569                     }
 570                 }
 571             }
 572         }
 573     }
 574
 575   free_dominance_info (CDI_DOMINATORS);
 576   free_dominance_info (CDI_POST_DOMINATORS);
 577   free_alloc_pool (occ_pool);
 578   return 0;
 579 }
 580
 581 struct gimple_opt_pass pass_cse_reciprocals =
 582 {
 583  {
 584   GIMPLE_PASS,
 585   "recip",                              /* name */
 586   gate_cse_reciprocals,                 /* gate */
 587   execute_cse_reciprocals,              /* execute */
 588   NULL,                                 /* sub */
 589   NULL,                                 /* next */
 590   0,                                    /* static_pass_number */
 591   0,                                    /* tv_id */
 592   PROP_ssa,                             /* properties_required */
 593   0,                                    /* properties_provided */
 594   0,                                    /* properties_destroyed */
 595   0,                                    /* todo_flags_start */
 596   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 597     | TODO_verify_stmts                /* todo_flags_finish */
 598  }
 599 };
 600
 601 /* Records an occurrence at statement USE_STMT in the vector of trees
 602    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 603    is not yet initialized.  Returns true if the occurrence was pushed on
 604    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 605    statements in the vector.  */
 606
 607 static bool
 608 maybe_record_sincos (VEC(gimple, heap) **stmts,
 609                      basic_block *top_bb, gimple use_stmt)
 610 {
 611   basic_block use_bb = gimple_bb (use_stmt);
 612   if (*top_bb
 613       && (*top_bb == use_bb
 614           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 615     VEC_safe_push (gimple, heap, *stmts, use_stmt);
 616   else if (!*top_bb
 617            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 618     {
 619       VEC_safe_push (gimple, heap, *stmts, use_stmt);
 620       *top_bb = use_bb;
 621     }
 622   else
 623     return false;
 624
 625   return true;
 626 }
 627
 628 /* Look for sin, cos and cexpi calls with the same argument NAME and
 629    create a single call to cexpi CSEing the result in this case.
 630    We first walk over all immediate uses of the argument collecting
 631    statements that we can CSE in a vector and in a second pass replace
 632    the statement rhs with a REALPART or IMAGPART expression on the
 633    result of the cexpi call we insert before the use statement that
 634    dominates all other candidates.  */
 635
 636 static void
 637 execute_cse_sincos_1 (tree name)
 638 {
 639   gimple_stmt_iterator gsi;
 640   imm_use_iterator use_iter;
 641   tree fndecl, res, type;
 642   gimple def_stmt, use_stmt, stmt;
 643   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 644   VEC(gimple, heap) *stmts = NULL;
 645   basic_block top_bb = NULL;
 646   int i;
 647
 648   type = TREE_TYPE (name);
 649   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 650     {
 651       if (gimple_code (use_stmt) != GIMPLE_CALL
 652           || !gimple_call_lhs (use_stmt)
 653           || !(fndecl = gimple_call_fndecl (use_stmt))
 654           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 655         continue;
 656
 657       switch (DECL_FUNCTION_CODE (fndecl))
 658         {
 659         CASE_FLT_FN (BUILT_IN_COS):
 660           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 661           break;
 662
 663         CASE_FLT_FN (BUILT_IN_SIN):
 664           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 665           break;
 666
 667         CASE_FLT_FN (BUILT_IN_CEXPI):
 668           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 669           break;
 670
 671         default:;
 672         }
 673     }
 674
 675   if (seen_cos + seen_sin + seen_cexpi <= 1)
 676     {
 677       VEC_free(gimple, heap, stmts);
 678       return;
 679     }
 680
 681   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 682      the name def statement.  */
 683   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 684   if (!fndecl)
 685     return;
 686   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 687   stmt = gimple_build_call (fndecl, 1, name);
 688   gimple_call_set_lhs (stmt, res);
 689
 690   def_stmt = SSA_NAME_DEF_STMT (name);
 691   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 692       && gimple_code (def_stmt) != GIMPLE_PHI
 693       && gimple_bb (def_stmt) == top_bb)
 694     {
 695       gsi = gsi_for_stmt (def_stmt);
 696       gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 697     }
 698   else
 699     {
 700       gsi = gsi_after_labels (top_bb);
 701       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 702     }
 703   update_stmt (stmt);
 704
 705   /* And adjust the recorded old call sites.  */
 706   for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
 707     {
 708       tree rhs = NULL;
 709       fndecl = gimple_call_fndecl (use_stmt);
 710
 711       switch (DECL_FUNCTION_CODE (fndecl))
 712         {
 713         CASE_FLT_FN (BUILT_IN_COS):
 714           rhs = fold_build1 (REALPART_EXPR, type, res);
 715           break;
 716
 717         CASE_FLT_FN (BUILT_IN_SIN):
 718           rhs = fold_build1 (IMAGPART_EXPR, type, res);
 719           break;
 720
 721         CASE_FLT_FN (BUILT_IN_CEXPI):
 722           rhs = res;
 723           break;
 724
 725         default:;
 726           gcc_unreachable ();
 727         }
 728
 729         /* Replace call with a copy.  */
 730         stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
 731
 732         gsi = gsi_for_stmt (use_stmt);
 733         gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 734         gsi_remove (&gsi, true);
 735     }
 736
 737   VEC_free(gimple, heap, stmts);
 738 }
 739
 740 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 741    on the SSA_NAME argument of each of them.  */
 742
 743 static unsigned int
 744 execute_cse_sincos (void)
 745 {
 746   basic_block bb;
 747
 748   calculate_dominance_info (CDI_DOMINATORS);
 749
 750   FOR_EACH_BB (bb)
 751     {
 752       gimple_stmt_iterator gsi;
 753
 754       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 755         {
 756           gimple stmt = gsi_stmt (gsi);
 757           tree fndecl;
 758
 759           if (is_gimple_call (stmt)
 760               && gimple_call_lhs (stmt)
 761               && (fndecl = gimple_call_fndecl (stmt))
 762               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 763             {
 764               tree arg;
 765
 766               switch (DECL_FUNCTION_CODE (fndecl))
 767                 {
 768                 CASE_FLT_FN (BUILT_IN_COS):
 769                 CASE_FLT_FN (BUILT_IN_SIN):
 770                 CASE_FLT_FN (BUILT_IN_CEXPI):
 771                   arg = gimple_call_arg (stmt, 0);
 772                   if (TREE_CODE (arg) == SSA_NAME)
 773                     execute_cse_sincos_1 (arg);
 774                   break;
 775
 776                 default:;
 777                 }
 778             }
 779         }
 780     }
 781
 782   free_dominance_info (CDI_DOMINATORS);
 783   return 0;
 784 }
 785
 786 static bool
 787 gate_cse_sincos (void)
 788 {
 789   /* Make sure we have either sincos or cexp.  */
 790   return (TARGET_HAS_SINCOS
 791           || TARGET_C99_FUNCTIONS)
 792          && optimize;
 793 }
 794
 795 struct gimple_opt_pass pass_cse_sincos =
 796 {
 797  {
 798   GIMPLE_PASS,
 799   "sincos",                             /* name */
 800   gate_cse_sincos,                      /* gate */
 801   execute_cse_sincos,                   /* execute */
 802   NULL,                                 /* sub */
 803   NULL,                                 /* next */
 804   0,                                    /* static_pass_number */
 805   0,                                    /* tv_id */
 806   PROP_ssa,                             /* properties_required */
 807   0,                                    /* properties_provided */
 808   0,                                    /* properties_destroyed */
 809   0,                                    /* todo_flags_start */
 810   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 811     | TODO_verify_stmts                 /* todo_flags_finish */
 812  }
 813 };
 814
 815 /* Find all expressions in the form of sqrt(a/b) and
 816    convert them to rsqrt(b/a).  */
 817
 818 static unsigned int
 819 execute_convert_to_rsqrt (void)
 820 {
 821   basic_block bb;
 822
 823   FOR_EACH_BB (bb)
 824     {
 825       gimple_stmt_iterator gsi;
 826
 827       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 828         {
 829           gimple stmt = gsi_stmt (gsi);
 830           tree fndecl;
 831
 832           if (is_gimple_call (stmt)
 833               && gimple_call_lhs (stmt)
 834               && (fndecl = gimple_call_fndecl (stmt))
 835               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 836                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 837             {
 838               enum built_in_function code;
 839               bool md_code;
 840               tree arg1;
 841               gimple stmt1;
 842
 843               code = DECL_FUNCTION_CODE (fndecl);
 844               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 845
 846               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 847               if (!fndecl)
 848                 continue;
 849
 850               arg1 = gimple_call_arg (stmt, 0);
 851
 852               if (TREE_CODE (arg1) != SSA_NAME)
 853                 continue;
 854
 855               stmt1 = SSA_NAME_DEF_STMT (arg1);
 856
 857               if (is_gimple_assign (stmt1)
 858                   && gimple_assign_rhs_code (stmt1) == RDIV_EXPR)
 859                 {
 860                   tree arg10, arg11;
 861
 862                   arg10 = gimple_assign_rhs1 (stmt1);
 863                   arg11 = gimple_assign_rhs2 (stmt1);
 864
 865                   /* Swap operands of RDIV_EXPR.  */
 866                   gimple_assign_set_rhs1 (stmt1, arg11);
 867                   gimple_assign_set_rhs2 (stmt1, arg10);
 868                   fold_stmt_inplace (stmt1);
 869                   update_stmt (stmt1);
 870
 871                   gimple_call_set_fndecl (stmt, fndecl);
 872                   update_stmt (stmt);
 873                 }
 874             }
 875         }
 876     }
 877
 878   return 0;
 879 }
 880
 881 static bool
 882 gate_convert_to_rsqrt (void)
 883 {
 884   return flag_unsafe_math_optimizations && optimize;
 885 }
 886
 887 struct gimple_opt_pass pass_convert_to_rsqrt =
 888 {
 889  {
 890   GIMPLE_PASS,
 891   "rsqrt",                              /* name */
 892   gate_convert_to_rsqrt,                /* gate */
 893   execute_convert_to_rsqrt,             /* execute */
 894   NULL,                                 /* sub */
 895   NULL,                                 /* next */
 896   0,                                    /* static_pass_number */
 897   0,                                    /* tv_id */
 898   PROP_ssa,                             /* properties_required */
 899   0,                                    /* properties_provided */
 900   0,                                    /* properties_destroyed */
 901   0,                                    /* todo_flags_start */
 902   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 903     | TODO_verify_stmts                 /* todo_flags_finish */
 904  }
 905 };