1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
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/>. */
21 /* Currently, the only mini-pass in this file tries to CSE reciprocal
22 operations. These are common in sequences such as this one:
24 modulus = sqrt(x*x + y*y + z*z);
29 that can be optimized to
31 modulus = sqrt(x*x + y*y + z*z);
32 rmodulus = 1.0 / modulus;
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.
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.
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
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).
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.
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.
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).
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.
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. */
90 #include "coretypes.h"
94 #include "tree-flow.h"
96 #include "tree-pass.h"
97 #include "alloc-pool.h"
98 #include "basic-block.h"
100 #include "gimple-pretty-print.h"
102 /* FIXME: RTL headers have to be included here for optabs. */
103 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */
104 #include "expr.h" /* Because optabs.h wants sepops. */
107 /* This structure represents one basic block that either computes a
108 division, or is a common dominator for basic block that compute a
111 /* The basic block represented by this structure. */
114 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
118 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
119 was inserted in BB. */
120 gimple recip_def_stmt
;
122 /* Pointer to a list of "struct occurrence"s for blocks dominated
124 struct occurrence
*children
;
126 /* Pointer to the next "struct occurrence"s in the list of blocks
127 sharing a common dominator. */
128 struct occurrence
*next
;
130 /* The number of divisions that are in BB before compute_merit. The
131 number of divisions that are in BB or post-dominate it after
135 /* True if the basic block has a division, false if it is a common
136 dominator for basic blocks that do. If it is false and trapping
137 math is active, BB is not a candidate for inserting a reciprocal. */
138 bool bb_has_division
;
143 /* Number of 1.0/X ops inserted. */
146 /* Number of 1.0/FUNC ops inserted. */
152 /* Number of cexpi calls inserted. */
158 /* Number of hand-written 32-bit bswaps found. */
161 /* Number of hand-written 64-bit bswaps found. */
167 /* Number of widening multiplication ops inserted. */
168 int widen_mults_inserted
;
170 /* Number of integer multiply-and-accumulate ops inserted. */
173 /* Number of fp fused multiply-add ops inserted. */
177 /* The instance of "struct occurrence" representing the highest
178 interesting block in the dominator tree. */
179 static struct occurrence
*occ_head
;
181 /* Allocation pool for getting instances of "struct occurrence". */
182 static alloc_pool occ_pool
;
186 /* Allocate and return a new struct occurrence for basic block BB, and
187 whose children list is headed by CHILDREN. */
188 static struct occurrence
*
189 occ_new (basic_block bb
, struct occurrence
*children
)
191 struct occurrence
*occ
;
193 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
194 memset (occ
, 0, sizeof (struct occurrence
));
197 occ
->children
= children
;
202 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
203 list of "struct occurrence"s, one per basic block, having IDOM as
204 their common dominator.
206 We try to insert NEW_OCC as deep as possible in the tree, and we also
207 insert any other block that is a common dominator for BB and one
208 block already in the tree. */
211 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
212 struct occurrence
**p_head
)
214 struct occurrence
*occ
, **p_occ
;
216 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
218 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
219 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
222 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
225 occ
->next
= new_occ
->children
;
226 new_occ
->children
= occ
;
228 /* Try the next block (it may as well be dominated by BB). */
231 else if (dom
== occ_bb
)
233 /* OCC_BB dominates BB. Tail recurse to look deeper. */
234 insert_bb (new_occ
, dom
, &occ
->children
);
238 else if (dom
!= idom
)
240 gcc_assert (!dom
->aux
);
242 /* There is a dominator between IDOM and BB, add it and make
243 two children out of NEW_OCC and OCC. First, remove OCC from
249 /* None of the previous blocks has DOM as a dominator: if we tail
250 recursed, we would reexamine them uselessly. Just switch BB with
251 DOM, and go on looking for blocks dominated by DOM. */
252 new_occ
= occ_new (dom
, new_occ
);
257 /* Nothing special, go on with the next element. */
262 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
263 new_occ
->next
= *p_head
;
267 /* Register that we found a division in BB. */
270 register_division_in (basic_block bb
)
272 struct occurrence
*occ
;
274 occ
= (struct occurrence
*) bb
->aux
;
277 occ
= occ_new (bb
, NULL
);
278 insert_bb (occ
, ENTRY_BLOCK_PTR
, &occ_head
);
281 occ
->bb_has_division
= true;
282 occ
->num_divisions
++;
286 /* Compute the number of divisions that postdominate each block in OCC and
290 compute_merit (struct occurrence
*occ
)
292 struct occurrence
*occ_child
;
293 basic_block dom
= occ
->bb
;
295 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
298 if (occ_child
->children
)
299 compute_merit (occ_child
);
302 bb
= single_noncomplex_succ (dom
);
306 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
307 occ
->num_divisions
+= occ_child
->num_divisions
;
312 /* Return whether USE_STMT is a floating-point division by DEF. */
314 is_division_by (gimple use_stmt
, tree def
)
316 return is_gimple_assign (use_stmt
)
317 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
318 && gimple_assign_rhs2 (use_stmt
) == def
319 /* Do not recognize x / x as valid division, as we are getting
320 confused later by replacing all immediate uses x in such
322 && gimple_assign_rhs1 (use_stmt
) != def
;
325 /* Walk the subset of the dominator tree rooted at OCC, setting the
326 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
327 the given basic block. The field may be left NULL, of course,
328 if it is not possible or profitable to do the optimization.
330 DEF_BSI is an iterator pointing at the statement defining DEF.
331 If RECIP_DEF is set, a dominator already has a computation that can
335 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
336 tree def
, tree recip_def
, int threshold
)
340 gimple_stmt_iterator gsi
;
341 struct occurrence
*occ_child
;
344 && (occ
->bb_has_division
|| !flag_trapping_math
)
345 && occ
->num_divisions
>= threshold
)
347 /* Make a variable with the replacement and substitute it. */
348 type
= TREE_TYPE (def
);
349 recip_def
= make_rename_temp (type
, "reciptmp");
350 new_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, recip_def
,
351 build_one_cst (type
), def
);
353 if (occ
->bb_has_division
)
355 /* Case 1: insert before an existing division. */
356 gsi
= gsi_after_labels (occ
->bb
);
357 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
360 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
362 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
364 /* Case 2: insert right after the definition. Note that this will
365 never happen if the definition statement can throw, because in
366 that case the sole successor of the statement's basic block will
367 dominate all the uses as well. */
368 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
372 /* Case 3: insert in a basic block not containing defs/uses. */
373 gsi
= gsi_after_labels (occ
->bb
);
374 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
377 reciprocal_stats
.rdivs_inserted
++;
379 occ
->recip_def_stmt
= new_stmt
;
382 occ
->recip_def
= recip_def
;
383 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
384 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
388 /* Replace the division at USE_P with a multiplication by the reciprocal, if
392 replace_reciprocal (use_operand_p use_p
)
394 gimple use_stmt
= USE_STMT (use_p
);
395 basic_block bb
= gimple_bb (use_stmt
);
396 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
398 if (optimize_bb_for_speed_p (bb
)
399 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
401 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
402 SET_USE (use_p
, occ
->recip_def
);
403 fold_stmt_inplace (use_stmt
);
404 update_stmt (use_stmt
);
409 /* Free OCC and return one more "struct occurrence" to be freed. */
411 static struct occurrence
*
412 free_bb (struct occurrence
*occ
)
414 struct occurrence
*child
, *next
;
416 /* First get the two pointers hanging off OCC. */
418 child
= occ
->children
;
420 pool_free (occ_pool
, occ
);
422 /* Now ensure that we don't recurse unless it is necessary. */
428 next
= free_bb (next
);
435 /* Look for floating-point divisions among DEF's uses, and try to
436 replace them by multiplications with the reciprocal. Add
437 as many statements computing the reciprocal as needed.
439 DEF must be a GIMPLE register of a floating-point type. */
442 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
445 imm_use_iterator use_iter
;
446 struct occurrence
*occ
;
447 int count
= 0, threshold
;
449 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
451 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
453 gimple use_stmt
= USE_STMT (use_p
);
454 if (is_division_by (use_stmt
, def
))
456 register_division_in (gimple_bb (use_stmt
));
461 /* Do the expensive part only if we can hope to optimize something. */
462 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
463 if (count
>= threshold
)
466 for (occ
= occ_head
; occ
; occ
= occ
->next
)
469 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
472 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
474 if (is_division_by (use_stmt
, def
))
476 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
477 replace_reciprocal (use_p
);
482 for (occ
= occ_head
; occ
; )
489 gate_cse_reciprocals (void)
491 return optimize
&& flag_reciprocal_math
;
494 /* Go through all the floating-point SSA_NAMEs, and call
495 execute_cse_reciprocals_1 on each of them. */
497 execute_cse_reciprocals (void)
502 occ_pool
= create_alloc_pool ("dominators for recip",
503 sizeof (struct occurrence
),
504 n_basic_blocks
/ 3 + 1);
506 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
507 calculate_dominance_info (CDI_DOMINATORS
);
508 calculate_dominance_info (CDI_POST_DOMINATORS
);
510 #ifdef ENABLE_CHECKING
512 gcc_assert (!bb
->aux
);
515 for (arg
= DECL_ARGUMENTS (cfun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
516 if (gimple_default_def (cfun
, arg
)
517 && FLOAT_TYPE_P (TREE_TYPE (arg
))
518 && is_gimple_reg (arg
))
519 execute_cse_reciprocals_1 (NULL
, gimple_default_def (cfun
, arg
));
523 gimple_stmt_iterator gsi
;
527 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
529 phi
= gsi_stmt (gsi
);
530 def
= PHI_RESULT (phi
);
531 if (FLOAT_TYPE_P (TREE_TYPE (def
))
532 && is_gimple_reg (def
))
533 execute_cse_reciprocals_1 (NULL
, def
);
536 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
538 gimple stmt
= gsi_stmt (gsi
);
540 if (gimple_has_lhs (stmt
)
541 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
542 && FLOAT_TYPE_P (TREE_TYPE (def
))
543 && TREE_CODE (def
) == SSA_NAME
)
544 execute_cse_reciprocals_1 (&gsi
, def
);
547 if (optimize_bb_for_size_p (bb
))
550 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
551 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
553 gimple stmt
= gsi_stmt (gsi
);
556 if (is_gimple_assign (stmt
)
557 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
559 tree arg1
= gimple_assign_rhs2 (stmt
);
562 if (TREE_CODE (arg1
) != SSA_NAME
)
565 stmt1
= SSA_NAME_DEF_STMT (arg1
);
567 if (is_gimple_call (stmt1
)
568 && gimple_call_lhs (stmt1
)
569 && (fndecl
= gimple_call_fndecl (stmt1
))
570 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
571 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
573 enum built_in_function code
;
578 code
= DECL_FUNCTION_CODE (fndecl
);
579 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
581 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
585 /* Check that all uses of the SSA name are divisions,
586 otherwise replacing the defining statement will do
589 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
591 gimple stmt2
= USE_STMT (use_p
);
592 if (is_gimple_debug (stmt2
))
594 if (!is_gimple_assign (stmt2
)
595 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
596 || gimple_assign_rhs1 (stmt2
) == arg1
597 || gimple_assign_rhs2 (stmt2
) != arg1
)
606 gimple_replace_lhs (stmt1
, arg1
);
607 gimple_call_set_fndecl (stmt1
, fndecl
);
609 reciprocal_stats
.rfuncs_inserted
++;
611 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
613 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
614 fold_stmt_inplace (stmt
);
622 statistics_counter_event (cfun
, "reciprocal divs inserted",
623 reciprocal_stats
.rdivs_inserted
);
624 statistics_counter_event (cfun
, "reciprocal functions inserted",
625 reciprocal_stats
.rfuncs_inserted
);
627 free_dominance_info (CDI_DOMINATORS
);
628 free_dominance_info (CDI_POST_DOMINATORS
);
629 free_alloc_pool (occ_pool
);
633 struct gimple_opt_pass pass_cse_reciprocals
=
638 gate_cse_reciprocals
, /* gate */
639 execute_cse_reciprocals
, /* execute */
642 0, /* static_pass_number */
644 PROP_ssa
, /* properties_required */
645 0, /* properties_provided */
646 0, /* properties_destroyed */
647 0, /* todo_flags_start */
648 TODO_update_ssa
| TODO_verify_ssa
649 | TODO_verify_stmts
/* todo_flags_finish */
653 /* Records an occurrence at statement USE_STMT in the vector of trees
654 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
655 is not yet initialized. Returns true if the occurrence was pushed on
656 the vector. Adjusts *TOP_BB to be the basic block dominating all
657 statements in the vector. */
660 maybe_record_sincos (VEC(gimple
, heap
) **stmts
,
661 basic_block
*top_bb
, gimple use_stmt
)
663 basic_block use_bb
= gimple_bb (use_stmt
);
665 && (*top_bb
== use_bb
666 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
667 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
669 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
671 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
680 /* Look for sin, cos and cexpi calls with the same argument NAME and
681 create a single call to cexpi CSEing the result in this case.
682 We first walk over all immediate uses of the argument collecting
683 statements that we can CSE in a vector and in a second pass replace
684 the statement rhs with a REALPART or IMAGPART expression on the
685 result of the cexpi call we insert before the use statement that
686 dominates all other candidates. */
689 execute_cse_sincos_1 (tree name
)
691 gimple_stmt_iterator gsi
;
692 imm_use_iterator use_iter
;
693 tree fndecl
, res
, type
;
694 gimple def_stmt
, use_stmt
, stmt
;
695 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
696 VEC(gimple
, heap
) *stmts
= NULL
;
697 basic_block top_bb
= NULL
;
699 bool cfg_changed
= false;
701 type
= TREE_TYPE (name
);
702 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
704 if (gimple_code (use_stmt
) != GIMPLE_CALL
705 || !gimple_call_lhs (use_stmt
)
706 || !(fndecl
= gimple_call_fndecl (use_stmt
))
707 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
710 switch (DECL_FUNCTION_CODE (fndecl
))
712 CASE_FLT_FN (BUILT_IN_COS
):
713 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
716 CASE_FLT_FN (BUILT_IN_SIN
):
717 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
720 CASE_FLT_FN (BUILT_IN_CEXPI
):
721 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
728 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
730 VEC_free(gimple
, heap
, stmts
);
734 /* Simply insert cexpi at the beginning of top_bb but not earlier than
735 the name def statement. */
736 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
739 res
= create_tmp_reg (TREE_TYPE (TREE_TYPE (fndecl
)), "sincostmp");
740 stmt
= gimple_build_call (fndecl
, 1, name
);
741 res
= make_ssa_name (res
, stmt
);
742 gimple_call_set_lhs (stmt
, res
);
744 def_stmt
= SSA_NAME_DEF_STMT (name
);
745 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
746 && gimple_code (def_stmt
) != GIMPLE_PHI
747 && gimple_bb (def_stmt
) == top_bb
)
749 gsi
= gsi_for_stmt (def_stmt
);
750 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
754 gsi
= gsi_after_labels (top_bb
);
755 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
758 sincos_stats
.inserted
++;
760 /* And adjust the recorded old call sites. */
761 for (i
= 0; VEC_iterate(gimple
, stmts
, i
, use_stmt
); ++i
)
764 fndecl
= gimple_call_fndecl (use_stmt
);
766 switch (DECL_FUNCTION_CODE (fndecl
))
768 CASE_FLT_FN (BUILT_IN_COS
):
769 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
772 CASE_FLT_FN (BUILT_IN_SIN
):
773 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
776 CASE_FLT_FN (BUILT_IN_CEXPI
):
784 /* Replace call with a copy. */
785 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
787 gsi
= gsi_for_stmt (use_stmt
);
788 gsi_replace (&gsi
, stmt
, true);
789 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
793 VEC_free(gimple
, heap
, stmts
);
798 /* To evaluate powi(x,n), the floating point value x raised to the
799 constant integer exponent n, we use a hybrid algorithm that
800 combines the "window method" with look-up tables. For an
801 introduction to exponentiation algorithms and "addition chains",
802 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
803 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
804 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
805 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
807 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
808 multiplications to inline before calling the system library's pow
809 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
810 so this default never requires calling pow, powf or powl. */
812 #ifndef POWI_MAX_MULTS
813 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
816 /* The size of the "optimal power tree" lookup table. All
817 exponents less than this value are simply looked up in the
818 powi_table below. This threshold is also used to size the
819 cache of pseudo registers that hold intermediate results. */
820 #define POWI_TABLE_SIZE 256
822 /* The size, in bits of the window, used in the "window method"
823 exponentiation algorithm. This is equivalent to a radix of
824 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
825 #define POWI_WINDOW_SIZE 3
827 /* The following table is an efficient representation of an
828 "optimal power tree". For each value, i, the corresponding
829 value, j, in the table states than an optimal evaluation
830 sequence for calculating pow(x,i) can be found by evaluating
831 pow(x,j)*pow(x,i-j). An optimal power tree for the first
832 100 integers is given in Knuth's "Seminumerical algorithms". */
834 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
836 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
837 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
838 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
839 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
840 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
841 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
842 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
843 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
844 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
845 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
846 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
847 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
848 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
849 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
850 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
851 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
852 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
853 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
854 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
855 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
856 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
857 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
858 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
859 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
860 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
861 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
862 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
863 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
864 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
865 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
866 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
867 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
871 /* Return the number of multiplications required to calculate
872 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
873 subroutine of powi_cost. CACHE is an array indicating
874 which exponents have already been calculated. */
877 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
879 /* If we've already calculated this exponent, then this evaluation
880 doesn't require any additional multiplications. */
885 return powi_lookup_cost (n
- powi_table
[n
], cache
)
886 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
889 /* Return the number of multiplications required to calculate
890 powi(x,n) for an arbitrary x, given the exponent N. This
891 function needs to be kept in sync with powi_as_mults below. */
894 powi_cost (HOST_WIDE_INT n
)
896 bool cache
[POWI_TABLE_SIZE
];
897 unsigned HOST_WIDE_INT digit
;
898 unsigned HOST_WIDE_INT val
;
904 /* Ignore the reciprocal when calculating the cost. */
905 val
= (n
< 0) ? -n
: n
;
907 /* Initialize the exponent cache. */
908 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
913 while (val
>= POWI_TABLE_SIZE
)
917 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
918 result
+= powi_lookup_cost (digit
, cache
)
919 + POWI_WINDOW_SIZE
+ 1;
920 val
>>= POWI_WINDOW_SIZE
;
929 return result
+ powi_lookup_cost (val
, cache
);
932 /* Recursive subroutine of powi_as_mults. This function takes the
933 array, CACHE, of already calculated exponents and an exponent N and
934 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
937 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
938 HOST_WIDE_INT n
, tree
*cache
, tree target
)
940 tree op0
, op1
, ssa_target
;
941 unsigned HOST_WIDE_INT digit
;
944 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
947 ssa_target
= make_ssa_name (target
, NULL
);
949 if (n
< POWI_TABLE_SIZE
)
951 cache
[n
] = ssa_target
;
952 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
, target
);
953 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
, target
);
957 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
958 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
, target
);
959 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
, target
);
963 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
, target
);
967 mult_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, ssa_target
, op0
, op1
);
968 gimple_set_location (mult_stmt
, loc
);
969 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
974 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
975 This function needs to be kept in sync with powi_cost above. */
978 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
979 tree arg0
, HOST_WIDE_INT n
)
981 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
), target
;
985 return build_real (type
, dconst1
);
987 memset (cache
, 0, sizeof (cache
));
990 target
= create_tmp_reg (type
, "powmult");
991 add_referenced_var (target
);
993 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
, target
);
998 /* If the original exponent was negative, reciprocate the result. */
999 target
= make_ssa_name (target
, NULL
);
1000 div_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, target
,
1001 build_real (type
, dconst1
),
1003 gimple_set_location (div_stmt
, loc
);
1004 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1009 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1010 location info LOC. If the arguments are appropriate, create an
1011 equivalent sequence of statements prior to GSI using an optimal
1012 number of multiplications, and return an expession holding the
1016 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1017 tree arg0
, HOST_WIDE_INT n
)
1019 /* Avoid largest negative number. */
1021 && ((n
>= -1 && n
<= 2)
1022 || (optimize_function_for_speed_p (cfun
)
1023 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1024 return powi_as_mults (gsi
, loc
, arg0
, n
);
1029 /* Build a gimple call statement that calls FN with argument ARG.
1030 Set the lhs of the call statement to a fresh SSA name for
1031 variable VAR. If VAR is NULL, first allocate it. Insert the
1032 statement prior to GSI's current position, and return the fresh
1036 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1037 tree
*var
, tree fn
, tree arg
)
1044 *var
= create_tmp_reg (TREE_TYPE (arg
), "powroot");
1045 add_referenced_var (*var
);
1048 call_stmt
= gimple_build_call (fn
, 1, arg
);
1049 ssa_target
= make_ssa_name (*var
, NULL
);
1050 gimple_set_lhs (call_stmt
, ssa_target
);
1051 gimple_set_location (call_stmt
, loc
);
1052 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1057 /* Build a gimple binary operation with the given CODE and arguments
1058 ARG0, ARG1, assigning the result to a new SSA name for variable
1059 TARGET. Insert the statement prior to GSI's current position, and
1060 return the fresh SSA name.*/
1063 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1064 tree target
, enum tree_code code
, tree arg0
, tree arg1
)
1066 tree result
= make_ssa_name (target
, NULL
);
1067 gimple stmt
= gimple_build_assign_with_ops (code
, result
, arg0
, arg1
);
1068 gimple_set_location (stmt
, loc
);
1069 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1073 /* Build a gimple reference operation with the given CODE and argument
1074 ARG, assigning the result to a new SSA name for variable TARGET.
1075 Insert the statement prior to GSI's current position, and return
1076 the fresh SSA name. */
1079 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1080 tree target
, enum tree_code code
, tree arg0
)
1082 tree result
= make_ssa_name (target
, NULL
);
1083 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1084 gimple_set_location (stmt
, loc
);
1085 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1089 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1090 with location info LOC. If possible, create an equivalent and
1091 less expensive sequence of statements prior to GSI, and return an
1092 expession holding the result. */
1095 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1096 tree arg0
, tree arg1
)
1098 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1099 REAL_VALUE_TYPE c2
, dconst3
;
1101 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1102 tree target
= NULL_TREE
;
1103 enum machine_mode mode
;
1104 bool hw_sqrt_exists
;
1106 /* If the exponent isn't a constant, there's nothing of interest
1108 if (TREE_CODE (arg1
) != REAL_CST
)
1111 /* If the exponent is equivalent to an integer, expand to an optimal
1112 multiplication sequence when profitable. */
1113 c
= TREE_REAL_CST (arg1
);
1114 n
= real_to_integer (&c
);
1115 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1117 if (real_identical (&c
, &cint
)
1118 && ((n
>= -1 && n
<= 2)
1119 || (flag_unsafe_math_optimizations
1120 && optimize_insn_for_speed_p ()
1121 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1122 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1124 /* Attempt various optimizations using sqrt and cbrt. */
1125 type
= TREE_TYPE (arg0
);
1126 mode
= TYPE_MODE (type
);
1127 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1129 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1130 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1133 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1134 && !HONOR_SIGNED_ZEROS (mode
))
1135 return build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1137 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1138 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1139 so do this optimization even if -Os. Don't do this optimization
1140 if we don't have a hardware sqrt insn. */
1141 dconst1_4
= dconst1
;
1142 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1143 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1145 if (flag_unsafe_math_optimizations
1147 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1151 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1154 return build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sqrt_arg0
);
1157 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1158 optimizing for space. Don't do this optimization if we don't have
1159 a hardware sqrt insn. */
1160 real_from_integer (&dconst3_4
, VOIDmode
, 3, 0, 0);
1161 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1163 if (flag_unsafe_math_optimizations
1165 && optimize_function_for_speed_p (cfun
)
1166 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1170 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1173 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sqrt_arg0
);
1175 /* sqrt(x) * sqrt(sqrt(x)) */
1176 return build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1177 sqrt_arg0
, sqrt_sqrt
);
1180 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1181 optimizations since 1./3. is not exactly representable. If x
1182 is negative and finite, the correct value of pow(x,1./3.) is
1183 a NaN with the "invalid" exception raised, because the value
1184 of 1./3. actually has an even denominator. The correct value
1185 of cbrt(x) is a negative real value. */
1186 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1187 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1189 if (flag_unsafe_math_optimizations
1191 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1192 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1193 return build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, arg0
);
1195 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1196 if we don't have a hardware sqrt insn. */
1197 dconst1_6
= dconst1_3
;
1198 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1200 if (flag_unsafe_math_optimizations
1203 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1204 && optimize_function_for_speed_p (cfun
)
1206 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1209 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1212 return build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, sqrt_arg0
);
1215 /* Optimize pow(x,c), where n = 2c for some nonzero integer n, into
1217 sqrt(x) * powi(x, n/2), n > 0;
1218 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1220 Do not calculate the powi factor when n/2 = 0. */
1221 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1222 n
= real_to_integer (&c2
);
1223 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1225 if (flag_unsafe_math_optimizations
1227 && real_identical (&c2
, &cint
))
1229 tree powi_x_ndiv2
= NULL_TREE
;
1231 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1232 possible or profitable, give up. Skip the degenerate case when
1233 n is 1 or -1, where the result is always 1. */
1234 if (abs_hwi (n
) != 1)
1236 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1242 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1243 result of the optimal multiply sequence just calculated. */
1244 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1246 if (abs_hwi (n
) == 1)
1249 result
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1250 sqrt_arg0
, powi_x_ndiv2
);
1252 /* If n is negative, reciprocate the result. */
1254 result
= build_and_insert_binop (gsi
, loc
, target
, RDIV_EXPR
,
1255 build_real (type
, dconst1
), result
);
1259 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1261 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1262 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1264 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1265 different from pow(x, 1./3.) due to rounding and behavior with
1266 negative x, we need to constrain this transformation to unsafe
1267 math and positive x or finite math. */
1268 real_from_integer (&dconst3
, VOIDmode
, 3, 0, 0);
1269 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1270 real_round (&c2
, mode
, &c2
);
1271 n
= real_to_integer (&c2
);
1272 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1273 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1274 real_convert (&c2
, mode
, &c2
);
1276 if (flag_unsafe_math_optimizations
1278 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1279 && real_identical (&c2
, &c
)
1280 && optimize_function_for_speed_p (cfun
)
1281 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1283 tree powi_x_ndiv3
= NULL_TREE
;
1285 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1286 possible or profitable, give up. Skip the degenerate case when
1287 abs(n) < 3, where the result is always 1. */
1288 if (abs_hwi (n
) >= 3)
1290 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1296 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1297 as that creates an unnecessary variable. Instead, just produce
1298 either cbrt(x) or cbrt(x) * cbrt(x). */
1299 cbrt_x
= build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, arg0
);
1301 if (abs_hwi (n
) % 3 == 1)
1302 powi_cbrt_x
= cbrt_x
;
1304 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1307 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1308 if (abs_hwi (n
) < 3)
1309 result
= powi_cbrt_x
;
1311 result
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1312 powi_x_ndiv3
, powi_cbrt_x
);
1314 /* If n is negative, reciprocate the result. */
1316 result
= build_and_insert_binop (gsi
, loc
, target
, RDIV_EXPR
,
1317 build_real (type
, dconst1
), result
);
1322 /* No optimizations succeeded. */
1326 /* ARG is the argument to a cabs builtin call in GSI with location info
1327 LOC. Create a sequence of statements prior to GSI that calculates
1328 sqrt(R*R + I*I), where R and I are the real and imaginary components
1329 of ARG, respectively. Return an expression holding the result. */
1332 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1334 tree target
, real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1335 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1336 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1337 enum machine_mode mode
= TYPE_MODE (type
);
1339 if (!flag_unsafe_math_optimizations
1340 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1342 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1345 target
= create_tmp_reg (type
, "cabs");
1346 add_referenced_var (target
);
1348 real_part
= build_and_insert_ref (gsi
, loc
, type
, target
,
1349 REALPART_EXPR
, arg
);
1350 addend1
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1351 real_part
, real_part
);
1352 imag_part
= build_and_insert_ref (gsi
, loc
, type
, target
,
1353 IMAGPART_EXPR
, arg
);
1354 addend2
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1355 imag_part
, imag_part
);
1356 sum
= build_and_insert_binop (gsi
, loc
, target
, PLUS_EXPR
, addend1
, addend2
);
1357 result
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sum
);
1362 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1363 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1364 an optimal number of multiplies, when n is a constant. */
1367 execute_cse_sincos (void)
1370 bool cfg_changed
= false;
1372 calculate_dominance_info (CDI_DOMINATORS
);
1373 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1377 gimple_stmt_iterator gsi
;
1379 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1381 gimple stmt
= gsi_stmt (gsi
);
1384 if (is_gimple_call (stmt
)
1385 && gimple_call_lhs (stmt
)
1386 && (fndecl
= gimple_call_fndecl (stmt
))
1387 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1389 tree arg
, arg0
, arg1
, result
;
1393 switch (DECL_FUNCTION_CODE (fndecl
))
1395 CASE_FLT_FN (BUILT_IN_COS
):
1396 CASE_FLT_FN (BUILT_IN_SIN
):
1397 CASE_FLT_FN (BUILT_IN_CEXPI
):
1398 /* Make sure we have either sincos or cexp. */
1399 if (!TARGET_HAS_SINCOS
&& !TARGET_C99_FUNCTIONS
)
1402 arg
= gimple_call_arg (stmt
, 0);
1403 if (TREE_CODE (arg
) == SSA_NAME
)
1404 cfg_changed
|= execute_cse_sincos_1 (arg
);
1407 CASE_FLT_FN (BUILT_IN_POW
):
1408 arg0
= gimple_call_arg (stmt
, 0);
1409 arg1
= gimple_call_arg (stmt
, 1);
1411 loc
= gimple_location (stmt
);
1412 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1416 tree lhs
= gimple_get_lhs (stmt
);
1417 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1418 gimple_set_location (new_stmt
, loc
);
1419 unlink_stmt_vdef (stmt
);
1420 gsi_replace (&gsi
, new_stmt
, true);
1424 CASE_FLT_FN (BUILT_IN_POWI
):
1425 arg0
= gimple_call_arg (stmt
, 0);
1426 arg1
= gimple_call_arg (stmt
, 1);
1427 if (!host_integerp (arg1
, 0))
1430 n
= TREE_INT_CST_LOW (arg1
);
1431 loc
= gimple_location (stmt
);
1432 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1436 tree lhs
= gimple_get_lhs (stmt
);
1437 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1438 gimple_set_location (new_stmt
, loc
);
1439 unlink_stmt_vdef (stmt
);
1440 gsi_replace (&gsi
, new_stmt
, true);
1444 CASE_FLT_FN (BUILT_IN_CABS
):
1445 arg0
= gimple_call_arg (stmt
, 0);
1446 loc
= gimple_location (stmt
);
1447 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1451 tree lhs
= gimple_get_lhs (stmt
);
1452 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1453 gimple_set_location (new_stmt
, loc
);
1454 unlink_stmt_vdef (stmt
);
1455 gsi_replace (&gsi
, new_stmt
, true);
1465 statistics_counter_event (cfun
, "sincos statements inserted",
1466 sincos_stats
.inserted
);
1468 free_dominance_info (CDI_DOMINATORS
);
1469 return cfg_changed
? TODO_cleanup_cfg
: 0;
1473 gate_cse_sincos (void)
1475 /* We no longer require either sincos or cexp, since powi expansion
1476 piggybacks on this pass. */
1480 struct gimple_opt_pass pass_cse_sincos
=
1484 "sincos", /* name */
1485 gate_cse_sincos
, /* gate */
1486 execute_cse_sincos
, /* execute */
1489 0, /* static_pass_number */
1490 TV_NONE
, /* tv_id */
1491 PROP_ssa
, /* properties_required */
1492 0, /* properties_provided */
1493 0, /* properties_destroyed */
1494 0, /* todo_flags_start */
1495 TODO_update_ssa
| TODO_verify_ssa
1496 | TODO_verify_stmts
/* todo_flags_finish */
1500 /* A symbolic number is used to detect byte permutation and selection
1501 patterns. Therefore the field N contains an artificial number
1502 consisting of byte size markers:
1504 0 - byte has the value 0
1505 1..size - byte contains the content of the byte
1506 number indexed with that value minus one */
1508 struct symbolic_number
{
1509 unsigned HOST_WIDEST_INT n
;
1513 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1514 number N. Return false if the requested operation is not permitted
1515 on a symbolic number. */
1518 do_shift_rotate (enum tree_code code
,
1519 struct symbolic_number
*n
,
1525 /* Zero out the extra bits of N in order to avoid them being shifted
1526 into the significant bits. */
1527 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1528 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1539 n
->n
= (n
->n
<< count
) | (n
->n
>> ((n
->size
* BITS_PER_UNIT
) - count
));
1542 n
->n
= (n
->n
>> count
) | (n
->n
<< ((n
->size
* BITS_PER_UNIT
) - count
));
1547 /* Zero unused bits for size. */
1548 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1549 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1553 /* Perform sanity checking for the symbolic number N and the gimple
1557 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1561 lhs_type
= gimple_expr_type (stmt
);
1563 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1566 if (TYPE_PRECISION (lhs_type
) != n
->size
* BITS_PER_UNIT
)
1572 /* find_bswap_1 invokes itself recursively with N and tries to perform
1573 the operation given by the rhs of STMT on the result. If the
1574 operation could successfully be executed the function returns the
1575 tree expression of the source operand and NULL otherwise. */
1578 find_bswap_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1580 enum tree_code code
;
1581 tree rhs1
, rhs2
= NULL
;
1582 gimple rhs1_stmt
, rhs2_stmt
;
1584 enum gimple_rhs_class rhs_class
;
1586 if (!limit
|| !is_gimple_assign (stmt
))
1589 rhs1
= gimple_assign_rhs1 (stmt
);
1591 if (TREE_CODE (rhs1
) != SSA_NAME
)
1594 code
= gimple_assign_rhs_code (stmt
);
1595 rhs_class
= gimple_assign_rhs_class (stmt
);
1596 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1598 if (rhs_class
== GIMPLE_BINARY_RHS
)
1599 rhs2
= gimple_assign_rhs2 (stmt
);
1601 /* Handle unary rhs and binary rhs with integer constants as second
1604 if (rhs_class
== GIMPLE_UNARY_RHS
1605 || (rhs_class
== GIMPLE_BINARY_RHS
1606 && TREE_CODE (rhs2
) == INTEGER_CST
))
1608 if (code
!= BIT_AND_EXPR
1609 && code
!= LSHIFT_EXPR
1610 && code
!= RSHIFT_EXPR
1611 && code
!= LROTATE_EXPR
1612 && code
!= RROTATE_EXPR
1614 && code
!= CONVERT_EXPR
)
1617 source_expr1
= find_bswap_1 (rhs1_stmt
, n
, limit
- 1);
1619 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
1620 to initialize the symbolic number. */
1623 /* Set up the symbolic number N by setting each byte to a
1624 value between 1 and the byte size of rhs1. The highest
1625 order byte is set to n->size and the lowest order
1627 n
->size
= TYPE_PRECISION (TREE_TYPE (rhs1
));
1628 if (n
->size
% BITS_PER_UNIT
!= 0)
1630 n
->size
/= BITS_PER_UNIT
;
1631 n
->n
= (sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1632 (unsigned HOST_WIDEST_INT
)0x08070605 << 32 | 0x04030201);
1634 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1635 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 <<
1636 (n
->size
* BITS_PER_UNIT
)) - 1;
1638 source_expr1
= rhs1
;
1646 unsigned HOST_WIDEST_INT val
= widest_int_cst_value (rhs2
);
1647 unsigned HOST_WIDEST_INT tmp
= val
;
1649 /* Only constants masking full bytes are allowed. */
1650 for (i
= 0; i
< n
->size
; i
++, tmp
>>= BITS_PER_UNIT
)
1651 if ((tmp
& 0xff) != 0 && (tmp
& 0xff) != 0xff)
1661 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1668 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1669 if (type_size
% BITS_PER_UNIT
!= 0)
1672 if (type_size
/ BITS_PER_UNIT
< (int)(sizeof (HOST_WIDEST_INT
)))
1674 /* If STMT casts to a smaller type mask out the bits not
1675 belonging to the target type. */
1676 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << type_size
) - 1;
1678 n
->size
= type_size
/ BITS_PER_UNIT
;
1684 return verify_symbolic_number_p (n
, stmt
) ? source_expr1
: NULL
;
1687 /* Handle binary rhs. */
1689 if (rhs_class
== GIMPLE_BINARY_RHS
)
1691 struct symbolic_number n1
, n2
;
1694 if (code
!= BIT_IOR_EXPR
)
1697 if (TREE_CODE (rhs2
) != SSA_NAME
)
1700 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1705 source_expr1
= find_bswap_1 (rhs1_stmt
, &n1
, limit
- 1);
1710 source_expr2
= find_bswap_1 (rhs2_stmt
, &n2
, limit
- 1);
1712 if (source_expr1
!= source_expr2
1713 || n1
.size
!= n2
.size
)
1719 if (!verify_symbolic_number_p (n
, stmt
))
1726 return source_expr1
;
1731 /* Check if STMT completes a bswap implementation consisting of ORs,
1732 SHIFTs and ANDs. Return the source tree expression on which the
1733 byte swap is performed and NULL if no bswap was found. */
1736 find_bswap (gimple stmt
)
1738 /* The number which the find_bswap result should match in order to
1739 have a full byte swap. The number is shifted to the left according
1740 to the size of the symbolic number before using it. */
1741 unsigned HOST_WIDEST_INT cmp
=
1742 sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1743 (unsigned HOST_WIDEST_INT
)0x01020304 << 32 | 0x05060708;
1745 struct symbolic_number n
;
1749 /* The last parameter determines the depth search limit. It usually
1750 correlates directly to the number of bytes to be touched. We
1751 increase that number by three here in order to also
1752 cover signed -> unsigned converions of the src operand as can be seen
1753 in libgcc, and for initial shift/and operation of the src operand. */
1754 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
1755 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
1756 source_expr
= find_bswap_1 (stmt
, &n
, limit
);
1761 /* Zero out the extra bits of N and CMP. */
1762 if (n
.size
< (int)sizeof (HOST_WIDEST_INT
))
1764 unsigned HOST_WIDEST_INT mask
=
1765 ((unsigned HOST_WIDEST_INT
)1 << (n
.size
* BITS_PER_UNIT
)) - 1;
1768 cmp
>>= (sizeof (HOST_WIDEST_INT
) - n
.size
) * BITS_PER_UNIT
;
1771 /* A complete byte swap should make the symbolic number to start
1772 with the largest digit in the highest order byte. */
1779 /* Find manual byte swap implementations and turn them into a bswap
1780 builtin invokation. */
1783 execute_optimize_bswap (void)
1786 bool bswap32_p
, bswap64_p
;
1787 bool changed
= false;
1788 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
1790 if (BITS_PER_UNIT
!= 8)
1793 if (sizeof (HOST_WIDEST_INT
) < 8)
1796 bswap32_p
= (built_in_decls
[BUILT_IN_BSWAP32
]
1797 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
1798 bswap64_p
= (built_in_decls
[BUILT_IN_BSWAP64
]
1799 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
1800 || (bswap32_p
&& word_mode
== SImode
)));
1802 if (!bswap32_p
&& !bswap64_p
)
1805 /* Determine the argument type of the builtins. The code later on
1806 assumes that the return and argument type are the same. */
1809 tree fndecl
= built_in_decls
[BUILT_IN_BSWAP32
];
1810 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1815 tree fndecl
= built_in_decls
[BUILT_IN_BSWAP64
];
1816 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1819 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
1823 gimple_stmt_iterator gsi
;
1825 /* We do a reverse scan for bswap patterns to make sure we get the
1826 widest match. As bswap pattern matching doesn't handle
1827 previously inserted smaller bswap replacements as sub-
1828 patterns, the wider variant wouldn't be detected. */
1829 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
1831 gimple stmt
= gsi_stmt (gsi
);
1832 tree bswap_src
, bswap_type
;
1834 tree fndecl
= NULL_TREE
;
1838 if (!is_gimple_assign (stmt
)
1839 || gimple_assign_rhs_code (stmt
) != BIT_IOR_EXPR
)
1842 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1849 fndecl
= built_in_decls
[BUILT_IN_BSWAP32
];
1850 bswap_type
= bswap32_type
;
1856 fndecl
= built_in_decls
[BUILT_IN_BSWAP64
];
1857 bswap_type
= bswap64_type
;
1867 bswap_src
= find_bswap (stmt
);
1873 if (type_size
== 32)
1874 bswap_stats
.found_32bit
++;
1876 bswap_stats
.found_64bit
++;
1878 bswap_tmp
= bswap_src
;
1880 /* Convert the src expression if necessary. */
1881 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1883 gimple convert_stmt
;
1885 bswap_tmp
= create_tmp_var (bswap_type
, "bswapsrc");
1886 add_referenced_var (bswap_tmp
);
1887 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1889 convert_stmt
= gimple_build_assign_with_ops (
1890 CONVERT_EXPR
, bswap_tmp
, bswap_src
, NULL
);
1891 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1894 call
= gimple_build_call (fndecl
, 1, bswap_tmp
);
1896 bswap_tmp
= gimple_assign_lhs (stmt
);
1898 /* Convert the result if necessary. */
1899 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1901 gimple convert_stmt
;
1903 bswap_tmp
= create_tmp_var (bswap_type
, "bswapdst");
1904 add_referenced_var (bswap_tmp
);
1905 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1906 convert_stmt
= gimple_build_assign_with_ops (
1907 CONVERT_EXPR
, gimple_assign_lhs (stmt
), bswap_tmp
, NULL
);
1908 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1911 gimple_call_set_lhs (call
, bswap_tmp
);
1915 fprintf (dump_file
, "%d bit bswap implementation found at: ",
1917 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1920 gsi_insert_after (&gsi
, call
, GSI_SAME_STMT
);
1921 gsi_remove (&gsi
, true);
1925 statistics_counter_event (cfun
, "32-bit bswap implementations found",
1926 bswap_stats
.found_32bit
);
1927 statistics_counter_event (cfun
, "64-bit bswap implementations found",
1928 bswap_stats
.found_64bit
);
1930 return (changed
? TODO_update_ssa
| TODO_verify_ssa
1931 | TODO_verify_stmts
: 0);
1935 gate_optimize_bswap (void)
1937 return flag_expensive_optimizations
&& optimize
;
1940 struct gimple_opt_pass pass_optimize_bswap
=
1945 gate_optimize_bswap
, /* gate */
1946 execute_optimize_bswap
, /* execute */
1949 0, /* static_pass_number */
1950 TV_NONE
, /* tv_id */
1951 PROP_ssa
, /* properties_required */
1952 0, /* properties_provided */
1953 0, /* properties_destroyed */
1954 0, /* todo_flags_start */
1955 0 /* todo_flags_finish */
1959 /* Return true if RHS is a suitable operand for a widening multiplication.
1960 There are two cases:
1962 - RHS makes some value twice as wide. Store that value in *NEW_RHS_OUT
1963 if so, and store its type in *TYPE_OUT.
1965 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
1966 but leave *TYPE_OUT untouched. */
1969 is_widening_mult_rhs_p (tree rhs
, tree
*type_out
, tree
*new_rhs_out
)
1972 tree type
, type1
, rhs1
;
1973 enum tree_code rhs_code
;
1975 if (TREE_CODE (rhs
) == SSA_NAME
)
1977 type
= TREE_TYPE (rhs
);
1978 stmt
= SSA_NAME_DEF_STMT (rhs
);
1979 if (!is_gimple_assign (stmt
))
1982 rhs_code
= gimple_assign_rhs_code (stmt
);
1983 if (TREE_CODE (type
) == INTEGER_TYPE
1984 ? !CONVERT_EXPR_CODE_P (rhs_code
)
1985 : rhs_code
!= FIXED_CONVERT_EXPR
)
1988 rhs1
= gimple_assign_rhs1 (stmt
);
1989 type1
= TREE_TYPE (rhs1
);
1990 if (TREE_CODE (type1
) != TREE_CODE (type
)
1991 || TYPE_PRECISION (type1
) * 2 != TYPE_PRECISION (type
))
1994 *new_rhs_out
= rhs1
;
1999 if (TREE_CODE (rhs
) == INTEGER_CST
)
2009 /* Return true if STMT performs a widening multiplication. If so,
2010 store the unwidened types of the operands in *TYPE1_OUT and *TYPE2_OUT
2011 respectively. Also fill *RHS1_OUT and *RHS2_OUT such that converting
2012 those operands to types *TYPE1_OUT and *TYPE2_OUT would give the
2013 operands of the multiplication. */
2016 is_widening_mult_p (gimple stmt
,
2017 tree
*type1_out
, tree
*rhs1_out
,
2018 tree
*type2_out
, tree
*rhs2_out
)
2022 type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2023 if (TREE_CODE (type
) != INTEGER_TYPE
2024 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2027 if (!is_widening_mult_rhs_p (gimple_assign_rhs1 (stmt
), type1_out
, rhs1_out
))
2030 if (!is_widening_mult_rhs_p (gimple_assign_rhs2 (stmt
), type2_out
, rhs2_out
))
2033 if (*type1_out
== NULL
)
2035 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2037 *type1_out
= *type2_out
;
2040 if (*type2_out
== NULL
)
2042 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2044 *type2_out
= *type1_out
;
2050 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2051 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2052 value is true iff we converted the statement. */
2055 convert_mult_to_widen (gimple stmt
)
2057 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
2058 enum insn_code handler
;
2060 lhs
= gimple_assign_lhs (stmt
);
2061 type
= TREE_TYPE (lhs
);
2062 if (TREE_CODE (type
) != INTEGER_TYPE
)
2065 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2068 if (TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
))
2069 handler
= optab_handler (umul_widen_optab
, TYPE_MODE (type
));
2070 else if (!TYPE_UNSIGNED (type1
) && !TYPE_UNSIGNED (type2
))
2071 handler
= optab_handler (smul_widen_optab
, TYPE_MODE (type
));
2073 handler
= optab_handler (usmul_widen_optab
, TYPE_MODE (type
));
2075 if (handler
== CODE_FOR_nothing
)
2078 gimple_assign_set_rhs1 (stmt
, fold_convert (type1
, rhs1
));
2079 gimple_assign_set_rhs2 (stmt
, fold_convert (type2
, rhs2
));
2080 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2082 widen_mul_stats
.widen_mults_inserted
++;
2086 /* Process a single gimple statement STMT, which is found at the
2087 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2088 rhs (given by CODE), and try to convert it into a
2089 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2090 is true iff we converted the statement. */
2093 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2094 enum tree_code code
)
2096 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2097 tree type
, type1
, type2
;
2098 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2099 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2101 enum tree_code wmult_code
;
2103 lhs
= gimple_assign_lhs (stmt
);
2104 type
= TREE_TYPE (lhs
);
2105 if (TREE_CODE (type
) != INTEGER_TYPE
2106 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2109 if (code
== MINUS_EXPR
)
2110 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2112 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2114 rhs1
= gimple_assign_rhs1 (stmt
);
2115 rhs2
= gimple_assign_rhs2 (stmt
);
2117 if (TREE_CODE (rhs1
) == SSA_NAME
)
2119 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2120 if (is_gimple_assign (rhs1_stmt
))
2121 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2126 if (TREE_CODE (rhs2
) == SSA_NAME
)
2128 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2129 if (is_gimple_assign (rhs2_stmt
))
2130 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2135 if (code
== PLUS_EXPR
&& rhs1_code
== MULT_EXPR
)
2137 if (!is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2138 &type2
, &mult_rhs2
))
2142 else if (rhs2_code
== MULT_EXPR
)
2144 if (!is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2145 &type2
, &mult_rhs2
))
2149 else if (code
== PLUS_EXPR
&& rhs1_code
== WIDEN_MULT_EXPR
)
2151 mult_rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2152 mult_rhs2
= gimple_assign_rhs2 (rhs1_stmt
);
2153 type1
= TREE_TYPE (mult_rhs1
);
2154 type2
= TREE_TYPE (mult_rhs2
);
2157 else if (rhs2_code
== WIDEN_MULT_EXPR
)
2159 mult_rhs1
= gimple_assign_rhs1 (rhs2_stmt
);
2160 mult_rhs2
= gimple_assign_rhs2 (rhs2_stmt
);
2161 type1
= TREE_TYPE (mult_rhs1
);
2162 type2
= TREE_TYPE (mult_rhs2
);
2168 if (TYPE_UNSIGNED (type1
) != TYPE_UNSIGNED (type2
))
2171 /* Verify that the machine can perform a widening multiply
2172 accumulate in this mode/signedness combination, otherwise
2173 this transformation is likely to pessimize code. */
2174 this_optab
= optab_for_tree_code (wmult_code
, type1
, optab_default
);
2175 if (optab_handler (this_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2178 /* ??? May need some type verification here? */
2180 gimple_assign_set_rhs_with_ops_1 (gsi
, wmult_code
,
2181 fold_convert (type1
, mult_rhs1
),
2182 fold_convert (type2
, mult_rhs2
),
2184 update_stmt (gsi_stmt (*gsi
));
2185 widen_mul_stats
.maccs_inserted
++;
2189 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2190 with uses in additions and subtractions to form fused multiply-add
2191 operations. Returns true if successful and MUL_STMT should be removed. */
2194 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2196 tree mul_result
= gimple_get_lhs (mul_stmt
);
2197 tree type
= TREE_TYPE (mul_result
);
2198 gimple use_stmt
, neguse_stmt
, fma_stmt
;
2199 use_operand_p use_p
;
2200 imm_use_iterator imm_iter
;
2202 if (FLOAT_TYPE_P (type
)
2203 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2206 /* We don't want to do bitfield reduction ops. */
2207 if (INTEGRAL_TYPE_P (type
)
2208 && (TYPE_PRECISION (type
)
2209 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2212 /* If the target doesn't support it, don't generate it. We assume that
2213 if fma isn't available then fms, fnma or fnms are not either. */
2214 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2217 /* Make sure that the multiplication statement becomes dead after
2218 the transformation, thus that all uses are transformed to FMAs.
2219 This means we assume that an FMA operation has the same cost
2221 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
2223 enum tree_code use_code
;
2224 tree result
= mul_result
;
2225 bool negate_p
= false;
2227 use_stmt
= USE_STMT (use_p
);
2229 if (is_gimple_debug (use_stmt
))
2232 /* For now restrict this operations to single basic blocks. In theory
2233 we would want to support sinking the multiplication in
2239 to form a fma in the then block and sink the multiplication to the
2241 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2244 if (!is_gimple_assign (use_stmt
))
2247 use_code
= gimple_assign_rhs_code (use_stmt
);
2249 /* A negate on the multiplication leads to FNMA. */
2250 if (use_code
== NEGATE_EXPR
)
2255 result
= gimple_assign_lhs (use_stmt
);
2257 /* Make sure the negate statement becomes dead with this
2258 single transformation. */
2259 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
2260 &use_p
, &neguse_stmt
))
2263 /* Make sure the multiplication isn't also used on that stmt. */
2264 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
2265 if (USE_FROM_PTR (usep
) == mul_result
)
2269 use_stmt
= neguse_stmt
;
2270 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2272 if (!is_gimple_assign (use_stmt
))
2275 use_code
= gimple_assign_rhs_code (use_stmt
);
2282 if (gimple_assign_rhs2 (use_stmt
) == result
)
2283 negate_p
= !negate_p
;
2288 /* FMA can only be formed from PLUS and MINUS. */
2292 /* We can't handle a * b + a * b. */
2293 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
2296 /* While it is possible to validate whether or not the exact form
2297 that we've recognized is available in the backend, the assumption
2298 is that the transformation is never a loss. For instance, suppose
2299 the target only has the plain FMA pattern available. Consider
2300 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
2301 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
2302 still have 3 operations, but in the FMA form the two NEGs are
2303 independant and could be run in parallel. */
2306 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
2308 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
2309 enum tree_code use_code
;
2310 tree addop
, mulop1
= op1
, result
= mul_result
;
2311 bool negate_p
= false;
2313 if (is_gimple_debug (use_stmt
))
2316 use_code
= gimple_assign_rhs_code (use_stmt
);
2317 if (use_code
== NEGATE_EXPR
)
2319 result
= gimple_assign_lhs (use_stmt
);
2320 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
2321 gsi_remove (&gsi
, true);
2322 release_defs (use_stmt
);
2324 use_stmt
= neguse_stmt
;
2325 gsi
= gsi_for_stmt (use_stmt
);
2326 use_code
= gimple_assign_rhs_code (use_stmt
);
2330 if (gimple_assign_rhs1 (use_stmt
) == result
)
2332 addop
= gimple_assign_rhs2 (use_stmt
);
2333 /* a * b - c -> a * b + (-c) */
2334 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2335 addop
= force_gimple_operand_gsi (&gsi
,
2336 build1 (NEGATE_EXPR
,
2338 true, NULL_TREE
, true,
2343 addop
= gimple_assign_rhs1 (use_stmt
);
2344 /* a - b * c -> (-b) * c + a */
2345 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2346 negate_p
= !negate_p
;
2350 mulop1
= force_gimple_operand_gsi (&gsi
,
2351 build1 (NEGATE_EXPR
,
2353 true, NULL_TREE
, true,
2356 fma_stmt
= gimple_build_assign_with_ops3 (FMA_EXPR
,
2357 gimple_assign_lhs (use_stmt
),
2360 gsi_replace (&gsi
, fma_stmt
, true);
2361 widen_mul_stats
.fmas_inserted
++;
2367 /* Find integer multiplications where the operands are extended from
2368 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
2369 where appropriate. */
2372 execute_optimize_widening_mul (void)
2375 bool cfg_changed
= false;
2377 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
2381 gimple_stmt_iterator gsi
;
2383 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
2385 gimple stmt
= gsi_stmt (gsi
);
2386 enum tree_code code
;
2388 if (is_gimple_assign (stmt
))
2390 code
= gimple_assign_rhs_code (stmt
);
2394 if (!convert_mult_to_widen (stmt
)
2395 && convert_mult_to_fma (stmt
,
2396 gimple_assign_rhs1 (stmt
),
2397 gimple_assign_rhs2 (stmt
)))
2399 gsi_remove (&gsi
, true);
2400 release_defs (stmt
);
2407 convert_plusminus_to_widen (&gsi
, stmt
, code
);
2413 else if (is_gimple_call (stmt
)
2414 && gimple_call_lhs (stmt
))
2416 tree fndecl
= gimple_call_fndecl (stmt
);
2418 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
2420 switch (DECL_FUNCTION_CODE (fndecl
))
2425 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
2426 && REAL_VALUES_EQUAL
2427 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
2429 && convert_mult_to_fma (stmt
,
2430 gimple_call_arg (stmt
, 0),
2431 gimple_call_arg (stmt
, 0)))
2433 unlink_stmt_vdef (stmt
);
2434 gsi_remove (&gsi
, true);
2435 release_defs (stmt
);
2436 if (gimple_purge_dead_eh_edges (bb
))
2450 statistics_counter_event (cfun
, "widening multiplications inserted",
2451 widen_mul_stats
.widen_mults_inserted
);
2452 statistics_counter_event (cfun
, "widening maccs inserted",
2453 widen_mul_stats
.maccs_inserted
);
2454 statistics_counter_event (cfun
, "fused multiply-adds inserted",
2455 widen_mul_stats
.fmas_inserted
);
2457 return cfg_changed
? TODO_cleanup_cfg
: 0;
2461 gate_optimize_widening_mul (void)
2463 return flag_expensive_optimizations
&& optimize
;
2466 struct gimple_opt_pass pass_optimize_widening_mul
=
2470 "widening_mul", /* name */
2471 gate_optimize_widening_mul
, /* gate */
2472 execute_optimize_widening_mul
, /* execute */
2475 0, /* static_pass_number */
2476 TV_NONE
, /* tv_id */
2477 PROP_ssa
, /* properties_required */
2478 0, /* properties_provided */
2479 0, /* properties_destroyed */
2480 0, /* todo_flags_start */
2483 | TODO_update_ssa
/* todo_flags_finish */