gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 3, or (at your option) any
   9 later version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* Currently, the only mini-pass in this file tries to CSE reciprocal
  21    operations.  These are common in sequences such as this one:
  22
  23         modulus = sqrt(x*x + y*y + z*z);
  24         x = x / modulus;
  25         y = y / modulus;
  26         z = z / modulus;
  27
  28    that can be optimized to
  29
  30         modulus = sqrt(x*x + y*y + z*z);
  31         rmodulus = 1.0 / modulus;
  32         x = x * rmodulus;
  33         y = y * rmodulus;
  34         z = z * rmodulus;
  35
  36    We do this for loop invariant divisors, and with this pass whenever
  37    we notice that a division has the same divisor multiple times.
  38
  39    Of course, like in PRE, we don't insert a division if a dominator
  40    already has one.  However, this cannot be done as an extension of
  41    PRE for several reasons.
  42
  43    First of all, with some experiments it was found out that the
  44    transformation is not always useful if there are only two divisions
  45    hy the same divisor.  This is probably because modern processors
  46    can pipeline the divisions; on older, in-order processors it should
  47    still be effective to optimize two divisions by the same number.
  48    We make this a param, and it shall be called N in the remainder of
  49    this comment.
  50
  51    Second, if trapping math is active, we have less freedom on where
  52    to insert divisions: we can only do so in basic blocks that already
  53    contain one.  (If divisions don't trap, instead, we can insert
  54    divisions elsewhere, which will be in blocks that are common dominators
  55    of those that have the division).
  56
  57    We really don't want to compute the reciprocal unless a division will
  58    be found.  To do this, we won't insert the division in a basic block
  59    that has less than N divisions *post-dominating* it.
  60
  61    The algorithm constructs a subset of the dominator tree, holding the
  62    blocks containing the divisions and the common dominators to them,
  63    and walk it twice.  The first walk is in post-order, and it annotates
  64    each block with the number of divisions that post-dominate it: this
  65    gives information on where divisions can be inserted profitably.
  66    The second walk is in pre-order, and it inserts divisions as explained
  67    above, and replaces divisions by multiplications.
  68
  69    In the best case, the cost of the pass is O(n_statements).  In the
  70    worst-case, the cost is due to creating the dominator tree subset,
  71    with a cost of O(n_basic_blocks ^ 2); however this can only happen
  72    for n_statements / n_basic_blocks statements.  So, the amortized cost
  73    of creating the dominator tree subset is O(n_basic_blocks) and the
  74    worst-case cost of the pass is O(n_statements * n_basic_blocks).
  75
  76    More practically, the cost will be small because there are few
  77    divisions, and they tend to be in the same basic block, so insert_bb
  78    is called very few times.
  79
  80    If we did this using domwalk.c, an efficient implementation would have
  81    to work on all the variables in a single pass, because we could not
  82    work on just a subset of the dominator tree, as we do now, and the
  83    cost would also be something like O(n_statements * n_basic_blocks).
  84    The data structures would be more complex in order to work on all the
  85    variables in a single pass.  */
  86
  87 #include "config.h"
  88 #include "system.h"
  89 #include "coretypes.h"
  90 #include "tm.h"
  91 #include "flags.h"
  92 #include "tree.h"
  93 #include "tree-flow.h"
  94 #include "real.h"
  95 #include "timevar.h"
  96 #include "tree-pass.h"
  97 #include "alloc-pool.h"
  98 #include "basic-block.h"
  99 #include "target.h"
 100
 101
 102 /* This structure represents one basic block that either computes a
 103    division, or is a common dominator for basic block that compute a
 104    division.  */
 105 struct occurrence {
 106   /* The basic block represented by this structure.  */
 107   basic_block bb;
 108
 109   /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
 110      inserted in BB.  */
 111   tree recip_def;
 112
 113   /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
 114      was inserted in BB.  */
 115   gimple recip_def_stmt;
 116
 117   /* Pointer to a list of "struct occurrence"s for blocks dominated
 118      by BB.  */
 119   struct occurrence *children;
 120
 121   /* Pointer to the next "struct occurrence"s in the list of blocks
 122      sharing a common dominator.  */
 123   struct occurrence *next;
 124
 125   /* The number of divisions that are in BB before compute_merit.  The
 126      number of divisions that are in BB or post-dominate it after
 127      compute_merit.  */
 128   int num_divisions;
 129
 130   /* True if the basic block has a division, false if it is a common
 131      dominator for basic blocks that do.  If it is false and trapping
 132      math is active, BB is not a candidate for inserting a reciprocal.  */
 133   bool bb_has_division;
 134 };
 135
 136
 137 /* The instance of "struct occurrence" representing the highest
 138    interesting block in the dominator tree.  */
 139 static struct occurrence *occ_head;
 140
 141 /* Allocation pool for getting instances of "struct occurrence".  */
 142 static alloc_pool occ_pool;
 143
 144
 145
 146 /* Allocate and return a new struct occurrence for basic block BB, and
 147    whose children list is headed by CHILDREN.  */
 148 static struct occurrence *
 149 occ_new (basic_block bb, struct occurrence *children)
 150 {
 151   struct occurrence *occ;
 152
 153   bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
 154   memset (occ, 0, sizeof (struct occurrence));
 155
 156   occ->bb = bb;
 157   occ->children = children;
 158   return occ;
 159 }
 160
 161
 162 /* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
 163    list of "struct occurrence"s, one per basic block, having IDOM as
 164    their common dominator.
 165
 166    We try to insert NEW_OCC as deep as possible in the tree, and we also
 167    insert any other block that is a common dominator for BB and one
 168    block already in the tree.  */
 169
 170 static void
 171 insert_bb (struct occurrence *new_occ, basic_block idom,
 172            struct occurrence **p_head)
 173 {
 174   struct occurrence *occ, **p_occ;
 175
 176   for (p_occ = p_head; (occ = *p_occ) != NULL; )
 177     {
 178       basic_block bb = new_occ->bb, occ_bb = occ->bb;
 179       basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
 180       if (dom == bb)
 181         {
 182           /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
 183              from its list.  */
 184           *p_occ = occ->next;
 185           occ->next = new_occ->children;
 186           new_occ->children = occ;
 187
 188           /* Try the next block (it may as well be dominated by BB).  */
 189         }
 190
 191       else if (dom == occ_bb)
 192         {
 193           /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
 194           insert_bb (new_occ, dom, &occ->children);
 195           return;
 196         }
 197
 198       else if (dom != idom)
 199         {
 200           gcc_assert (!dom->aux);
 201
 202           /* There is a dominator between IDOM and BB, add it and make
 203              two children out of NEW_OCC and OCC.  First, remove OCC from
 204              its list.  */
 205           *p_occ = occ->next;
 206           new_occ->next = occ;
 207           occ->next = NULL;
 208
 209           /* None of the previous blocks has DOM as a dominator: if we tail
 210              recursed, we would reexamine them uselessly. Just switch BB with
 211              DOM, and go on looking for blocks dominated by DOM.  */
 212           new_occ = occ_new (dom, new_occ);
 213         }
 214
 215       else
 216         {
 217           /* Nothing special, go on with the next element.  */
 218           p_occ = &occ->next;
 219         }
 220     }
 221
 222   /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
 223   new_occ->next = *p_head;
 224   *p_head = new_occ;
 225 }
 226
 227 /* Register that we found a division in BB.  */
 228
 229 static inline void
 230 register_division_in (basic_block bb)
 231 {
 232   struct occurrence *occ;
 233
 234   occ = (struct occurrence *) bb->aux;
 235   if (!occ)
 236     {
 237       occ = occ_new (bb, NULL);
 238       insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
 239     }
 240
 241   occ->bb_has_division = true;
 242   occ->num_divisions++;
 243 }
 244
 245
 246 /* Compute the number of divisions that postdominate each block in OCC and
 247    its children.  */
 248
 249 static void
 250 compute_merit (struct occurrence *occ)
 251 {
 252   struct occurrence *occ_child;
 253   basic_block dom = occ->bb;
 254
 255   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 256     {
 257       basic_block bb;
 258       if (occ_child->children)
 259         compute_merit (occ_child);
 260
 261       if (flag_exceptions)
 262         bb = single_noncomplex_succ (dom);
 263       else
 264         bb = dom;
 265
 266       if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
 267         occ->num_divisions += occ_child->num_divisions;
 268     }
 269 }
 270
 271
 272 /* Return whether USE_STMT is a floating-point division by DEF.  */
 273 static inline bool
 274 is_division_by (gimple use_stmt, tree def)
 275 {
 276   return is_gimple_assign (use_stmt)
 277          && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
 278          && gimple_assign_rhs2 (use_stmt) == def
 279          /* Do not recognize x / x as valid division, as we are getting
 280             confused later by replacing all immediate uses x in such
 281             a stmt.  */
 282          && gimple_assign_rhs1 (use_stmt) != def;
 283 }
 284
 285 /* Walk the subset of the dominator tree rooted at OCC, setting the
 286    RECIP_DEF field to a definition of 1.0 / DEF that can be used in
 287    the given basic block.  The field may be left NULL, of course,
 288    if it is not possible or profitable to do the optimization.
 289
 290    DEF_BSI is an iterator pointing at the statement defining DEF.
 291    If RECIP_DEF is set, a dominator already has a computation that can
 292    be used.  */
 293
 294 static void
 295 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
 296                     tree def, tree recip_def, int threshold)
 297 {
 298   tree type;
 299   gimple new_stmt;
 300   gimple_stmt_iterator gsi;
 301   struct occurrence *occ_child;
 302
 303   if (!recip_def
 304       && (occ->bb_has_division || !flag_trapping_math)
 305       && occ->num_divisions >= threshold)
 306     {
 307       /* Make a variable with the replacement and substitute it.  */
 308       type = TREE_TYPE (def);
 309       recip_def = make_rename_temp (type, "reciptmp");
 310       new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
 311                                                build_one_cst (type), def);
 312
 313       if (occ->bb_has_division)
 314         {
 315           /* Case 1: insert before an existing division.  */
 316           gsi = gsi_after_labels (occ->bb);
 317           while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
 318             gsi_next (&gsi);
 319
 320           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 321         }
 322       else if (def_gsi && occ->bb == def_gsi->bb)
 323         {
 324           /* Case 2: insert right after the definition.  Note that this will
 325              never happen if the definition statement can throw, because in
 326              that case the sole successor of the statement's basic block will
 327              dominate all the uses as well.  */
 328           gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
 329         }
 330       else
 331         {
 332           /* Case 3: insert in a basic block not containing defs/uses.  */
 333           gsi = gsi_after_labels (occ->bb);
 334           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 335         }
 336
 337       occ->recip_def_stmt = new_stmt;
 338     }
 339
 340   occ->recip_def = recip_def;
 341   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 342     insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
 343 }
 344
 345
 346 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 347    possible.  */
 348
 349 static inline void
 350 replace_reciprocal (use_operand_p use_p)
 351 {
 352   gimple use_stmt = USE_STMT (use_p);
 353   basic_block bb = gimple_bb (use_stmt);
 354   struct occurrence *occ = (struct occurrence *) bb->aux;
 355
 356   if (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;
 532
 533                   code = DECL_FUNCTION_CODE (fndecl);
 534                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 535
 536                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 537                   if (!fndecl)
 538                     continue;
 539
 540                   gimple_call_set_fndecl (stmt1, fndecl);
 541                   update_stmt (stmt1);
 542
 543                   gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 544                   fold_stmt_inplace (stmt);
 545                   update_stmt (stmt);
 546                 }
 547             }
 548         }
 549     }
 550
 551   free_dominance_info (CDI_DOMINATORS);
 552   free_dominance_info (CDI_POST_DOMINATORS);
 553   free_alloc_pool (occ_pool);
 554   return 0;
 555 }
 556
 557 struct gimple_opt_pass pass_cse_reciprocals =
 558 {
 559  {
 560   GIMPLE_PASS,
 561   "recip",                              /* name */
 562   gate_cse_reciprocals,                 /* gate */
 563   execute_cse_reciprocals,              /* execute */
 564   NULL,                                 /* sub */
 565   NULL,                                 /* next */
 566   0,                                    /* static_pass_number */
 567   0,                                    /* tv_id */
 568   PROP_ssa,                             /* properties_required */
 569   0,                                    /* properties_provided */
 570   0,                                    /* properties_destroyed */
 571   0,                                    /* todo_flags_start */
 572   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 573     | TODO_verify_stmts                /* todo_flags_finish */
 574  }
 575 };
 576
 577 /* Records an occurrence at statement USE_STMT in the vector of trees
 578    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 579    is not yet initialized.  Returns true if the occurrence was pushed on
 580    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 581    statements in the vector.  */
 582
 583 static bool
 584 maybe_record_sincos (VEC(gimple, heap) **stmts,
 585                      basic_block *top_bb, gimple use_stmt)
 586 {
 587   basic_block use_bb = gimple_bb (use_stmt);
 588   if (*top_bb
 589       && (*top_bb == use_bb
 590           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 591     VEC_safe_push (gimple, heap, *stmts, use_stmt);
 592   else if (!*top_bb
 593            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 594     {
 595       VEC_safe_push (gimple, heap, *stmts, use_stmt);
 596       *top_bb = use_bb;
 597     }
 598   else
 599     return false;
 600
 601   return true;
 602 }
 603
 604 /* Look for sin, cos and cexpi calls with the same argument NAME and
 605    create a single call to cexpi CSEing the result in this case.
 606    We first walk over all immediate uses of the argument collecting
 607    statements that we can CSE in a vector and in a second pass replace
 608    the statement rhs with a REALPART or IMAGPART expression on the
 609    result of the cexpi call we insert before the use statement that
 610    dominates all other candidates.  */
 611
 612 static void
 613 execute_cse_sincos_1 (tree name)
 614 {
 615   gimple_stmt_iterator gsi;
 616   imm_use_iterator use_iter;
 617   tree fndecl, res, type;
 618   gimple def_stmt, use_stmt, stmt;
 619   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 620   VEC(gimple, 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 (gimple_code (use_stmt) != GIMPLE_CALL
 628           || !gimple_call_lhs (use_stmt)
 629           || !(fndecl = gimple_call_fndecl (use_stmt))
 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(gimple, 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   stmt = gimple_build_call (fndecl, 1, name);
 664   gimple_call_set_lhs (stmt, res);
 665
 666   def_stmt = SSA_NAME_DEF_STMT (name);
 667   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 668       && gimple_code (def_stmt) != GIMPLE_PHI
 669       && gimple_bb (def_stmt) == top_bb)
 670     {
 671       gsi = gsi_for_stmt (def_stmt);
 672       gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 673     }
 674   else
 675     {
 676       gsi = gsi_after_labels (top_bb);
 677       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 678     }
 679   update_stmt (stmt);
 680
 681   /* And adjust the recorded old call sites.  */
 682   for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
 683     {
 684       tree rhs = NULL;
 685       fndecl = gimple_call_fndecl (use_stmt);
 686
 687       switch (DECL_FUNCTION_CODE (fndecl))
 688         {
 689         CASE_FLT_FN (BUILT_IN_COS):
 690           rhs = fold_build1 (REALPART_EXPR, type, res);
 691           break;
 692
 693         CASE_FLT_FN (BUILT_IN_SIN):
 694           rhs = fold_build1 (IMAGPART_EXPR, type, res);
 695           break;
 696
 697         CASE_FLT_FN (BUILT_IN_CEXPI):
 698           rhs = res;
 699           break;
 700
 701         default:;
 702           gcc_unreachable ();
 703         }
 704
 705         /* Replace call with a copy.  */
 706         stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
 707
 708         gsi = gsi_for_stmt (use_stmt);
 709         gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 710         gsi_remove (&gsi, true);
 711     }
 712
 713   VEC_free(gimple, heap, stmts);
 714 }
 715
 716 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 717    on the SSA_NAME argument of each of them.  */
 718
 719 static unsigned int
 720 execute_cse_sincos (void)
 721 {
 722   basic_block bb;
 723
 724   calculate_dominance_info (CDI_DOMINATORS);
 725
 726   FOR_EACH_BB (bb)
 727     {
 728       gimple_stmt_iterator gsi;
 729
 730       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 731         {
 732           gimple stmt = gsi_stmt (gsi);
 733           tree fndecl;
 734
 735           if (is_gimple_call (stmt)
 736               && gimple_call_lhs (stmt)
 737               && (fndecl = gimple_call_fndecl (stmt))
 738               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 739             {
 740               tree arg;
 741
 742               switch (DECL_FUNCTION_CODE (fndecl))
 743                 {
 744                 CASE_FLT_FN (BUILT_IN_COS):
 745                 CASE_FLT_FN (BUILT_IN_SIN):
 746                 CASE_FLT_FN (BUILT_IN_CEXPI):
 747                   arg = gimple_call_arg (stmt, 0);
 748                   if (TREE_CODE (arg) == SSA_NAME)
 749                     execute_cse_sincos_1 (arg);
 750                   break;
 751
 752                 default:;
 753                 }
 754             }
 755         }
 756     }
 757
 758   free_dominance_info (CDI_DOMINATORS);
 759   return 0;
 760 }
 761
 762 static bool
 763 gate_cse_sincos (void)
 764 {
 765   /* Make sure we have either sincos or cexp.  */
 766   return (TARGET_HAS_SINCOS
 767           || TARGET_C99_FUNCTIONS)
 768          && optimize;
 769 }
 770
 771 struct gimple_opt_pass pass_cse_sincos =
 772 {
 773  {
 774   GIMPLE_PASS,
 775   "sincos",                             /* name */
 776   gate_cse_sincos,                      /* gate */
 777   execute_cse_sincos,                   /* execute */
 778   NULL,                                 /* sub */
 779   NULL,                                 /* next */
 780   0,                                    /* static_pass_number */
 781   0,                                    /* tv_id */
 782   PROP_ssa,                             /* properties_required */
 783   0,                                    /* properties_provided */
 784   0,                                    /* properties_destroyed */
 785   0,                                    /* todo_flags_start */
 786   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 787     | TODO_verify_stmts                 /* todo_flags_finish */
 788  }
 789 };
 790
 791 /* Find all expressions in the form of sqrt(a/b) and
 792    convert them to rsqrt(b/a).  */
 793
 794 static unsigned int
 795 execute_convert_to_rsqrt (void)
 796 {
 797   basic_block bb;
 798
 799   FOR_EACH_BB (bb)
 800     {
 801       gimple_stmt_iterator gsi;
 802
 803       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 804         {
 805           gimple stmt = gsi_stmt (gsi);
 806           tree fndecl;
 807
 808           if (is_gimple_call (stmt)
 809               && gimple_call_lhs (stmt)
 810               && (fndecl = gimple_call_fndecl (stmt))
 811               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 812                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 813             {
 814               enum built_in_function code;
 815               bool md_code;
 816               tree arg1;
 817               gimple stmt1;
 818
 819               code = DECL_FUNCTION_CODE (fndecl);
 820               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 821
 822               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 823               if (!fndecl)
 824                 continue;
 825
 826               arg1 = gimple_call_arg (stmt, 0);
 827
 828               if (TREE_CODE (arg1) != SSA_NAME)
 829                 continue;
 830
 831               stmt1 = SSA_NAME_DEF_STMT (arg1);
 832
 833               if (is_gimple_assign (stmt1)
 834                   && gimple_assign_rhs_code (stmt1) == RDIV_EXPR)
 835                 {
 836                   tree arg10, arg11;
 837
 838                   arg10 = gimple_assign_rhs1 (stmt1);
 839                   arg11 = gimple_assign_rhs2 (stmt1);
 840
 841                   /* Swap operands of RDIV_EXPR.  */
 842                   gimple_assign_set_rhs1 (stmt1, arg11);
 843                   gimple_assign_set_rhs2 (stmt1, arg10);
 844                   fold_stmt_inplace (stmt1);
 845                   update_stmt (stmt1);
 846
 847                   gimple_call_set_fndecl (stmt, fndecl);
 848                   update_stmt (stmt);
 849                 }
 850             }
 851         }
 852     }
 853
 854   return 0;
 855 }
 856
 857 static bool
 858 gate_convert_to_rsqrt (void)
 859 {
 860   return flag_unsafe_math_optimizations && optimize;
 861 }
 862
 863 struct gimple_opt_pass pass_convert_to_rsqrt =
 864 {
 865  {
 866   GIMPLE_PASS,
 867   "rsqrt",                              /* name */
 868   gate_convert_to_rsqrt,                /* gate */
 869   execute_convert_to_rsqrt,             /* execute */
 870   NULL,                                 /* sub */
 871   NULL,                                 /* next */
 872   0,                                    /* static_pass_number */
 873   0,                                    /* tv_id */
 874   PROP_ssa,                             /* properties_required */
 875   0,                                    /* properties_provided */
 876   0,                                    /* properties_destroyed */
 877   0,                                    /* todo_flags_start */
 878   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 879     | TODO_verify_stmts                 /* todo_flags_finish */
 880  }
 881 };