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_MODIFY_STMT for a reciprocal computation that
 114      was inserted in BB.  */
 115   tree 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 (tree use_stmt, tree def)
 275 {
 276   return TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
 277          && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == RDIV_EXPR
 278          && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 1) == 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          && TREE_OPERAND (GIMPLE_STMT_OPERAND (use_stmt, 1), 0) != 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 (block_stmt_iterator *def_bsi, struct occurrence *occ,
 296                     tree def, tree recip_def, int threshold)
 297 {
 298   tree type, new_stmt;
 299   block_stmt_iterator bsi;
 300   struct occurrence *occ_child;
 301
 302   if (!recip_def
 303       && (occ->bb_has_division || !flag_trapping_math)
 304       && occ->num_divisions >= threshold)
 305     {
 306       /* Make a variable with the replacement and substitute it.  */
 307       type = TREE_TYPE (def);
 308       recip_def = make_rename_temp (type, "reciptmp");
 309       new_stmt = build_gimple_modify_stmt (recip_def,
 310                                            fold_build2 (RDIV_EXPR, type,
 311                                                         build_one_cst (type),
 312                                                         def));
 313
 314
 315       if (occ->bb_has_division)
 316         {
 317           /* Case 1: insert before an existing division.  */
 318           bsi = bsi_after_labels (occ->bb);
 319           while (!bsi_end_p (bsi) && !is_division_by (bsi_stmt (bsi), def))
 320             bsi_next (&bsi);
 321
 322           bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
 323         }
 324       else if (def_bsi && occ->bb == def_bsi->bb)
 325         {
 326           /* Case 2: insert right after the definition.  Note that this will
 327              never happen if the definition statement can throw, because in
 328              that case the sole successor of the statement's basic block will
 329              dominate all the uses as well.  */
 330           bsi_insert_after (def_bsi, new_stmt, BSI_NEW_STMT);
 331         }
 332       else
 333         {
 334           /* Case 3: insert in a basic block not containing defs/uses.  */
 335           bsi = bsi_after_labels (occ->bb);
 336           bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
 337         }
 338
 339       occ->recip_def_stmt = new_stmt;
 340     }
 341
 342   occ->recip_def = recip_def;
 343   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 344     insert_reciprocals (def_bsi, occ_child, def, recip_def, threshold);
 345 }
 346
 347
 348 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 349    possible.  */
 350
 351 static inline void
 352 replace_reciprocal (use_operand_p use_p)
 353 {
 354   tree use_stmt = USE_STMT (use_p);
 355   basic_block bb = bb_for_stmt (use_stmt);
 356   struct occurrence *occ = (struct occurrence *) bb->aux;
 357
 358   if (occ->recip_def && use_stmt != occ->recip_def_stmt)
 359     {
 360       TREE_SET_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1), MULT_EXPR);
 361       SET_USE (use_p, occ->recip_def);
 362       fold_stmt_inplace (use_stmt);
 363       update_stmt (use_stmt);
 364     }
 365 }
 366
 367
 368 /* Free OCC and return one more "struct occurrence" to be freed.  */
 369
 370 static struct occurrence *
 371 free_bb (struct occurrence *occ)
 372 {
 373   struct occurrence *child, *next;
 374
 375   /* First get the two pointers hanging off OCC.  */
 376   next = occ->next;
 377   child = occ->children;
 378   occ->bb->aux = NULL;
 379   pool_free (occ_pool, occ);
 380
 381   /* Now ensure that we don't recurse unless it is necessary.  */
 382   if (!child)
 383     return next;
 384   else
 385     {
 386       while (next)
 387         next = free_bb (next);
 388
 389       return child;
 390     }
 391 }
 392
 393
 394 /* Look for floating-point divisions among DEF's uses, and try to
 395    replace them by multiplications with the reciprocal.  Add
 396    as many statements computing the reciprocal as needed.
 397
 398    DEF must be a GIMPLE register of a floating-point type.  */
 399
 400 static void
 401 execute_cse_reciprocals_1 (block_stmt_iterator *def_bsi, tree def)
 402 {
 403   use_operand_p use_p;
 404   imm_use_iterator use_iter;
 405   struct occurrence *occ;
 406   int count = 0, threshold;
 407
 408   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 409
 410   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 411     {
 412       tree use_stmt = USE_STMT (use_p);
 413       if (is_division_by (use_stmt, def))
 414         {
 415           register_division_in (bb_for_stmt (use_stmt));
 416           count++;
 417         }
 418     }
 419
 420   /* Do the expensive part only if we can hope to optimize something.  */
 421   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 422   if (count >= threshold)
 423     {
 424       tree use_stmt;
 425       for (occ = occ_head; occ; occ = occ->next)
 426         {
 427           compute_merit (occ);
 428           insert_reciprocals (def_bsi, occ, def, NULL, threshold);
 429         }
 430
 431       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 432         {
 433           if (is_division_by (use_stmt, def))
 434             {
 435               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 436                 replace_reciprocal (use_p);
 437             }
 438         }
 439     }
 440
 441   for (occ = occ_head; occ; )
 442     occ = free_bb (occ);
 443
 444   occ_head = NULL;
 445 }
 446
 447 static bool
 448 gate_cse_reciprocals (void)
 449 {
 450   return optimize && !optimize_size && flag_reciprocal_math;
 451 }
 452
 453 /* Go through all the floating-point SSA_NAMEs, and call
 454    execute_cse_reciprocals_1 on each of them.  */
 455 static unsigned int
 456 execute_cse_reciprocals (void)
 457 {
 458   basic_block bb;
 459   tree arg;
 460
 461   occ_pool = create_alloc_pool ("dominators for recip",
 462                                 sizeof (struct occurrence),
 463                                 n_basic_blocks / 3 + 1);
 464
 465   calculate_dominance_info (CDI_DOMINATORS);
 466   calculate_dominance_info (CDI_POST_DOMINATORS);
 467
 468 #ifdef ENABLE_CHECKING
 469   FOR_EACH_BB (bb)
 470     gcc_assert (!bb->aux);
 471 #endif
 472
 473   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 474     if (gimple_default_def (cfun, arg)
 475         && FLOAT_TYPE_P (TREE_TYPE (arg))
 476         && is_gimple_reg (arg))
 477       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 478
 479   FOR_EACH_BB (bb)
 480     {
 481       block_stmt_iterator bsi;
 482       tree phi, def;
 483
 484       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 485         {
 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 (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 493         {
 494           tree stmt = bsi_stmt (bsi);
 495
 496           if (TREE_CODE (stmt) == GIMPLE_MODIFY_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 (&bsi, def);
 501         }
 502
 503       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 504       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 505         {
 506           tree stmt = bsi_stmt (bsi);
 507           tree fndecl;
 508
 509           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 510               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == RDIV_EXPR)
 511             {
 512               tree arg1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 1);
 513               tree stmt1;
 514
 515               if (TREE_CODE (arg1) != SSA_NAME)
 516                 continue;
 517
 518               stmt1 = SSA_NAME_DEF_STMT (arg1);
 519
 520               if (TREE_CODE (stmt1) == GIMPLE_MODIFY_STMT
 521                   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1)) == CALL_EXPR
 522                   && (fndecl
 523                       = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt1, 1)))
 524                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 525                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 526                 {
 527                   enum built_in_function code;
 528                   bool md_code;
 529                   tree arg10;
 530                   tree tmp;
 531
 532                   code = DECL_FUNCTION_CODE (fndecl);
 533                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 534
 535                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 536                   if (!fndecl)
 537                     continue;
 538
 539                   arg10 = CALL_EXPR_ARG (GIMPLE_STMT_OPERAND (stmt1, 1), 0);
 540                   tmp = build_call_expr (fndecl, 1, arg10);
 541                   GIMPLE_STMT_OPERAND (stmt1, 1) = tmp;
 542                   update_stmt (stmt1);
 543
 544                   TREE_SET_CODE (GIMPLE_STMT_OPERAND (stmt, 1), MULT_EXPR);
 545                   fold_stmt_inplace (stmt);
 546                   update_stmt (stmt);
 547                 }
 548             }
 549         }
 550     }
 551
 552   free_dominance_info (CDI_DOMINATORS);
 553   free_dominance_info (CDI_POST_DOMINATORS);
 554   free_alloc_pool (occ_pool);
 555   return 0;
 556 }
 557
 558 struct gimple_opt_pass pass_cse_reciprocals =
 559 {
 560  {
 561   GIMPLE_PASS,
 562   "recip",                              /* name */
 563   gate_cse_reciprocals,                 /* gate */
 564   execute_cse_reciprocals,              /* execute */
 565   NULL,                                 /* sub */
 566   NULL,                                 /* next */
 567   0,                                    /* static_pass_number */
 568   0,                                    /* tv_id */
 569   PROP_ssa,                             /* properties_required */
 570   0,                                    /* properties_provided */
 571   0,                                    /* properties_destroyed */
 572   0,                                    /* todo_flags_start */
 573   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 574     | TODO_verify_stmts                /* todo_flags_finish */
 575  }
 576 };
 577
 578 /* Records an occurrence at statement USE_STMT in the vector of trees
 579    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 580    is not yet initialized.  Returns true if the occurrence was pushed on
 581    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 582    statements in the vector.  */
 583
 584 static bool
 585 maybe_record_sincos (VEC(tree, heap) **stmts,
 586                      basic_block *top_bb, tree use_stmt)
 587 {
 588   basic_block use_bb = bb_for_stmt (use_stmt);
 589   if (*top_bb
 590       && (*top_bb == use_bb
 591           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 592     VEC_safe_push (tree, heap, *stmts, use_stmt);
 593   else if (!*top_bb
 594            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 595     {
 596       VEC_safe_push (tree, heap, *stmts, use_stmt);
 597       *top_bb = use_bb;
 598     }
 599   else
 600     return false;
 601
 602   return true;
 603 }
 604
 605 /* Look for sin, cos and cexpi calls with the same argument NAME and
 606    create a single call to cexpi CSEing the result in this case.
 607    We first walk over all immediate uses of the argument collecting
 608    statements that we can CSE in a vector and in a second pass replace
 609    the statement rhs with a REALPART or IMAGPART expression on the
 610    result of the cexpi call we insert before the use statement that
 611    dominates all other candidates.  */
 612
 613 static void
 614 execute_cse_sincos_1 (tree name)
 615 {
 616   block_stmt_iterator bsi;
 617   imm_use_iterator use_iter;
 618   tree def_stmt, use_stmt, fndecl, res, call, stmt, type;
 619   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 620   VEC(tree, heap) *stmts = NULL;
 621   basic_block top_bb = NULL;
 622   int i;
 623
 624   type = TREE_TYPE (name);
 625   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 626     {
 627       if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT
 628           || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) != CALL_EXPR
 629           || !(fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1)))
 630           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 631         continue;
 632
 633       switch (DECL_FUNCTION_CODE (fndecl))
 634         {
 635         CASE_FLT_FN (BUILT_IN_COS):
 636           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 637           break;
 638
 639         CASE_FLT_FN (BUILT_IN_SIN):
 640           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 641           break;
 642
 643         CASE_FLT_FN (BUILT_IN_CEXPI):
 644           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 645           break;
 646
 647         default:;
 648         }
 649     }
 650
 651   if (seen_cos + seen_sin + seen_cexpi <= 1)
 652     {
 653       VEC_free(tree, heap, stmts);
 654       return;
 655     }
 656
 657   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 658      the name def statement.  */
 659   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 660   if (!fndecl)
 661     return;
 662   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 663   call = build_call_expr (fndecl, 1, name);
 664   stmt = build_gimple_modify_stmt (res, call);
 665   def_stmt = SSA_NAME_DEF_STMT (name);
 666   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 667       && TREE_CODE (def_stmt) != PHI_NODE
 668       && bb_for_stmt (def_stmt) == top_bb)
 669     {
 670       bsi = bsi_for_stmt (def_stmt);
 671       bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
 672     }
 673   else
 674     {
 675       bsi = bsi_after_labels (top_bb);
 676       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 677     }
 678   update_stmt (stmt);
 679
 680   /* And adjust the recorded old call sites.  */
 681   for (i = 0; VEC_iterate(tree, stmts, i, use_stmt); ++i)
 682     {
 683       fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1));
 684       switch (DECL_FUNCTION_CODE (fndecl))
 685         {
 686         CASE_FLT_FN (BUILT_IN_COS):
 687           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (REALPART_EXPR,
 688                                                            type, res);
 689           break;
 690
 691         CASE_FLT_FN (BUILT_IN_SIN):
 692           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (IMAGPART_EXPR,
 693                                                            type, res);
 694           break;
 695
 696         CASE_FLT_FN (BUILT_IN_CEXPI):
 697           GIMPLE_STMT_OPERAND (use_stmt, 1) = res;
 698           break;
 699
 700         default:;
 701           gcc_unreachable ();
 702         }
 703
 704         update_stmt (use_stmt);
 705     }
 706
 707   VEC_free(tree, heap, stmts);
 708 }
 709
 710 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 711    on the SSA_NAME argument of each of them.  */
 712
 713 static unsigned int
 714 execute_cse_sincos (void)
 715 {
 716   basic_block bb;
 717
 718   calculate_dominance_info (CDI_DOMINATORS);
 719
 720   FOR_EACH_BB (bb)
 721     {
 722       block_stmt_iterator bsi;
 723
 724       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 725         {
 726           tree stmt = bsi_stmt (bsi);
 727           tree fndecl;
 728
 729           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 730               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 731               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 732               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 733             {
 734               tree arg;
 735
 736               switch (DECL_FUNCTION_CODE (fndecl))
 737                 {
 738                 CASE_FLT_FN (BUILT_IN_COS):
 739                 CASE_FLT_FN (BUILT_IN_SIN):
 740                 CASE_FLT_FN (BUILT_IN_CEXPI):
 741                   arg = GIMPLE_STMT_OPERAND (stmt, 1);
 742                   arg = CALL_EXPR_ARG (arg, 0);
 743                   if (TREE_CODE (arg) == SSA_NAME)
 744                     execute_cse_sincos_1 (arg);
 745                   break;
 746
 747                 default:;
 748                 }
 749             }
 750         }
 751     }
 752
 753   free_dominance_info (CDI_DOMINATORS);
 754   return 0;
 755 }
 756
 757 static bool
 758 gate_cse_sincos (void)
 759 {
 760   /* Make sure we have either sincos or cexp.  */
 761   return (TARGET_HAS_SINCOS
 762           || TARGET_C99_FUNCTIONS)
 763          && optimize;
 764 }
 765
 766 struct gimple_opt_pass pass_cse_sincos =
 767 {
 768  {
 769   GIMPLE_PASS,
 770   "sincos",                             /* name */
 771   gate_cse_sincos,                      /* gate */
 772   execute_cse_sincos,                   /* execute */
 773   NULL,                                 /* sub */
 774   NULL,                                 /* next */
 775   0,                                    /* static_pass_number */
 776   0,                                    /* tv_id */
 777   PROP_ssa,                             /* properties_required */
 778   0,                                    /* properties_provided */
 779   0,                                    /* properties_destroyed */
 780   0,                                    /* todo_flags_start */
 781   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 782     | TODO_verify_stmts                 /* todo_flags_finish */
 783  }
 784 };
 785
 786 /* Find all expressions in the form of sqrt(a/b) and
 787    convert them to rsqrt(b/a).  */
 788
 789 static unsigned int
 790 execute_convert_to_rsqrt (void)
 791 {
 792   basic_block bb;
 793
 794   FOR_EACH_BB (bb)
 795     {
 796       block_stmt_iterator bsi;
 797
 798       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 799         {
 800           tree stmt = bsi_stmt (bsi);
 801           tree fndecl;
 802
 803           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 804               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 805               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 806               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 807                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 808             {
 809               enum built_in_function code;
 810               bool md_code;
 811               tree arg1;
 812               tree stmt1;
 813
 814               code = DECL_FUNCTION_CODE (fndecl);
 815               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 816
 817               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 818               if (!fndecl)
 819                 continue;
 820
 821               arg1 = CALL_EXPR_ARG (GIMPLE_STMT_OPERAND (stmt, 1), 0);
 822
 823               if (TREE_CODE (arg1) != SSA_NAME)
 824                 continue;
 825
 826               stmt1 = SSA_NAME_DEF_STMT (arg1);
 827
 828               if (TREE_CODE (stmt1) == GIMPLE_MODIFY_STMT
 829                   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1)) == RDIV_EXPR)
 830                 {
 831                   tree arg10, arg11;
 832                   tree tmp;
 833
 834                   arg10 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0);
 835                   arg11 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1);
 836
 837                   /* Swap operands of RDIV_EXPR.  */
 838                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0) = arg11;
 839                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1) = arg10;
 840                   fold_stmt_inplace (stmt1);
 841                   update_stmt (stmt1);
 842
 843                   tmp = build_call_expr (fndecl, 1, arg1);
 844                   GIMPLE_STMT_OPERAND (stmt, 1) = tmp;
 845                   update_stmt (stmt);
 846                 }
 847             }
 848         }
 849     }
 850
 851   return 0;
 852 }
 853
 854 static bool
 855 gate_convert_to_rsqrt (void)
 856 {
 857   return flag_unsafe_math_optimizations && optimize;
 858 }
 859
 860 struct gimple_opt_pass pass_convert_to_rsqrt =
 861 {
 862  {
 863   GIMPLE_PASS,
 864   "rsqrt",                              /* name */
 865   gate_convert_to_rsqrt,                /* gate */
 866   execute_convert_to_rsqrt,             /* execute */
 867   NULL,                                 /* sub */
 868   NULL,                                 /* next */
 869   0,                                    /* static_pass_number */
 870   0,                                    /* tv_id */
 871   PROP_ssa,                             /* properties_required */
 872   0,                                    /* properties_provided */
 873   0,                                    /* properties_destroyed */
 874   0,                                    /* todo_flags_start */
 875   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 876     | TODO_verify_stmts                 /* todo_flags_finish */
 877  }
 878 };