gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005, 2006, 2007, 2008, 2009 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 #include "diagnostic.h"
 101 #include "rtl.h"
 102 #include "expr.h"
 103 #include "optabs.h"
 104
 105 /* This structure represents one basic block that either computes a
 106    division, or is a common dominator for basic block that compute a
 107    division.  */
 108 struct occurrence {
 109   /* The basic block represented by this structure.  */
 110   basic_block bb;
 111
 112   /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
 113      inserted in BB.  */
 114   tree recip_def;
 115
 116   /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
 117      was inserted in BB.  */
 118   gimple recip_def_stmt;
 119
 120   /* Pointer to a list of "struct occurrence"s for blocks dominated
 121      by BB.  */
 122   struct occurrence *children;
 123
 124   /* Pointer to the next "struct occurrence"s in the list of blocks
 125      sharing a common dominator.  */
 126   struct occurrence *next;
 127
 128   /* The number of divisions that are in BB before compute_merit.  The
 129      number of divisions that are in BB or post-dominate it after
 130      compute_merit.  */
 131   int num_divisions;
 132
 133   /* True if the basic block has a division, false if it is a common
 134      dominator for basic blocks that do.  If it is false and trapping
 135      math is active, BB is not a candidate for inserting a reciprocal.  */
 136   bool bb_has_division;
 137 };
 138
 139
 140 /* The instance of "struct occurrence" representing the highest
 141    interesting block in the dominator tree.  */
 142 static struct occurrence *occ_head;
 143
 144 /* Allocation pool for getting instances of "struct occurrence".  */
 145 static alloc_pool occ_pool;
 146
 147
 148
 149 /* Allocate and return a new struct occurrence for basic block BB, and
 150    whose children list is headed by CHILDREN.  */
 151 static struct occurrence *
 152 occ_new (basic_block bb, struct occurrence *children)
 153 {
 154   struct occurrence *occ;
 155
 156   bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
 157   memset (occ, 0, sizeof (struct occurrence));
 158
 159   occ->bb = bb;
 160   occ->children = children;
 161   return occ;
 162 }
 163
 164
 165 /* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
 166    list of "struct occurrence"s, one per basic block, having IDOM as
 167    their common dominator.
 168
 169    We try to insert NEW_OCC as deep as possible in the tree, and we also
 170    insert any other block that is a common dominator for BB and one
 171    block already in the tree.  */
 172
 173 static void
 174 insert_bb (struct occurrence *new_occ, basic_block idom,
 175            struct occurrence **p_head)
 176 {
 177   struct occurrence *occ, **p_occ;
 178
 179   for (p_occ = p_head; (occ = *p_occ) != NULL; )
 180     {
 181       basic_block bb = new_occ->bb, occ_bb = occ->bb;
 182       basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
 183       if (dom == bb)
 184         {
 185           /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
 186              from its list.  */
 187           *p_occ = occ->next;
 188           occ->next = new_occ->children;
 189           new_occ->children = occ;
 190
 191           /* Try the next block (it may as well be dominated by BB).  */
 192         }
 193
 194       else if (dom == occ_bb)
 195         {
 196           /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
 197           insert_bb (new_occ, dom, &occ->children);
 198           return;
 199         }
 200
 201       else if (dom != idom)
 202         {
 203           gcc_assert (!dom->aux);
 204
 205           /* There is a dominator between IDOM and BB, add it and make
 206              two children out of NEW_OCC and OCC.  First, remove OCC from
 207              its list.  */
 208           *p_occ = occ->next;
 209           new_occ->next = occ;
 210           occ->next = NULL;
 211
 212           /* None of the previous blocks has DOM as a dominator: if we tail
 213              recursed, we would reexamine them uselessly. Just switch BB with
 214              DOM, and go on looking for blocks dominated by DOM.  */
 215           new_occ = occ_new (dom, new_occ);
 216         }
 217
 218       else
 219         {
 220           /* Nothing special, go on with the next element.  */
 221           p_occ = &occ->next;
 222         }
 223     }
 224
 225   /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
 226   new_occ->next = *p_head;
 227   *p_head = new_occ;
 228 }
 229
 230 /* Register that we found a division in BB.  */
 231
 232 static inline void
 233 register_division_in (basic_block bb)
 234 {
 235   struct occurrence *occ;
 236
 237   occ = (struct occurrence *) bb->aux;
 238   if (!occ)
 239     {
 240       occ = occ_new (bb, NULL);
 241       insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
 242     }
 243
 244   occ->bb_has_division = true;
 245   occ->num_divisions++;
 246 }
 247
 248
 249 /* Compute the number of divisions that postdominate each block in OCC and
 250    its children.  */
 251
 252 static void
 253 compute_merit (struct occurrence *occ)
 254 {
 255   struct occurrence *occ_child;
 256   basic_block dom = occ->bb;
 257
 258   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 259     {
 260       basic_block bb;
 261       if (occ_child->children)
 262         compute_merit (occ_child);
 263
 264       if (flag_exceptions)
 265         bb = single_noncomplex_succ (dom);
 266       else
 267         bb = dom;
 268
 269       if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
 270         occ->num_divisions += occ_child->num_divisions;
 271     }
 272 }
 273
 274
 275 /* Return whether USE_STMT is a floating-point division by DEF.  */
 276 static inline bool
 277 is_division_by (gimple use_stmt, tree def)
 278 {
 279   return is_gimple_assign (use_stmt)
 280          && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
 281          && gimple_assign_rhs2 (use_stmt) == def
 282          /* Do not recognize x / x as valid division, as we are getting
 283             confused later by replacing all immediate uses x in such
 284             a stmt.  */
 285          && gimple_assign_rhs1 (use_stmt) != def;
 286 }
 287
 288 /* Walk the subset of the dominator tree rooted at OCC, setting the
 289    RECIP_DEF field to a definition of 1.0 / DEF that can be used in
 290    the given basic block.  The field may be left NULL, of course,
 291    if it is not possible or profitable to do the optimization.
 292
 293    DEF_BSI is an iterator pointing at the statement defining DEF.
 294    If RECIP_DEF is set, a dominator already has a computation that can
 295    be used.  */
 296
 297 static void
 298 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
 299                     tree def, tree recip_def, int threshold)
 300 {
 301   tree type;
 302   gimple new_stmt;
 303   gimple_stmt_iterator gsi;
 304   struct occurrence *occ_child;
 305
 306   if (!recip_def
 307       && (occ->bb_has_division || !flag_trapping_math)
 308       && occ->num_divisions >= threshold)
 309     {
 310       /* Make a variable with the replacement and substitute it.  */
 311       type = TREE_TYPE (def);
 312       recip_def = make_rename_temp (type, "reciptmp");
 313       new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
 314                                                build_one_cst (type), def);
 315
 316       if (occ->bb_has_division)
 317         {
 318           /* Case 1: insert before an existing division.  */
 319           gsi = gsi_after_labels (occ->bb);
 320           while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
 321             gsi_next (&gsi);
 322
 323           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 324         }
 325       else if (def_gsi && occ->bb == def_gsi->bb)
 326         {
 327           /* Case 2: insert right after the definition.  Note that this will
 328              never happen if the definition statement can throw, because in
 329              that case the sole successor of the statement's basic block will
 330              dominate all the uses as well.  */
 331           gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
 332         }
 333       else
 334         {
 335           /* Case 3: insert in a basic block not containing defs/uses.  */
 336           gsi = gsi_after_labels (occ->bb);
 337           gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
 338         }
 339
 340       occ->recip_def_stmt = new_stmt;
 341     }
 342
 343   occ->recip_def = recip_def;
 344   for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
 345     insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
 346 }
 347
 348
 349 /* Replace the division at USE_P with a multiplication by the reciprocal, if
 350    possible.  */
 351
 352 static inline void
 353 replace_reciprocal (use_operand_p use_p)
 354 {
 355   gimple use_stmt = USE_STMT (use_p);
 356   basic_block bb = gimple_bb (use_stmt);
 357   struct occurrence *occ = (struct occurrence *) bb->aux;
 358
 359   if (optimize_bb_for_speed_p (bb)
 360       && occ->recip_def && use_stmt != occ->recip_def_stmt)
 361     {
 362       gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
 363       SET_USE (use_p, occ->recip_def);
 364       fold_stmt_inplace (use_stmt);
 365       update_stmt (use_stmt);
 366     }
 367 }
 368
 369
 370 /* Free OCC and return one more "struct occurrence" to be freed.  */
 371
 372 static struct occurrence *
 373 free_bb (struct occurrence *occ)
 374 {
 375   struct occurrence *child, *next;
 376
 377   /* First get the two pointers hanging off OCC.  */
 378   next = occ->next;
 379   child = occ->children;
 380   occ->bb->aux = NULL;
 381   pool_free (occ_pool, occ);
 382
 383   /* Now ensure that we don't recurse unless it is necessary.  */
 384   if (!child)
 385     return next;
 386   else
 387     {
 388       while (next)
 389         next = free_bb (next);
 390
 391       return child;
 392     }
 393 }
 394
 395
 396 /* Look for floating-point divisions among DEF's uses, and try to
 397    replace them by multiplications with the reciprocal.  Add
 398    as many statements computing the reciprocal as needed.
 399
 400    DEF must be a GIMPLE register of a floating-point type.  */
 401
 402 static void
 403 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
 404 {
 405   use_operand_p use_p;
 406   imm_use_iterator use_iter;
 407   struct occurrence *occ;
 408   int count = 0, threshold;
 409
 410   gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
 411
 412   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
 413     {
 414       gimple use_stmt = USE_STMT (use_p);
 415       if (is_division_by (use_stmt, def))
 416         {
 417           register_division_in (gimple_bb (use_stmt));
 418           count++;
 419         }
 420     }
 421
 422   /* Do the expensive part only if we can hope to optimize something.  */
 423   threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
 424   if (count >= threshold)
 425     {
 426       gimple use_stmt;
 427       for (occ = occ_head; occ; occ = occ->next)
 428         {
 429           compute_merit (occ);
 430           insert_reciprocals (def_gsi, occ, def, NULL, threshold);
 431         }
 432
 433       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
 434         {
 435           if (is_division_by (use_stmt, def))
 436             {
 437               FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
 438                 replace_reciprocal (use_p);
 439             }
 440         }
 441     }
 442
 443   for (occ = occ_head; occ; )
 444     occ = free_bb (occ);
 445
 446   occ_head = NULL;
 447 }
 448
 449 static bool
 450 gate_cse_reciprocals (void)
 451 {
 452   return optimize && flag_reciprocal_math;
 453 }
 454
 455 /* Go through all the floating-point SSA_NAMEs, and call
 456    execute_cse_reciprocals_1 on each of them.  */
 457 static unsigned int
 458 execute_cse_reciprocals (void)
 459 {
 460   basic_block bb;
 461   tree arg;
 462
 463   occ_pool = create_alloc_pool ("dominators for recip",
 464                                 sizeof (struct occurrence),
 465                                 n_basic_blocks / 3 + 1);
 466
 467   calculate_dominance_info (CDI_DOMINATORS);
 468   calculate_dominance_info (CDI_POST_DOMINATORS);
 469
 470 #ifdef ENABLE_CHECKING
 471   FOR_EACH_BB (bb)
 472     gcc_assert (!bb->aux);
 473 #endif
 474
 475   for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 476     if (gimple_default_def (cfun, arg)
 477         && FLOAT_TYPE_P (TREE_TYPE (arg))
 478         && is_gimple_reg (arg))
 479       execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
 480
 481   FOR_EACH_BB (bb)
 482     {
 483       gimple_stmt_iterator gsi;
 484       gimple phi;
 485       tree def;
 486
 487       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 488         {
 489           phi = gsi_stmt (gsi);
 490           def = PHI_RESULT (phi);
 491           if (FLOAT_TYPE_P (TREE_TYPE (def))
 492               && is_gimple_reg (def))
 493             execute_cse_reciprocals_1 (NULL, def);
 494         }
 495
 496       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 497         {
 498           gimple stmt = gsi_stmt (gsi);
 499
 500           if (gimple_has_lhs (stmt)
 501               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 502               && FLOAT_TYPE_P (TREE_TYPE (def))
 503               && TREE_CODE (def) == SSA_NAME)
 504             execute_cse_reciprocals_1 (&gsi, def);
 505         }
 506
 507       if (optimize_bb_for_size_p (bb))
 508         continue;
 509
 510       /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b).  */
 511       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 512         {
 513           gimple stmt = gsi_stmt (gsi);
 514           tree fndecl;
 515
 516           if (is_gimple_assign (stmt)
 517               && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
 518             {
 519               tree arg1 = gimple_assign_rhs2 (stmt);
 520               gimple stmt1;
 521
 522               if (TREE_CODE (arg1) != SSA_NAME)
 523                 continue;
 524
 525               stmt1 = SSA_NAME_DEF_STMT (arg1);
 526
 527               if (is_gimple_call (stmt1)
 528                   && gimple_call_lhs (stmt1)
 529                   && (fndecl = gimple_call_fndecl (stmt1))
 530                   && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
 531                       || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
 532                 {
 533                   enum built_in_function code;
 534                   bool md_code, fail;
 535                   imm_use_iterator ui;
 536                   use_operand_p use_p;
 537
 538                   code = DECL_FUNCTION_CODE (fndecl);
 539                   md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
 540
 541                   fndecl = targetm.builtin_reciprocal (code, md_code, false);
 542                   if (!fndecl)
 543                     continue;
 544
 545                   /* Check that all uses of the SSA name are divisions,
 546                      otherwise replacing the defining statement will do
 547                      the wrong thing.  */
 548                   fail = false;
 549                   FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
 550                     {
 551                       gimple stmt2 = USE_STMT (use_p);
 552                       if (is_gimple_debug (stmt2))
 553                         continue;
 554                       if (!is_gimple_assign (stmt2)
 555                           || gimple_assign_rhs_code (stmt2) != RDIV_EXPR
 556                           || gimple_assign_rhs1 (stmt2) == arg1
 557                           || gimple_assign_rhs2 (stmt2) != arg1)
 558                         {
 559                           fail = true;
 560                           break;
 561                         }
 562                     }
 563                   if (fail)
 564                     continue;
 565
 566                   gimple_call_set_fndecl (stmt1, fndecl);
 567                   update_stmt (stmt1);
 568
 569                   FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
 570                     {
 571                       gimple_assign_set_rhs_code (stmt, MULT_EXPR);
 572                       fold_stmt_inplace (stmt);
 573                       update_stmt (stmt);
 574                     }
 575                 }
 576             }
 577         }
 578     }
 579
 580   free_dominance_info (CDI_DOMINATORS);
 581   free_dominance_info (CDI_POST_DOMINATORS);
 582   free_alloc_pool (occ_pool);
 583   return 0;
 584 }
 585
 586 struct gimple_opt_pass pass_cse_reciprocals =
 587 {
 588  {
 589   GIMPLE_PASS,
 590   "recip",                              /* name */
 591   gate_cse_reciprocals,                 /* gate */
 592   execute_cse_reciprocals,              /* execute */
 593   NULL,                                 /* sub */
 594   NULL,                                 /* next */
 595   0,                                    /* static_pass_number */
 596   TV_NONE,                              /* tv_id */
 597   PROP_ssa,                             /* properties_required */
 598   0,                                    /* properties_provided */
 599   0,                                    /* properties_destroyed */
 600   0,                                    /* todo_flags_start */
 601   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 602     | TODO_verify_stmts                /* todo_flags_finish */
 603  }
 604 };
 605
 606 /* Records an occurrence at statement USE_STMT in the vector of trees
 607    STMTS if it is dominated by *TOP_BB or dominates it or this basic block
 608    is not yet initialized.  Returns true if the occurrence was pushed on
 609    the vector.  Adjusts *TOP_BB to be the basic block dominating all
 610    statements in the vector.  */
 611
 612 static bool
 613 maybe_record_sincos (VEC(gimple, heap) **stmts,
 614                      basic_block *top_bb, gimple use_stmt)
 615 {
 616   basic_block use_bb = gimple_bb (use_stmt);
 617   if (*top_bb
 618       && (*top_bb == use_bb
 619           || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
 620     VEC_safe_push (gimple, heap, *stmts, use_stmt);
 621   else if (!*top_bb
 622            || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
 623     {
 624       VEC_safe_push (gimple, heap, *stmts, use_stmt);
 625       *top_bb = use_bb;
 626     }
 627   else
 628     return false;
 629
 630   return true;
 631 }
 632
 633 /* Look for sin, cos and cexpi calls with the same argument NAME and
 634    create a single call to cexpi CSEing the result in this case.
 635    We first walk over all immediate uses of the argument collecting
 636    statements that we can CSE in a vector and in a second pass replace
 637    the statement rhs with a REALPART or IMAGPART expression on the
 638    result of the cexpi call we insert before the use statement that
 639    dominates all other candidates.  */
 640
 641 static void
 642 execute_cse_sincos_1 (tree name)
 643 {
 644   gimple_stmt_iterator gsi;
 645   imm_use_iterator use_iter;
 646   tree fndecl, res, type;
 647   gimple def_stmt, use_stmt, stmt;
 648   int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
 649   VEC(gimple, heap) *stmts = NULL;
 650   basic_block top_bb = NULL;
 651   int i;
 652
 653   type = TREE_TYPE (name);
 654   FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 655     {
 656       if (gimple_code (use_stmt) != GIMPLE_CALL
 657           || !gimple_call_lhs (use_stmt)
 658           || !(fndecl = gimple_call_fndecl (use_stmt))
 659           || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
 660         continue;
 661
 662       switch (DECL_FUNCTION_CODE (fndecl))
 663         {
 664         CASE_FLT_FN (BUILT_IN_COS):
 665           seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 666           break;
 667
 668         CASE_FLT_FN (BUILT_IN_SIN):
 669           seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 670           break;
 671
 672         CASE_FLT_FN (BUILT_IN_CEXPI):
 673           seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
 674           break;
 675
 676         default:;
 677         }
 678     }
 679
 680   if (seen_cos + seen_sin + seen_cexpi <= 1)
 681     {
 682       VEC_free(gimple, heap, stmts);
 683       return;
 684     }
 685
 686   /* Simply insert cexpi at the beginning of top_bb but not earlier than
 687      the name def statement.  */
 688   fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
 689   if (!fndecl)
 690     return;
 691   res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
 692   stmt = gimple_build_call (fndecl, 1, name);
 693   gimple_call_set_lhs (stmt, res);
 694
 695   def_stmt = SSA_NAME_DEF_STMT (name);
 696   if (!SSA_NAME_IS_DEFAULT_DEF (name)
 697       && gimple_code (def_stmt) != GIMPLE_PHI
 698       && gimple_bb (def_stmt) == top_bb)
 699     {
 700       gsi = gsi_for_stmt (def_stmt);
 701       gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 702     }
 703   else
 704     {
 705       gsi = gsi_after_labels (top_bb);
 706       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
 707     }
 708   update_stmt (stmt);
 709
 710   /* And adjust the recorded old call sites.  */
 711   for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
 712     {
 713       tree rhs = NULL;
 714       fndecl = gimple_call_fndecl (use_stmt);
 715
 716       switch (DECL_FUNCTION_CODE (fndecl))
 717         {
 718         CASE_FLT_FN (BUILT_IN_COS):
 719           rhs = fold_build1 (REALPART_EXPR, type, res);
 720           break;
 721
 722         CASE_FLT_FN (BUILT_IN_SIN):
 723           rhs = fold_build1 (IMAGPART_EXPR, type, res);
 724           break;
 725
 726         CASE_FLT_FN (BUILT_IN_CEXPI):
 727           rhs = res;
 728           break;
 729
 730         default:;
 731           gcc_unreachable ();
 732         }
 733
 734         /* Replace call with a copy.  */
 735         stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
 736
 737         gsi = gsi_for_stmt (use_stmt);
 738         gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
 739         gsi_remove (&gsi, true);
 740     }
 741
 742   VEC_free(gimple, heap, stmts);
 743 }
 744
 745 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
 746    on the SSA_NAME argument of each of them.  */
 747
 748 static unsigned int
 749 execute_cse_sincos (void)
 750 {
 751   basic_block bb;
 752
 753   calculate_dominance_info (CDI_DOMINATORS);
 754
 755   FOR_EACH_BB (bb)
 756     {
 757       gimple_stmt_iterator gsi;
 758
 759       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 760         {
 761           gimple stmt = gsi_stmt (gsi);
 762           tree fndecl;
 763
 764           if (is_gimple_call (stmt)
 765               && gimple_call_lhs (stmt)
 766               && (fndecl = gimple_call_fndecl (stmt))
 767               && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
 768             {
 769               tree arg;
 770
 771               switch (DECL_FUNCTION_CODE (fndecl))
 772                 {
 773                 CASE_FLT_FN (BUILT_IN_COS):
 774                 CASE_FLT_FN (BUILT_IN_SIN):
 775                 CASE_FLT_FN (BUILT_IN_CEXPI):
 776                   arg = gimple_call_arg (stmt, 0);
 777                   if (TREE_CODE (arg) == SSA_NAME)
 778                     execute_cse_sincos_1 (arg);
 779                   break;
 780
 781                 default:;
 782                 }
 783             }
 784         }
 785     }
 786
 787   free_dominance_info (CDI_DOMINATORS);
 788   return 0;
 789 }
 790
 791 static bool
 792 gate_cse_sincos (void)
 793 {
 794   /* Make sure we have either sincos or cexp.  */
 795   return (TARGET_HAS_SINCOS
 796           || TARGET_C99_FUNCTIONS)
 797          && optimize;
 798 }
 799
 800 struct gimple_opt_pass pass_cse_sincos =
 801 {
 802  {
 803   GIMPLE_PASS,
 804   "sincos",                             /* name */
 805   gate_cse_sincos,                      /* gate */
 806   execute_cse_sincos,                   /* execute */
 807   NULL,                                 /* sub */
 808   NULL,                                 /* next */
 809   0,                                    /* static_pass_number */
 810   TV_NONE,                              /* tv_id */
 811   PROP_ssa,                             /* properties_required */
 812   0,                                    /* properties_provided */
 813   0,                                    /* properties_destroyed */
 814   0,                                    /* todo_flags_start */
 815   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 816     | TODO_verify_stmts                 /* todo_flags_finish */
 817  }
 818 };
 819
 820 /* A symbolic number is used to detect byte permutation and selection
 821    patterns.  Therefore the field N contains an artificial number
 822    consisting of byte size markers:
 823
 824    0    - byte has the value 0
 825    1..size - byte contains the content of the byte
 826    number indexed with that value minus one  */
 827
 828 struct symbolic_number {
 829   unsigned HOST_WIDEST_INT n;
 830   int size;
 831 };
 832
 833 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
 834    number N.  Return false if the requested operation is not permitted
 835    on a symbolic number.  */
 836
 837 static inline bool
 838 do_shift_rotate (enum tree_code code,
 839                  struct symbolic_number *n,
 840                  int count)
 841 {
 842   if (count % 8 != 0)
 843     return false;
 844
 845   /* Zero out the extra bits of N in order to avoid them being shifted
 846      into the significant bits.  */
 847   if (n->size < (int)sizeof (HOST_WIDEST_INT))
 848     n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
 849
 850   switch (code)
 851     {
 852     case LSHIFT_EXPR:
 853       n->n <<= count;
 854       break;
 855     case RSHIFT_EXPR:
 856       n->n >>= count;
 857       break;
 858     case LROTATE_EXPR:
 859       n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
 860       break;
 861     case RROTATE_EXPR:
 862       n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
 863       break;
 864     default:
 865       return false;
 866     }
 867   return true;
 868 }
 869
 870 /* Perform sanity checking for the symbolic number N and the gimple
 871    statement STMT.  */
 872
 873 static inline bool
 874 verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
 875 {
 876   tree lhs_type;
 877
 878   lhs_type = gimple_expr_type (stmt);
 879
 880   if (TREE_CODE (lhs_type) != INTEGER_TYPE)
 881     return false;
 882
 883   if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
 884     return false;
 885
 886   return true;
 887 }
 888
 889 /* find_bswap_1 invokes itself recursively with N and tries to perform
 890    the operation given by the rhs of STMT on the result.  If the
 891    operation could successfully be executed the function returns the
 892    tree expression of the source operand and NULL otherwise.  */
 893
 894 static tree
 895 find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
 896 {
 897   enum tree_code code;
 898   tree rhs1, rhs2 = NULL;
 899   gimple rhs1_stmt, rhs2_stmt;
 900   tree source_expr1;
 901   enum gimple_rhs_class rhs_class;
 902
 903   if (!limit || !is_gimple_assign (stmt))
 904     return NULL_TREE;
 905
 906   rhs1 = gimple_assign_rhs1 (stmt);
 907
 908   if (TREE_CODE (rhs1) != SSA_NAME)
 909     return NULL_TREE;
 910
 911   code = gimple_assign_rhs_code (stmt);
 912   rhs_class = gimple_assign_rhs_class (stmt);
 913   rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
 914
 915   if (rhs_class == GIMPLE_BINARY_RHS)
 916     rhs2 = gimple_assign_rhs2 (stmt);
 917
 918   /* Handle unary rhs and binary rhs with integer constants as second
 919      operand.  */
 920
 921   if (rhs_class == GIMPLE_UNARY_RHS
 922       || (rhs_class == GIMPLE_BINARY_RHS
 923           && TREE_CODE (rhs2) == INTEGER_CST))
 924     {
 925       if (code != BIT_AND_EXPR
 926           && code != LSHIFT_EXPR
 927           && code != RSHIFT_EXPR
 928           && code != LROTATE_EXPR
 929           && code != RROTATE_EXPR
 930           && code != NOP_EXPR
 931           && code != CONVERT_EXPR)
 932         return NULL_TREE;
 933
 934       source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
 935
 936       /* If find_bswap_1 returned NULL STMT is a leaf node and we have
 937          to initialize the symbolic number.  */
 938       if (!source_expr1)
 939         {
 940           /* Set up the symbolic number N by setting each byte to a
 941              value between 1 and the byte size of rhs1.  The highest
 942              order byte is set to 1 and the lowest order byte to
 943              n.size.  */
 944           n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
 945           if (n->size % BITS_PER_UNIT != 0)
 946             return NULL_TREE;
 947           n->size /= BITS_PER_UNIT;
 948           n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
 949                   (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708);
 950           n->n >>= (sizeof (HOST_WIDEST_INT) - n->size) * BITS_PER_UNIT;
 951
 952           source_expr1 = rhs1;
 953         }
 954
 955       switch (code)
 956         {
 957         case BIT_AND_EXPR:
 958           {
 959             int i;
 960             unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
 961             unsigned HOST_WIDEST_INT tmp = val;
 962
 963             /* Only constants masking full bytes are allowed.  */
 964             for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
 965               if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
 966                 return NULL_TREE;
 967
 968             n->n &= val;
 969           }
 970           break;
 971         case LSHIFT_EXPR:
 972         case RSHIFT_EXPR:
 973         case LROTATE_EXPR:
 974         case RROTATE_EXPR:
 975           if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
 976             return NULL_TREE;
 977           break;
 978         CASE_CONVERT:
 979           {
 980             int type_size;
 981
 982             type_size = TYPE_PRECISION (gimple_expr_type (stmt));
 983             if (type_size % BITS_PER_UNIT != 0)
 984               return NULL_TREE;
 985
 986             if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
 987               {
 988                 /* If STMT casts to a smaller type mask out the bits not
 989                    belonging to the target type.  */
 990                 n->size = type_size / BITS_PER_UNIT;
 991                 n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
 992               }
 993           }
 994           break;
 995         default:
 996           return NULL_TREE;
 997         };
 998       return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
 999     }
1000
1001   /* Handle binary rhs.  */
1002
1003   if (rhs_class == GIMPLE_BINARY_RHS)
1004     {
1005       struct symbolic_number n1, n2;
1006       tree source_expr2;
1007
1008       if (code != BIT_IOR_EXPR)
1009         return NULL_TREE;
1010
1011       if (TREE_CODE (rhs2) != SSA_NAME)
1012         return NULL_TREE;
1013
1014       rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
1015
1016       switch (code)
1017         {
1018         case BIT_IOR_EXPR:
1019           source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
1020
1021           if (!source_expr1)
1022             return NULL_TREE;
1023
1024           source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
1025
1026           if (source_expr1 != source_expr2
1027               || n1.size != n2.size)
1028             return NULL_TREE;
1029
1030           n->size = n1.size;
1031           n->n = n1.n | n2.n;
1032
1033           if (!verify_symbolic_number_p (n, stmt))
1034             return NULL_TREE;
1035
1036           break;
1037         default:
1038           return NULL_TREE;
1039         }
1040       return source_expr1;
1041     }
1042   return NULL_TREE;
1043 }
1044
1045 /* Check if STMT completes a bswap implementation consisting of ORs,
1046    SHIFTs and ANDs.  Return the source tree expression on which the
1047    byte swap is performed and NULL if no bswap was found.  */
1048
1049 static tree
1050 find_bswap (gimple stmt)
1051 {
1052 /* The number which the find_bswap result should match in order to
1053    have a full byte swap.  The insignificant bytes are masked out
1054    before using it.  */
1055   unsigned HOST_WIDEST_INT cmp =
1056     sizeof (HOST_WIDEST_INT) < 8 ? 0 :
1057     (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201;
1058
1059   struct symbolic_number n;
1060   tree source_expr;
1061
1062   /* The last parameter determines the depth search limit.  It usually
1063      correlates directly to the number of bytes to be touched.  We
1064      increase that number by one here in order to also cover signed ->
1065      unsigned conversions of the src operand as can be seen in
1066      libgcc.  */
1067   source_expr =  find_bswap_1 (stmt, &n,
1068                                TREE_INT_CST_LOW (
1069                                  TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
1070
1071   if (!source_expr)
1072     return NULL_TREE;
1073
1074   /* Zero out the extra bits of N and CMP.  */
1075   if (n.size < (int)sizeof (HOST_WIDEST_INT))
1076     {
1077       unsigned HOST_WIDEST_INT mask =
1078         ((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
1079
1080       n.n &= mask;
1081       cmp &= mask;
1082     }
1083
1084   /* A complete byte swap should make the symbolic number to start
1085      with the largest digit in the highest order byte.  */
1086   if (cmp != n.n)
1087     return NULL_TREE;
1088
1089   return source_expr;
1090 }
1091
1092 /* Find manual byte swap implementations and turn them into a bswap
1093    builtin invokation.  */
1094
1095 static unsigned int
1096 execute_optimize_bswap (void)
1097 {
1098   basic_block bb;
1099   bool bswap32_p, bswap64_p;
1100   bool changed = false;
1101   tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1102
1103   if (BITS_PER_UNIT != 8)
1104     return 0;
1105
1106   if (sizeof (HOST_WIDEST_INT) < 8)
1107     return 0;
1108
1109   bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
1110                && optab_handler (bswap_optab, SImode)->insn_code !=
1111                CODE_FOR_nothing);
1112   bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
1113                && optab_handler (bswap_optab, DImode)->insn_code !=
1114                CODE_FOR_nothing);
1115
1116   if (!bswap32_p && !bswap64_p)
1117     return 0;
1118
1119   /* Determine the argument type of the builtins.  The code later on
1120      assumes that the return and argument type are the same.  */
1121   if (bswap32_p)
1122     {
1123       tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
1124       bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1125     }
1126
1127   if (bswap64_p)
1128     {
1129       tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
1130       bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1131     }
1132
1133   FOR_EACH_BB (bb)
1134     {
1135       gimple_stmt_iterator gsi;
1136
1137       for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1138         {
1139           gimple stmt = gsi_stmt (gsi);
1140           tree bswap_src, bswap_type;
1141           tree bswap_tmp;
1142           tree fndecl = NULL_TREE;
1143           int type_size;
1144           gimple call;
1145
1146           if (!is_gimple_assign (stmt)
1147               || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
1148             continue;
1149
1150           type_size = TYPE_PRECISION (gimple_expr_type (stmt));
1151
1152           switch (type_size)
1153             {
1154             case 32:
1155               if (bswap32_p)
1156                 {
1157                   fndecl = built_in_decls[BUILT_IN_BSWAP32];
1158                   bswap_type = bswap32_type;
1159                 }
1160               break;
1161             case 64:
1162               if (bswap64_p)
1163                 {
1164                   fndecl = built_in_decls[BUILT_IN_BSWAP64];
1165                   bswap_type = bswap64_type;
1166                 }
1167               break;
1168             default:
1169               continue;
1170             }
1171
1172           if (!fndecl)
1173             continue;
1174
1175           bswap_src = find_bswap (stmt);
1176
1177           if (!bswap_src)
1178             continue;
1179
1180           changed = true;
1181
1182           bswap_tmp = bswap_src;
1183
1184           /* Convert the src expression if necessary.  */
1185           if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1186             {
1187               gimple convert_stmt;
1188
1189               bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
1190               add_referenced_var (bswap_tmp);
1191               bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1192
1193               convert_stmt = gimple_build_assign_with_ops (
1194                                CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
1195               gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
1196             }
1197
1198           call = gimple_build_call (fndecl, 1, bswap_tmp);
1199
1200           bswap_tmp = gimple_assign_lhs (stmt);
1201
1202           /* Convert the result if necessary.  */
1203           if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1204             {
1205               gimple convert_stmt;
1206
1207               bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
1208               add_referenced_var (bswap_tmp);
1209               bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1210               convert_stmt = gimple_build_assign_with_ops (
1211                                CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
1212               gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
1213             }
1214
1215           gimple_call_set_lhs (call, bswap_tmp);
1216
1217           if (dump_file)
1218             {
1219               fprintf (dump_file, "%d bit bswap implementation found at: ",
1220                        (int)type_size);
1221               print_gimple_stmt (dump_file, stmt, 0, 0);
1222             }
1223
1224           gsi_insert_after (&gsi, call, GSI_SAME_STMT);
1225           gsi_remove (&gsi, true);
1226         }
1227     }
1228
1229   return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
1230           | TODO_verify_stmts : 0);
1231 }
1232
1233 static bool
1234 gate_optimize_bswap (void)
1235 {
1236   return flag_expensive_optimizations && optimize;
1237 }
1238
1239 struct gimple_opt_pass pass_optimize_bswap =
1240 {
1241  {
1242   GIMPLE_PASS,
1243   "bswap",                              /* name */
1244   gate_optimize_bswap,                  /* gate */
1245   execute_optimize_bswap,               /* execute */
1246   NULL,                                 /* sub */
1247   NULL,                                 /* next */
1248   0,                                    /* static_pass_number */
1249   TV_NONE,                              /* tv_id */
1250   PROP_ssa,                             /* properties_required */
1251   0,                                    /* properties_provided */
1252   0,                                    /* properties_destroyed */
1253   0,                                    /* todo_flags_start */
1254   0                                     /* todo_flags_finish */
1255  }
1256 };