1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* Currently, the only mini-pass in this file tries to CSE reciprocal
21 operations. These are common in sequences such as this one:
23 modulus = sqrt(x*x + y*y + z*z);
28 that can be optimized to
30 modulus = sqrt(x*x + y*y + z*z);
31 rmodulus = 1.0 / modulus;
36 We do this for loop invariant divisors, and with this pass whenever
37 we notice that a division has the same divisor multiple times.
39 Of course, like in PRE, we don't insert a division if a dominator
40 already has one. However, this cannot be done as an extension of
41 PRE for several reasons.
43 First of all, with some experiments it was found out that the
44 transformation is not always useful if there are only two divisions
45 hy the same divisor. This is probably because modern processors
46 can pipeline the divisions; on older, in-order processors it should
47 still be effective to optimize two divisions by the same number.
48 We make this a param, and it shall be called N in the remainder of
51 Second, if trapping math is active, we have less freedom on where
52 to insert divisions: we can only do so in basic blocks that already
53 contain one. (If divisions don't trap, instead, we can insert
54 divisions elsewhere, which will be in blocks that are common dominators
55 of those that have the division).
57 We really don't want to compute the reciprocal unless a division will
58 be found. To do this, we won't insert the division in a basic block
59 that has less than N divisions *post-dominating* it.
61 The algorithm constructs a subset of the dominator tree, holding the
62 blocks containing the divisions and the common dominators to them,
63 and walk it twice. The first walk is in post-order, and it annotates
64 each block with the number of divisions that post-dominate it: this
65 gives information on where divisions can be inserted profitably.
66 The second walk is in pre-order, and it inserts divisions as explained
67 above, and replaces divisions by multiplications.
69 In the best case, the cost of the pass is O(n_statements). In the
70 worst-case, the cost is due to creating the dominator tree subset,
71 with a cost of O(n_basic_blocks ^ 2); however this can only happen
72 for n_statements / n_basic_blocks statements. So, the amortized cost
73 of creating the dominator tree subset is O(n_basic_blocks) and the
74 worst-case cost of the pass is O(n_statements * n_basic_blocks).
76 More practically, the cost will be small because there are few
77 divisions, and they tend to be in the same basic block, so insert_bb
78 is called very few times.
80 If we did this using domwalk.c, an efficient implementation would have
81 to work on all the variables in a single pass, because we could not
82 work on just a subset of the dominator tree, as we do now, and the
83 cost would also be something like O(n_statements * n_basic_blocks).
84 The data structures would be more complex in order to work on all the
85 variables in a single pass. */
89 #include "coretypes.h"
93 #include "tree-flow.h"
94 #include "tree-pass.h"
95 #include "alloc-pool.h"
96 #include "basic-block.h"
98 #include "gimple-pretty-print.h"
100 /* FIXME: RTL headers have to be included here for optabs. */
101 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */
102 #include "expr.h" /* Because optabs.h wants sepops. */
105 /* This structure represents one basic block that either computes a
106 division, or is a common dominator for basic block that compute a
109 /* The basic block represented by this structure. */
112 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
116 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
117 was inserted in BB. */
118 gimple recip_def_stmt
;
120 /* Pointer to a list of "struct occurrence"s for blocks dominated
122 struct occurrence
*children
;
124 /* Pointer to the next "struct occurrence"s in the list of blocks
125 sharing a common dominator. */
126 struct occurrence
*next
;
128 /* The number of divisions that are in BB before compute_merit. The
129 number of divisions that are in BB or post-dominate it after
133 /* True if the basic block has a division, false if it is a common
134 dominator for basic blocks that do. If it is false and trapping
135 math is active, BB is not a candidate for inserting a reciprocal. */
136 bool bb_has_division
;
141 /* Number of 1.0/X ops inserted. */
144 /* Number of 1.0/FUNC ops inserted. */
150 /* Number of cexpi calls inserted. */
156 /* Number of hand-written 16-bit bswaps found. */
159 /* Number of hand-written 32-bit bswaps found. */
162 /* Number of hand-written 64-bit bswaps found. */
168 /* Number of widening multiplication ops inserted. */
169 int widen_mults_inserted
;
171 /* Number of integer multiply-and-accumulate ops inserted. */
174 /* Number of fp fused multiply-add ops inserted. */
178 /* The instance of "struct occurrence" representing the highest
179 interesting block in the dominator tree. */
180 static struct occurrence
*occ_head
;
182 /* Allocation pool for getting instances of "struct occurrence". */
183 static alloc_pool occ_pool
;
187 /* Allocate and return a new struct occurrence for basic block BB, and
188 whose children list is headed by CHILDREN. */
189 static struct occurrence
*
190 occ_new (basic_block bb
, struct occurrence
*children
)
192 struct occurrence
*occ
;
194 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
195 memset (occ
, 0, sizeof (struct occurrence
));
198 occ
->children
= children
;
203 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
204 list of "struct occurrence"s, one per basic block, having IDOM as
205 their common dominator.
207 We try to insert NEW_OCC as deep as possible in the tree, and we also
208 insert any other block that is a common dominator for BB and one
209 block already in the tree. */
212 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
213 struct occurrence
**p_head
)
215 struct occurrence
*occ
, **p_occ
;
217 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
219 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
220 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
223 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
226 occ
->next
= new_occ
->children
;
227 new_occ
->children
= occ
;
229 /* Try the next block (it may as well be dominated by BB). */
232 else if (dom
== occ_bb
)
234 /* OCC_BB dominates BB. Tail recurse to look deeper. */
235 insert_bb (new_occ
, dom
, &occ
->children
);
239 else if (dom
!= idom
)
241 gcc_assert (!dom
->aux
);
243 /* There is a dominator between IDOM and BB, add it and make
244 two children out of NEW_OCC and OCC. First, remove OCC from
250 /* None of the previous blocks has DOM as a dominator: if we tail
251 recursed, we would reexamine them uselessly. Just switch BB with
252 DOM, and go on looking for blocks dominated by DOM. */
253 new_occ
= occ_new (dom
, new_occ
);
258 /* Nothing special, go on with the next element. */
263 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
264 new_occ
->next
= *p_head
;
268 /* Register that we found a division in BB. */
271 register_division_in (basic_block bb
)
273 struct occurrence
*occ
;
275 occ
= (struct occurrence
*) bb
->aux
;
278 occ
= occ_new (bb
, NULL
);
279 insert_bb (occ
, ENTRY_BLOCK_PTR
, &occ_head
);
282 occ
->bb_has_division
= true;
283 occ
->num_divisions
++;
287 /* Compute the number of divisions that postdominate each block in OCC and
291 compute_merit (struct occurrence
*occ
)
293 struct occurrence
*occ_child
;
294 basic_block dom
= occ
->bb
;
296 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
299 if (occ_child
->children
)
300 compute_merit (occ_child
);
303 bb
= single_noncomplex_succ (dom
);
307 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
308 occ
->num_divisions
+= occ_child
->num_divisions
;
313 /* Return whether USE_STMT is a floating-point division by DEF. */
315 is_division_by (gimple use_stmt
, tree def
)
317 return is_gimple_assign (use_stmt
)
318 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
319 && gimple_assign_rhs2 (use_stmt
) == def
320 /* Do not recognize x / x as valid division, as we are getting
321 confused later by replacing all immediate uses x in such
323 && gimple_assign_rhs1 (use_stmt
) != def
;
326 /* Walk the subset of the dominator tree rooted at OCC, setting the
327 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
328 the given basic block. The field may be left NULL, of course,
329 if it is not possible or profitable to do the optimization.
331 DEF_BSI is an iterator pointing at the statement defining DEF.
332 If RECIP_DEF is set, a dominator already has a computation that can
336 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
337 tree def
, tree recip_def
, int threshold
)
341 gimple_stmt_iterator gsi
;
342 struct occurrence
*occ_child
;
345 && (occ
->bb_has_division
|| !flag_trapping_math
)
346 && occ
->num_divisions
>= threshold
)
348 /* Make a variable with the replacement and substitute it. */
349 type
= TREE_TYPE (def
);
350 recip_def
= create_tmp_reg (type
, "reciptmp");
351 new_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, recip_def
,
352 build_one_cst (type
), def
);
354 if (occ
->bb_has_division
)
356 /* Case 1: insert before an existing division. */
357 gsi
= gsi_after_labels (occ
->bb
);
358 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
361 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
363 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
365 /* Case 2: insert right after the definition. Note that this will
366 never happen if the definition statement can throw, because in
367 that case the sole successor of the statement's basic block will
368 dominate all the uses as well. */
369 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
373 /* Case 3: insert in a basic block not containing defs/uses. */
374 gsi
= gsi_after_labels (occ
->bb
);
375 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
378 reciprocal_stats
.rdivs_inserted
++;
380 occ
->recip_def_stmt
= new_stmt
;
383 occ
->recip_def
= recip_def
;
384 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
385 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
389 /* Replace the division at USE_P with a multiplication by the reciprocal, if
393 replace_reciprocal (use_operand_p use_p
)
395 gimple use_stmt
= USE_STMT (use_p
);
396 basic_block bb
= gimple_bb (use_stmt
);
397 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
399 if (optimize_bb_for_speed_p (bb
)
400 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
402 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
403 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
404 SET_USE (use_p
, occ
->recip_def
);
405 fold_stmt_inplace (&gsi
);
406 update_stmt (use_stmt
);
411 /* Free OCC and return one more "struct occurrence" to be freed. */
413 static struct occurrence
*
414 free_bb (struct occurrence
*occ
)
416 struct occurrence
*child
, *next
;
418 /* First get the two pointers hanging off OCC. */
420 child
= occ
->children
;
422 pool_free (occ_pool
, occ
);
424 /* Now ensure that we don't recurse unless it is necessary. */
430 next
= free_bb (next
);
437 /* Look for floating-point divisions among DEF's uses, and try to
438 replace them by multiplications with the reciprocal. Add
439 as many statements computing the reciprocal as needed.
441 DEF must be a GIMPLE register of a floating-point type. */
444 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
447 imm_use_iterator use_iter
;
448 struct occurrence
*occ
;
449 int count
= 0, threshold
;
451 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
453 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
455 gimple use_stmt
= USE_STMT (use_p
);
456 if (is_division_by (use_stmt
, def
))
458 register_division_in (gimple_bb (use_stmt
));
463 /* Do the expensive part only if we can hope to optimize something. */
464 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
465 if (count
>= threshold
)
468 for (occ
= occ_head
; occ
; occ
= occ
->next
)
471 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
474 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
476 if (is_division_by (use_stmt
, def
))
478 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
479 replace_reciprocal (use_p
);
484 for (occ
= occ_head
; occ
; )
491 gate_cse_reciprocals (void)
493 return optimize
&& flag_reciprocal_math
;
496 /* Go through all the floating-point SSA_NAMEs, and call
497 execute_cse_reciprocals_1 on each of them. */
499 execute_cse_reciprocals (void)
504 occ_pool
= create_alloc_pool ("dominators for recip",
505 sizeof (struct occurrence
),
506 n_basic_blocks
/ 3 + 1);
508 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
509 calculate_dominance_info (CDI_DOMINATORS
);
510 calculate_dominance_info (CDI_POST_DOMINATORS
);
512 #ifdef ENABLE_CHECKING
514 gcc_assert (!bb
->aux
);
517 for (arg
= DECL_ARGUMENTS (cfun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
518 if (FLOAT_TYPE_P (TREE_TYPE (arg
))
519 && is_gimple_reg (arg
))
521 tree name
= ssa_default_def (cfun
, arg
);
523 execute_cse_reciprocals_1 (NULL
, name
);
528 gimple_stmt_iterator gsi
;
532 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
534 phi
= gsi_stmt (gsi
);
535 def
= PHI_RESULT (phi
);
536 if (! virtual_operand_p (def
)
537 && FLOAT_TYPE_P (TREE_TYPE (def
)))
538 execute_cse_reciprocals_1 (NULL
, def
);
541 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
543 gimple stmt
= gsi_stmt (gsi
);
545 if (gimple_has_lhs (stmt
)
546 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
547 && FLOAT_TYPE_P (TREE_TYPE (def
))
548 && TREE_CODE (def
) == SSA_NAME
)
549 execute_cse_reciprocals_1 (&gsi
, def
);
552 if (optimize_bb_for_size_p (bb
))
555 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
556 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
558 gimple stmt
= gsi_stmt (gsi
);
561 if (is_gimple_assign (stmt
)
562 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
564 tree arg1
= gimple_assign_rhs2 (stmt
);
567 if (TREE_CODE (arg1
) != SSA_NAME
)
570 stmt1
= SSA_NAME_DEF_STMT (arg1
);
572 if (is_gimple_call (stmt1
)
573 && gimple_call_lhs (stmt1
)
574 && (fndecl
= gimple_call_fndecl (stmt1
))
575 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
576 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
578 enum built_in_function code
;
583 code
= DECL_FUNCTION_CODE (fndecl
);
584 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
586 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
590 /* Check that all uses of the SSA name are divisions,
591 otherwise replacing the defining statement will do
594 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
596 gimple stmt2
= USE_STMT (use_p
);
597 if (is_gimple_debug (stmt2
))
599 if (!is_gimple_assign (stmt2
)
600 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
601 || gimple_assign_rhs1 (stmt2
) == arg1
602 || gimple_assign_rhs2 (stmt2
) != arg1
)
611 gimple_replace_lhs (stmt1
, arg1
);
612 gimple_call_set_fndecl (stmt1
, fndecl
);
614 reciprocal_stats
.rfuncs_inserted
++;
616 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
618 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
619 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
620 fold_stmt_inplace (&gsi
);
628 statistics_counter_event (cfun
, "reciprocal divs inserted",
629 reciprocal_stats
.rdivs_inserted
);
630 statistics_counter_event (cfun
, "reciprocal functions inserted",
631 reciprocal_stats
.rfuncs_inserted
);
633 free_dominance_info (CDI_DOMINATORS
);
634 free_dominance_info (CDI_POST_DOMINATORS
);
635 free_alloc_pool (occ_pool
);
639 struct gimple_opt_pass pass_cse_reciprocals
=
644 OPTGROUP_NONE
, /* optinfo_flags */
645 gate_cse_reciprocals
, /* gate */
646 execute_cse_reciprocals
, /* execute */
649 0, /* static_pass_number */
651 PROP_ssa
, /* properties_required */
652 0, /* properties_provided */
653 0, /* properties_destroyed */
654 0, /* todo_flags_start */
655 TODO_update_ssa
| TODO_verify_ssa
656 | TODO_verify_stmts
/* todo_flags_finish */
660 /* Records an occurrence at statement USE_STMT in the vector of trees
661 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
662 is not yet initialized. Returns true if the occurrence was pushed on
663 the vector. Adjusts *TOP_BB to be the basic block dominating all
664 statements in the vector. */
667 maybe_record_sincos (vec
<gimple
> *stmts
,
668 basic_block
*top_bb
, gimple use_stmt
)
670 basic_block use_bb
= gimple_bb (use_stmt
);
672 && (*top_bb
== use_bb
673 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
674 stmts
->safe_push (use_stmt
);
676 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
678 stmts
->safe_push (use_stmt
);
687 /* Look for sin, cos and cexpi calls with the same argument NAME and
688 create a single call to cexpi CSEing the result in this case.
689 We first walk over all immediate uses of the argument collecting
690 statements that we can CSE in a vector and in a second pass replace
691 the statement rhs with a REALPART or IMAGPART expression on the
692 result of the cexpi call we insert before the use statement that
693 dominates all other candidates. */
696 execute_cse_sincos_1 (tree name
)
698 gimple_stmt_iterator gsi
;
699 imm_use_iterator use_iter
;
700 tree fndecl
, res
, type
;
701 gimple def_stmt
, use_stmt
, stmt
;
702 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
703 vec
<gimple
> stmts
= vNULL
;
704 basic_block top_bb
= NULL
;
706 bool cfg_changed
= false;
708 type
= TREE_TYPE (name
);
709 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
711 if (gimple_code (use_stmt
) != GIMPLE_CALL
712 || !gimple_call_lhs (use_stmt
)
713 || !(fndecl
= gimple_call_fndecl (use_stmt
))
714 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
717 switch (DECL_FUNCTION_CODE (fndecl
))
719 CASE_FLT_FN (BUILT_IN_COS
):
720 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
723 CASE_FLT_FN (BUILT_IN_SIN
):
724 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
727 CASE_FLT_FN (BUILT_IN_CEXPI
):
728 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
735 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
741 /* Simply insert cexpi at the beginning of top_bb but not earlier than
742 the name def statement. */
743 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
746 stmt
= gimple_build_call (fndecl
, 1, name
);
747 res
= make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl
)), stmt
, "sincostmp");
748 gimple_call_set_lhs (stmt
, res
);
750 def_stmt
= SSA_NAME_DEF_STMT (name
);
751 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
752 && gimple_code (def_stmt
) != GIMPLE_PHI
753 && gimple_bb (def_stmt
) == top_bb
)
755 gsi
= gsi_for_stmt (def_stmt
);
756 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
760 gsi
= gsi_after_labels (top_bb
);
761 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
763 sincos_stats
.inserted
++;
765 /* And adjust the recorded old call sites. */
766 for (i
= 0; stmts
.iterate (i
, &use_stmt
); ++i
)
769 fndecl
= gimple_call_fndecl (use_stmt
);
771 switch (DECL_FUNCTION_CODE (fndecl
))
773 CASE_FLT_FN (BUILT_IN_COS
):
774 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
777 CASE_FLT_FN (BUILT_IN_SIN
):
778 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
781 CASE_FLT_FN (BUILT_IN_CEXPI
):
789 /* Replace call with a copy. */
790 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
792 gsi
= gsi_for_stmt (use_stmt
);
793 gsi_replace (&gsi
, stmt
, true);
794 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
803 /* To evaluate powi(x,n), the floating point value x raised to the
804 constant integer exponent n, we use a hybrid algorithm that
805 combines the "window method" with look-up tables. For an
806 introduction to exponentiation algorithms and "addition chains",
807 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
808 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
809 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
810 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
812 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
813 multiplications to inline before calling the system library's pow
814 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
815 so this default never requires calling pow, powf or powl. */
817 #ifndef POWI_MAX_MULTS
818 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
821 /* The size of the "optimal power tree" lookup table. All
822 exponents less than this value are simply looked up in the
823 powi_table below. This threshold is also used to size the
824 cache of pseudo registers that hold intermediate results. */
825 #define POWI_TABLE_SIZE 256
827 /* The size, in bits of the window, used in the "window method"
828 exponentiation algorithm. This is equivalent to a radix of
829 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
830 #define POWI_WINDOW_SIZE 3
832 /* The following table is an efficient representation of an
833 "optimal power tree". For each value, i, the corresponding
834 value, j, in the table states than an optimal evaluation
835 sequence for calculating pow(x,i) can be found by evaluating
836 pow(x,j)*pow(x,i-j). An optimal power tree for the first
837 100 integers is given in Knuth's "Seminumerical algorithms". */
839 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
841 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
842 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
843 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
844 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
845 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
846 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
847 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
848 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
849 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
850 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
851 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
852 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
853 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
854 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
855 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
856 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
857 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
858 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
859 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
860 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
861 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
862 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
863 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
864 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
865 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
866 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
867 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
868 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
869 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
870 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
871 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
872 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
876 /* Return the number of multiplications required to calculate
877 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
878 subroutine of powi_cost. CACHE is an array indicating
879 which exponents have already been calculated. */
882 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
884 /* If we've already calculated this exponent, then this evaluation
885 doesn't require any additional multiplications. */
890 return powi_lookup_cost (n
- powi_table
[n
], cache
)
891 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
894 /* Return the number of multiplications required to calculate
895 powi(x,n) for an arbitrary x, given the exponent N. This
896 function needs to be kept in sync with powi_as_mults below. */
899 powi_cost (HOST_WIDE_INT n
)
901 bool cache
[POWI_TABLE_SIZE
];
902 unsigned HOST_WIDE_INT digit
;
903 unsigned HOST_WIDE_INT val
;
909 /* Ignore the reciprocal when calculating the cost. */
910 val
= (n
< 0) ? -n
: n
;
912 /* Initialize the exponent cache. */
913 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
918 while (val
>= POWI_TABLE_SIZE
)
922 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
923 result
+= powi_lookup_cost (digit
, cache
)
924 + POWI_WINDOW_SIZE
+ 1;
925 val
>>= POWI_WINDOW_SIZE
;
934 return result
+ powi_lookup_cost (val
, cache
);
937 /* Recursive subroutine of powi_as_mults. This function takes the
938 array, CACHE, of already calculated exponents and an exponent N and
939 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
942 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
943 HOST_WIDE_INT n
, tree
*cache
)
945 tree op0
, op1
, ssa_target
;
946 unsigned HOST_WIDE_INT digit
;
949 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
952 ssa_target
= make_temp_ssa_name (type
, NULL
, "powmult");
954 if (n
< POWI_TABLE_SIZE
)
956 cache
[n
] = ssa_target
;
957 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
);
958 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
);
962 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
963 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
);
964 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
);
968 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
);
972 mult_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, ssa_target
, op0
, op1
);
973 gimple_set_location (mult_stmt
, loc
);
974 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
979 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
980 This function needs to be kept in sync with powi_cost above. */
983 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
984 tree arg0
, HOST_WIDE_INT n
)
986 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
);
991 return build_real (type
, dconst1
);
993 memset (cache
, 0, sizeof (cache
));
996 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
);
1000 /* If the original exponent was negative, reciprocate the result. */
1001 target
= make_temp_ssa_name (type
, NULL
, "powmult");
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. Insert the
1033 statement prior to GSI's current position, and return the fresh
1037 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1043 call_stmt
= gimple_build_call (fn
, 1, arg
);
1044 ssa_target
= make_temp_ssa_name (TREE_TYPE (arg
), NULL
, "powroot");
1045 gimple_set_lhs (call_stmt
, ssa_target
);
1046 gimple_set_location (call_stmt
, loc
);
1047 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1052 /* Build a gimple binary operation with the given CODE and arguments
1053 ARG0, ARG1, assigning the result to a new SSA name for variable
1054 TARGET. Insert the statement prior to GSI's current position, and
1055 return the fresh SSA name.*/
1058 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1059 const char *name
, enum tree_code code
,
1060 tree arg0
, tree arg1
)
1062 tree result
= make_temp_ssa_name (TREE_TYPE (arg0
), NULL
, name
);
1063 gimple stmt
= gimple_build_assign_with_ops (code
, result
, arg0
, arg1
);
1064 gimple_set_location (stmt
, loc
);
1065 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1069 /* Build a gimple reference operation with the given CODE and argument
1070 ARG, assigning the result to a new SSA name of TYPE with NAME.
1071 Insert the statement prior to GSI's current position, and return
1072 the fresh SSA name. */
1075 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1076 const char *name
, enum tree_code code
, tree arg0
)
1078 tree result
= make_temp_ssa_name (type
, NULL
, name
);
1079 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1080 gimple_set_location (stmt
, loc
);
1081 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1085 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement
1086 prior to GSI's current position, and return the fresh SSA name. */
1089 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1090 tree type
, tree val
)
1092 tree result
= make_ssa_name (type
, NULL
);
1093 gimple stmt
= gimple_build_assign_with_ops (NOP_EXPR
, result
, val
, NULL_TREE
);
1094 gimple_set_location (stmt
, loc
);
1095 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1099 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1100 with location info LOC. If possible, create an equivalent and
1101 less expensive sequence of statements prior to GSI, and return an
1102 expession holding the result. */
1105 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1106 tree arg0
, tree arg1
)
1108 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1109 REAL_VALUE_TYPE c2
, dconst3
;
1111 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1112 enum machine_mode mode
;
1113 bool hw_sqrt_exists
, c_is_int
, c2_is_int
;
1115 /* If the exponent isn't a constant, there's nothing of interest
1117 if (TREE_CODE (arg1
) != REAL_CST
)
1120 /* If the exponent is equivalent to an integer, expand to an optimal
1121 multiplication sequence when profitable. */
1122 c
= TREE_REAL_CST (arg1
);
1123 n
= real_to_integer (&c
);
1124 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1125 c_is_int
= real_identical (&c
, &cint
);
1128 && ((n
>= -1 && n
<= 2)
1129 || (flag_unsafe_math_optimizations
1130 && optimize_insn_for_speed_p ()
1131 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1132 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1134 /* Attempt various optimizations using sqrt and cbrt. */
1135 type
= TREE_TYPE (arg0
);
1136 mode
= TYPE_MODE (type
);
1137 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1139 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1140 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1143 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1144 && !HONOR_SIGNED_ZEROS (mode
))
1145 return build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1147 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1148 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1149 so do this optimization even if -Os. Don't do this optimization
1150 if we don't have a hardware sqrt insn. */
1151 dconst1_4
= dconst1
;
1152 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1153 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1155 if (flag_unsafe_math_optimizations
1157 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1161 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1164 return build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1167 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1168 optimizing for space. Don't do this optimization if we don't have
1169 a hardware sqrt insn. */
1170 real_from_integer (&dconst3_4
, VOIDmode
, 3, 0, 0);
1171 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1173 if (flag_unsafe_math_optimizations
1175 && optimize_function_for_speed_p (cfun
)
1176 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1180 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1183 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1185 /* sqrt(x) * sqrt(sqrt(x)) */
1186 return build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1187 sqrt_arg0
, sqrt_sqrt
);
1190 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1191 optimizations since 1./3. is not exactly representable. If x
1192 is negative and finite, the correct value of pow(x,1./3.) is
1193 a NaN with the "invalid" exception raised, because the value
1194 of 1./3. actually has an even denominator. The correct value
1195 of cbrt(x) is a negative real value. */
1196 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1197 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1199 if (flag_unsafe_math_optimizations
1201 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1202 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1203 return build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1205 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1206 if we don't have a hardware sqrt insn. */
1207 dconst1_6
= dconst1_3
;
1208 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1210 if (flag_unsafe_math_optimizations
1213 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1214 && optimize_function_for_speed_p (cfun
)
1216 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1219 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1222 return build_and_insert_call (gsi
, loc
, cbrtfn
, sqrt_arg0
);
1225 /* Optimize pow(x,c), where n = 2c for some nonzero integer n
1226 and c not an integer, into
1228 sqrt(x) * powi(x, n/2), n > 0;
1229 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1231 Do not calculate the powi factor when n/2 = 0. */
1232 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1233 n
= real_to_integer (&c2
);
1234 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1235 c2_is_int
= real_identical (&c2
, &cint
);
1237 if (flag_unsafe_math_optimizations
1241 && optimize_function_for_speed_p (cfun
))
1243 tree powi_x_ndiv2
= NULL_TREE
;
1245 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1246 possible or profitable, give up. Skip the degenerate case when
1247 n is 1 or -1, where the result is always 1. */
1248 if (absu_hwi (n
) != 1)
1250 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1256 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1257 result of the optimal multiply sequence just calculated. */
1258 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1260 if (absu_hwi (n
) == 1)
1263 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1264 sqrt_arg0
, powi_x_ndiv2
);
1266 /* If n is negative, reciprocate the result. */
1268 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1269 build_real (type
, dconst1
), result
);
1273 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1275 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1276 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1278 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1279 different from pow(x, 1./3.) due to rounding and behavior with
1280 negative x, we need to constrain this transformation to unsafe
1281 math and positive x or finite math. */
1282 real_from_integer (&dconst3
, VOIDmode
, 3, 0, 0);
1283 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1284 real_round (&c2
, mode
, &c2
);
1285 n
= real_to_integer (&c2
);
1286 real_from_integer (&cint
, VOIDmode
, n
, n
< 0 ? -1 : 0, 0);
1287 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1288 real_convert (&c2
, mode
, &c2
);
1290 if (flag_unsafe_math_optimizations
1292 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1293 && real_identical (&c2
, &c
)
1295 && optimize_function_for_speed_p (cfun
)
1296 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1298 tree powi_x_ndiv3
= NULL_TREE
;
1300 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1301 possible or profitable, give up. Skip the degenerate case when
1302 abs(n) < 3, where the result is always 1. */
1303 if (absu_hwi (n
) >= 3)
1305 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1311 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1312 as that creates an unnecessary variable. Instead, just produce
1313 either cbrt(x) or cbrt(x) * cbrt(x). */
1314 cbrt_x
= build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1316 if (absu_hwi (n
) % 3 == 1)
1317 powi_cbrt_x
= cbrt_x
;
1319 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1322 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1323 if (absu_hwi (n
) < 3)
1324 result
= powi_cbrt_x
;
1326 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1327 powi_x_ndiv3
, powi_cbrt_x
);
1329 /* If n is negative, reciprocate the result. */
1331 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1332 build_real (type
, dconst1
), result
);
1337 /* No optimizations succeeded. */
1341 /* ARG is the argument to a cabs builtin call in GSI with location info
1342 LOC. Create a sequence of statements prior to GSI that calculates
1343 sqrt(R*R + I*I), where R and I are the real and imaginary components
1344 of ARG, respectively. Return an expression holding the result. */
1347 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1349 tree real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1350 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1351 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1352 enum machine_mode mode
= TYPE_MODE (type
);
1354 if (!flag_unsafe_math_optimizations
1355 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1357 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1360 real_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1361 REALPART_EXPR
, arg
);
1362 addend1
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1363 real_part
, real_part
);
1364 imag_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1365 IMAGPART_EXPR
, arg
);
1366 addend2
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1367 imag_part
, imag_part
);
1368 sum
= build_and_insert_binop (gsi
, loc
, "cabs", PLUS_EXPR
, addend1
, addend2
);
1369 result
= build_and_insert_call (gsi
, loc
, 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
;
1390 bool cleanup_eh
= false;
1392 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1394 gimple stmt
= gsi_stmt (gsi
);
1397 /* Only the last stmt in a bb could throw, no need to call
1398 gimple_purge_dead_eh_edges if we change something in the middle
1399 of a basic block. */
1402 if (is_gimple_call (stmt
)
1403 && gimple_call_lhs (stmt
)
1404 && (fndecl
= gimple_call_fndecl (stmt
))
1405 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1407 tree arg
, arg0
, arg1
, result
;
1411 switch (DECL_FUNCTION_CODE (fndecl
))
1413 CASE_FLT_FN (BUILT_IN_COS
):
1414 CASE_FLT_FN (BUILT_IN_SIN
):
1415 CASE_FLT_FN (BUILT_IN_CEXPI
):
1416 /* Make sure we have either sincos or cexp. */
1417 if (!TARGET_HAS_SINCOS
&& !TARGET_C99_FUNCTIONS
)
1420 arg
= gimple_call_arg (stmt
, 0);
1421 if (TREE_CODE (arg
) == SSA_NAME
)
1422 cfg_changed
|= execute_cse_sincos_1 (arg
);
1425 CASE_FLT_FN (BUILT_IN_POW
):
1426 arg0
= gimple_call_arg (stmt
, 0);
1427 arg1
= gimple_call_arg (stmt
, 1);
1429 loc
= gimple_location (stmt
);
1430 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1434 tree lhs
= gimple_get_lhs (stmt
);
1435 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1436 gimple_set_location (new_stmt
, loc
);
1437 unlink_stmt_vdef (stmt
);
1438 gsi_replace (&gsi
, new_stmt
, true);
1440 if (gimple_vdef (stmt
))
1441 release_ssa_name (gimple_vdef (stmt
));
1445 CASE_FLT_FN (BUILT_IN_POWI
):
1446 arg0
= gimple_call_arg (stmt
, 0);
1447 arg1
= gimple_call_arg (stmt
, 1);
1448 loc
= gimple_location (stmt
);
1450 if (!host_integerp (arg1
, 0))
1453 if (real_minus_onep (arg0
))
1455 tree t0
, t1
, cond
, one
, minus_one
;
1458 t0
= TREE_TYPE (arg0
);
1459 t1
= TREE_TYPE (arg1
);
1460 one
= build_real (t0
, dconst1
);
1461 minus_one
= build_real (t0
, dconstm1
);
1463 cond
= make_temp_ssa_name (t1
, NULL
, "powi_cond");
1464 stmt
= gimple_build_assign_with_ops (BIT_AND_EXPR
, cond
,
1468 gimple_set_location (stmt
, loc
);
1469 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1471 result
= make_temp_ssa_name (t0
, NULL
, "powi");
1472 stmt
= gimple_build_assign_with_ops (COND_EXPR
, result
,
1475 gimple_set_location (stmt
, loc
);
1476 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1480 n
= TREE_INT_CST_LOW (arg1
);
1481 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1486 tree lhs
= gimple_get_lhs (stmt
);
1487 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1488 gimple_set_location (new_stmt
, loc
);
1489 unlink_stmt_vdef (stmt
);
1490 gsi_replace (&gsi
, new_stmt
, true);
1492 if (gimple_vdef (stmt
))
1493 release_ssa_name (gimple_vdef (stmt
));
1497 CASE_FLT_FN (BUILT_IN_CABS
):
1498 arg0
= gimple_call_arg (stmt
, 0);
1499 loc
= gimple_location (stmt
);
1500 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1504 tree lhs
= gimple_get_lhs (stmt
);
1505 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1506 gimple_set_location (new_stmt
, loc
);
1507 unlink_stmt_vdef (stmt
);
1508 gsi_replace (&gsi
, new_stmt
, true);
1510 if (gimple_vdef (stmt
))
1511 release_ssa_name (gimple_vdef (stmt
));
1520 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
1523 statistics_counter_event (cfun
, "sincos statements inserted",
1524 sincos_stats
.inserted
);
1526 free_dominance_info (CDI_DOMINATORS
);
1527 return cfg_changed
? TODO_cleanup_cfg
: 0;
1531 gate_cse_sincos (void)
1533 /* We no longer require either sincos or cexp, since powi expansion
1534 piggybacks on this pass. */
1538 struct gimple_opt_pass pass_cse_sincos
=
1542 "sincos", /* name */
1543 OPTGROUP_NONE
, /* optinfo_flags */
1544 gate_cse_sincos
, /* gate */
1545 execute_cse_sincos
, /* execute */
1548 0, /* static_pass_number */
1549 TV_NONE
, /* tv_id */
1550 PROP_ssa
, /* properties_required */
1551 0, /* properties_provided */
1552 0, /* properties_destroyed */
1553 0, /* todo_flags_start */
1554 TODO_update_ssa
| TODO_verify_ssa
1555 | TODO_verify_stmts
/* todo_flags_finish */
1559 /* A symbolic number is used to detect byte permutation and selection
1560 patterns. Therefore the field N contains an artificial number
1561 consisting of byte size markers:
1563 0 - byte has the value 0
1564 1..size - byte contains the content of the byte
1565 number indexed with that value minus one */
1567 struct symbolic_number
{
1568 unsigned HOST_WIDEST_INT n
;
1572 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1573 number N. Return false if the requested operation is not permitted
1574 on a symbolic number. */
1577 do_shift_rotate (enum tree_code code
,
1578 struct symbolic_number
*n
,
1584 /* Zero out the extra bits of N in order to avoid them being shifted
1585 into the significant bits. */
1586 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1587 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1598 n
->n
= (n
->n
<< count
) | (n
->n
>> ((n
->size
* BITS_PER_UNIT
) - count
));
1601 n
->n
= (n
->n
>> count
) | (n
->n
<< ((n
->size
* BITS_PER_UNIT
) - count
));
1606 /* Zero unused bits for size. */
1607 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1608 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1612 /* Perform sanity checking for the symbolic number N and the gimple
1616 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1620 lhs_type
= gimple_expr_type (stmt
);
1622 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1625 if (TYPE_PRECISION (lhs_type
) != n
->size
* BITS_PER_UNIT
)
1631 /* find_bswap_1 invokes itself recursively with N and tries to perform
1632 the operation given by the rhs of STMT on the result. If the
1633 operation could successfully be executed the function returns the
1634 tree expression of the source operand and NULL otherwise. */
1637 find_bswap_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1639 enum tree_code code
;
1640 tree rhs1
, rhs2
= NULL
;
1641 gimple rhs1_stmt
, rhs2_stmt
;
1643 enum gimple_rhs_class rhs_class
;
1645 if (!limit
|| !is_gimple_assign (stmt
))
1648 rhs1
= gimple_assign_rhs1 (stmt
);
1650 if (TREE_CODE (rhs1
) != SSA_NAME
)
1653 code
= gimple_assign_rhs_code (stmt
);
1654 rhs_class
= gimple_assign_rhs_class (stmt
);
1655 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1657 if (rhs_class
== GIMPLE_BINARY_RHS
)
1658 rhs2
= gimple_assign_rhs2 (stmt
);
1660 /* Handle unary rhs and binary rhs with integer constants as second
1663 if (rhs_class
== GIMPLE_UNARY_RHS
1664 || (rhs_class
== GIMPLE_BINARY_RHS
1665 && TREE_CODE (rhs2
) == INTEGER_CST
))
1667 if (code
!= BIT_AND_EXPR
1668 && code
!= LSHIFT_EXPR
1669 && code
!= RSHIFT_EXPR
1670 && code
!= LROTATE_EXPR
1671 && code
!= RROTATE_EXPR
1673 && code
!= CONVERT_EXPR
)
1676 source_expr1
= find_bswap_1 (rhs1_stmt
, n
, limit
- 1);
1678 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
1679 to initialize the symbolic number. */
1682 /* Set up the symbolic number N by setting each byte to a
1683 value between 1 and the byte size of rhs1. The highest
1684 order byte is set to n->size and the lowest order
1686 n
->size
= TYPE_PRECISION (TREE_TYPE (rhs1
));
1687 if (n
->size
% BITS_PER_UNIT
!= 0)
1689 n
->size
/= BITS_PER_UNIT
;
1690 n
->n
= (sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1691 (unsigned HOST_WIDEST_INT
)0x08070605 << 32 | 0x04030201);
1693 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1694 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 <<
1695 (n
->size
* BITS_PER_UNIT
)) - 1;
1697 source_expr1
= rhs1
;
1705 unsigned HOST_WIDEST_INT val
= widest_int_cst_value (rhs2
);
1706 unsigned HOST_WIDEST_INT tmp
= val
;
1708 /* Only constants masking full bytes are allowed. */
1709 for (i
= 0; i
< n
->size
; i
++, tmp
>>= BITS_PER_UNIT
)
1710 if ((tmp
& 0xff) != 0 && (tmp
& 0xff) != 0xff)
1720 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1727 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1728 if (type_size
% BITS_PER_UNIT
!= 0)
1731 if (type_size
/ BITS_PER_UNIT
< (int)(sizeof (HOST_WIDEST_INT
)))
1733 /* If STMT casts to a smaller type mask out the bits not
1734 belonging to the target type. */
1735 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << type_size
) - 1;
1737 n
->size
= type_size
/ BITS_PER_UNIT
;
1743 return verify_symbolic_number_p (n
, stmt
) ? source_expr1
: NULL
;
1746 /* Handle binary rhs. */
1748 if (rhs_class
== GIMPLE_BINARY_RHS
)
1750 struct symbolic_number n1
, n2
;
1753 if (code
!= BIT_IOR_EXPR
)
1756 if (TREE_CODE (rhs2
) != SSA_NAME
)
1759 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1764 source_expr1
= find_bswap_1 (rhs1_stmt
, &n1
, limit
- 1);
1769 source_expr2
= find_bswap_1 (rhs2_stmt
, &n2
, limit
- 1);
1771 if (source_expr1
!= source_expr2
1772 || n1
.size
!= n2
.size
)
1778 if (!verify_symbolic_number_p (n
, stmt
))
1785 return source_expr1
;
1790 /* Check if STMT completes a bswap implementation consisting of ORs,
1791 SHIFTs and ANDs. Return the source tree expression on which the
1792 byte swap is performed and NULL if no bswap was found. */
1795 find_bswap (gimple stmt
)
1797 /* The number which the find_bswap result should match in order to
1798 have a full byte swap. The number is shifted to the left according
1799 to the size of the symbolic number before using it. */
1800 unsigned HOST_WIDEST_INT cmp
=
1801 sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1802 (unsigned HOST_WIDEST_INT
)0x01020304 << 32 | 0x05060708;
1804 struct symbolic_number n
;
1808 /* The last parameter determines the depth search limit. It usually
1809 correlates directly to the number of bytes to be touched. We
1810 increase that number by three here in order to also
1811 cover signed -> unsigned converions of the src operand as can be seen
1812 in libgcc, and for initial shift/and operation of the src operand. */
1813 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
1814 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
1815 source_expr
= find_bswap_1 (stmt
, &n
, limit
);
1820 /* Zero out the extra bits of N and CMP. */
1821 if (n
.size
< (int)sizeof (HOST_WIDEST_INT
))
1823 unsigned HOST_WIDEST_INT mask
=
1824 ((unsigned HOST_WIDEST_INT
)1 << (n
.size
* BITS_PER_UNIT
)) - 1;
1827 cmp
>>= (sizeof (HOST_WIDEST_INT
) - n
.size
) * BITS_PER_UNIT
;
1830 /* A complete byte swap should make the symbolic number to start
1831 with the largest digit in the highest order byte. */
1838 /* Find manual byte swap implementations and turn them into a bswap
1839 builtin invokation. */
1842 execute_optimize_bswap (void)
1845 bool bswap16_p
, bswap32_p
, bswap64_p
;
1846 bool changed
= false;
1847 tree bswap16_type
= NULL_TREE
, bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
1849 if (BITS_PER_UNIT
!= 8)
1852 if (sizeof (HOST_WIDEST_INT
) < 8)
1855 bswap16_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP16
)
1856 && optab_handler (bswap_optab
, HImode
) != CODE_FOR_nothing
);
1857 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
1858 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
1859 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
1860 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
1861 || (bswap32_p
&& word_mode
== SImode
)));
1863 if (!bswap16_p
&& !bswap32_p
&& !bswap64_p
)
1866 /* Determine the argument type of the builtins. The code later on
1867 assumes that the return and argument type are the same. */
1870 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
1871 bswap16_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1876 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1877 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1882 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1883 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1886 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
1890 gimple_stmt_iterator gsi
;
1892 /* We do a reverse scan for bswap patterns to make sure we get the
1893 widest match. As bswap pattern matching doesn't handle
1894 previously inserted smaller bswap replacements as sub-
1895 patterns, the wider variant wouldn't be detected. */
1896 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
1898 gimple stmt
= gsi_stmt (gsi
);
1899 tree bswap_src
, bswap_type
;
1901 tree fndecl
= NULL_TREE
;
1905 if (!is_gimple_assign (stmt
)
1906 || gimple_assign_rhs_code (stmt
) != BIT_IOR_EXPR
)
1909 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1916 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
1917 bswap_type
= bswap16_type
;
1923 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
1924 bswap_type
= bswap32_type
;
1930 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
1931 bswap_type
= bswap64_type
;
1941 bswap_src
= find_bswap (stmt
);
1947 if (type_size
== 16)
1948 bswap_stats
.found_16bit
++;
1949 else if (type_size
== 32)
1950 bswap_stats
.found_32bit
++;
1952 bswap_stats
.found_64bit
++;
1954 bswap_tmp
= bswap_src
;
1956 /* Convert the src expression if necessary. */
1957 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1959 gimple convert_stmt
;
1960 bswap_tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
1961 convert_stmt
= gimple_build_assign_with_ops
1962 (NOP_EXPR
, bswap_tmp
, bswap_src
, NULL
);
1963 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1966 call
= gimple_build_call (fndecl
, 1, bswap_tmp
);
1968 bswap_tmp
= gimple_assign_lhs (stmt
);
1970 /* Convert the result if necessary. */
1971 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1973 gimple convert_stmt
;
1974 bswap_tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapdst");
1975 convert_stmt
= gimple_build_assign_with_ops
1976 (NOP_EXPR
, gimple_assign_lhs (stmt
), bswap_tmp
, NULL
);
1977 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1980 gimple_call_set_lhs (call
, bswap_tmp
);
1984 fprintf (dump_file
, "%d bit bswap implementation found at: ",
1986 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1989 gsi_insert_after (&gsi
, call
, GSI_SAME_STMT
);
1990 gsi_remove (&gsi
, true);
1994 statistics_counter_event (cfun
, "16-bit bswap implementations found",
1995 bswap_stats
.found_16bit
);
1996 statistics_counter_event (cfun
, "32-bit bswap implementations found",
1997 bswap_stats
.found_32bit
);
1998 statistics_counter_event (cfun
, "64-bit bswap implementations found",
1999 bswap_stats
.found_64bit
);
2001 return (changed
? TODO_update_ssa
| TODO_verify_ssa
2002 | TODO_verify_stmts
: 0);
2006 gate_optimize_bswap (void)
2008 return flag_expensive_optimizations
&& optimize
;
2011 struct gimple_opt_pass pass_optimize_bswap
=
2016 OPTGROUP_NONE
, /* optinfo_flags */
2017 gate_optimize_bswap
, /* gate */
2018 execute_optimize_bswap
, /* execute */
2021 0, /* static_pass_number */
2022 TV_NONE
, /* tv_id */
2023 PROP_ssa
, /* properties_required */
2024 0, /* properties_provided */
2025 0, /* properties_destroyed */
2026 0, /* todo_flags_start */
2027 0 /* todo_flags_finish */
2031 /* Return true if stmt is a type conversion operation that can be stripped
2032 when used in a widening multiply operation. */
2034 widening_mult_conversion_strippable_p (tree result_type
, gimple stmt
)
2036 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2038 if (TREE_CODE (result_type
) == INTEGER_TYPE
)
2043 if (!CONVERT_EXPR_CODE_P (rhs_code
))
2046 op_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2048 /* If the type of OP has the same precision as the result, then
2049 we can strip this conversion. The multiply operation will be
2050 selected to create the correct extension as a by-product. */
2051 if (TYPE_PRECISION (result_type
) == TYPE_PRECISION (op_type
))
2054 /* We can also strip a conversion if it preserves the signed-ness of
2055 the operation and doesn't narrow the range. */
2056 inner_op_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
2058 /* If the inner-most type is unsigned, then we can strip any
2059 intermediate widening operation. If it's signed, then the
2060 intermediate widening operation must also be signed. */
2061 if ((TYPE_UNSIGNED (inner_op_type
)
2062 || TYPE_UNSIGNED (op_type
) == TYPE_UNSIGNED (inner_op_type
))
2063 && TYPE_PRECISION (op_type
) > TYPE_PRECISION (inner_op_type
))
2069 return rhs_code
== FIXED_CONVERT_EXPR
;
2072 /* Return true if RHS is a suitable operand for a widening multiplication,
2073 assuming a target type of TYPE.
2074 There are two cases:
2076 - RHS makes some value at least twice as wide. Store that value
2077 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
2079 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
2080 but leave *TYPE_OUT untouched. */
2083 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
2089 if (TREE_CODE (rhs
) == SSA_NAME
)
2091 stmt
= SSA_NAME_DEF_STMT (rhs
);
2092 if (is_gimple_assign (stmt
))
2094 if (! widening_mult_conversion_strippable_p (type
, stmt
))
2098 rhs1
= gimple_assign_rhs1 (stmt
);
2100 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2102 *new_rhs_out
= rhs1
;
2111 type1
= TREE_TYPE (rhs1
);
2113 if (TREE_CODE (type1
) != TREE_CODE (type
)
2114 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2117 *new_rhs_out
= rhs1
;
2122 if (TREE_CODE (rhs
) == INTEGER_CST
)
2132 /* Return true if STMT performs a widening multiplication, assuming the
2133 output type is TYPE. If so, store the unwidened types of the operands
2134 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2135 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2136 and *TYPE2_OUT would give the operands of the multiplication. */
2139 is_widening_mult_p (gimple stmt
,
2140 tree
*type1_out
, tree
*rhs1_out
,
2141 tree
*type2_out
, tree
*rhs2_out
)
2143 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2145 if (TREE_CODE (type
) != INTEGER_TYPE
2146 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2149 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2153 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2157 if (*type1_out
== NULL
)
2159 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2161 *type1_out
= *type2_out
;
2164 if (*type2_out
== NULL
)
2166 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2168 *type2_out
= *type1_out
;
2171 /* Ensure that the larger of the two operands comes first. */
2172 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
2176 *type1_out
= *type2_out
;
2179 *rhs1_out
= *rhs2_out
;
2186 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2187 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2188 value is true iff we converted the statement. */
2191 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
2193 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
2194 enum insn_code handler
;
2195 enum machine_mode to_mode
, from_mode
, actual_mode
;
2197 int actual_precision
;
2198 location_t loc
= gimple_location (stmt
);
2199 bool from_unsigned1
, from_unsigned2
;
2201 lhs
= gimple_assign_lhs (stmt
);
2202 type
= TREE_TYPE (lhs
);
2203 if (TREE_CODE (type
) != INTEGER_TYPE
)
2206 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2209 to_mode
= TYPE_MODE (type
);
2210 from_mode
= TYPE_MODE (type1
);
2211 from_unsigned1
= TYPE_UNSIGNED (type1
);
2212 from_unsigned2
= TYPE_UNSIGNED (type2
);
2214 if (from_unsigned1
&& from_unsigned2
)
2215 op
= umul_widen_optab
;
2216 else if (!from_unsigned1
&& !from_unsigned2
)
2217 op
= smul_widen_optab
;
2219 op
= usmul_widen_optab
;
2221 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
2224 if (handler
== CODE_FOR_nothing
)
2226 if (op
!= smul_widen_optab
)
2228 /* We can use a signed multiply with unsigned types as long as
2229 there is a wider mode to use, or it is the smaller of the two
2230 types that is unsigned. Note that type1 >= type2, always. */
2231 if ((TYPE_UNSIGNED (type1
)
2232 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2233 || (TYPE_UNSIGNED (type2
)
2234 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2236 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2237 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
2241 op
= smul_widen_optab
;
2242 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
2246 if (handler
== CODE_FOR_nothing
)
2249 from_unsigned1
= from_unsigned2
= false;
2255 /* Ensure that the inputs to the handler are in the correct precison
2256 for the opcode. This will be the full mode size. */
2257 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2258 if (2 * actual_precision
> TYPE_PRECISION (type
))
2260 if (actual_precision
!= TYPE_PRECISION (type1
)
2261 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2262 rhs1
= build_and_insert_cast (gsi
, loc
,
2263 build_nonstandard_integer_type
2264 (actual_precision
, from_unsigned1
), rhs1
);
2265 if (actual_precision
!= TYPE_PRECISION (type2
)
2266 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2267 rhs2
= build_and_insert_cast (gsi
, loc
,
2268 build_nonstandard_integer_type
2269 (actual_precision
, from_unsigned2
), rhs2
);
2271 /* Handle constants. */
2272 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2273 rhs1
= fold_convert (type1
, rhs1
);
2274 if (TREE_CODE (rhs2
) == INTEGER_CST
)
2275 rhs2
= fold_convert (type2
, rhs2
);
2277 gimple_assign_set_rhs1 (stmt
, rhs1
);
2278 gimple_assign_set_rhs2 (stmt
, rhs2
);
2279 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2281 widen_mul_stats
.widen_mults_inserted
++;
2285 /* Process a single gimple statement STMT, which is found at the
2286 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2287 rhs (given by CODE), and try to convert it into a
2288 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2289 is true iff we converted the statement. */
2292 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2293 enum tree_code code
)
2295 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2296 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
2297 tree type
, type1
, type2
, optype
;
2298 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2299 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2301 enum tree_code wmult_code
;
2302 enum insn_code handler
;
2303 enum machine_mode to_mode
, from_mode
, actual_mode
;
2304 location_t loc
= gimple_location (stmt
);
2305 int actual_precision
;
2306 bool from_unsigned1
, from_unsigned2
;
2308 lhs
= gimple_assign_lhs (stmt
);
2309 type
= TREE_TYPE (lhs
);
2310 if (TREE_CODE (type
) != INTEGER_TYPE
2311 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2314 if (code
== MINUS_EXPR
)
2315 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2317 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2319 rhs1
= gimple_assign_rhs1 (stmt
);
2320 rhs2
= gimple_assign_rhs2 (stmt
);
2322 if (TREE_CODE (rhs1
) == SSA_NAME
)
2324 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2325 if (is_gimple_assign (rhs1_stmt
))
2326 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2329 if (TREE_CODE (rhs2
) == SSA_NAME
)
2331 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2332 if (is_gimple_assign (rhs2_stmt
))
2333 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2336 /* Allow for one conversion statement between the multiply
2337 and addition/subtraction statement. If there are more than
2338 one conversions then we assume they would invalidate this
2339 transformation. If that's not the case then they should have
2340 been folded before now. */
2341 if (CONVERT_EXPR_CODE_P (rhs1_code
))
2343 conv1_stmt
= rhs1_stmt
;
2344 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2345 if (TREE_CODE (rhs1
) == SSA_NAME
)
2347 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2348 if (is_gimple_assign (rhs1_stmt
))
2349 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2354 if (CONVERT_EXPR_CODE_P (rhs2_code
))
2356 conv2_stmt
= rhs2_stmt
;
2357 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
2358 if (TREE_CODE (rhs2
) == SSA_NAME
)
2360 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2361 if (is_gimple_assign (rhs2_stmt
))
2362 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2368 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
2369 is_widening_mult_p, but we still need the rhs returns.
2371 It might also appear that it would be sufficient to use the existing
2372 operands of the widening multiply, but that would limit the choice of
2373 multiply-and-accumulate instructions. */
2374 if (code
== PLUS_EXPR
2375 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
2377 if (!is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2378 &type2
, &mult_rhs2
))
2381 conv_stmt
= conv1_stmt
;
2383 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
2385 if (!is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2386 &type2
, &mult_rhs2
))
2389 conv_stmt
= conv2_stmt
;
2394 to_mode
= TYPE_MODE (type
);
2395 from_mode
= TYPE_MODE (type1
);
2396 from_unsigned1
= TYPE_UNSIGNED (type1
);
2397 from_unsigned2
= TYPE_UNSIGNED (type2
);
2400 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
2401 if (from_unsigned1
!= from_unsigned2
)
2403 if (!INTEGRAL_TYPE_P (type
))
2405 /* We can use a signed multiply with unsigned types as long as
2406 there is a wider mode to use, or it is the smaller of the two
2407 types that is unsigned. Note that type1 >= type2, always. */
2409 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2411 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2413 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2414 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
2418 from_unsigned1
= from_unsigned2
= false;
2419 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
2423 /* If there was a conversion between the multiply and addition
2424 then we need to make sure it fits a multiply-and-accumulate.
2425 The should be a single mode change which does not change the
2429 /* We use the original, unmodified data types for this. */
2430 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
2431 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
2432 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
2433 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
2435 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
2437 /* Conversion is a truncate. */
2438 if (TYPE_PRECISION (to_type
) < data_size
)
2441 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
2443 /* Conversion is an extend. Check it's the right sort. */
2444 if (TYPE_UNSIGNED (from_type
) != is_unsigned
2445 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
2448 /* else convert is a no-op for our purposes. */
2451 /* Verify that the machine can perform a widening multiply
2452 accumulate in this mode/signedness combination, otherwise
2453 this transformation is likely to pessimize code. */
2454 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
2455 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
2456 from_mode
, 0, &actual_mode
);
2458 if (handler
== CODE_FOR_nothing
)
2461 /* Ensure that the inputs to the handler are in the correct precison
2462 for the opcode. This will be the full mode size. */
2463 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2464 if (actual_precision
!= TYPE_PRECISION (type1
)
2465 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2466 mult_rhs1
= build_and_insert_cast (gsi
, loc
,
2467 build_nonstandard_integer_type
2468 (actual_precision
, from_unsigned1
),
2470 if (actual_precision
!= TYPE_PRECISION (type2
)
2471 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2472 mult_rhs2
= build_and_insert_cast (gsi
, loc
,
2473 build_nonstandard_integer_type
2474 (actual_precision
, from_unsigned2
),
2477 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
2478 add_rhs
= build_and_insert_cast (gsi
, loc
, type
, add_rhs
);
2480 /* Handle constants. */
2481 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
2482 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
2483 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
2484 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
2486 gimple_assign_set_rhs_with_ops_1 (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
2488 update_stmt (gsi_stmt (*gsi
));
2489 widen_mul_stats
.maccs_inserted
++;
2493 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2494 with uses in additions and subtractions to form fused multiply-add
2495 operations. Returns true if successful and MUL_STMT should be removed. */
2498 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2500 tree mul_result
= gimple_get_lhs (mul_stmt
);
2501 tree type
= TREE_TYPE (mul_result
);
2502 gimple use_stmt
, neguse_stmt
, fma_stmt
;
2503 use_operand_p use_p
;
2504 imm_use_iterator imm_iter
;
2506 if (FLOAT_TYPE_P (type
)
2507 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2510 /* We don't want to do bitfield reduction ops. */
2511 if (INTEGRAL_TYPE_P (type
)
2512 && (TYPE_PRECISION (type
)
2513 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2516 /* If the target doesn't support it, don't generate it. We assume that
2517 if fma isn't available then fms, fnma or fnms are not either. */
2518 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2521 /* If the multiplication has zero uses, it is kept around probably because
2522 of -fnon-call-exceptions. Don't optimize it away in that case,
2524 if (has_zero_uses (mul_result
))
2527 /* Make sure that the multiplication statement becomes dead after
2528 the transformation, thus that all uses are transformed to FMAs.
2529 This means we assume that an FMA operation has the same cost
2531 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
2533 enum tree_code use_code
;
2534 tree result
= mul_result
;
2535 bool negate_p
= false;
2537 use_stmt
= USE_STMT (use_p
);
2539 if (is_gimple_debug (use_stmt
))
2542 /* For now restrict this operations to single basic blocks. In theory
2543 we would want to support sinking the multiplication in
2549 to form a fma in the then block and sink the multiplication to the
2551 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2554 if (!is_gimple_assign (use_stmt
))
2557 use_code
= gimple_assign_rhs_code (use_stmt
);
2559 /* A negate on the multiplication leads to FNMA. */
2560 if (use_code
== NEGATE_EXPR
)
2565 result
= gimple_assign_lhs (use_stmt
);
2567 /* Make sure the negate statement becomes dead with this
2568 single transformation. */
2569 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
2570 &use_p
, &neguse_stmt
))
2573 /* Make sure the multiplication isn't also used on that stmt. */
2574 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
2575 if (USE_FROM_PTR (usep
) == mul_result
)
2579 use_stmt
= neguse_stmt
;
2580 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2582 if (!is_gimple_assign (use_stmt
))
2585 use_code
= gimple_assign_rhs_code (use_stmt
);
2592 if (gimple_assign_rhs2 (use_stmt
) == result
)
2593 negate_p
= !negate_p
;
2598 /* FMA can only be formed from PLUS and MINUS. */
2602 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
2603 by a MULT_EXPR that we'll visit later, we might be able to
2604 get a more profitable match with fnma.
2605 OTOH, if we don't, a negate / fma pair has likely lower latency
2606 that a mult / subtract pair. */
2607 if (use_code
== MINUS_EXPR
&& !negate_p
2608 && gimple_assign_rhs1 (use_stmt
) == result
2609 && optab_handler (fms_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
2610 && optab_handler (fnma_optab
, TYPE_MODE (type
)) != CODE_FOR_nothing
)
2612 tree rhs2
= gimple_assign_rhs2 (use_stmt
);
2614 if (TREE_CODE (rhs2
) == SSA_NAME
)
2616 gimple stmt2
= SSA_NAME_DEF_STMT (rhs2
);
2617 if (has_single_use (rhs2
)
2618 && is_gimple_assign (stmt2
)
2619 && gimple_assign_rhs_code (stmt2
) == MULT_EXPR
)
2624 /* We can't handle a * b + a * b. */
2625 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
2628 /* While it is possible to validate whether or not the exact form
2629 that we've recognized is available in the backend, the assumption
2630 is that the transformation is never a loss. For instance, suppose
2631 the target only has the plain FMA pattern available. Consider
2632 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
2633 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
2634 still have 3 operations, but in the FMA form the two NEGs are
2635 independent and could be run in parallel. */
2638 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
2640 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
2641 enum tree_code use_code
;
2642 tree addop
, mulop1
= op1
, result
= mul_result
;
2643 bool negate_p
= false;
2645 if (is_gimple_debug (use_stmt
))
2648 use_code
= gimple_assign_rhs_code (use_stmt
);
2649 if (use_code
== NEGATE_EXPR
)
2651 result
= gimple_assign_lhs (use_stmt
);
2652 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
2653 gsi_remove (&gsi
, true);
2654 release_defs (use_stmt
);
2656 use_stmt
= neguse_stmt
;
2657 gsi
= gsi_for_stmt (use_stmt
);
2658 use_code
= gimple_assign_rhs_code (use_stmt
);
2662 if (gimple_assign_rhs1 (use_stmt
) == result
)
2664 addop
= gimple_assign_rhs2 (use_stmt
);
2665 /* a * b - c -> a * b + (-c) */
2666 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2667 addop
= force_gimple_operand_gsi (&gsi
,
2668 build1 (NEGATE_EXPR
,
2670 true, NULL_TREE
, true,
2675 addop
= gimple_assign_rhs1 (use_stmt
);
2676 /* a - b * c -> (-b) * c + a */
2677 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
2678 negate_p
= !negate_p
;
2682 mulop1
= force_gimple_operand_gsi (&gsi
,
2683 build1 (NEGATE_EXPR
,
2685 true, NULL_TREE
, true,
2688 fma_stmt
= gimple_build_assign_with_ops (FMA_EXPR
,
2689 gimple_assign_lhs (use_stmt
),
2692 gsi_replace (&gsi
, fma_stmt
, true);
2693 widen_mul_stats
.fmas_inserted
++;
2699 /* Find integer multiplications where the operands are extended from
2700 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
2701 where appropriate. */
2704 execute_optimize_widening_mul (void)
2707 bool cfg_changed
= false;
2709 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
2713 gimple_stmt_iterator gsi
;
2715 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
2717 gimple stmt
= gsi_stmt (gsi
);
2718 enum tree_code code
;
2720 if (is_gimple_assign (stmt
))
2722 code
= gimple_assign_rhs_code (stmt
);
2726 if (!convert_mult_to_widen (stmt
, &gsi
)
2727 && convert_mult_to_fma (stmt
,
2728 gimple_assign_rhs1 (stmt
),
2729 gimple_assign_rhs2 (stmt
)))
2731 gsi_remove (&gsi
, true);
2732 release_defs (stmt
);
2739 convert_plusminus_to_widen (&gsi
, stmt
, code
);
2745 else if (is_gimple_call (stmt
)
2746 && gimple_call_lhs (stmt
))
2748 tree fndecl
= gimple_call_fndecl (stmt
);
2750 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
2752 switch (DECL_FUNCTION_CODE (fndecl
))
2757 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
2758 && REAL_VALUES_EQUAL
2759 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
2761 && convert_mult_to_fma (stmt
,
2762 gimple_call_arg (stmt
, 0),
2763 gimple_call_arg (stmt
, 0)))
2765 unlink_stmt_vdef (stmt
);
2766 if (gsi_remove (&gsi
, true)
2767 && gimple_purge_dead_eh_edges (bb
))
2769 release_defs (stmt
);
2782 statistics_counter_event (cfun
, "widening multiplications inserted",
2783 widen_mul_stats
.widen_mults_inserted
);
2784 statistics_counter_event (cfun
, "widening maccs inserted",
2785 widen_mul_stats
.maccs_inserted
);
2786 statistics_counter_event (cfun
, "fused multiply-adds inserted",
2787 widen_mul_stats
.fmas_inserted
);
2789 return cfg_changed
? TODO_cleanup_cfg
: 0;
2793 gate_optimize_widening_mul (void)
2795 return flag_expensive_optimizations
&& optimize
;
2798 struct gimple_opt_pass pass_optimize_widening_mul
=
2802 "widening_mul", /* name */
2803 OPTGROUP_NONE
, /* optinfo_flags */
2804 gate_optimize_widening_mul
, /* gate */
2805 execute_optimize_widening_mul
, /* execute */
2808 0, /* static_pass_number */
2809 TV_NONE
, /* tv_id */
2810 PROP_ssa
, /* properties_required */
2811 0, /* properties_provided */
2812 0, /* properties_destroyed */
2813 0, /* todo_flags_start */
2816 | TODO_update_ssa
/* todo_flags_finish */