1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005-2015 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"
98 #include "hard-reg-set.h"
100 #include "function.h"
101 #include "dominance.h"
103 #include "basic-block.h"
104 #include "tree-ssa-alias.h"
105 #include "internal-fn.h"
106 #include "gimple-fold.h"
107 #include "gimple-expr.h"
110 #include "gimple-iterator.h"
111 #include "gimplify.h"
112 #include "gimplify-me.h"
113 #include "stor-layout.h"
114 #include "gimple-ssa.h"
115 #include "tree-cfg.h"
116 #include "tree-phinodes.h"
117 #include "ssa-iterators.h"
118 #include "stringpool.h"
119 #include "tree-ssanames.h"
121 #include "tree-dfa.h"
122 #include "tree-ssa.h"
123 #include "tree-pass.h"
124 #include "alloc-pool.h"
126 #include "gimple-pretty-print.h"
127 #include "builtins.h"
129 /* FIXME: RTL headers have to be included here for optabs. */
130 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */
131 #include "expr.h" /* Because optabs.h wants sepops. */
132 #include "insn-codes.h"
135 /* This structure represents one basic block that either computes a
136 division, or is a common dominator for basic block that compute a
139 /* The basic block represented by this structure. */
142 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
146 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
147 was inserted in BB. */
148 gimple recip_def_stmt
;
150 /* Pointer to a list of "struct occurrence"s for blocks dominated
152 struct occurrence
*children
;
154 /* Pointer to the next "struct occurrence"s in the list of blocks
155 sharing a common dominator. */
156 struct occurrence
*next
;
158 /* The number of divisions that are in BB before compute_merit. The
159 number of divisions that are in BB or post-dominate it after
163 /* True if the basic block has a division, false if it is a common
164 dominator for basic blocks that do. If it is false and trapping
165 math is active, BB is not a candidate for inserting a reciprocal. */
166 bool bb_has_division
;
171 /* Number of 1.0/X ops inserted. */
174 /* Number of 1.0/FUNC ops inserted. */
180 /* Number of cexpi calls inserted. */
186 /* Number of hand-written 16-bit nop / bswaps found. */
189 /* Number of hand-written 32-bit nop / bswaps found. */
192 /* Number of hand-written 64-bit nop / bswaps found. */
194 } nop_stats
, bswap_stats
;
198 /* Number of widening multiplication ops inserted. */
199 int widen_mults_inserted
;
201 /* Number of integer multiply-and-accumulate ops inserted. */
204 /* Number of fp fused multiply-add ops inserted. */
208 /* The instance of "struct occurrence" representing the highest
209 interesting block in the dominator tree. */
210 static struct occurrence
*occ_head
;
212 /* Allocation pool for getting instances of "struct occurrence". */
213 static alloc_pool occ_pool
;
217 /* Allocate and return a new struct occurrence for basic block BB, and
218 whose children list is headed by CHILDREN. */
219 static struct occurrence
*
220 occ_new (basic_block bb
, struct occurrence
*children
)
222 struct occurrence
*occ
;
224 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
225 memset (occ
, 0, sizeof (struct occurrence
));
228 occ
->children
= children
;
233 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
234 list of "struct occurrence"s, one per basic block, having IDOM as
235 their common dominator.
237 We try to insert NEW_OCC as deep as possible in the tree, and we also
238 insert any other block that is a common dominator for BB and one
239 block already in the tree. */
242 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
243 struct occurrence
**p_head
)
245 struct occurrence
*occ
, **p_occ
;
247 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
249 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
250 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
253 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
256 occ
->next
= new_occ
->children
;
257 new_occ
->children
= occ
;
259 /* Try the next block (it may as well be dominated by BB). */
262 else if (dom
== occ_bb
)
264 /* OCC_BB dominates BB. Tail recurse to look deeper. */
265 insert_bb (new_occ
, dom
, &occ
->children
);
269 else if (dom
!= idom
)
271 gcc_assert (!dom
->aux
);
273 /* There is a dominator between IDOM and BB, add it and make
274 two children out of NEW_OCC and OCC. First, remove OCC from
280 /* None of the previous blocks has DOM as a dominator: if we tail
281 recursed, we would reexamine them uselessly. Just switch BB with
282 DOM, and go on looking for blocks dominated by DOM. */
283 new_occ
= occ_new (dom
, new_occ
);
288 /* Nothing special, go on with the next element. */
293 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
294 new_occ
->next
= *p_head
;
298 /* Register that we found a division in BB. */
301 register_division_in (basic_block bb
)
303 struct occurrence
*occ
;
305 occ
= (struct occurrence
*) bb
->aux
;
308 occ
= occ_new (bb
, NULL
);
309 insert_bb (occ
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), &occ_head
);
312 occ
->bb_has_division
= true;
313 occ
->num_divisions
++;
317 /* Compute the number of divisions that postdominate each block in OCC and
321 compute_merit (struct occurrence
*occ
)
323 struct occurrence
*occ_child
;
324 basic_block dom
= occ
->bb
;
326 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
329 if (occ_child
->children
)
330 compute_merit (occ_child
);
333 bb
= single_noncomplex_succ (dom
);
337 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
338 occ
->num_divisions
+= occ_child
->num_divisions
;
343 /* Return whether USE_STMT is a floating-point division by DEF. */
345 is_division_by (gimple use_stmt
, tree def
)
347 return is_gimple_assign (use_stmt
)
348 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
349 && gimple_assign_rhs2 (use_stmt
) == def
350 /* Do not recognize x / x as valid division, as we are getting
351 confused later by replacing all immediate uses x in such
353 && gimple_assign_rhs1 (use_stmt
) != def
;
356 /* Walk the subset of the dominator tree rooted at OCC, setting the
357 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
358 the given basic block. The field may be left NULL, of course,
359 if it is not possible or profitable to do the optimization.
361 DEF_BSI is an iterator pointing at the statement defining DEF.
362 If RECIP_DEF is set, a dominator already has a computation that can
366 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
367 tree def
, tree recip_def
, int threshold
)
371 gimple_stmt_iterator gsi
;
372 struct occurrence
*occ_child
;
375 && (occ
->bb_has_division
|| !flag_trapping_math
)
376 && occ
->num_divisions
>= threshold
)
378 /* Make a variable with the replacement and substitute it. */
379 type
= TREE_TYPE (def
);
380 recip_def
= create_tmp_reg (type
, "reciptmp");
381 new_stmt
= gimple_build_assign (recip_def
, RDIV_EXPR
,
382 build_one_cst (type
), def
);
384 if (occ
->bb_has_division
)
386 /* Case 1: insert before an existing division. */
387 gsi
= gsi_after_labels (occ
->bb
);
388 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
391 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
393 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
395 /* Case 2: insert right after the definition. Note that this will
396 never happen if the definition statement can throw, because in
397 that case the sole successor of the statement's basic block will
398 dominate all the uses as well. */
399 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
403 /* Case 3: insert in a basic block not containing defs/uses. */
404 gsi
= gsi_after_labels (occ
->bb
);
405 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
408 reciprocal_stats
.rdivs_inserted
++;
410 occ
->recip_def_stmt
= new_stmt
;
413 occ
->recip_def
= recip_def
;
414 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
415 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
419 /* Replace the division at USE_P with a multiplication by the reciprocal, if
423 replace_reciprocal (use_operand_p use_p
)
425 gimple use_stmt
= USE_STMT (use_p
);
426 basic_block bb
= gimple_bb (use_stmt
);
427 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
429 if (optimize_bb_for_speed_p (bb
)
430 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
432 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
433 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
434 SET_USE (use_p
, occ
->recip_def
);
435 fold_stmt_inplace (&gsi
);
436 update_stmt (use_stmt
);
441 /* Free OCC and return one more "struct occurrence" to be freed. */
443 static struct occurrence
*
444 free_bb (struct occurrence
*occ
)
446 struct occurrence
*child
, *next
;
448 /* First get the two pointers hanging off OCC. */
450 child
= occ
->children
;
452 pool_free (occ_pool
, occ
);
454 /* Now ensure that we don't recurse unless it is necessary. */
460 next
= free_bb (next
);
467 /* Look for floating-point divisions among DEF's uses, and try to
468 replace them by multiplications with the reciprocal. Add
469 as many statements computing the reciprocal as needed.
471 DEF must be a GIMPLE register of a floating-point type. */
474 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
477 imm_use_iterator use_iter
;
478 struct occurrence
*occ
;
479 int count
= 0, threshold
;
481 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
483 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
485 gimple use_stmt
= USE_STMT (use_p
);
486 if (is_division_by (use_stmt
, def
))
488 register_division_in (gimple_bb (use_stmt
));
493 /* Do the expensive part only if we can hope to optimize something. */
494 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
495 if (count
>= threshold
)
498 for (occ
= occ_head
; occ
; occ
= occ
->next
)
501 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
504 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
506 if (is_division_by (use_stmt
, def
))
508 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
509 replace_reciprocal (use_p
);
514 for (occ
= occ_head
; occ
; )
520 /* Go through all the floating-point SSA_NAMEs, and call
521 execute_cse_reciprocals_1 on each of them. */
524 const pass_data pass_data_cse_reciprocals
=
526 GIMPLE_PASS
, /* type */
528 OPTGROUP_NONE
, /* optinfo_flags */
530 PROP_ssa
, /* properties_required */
531 0, /* properties_provided */
532 0, /* properties_destroyed */
533 0, /* todo_flags_start */
534 TODO_update_ssa
, /* todo_flags_finish */
537 class pass_cse_reciprocals
: public gimple_opt_pass
540 pass_cse_reciprocals (gcc::context
*ctxt
)
541 : gimple_opt_pass (pass_data_cse_reciprocals
, ctxt
)
544 /* opt_pass methods: */
545 virtual bool gate (function
*) { return optimize
&& flag_reciprocal_math
; }
546 virtual unsigned int execute (function
*);
548 }; // class pass_cse_reciprocals
551 pass_cse_reciprocals::execute (function
*fun
)
556 occ_pool
= create_alloc_pool ("dominators for recip",
557 sizeof (struct occurrence
),
558 n_basic_blocks_for_fn (fun
) / 3 + 1);
560 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
561 calculate_dominance_info (CDI_DOMINATORS
);
562 calculate_dominance_info (CDI_POST_DOMINATORS
);
564 #ifdef ENABLE_CHECKING
565 FOR_EACH_BB_FN (bb
, fun
)
566 gcc_assert (!bb
->aux
);
569 for (arg
= DECL_ARGUMENTS (fun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
570 if (FLOAT_TYPE_P (TREE_TYPE (arg
))
571 && is_gimple_reg (arg
))
573 tree name
= ssa_default_def (fun
, arg
);
575 execute_cse_reciprocals_1 (NULL
, name
);
578 FOR_EACH_BB_FN (bb
, fun
)
582 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
585 gphi
*phi
= gsi
.phi ();
586 def
= PHI_RESULT (phi
);
587 if (! virtual_operand_p (def
)
588 && FLOAT_TYPE_P (TREE_TYPE (def
)))
589 execute_cse_reciprocals_1 (NULL
, def
);
592 for (gimple_stmt_iterator gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);
595 gimple stmt
= gsi_stmt (gsi
);
597 if (gimple_has_lhs (stmt
)
598 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
599 && FLOAT_TYPE_P (TREE_TYPE (def
))
600 && TREE_CODE (def
) == SSA_NAME
)
601 execute_cse_reciprocals_1 (&gsi
, def
);
604 if (optimize_bb_for_size_p (bb
))
607 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
608 for (gimple_stmt_iterator gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);
611 gimple stmt
= gsi_stmt (gsi
);
614 if (is_gimple_assign (stmt
)
615 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
617 tree arg1
= gimple_assign_rhs2 (stmt
);
620 if (TREE_CODE (arg1
) != SSA_NAME
)
623 stmt1
= SSA_NAME_DEF_STMT (arg1
);
625 if (is_gimple_call (stmt1
)
626 && gimple_call_lhs (stmt1
)
627 && (fndecl
= gimple_call_fndecl (stmt1
))
628 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
629 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
631 enum built_in_function code
;
636 code
= DECL_FUNCTION_CODE (fndecl
);
637 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
639 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
643 /* Check that all uses of the SSA name are divisions,
644 otherwise replacing the defining statement will do
647 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
649 gimple stmt2
= USE_STMT (use_p
);
650 if (is_gimple_debug (stmt2
))
652 if (!is_gimple_assign (stmt2
)
653 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
654 || gimple_assign_rhs1 (stmt2
) == arg1
655 || gimple_assign_rhs2 (stmt2
) != arg1
)
664 gimple_replace_ssa_lhs (stmt1
, arg1
);
665 gimple_call_set_fndecl (stmt1
, fndecl
);
667 reciprocal_stats
.rfuncs_inserted
++;
669 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
671 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
672 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
673 fold_stmt_inplace (&gsi
);
681 statistics_counter_event (fun
, "reciprocal divs inserted",
682 reciprocal_stats
.rdivs_inserted
);
683 statistics_counter_event (fun
, "reciprocal functions inserted",
684 reciprocal_stats
.rfuncs_inserted
);
686 free_dominance_info (CDI_DOMINATORS
);
687 free_dominance_info (CDI_POST_DOMINATORS
);
688 free_alloc_pool (occ_pool
);
695 make_pass_cse_reciprocals (gcc::context
*ctxt
)
697 return new pass_cse_reciprocals (ctxt
);
700 /* Records an occurrence at statement USE_STMT in the vector of trees
701 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
702 is not yet initialized. Returns true if the occurrence was pushed on
703 the vector. Adjusts *TOP_BB to be the basic block dominating all
704 statements in the vector. */
707 maybe_record_sincos (vec
<gimple
> *stmts
,
708 basic_block
*top_bb
, gimple use_stmt
)
710 basic_block use_bb
= gimple_bb (use_stmt
);
712 && (*top_bb
== use_bb
713 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
714 stmts
->safe_push (use_stmt
);
716 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
718 stmts
->safe_push (use_stmt
);
727 /* Look for sin, cos and cexpi calls with the same argument NAME and
728 create a single call to cexpi CSEing the result in this case.
729 We first walk over all immediate uses of the argument collecting
730 statements that we can CSE in a vector and in a second pass replace
731 the statement rhs with a REALPART or IMAGPART expression on the
732 result of the cexpi call we insert before the use statement that
733 dominates all other candidates. */
736 execute_cse_sincos_1 (tree name
)
738 gimple_stmt_iterator gsi
;
739 imm_use_iterator use_iter
;
740 tree fndecl
, res
, type
;
741 gimple def_stmt
, use_stmt
, stmt
;
742 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
743 auto_vec
<gimple
> stmts
;
744 basic_block top_bb
= NULL
;
746 bool cfg_changed
= false;
748 type
= TREE_TYPE (name
);
749 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
751 if (gimple_code (use_stmt
) != GIMPLE_CALL
752 || !gimple_call_lhs (use_stmt
)
753 || !(fndecl
= gimple_call_fndecl (use_stmt
))
754 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
757 switch (DECL_FUNCTION_CODE (fndecl
))
759 CASE_FLT_FN (BUILT_IN_COS
):
760 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
763 CASE_FLT_FN (BUILT_IN_SIN
):
764 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
767 CASE_FLT_FN (BUILT_IN_CEXPI
):
768 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
775 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
778 /* Simply insert cexpi at the beginning of top_bb but not earlier than
779 the name def statement. */
780 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
783 stmt
= gimple_build_call (fndecl
, 1, name
);
784 res
= make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl
)), stmt
, "sincostmp");
785 gimple_call_set_lhs (stmt
, res
);
787 def_stmt
= SSA_NAME_DEF_STMT (name
);
788 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
789 && gimple_code (def_stmt
) != GIMPLE_PHI
790 && gimple_bb (def_stmt
) == top_bb
)
792 gsi
= gsi_for_stmt (def_stmt
);
793 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
797 gsi
= gsi_after_labels (top_bb
);
798 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
800 sincos_stats
.inserted
++;
802 /* And adjust the recorded old call sites. */
803 for (i
= 0; stmts
.iterate (i
, &use_stmt
); ++i
)
806 fndecl
= gimple_call_fndecl (use_stmt
);
808 switch (DECL_FUNCTION_CODE (fndecl
))
810 CASE_FLT_FN (BUILT_IN_COS
):
811 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
814 CASE_FLT_FN (BUILT_IN_SIN
):
815 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
818 CASE_FLT_FN (BUILT_IN_CEXPI
):
826 /* Replace call with a copy. */
827 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
829 gsi
= gsi_for_stmt (use_stmt
);
830 gsi_replace (&gsi
, stmt
, true);
831 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
838 /* To evaluate powi(x,n), the floating point value x raised to the
839 constant integer exponent n, we use a hybrid algorithm that
840 combines the "window method" with look-up tables. For an
841 introduction to exponentiation algorithms and "addition chains",
842 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
843 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
844 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
845 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
847 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
848 multiplications to inline before calling the system library's pow
849 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
850 so this default never requires calling pow, powf or powl. */
852 #ifndef POWI_MAX_MULTS
853 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
856 /* The size of the "optimal power tree" lookup table. All
857 exponents less than this value are simply looked up in the
858 powi_table below. This threshold is also used to size the
859 cache of pseudo registers that hold intermediate results. */
860 #define POWI_TABLE_SIZE 256
862 /* The size, in bits of the window, used in the "window method"
863 exponentiation algorithm. This is equivalent to a radix of
864 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
865 #define POWI_WINDOW_SIZE 3
867 /* The following table is an efficient representation of an
868 "optimal power tree". For each value, i, the corresponding
869 value, j, in the table states than an optimal evaluation
870 sequence for calculating pow(x,i) can be found by evaluating
871 pow(x,j)*pow(x,i-j). An optimal power tree for the first
872 100 integers is given in Knuth's "Seminumerical algorithms". */
874 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
876 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
877 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
878 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
879 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
880 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
881 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
882 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
883 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
884 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
885 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
886 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
887 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
888 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
889 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
890 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
891 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
892 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
893 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
894 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
895 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
896 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
897 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
898 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
899 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
900 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
901 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
902 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
903 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
904 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
905 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
906 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
907 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
911 /* Return the number of multiplications required to calculate
912 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
913 subroutine of powi_cost. CACHE is an array indicating
914 which exponents have already been calculated. */
917 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
919 /* If we've already calculated this exponent, then this evaluation
920 doesn't require any additional multiplications. */
925 return powi_lookup_cost (n
- powi_table
[n
], cache
)
926 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
929 /* Return the number of multiplications required to calculate
930 powi(x,n) for an arbitrary x, given the exponent N. This
931 function needs to be kept in sync with powi_as_mults below. */
934 powi_cost (HOST_WIDE_INT n
)
936 bool cache
[POWI_TABLE_SIZE
];
937 unsigned HOST_WIDE_INT digit
;
938 unsigned HOST_WIDE_INT val
;
944 /* Ignore the reciprocal when calculating the cost. */
945 val
= (n
< 0) ? -n
: n
;
947 /* Initialize the exponent cache. */
948 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
953 while (val
>= POWI_TABLE_SIZE
)
957 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
958 result
+= powi_lookup_cost (digit
, cache
)
959 + POWI_WINDOW_SIZE
+ 1;
960 val
>>= POWI_WINDOW_SIZE
;
969 return result
+ powi_lookup_cost (val
, cache
);
972 /* Recursive subroutine of powi_as_mults. This function takes the
973 array, CACHE, of already calculated exponents and an exponent N and
974 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
977 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
978 HOST_WIDE_INT n
, tree
*cache
)
980 tree op0
, op1
, ssa_target
;
981 unsigned HOST_WIDE_INT digit
;
984 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
987 ssa_target
= make_temp_ssa_name (type
, NULL
, "powmult");
989 if (n
< POWI_TABLE_SIZE
)
991 cache
[n
] = ssa_target
;
992 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
);
993 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
);
997 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
998 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
);
999 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
);
1003 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
);
1007 mult_stmt
= gimple_build_assign (ssa_target
, MULT_EXPR
, op0
, op1
);
1008 gimple_set_location (mult_stmt
, loc
);
1009 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
1014 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
1015 This function needs to be kept in sync with powi_cost above. */
1018 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
1019 tree arg0
, HOST_WIDE_INT n
)
1021 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
);
1026 return build_real (type
, dconst1
);
1028 memset (cache
, 0, sizeof (cache
));
1031 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
);
1035 /* If the original exponent was negative, reciprocate the result. */
1036 target
= make_temp_ssa_name (type
, NULL
, "powmult");
1037 div_stmt
= gimple_build_assign (target
, RDIV_EXPR
,
1038 build_real (type
, dconst1
), result
);
1039 gimple_set_location (div_stmt
, loc
);
1040 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1045 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1046 location info LOC. If the arguments are appropriate, create an
1047 equivalent sequence of statements prior to GSI using an optimal
1048 number of multiplications, and return an expession holding the
1052 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1053 tree arg0
, HOST_WIDE_INT n
)
1055 /* Avoid largest negative number. */
1057 && ((n
>= -1 && n
<= 2)
1058 || (optimize_function_for_speed_p (cfun
)
1059 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1060 return powi_as_mults (gsi
, loc
, arg0
, n
);
1065 /* Build a gimple call statement that calls FN with argument ARG.
1066 Set the lhs of the call statement to a fresh SSA name. Insert the
1067 statement prior to GSI's current position, and return the fresh
1071 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1077 call_stmt
= gimple_build_call (fn
, 1, arg
);
1078 ssa_target
= make_temp_ssa_name (TREE_TYPE (arg
), NULL
, "powroot");
1079 gimple_set_lhs (call_stmt
, ssa_target
);
1080 gimple_set_location (call_stmt
, loc
);
1081 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1086 /* Build a gimple binary operation with the given CODE and arguments
1087 ARG0, ARG1, assigning the result to a new SSA name for variable
1088 TARGET. Insert the statement prior to GSI's current position, and
1089 return the fresh SSA name.*/
1092 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1093 const char *name
, enum tree_code code
,
1094 tree arg0
, tree arg1
)
1096 tree result
= make_temp_ssa_name (TREE_TYPE (arg0
), NULL
, name
);
1097 gassign
*stmt
= gimple_build_assign (result
, code
, arg0
, arg1
);
1098 gimple_set_location (stmt
, loc
);
1099 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1103 /* Build a gimple reference operation with the given CODE and argument
1104 ARG, assigning the result to a new SSA name of TYPE with NAME.
1105 Insert the statement prior to GSI's current position, and return
1106 the fresh SSA name. */
1109 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1110 const char *name
, enum tree_code code
, tree arg0
)
1112 tree result
= make_temp_ssa_name (type
, NULL
, name
);
1113 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1114 gimple_set_location (stmt
, loc
);
1115 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1119 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement
1120 prior to GSI's current position, and return the fresh SSA name. */
1123 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1124 tree type
, tree val
)
1126 tree result
= make_ssa_name (type
);
1127 gassign
*stmt
= gimple_build_assign (result
, NOP_EXPR
, val
);
1128 gimple_set_location (stmt
, loc
);
1129 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1133 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1134 with location info LOC. If possible, create an equivalent and
1135 less expensive sequence of statements prior to GSI, and return an
1136 expession holding the result. */
1139 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1140 tree arg0
, tree arg1
)
1142 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1143 REAL_VALUE_TYPE c2
, dconst3
;
1145 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1147 bool hw_sqrt_exists
, c_is_int
, c2_is_int
;
1149 /* If the exponent isn't a constant, there's nothing of interest
1151 if (TREE_CODE (arg1
) != REAL_CST
)
1154 /* If the exponent is equivalent to an integer, expand to an optimal
1155 multiplication sequence when profitable. */
1156 c
= TREE_REAL_CST (arg1
);
1157 n
= real_to_integer (&c
);
1158 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1159 c_is_int
= real_identical (&c
, &cint
);
1162 && ((n
>= -1 && n
<= 2)
1163 || (flag_unsafe_math_optimizations
1164 && optimize_bb_for_speed_p (gsi_bb (*gsi
))
1165 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1166 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1168 /* Attempt various optimizations using sqrt and cbrt. */
1169 type
= TREE_TYPE (arg0
);
1170 mode
= TYPE_MODE (type
);
1171 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1173 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1174 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1177 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1178 && !HONOR_SIGNED_ZEROS (mode
))
1179 return build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1181 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1182 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1183 so do this optimization even if -Os. Don't do this optimization
1184 if we don't have a hardware sqrt insn. */
1185 dconst1_4
= dconst1
;
1186 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1187 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1189 if (flag_unsafe_math_optimizations
1191 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1195 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1198 return build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1201 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1202 optimizing for space. Don't do this optimization if we don't have
1203 a hardware sqrt insn. */
1204 real_from_integer (&dconst3_4
, VOIDmode
, 3, SIGNED
);
1205 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1207 if (flag_unsafe_math_optimizations
1209 && optimize_function_for_speed_p (cfun
)
1210 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1214 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1217 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1219 /* sqrt(x) * sqrt(sqrt(x)) */
1220 return build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1221 sqrt_arg0
, sqrt_sqrt
);
1224 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1225 optimizations since 1./3. is not exactly representable. If x
1226 is negative and finite, the correct value of pow(x,1./3.) is
1227 a NaN with the "invalid" exception raised, because the value
1228 of 1./3. actually has an even denominator. The correct value
1229 of cbrt(x) is a negative real value. */
1230 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1231 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1233 if (flag_unsafe_math_optimizations
1235 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1236 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1237 return build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1239 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1240 if we don't have a hardware sqrt insn. */
1241 dconst1_6
= dconst1_3
;
1242 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1244 if (flag_unsafe_math_optimizations
1247 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1248 && optimize_function_for_speed_p (cfun
)
1250 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1253 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1256 return build_and_insert_call (gsi
, loc
, cbrtfn
, sqrt_arg0
);
1259 /* Optimize pow(x,c), where n = 2c for some nonzero integer n
1260 and c not an integer, into
1262 sqrt(x) * powi(x, n/2), n > 0;
1263 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1265 Do not calculate the powi factor when n/2 = 0. */
1266 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1267 n
= real_to_integer (&c2
);
1268 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1269 c2_is_int
= real_identical (&c2
, &cint
);
1271 if (flag_unsafe_math_optimizations
1275 && optimize_function_for_speed_p (cfun
))
1277 tree powi_x_ndiv2
= NULL_TREE
;
1279 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1280 possible or profitable, give up. Skip the degenerate case when
1281 n is 1 or -1, where the result is always 1. */
1282 if (absu_hwi (n
) != 1)
1284 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1290 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1291 result of the optimal multiply sequence just calculated. */
1292 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1294 if (absu_hwi (n
) == 1)
1297 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1298 sqrt_arg0
, powi_x_ndiv2
);
1300 /* If n is negative, reciprocate the result. */
1302 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1303 build_real (type
, dconst1
), result
);
1307 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1309 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1310 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1312 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1313 different from pow(x, 1./3.) due to rounding and behavior with
1314 negative x, we need to constrain this transformation to unsafe
1315 math and positive x or finite math. */
1316 real_from_integer (&dconst3
, VOIDmode
, 3, SIGNED
);
1317 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1318 real_round (&c2
, mode
, &c2
);
1319 n
= real_to_integer (&c2
);
1320 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1321 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1322 real_convert (&c2
, mode
, &c2
);
1324 if (flag_unsafe_math_optimizations
1326 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1327 && real_identical (&c2
, &c
)
1329 && optimize_function_for_speed_p (cfun
)
1330 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1332 tree powi_x_ndiv3
= NULL_TREE
;
1334 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1335 possible or profitable, give up. Skip the degenerate case when
1336 abs(n) < 3, where the result is always 1. */
1337 if (absu_hwi (n
) >= 3)
1339 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1345 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1346 as that creates an unnecessary variable. Instead, just produce
1347 either cbrt(x) or cbrt(x) * cbrt(x). */
1348 cbrt_x
= build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1350 if (absu_hwi (n
) % 3 == 1)
1351 powi_cbrt_x
= cbrt_x
;
1353 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1356 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1357 if (absu_hwi (n
) < 3)
1358 result
= powi_cbrt_x
;
1360 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1361 powi_x_ndiv3
, powi_cbrt_x
);
1363 /* If n is negative, reciprocate the result. */
1365 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1366 build_real (type
, dconst1
), result
);
1371 /* No optimizations succeeded. */
1375 /* ARG is the argument to a cabs builtin call in GSI with location info
1376 LOC. Create a sequence of statements prior to GSI that calculates
1377 sqrt(R*R + I*I), where R and I are the real and imaginary components
1378 of ARG, respectively. Return an expression holding the result. */
1381 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1383 tree real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1384 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1385 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1386 machine_mode mode
= TYPE_MODE (type
);
1388 if (!flag_unsafe_math_optimizations
1389 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1391 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1394 real_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1395 REALPART_EXPR
, arg
);
1396 addend1
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1397 real_part
, real_part
);
1398 imag_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1399 IMAGPART_EXPR
, arg
);
1400 addend2
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1401 imag_part
, imag_part
);
1402 sum
= build_and_insert_binop (gsi
, loc
, "cabs", PLUS_EXPR
, addend1
, addend2
);
1403 result
= build_and_insert_call (gsi
, loc
, sqrtfn
, sum
);
1408 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1409 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1410 an optimal number of multiplies, when n is a constant. */
1414 const pass_data pass_data_cse_sincos
=
1416 GIMPLE_PASS
, /* type */
1417 "sincos", /* name */
1418 OPTGROUP_NONE
, /* optinfo_flags */
1419 TV_NONE
, /* tv_id */
1420 PROP_ssa
, /* properties_required */
1421 0, /* properties_provided */
1422 0, /* properties_destroyed */
1423 0, /* todo_flags_start */
1424 TODO_update_ssa
, /* todo_flags_finish */
1427 class pass_cse_sincos
: public gimple_opt_pass
1430 pass_cse_sincos (gcc::context
*ctxt
)
1431 : gimple_opt_pass (pass_data_cse_sincos
, ctxt
)
1434 /* opt_pass methods: */
1435 virtual bool gate (function
*)
1437 /* We no longer require either sincos or cexp, since powi expansion
1438 piggybacks on this pass. */
1442 virtual unsigned int execute (function
*);
1444 }; // class pass_cse_sincos
1447 pass_cse_sincos::execute (function
*fun
)
1450 bool cfg_changed
= false;
1452 calculate_dominance_info (CDI_DOMINATORS
);
1453 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1455 FOR_EACH_BB_FN (bb
, fun
)
1457 gimple_stmt_iterator gsi
;
1458 bool cleanup_eh
= false;
1460 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1462 gimple stmt
= gsi_stmt (gsi
);
1465 /* Only the last stmt in a bb could throw, no need to call
1466 gimple_purge_dead_eh_edges if we change something in the middle
1467 of a basic block. */
1470 if (is_gimple_call (stmt
)
1471 && gimple_call_lhs (stmt
)
1472 && (fndecl
= gimple_call_fndecl (stmt
))
1473 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1475 tree arg
, arg0
, arg1
, result
;
1479 switch (DECL_FUNCTION_CODE (fndecl
))
1481 CASE_FLT_FN (BUILT_IN_COS
):
1482 CASE_FLT_FN (BUILT_IN_SIN
):
1483 CASE_FLT_FN (BUILT_IN_CEXPI
):
1484 /* Make sure we have either sincos or cexp. */
1485 if (!targetm
.libc_has_function (function_c99_math_complex
)
1486 && !targetm
.libc_has_function (function_sincos
))
1489 arg
= gimple_call_arg (stmt
, 0);
1490 if (TREE_CODE (arg
) == SSA_NAME
)
1491 cfg_changed
|= execute_cse_sincos_1 (arg
);
1494 CASE_FLT_FN (BUILT_IN_POW
):
1495 arg0
= gimple_call_arg (stmt
, 0);
1496 arg1
= gimple_call_arg (stmt
, 1);
1498 loc
= gimple_location (stmt
);
1499 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1503 tree lhs
= gimple_get_lhs (stmt
);
1504 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1505 gimple_set_location (new_stmt
, loc
);
1506 unlink_stmt_vdef (stmt
);
1507 gsi_replace (&gsi
, new_stmt
, true);
1509 if (gimple_vdef (stmt
))
1510 release_ssa_name (gimple_vdef (stmt
));
1514 CASE_FLT_FN (BUILT_IN_POWI
):
1515 arg0
= gimple_call_arg (stmt
, 0);
1516 arg1
= gimple_call_arg (stmt
, 1);
1517 loc
= gimple_location (stmt
);
1519 if (real_minus_onep (arg0
))
1521 tree t0
, t1
, cond
, one
, minus_one
;
1524 t0
= TREE_TYPE (arg0
);
1525 t1
= TREE_TYPE (arg1
);
1526 one
= build_real (t0
, dconst1
);
1527 minus_one
= build_real (t0
, dconstm1
);
1529 cond
= make_temp_ssa_name (t1
, NULL
, "powi_cond");
1530 stmt
= gimple_build_assign (cond
, BIT_AND_EXPR
,
1531 arg1
, build_int_cst (t1
, 1));
1532 gimple_set_location (stmt
, loc
);
1533 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1535 result
= make_temp_ssa_name (t0
, NULL
, "powi");
1536 stmt
= gimple_build_assign (result
, COND_EXPR
, cond
,
1538 gimple_set_location (stmt
, loc
);
1539 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1543 if (!tree_fits_shwi_p (arg1
))
1546 n
= tree_to_shwi (arg1
);
1547 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1552 tree lhs
= gimple_get_lhs (stmt
);
1553 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1554 gimple_set_location (new_stmt
, loc
);
1555 unlink_stmt_vdef (stmt
);
1556 gsi_replace (&gsi
, new_stmt
, true);
1558 if (gimple_vdef (stmt
))
1559 release_ssa_name (gimple_vdef (stmt
));
1563 CASE_FLT_FN (BUILT_IN_CABS
):
1564 arg0
= gimple_call_arg (stmt
, 0);
1565 loc
= gimple_location (stmt
);
1566 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1570 tree lhs
= gimple_get_lhs (stmt
);
1571 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1572 gimple_set_location (new_stmt
, loc
);
1573 unlink_stmt_vdef (stmt
);
1574 gsi_replace (&gsi
, new_stmt
, true);
1576 if (gimple_vdef (stmt
))
1577 release_ssa_name (gimple_vdef (stmt
));
1586 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
1589 statistics_counter_event (fun
, "sincos statements inserted",
1590 sincos_stats
.inserted
);
1592 free_dominance_info (CDI_DOMINATORS
);
1593 return cfg_changed
? TODO_cleanup_cfg
: 0;
1599 make_pass_cse_sincos (gcc::context
*ctxt
)
1601 return new pass_cse_sincos (ctxt
);
1604 /* A symbolic number is used to detect byte permutation and selection
1605 patterns. Therefore the field N contains an artificial number
1606 consisting of octet sized markers:
1608 0 - target byte has the value 0
1609 FF - target byte has an unknown value (eg. due to sign extension)
1610 1..size - marker value is the target byte index minus one.
1612 To detect permutations on memory sources (arrays and structures), a symbolic
1613 number is also associated a base address (the array or structure the load is
1614 made from), an offset from the base address and a range which gives the
1615 difference between the highest and lowest accessed memory location to make
1616 such a symbolic number. The range is thus different from size which reflects
1617 the size of the type of current expression. Note that for non memory source,
1618 range holds the same value as size.
1620 For instance, for an array char a[], (short) a[0] | (short) a[3] would have
1621 a size of 2 but a range of 4 while (short) a[0] | ((short) a[0] << 1) would
1622 still have a size of 2 but this time a range of 1. */
1624 struct symbolic_number
{
1629 HOST_WIDE_INT bytepos
;
1632 unsigned HOST_WIDE_INT range
;
1635 #define BITS_PER_MARKER 8
1636 #define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
1637 #define MARKER_BYTE_UNKNOWN MARKER_MASK
1638 #define HEAD_MARKER(n, size) \
1639 ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
1641 /* The number which the find_bswap_or_nop_1 result should match in
1642 order to have a nop. The number is masked according to the size of
1643 the symbolic number before using it. */
1644 #define CMPNOP (sizeof (int64_t) < 8 ? 0 : \
1645 (uint64_t)0x08070605 << 32 | 0x04030201)
1647 /* The number which the find_bswap_or_nop_1 result should match in
1648 order to have a byte swap. The number is masked according to the
1649 size of the symbolic number before using it. */
1650 #define CMPXCHG (sizeof (int64_t) < 8 ? 0 : \
1651 (uint64_t)0x01020304 << 32 | 0x05060708)
1653 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1654 number N. Return false if the requested operation is not permitted
1655 on a symbolic number. */
1658 do_shift_rotate (enum tree_code code
,
1659 struct symbolic_number
*n
,
1662 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1663 unsigned head_marker
;
1665 if (count
% BITS_PER_UNIT
!= 0)
1667 count
= (count
/ BITS_PER_UNIT
) * BITS_PER_MARKER
;
1669 /* Zero out the extra bits of N in order to avoid them being shifted
1670 into the significant bits. */
1671 if (size
< 64 / BITS_PER_MARKER
)
1672 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1680 head_marker
= HEAD_MARKER (n
->n
, size
);
1682 /* Arithmetic shift of signed type: result is dependent on the value. */
1683 if (!TYPE_UNSIGNED (n
->type
) && head_marker
)
1684 for (i
= 0; i
< count
/ BITS_PER_MARKER
; i
++)
1685 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
1686 << ((size
- 1 - i
) * BITS_PER_MARKER
);
1689 n
->n
= (n
->n
<< count
) | (n
->n
>> ((size
* BITS_PER_MARKER
) - count
));
1692 n
->n
= (n
->n
>> count
) | (n
->n
<< ((size
* BITS_PER_MARKER
) - count
));
1697 /* Zero unused bits for size. */
1698 if (size
< 64 / BITS_PER_MARKER
)
1699 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1703 /* Perform sanity checking for the symbolic number N and the gimple
1707 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1711 lhs_type
= gimple_expr_type (stmt
);
1713 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1716 if (TYPE_PRECISION (lhs_type
) != TYPE_PRECISION (n
->type
))
1722 /* Initialize the symbolic number N for the bswap pass from the base element
1723 SRC manipulated by the bitwise OR expression. */
1726 init_symbolic_number (struct symbolic_number
*n
, tree src
)
1730 n
->base_addr
= n
->offset
= n
->alias_set
= n
->vuse
= NULL_TREE
;
1732 /* Set up the symbolic number N by setting each byte to a value between 1 and
1733 the byte size of rhs1. The highest order byte is set to n->size and the
1734 lowest order byte to 1. */
1735 n
->type
= TREE_TYPE (src
);
1736 size
= TYPE_PRECISION (n
->type
);
1737 if (size
% BITS_PER_UNIT
!= 0)
1739 size
/= BITS_PER_UNIT
;
1740 if (size
> 64 / BITS_PER_MARKER
)
1745 if (size
< 64 / BITS_PER_MARKER
)
1746 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1751 /* Check if STMT might be a byte swap or a nop from a memory source and returns
1752 the answer. If so, REF is that memory source and the base of the memory area
1753 accessed and the offset of the access from that base are recorded in N. */
1756 find_bswap_or_nop_load (gimple stmt
, tree ref
, struct symbolic_number
*n
)
1758 /* Leaf node is an array or component ref. Memorize its base and
1759 offset from base to compare to other such leaf node. */
1760 HOST_WIDE_INT bitsize
, bitpos
;
1762 int unsignedp
, volatilep
;
1763 tree offset
, base_addr
;
1765 if (!gimple_assign_load_p (stmt
) || gimple_has_volatile_ops (stmt
))
1768 base_addr
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
1769 &unsignedp
, &volatilep
, false);
1771 if (TREE_CODE (base_addr
) == MEM_REF
)
1773 offset_int bit_offset
= 0;
1774 tree off
= TREE_OPERAND (base_addr
, 1);
1776 if (!integer_zerop (off
))
1778 offset_int boff
, coff
= mem_ref_offset (base_addr
);
1779 boff
= wi::lshift (coff
, LOG2_BITS_PER_UNIT
);
1783 base_addr
= TREE_OPERAND (base_addr
, 0);
1785 /* Avoid returning a negative bitpos as this may wreak havoc later. */
1786 if (wi::neg_p (bit_offset
))
1788 offset_int mask
= wi::mask
<offset_int
> (LOG2_BITS_PER_UNIT
, false);
1789 offset_int tem
= bit_offset
.and_not (mask
);
1790 /* TEM is the bitpos rounded to BITS_PER_UNIT towards -Inf.
1791 Subtract it to BIT_OFFSET and add it (scaled) to OFFSET. */
1793 tem
= wi::arshift (tem
, LOG2_BITS_PER_UNIT
);
1795 offset
= size_binop (PLUS_EXPR
, offset
,
1796 wide_int_to_tree (sizetype
, tem
));
1798 offset
= wide_int_to_tree (sizetype
, tem
);
1801 bitpos
+= bit_offset
.to_shwi ();
1804 if (bitpos
% BITS_PER_UNIT
)
1806 if (bitsize
% BITS_PER_UNIT
)
1809 if (!init_symbolic_number (n
, ref
))
1811 n
->base_addr
= base_addr
;
1813 n
->bytepos
= bitpos
/ BITS_PER_UNIT
;
1814 n
->alias_set
= reference_alias_ptr_type (ref
);
1815 n
->vuse
= gimple_vuse (stmt
);
1819 /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
1820 the operation given by the rhs of STMT on the result. If the operation
1821 could successfully be executed the function returns a gimple stmt whose
1822 rhs's first tree is the expression of the source operand and NULL
1826 find_bswap_or_nop_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1828 enum tree_code code
;
1829 tree rhs1
, rhs2
= NULL
;
1830 gimple rhs1_stmt
, rhs2_stmt
, source_stmt1
;
1831 enum gimple_rhs_class rhs_class
;
1833 if (!limit
|| !is_gimple_assign (stmt
))
1836 rhs1
= gimple_assign_rhs1 (stmt
);
1838 if (find_bswap_or_nop_load (stmt
, rhs1
, n
))
1841 if (TREE_CODE (rhs1
) != SSA_NAME
)
1844 code
= gimple_assign_rhs_code (stmt
);
1845 rhs_class
= gimple_assign_rhs_class (stmt
);
1846 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1848 if (rhs_class
== GIMPLE_BINARY_RHS
)
1849 rhs2
= gimple_assign_rhs2 (stmt
);
1851 /* Handle unary rhs and binary rhs with integer constants as second
1854 if (rhs_class
== GIMPLE_UNARY_RHS
1855 || (rhs_class
== GIMPLE_BINARY_RHS
1856 && TREE_CODE (rhs2
) == INTEGER_CST
))
1858 if (code
!= BIT_AND_EXPR
1859 && code
!= LSHIFT_EXPR
1860 && code
!= RSHIFT_EXPR
1861 && code
!= LROTATE_EXPR
1862 && code
!= RROTATE_EXPR
1863 && !CONVERT_EXPR_CODE_P (code
))
1866 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, n
, limit
- 1);
1868 /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
1869 we have to initialize the symbolic number. */
1872 if (gimple_assign_load_p (stmt
)
1873 || !init_symbolic_number (n
, rhs1
))
1875 source_stmt1
= stmt
;
1882 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1883 uint64_t val
= int_cst_value (rhs2
), mask
= 0;
1884 uint64_t tmp
= (1 << BITS_PER_UNIT
) - 1;
1886 /* Only constants masking full bytes are allowed. */
1887 for (i
= 0; i
< size
; i
++, tmp
<<= BITS_PER_UNIT
)
1888 if ((val
& tmp
) != 0 && (val
& tmp
) != tmp
)
1891 mask
|= (uint64_t) MARKER_MASK
<< (i
* BITS_PER_MARKER
);
1900 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1905 int i
, type_size
, old_type_size
;
1908 type
= gimple_expr_type (stmt
);
1909 type_size
= TYPE_PRECISION (type
);
1910 if (type_size
% BITS_PER_UNIT
!= 0)
1912 type_size
/= BITS_PER_UNIT
;
1913 if (type_size
> 64 / BITS_PER_MARKER
)
1916 /* Sign extension: result is dependent on the value. */
1917 old_type_size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1918 if (!TYPE_UNSIGNED (n
->type
) && type_size
> old_type_size
1919 && HEAD_MARKER (n
->n
, old_type_size
))
1920 for (i
= 0; i
< type_size
- old_type_size
; i
++)
1921 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
1922 << ((type_size
- 1 - i
) * BITS_PER_MARKER
);
1924 if (type_size
< 64 / BITS_PER_MARKER
)
1926 /* If STMT casts to a smaller type mask out the bits not
1927 belonging to the target type. */
1928 n
->n
&= ((uint64_t) 1 << (type_size
* BITS_PER_MARKER
)) - 1;
1932 n
->range
= type_size
;
1938 return verify_symbolic_number_p (n
, stmt
) ? source_stmt1
: NULL
;
1941 /* Handle binary rhs. */
1943 if (rhs_class
== GIMPLE_BINARY_RHS
)
1946 struct symbolic_number n1
, n2
;
1948 gimple source_stmt2
;
1950 if (code
!= BIT_IOR_EXPR
)
1953 if (TREE_CODE (rhs2
) != SSA_NAME
)
1956 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1961 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, &n1
, limit
- 1);
1966 source_stmt2
= find_bswap_or_nop_1 (rhs2_stmt
, &n2
, limit
- 1);
1971 if (TYPE_PRECISION (n1
.type
) != TYPE_PRECISION (n2
.type
))
1974 if (!n1
.vuse
!= !n2
.vuse
||
1975 (n1
.vuse
&& !operand_equal_p (n1
.vuse
, n2
.vuse
, 0)))
1978 if (gimple_assign_rhs1 (source_stmt1
)
1979 != gimple_assign_rhs1 (source_stmt2
))
1982 HOST_WIDE_INT off_sub
;
1983 struct symbolic_number
*n_ptr
;
1985 if (!n1
.base_addr
|| !n2
.base_addr
1986 || !operand_equal_p (n1
.base_addr
, n2
.base_addr
, 0))
1988 if (!n1
.offset
!= !n2
.offset
||
1989 (n1
.offset
&& !operand_equal_p (n1
.offset
, n2
.offset
, 0)))
1992 /* We swap n1 with n2 to have n1 < n2. */
1993 if (n2
.bytepos
< n1
.bytepos
)
1995 struct symbolic_number tmpn
;
2000 source_stmt1
= source_stmt2
;
2003 off_sub
= n2
.bytepos
- n1
.bytepos
;
2005 /* Check that the range of memory covered can be represented by
2006 a symbolic number. */
2007 if (off_sub
+ n2
.range
> 64 / BITS_PER_MARKER
)
2009 n
->range
= n2
.range
+ off_sub
;
2011 /* Reinterpret byte marks in symbolic number holding the value of
2012 bigger weight according to target endianness. */
2013 inc
= BYTES_BIG_ENDIAN
? off_sub
+ n2
.range
- n1
.range
: off_sub
;
2014 size
= TYPE_PRECISION (n1
.type
) / BITS_PER_UNIT
;
2015 if (BYTES_BIG_ENDIAN
)
2019 for (i
= 0; i
< size
; i
++, inc
<<= BITS_PER_MARKER
)
2022 (n_ptr
->n
>> (i
* BITS_PER_MARKER
)) & MARKER_MASK
;
2023 if (marker
&& marker
!= MARKER_BYTE_UNKNOWN
)
2028 n
->range
= n1
.range
;
2031 || alias_ptr_types_compatible_p (n1
.alias_set
, n2
.alias_set
))
2032 n
->alias_set
= n1
.alias_set
;
2034 n
->alias_set
= ptr_type_node
;
2036 n
->base_addr
= n1
.base_addr
;
2037 n
->offset
= n1
.offset
;
2038 n
->bytepos
= n1
.bytepos
;
2040 size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
2041 for (i
= 0, mask
= MARKER_MASK
; i
< size
;
2042 i
++, mask
<<= BITS_PER_MARKER
)
2044 uint64_t masked1
, masked2
;
2046 masked1
= n1
.n
& mask
;
2047 masked2
= n2
.n
& mask
;
2048 if (masked1
&& masked2
&& masked1
!= masked2
)
2053 if (!verify_symbolic_number_p (n
, stmt
))
2060 return source_stmt1
;
2065 /* Check if STMT completes a bswap implementation or a read in a given
2066 endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
2067 accordingly. It also sets N to represent the kind of operations
2068 performed: size of the resulting expression and whether it works on
2069 a memory source, and if so alias-set and vuse. At last, the
2070 function returns a stmt whose rhs's first tree is the source
2074 find_bswap_or_nop (gimple stmt
, struct symbolic_number
*n
, bool *bswap
)
2076 /* The number which the find_bswap_or_nop_1 result should match in order
2077 to have a full byte swap. The number is shifted to the right
2078 according to the size of the symbolic number before using it. */
2079 uint64_t cmpxchg
= CMPXCHG
;
2080 uint64_t cmpnop
= CMPNOP
;
2085 /* The last parameter determines the depth search limit. It usually
2086 correlates directly to the number n of bytes to be touched. We
2087 increase that number by log2(n) + 1 here in order to also
2088 cover signed -> unsigned conversions of the src operand as can be seen
2089 in libgcc, and for initial shift/and operation of the src operand. */
2090 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
2091 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
2092 source_stmt
= find_bswap_or_nop_1 (stmt
, n
, limit
);
2097 /* Find real size of result (highest non zero byte). */
2103 for (tmpn
= n
->n
, rsize
= 0; tmpn
; tmpn
>>= BITS_PER_MARKER
, rsize
++);
2107 /* Zero out the extra bits of N and CMP*. */
2108 if (n
->range
< (int) sizeof (int64_t))
2112 mask
= ((uint64_t) 1 << (n
->range
* BITS_PER_MARKER
)) - 1;
2113 cmpxchg
>>= (64 / BITS_PER_MARKER
- n
->range
) * BITS_PER_MARKER
;
2117 /* A complete byte swap should make the symbolic number to start with
2118 the largest digit in the highest order byte. Unchanged symbolic
2119 number indicates a read with same endianness as target architecture. */
2122 else if (n
->n
== cmpxchg
)
2127 /* Useless bit manipulation performed by code. */
2128 if (!n
->base_addr
&& n
->n
== cmpnop
)
2131 n
->range
*= BITS_PER_UNIT
;
2137 const pass_data pass_data_optimize_bswap
=
2139 GIMPLE_PASS
, /* type */
2141 OPTGROUP_NONE
, /* optinfo_flags */
2142 TV_NONE
, /* tv_id */
2143 PROP_ssa
, /* properties_required */
2144 0, /* properties_provided */
2145 0, /* properties_destroyed */
2146 0, /* todo_flags_start */
2147 0, /* todo_flags_finish */
2150 class pass_optimize_bswap
: public gimple_opt_pass
2153 pass_optimize_bswap (gcc::context
*ctxt
)
2154 : gimple_opt_pass (pass_data_optimize_bswap
, ctxt
)
2157 /* opt_pass methods: */
2158 virtual bool gate (function
*)
2160 return flag_expensive_optimizations
&& optimize
;
2163 virtual unsigned int execute (function
*);
2165 }; // class pass_optimize_bswap
2167 /* Perform the bswap optimization: replace the expression computed in the rhs
2168 of CUR_STMT by an equivalent bswap, load or load + bswap expression.
2169 Which of these alternatives replace the rhs is given by N->base_addr (non
2170 null if a load is needed) and BSWAP. The type, VUSE and set-alias of the
2171 load to perform are also given in N while the builtin bswap invoke is given
2172 in FNDEL. Finally, if a load is involved, SRC_STMT refers to one of the
2173 load statements involved to construct the rhs in CUR_STMT and N->range gives
2174 the size of the rhs expression for maintaining some statistics.
2176 Note that if the replacement involve a load, CUR_STMT is moved just after
2177 SRC_STMT to do the load with the same VUSE which can lead to CUR_STMT
2178 changing of basic block. */
2181 bswap_replace (gimple cur_stmt
, gimple src_stmt
, tree fndecl
, tree bswap_type
,
2182 tree load_type
, struct symbolic_number
*n
, bool bswap
)
2184 gimple_stmt_iterator gsi
;
2188 gsi
= gsi_for_stmt (cur_stmt
);
2189 src
= gimple_assign_rhs1 (src_stmt
);
2190 tgt
= gimple_assign_lhs (cur_stmt
);
2192 /* Need to load the value from memory first. */
2195 gimple_stmt_iterator gsi_ins
= gsi_for_stmt (src_stmt
);
2196 tree addr_expr
, addr_tmp
, val_expr
, val_tmp
;
2197 tree load_offset_ptr
, aligned_load_type
;
2198 gimple addr_stmt
, load_stmt
;
2201 align
= get_object_alignment (src
);
2203 && align
< GET_MODE_ALIGNMENT (TYPE_MODE (load_type
))
2204 && SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type
), align
))
2207 /* Move cur_stmt just before one of the load of the original
2208 to ensure it has the same VUSE. See PR61517 for what could
2210 gsi_move_before (&gsi
, &gsi_ins
);
2211 gsi
= gsi_for_stmt (cur_stmt
);
2213 /* Compute address to load from and cast according to the size
2215 addr_expr
= build_fold_addr_expr (unshare_expr (src
));
2216 if (is_gimple_min_invariant (addr_expr
))
2217 addr_tmp
= addr_expr
;
2220 addr_tmp
= make_temp_ssa_name (TREE_TYPE (addr_expr
), NULL
,
2222 addr_stmt
= gimple_build_assign (addr_tmp
, addr_expr
);
2223 gsi_insert_before (&gsi
, addr_stmt
, GSI_SAME_STMT
);
2226 /* Perform the load. */
2227 aligned_load_type
= load_type
;
2228 if (align
< TYPE_ALIGN (load_type
))
2229 aligned_load_type
= build_aligned_type (load_type
, align
);
2230 load_offset_ptr
= build_int_cst (n
->alias_set
, 0);
2231 val_expr
= fold_build2 (MEM_REF
, aligned_load_type
, addr_tmp
,
2237 nop_stats
.found_16bit
++;
2238 else if (n
->range
== 32)
2239 nop_stats
.found_32bit
++;
2242 gcc_assert (n
->range
== 64);
2243 nop_stats
.found_64bit
++;
2246 /* Convert the result of load if necessary. */
2247 if (!useless_type_conversion_p (TREE_TYPE (tgt
), load_type
))
2249 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
,
2251 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2252 gimple_set_vuse (load_stmt
, n
->vuse
);
2253 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
2254 gimple_assign_set_rhs_with_ops (&gsi
, NOP_EXPR
, val_tmp
);
2258 gimple_assign_set_rhs_with_ops (&gsi
, MEM_REF
, val_expr
);
2259 gimple_set_vuse (cur_stmt
, n
->vuse
);
2261 update_stmt (cur_stmt
);
2266 "%d bit load in target endianness found at: ",
2268 print_gimple_stmt (dump_file
, cur_stmt
, 0, 0);
2274 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
, "load_dst");
2275 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2276 gimple_set_vuse (load_stmt
, n
->vuse
);
2277 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
2283 bswap_stats
.found_16bit
++;
2284 else if (n
->range
== 32)
2285 bswap_stats
.found_32bit
++;
2288 gcc_assert (n
->range
== 64);
2289 bswap_stats
.found_64bit
++;
2294 /* Canonical form for 16 bit bswap is a rotate expression. Only 16bit values
2295 are considered as rotation of 2N bit values by N bits is generally not
2296 equivalent to a bswap. Consider for instance 0x01020304 >> 16 which gives
2297 0x03040102 while a bswap for that value is 0x04030201. */
2298 if (bswap
&& n
->range
== 16)
2300 tree count
= build_int_cst (NULL
, BITS_PER_UNIT
);
2301 bswap_type
= TREE_TYPE (src
);
2302 src
= fold_build2 (LROTATE_EXPR
, bswap_type
, src
, count
);
2303 bswap_stmt
= gimple_build_assign (NULL
, src
);
2307 /* Convert the src expression if necessary. */
2308 if (!useless_type_conversion_p (TREE_TYPE (tmp
), bswap_type
))
2310 gimple convert_stmt
;
2311 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
2312 convert_stmt
= gimple_build_assign (tmp
, NOP_EXPR
, src
);
2313 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
2316 bswap_stmt
= gimple_build_call (fndecl
, 1, tmp
);
2321 /* Convert the result if necessary. */
2322 if (!useless_type_conversion_p (TREE_TYPE (tgt
), bswap_type
))
2324 gimple convert_stmt
;
2325 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapdst");
2326 convert_stmt
= gimple_build_assign (tgt
, NOP_EXPR
, tmp
);
2327 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
2330 gimple_set_lhs (bswap_stmt
, tmp
);
2334 fprintf (dump_file
, "%d bit bswap implementation found at: ",
2336 print_gimple_stmt (dump_file
, cur_stmt
, 0, 0);
2339 gsi_insert_after (&gsi
, bswap_stmt
, GSI_SAME_STMT
);
2340 gsi_remove (&gsi
, true);
2344 /* Find manual byte swap implementations as well as load in a given
2345 endianness. Byte swaps are turned into a bswap builtin invokation
2346 while endian loads are converted to bswap builtin invokation or
2347 simple load according to the target endianness. */
2350 pass_optimize_bswap::execute (function
*fun
)
2353 bool bswap32_p
, bswap64_p
;
2354 bool changed
= false;
2355 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
2357 if (BITS_PER_UNIT
!= 8)
2360 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
2361 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
2362 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
2363 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
2364 || (bswap32_p
&& word_mode
== SImode
)));
2366 /* Determine the argument type of the builtins. The code later on
2367 assumes that the return and argument type are the same. */
2370 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2371 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2376 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2377 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2380 memset (&nop_stats
, 0, sizeof (nop_stats
));
2381 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
2383 FOR_EACH_BB_FN (bb
, fun
)
2385 gimple_stmt_iterator gsi
;
2387 /* We do a reverse scan for bswap patterns to make sure we get the
2388 widest match. As bswap pattern matching doesn't handle previously
2389 inserted smaller bswap replacements as sub-patterns, the wider
2390 variant wouldn't be detected. */
2391 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
2393 gimple src_stmt
, cur_stmt
= gsi_stmt (gsi
);
2394 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
, load_type
;
2395 enum tree_code code
;
2396 struct symbolic_number n
;
2399 /* This gsi_prev (&gsi) is not part of the for loop because cur_stmt
2400 might be moved to a different basic block by bswap_replace and gsi
2401 must not points to it if that's the case. Moving the gsi_prev
2402 there make sure that gsi points to the statement previous to
2403 cur_stmt while still making sure that all statements are
2404 considered in this basic block. */
2407 if (!is_gimple_assign (cur_stmt
))
2410 code
= gimple_assign_rhs_code (cur_stmt
);
2415 if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt
))
2416 || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt
))
2426 src_stmt
= find_bswap_or_nop (cur_stmt
, &n
, &bswap
);
2434 /* Already in canonical form, nothing to do. */
2435 if (code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
2437 load_type
= uint16_type_node
;
2440 load_type
= uint32_type_node
;
2443 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2444 bswap_type
= bswap32_type
;
2448 load_type
= uint64_type_node
;
2451 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2452 bswap_type
= bswap64_type
;
2459 if (bswap
&& !fndecl
&& n
.range
!= 16)
2462 if (bswap_replace (cur_stmt
, src_stmt
, fndecl
, bswap_type
, load_type
,
2468 statistics_counter_event (fun
, "16-bit nop implementations found",
2469 nop_stats
.found_16bit
);
2470 statistics_counter_event (fun
, "32-bit nop implementations found",
2471 nop_stats
.found_32bit
);
2472 statistics_counter_event (fun
, "64-bit nop implementations found",
2473 nop_stats
.found_64bit
);
2474 statistics_counter_event (fun
, "16-bit bswap implementations found",
2475 bswap_stats
.found_16bit
);
2476 statistics_counter_event (fun
, "32-bit bswap implementations found",
2477 bswap_stats
.found_32bit
);
2478 statistics_counter_event (fun
, "64-bit bswap implementations found",
2479 bswap_stats
.found_64bit
);
2481 return (changed
? TODO_update_ssa
: 0);
2487 make_pass_optimize_bswap (gcc::context
*ctxt
)
2489 return new pass_optimize_bswap (ctxt
);
2492 /* Return true if stmt is a type conversion operation that can be stripped
2493 when used in a widening multiply operation. */
2495 widening_mult_conversion_strippable_p (tree result_type
, gimple stmt
)
2497 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2499 if (TREE_CODE (result_type
) == INTEGER_TYPE
)
2504 if (!CONVERT_EXPR_CODE_P (rhs_code
))
2507 op_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2509 /* If the type of OP has the same precision as the result, then
2510 we can strip this conversion. The multiply operation will be
2511 selected to create the correct extension as a by-product. */
2512 if (TYPE_PRECISION (result_type
) == TYPE_PRECISION (op_type
))
2515 /* We can also strip a conversion if it preserves the signed-ness of
2516 the operation and doesn't narrow the range. */
2517 inner_op_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
2519 /* If the inner-most type is unsigned, then we can strip any
2520 intermediate widening operation. If it's signed, then the
2521 intermediate widening operation must also be signed. */
2522 if ((TYPE_UNSIGNED (inner_op_type
)
2523 || TYPE_UNSIGNED (op_type
) == TYPE_UNSIGNED (inner_op_type
))
2524 && TYPE_PRECISION (op_type
) > TYPE_PRECISION (inner_op_type
))
2530 return rhs_code
== FIXED_CONVERT_EXPR
;
2533 /* Return true if RHS is a suitable operand for a widening multiplication,
2534 assuming a target type of TYPE.
2535 There are two cases:
2537 - RHS makes some value at least twice as wide. Store that value
2538 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
2540 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
2541 but leave *TYPE_OUT untouched. */
2544 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
2550 if (TREE_CODE (rhs
) == SSA_NAME
)
2552 stmt
= SSA_NAME_DEF_STMT (rhs
);
2553 if (is_gimple_assign (stmt
))
2555 if (! widening_mult_conversion_strippable_p (type
, stmt
))
2559 rhs1
= gimple_assign_rhs1 (stmt
);
2561 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2563 *new_rhs_out
= rhs1
;
2572 type1
= TREE_TYPE (rhs1
);
2574 if (TREE_CODE (type1
) != TREE_CODE (type
)
2575 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2578 *new_rhs_out
= rhs1
;
2583 if (TREE_CODE (rhs
) == INTEGER_CST
)
2593 /* Return true if STMT performs a widening multiplication, assuming the
2594 output type is TYPE. If so, store the unwidened types of the operands
2595 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2596 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2597 and *TYPE2_OUT would give the operands of the multiplication. */
2600 is_widening_mult_p (gimple stmt
,
2601 tree
*type1_out
, tree
*rhs1_out
,
2602 tree
*type2_out
, tree
*rhs2_out
)
2604 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2606 if (TREE_CODE (type
) != INTEGER_TYPE
2607 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2610 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2614 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2618 if (*type1_out
== NULL
)
2620 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2622 *type1_out
= *type2_out
;
2625 if (*type2_out
== NULL
)
2627 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2629 *type2_out
= *type1_out
;
2632 /* Ensure that the larger of the two operands comes first. */
2633 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
2637 *type1_out
= *type2_out
;
2640 *rhs1_out
= *rhs2_out
;
2647 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2648 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2649 value is true iff we converted the statement. */
2652 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
2654 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
2655 enum insn_code handler
;
2656 machine_mode to_mode
, from_mode
, actual_mode
;
2658 int actual_precision
;
2659 location_t loc
= gimple_location (stmt
);
2660 bool from_unsigned1
, from_unsigned2
;
2662 lhs
= gimple_assign_lhs (stmt
);
2663 type
= TREE_TYPE (lhs
);
2664 if (TREE_CODE (type
) != INTEGER_TYPE
)
2667 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2670 to_mode
= TYPE_MODE (type
);
2671 from_mode
= TYPE_MODE (type1
);
2672 from_unsigned1
= TYPE_UNSIGNED (type1
);
2673 from_unsigned2
= TYPE_UNSIGNED (type2
);
2675 if (from_unsigned1
&& from_unsigned2
)
2676 op
= umul_widen_optab
;
2677 else if (!from_unsigned1
&& !from_unsigned2
)
2678 op
= smul_widen_optab
;
2680 op
= usmul_widen_optab
;
2682 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
2685 if (handler
== CODE_FOR_nothing
)
2687 if (op
!= smul_widen_optab
)
2689 /* We can use a signed multiply with unsigned types as long as
2690 there is a wider mode to use, or it is the smaller of the two
2691 types that is unsigned. Note that type1 >= type2, always. */
2692 if ((TYPE_UNSIGNED (type1
)
2693 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2694 || (TYPE_UNSIGNED (type2
)
2695 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2697 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2698 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
2702 op
= smul_widen_optab
;
2703 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
2707 if (handler
== CODE_FOR_nothing
)
2710 from_unsigned1
= from_unsigned2
= false;
2716 /* Ensure that the inputs to the handler are in the correct precison
2717 for the opcode. This will be the full mode size. */
2718 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2719 if (2 * actual_precision
> TYPE_PRECISION (type
))
2721 if (actual_precision
!= TYPE_PRECISION (type1
)
2722 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2723 rhs1
= build_and_insert_cast (gsi
, loc
,
2724 build_nonstandard_integer_type
2725 (actual_precision
, from_unsigned1
), rhs1
);
2726 if (actual_precision
!= TYPE_PRECISION (type2
)
2727 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2728 rhs2
= build_and_insert_cast (gsi
, loc
,
2729 build_nonstandard_integer_type
2730 (actual_precision
, from_unsigned2
), rhs2
);
2732 /* Handle constants. */
2733 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2734 rhs1
= fold_convert (type1
, rhs1
);
2735 if (TREE_CODE (rhs2
) == INTEGER_CST
)
2736 rhs2
= fold_convert (type2
, rhs2
);
2738 gimple_assign_set_rhs1 (stmt
, rhs1
);
2739 gimple_assign_set_rhs2 (stmt
, rhs2
);
2740 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2742 widen_mul_stats
.widen_mults_inserted
++;
2746 /* Process a single gimple statement STMT, which is found at the
2747 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2748 rhs (given by CODE), and try to convert it into a
2749 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2750 is true iff we converted the statement. */
2753 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2754 enum tree_code code
)
2756 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2757 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
2758 tree type
, type1
, type2
, optype
;
2759 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2760 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2762 enum tree_code wmult_code
;
2763 enum insn_code handler
;
2764 machine_mode to_mode
, from_mode
, actual_mode
;
2765 location_t loc
= gimple_location (stmt
);
2766 int actual_precision
;
2767 bool from_unsigned1
, from_unsigned2
;
2769 lhs
= gimple_assign_lhs (stmt
);
2770 type
= TREE_TYPE (lhs
);
2771 if (TREE_CODE (type
) != INTEGER_TYPE
2772 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2775 if (code
== MINUS_EXPR
)
2776 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2778 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2780 rhs1
= gimple_assign_rhs1 (stmt
);
2781 rhs2
= gimple_assign_rhs2 (stmt
);
2783 if (TREE_CODE (rhs1
) == SSA_NAME
)
2785 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2786 if (is_gimple_assign (rhs1_stmt
))
2787 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2790 if (TREE_CODE (rhs2
) == SSA_NAME
)
2792 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2793 if (is_gimple_assign (rhs2_stmt
))
2794 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2797 /* Allow for one conversion statement between the multiply
2798 and addition/subtraction statement. If there are more than
2799 one conversions then we assume they would invalidate this
2800 transformation. If that's not the case then they should have
2801 been folded before now. */
2802 if (CONVERT_EXPR_CODE_P (rhs1_code
))
2804 conv1_stmt
= rhs1_stmt
;
2805 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2806 if (TREE_CODE (rhs1
) == SSA_NAME
)
2808 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2809 if (is_gimple_assign (rhs1_stmt
))
2810 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2815 if (CONVERT_EXPR_CODE_P (rhs2_code
))
2817 conv2_stmt
= rhs2_stmt
;
2818 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
2819 if (TREE_CODE (rhs2
) == SSA_NAME
)
2821 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2822 if (is_gimple_assign (rhs2_stmt
))
2823 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2829 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
2830 is_widening_mult_p, but we still need the rhs returns.
2832 It might also appear that it would be sufficient to use the existing
2833 operands of the widening multiply, but that would limit the choice of
2834 multiply-and-accumulate instructions.
2836 If the widened-multiplication result has more than one uses, it is
2837 probably wiser not to do the conversion. */
2838 if (code
== PLUS_EXPR
2839 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
2841 if (!has_single_use (rhs1
)
2842 || !is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2843 &type2
, &mult_rhs2
))
2846 conv_stmt
= conv1_stmt
;
2848 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
2850 if (!has_single_use (rhs2
)
2851 || !is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2852 &type2
, &mult_rhs2
))
2855 conv_stmt
= conv2_stmt
;
2860 to_mode
= TYPE_MODE (type
);
2861 from_mode
= TYPE_MODE (type1
);
2862 from_unsigned1
= TYPE_UNSIGNED (type1
);
2863 from_unsigned2
= TYPE_UNSIGNED (type2
);
2866 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
2867 if (from_unsigned1
!= from_unsigned2
)
2869 if (!INTEGRAL_TYPE_P (type
))
2871 /* We can use a signed multiply with unsigned types as long as
2872 there is a wider mode to use, or it is the smaller of the two
2873 types that is unsigned. Note that type1 >= type2, always. */
2875 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2877 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2879 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2880 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
2884 from_unsigned1
= from_unsigned2
= false;
2885 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
2889 /* If there was a conversion between the multiply and addition
2890 then we need to make sure it fits a multiply-and-accumulate.
2891 The should be a single mode change which does not change the
2895 /* We use the original, unmodified data types for this. */
2896 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
2897 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
2898 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
2899 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
2901 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
2903 /* Conversion is a truncate. */
2904 if (TYPE_PRECISION (to_type
) < data_size
)
2907 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
2909 /* Conversion is an extend. Check it's the right sort. */
2910 if (TYPE_UNSIGNED (from_type
) != is_unsigned
2911 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
2914 /* else convert is a no-op for our purposes. */
2917 /* Verify that the machine can perform a widening multiply
2918 accumulate in this mode/signedness combination, otherwise
2919 this transformation is likely to pessimize code. */
2920 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
2921 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
2922 from_mode
, 0, &actual_mode
);
2924 if (handler
== CODE_FOR_nothing
)
2927 /* Ensure that the inputs to the handler are in the correct precison
2928 for the opcode. This will be the full mode size. */
2929 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2930 if (actual_precision
!= TYPE_PRECISION (type1
)
2931 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2932 mult_rhs1
= build_and_insert_cast (gsi
, loc
,
2933 build_nonstandard_integer_type
2934 (actual_precision
, from_unsigned1
),
2936 if (actual_precision
!= TYPE_PRECISION (type2
)
2937 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2938 mult_rhs2
= build_and_insert_cast (gsi
, loc
,
2939 build_nonstandard_integer_type
2940 (actual_precision
, from_unsigned2
),
2943 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
2944 add_rhs
= build_and_insert_cast (gsi
, loc
, type
, add_rhs
);
2946 /* Handle constants. */
2947 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
2948 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
2949 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
2950 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
2952 gimple_assign_set_rhs_with_ops (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
2954 update_stmt (gsi_stmt (*gsi
));
2955 widen_mul_stats
.maccs_inserted
++;
2959 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2960 with uses in additions and subtractions to form fused multiply-add
2961 operations. Returns true if successful and MUL_STMT should be removed. */
2964 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2966 tree mul_result
= gimple_get_lhs (mul_stmt
);
2967 tree type
= TREE_TYPE (mul_result
);
2968 gimple use_stmt
, neguse_stmt
;
2970 use_operand_p use_p
;
2971 imm_use_iterator imm_iter
;
2973 if (FLOAT_TYPE_P (type
)
2974 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2977 /* We don't want to do bitfield reduction ops. */
2978 if (INTEGRAL_TYPE_P (type
)
2979 && (TYPE_PRECISION (type
)
2980 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2983 /* If the target doesn't support it, don't generate it. We assume that
2984 if fma isn't available then fms, fnma or fnms are not either. */
2985 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2988 /* If the multiplication has zero uses, it is kept around probably because
2989 of -fnon-call-exceptions. Don't optimize it away in that case,
2991 if (has_zero_uses (mul_result
))
2994 /* Make sure that the multiplication statement becomes dead after
2995 the transformation, thus that all uses are transformed to FMAs.
2996 This means we assume that an FMA operation has the same cost
2998 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
3000 enum tree_code use_code
;
3001 tree result
= mul_result
;
3002 bool negate_p
= false;
3004 use_stmt
= USE_STMT (use_p
);
3006 if (is_gimple_debug (use_stmt
))
3009 /* For now restrict this operations to single basic blocks. In theory
3010 we would want to support sinking the multiplication in
3016 to form a fma in the then block and sink the multiplication to the
3018 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3021 if (!is_gimple_assign (use_stmt
))
3024 use_code
= gimple_assign_rhs_code (use_stmt
);
3026 /* A negate on the multiplication leads to FNMA. */
3027 if (use_code
== NEGATE_EXPR
)
3032 result
= gimple_assign_lhs (use_stmt
);
3034 /* Make sure the negate statement becomes dead with this
3035 single transformation. */
3036 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
3037 &use_p
, &neguse_stmt
))
3040 /* Make sure the multiplication isn't also used on that stmt. */
3041 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
3042 if (USE_FROM_PTR (usep
) == mul_result
)
3046 use_stmt
= neguse_stmt
;
3047 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3049 if (!is_gimple_assign (use_stmt
))
3052 use_code
= gimple_assign_rhs_code (use_stmt
);
3059 if (gimple_assign_rhs2 (use_stmt
) == result
)
3060 negate_p
= !negate_p
;
3065 /* FMA can only be formed from PLUS and MINUS. */
3069 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
3070 by a MULT_EXPR that we'll visit later, we might be able to
3071 get a more profitable match with fnma.
3072 OTOH, if we don't, a negate / fma pair has likely lower latency
3073 that a mult / subtract pair. */
3074 if (use_code
== MINUS_EXPR
&& !negate_p
3075 && gimple_assign_rhs1 (use_stmt
) == result
3076 && optab_handler (fms_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
3077 && optab_handler (fnma_optab
, TYPE_MODE (type
)) != CODE_FOR_nothing
)
3079 tree rhs2
= gimple_assign_rhs2 (use_stmt
);
3081 if (TREE_CODE (rhs2
) == SSA_NAME
)
3083 gimple stmt2
= SSA_NAME_DEF_STMT (rhs2
);
3084 if (has_single_use (rhs2
)
3085 && is_gimple_assign (stmt2
)
3086 && gimple_assign_rhs_code (stmt2
) == MULT_EXPR
)
3091 /* We can't handle a * b + a * b. */
3092 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
3095 /* While it is possible to validate whether or not the exact form
3096 that we've recognized is available in the backend, the assumption
3097 is that the transformation is never a loss. For instance, suppose
3098 the target only has the plain FMA pattern available. Consider
3099 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
3100 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
3101 still have 3 operations, but in the FMA form the two NEGs are
3102 independent and could be run in parallel. */
3105 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
3107 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
3108 enum tree_code use_code
;
3109 tree addop
, mulop1
= op1
, result
= mul_result
;
3110 bool negate_p
= false;
3112 if (is_gimple_debug (use_stmt
))
3115 use_code
= gimple_assign_rhs_code (use_stmt
);
3116 if (use_code
== NEGATE_EXPR
)
3118 result
= gimple_assign_lhs (use_stmt
);
3119 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
3120 gsi_remove (&gsi
, true);
3121 release_defs (use_stmt
);
3123 use_stmt
= neguse_stmt
;
3124 gsi
= gsi_for_stmt (use_stmt
);
3125 use_code
= gimple_assign_rhs_code (use_stmt
);
3129 if (gimple_assign_rhs1 (use_stmt
) == result
)
3131 addop
= gimple_assign_rhs2 (use_stmt
);
3132 /* a * b - c -> a * b + (-c) */
3133 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3134 addop
= force_gimple_operand_gsi (&gsi
,
3135 build1 (NEGATE_EXPR
,
3137 true, NULL_TREE
, true,
3142 addop
= gimple_assign_rhs1 (use_stmt
);
3143 /* a - b * c -> (-b) * c + a */
3144 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3145 negate_p
= !negate_p
;
3149 mulop1
= force_gimple_operand_gsi (&gsi
,
3150 build1 (NEGATE_EXPR
,
3152 true, NULL_TREE
, true,
3155 fma_stmt
= gimple_build_assign (gimple_assign_lhs (use_stmt
),
3156 FMA_EXPR
, mulop1
, op2
, addop
);
3157 gsi_replace (&gsi
, fma_stmt
, true);
3158 widen_mul_stats
.fmas_inserted
++;
3164 /* Find integer multiplications where the operands are extended from
3165 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
3166 where appropriate. */
3170 const pass_data pass_data_optimize_widening_mul
=
3172 GIMPLE_PASS
, /* type */
3173 "widening_mul", /* name */
3174 OPTGROUP_NONE
, /* optinfo_flags */
3175 TV_NONE
, /* tv_id */
3176 PROP_ssa
, /* properties_required */
3177 0, /* properties_provided */
3178 0, /* properties_destroyed */
3179 0, /* todo_flags_start */
3180 TODO_update_ssa
, /* todo_flags_finish */
3183 class pass_optimize_widening_mul
: public gimple_opt_pass
3186 pass_optimize_widening_mul (gcc::context
*ctxt
)
3187 : gimple_opt_pass (pass_data_optimize_widening_mul
, ctxt
)
3190 /* opt_pass methods: */
3191 virtual bool gate (function
*)
3193 return flag_expensive_optimizations
&& optimize
;
3196 virtual unsigned int execute (function
*);
3198 }; // class pass_optimize_widening_mul
3201 pass_optimize_widening_mul::execute (function
*fun
)
3204 bool cfg_changed
= false;
3206 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
3208 FOR_EACH_BB_FN (bb
, fun
)
3210 gimple_stmt_iterator gsi
;
3212 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
3214 gimple stmt
= gsi_stmt (gsi
);
3215 enum tree_code code
;
3217 if (is_gimple_assign (stmt
))
3219 code
= gimple_assign_rhs_code (stmt
);
3223 if (!convert_mult_to_widen (stmt
, &gsi
)
3224 && convert_mult_to_fma (stmt
,
3225 gimple_assign_rhs1 (stmt
),
3226 gimple_assign_rhs2 (stmt
)))
3228 gsi_remove (&gsi
, true);
3229 release_defs (stmt
);
3236 convert_plusminus_to_widen (&gsi
, stmt
, code
);
3242 else if (is_gimple_call (stmt
)
3243 && gimple_call_lhs (stmt
))
3245 tree fndecl
= gimple_call_fndecl (stmt
);
3247 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3249 switch (DECL_FUNCTION_CODE (fndecl
))
3254 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
3255 && REAL_VALUES_EQUAL
3256 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
3258 && convert_mult_to_fma (stmt
,
3259 gimple_call_arg (stmt
, 0),
3260 gimple_call_arg (stmt
, 0)))
3262 unlink_stmt_vdef (stmt
);
3263 if (gsi_remove (&gsi
, true)
3264 && gimple_purge_dead_eh_edges (bb
))
3266 release_defs (stmt
);
3279 statistics_counter_event (fun
, "widening multiplications inserted",
3280 widen_mul_stats
.widen_mults_inserted
);
3281 statistics_counter_event (fun
, "widening maccs inserted",
3282 widen_mul_stats
.maccs_inserted
);
3283 statistics_counter_event (fun
, "fused multiply-adds inserted",
3284 widen_mul_stats
.fmas_inserted
);
3286 return cfg_changed
? TODO_cleanup_cfg
: 0;
3292 make_pass_optimize_widening_mul (gcc::context
*ctxt
)
3294 return new pass_optimize_widening_mul (ctxt
);