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