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