gcc/tree-ssa-math-opts.c

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