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 tree_opt_pass pass_cse_reciprocals =
 559 {
 560   "recip",                              /* name */
 561   gate_cse_reciprocals,                 /* gate */
 562   execute_cse_reciprocals,              /* execute */
 563   NULL,                                 /* sub */
 564   NULL,                                 /* next */
 565   0,                                    /* static_pass_number */
 566   0,                                    /* tv_id */
 567   PROP_ssa,                             /* properties_required */
 568   0,                                    /* properties_provided */
 569   0,                                    /* properties_destroyed */
 570   0,                                    /* todo_flags_start */
 571   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 572     | TODO_verify_stmts,                /* todo_flags_finish */
 573   0                                     /* letter */
 574 };
 575
 576 /* Records an occurrence at statement USE_STMT in the vector of trees
 577    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 578    is not yet initialized.  Returns true if the occurrence was pushed on
 579    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 580    statements in the vector.  */
 581
 582 static bool
 583 maybe_record_sincos (VEC(tree, heap) **stmts,
 584                      basic_block *top_bb, tree use_stmt)
 585 {
 586   basic_block use_bb = bb_for_stmt (use_stmt);
 587   if (*top_bb
 588       && (*top_bb == use_bb
 589           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 590     VEC_safe_push (tree, heap, *stmts, use_stmt);
 591   else if (!*top_bb
 592            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 593     {
 594       VEC_safe_push (tree, heap, *stmts, use_stmt);
 595       *top_bb = use_bb;
 596     }
 597   else
 598     return false;
 599
 600   return true;
 601 }
 602
 603 /* Look for sin, cos and cexpi calls with the same argument NAME and
 604    create a single call to cexpi CSEing the result in this case.
 605    We first walk over all immediate uses of the argument collecting
 606    statements that we can CSE in a vector and in a second pass replace
 607    the statement rhs with a REALPART or IMAGPART expression on the
 608    result of the cexpi call we insert before the use statement that
 609    dominates all other candidates.  */
 610
 611 static void
 612 execute_cse_sincos_1 (tree name)
 613 {
 614   block_stmt_iterator bsi;
 615   imm_use_iterator use_iter;
 616   tree def_stmt, use_stmt, fndecl, res, call, stmt, type;
 617   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 618   VEC(tree, heap) *stmts = NULL;
 619   basic_block top_bb = NULL;
 620   int i;
 621
 622   type = TREE_TYPE (name);
 623   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 624     {
 625       if (TREE_CODE (use_stmt) != GIMPLE_MODIFY_STMT
 626           || TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) != CALL_EXPR
 627           || !(fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1)))
 628           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 629         continue;
 630
 631       switch (DECL_FUNCTION_CODE (fndecl))
 632         {
 633         CASE_FLT_FN (BUILT_IN_COS):
 634           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 635           break;
 636
 637         CASE_FLT_FN (BUILT_IN_SIN):
 638           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 639           break;
 640
 641         CASE_FLT_FN (BUILT_IN_CEXPI):
 642           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 643           break;
 644
 645         default:;
 646         }
 647     }
 648
 649   if (seen_cos + seen_sin + seen_cexpi <= 1)
 650     {
 651       VEC_free(tree, heap, stmts);
 652       return;
 653     }
 654
 655   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 656      the name def statement.  */
 657   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 658   if (!fndecl)
 659     return;
 660   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 661   call = build_call_expr (fndecl, 1, name);
 662   stmt = build_gimple_modify_stmt (res, call);
 663   def_stmt = SSA_NAME_DEF_STMT (name);
 664   if (bb_for_stmt (def_stmt) == top_bb
 665       && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT)
 666     {
 667       bsi = bsi_for_stmt (def_stmt);
 668       bsi_insert_after (&bsi, stmt, BSI_SAME_STMT);
 669     }
 670   else
 671     {
 672       bsi = bsi_after_labels (top_bb);
 673       bsi_insert_before (&bsi, stmt, BSI_SAME_STMT);
 674     }
 675   update_stmt (stmt);
 676
 677   /* And adjust the recorded old call sites.  */
 678   for (i = 0; VEC_iterate(tree, stmts, i, use_stmt); ++i)
 679     {
 680       fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (use_stmt, 1));
 681       switch (DECL_FUNCTION_CODE (fndecl))
 682         {
 683         CASE_FLT_FN (BUILT_IN_COS):
 684           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (REALPART_EXPR,
 685                                                            type, res);
 686           break;
 687
 688         CASE_FLT_FN (BUILT_IN_SIN):
 689           GIMPLE_STMT_OPERAND (use_stmt, 1) = fold_build1 (IMAGPART_EXPR,
 690                                                            type, res);
 691           break;
 692
 693         CASE_FLT_FN (BUILT_IN_CEXPI):
 694           GIMPLE_STMT_OPERAND (use_stmt, 1) = res;
 695           break;
 696
 697         default:;
 698           gcc_unreachable ();
 699         }
 700
 701         update_stmt (use_stmt);
 702     }
 703
 704   VEC_free(tree, heap, stmts);
 705 }
 706
 707 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 708    on the SSA_NAME argument of each of them.  */
 709
 710 static unsigned int
 711 execute_cse_sincos (void)
 712 {
 713   basic_block bb;
 714
 715   calculate_dominance_info (CDI_DOMINATORS);
 716
 717   FOR_EACH_BB (bb)
 718     {
 719       block_stmt_iterator bsi;
 720
 721       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 722         {
 723           tree stmt = bsi_stmt (bsi);
 724           tree fndecl;
 725
 726           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 727               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 728               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 729               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 730             {
 731               tree arg;
 732
 733               switch (DECL_FUNCTION_CODE (fndecl))
 734                 {
 735                 CASE_FLT_FN (BUILT_IN_COS):
 736                 CASE_FLT_FN (BUILT_IN_SIN):
 737                 CASE_FLT_FN (BUILT_IN_CEXPI):
 738                   arg = GIMPLE_STMT_OPERAND (stmt, 1);
 739                   arg = CALL_EXPR_ARG (arg, 0);
 740                   if (TREE_CODE (arg) == SSA_NAME)
 741                     execute_cse_sincos_1 (arg);
 742                   break;
 743
 744                 default:;
 745                 }
 746             }
 747         }
 748     }
 749
 750   free_dominance_info (CDI_DOMINATORS);
 751   return 0;
 752 }
 753
 754 static bool
 755 gate_cse_sincos (void)
 756 {
 757   /* Make sure we have either sincos or cexp.  */
 758   return (TARGET_HAS_SINCOS
 759           || TARGET_C99_FUNCTIONS)
 760          && optimize;
 761 }
 762
 763 struct tree_opt_pass pass_cse_sincos =
 764 {
 765   "sincos",                             /* name */
 766   gate_cse_sincos,                      /* gate */
 767   execute_cse_sincos,                   /* execute */
 768   NULL,                                 /* sub */
 769   NULL,                                 /* next */
 770   0,                                    /* static_pass_number */
 771   0,                                    /* tv_id */
 772   PROP_ssa,                             /* properties_required */
 773   0,                                    /* properties_provided */
 774   0,                                    /* properties_destroyed */
 775   0,                                    /* todo_flags_start */
 776   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 777     | TODO_verify_stmts,                /* todo_flags_finish */
 778   0                                     /* letter */
 779 };
 780
 781 /* Find all expressions in the form of sqrt(a/b) and
 782    convert them to rsqrt(b/a).  */
 783
 784 static unsigned int
 785 execute_convert_to_rsqrt (void)
 786 {
 787   basic_block bb;
 788
 789   FOR_EACH_BB (bb)
 790     {
 791       block_stmt_iterator bsi;
 792
 793       for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 794         {
 795           tree stmt = bsi_stmt (bsi);
 796           tree fndecl;
 797
 798           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 799               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CALL_EXPR
 800               && (fndecl = get_callee_fndecl (GIMPLE_STMT_OPERAND (stmt, 1)))
 801               && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 802                   || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 803             {
 804               enum built_in_function code;
 805               bool md_code;
 806               tree arg1;
 807               tree stmt1;
 808
 809               code = DECL_FUNCTION_CODE (fndecl);
 810               md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 811
 812               fndecl = targetm.builtin_reciprocal (code, md_code, true);
 813               if (!fndecl)
 814                 continue;
 815
 816               arg1 = CALL_EXPR_ARG (GIMPLE_STMT_OPERAND (stmt, 1), 0);
 817
 818               if (TREE_CODE (arg1) != SSA_NAME)
 819                 continue;
 820
 821               stmt1 = SSA_NAME_DEF_STMT (arg1);
 822
 823               if (TREE_CODE (stmt1) == GIMPLE_MODIFY_STMT
 824                   && TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1)) == RDIV_EXPR)
 825                 {
 826                   tree arg10, arg11;
 827                   tree tmp;
 828
 829                   arg10 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0);
 830                   arg11 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1);
 831
 832                   /* Swap operands of RDIV_EXPR.  */
 833                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 0) = arg11;
 834                   TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt1, 1), 1) = arg10;
 835                   fold_stmt_inplace (stmt1);
 836                   update_stmt (stmt1);
 837
 838                   tmp = build_call_expr (fndecl, 1, arg1);
 839                   GIMPLE_STMT_OPERAND (stmt, 1) = tmp;
 840                   update_stmt (stmt);
 841                 }
 842             }
 843         }
 844     }
 845
 846   return 0;
 847 }
 848
 849 static bool
 850 gate_convert_to_rsqrt (void)
 851 {
 852   return flag_unsafe_math_optimizations && optimize;
 853 }
 854
 855 struct tree_opt_pass pass_convert_to_rsqrt =
 856 {
 857   "rsqrt",                              /* name */
 858   gate_convert_to_rsqrt,                /* gate */
 859   execute_convert_to_rsqrt,             /* execute */
 860   NULL,                                 /* sub */
 861   NULL,                                 /* next */
 862   0,                                    /* static_pass_number */
 863   0,                                    /* tv_id */
 864   PROP_ssa,                             /* properties_required */
 865   0,                                    /* properties_provided */
 866   0,                                    /* properties_destroyed */
 867   0,                                    /* todo_flags_start */
 868   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 869     | TODO_verify_stmts,                /* todo_flags_finish */
 870   0                                     /* letter */
 871 };