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_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
402 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
403 SET_USE (use_p
, occ
->recip_def
);
404 fold_stmt_inplace (&gsi
);
405 update_stmt (use_stmt
);
410 /* Free OCC and return one more "struct occurrence" to be freed. */
412 static struct occurrence
*
413 free_bb (struct occurrence
*occ
)
415 struct occurrence
*child
, *next
;
417 /* First get the two pointers hanging off OCC. */
419 child
= occ
->children
;
421 pool_free (occ_pool
, occ
);
423 /* Now ensure that we don't recurse unless it is necessary. */
429 next
= free_bb (next
);
436 /* Look for floating-point divisions among DEF's uses, and try to
437 replace them by multiplications with the reciprocal. Add
438 as many statements computing the reciprocal as needed.
440 DEF must be a GIMPLE register of a floating-point type. */
443 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
446 imm_use_iterator use_iter
;
447 struct occurrence
*occ
;
448 int count
= 0, threshold
;
450 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
452 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
454 gimple use_stmt
= USE_STMT (use_p
);
455 if (is_division_by (use_stmt
, def
))
457 register_division_in (gimple_bb (use_stmt
));
462 /* Do the expensive part only if we can hope to optimize something. */
463 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
464 if (count
>= threshold
)
467 for (occ
= occ_head
; occ
; occ
= occ
->next
)
470 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
473 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
475 if (is_division_by (use_stmt
, def
))
477 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
478 replace_reciprocal (use_p
);
483 for (occ
= occ_head
; occ
; )
490 gate_cse_reciprocals (void)
492 return optimize
&& flag_reciprocal_math
;
495 /* Go through all the floating-point SSA_NAMEs, and call
496 execute_cse_reciprocals_1 on each of them. */
498 execute_cse_reciprocals (void)
503 occ_pool
= create_alloc_pool ("dominators for recip",
504 sizeof (struct occurrence
),
505 n_basic_blocks
/ 3 + 1);
507 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
508 calculate_dominance_info (CDI_DOMINATORS
);
509 calculate_dominance_info (CDI_POST_DOMINATORS
);
511 #ifdef ENABLE_CHECKING
513 gcc_assert (!bb
->aux
);
516 for (arg
= DECL_ARGUMENTS (cfun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
517 if (gimple_default_def (cfun
, arg
)
518 && FLOAT_TYPE_P (TREE_TYPE (arg
))
519 && is_gimple_reg (arg
))
520 execute_cse_reciprocals_1 (NULL
, gimple_default_def (cfun
, arg
));
524 gimple_stmt_iterator gsi
;
528 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
530 phi
= gsi_stmt (gsi
);
531 def
= PHI_RESULT (phi
);
532 if (FLOAT_TYPE_P (TREE_TYPE (def
))
533 && is_gimple_reg (def
))
534 execute_cse_reciprocals_1 (NULL
, def
);
537 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
539 gimple stmt
= gsi_stmt (gsi
);
541 if (gimple_has_lhs (stmt
)
542 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
543 && FLOAT_TYPE_P (TREE_TYPE (def
))
544 && TREE_CODE (def
) == SSA_NAME
)
545 execute_cse_reciprocals_1 (&gsi
, def
);
548 if (optimize_bb_for_size_p (bb
))
551 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
552 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
554 gimple stmt
= gsi_stmt (gsi
);
557 if (is_gimple_assign (stmt
)
558 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
560 tree arg1
= gimple_assign_rhs2 (stmt
);
563 if (TREE_CODE (arg1
) != SSA_NAME
)
566 stmt1
= SSA_NAME_DEF_STMT (arg1
);
568 if (is_gimple_call (stmt1
)
569 && gimple_call_lhs (stmt1
)
570 && (fndecl
= gimple_call_fndecl (stmt1
))
571 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
572 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
574 enum built_in_function code
;
579 code
= DECL_FUNCTION_CODE (fndecl
);
580 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
582 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
586 /* Check that all uses of the SSA name are divisions,
587 otherwise replacing the defining statement will do
590 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
592 gimple stmt2
= USE_STMT (use_p
);
593 if (is_gimple_debug (stmt2
))
595 if (!is_gimple_assign (stmt2
)
596 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
597 || gimple_assign_rhs1 (stmt2
) == arg1
598 || gimple_assign_rhs2 (stmt2
) != arg1
)
607 gimple_replace_lhs (stmt1
, arg1
);
608 gimple_call_set_fndecl (stmt1
, fndecl
);
610 reciprocal_stats
.rfuncs_inserted
++;
612 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
614 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
615 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
616 fold_stmt_inplace (&gsi
);
624 statistics_counter_event (cfun
, "reciprocal divs inserted",
625 reciprocal_stats
.rdivs_inserted
);
626 statistics_counter_event (cfun
, "reciprocal functions inserted",
627 reciprocal_stats
.rfuncs_inserted
);
629 free_dominance_info (CDI_DOMINATORS
);
630 free_dominance_info (CDI_POST_DOMINATORS
);
631 free_alloc_pool (occ_pool
);
635 struct gimple_opt_pass pass_cse_reciprocals
=
640 gate_cse_reciprocals
, /* gate */
641 execute_cse_reciprocals
, /* execute */
644 0, /* static_pass_number */
646 PROP_ssa
, /* properties_required */
647 0, /* properties_provided */
648 0, /* properties_destroyed */
649 0, /* todo_flags_start */
650 TODO_update_ssa
| TODO_verify_ssa
651 | TODO_verify_stmts
/* todo_flags_finish */
655 /* Records an occurrence at statement USE_STMT in the vector of trees
656 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
657 is not yet initialized. Returns true if the occurrence was pushed on
658 the vector. Adjusts *TOP_BB to be the basic block dominating all
659 statements in the vector. */
662 maybe_record_sincos (VEC(gimple
, heap
) **stmts
,
663 basic_block
*top_bb
, gimple use_stmt
)
665 basic_block use_bb
= gimple_bb (use_stmt
);
667 && (*top_bb
== use_bb
668 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
669 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
671 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
673 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
682 /* Look for sin, cos and cexpi calls with the same argument NAME and
683 create a single call to cexpi CSEing the result in this case.
684 We first walk over all immediate uses of the argument collecting
685 statements that we can CSE in a vector and in a second pass replace
686 the statement rhs with a REALPART or IMAGPART expression on the
687 result of the cexpi call we insert before the use statement that
688 dominates all other candidates. */
691 execute_cse_sincos_1 (tree name
)
693 gimple_stmt_iterator gsi
;
694 imm_use_iterator use_iter
;
695 tree fndecl
, res
, type
;
696 gimple def_stmt
, use_stmt
, stmt
;
697 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
698 VEC(gimple
, heap
) *stmts
= NULL
;
699 basic_block top_bb
= NULL
;
701 bool cfg_changed
= false;
703 type
= TREE_TYPE (name
);
704 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
706 if (gimple_code (use_stmt
) != GIMPLE_CALL
707 || !gimple_call_lhs (use_stmt
)
708 || !(fndecl
= gimple_call_fndecl (use_stmt
))
709 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
712 switch (DECL_FUNCTION_CODE (fndecl
))
714 CASE_FLT_FN (BUILT_IN_COS
):
715 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
718 CASE_FLT_FN (BUILT_IN_SIN
):
719 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
722 CASE_FLT_FN (BUILT_IN_CEXPI
):
723 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
730 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
732 VEC_free(gimple
, heap
, stmts
);
736 /* Simply insert cexpi at the beginning of top_bb but not earlier than
737 the name def statement. */
738 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
741 res
= create_tmp_reg (TREE_TYPE (TREE_TYPE (fndecl
)), "sincostmp");
742 stmt
= gimple_build_call (fndecl
, 1, name
);
743 res
= make_ssa_name (res
, stmt
);
744 gimple_call_set_lhs (stmt
, res
);
746 def_stmt
= SSA_NAME_DEF_STMT (name
);
747 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
748 && gimple_code (def_stmt
) != GIMPLE_PHI
749 && gimple_bb (def_stmt
) == top_bb
)
751 gsi
= gsi_for_stmt (def_stmt
);
752 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
756 gsi
= gsi_after_labels (top_bb
);
757 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
760 sincos_stats
.inserted
++;
762 /* And adjust the recorded old call sites. */
763 for (i
= 0; VEC_iterate(gimple
, stmts
, i
, use_stmt
); ++i
)
766 fndecl
= gimple_call_fndecl (use_stmt
);
768 switch (DECL_FUNCTION_CODE (fndecl
))
770 CASE_FLT_FN (BUILT_IN_COS
):
771 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
774 CASE_FLT_FN (BUILT_IN_SIN
):
775 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
778 CASE_FLT_FN (BUILT_IN_CEXPI
):
786 /* Replace call with a copy. */
787 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
789 gsi
= gsi_for_stmt (use_stmt
);
790 gsi_replace (&gsi
, stmt
, true);
791 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
795 VEC_free(gimple
, heap
, stmts
);
800 /* To evaluate powi(x,n), the floating point value x raised to the
801 constant integer exponent n, we use a hybrid algorithm that
802 combines the "window method" with look-up tables. For an
803 introduction to exponentiation algorithms and "addition chains",
804 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
805 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
806 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
807 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
809 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
810 multiplications to inline before calling the system library's pow
811 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
812 so this default never requires calling pow, powf or powl. */
814 #ifndef POWI_MAX_MULTS
815 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
818 /* The size of the "optimal power tree" lookup table. All
819 exponents less than this value are simply looked up in the
820 powi_table below. This threshold is also used to size the
821 cache of pseudo registers that hold intermediate results. */
822 #define POWI_TABLE_SIZE 256
824 /* The size, in bits of the window, used in the "window method"
825 exponentiation algorithm. This is equivalent to a radix of
826 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
827 #define POWI_WINDOW_SIZE 3
829 /* The following table is an efficient representation of an
830 "optimal power tree". For each value, i, the corresponding
831 value, j, in the table states than an optimal evaluation
832 sequence for calculating pow(x,i) can be found by evaluating
833 pow(x,j)*pow(x,i-j). An optimal power tree for the first
834 100 integers is given in Knuth's "Seminumerical algorithms". */
836 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
838 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
839 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
840 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
841 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
842 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
843 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
844 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
845 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
846 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
847 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
848 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
849 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
850 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
851 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
852 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
853 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
854 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
855 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
856 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
857 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
858 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
859 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
860 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
861 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
862 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
863 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
864 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
865 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
866 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
867 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
868 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
869 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
873 /* Return the number of multiplications required to calculate
874 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
875 subroutine of powi_cost. CACHE is an array indicating
876 which exponents have already been calculated. */
879 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
881 /* If we've already calculated this exponent, then this evaluation
882 doesn't require any additional multiplications. */
887 return powi_lookup_cost (n
- powi_table
[n
], cache
)
888 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
891 /* Return the number of multiplications required to calculate
892 powi(x,n) for an arbitrary x, given the exponent N. This
893 function needs to be kept in sync with powi_as_mults below. */
896 powi_cost (HOST_WIDE_INT n
)
898 bool cache
[POWI_TABLE_SIZE
];
899 unsigned HOST_WIDE_INT digit
;
900 unsigned HOST_WIDE_INT val
;
906 /* Ignore the reciprocal when calculating the cost. */
907 val
= (n
< 0) ? -n
: n
;
909 /* Initialize the exponent cache. */
910 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
915 while (val
>= POWI_TABLE_SIZE
)
919 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
920 result
+= powi_lookup_cost (digit
, cache
)
921 + POWI_WINDOW_SIZE
+ 1;
922 val
>>= POWI_WINDOW_SIZE
;
931 return result
+ powi_lookup_cost (val
, cache
);
934 /* Recursive subroutine of powi_as_mults. This function takes the
935 array, CACHE, of already calculated exponents and an exponent N and
936 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
939 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
940 HOST_WIDE_INT n
, tree
*cache
, tree target
)
942 tree op0
, op1
, ssa_target
;
943 unsigned HOST_WIDE_INT digit
;
946 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
949 ssa_target
= make_ssa_name (target
, NULL
);
951 if (n
< POWI_TABLE_SIZE
)
953 cache
[n
] = ssa_target
;
954 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
, target
);
955 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
, target
);
959 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
960 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
, target
);
961 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
, target
);
965 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
, target
);
969 mult_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, ssa_target
, op0
, op1
);
970 gimple_set_location (mult_stmt
, loc
);
971 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
976 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
977 This function needs to be kept in sync with powi_cost above. */
980 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
981 tree arg0
, HOST_WIDE_INT n
)
983 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
), target
;
987 return build_real (type
, dconst1
);
989 memset (cache
, 0, sizeof (cache
));
992 target
= create_tmp_reg (type
, "powmult");
993 add_referenced_var (target
);
995 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
, target
);
1000 /* If the original exponent was negative, reciprocate the result. */
1001 target
= make_ssa_name (target
, NULL
);
1002 div_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, target
,
1003 build_real (type
, dconst1
),
1005 gimple_set_location (div_stmt
, loc
);
1006 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1011 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1012 location info LOC. If the arguments are appropriate, create an
1013 equivalent sequence of statements prior to GSI using an optimal
1014 number of multiplications, and return an expession holding the
1018 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1019 tree arg0
, HOST_WIDE_INT n
)
1021 /* Avoid largest negative number. */
1023 && ((n
>= -1 && n
<= 2)
1024 || (optimize_function_for_speed_p (cfun
)
1025 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1026 return powi_as_mults (gsi
, loc
, arg0
, n
);
1031 /* Build a gimple call statement that calls FN with argument ARG.
1032 Set the lhs of the call statement to a fresh SSA name for
1033 variable VAR. If VAR is NULL, first allocate it. Insert the
1034 statement prior to GSI's current position, and return the fresh
1038 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1039 tree
*var
, tree fn
, tree arg
)
1046 *var
= create_tmp_reg (TREE_TYPE (arg
), "powroot");
1047 add_referenced_var (*var
);
1050 call_stmt
= gimple_build_call (fn
, 1, arg
);
1051 ssa_target
= make_ssa_name (*var
, NULL
);
1052 gimple_set_lhs (call_stmt
, ssa_target
);
1053 gimple_set_location (call_stmt
, loc
);
1054 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1059 /* Build a gimple binary operation with the given CODE and arguments
1060 ARG0, ARG1, assigning the result to a new SSA name for variable
1061 TARGET. Insert the statement prior to GSI's current position, and
1062 return the fresh SSA name.*/
1065 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1066 tree target
, enum tree_code code
, tree arg0
, tree arg1
)
1068 tree result
= make_ssa_name (target
, NULL
);
1069 gimple stmt
= gimple_build_assign_with_ops (code
, result
, arg0
, arg1
);
1070 gimple_set_location (stmt
, loc
);
1071 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1075 /* Build a gimple reference operation with the given CODE and argument
1076 ARG, assigning the result to a new SSA name for variable TARGET.
1077 Insert the statement prior to GSI's current position, and return
1078 the fresh SSA name. */
1081 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1082 tree target
, enum tree_code code
, tree arg0
)
1084 tree result
= make_ssa_name (target
, NULL
);
1085 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1086 gimple_set_location (stmt
, loc
);
1087 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1091 /* Build a gimple assignment to cast VAL to TARGET. Insert the statement
1092 prior to GSI's current position, and return the fresh SSA name. */
1095 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1096 tree target
, tree val
)
1098 return build_and_insert_binop (gsi
, loc
, target
, CONVERT_EXPR
, val
, NULL
);
1101 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1102 with location info LOC. If possible, create an equivalent and
1103 less expensive sequence of statements prior to GSI, and return an
1104 expession holding the result. */
1107 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1108 tree arg0
, tree arg1
)
1110 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1111 REAL_VALUE_TYPE c2
, dconst3
;
1113 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1114 tree target
= NULL_TREE
;
1115 enum machine_mode mode
;
1116 bool hw_sqrt_exists
;
1118 /* If the exponent isn't a constant, there's nothing of interest
1120 if (TREE_CODE (arg1
) != REAL_CST
)
1123 /* If the exponent is equivalent to an integer, expand to an optimal
1124 multiplication sequence when profitable. */
1125 c
= TREE_REAL_CST (arg1
);
1126 n
= real_to_integer (&c
);
1127 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1129 if (real_identical (&c
, &cint
)
1130 && ((n
>= -1 && n
<= 2)
1131 || (flag_unsafe_math_optimizations
1132 && optimize_insn_for_speed_p ()
1133 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1134 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1136 /* Attempt various optimizations using sqrt and cbrt. */
1137 type
= TREE_TYPE (arg0
);
1138 mode
= TYPE_MODE (type
);
1139 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1141 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1142 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1145 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1146 && !HONOR_SIGNED_ZEROS (mode
))
1147 return build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1149 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1150 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1151 so do this optimization even if -Os. Don't do this optimization
1152 if we don't have a hardware sqrt insn. */
1153 dconst1_4
= dconst1
;
1154 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1155 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1157 if (flag_unsafe_math_optimizations
1159 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1163 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1166 return build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sqrt_arg0
);
1169 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1170 optimizing for space. Don't do this optimization if we don't have
1171 a hardware sqrt insn. */
1172 real_from_integer (&dconst3_4
, VOIDmode
, 3, 0, 0);
1173 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1175 if (flag_unsafe_math_optimizations
1177 && optimize_function_for_speed_p (cfun
)
1178 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1182 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1185 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sqrt_arg0
);
1187 /* sqrt(x) * sqrt(sqrt(x)) */
1188 return build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1189 sqrt_arg0
, sqrt_sqrt
);
1192 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1193 optimizations since 1./3. is not exactly representable. If x
1194 is negative and finite, the correct value of pow(x,1./3.) is
1195 a NaN with the "invalid" exception raised, because the value
1196 of 1./3. actually has an even denominator. The correct value
1197 of cbrt(x) is a negative real value. */
1198 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1199 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1201 if (flag_unsafe_math_optimizations
1203 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1204 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1205 return build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, arg0
);
1207 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1208 if we don't have a hardware sqrt insn. */
1209 dconst1_6
= dconst1_3
;
1210 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1212 if (flag_unsafe_math_optimizations
1215 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1216 && optimize_function_for_speed_p (cfun
)
1218 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1221 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1224 return build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, sqrt_arg0
);
1227 /* Optimize pow(x,c), where n = 2c for some nonzero integer n, into
1229 sqrt(x) * powi(x, n/2), n > 0;
1230 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1232 Do not calculate the powi factor when n/2 = 0. */
1233 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1234 n
= real_to_integer (&c2
);
1235 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1237 if (flag_unsafe_math_optimizations
1239 && real_identical (&c2
, &cint
))
1241 tree powi_x_ndiv2
= NULL_TREE
;
1243 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1244 possible or profitable, give up. Skip the degenerate case when
1245 n is 1 or -1, where the result is always 1. */
1246 if (absu_hwi (n
) != 1)
1248 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1254 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1255 result of the optimal multiply sequence just calculated. */
1256 sqrt_arg0
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, arg0
);
1258 if (absu_hwi (n
) == 1)
1261 result
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1262 sqrt_arg0
, powi_x_ndiv2
);
1264 /* If n is negative, reciprocate the result. */
1266 result
= build_and_insert_binop (gsi
, loc
, target
, RDIV_EXPR
,
1267 build_real (type
, dconst1
), result
);
1271 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1273 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1274 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1276 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1277 different from pow(x, 1./3.) due to rounding and behavior with
1278 negative x, we need to constrain this transformation to unsafe
1279 math and positive x or finite math. */
1280 real_from_integer (&dconst3
, VOIDmode
, 3, 0, 0);
1281 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1282 real_round (&c2
, mode
, &c2
);
1283 n
= real_to_integer (&c2
);
1284 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1285 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1286 real_convert (&c2
, mode
, &c2
);
1288 if (flag_unsafe_math_optimizations
1290 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1291 && real_identical (&c2
, &c
)
1292 && optimize_function_for_speed_p (cfun
)
1293 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1295 tree powi_x_ndiv3
= NULL_TREE
;
1297 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1298 possible or profitable, give up. Skip the degenerate case when
1299 abs(n) < 3, where the result is always 1. */
1300 if (absu_hwi (n
) >= 3)
1302 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1308 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1309 as that creates an unnecessary variable. Instead, just produce
1310 either cbrt(x) or cbrt(x) * cbrt(x). */
1311 cbrt_x
= build_and_insert_call (gsi
, loc
, &target
, cbrtfn
, arg0
);
1313 if (absu_hwi (n
) % 3 == 1)
1314 powi_cbrt_x
= cbrt_x
;
1316 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1319 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1320 if (absu_hwi (n
) < 3)
1321 result
= powi_cbrt_x
;
1323 result
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1324 powi_x_ndiv3
, powi_cbrt_x
);
1326 /* If n is negative, reciprocate the result. */
1328 result
= build_and_insert_binop (gsi
, loc
, target
, RDIV_EXPR
,
1329 build_real (type
, dconst1
), result
);
1334 /* No optimizations succeeded. */
1338 /* ARG is the argument to a cabs builtin call in GSI with location info
1339 LOC. Create a sequence of statements prior to GSI that calculates
1340 sqrt(R*R + I*I), where R and I are the real and imaginary components
1341 of ARG, respectively. Return an expression holding the result. */
1344 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1346 tree target
, real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1347 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1348 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1349 enum machine_mode mode
= TYPE_MODE (type
);
1351 if (!flag_unsafe_math_optimizations
1352 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1354 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1357 target
= create_tmp_reg (type
, "cabs");
1358 add_referenced_var (target
);
1360 real_part
= build_and_insert_ref (gsi
, loc
, type
, target
,
1361 REALPART_EXPR
, arg
);
1362 addend1
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1363 real_part
, real_part
);
1364 imag_part
= build_and_insert_ref (gsi
, loc
, type
, target
,
1365 IMAGPART_EXPR
, arg
);
1366 addend2
= build_and_insert_binop (gsi
, loc
, target
, MULT_EXPR
,
1367 imag_part
, imag_part
);
1368 sum
= build_and_insert_binop (gsi
, loc
, target
, PLUS_EXPR
, addend1
, addend2
);
1369 result
= build_and_insert_call (gsi
, loc
, &target
, sqrtfn
, sum
);
1374 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1375 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1376 an optimal number of multiplies, when n is a constant. */
1379 execute_cse_sincos (void)
1382 bool cfg_changed
= false;
1384 calculate_dominance_info (CDI_DOMINATORS
);
1385 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1389 gimple_stmt_iterator gsi
;
1391 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1393 gimple stmt
= gsi_stmt (gsi
);
1396 if (is_gimple_call (stmt
)
1397 && gimple_call_lhs (stmt
)
1398 && (fndecl
= gimple_call_fndecl (stmt
))
1399 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1401 tree arg
, arg0
, arg1
, result
;
1405 switch (DECL_FUNCTION_CODE (fndecl
))
1407 CASE_FLT_FN (BUILT_IN_COS
):
1408 CASE_FLT_FN (BUILT_IN_SIN
):
1409 CASE_FLT_FN (BUILT_IN_CEXPI
):
1410 /* Make sure we have either sincos or cexp. */
1411 if (!TARGET_HAS_SINCOS
&& !TARGET_C99_FUNCTIONS
)
1414 arg
= gimple_call_arg (stmt
, 0);
1415 if (TREE_CODE (arg
) == SSA_NAME
)
1416 cfg_changed
|= execute_cse_sincos_1 (arg
);
1419 CASE_FLT_FN (BUILT_IN_POW
):
1420 arg0
= gimple_call_arg (stmt
, 0);
1421 arg1
= gimple_call_arg (stmt
, 1);
1423 loc
= gimple_location (stmt
);
1424 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1428 tree lhs
= gimple_get_lhs (stmt
);
1429 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1430 gimple_set_location (new_stmt
, loc
);
1431 unlink_stmt_vdef (stmt
);
1432 gsi_replace (&gsi
, new_stmt
, true);
1433 if (gimple_vdef (stmt
))
1434 release_ssa_name (gimple_vdef (stmt
));
1438 CASE_FLT_FN (BUILT_IN_POWI
):
1439 arg0
= gimple_call_arg (stmt
, 0);
1440 arg1
= gimple_call_arg (stmt
, 1);
1441 if (!host_integerp (arg1
, 0))
1444 n
= TREE_INT_CST_LOW (arg1
);
1445 loc
= gimple_location (stmt
);
1446 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1450 tree lhs
= gimple_get_lhs (stmt
);
1451 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1452 gimple_set_location (new_stmt
, loc
);
1453 unlink_stmt_vdef (stmt
);
1454 gsi_replace (&gsi
, new_stmt
, true);
1455 if (gimple_vdef (stmt
))
1456 release_ssa_name (gimple_vdef (stmt
));
1460 CASE_FLT_FN (BUILT_IN_CABS
):
1461 arg0
= gimple_call_arg (stmt
, 0);
1462 loc
= gimple_location (stmt
);
1463 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1467 tree lhs
= gimple_get_lhs (stmt
);
1468 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1469 gimple_set_location (new_stmt
, loc
);
1470 unlink_stmt_vdef (stmt
);
1471 gsi_replace (&gsi
, new_stmt
, true);
1472 if (gimple_vdef (stmt
))
1473 release_ssa_name (gimple_vdef (stmt
));
1483 statistics_counter_event (cfun
, "sincos statements inserted",
1484 sincos_stats
.inserted
);
1486 free_dominance_info (CDI_DOMINATORS
);
1487 return cfg_changed
? TODO_cleanup_cfg
: 0;
1491 gate_cse_sincos (void)
1493 /* We no longer require either sincos or cexp, since powi expansion
1494 piggybacks on this pass. */
1498 struct gimple_opt_pass pass_cse_sincos
=
1502 "sincos", /* name */
1503 gate_cse_sincos
, /* gate */
1504 execute_cse_sincos
, /* execute */
1507 0, /* static_pass_number */
1508 TV_NONE
, /* tv_id */
1509 PROP_ssa
, /* properties_required */
1510 0, /* properties_provided */
1511 0, /* properties_destroyed */
1512 0, /* todo_flags_start */
1513 TODO_update_ssa
| TODO_verify_ssa
1514 | TODO_verify_stmts
/* todo_flags_finish */
1518 /* A symbolic number is used to detect byte permutation and selection
1519 patterns. Therefore the field N contains an artificial number
1520 consisting of byte size markers:
1522 0 - byte has the value 0
1523 1..size - byte contains the content of the byte
1524 number indexed with that value minus one */
1526 struct symbolic_number
{
1527 unsigned HOST_WIDEST_INT n
;
1531 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1532 number N. Return false if the requested operation is not permitted
1533 on a symbolic number. */
1536 do_shift_rotate (enum tree_code code
,
1537 struct symbolic_number
*n
,
1543 /* Zero out the extra bits of N in order to avoid them being shifted
1544 into the significant bits. */
1545 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1546 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1557 n
->n
= (n
->n
<< count
) | (n
->n
>> ((n
->size
* BITS_PER_UNIT
) - count
));
1560 n
->n
= (n
->n
>> count
) | (n
->n
<< ((n
->size
* BITS_PER_UNIT
) - count
));
1565 /* Zero unused bits for size. */
1566 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1567 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1571 /* Perform sanity checking for the symbolic number N and the gimple
1575 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1579 lhs_type
= gimple_expr_type (stmt
);
1581 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1584 if (TYPE_PRECISION (lhs_type
) != n
->size
* BITS_PER_UNIT
)
1590 /* find_bswap_1 invokes itself recursively with N and tries to perform
1591 the operation given by the rhs of STMT on the result. If the
1592 operation could successfully be executed the function returns the
1593 tree expression of the source operand and NULL otherwise. */
1596 find_bswap_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1598 enum tree_code code
;
1599 tree rhs1
, rhs2
= NULL
;
1600 gimple rhs1_stmt
, rhs2_stmt
;
1602 enum gimple_rhs_class rhs_class
;
1604 if (!limit
|| !is_gimple_assign (stmt
))
1607 rhs1
= gimple_assign_rhs1 (stmt
);
1609 if (TREE_CODE (rhs1
) != SSA_NAME
)
1612 code
= gimple_assign_rhs_code (stmt
);
1613 rhs_class
= gimple_assign_rhs_class (stmt
);
1614 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1616 if (rhs_class
== GIMPLE_BINARY_RHS
)
1617 rhs2
= gimple_assign_rhs2 (stmt
);
1619 /* Handle unary rhs and binary rhs with integer constants as second
1622 if (rhs_class
== GIMPLE_UNARY_RHS
1623 || (rhs_class
== GIMPLE_BINARY_RHS
1624 && TREE_CODE (rhs2
) == INTEGER_CST
))
1626 if (code
!= BIT_AND_EXPR
1627 && code
!= LSHIFT_EXPR
1628 && code
!= RSHIFT_EXPR
1629 && code
!= LROTATE_EXPR
1630 && code
!= RROTATE_EXPR
1632 && code
!= CONVERT_EXPR
)
1635 source_expr1
= find_bswap_1 (rhs1_stmt
, n
, limit
- 1);
1637 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
1638 to initialize the symbolic number. */
1641 /* Set up the symbolic number N by setting each byte to a
1642 value between 1 and the byte size of rhs1. The highest
1643 order byte is set to n->size and the lowest order
1645 n
->size
= TYPE_PRECISION (TREE_TYPE (rhs1
));
1646 if (n
->size
% BITS_PER_UNIT
!= 0)
1648 n
->size
/= BITS_PER_UNIT
;
1649 n
->n
= (sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1650 (unsigned HOST_WIDEST_INT
)0x08070605 << 32 | 0x04030201);
1652 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1653 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 <<
1654 (n
->size
* BITS_PER_UNIT
)) - 1;
1656 source_expr1
= rhs1
;
1664 unsigned HOST_WIDEST_INT val
= widest_int_cst_value (rhs2
);
1665 unsigned HOST_WIDEST_INT tmp
= val
;
1667 /* Only constants masking full bytes are allowed. */
1668 for (i
= 0; i
< n
->size
; i
++, tmp
>>= BITS_PER_UNIT
)
1669 if ((tmp
& 0xff) != 0 && (tmp
& 0xff) != 0xff)
1679 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1686 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1687 if (type_size
% BITS_PER_UNIT
!= 0)
1690 if (type_size
/ BITS_PER_UNIT
< (int)(sizeof (HOST_WIDEST_INT
)))
1692 /* If STMT casts to a smaller type mask out the bits not
1693 belonging to the target type. */
1694 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << type_size
) - 1;
1696 n
->size
= type_size
/ BITS_PER_UNIT
;
1702 return verify_symbolic_number_p (n
, stmt
) ? source_expr1
: NULL
;
1705 /* Handle binary rhs. */
1707 if (rhs_class
== GIMPLE_BINARY_RHS
)
1709 struct symbolic_number n1
, n2
;
1712 if (code
!= BIT_IOR_EXPR
)
1715 if (TREE_CODE (rhs2
) != SSA_NAME
)
1718 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1723 source_expr1
= find_bswap_1 (rhs1_stmt
, &n1
, limit
- 1);
1728 source_expr2
= find_bswap_1 (rhs2_stmt
, &n2
, limit
- 1);
1730 if (source_expr1
!= source_expr2
1731 || n1
.size
!= n2
.size
)
1737 if (!verify_symbolic_number_p (n
, stmt
))
1744 return source_expr1
;
1749 /* Check if STMT completes a bswap implementation consisting of ORs,
1750 SHIFTs and ANDs. Return the source tree expression on which the
1751 byte swap is performed and NULL if no bswap was found. */
1754 find_bswap (gimple stmt
)
1756 /* The number which the find_bswap result should match in order to
1757 have a full byte swap. The number is shifted to the left according
1758 to the size of the symbolic number before using it. */
1759 unsigned HOST_WIDEST_INT cmp
=
1760 sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1761 (unsigned HOST_WIDEST_INT
)0x01020304 << 32 | 0x05060708;
1763 struct symbolic_number n
;
1767 /* The last parameter determines the depth search limit. It usually
1768 correlates directly to the number of bytes to be touched. We
1769 increase that number by three here in order to also
1770 cover signed -> unsigned converions of the src operand as can be seen
1771 in libgcc, and for initial shift/and operation of the src operand. */
1772 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
1773 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
1774 source_expr
= find_bswap_1 (stmt
, &n
, limit
);
1779 /* Zero out the extra bits of N and CMP. */
1780 if (n
.size
< (int)sizeof (HOST_WIDEST_INT
))
1782 unsigned HOST_WIDEST_INT mask
=
1783 ((unsigned HOST_WIDEST_INT
)1 << (n
.size
* BITS_PER_UNIT
)) - 1;
1786 cmp
>>= (sizeof (HOST_WIDEST_INT
) - n
.size
) * BITS_PER_UNIT
;
1789 /* A complete byte swap should make the symbolic number to start
1790 with the largest digit in the highest order byte. */
1797 /* Find manual byte swap implementations and turn them into a bswap
1798 builtin invokation. */
1801 execute_optimize_bswap (void)
1804 bool bswap32_p
, bswap64_p
;
1805 bool changed
= false;
1806 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
1808 if (BITS_PER_UNIT
!= 8)
1811 if (sizeof (HOST_WIDEST_INT
) < 8)
1814 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
1815 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
1816 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
1817 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
1818 || (bswap32_p
&& word_mode
== SImode
)));
1820 if (!bswap32_p
&& !bswap64_p
)
1823 /* Determine the argument type of the builtins. The code later on
1824 assumes that the return and argument type are the same. */
1827 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1828 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1833 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1834 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1837 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
1841 gimple_stmt_iterator gsi
;
1843 /* We do a reverse scan for bswap patterns to make sure we get the
1844 widest match. As bswap pattern matching doesn't handle
1845 previously inserted smaller bswap replacements as sub-
1846 patterns, the wider variant wouldn't be detected. */
1847 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
1849 gimple stmt
= gsi_stmt (gsi
);
1850 tree bswap_src
, bswap_type
;
1852 tree fndecl
= NULL_TREE
;
1856 if (!is_gimple_assign (stmt
)
1857 || gimple_assign_rhs_code (stmt
) != BIT_IOR_EXPR
)
1860 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1867 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1868 bswap_type
= bswap32_type
;
1874 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1875 bswap_type
= bswap64_type
;
1885 bswap_src
= find_bswap (stmt
);
1891 if (type_size
== 32)
1892 bswap_stats
.found_32bit
++;
1894 bswap_stats
.found_64bit
++;
1896 bswap_tmp
= bswap_src
;
1898 /* Convert the src expression 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
, "bswapsrc");
1904 add_referenced_var (bswap_tmp
);
1905 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1907 convert_stmt
= gimple_build_assign_with_ops (
1908 CONVERT_EXPR
, bswap_tmp
, bswap_src
, NULL
);
1909 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1912 call
= gimple_build_call (fndecl
, 1, bswap_tmp
);
1914 bswap_tmp
= gimple_assign_lhs (stmt
);
1916 /* Convert the result if necessary. */
1917 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1919 gimple convert_stmt
;
1921 bswap_tmp
= create_tmp_var (bswap_type
, "bswapdst");
1922 add_referenced_var (bswap_tmp
);
1923 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1924 convert_stmt
= gimple_build_assign_with_ops (
1925 CONVERT_EXPR
, gimple_assign_lhs (stmt
), bswap_tmp
, NULL
);
1926 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1929 gimple_call_set_lhs (call
, bswap_tmp
);
1933 fprintf (dump_file
, "%d bit bswap implementation found at: ",
1935 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1938 gsi_insert_after (&gsi
, call
, GSI_SAME_STMT
);
1939 gsi_remove (&gsi
, true);
1943 statistics_counter_event (cfun
, "32-bit bswap implementations found",
1944 bswap_stats
.found_32bit
);
1945 statistics_counter_event (cfun
, "64-bit bswap implementations found",
1946 bswap_stats
.found_64bit
);
1948 return (changed
? TODO_update_ssa
| TODO_verify_ssa
1949 | TODO_verify_stmts
: 0);
1953 gate_optimize_bswap (void)
1955 return flag_expensive_optimizations
&& optimize
;
1958 struct gimple_opt_pass pass_optimize_bswap
=
1963 gate_optimize_bswap
, /* gate */
1964 execute_optimize_bswap
, /* execute */
1967 0, /* static_pass_number */
1968 TV_NONE
, /* tv_id */
1969 PROP_ssa
, /* properties_required */
1970 0, /* properties_provided */
1971 0, /* properties_destroyed */
1972 0, /* todo_flags_start */
1973 0 /* todo_flags_finish */
1977 /* Return true if RHS is a suitable operand for a widening multiplication,
1978 assuming a target type of TYPE.
1979 There are two cases:
1981 - RHS makes some value at least twice as wide. Store that value
1982 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
1984 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
1985 but leave *TYPE_OUT untouched. */
1988 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
1993 enum tree_code rhs_code
;
1995 if (TREE_CODE (rhs
) == SSA_NAME
)
1997 stmt
= SSA_NAME_DEF_STMT (rhs
);
1998 if (is_gimple_assign (stmt
))
2000 rhs_code
= gimple_assign_rhs_code (stmt
);
2001 if (TREE_CODE (type
) == INTEGER_TYPE
2002 ? !CONVERT_EXPR_CODE_P (rhs_code
)
2003 : rhs_code
!= FIXED_CONVERT_EXPR
)
2007 rhs1
= gimple_assign_rhs1 (stmt
);
2009 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2011 *new_rhs_out
= rhs1
;
2020 type1
= TREE_TYPE (rhs1
);
2022 if (TREE_CODE (type1
) != TREE_CODE (type
)
2023 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2026 *new_rhs_out
= rhs1
;
2031 if (TREE_CODE (rhs
) == INTEGER_CST
)
2041 /* Return true if STMT performs a widening multiplication, assuming the
2042 output type is TYPE. If so, store the unwidened types of the operands
2043 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2044 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2045 and *TYPE2_OUT would give the operands of the multiplication. */
2048 is_widening_mult_p (gimple stmt
,
2049 tree
*type1_out
, tree
*rhs1_out
,
2050 tree
*type2_out
, tree
*rhs2_out
)
2052 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2054 if (TREE_CODE (type
) != INTEGER_TYPE
2055 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2058 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2062 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2066 if (*type1_out
== NULL
)
2068 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2070 *type1_out
= *type2_out
;
2073 if (*type2_out
== NULL
)
2075 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2077 *type2_out
= *type1_out
;
2080 /* Ensure that the larger of the two operands comes first. */
2081 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
2085 *type1_out
= *type2_out
;
2088 *rhs1_out
= *rhs2_out
;
2095 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2096 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2097 value is true iff we converted the statement. */
2100 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
2102 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
, tmp
= NULL
;
2103 enum insn_code handler
;
2104 enum machine_mode to_mode
, from_mode
, actual_mode
;
2106 int actual_precision
;
2107 location_t loc
= gimple_location (stmt
);
2108 bool from_unsigned1
, from_unsigned2
;
2110 lhs
= gimple_assign_lhs (stmt
);
2111 type
= TREE_TYPE (lhs
);
2112 if (TREE_CODE (type
) != INTEGER_TYPE
)
2115 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2118 to_mode
= TYPE_MODE (type
);
2119 from_mode
= TYPE_MODE (type1
);
2120 from_unsigned1
= TYPE_UNSIGNED (type1
);
2121 from_unsigned2
= TYPE_UNSIGNED (type2
);
2123 if (from_unsigned1
&& from_unsigned2
)
2124 op
= umul_widen_optab
;
2125 else if (!from_unsigned1
&& !from_unsigned2
)
2126 op
= smul_widen_optab
;
2128 op
= usmul_widen_optab
;
2130 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
2133 if (handler
== CODE_FOR_nothing
)
2135 if (op
!= smul_widen_optab
)
2137 /* We can use a signed multiply with unsigned types as long as
2138 there is a wider mode to use, or it is the smaller of the two
2139 types that is unsigned. Note that type1 >= type2, always. */
2140 if ((TYPE_UNSIGNED (type1
)
2141 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2142 || (TYPE_UNSIGNED (type2
)
2143 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2145 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2146 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
2150 op
= smul_widen_optab
;
2151 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
2155 if (handler
== CODE_FOR_nothing
)
2158 from_unsigned1
= from_unsigned2
= false;
2164 /* Ensure that the inputs to the handler are in the correct precison
2165 for the opcode. This will be the full mode size. */
2166 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2167 if (2 * actual_precision
> TYPE_PRECISION (type
))
2169 if (actual_precision
!= TYPE_PRECISION (type1
)
2170 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2172 tmp
= create_tmp_var (build_nonstandard_integer_type
2173 (actual_precision
, from_unsigned1
),
2175 rhs1
= build_and_insert_cast (gsi
, loc
, tmp
, rhs1
);
2177 if (actual_precision
!= TYPE_PRECISION (type2
)
2178 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2180 /* Reuse the same type info, if possible. */
2181 if (!tmp
|| from_unsigned1
!= from_unsigned2
)
2182 tmp
= create_tmp_var (build_nonstandard_integer_type
2183 (actual_precision
, from_unsigned2
),
2185 rhs2
= build_and_insert_cast (gsi
, loc
, tmp
, rhs2
);
2188 /* Handle constants. */
2189 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2190 rhs1
= fold_convert (type1
, rhs1
);
2191 if (TREE_CODE (rhs2
) == INTEGER_CST
)
2192 rhs2
= fold_convert (type2
, rhs2
);
2194 gimple_assign_set_rhs1 (stmt
, rhs1
);
2195 gimple_assign_set_rhs2 (stmt
, rhs2
);
2196 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2198 widen_mul_stats
.widen_mults_inserted
++;
2202 /* Process a single gimple statement STMT, which is found at the
2203 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2204 rhs (given by CODE), and try to convert it into a
2205 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2206 is true iff we converted the statement. */
2209 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2210 enum tree_code code
)
2212 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2213 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
2214 tree type
, type1
, type2
, optype
, tmp
= NULL
;
2215 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2216 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2218 enum tree_code wmult_code
;
2219 enum insn_code handler
;
2220 enum machine_mode to_mode
, from_mode
, actual_mode
;
2221 location_t loc
= gimple_location (stmt
);
2222 int actual_precision
;
2223 bool from_unsigned1
, from_unsigned2
;
2225 lhs
= gimple_assign_lhs (stmt
);
2226 type
= TREE_TYPE (lhs
);
2227 if (TREE_CODE (type
) != INTEGER_TYPE
2228 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2231 if (code
== MINUS_EXPR
)
2232 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2234 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2236 rhs1
= gimple_assign_rhs1 (stmt
);
2237 rhs2
= gimple_assign_rhs2 (stmt
);
2239 if (TREE_CODE (rhs1
) == SSA_NAME
)
2241 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2242 if (is_gimple_assign (rhs1_stmt
))
2243 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2246 if (TREE_CODE (rhs2
) == SSA_NAME
)
2248 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2249 if (is_gimple_assign (rhs2_stmt
))
2250 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2253 /* Allow for one conversion statement between the multiply
2254 and addition/subtraction statement. If there are more than
2255 one conversions then we assume they would invalidate this
2256 transformation. If that's not the case then they should have
2257 been folded before now. */
2258 if (CONVERT_EXPR_CODE_P (rhs1_code
))
2260 conv1_stmt
= rhs1_stmt
;
2261 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2262 if (TREE_CODE (rhs1
) == SSA_NAME
)
2264 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2265 if (is_gimple_assign (rhs1_stmt
))
2266 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2271 if (CONVERT_EXPR_CODE_P (rhs2_code
))
2273 conv2_stmt
= rhs2_stmt
;
2274 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
2275 if (TREE_CODE (rhs2
) == SSA_NAME
)
2277 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2278 if (is_gimple_assign (rhs2_stmt
))
2279 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2285 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
2286 is_widening_mult_p, but we still need the rhs returns.
2288 It might also appear that it would be sufficient to use the existing
2289 operands of the widening multiply, but that would limit the choice of
2290 multiply-and-accumulate instructions. */
2291 if (code
== PLUS_EXPR
2292 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
2294 if (!is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2295 &type2
, &mult_rhs2
))
2298 conv_stmt
= conv1_stmt
;
2300 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
2302 if (!is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2303 &type2
, &mult_rhs2
))
2306 conv_stmt
= conv2_stmt
;
2311 to_mode
= TYPE_MODE (type
);
2312 from_mode
= TYPE_MODE (type1
);
2313 from_unsigned1
= TYPE_UNSIGNED (type1
);
2314 from_unsigned2
= TYPE_UNSIGNED (type2
);
2317 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
2318 if (from_unsigned1
!= from_unsigned2
)
2320 if (!INTEGRAL_TYPE_P (type
))
2322 /* We can use a signed multiply with unsigned types as long as
2323 there is a wider mode to use, or it is the smaller of the two
2324 types that is unsigned. Note that type1 >= type2, always. */
2326 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2328 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2330 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2331 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
2335 from_unsigned1
= from_unsigned2
= false;
2336 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
2340 /* If there was a conversion between the multiply and addition
2341 then we need to make sure it fits a multiply-and-accumulate.
2342 The should be a single mode change which does not change the
2346 /* We use the original, unmodified data types for this. */
2347 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
2348 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
2349 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
2350 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
2352 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
2354 /* Conversion is a truncate. */
2355 if (TYPE_PRECISION (to_type
) < data_size
)
2358 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
2360 /* Conversion is an extend. Check it's the right sort. */
2361 if (TYPE_UNSIGNED (from_type
) != is_unsigned
2362 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
2365 /* else convert is a no-op for our purposes. */
2368 /* Verify that the machine can perform a widening multiply
2369 accumulate in this mode/signedness combination, otherwise
2370 this transformation is likely to pessimize code. */
2371 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
2372 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
2373 from_mode
, 0, &actual_mode
);
2375 if (handler
== CODE_FOR_nothing
)
2378 /* Ensure that the inputs to the handler are in the correct precison
2379 for the opcode. This will be the full mode size. */
2380 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2381 if (actual_precision
!= TYPE_PRECISION (type1
)
2382 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2384 tmp
= create_tmp_var (build_nonstandard_integer_type
2385 (actual_precision
, from_unsigned1
),
2387 mult_rhs1
= build_and_insert_cast (gsi
, loc
, tmp
, mult_rhs1
);
2389 if (actual_precision
!= TYPE_PRECISION (type2
)
2390 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2392 if (!tmp
|| from_unsigned1
!= from_unsigned2
)
2393 tmp
= create_tmp_var (build_nonstandard_integer_type
2394 (actual_precision
, from_unsigned2
),
2396 mult_rhs2
= build_and_insert_cast (gsi
, loc
, tmp
, mult_rhs2
);
2399 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
2400 add_rhs
= build_and_insert_cast (gsi
, loc
, create_tmp_var (type
, NULL
),
2403 /* Handle constants. */
2404 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
2405 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
2406 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
2407 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
2409 gimple_assign_set_rhs_with_ops_1 (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
2411 update_stmt (gsi_stmt (*gsi
));
2412 widen_mul_stats
.maccs_inserted
++;
2416 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2417 with uses in additions and subtractions to form fused multiply-add
2418 operations. Returns true if successful and MUL_STMT should be removed. */
2421 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2423 tree mul_result
= gimple_get_lhs (mul_stmt
);
2424 tree type
= TREE_TYPE (mul_result
);
2425 gimple use_stmt
, neguse_stmt
, fma_stmt
;
2426 use_operand_p use_p
;
2427 imm_use_iterator imm_iter
;
2429 if (FLOAT_TYPE_P (type
)
2430 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2433 /* We don't want to do bitfield reduction ops. */
2434 if (INTEGRAL_TYPE_P (type
)
2435 && (TYPE_PRECISION (type
)
2436 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2439 /* If the target doesn't support it, don't generate it. We assume that
2440 if fma isn't available then fms, fnma or fnms are not either. */
2441 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2444 /* If the multiplication has zero uses, it is kept around probably because
2445 of -fnon-call-exceptions. Don't optimize it away in that case,
2447 if (has_zero_uses (mul_result
))
2450 /* Make sure that the multiplication statement becomes dead after
2451 the transformation, thus that all uses are transformed to FMAs.
2452 This means we assume that an FMA operation has the same cost
2454 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
2456 enum tree_code use_code
;
2457 tree result
= mul_result
;
2458 bool negate_p
= false;
2460 use_stmt
= USE_STMT (use_p
);
2462 if (is_gimple_debug (use_stmt
))
2465 /* For now restrict this operations to single basic blocks. In theory
2466 we would want to support sinking the multiplication in
2472 to form a fma in the then block and sink the multiplication to the
2474 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2477 if (!is_gimple_assign (use_stmt
))
2480 use_code
= gimple_assign_rhs_code (use_stmt
);
2482 /* A negate on the multiplication leads to FNMA. */
2483 if (use_code
== NEGATE_EXPR
)
2488 result
= gimple_assign_lhs (use_stmt
);
2490 /* Make sure the negate statement becomes dead with this
2491 single transformation. */
2492 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
2493 &use_p
, &neguse_stmt
))
2496 /* Make sure the multiplication isn't also used on that stmt. */
2497 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
2498 if (USE_FROM_PTR (usep
) == mul_result
)
2502 use_stmt
= neguse_stmt
;
2503 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2505 if (!is_gimple_assign (use_stmt
))
2508 use_code
= gimple_assign_rhs_code (use_stmt
);
2515 if (gimple_assign_rhs2 (use_stmt
) == result
)
2516 negate_p
= !negate_p
;
2521 /* FMA can only be formed from PLUS and MINUS. */
2525 /* We can't handle a * b + a * b. */
2526 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
2529 /* While it is possible to validate whether or not the exact form
2530 that we've recognized is available in the backend, the assumption
2531 is that the transformation is never a loss. For instance, suppose
2532 the target only has the plain FMA pattern available. Consider
2533 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
2534 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
2535 still have 3 operations, but in the FMA form the two NEGs are
2536 independent and could be run in parallel. */
2539 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
2541 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
2542 enum tree_code use_code
;
2543 tree addop
, mulop1
= op1
, result
= mul_result
;
2544 bool negate_p
= false;
2546 if (is_gimple_debug (use_stmt
))
2549 use_code
= gimple_assign_rhs_code (use_stmt
);
2550 if (use_code
== NEGATE_EXPR
)
2552 result
= gimple_assign_lhs (use_stmt
);
2553 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
2554 gsi_remove (&gsi
, true);
2555 release_defs (use_stmt
);
2557 use_stmt
= neguse_stmt
;
2558 gsi
= gsi_for_stmt (use_stmt
);
2559 use_code
= gimple_assign_rhs_code (use_stmt
);
2563 if (gimple_assign_rhs1 (use_stmt
) == result
)
2565 addop
= gimple_assign_rhs2 (use_stmt
);
2566 /* a * b - c -> a * b + (-c) */
2567 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2568 addop
= force_gimple_operand_gsi (&gsi
,
2569 build1 (NEGATE_EXPR
,
2571 true, NULL_TREE
, true,
2576 addop
= gimple_assign_rhs1 (use_stmt
);
2577 /* a - b * c -> (-b) * c + a */
2578 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2579 negate_p
= !negate_p
;
2583 mulop1
= force_gimple_operand_gsi (&gsi
,
2584 build1 (NEGATE_EXPR
,
2586 true, NULL_TREE
, true,
2589 fma_stmt
= gimple_build_assign_with_ops3 (FMA_EXPR
,
2590 gimple_assign_lhs (use_stmt
),
2593 gsi_replace (&gsi
, fma_stmt
, true);
2594 widen_mul_stats
.fmas_inserted
++;
2600 /* Find integer multiplications where the operands are extended from
2601 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
2602 where appropriate. */
2605 execute_optimize_widening_mul (void)
2608 bool cfg_changed
= false;
2610 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
2614 gimple_stmt_iterator gsi
;
2616 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
2618 gimple stmt
= gsi_stmt (gsi
);
2619 enum tree_code code
;
2621 if (is_gimple_assign (stmt
))
2623 code
= gimple_assign_rhs_code (stmt
);
2627 if (!convert_mult_to_widen (stmt
, &gsi
)
2628 && convert_mult_to_fma (stmt
,
2629 gimple_assign_rhs1 (stmt
),
2630 gimple_assign_rhs2 (stmt
)))
2632 gsi_remove (&gsi
, true);
2633 release_defs (stmt
);
2640 convert_plusminus_to_widen (&gsi
, stmt
, code
);
2646 else if (is_gimple_call (stmt
)
2647 && gimple_call_lhs (stmt
))
2649 tree fndecl
= gimple_call_fndecl (stmt
);
2651 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
2653 switch (DECL_FUNCTION_CODE (fndecl
))
2658 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
2659 && REAL_VALUES_EQUAL
2660 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
2662 && convert_mult_to_fma (stmt
,
2663 gimple_call_arg (stmt
, 0),
2664 gimple_call_arg (stmt
, 0)))
2666 unlink_stmt_vdef (stmt
);
2667 if (gsi_remove (&gsi
, true)
2668 && gimple_purge_dead_eh_edges (bb
))
2670 release_defs (stmt
);
2683 statistics_counter_event (cfun
, "widening multiplications inserted",
2684 widen_mul_stats
.widen_mults_inserted
);
2685 statistics_counter_event (cfun
, "widening maccs inserted",
2686 widen_mul_stats
.maccs_inserted
);
2687 statistics_counter_event (cfun
, "fused multiply-adds inserted",
2688 widen_mul_stats
.fmas_inserted
);
2690 return cfg_changed
? TODO_cleanup_cfg
: 0;
2694 gate_optimize_widening_mul (void)
2696 return flag_expensive_optimizations
&& optimize
;
2699 struct gimple_opt_pass pass_optimize_widening_mul
=
2703 "widening_mul", /* name */
2704 gate_optimize_widening_mul
, /* gate */
2705 execute_optimize_widening_mul
, /* execute */
2708 0, /* static_pass_number */
2709 TV_NONE
, /* tv_id */
2710 PROP_ssa
, /* properties_required */
2711 0, /* properties_provided */
2712 0, /* properties_destroyed */
2713 0, /* todo_flags_start */
2716 | TODO_update_ssa
/* todo_flags_finish */