1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005-2014 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 "basic-block.h"
94 #include "tree-ssa-alias.h"
95 #include "internal-fn.h"
96 #include "gimple-fold.h"
97 #include "gimple-expr.h"
100 #include "gimple-iterator.h"
101 #include "gimplify.h"
102 #include "gimplify-me.h"
103 #include "stor-layout.h"
104 #include "gimple-ssa.h"
105 #include "tree-cfg.h"
106 #include "tree-phinodes.h"
107 #include "ssa-iterators.h"
108 #include "stringpool.h"
109 #include "tree-ssanames.h"
111 #include "tree-dfa.h"
112 #include "tree-ssa.h"
113 #include "tree-pass.h"
114 #include "alloc-pool.h"
116 #include "gimple-pretty-print.h"
118 /* FIXME: RTL headers have to be included here for optabs. */
119 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */
120 #include "expr.h" /* Because optabs.h wants sepops. */
123 /* This structure represents one basic block that either computes a
124 division, or is a common dominator for basic block that compute a
127 /* The basic block represented by this structure. */
130 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
134 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
135 was inserted in BB. */
136 gimple recip_def_stmt
;
138 /* Pointer to a list of "struct occurrence"s for blocks dominated
140 struct occurrence
*children
;
142 /* Pointer to the next "struct occurrence"s in the list of blocks
143 sharing a common dominator. */
144 struct occurrence
*next
;
146 /* The number of divisions that are in BB before compute_merit. The
147 number of divisions that are in BB or post-dominate it after
151 /* True if the basic block has a division, false if it is a common
152 dominator for basic blocks that do. If it is false and trapping
153 math is active, BB is not a candidate for inserting a reciprocal. */
154 bool bb_has_division
;
159 /* Number of 1.0/X ops inserted. */
162 /* Number of 1.0/FUNC ops inserted. */
168 /* Number of cexpi calls inserted. */
174 /* Number of hand-written 16-bit nop / bswaps found. */
177 /* Number of hand-written 32-bit nop / bswaps found. */
180 /* Number of hand-written 64-bit nop / bswaps found. */
182 } nop_stats
, bswap_stats
;
186 /* Number of widening multiplication ops inserted. */
187 int widen_mults_inserted
;
189 /* Number of integer multiply-and-accumulate ops inserted. */
192 /* Number of fp fused multiply-add ops inserted. */
196 /* The instance of "struct occurrence" representing the highest
197 interesting block in the dominator tree. */
198 static struct occurrence
*occ_head
;
200 /* Allocation pool for getting instances of "struct occurrence". */
201 static alloc_pool occ_pool
;
205 /* Allocate and return a new struct occurrence for basic block BB, and
206 whose children list is headed by CHILDREN. */
207 static struct occurrence
*
208 occ_new (basic_block bb
, struct occurrence
*children
)
210 struct occurrence
*occ
;
212 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
213 memset (occ
, 0, sizeof (struct occurrence
));
216 occ
->children
= children
;
221 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
222 list of "struct occurrence"s, one per basic block, having IDOM as
223 their common dominator.
225 We try to insert NEW_OCC as deep as possible in the tree, and we also
226 insert any other block that is a common dominator for BB and one
227 block already in the tree. */
230 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
231 struct occurrence
**p_head
)
233 struct occurrence
*occ
, **p_occ
;
235 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
237 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
238 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
241 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
244 occ
->next
= new_occ
->children
;
245 new_occ
->children
= occ
;
247 /* Try the next block (it may as well be dominated by BB). */
250 else if (dom
== occ_bb
)
252 /* OCC_BB dominates BB. Tail recurse to look deeper. */
253 insert_bb (new_occ
, dom
, &occ
->children
);
257 else if (dom
!= idom
)
259 gcc_assert (!dom
->aux
);
261 /* There is a dominator between IDOM and BB, add it and make
262 two children out of NEW_OCC and OCC. First, remove OCC from
268 /* None of the previous blocks has DOM as a dominator: if we tail
269 recursed, we would reexamine them uselessly. Just switch BB with
270 DOM, and go on looking for blocks dominated by DOM. */
271 new_occ
= occ_new (dom
, new_occ
);
276 /* Nothing special, go on with the next element. */
281 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
282 new_occ
->next
= *p_head
;
286 /* Register that we found a division in BB. */
289 register_division_in (basic_block bb
)
291 struct occurrence
*occ
;
293 occ
= (struct occurrence
*) bb
->aux
;
296 occ
= occ_new (bb
, NULL
);
297 insert_bb (occ
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), &occ_head
);
300 occ
->bb_has_division
= true;
301 occ
->num_divisions
++;
305 /* Compute the number of divisions that postdominate each block in OCC and
309 compute_merit (struct occurrence
*occ
)
311 struct occurrence
*occ_child
;
312 basic_block dom
= occ
->bb
;
314 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
317 if (occ_child
->children
)
318 compute_merit (occ_child
);
321 bb
= single_noncomplex_succ (dom
);
325 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
326 occ
->num_divisions
+= occ_child
->num_divisions
;
331 /* Return whether USE_STMT is a floating-point division by DEF. */
333 is_division_by (gimple use_stmt
, tree def
)
335 return is_gimple_assign (use_stmt
)
336 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
337 && gimple_assign_rhs2 (use_stmt
) == def
338 /* Do not recognize x / x as valid division, as we are getting
339 confused later by replacing all immediate uses x in such
341 && gimple_assign_rhs1 (use_stmt
) != def
;
344 /* Walk the subset of the dominator tree rooted at OCC, setting the
345 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
346 the given basic block. The field may be left NULL, of course,
347 if it is not possible or profitable to do the optimization.
349 DEF_BSI is an iterator pointing at the statement defining DEF.
350 If RECIP_DEF is set, a dominator already has a computation that can
354 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
355 tree def
, tree recip_def
, int threshold
)
359 gimple_stmt_iterator gsi
;
360 struct occurrence
*occ_child
;
363 && (occ
->bb_has_division
|| !flag_trapping_math
)
364 && occ
->num_divisions
>= threshold
)
366 /* Make a variable with the replacement and substitute it. */
367 type
= TREE_TYPE (def
);
368 recip_def
= create_tmp_reg (type
, "reciptmp");
369 new_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, recip_def
,
370 build_one_cst (type
), def
);
372 if (occ
->bb_has_division
)
374 /* Case 1: insert before an existing division. */
375 gsi
= gsi_after_labels (occ
->bb
);
376 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
379 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
381 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
383 /* Case 2: insert right after the definition. Note that this will
384 never happen if the definition statement can throw, because in
385 that case the sole successor of the statement's basic block will
386 dominate all the uses as well. */
387 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
391 /* Case 3: insert in a basic block not containing defs/uses. */
392 gsi
= gsi_after_labels (occ
->bb
);
393 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
396 reciprocal_stats
.rdivs_inserted
++;
398 occ
->recip_def_stmt
= new_stmt
;
401 occ
->recip_def
= recip_def
;
402 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
403 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
407 /* Replace the division at USE_P with a multiplication by the reciprocal, if
411 replace_reciprocal (use_operand_p use_p
)
413 gimple use_stmt
= USE_STMT (use_p
);
414 basic_block bb
= gimple_bb (use_stmt
);
415 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
417 if (optimize_bb_for_speed_p (bb
)
418 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
420 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
421 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
422 SET_USE (use_p
, occ
->recip_def
);
423 fold_stmt_inplace (&gsi
);
424 update_stmt (use_stmt
);
429 /* Free OCC and return one more "struct occurrence" to be freed. */
431 static struct occurrence
*
432 free_bb (struct occurrence
*occ
)
434 struct occurrence
*child
, *next
;
436 /* First get the two pointers hanging off OCC. */
438 child
= occ
->children
;
440 pool_free (occ_pool
, occ
);
442 /* Now ensure that we don't recurse unless it is necessary. */
448 next
= free_bb (next
);
455 /* Look for floating-point divisions among DEF's uses, and try to
456 replace them by multiplications with the reciprocal. Add
457 as many statements computing the reciprocal as needed.
459 DEF must be a GIMPLE register of a floating-point type. */
462 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
465 imm_use_iterator use_iter
;
466 struct occurrence
*occ
;
467 int count
= 0, threshold
;
469 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
471 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
473 gimple use_stmt
= USE_STMT (use_p
);
474 if (is_division_by (use_stmt
, def
))
476 register_division_in (gimple_bb (use_stmt
));
481 /* Do the expensive part only if we can hope to optimize something. */
482 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
483 if (count
>= threshold
)
486 for (occ
= occ_head
; occ
; occ
= occ
->next
)
489 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
492 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
494 if (is_division_by (use_stmt
, def
))
496 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
497 replace_reciprocal (use_p
);
502 for (occ
= occ_head
; occ
; )
508 /* Go through all the floating-point SSA_NAMEs, and call
509 execute_cse_reciprocals_1 on each of them. */
512 const pass_data pass_data_cse_reciprocals
=
514 GIMPLE_PASS
, /* type */
516 OPTGROUP_NONE
, /* optinfo_flags */
517 true, /* has_execute */
519 PROP_ssa
, /* properties_required */
520 0, /* properties_provided */
521 0, /* properties_destroyed */
522 0, /* todo_flags_start */
523 TODO_update_ssa
, /* todo_flags_finish */
526 class pass_cse_reciprocals
: public gimple_opt_pass
529 pass_cse_reciprocals (gcc::context
*ctxt
)
530 : gimple_opt_pass (pass_data_cse_reciprocals
, ctxt
)
533 /* opt_pass methods: */
534 virtual bool gate (function
*) { return optimize
&& flag_reciprocal_math
; }
535 virtual unsigned int execute (function
*);
537 }; // class pass_cse_reciprocals
540 pass_cse_reciprocals::execute (function
*fun
)
545 occ_pool
= create_alloc_pool ("dominators for recip",
546 sizeof (struct occurrence
),
547 n_basic_blocks_for_fn (fun
) / 3 + 1);
549 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
550 calculate_dominance_info (CDI_DOMINATORS
);
551 calculate_dominance_info (CDI_POST_DOMINATORS
);
553 #ifdef ENABLE_CHECKING
554 FOR_EACH_BB_FN (bb
, fun
)
555 gcc_assert (!bb
->aux
);
558 for (arg
= DECL_ARGUMENTS (fun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
559 if (FLOAT_TYPE_P (TREE_TYPE (arg
))
560 && is_gimple_reg (arg
))
562 tree name
= ssa_default_def (fun
, arg
);
564 execute_cse_reciprocals_1 (NULL
, name
);
567 FOR_EACH_BB_FN (bb
, fun
)
569 gimple_stmt_iterator gsi
;
573 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
575 phi
= gsi_stmt (gsi
);
576 def
= PHI_RESULT (phi
);
577 if (! virtual_operand_p (def
)
578 && FLOAT_TYPE_P (TREE_TYPE (def
)))
579 execute_cse_reciprocals_1 (NULL
, def
);
582 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
584 gimple stmt
= gsi_stmt (gsi
);
586 if (gimple_has_lhs (stmt
)
587 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
588 && FLOAT_TYPE_P (TREE_TYPE (def
))
589 && TREE_CODE (def
) == SSA_NAME
)
590 execute_cse_reciprocals_1 (&gsi
, def
);
593 if (optimize_bb_for_size_p (bb
))
596 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
597 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
599 gimple stmt
= gsi_stmt (gsi
);
602 if (is_gimple_assign (stmt
)
603 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
605 tree arg1
= gimple_assign_rhs2 (stmt
);
608 if (TREE_CODE (arg1
) != SSA_NAME
)
611 stmt1
= SSA_NAME_DEF_STMT (arg1
);
613 if (is_gimple_call (stmt1
)
614 && gimple_call_lhs (stmt1
)
615 && (fndecl
= gimple_call_fndecl (stmt1
))
616 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
617 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
619 enum built_in_function code
;
624 code
= DECL_FUNCTION_CODE (fndecl
);
625 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
627 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
631 /* Check that all uses of the SSA name are divisions,
632 otherwise replacing the defining statement will do
635 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
637 gimple stmt2
= USE_STMT (use_p
);
638 if (is_gimple_debug (stmt2
))
640 if (!is_gimple_assign (stmt2
)
641 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
642 || gimple_assign_rhs1 (stmt2
) == arg1
643 || gimple_assign_rhs2 (stmt2
) != arg1
)
652 gimple_replace_ssa_lhs (stmt1
, arg1
);
653 gimple_call_set_fndecl (stmt1
, fndecl
);
655 reciprocal_stats
.rfuncs_inserted
++;
657 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
659 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
660 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
661 fold_stmt_inplace (&gsi
);
669 statistics_counter_event (fun
, "reciprocal divs inserted",
670 reciprocal_stats
.rdivs_inserted
);
671 statistics_counter_event (fun
, "reciprocal functions inserted",
672 reciprocal_stats
.rfuncs_inserted
);
674 free_dominance_info (CDI_DOMINATORS
);
675 free_dominance_info (CDI_POST_DOMINATORS
);
676 free_alloc_pool (occ_pool
);
683 make_pass_cse_reciprocals (gcc::context
*ctxt
)
685 return new pass_cse_reciprocals (ctxt
);
688 /* Records an occurrence at statement USE_STMT in the vector of trees
689 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
690 is not yet initialized. Returns true if the occurrence was pushed on
691 the vector. Adjusts *TOP_BB to be the basic block dominating all
692 statements in the vector. */
695 maybe_record_sincos (vec
<gimple
> *stmts
,
696 basic_block
*top_bb
, gimple use_stmt
)
698 basic_block use_bb
= gimple_bb (use_stmt
);
700 && (*top_bb
== use_bb
701 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
702 stmts
->safe_push (use_stmt
);
704 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
706 stmts
->safe_push (use_stmt
);
715 /* Look for sin, cos and cexpi calls with the same argument NAME and
716 create a single call to cexpi CSEing the result in this case.
717 We first walk over all immediate uses of the argument collecting
718 statements that we can CSE in a vector and in a second pass replace
719 the statement rhs with a REALPART or IMAGPART expression on the
720 result of the cexpi call we insert before the use statement that
721 dominates all other candidates. */
724 execute_cse_sincos_1 (tree name
)
726 gimple_stmt_iterator gsi
;
727 imm_use_iterator use_iter
;
728 tree fndecl
, res
, type
;
729 gimple def_stmt
, use_stmt
, stmt
;
730 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
731 vec
<gimple
> stmts
= vNULL
;
732 basic_block top_bb
= NULL
;
734 bool cfg_changed
= false;
736 type
= TREE_TYPE (name
);
737 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
739 if (gimple_code (use_stmt
) != GIMPLE_CALL
740 || !gimple_call_lhs (use_stmt
)
741 || !(fndecl
= gimple_call_fndecl (use_stmt
))
742 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
745 switch (DECL_FUNCTION_CODE (fndecl
))
747 CASE_FLT_FN (BUILT_IN_COS
):
748 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
751 CASE_FLT_FN (BUILT_IN_SIN
):
752 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
755 CASE_FLT_FN (BUILT_IN_CEXPI
):
756 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
763 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
769 /* Simply insert cexpi at the beginning of top_bb but not earlier than
770 the name def statement. */
771 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
774 stmt
= gimple_build_call (fndecl
, 1, name
);
775 res
= make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl
)), stmt
, "sincostmp");
776 gimple_call_set_lhs (stmt
, res
);
778 def_stmt
= SSA_NAME_DEF_STMT (name
);
779 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
780 && gimple_code (def_stmt
) != GIMPLE_PHI
781 && gimple_bb (def_stmt
) == top_bb
)
783 gsi
= gsi_for_stmt (def_stmt
);
784 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
788 gsi
= gsi_after_labels (top_bb
);
789 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
791 sincos_stats
.inserted
++;
793 /* And adjust the recorded old call sites. */
794 for (i
= 0; stmts
.iterate (i
, &use_stmt
); ++i
)
797 fndecl
= gimple_call_fndecl (use_stmt
);
799 switch (DECL_FUNCTION_CODE (fndecl
))
801 CASE_FLT_FN (BUILT_IN_COS
):
802 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
805 CASE_FLT_FN (BUILT_IN_SIN
):
806 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
809 CASE_FLT_FN (BUILT_IN_CEXPI
):
817 /* Replace call with a copy. */
818 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
820 gsi
= gsi_for_stmt (use_stmt
);
821 gsi_replace (&gsi
, stmt
, true);
822 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
831 /* To evaluate powi(x,n), the floating point value x raised to the
832 constant integer exponent n, we use a hybrid algorithm that
833 combines the "window method" with look-up tables. For an
834 introduction to exponentiation algorithms and "addition chains",
835 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
836 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
837 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
838 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
840 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
841 multiplications to inline before calling the system library's pow
842 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
843 so this default never requires calling pow, powf or powl. */
845 #ifndef POWI_MAX_MULTS
846 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
849 /* The size of the "optimal power tree" lookup table. All
850 exponents less than this value are simply looked up in the
851 powi_table below. This threshold is also used to size the
852 cache of pseudo registers that hold intermediate results. */
853 #define POWI_TABLE_SIZE 256
855 /* The size, in bits of the window, used in the "window method"
856 exponentiation algorithm. This is equivalent to a radix of
857 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
858 #define POWI_WINDOW_SIZE 3
860 /* The following table is an efficient representation of an
861 "optimal power tree". For each value, i, the corresponding
862 value, j, in the table states than an optimal evaluation
863 sequence for calculating pow(x,i) can be found by evaluating
864 pow(x,j)*pow(x,i-j). An optimal power tree for the first
865 100 integers is given in Knuth's "Seminumerical algorithms". */
867 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
869 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
870 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
871 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
872 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
873 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
874 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
875 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
876 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
877 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
878 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
879 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
880 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
881 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
882 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
883 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
884 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
885 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
886 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
887 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
888 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
889 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
890 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
891 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
892 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
893 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
894 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
895 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
896 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
897 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
898 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
899 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
900 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
904 /* Return the number of multiplications required to calculate
905 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
906 subroutine of powi_cost. CACHE is an array indicating
907 which exponents have already been calculated. */
910 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
912 /* If we've already calculated this exponent, then this evaluation
913 doesn't require any additional multiplications. */
918 return powi_lookup_cost (n
- powi_table
[n
], cache
)
919 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
922 /* Return the number of multiplications required to calculate
923 powi(x,n) for an arbitrary x, given the exponent N. This
924 function needs to be kept in sync with powi_as_mults below. */
927 powi_cost (HOST_WIDE_INT n
)
929 bool cache
[POWI_TABLE_SIZE
];
930 unsigned HOST_WIDE_INT digit
;
931 unsigned HOST_WIDE_INT val
;
937 /* Ignore the reciprocal when calculating the cost. */
938 val
= (n
< 0) ? -n
: n
;
940 /* Initialize the exponent cache. */
941 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
946 while (val
>= POWI_TABLE_SIZE
)
950 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
951 result
+= powi_lookup_cost (digit
, cache
)
952 + POWI_WINDOW_SIZE
+ 1;
953 val
>>= POWI_WINDOW_SIZE
;
962 return result
+ powi_lookup_cost (val
, cache
);
965 /* Recursive subroutine of powi_as_mults. This function takes the
966 array, CACHE, of already calculated exponents and an exponent N and
967 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
970 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
971 HOST_WIDE_INT n
, tree
*cache
)
973 tree op0
, op1
, ssa_target
;
974 unsigned HOST_WIDE_INT digit
;
977 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
980 ssa_target
= make_temp_ssa_name (type
, NULL
, "powmult");
982 if (n
< POWI_TABLE_SIZE
)
984 cache
[n
] = ssa_target
;
985 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
);
986 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
);
990 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
991 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
);
992 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
);
996 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
);
1000 mult_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, ssa_target
, op0
, op1
);
1001 gimple_set_location (mult_stmt
, loc
);
1002 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
1007 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
1008 This function needs to be kept in sync with powi_cost above. */
1011 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
1012 tree arg0
, HOST_WIDE_INT n
)
1014 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
);
1019 return build_real (type
, dconst1
);
1021 memset (cache
, 0, sizeof (cache
));
1024 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
);
1028 /* If the original exponent was negative, reciprocate the result. */
1029 target
= make_temp_ssa_name (type
, NULL
, "powmult");
1030 div_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, target
,
1031 build_real (type
, dconst1
),
1033 gimple_set_location (div_stmt
, loc
);
1034 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1039 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1040 location info LOC. If the arguments are appropriate, create an
1041 equivalent sequence of statements prior to GSI using an optimal
1042 number of multiplications, and return an expession holding the
1046 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1047 tree arg0
, HOST_WIDE_INT n
)
1049 /* Avoid largest negative number. */
1051 && ((n
>= -1 && n
<= 2)
1052 || (optimize_function_for_speed_p (cfun
)
1053 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1054 return powi_as_mults (gsi
, loc
, arg0
, n
);
1059 /* Build a gimple call statement that calls FN with argument ARG.
1060 Set the lhs of the call statement to a fresh SSA name. Insert the
1061 statement prior to GSI's current position, and return the fresh
1065 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1071 call_stmt
= gimple_build_call (fn
, 1, arg
);
1072 ssa_target
= make_temp_ssa_name (TREE_TYPE (arg
), NULL
, "powroot");
1073 gimple_set_lhs (call_stmt
, ssa_target
);
1074 gimple_set_location (call_stmt
, loc
);
1075 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1080 /* Build a gimple binary operation with the given CODE and arguments
1081 ARG0, ARG1, assigning the result to a new SSA name for variable
1082 TARGET. Insert the statement prior to GSI's current position, and
1083 return the fresh SSA name.*/
1086 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1087 const char *name
, enum tree_code code
,
1088 tree arg0
, tree arg1
)
1090 tree result
= make_temp_ssa_name (TREE_TYPE (arg0
), NULL
, name
);
1091 gimple stmt
= gimple_build_assign_with_ops (code
, result
, arg0
, arg1
);
1092 gimple_set_location (stmt
, loc
);
1093 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1097 /* Build a gimple reference operation with the given CODE and argument
1098 ARG, assigning the result to a new SSA name of TYPE with NAME.
1099 Insert the statement prior to GSI's current position, and return
1100 the fresh SSA name. */
1103 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1104 const char *name
, enum tree_code code
, tree arg0
)
1106 tree result
= make_temp_ssa_name (type
, NULL
, name
);
1107 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1108 gimple_set_location (stmt
, loc
);
1109 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1113 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement
1114 prior to GSI's current position, and return the fresh SSA name. */
1117 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1118 tree type
, tree val
)
1120 tree result
= make_ssa_name (type
, NULL
);
1121 gimple stmt
= gimple_build_assign_with_ops (NOP_EXPR
, result
, val
, NULL_TREE
);
1122 gimple_set_location (stmt
, loc
);
1123 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1127 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1128 with location info LOC. If possible, create an equivalent and
1129 less expensive sequence of statements prior to GSI, and return an
1130 expession holding the result. */
1133 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1134 tree arg0
, tree arg1
)
1136 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1137 REAL_VALUE_TYPE c2
, dconst3
;
1139 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1140 enum machine_mode mode
;
1141 bool hw_sqrt_exists
, c_is_int
, c2_is_int
;
1143 /* If the exponent isn't a constant, there's nothing of interest
1145 if (TREE_CODE (arg1
) != REAL_CST
)
1148 /* If the exponent is equivalent to an integer, expand to an optimal
1149 multiplication sequence when profitable. */
1150 c
= TREE_REAL_CST (arg1
);
1151 n
= real_to_integer (&c
);
1152 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1153 c_is_int
= real_identical (&c
, &cint
);
1156 && ((n
>= -1 && n
<= 2)
1157 || (flag_unsafe_math_optimizations
1158 && optimize_bb_for_speed_p (gsi_bb (*gsi
))
1159 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1160 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1162 /* Attempt various optimizations using sqrt and cbrt. */
1163 type
= TREE_TYPE (arg0
);
1164 mode
= TYPE_MODE (type
);
1165 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1167 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1168 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1171 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1172 && !HONOR_SIGNED_ZEROS (mode
))
1173 return build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1175 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1176 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1177 so do this optimization even if -Os. Don't do this optimization
1178 if we don't have a hardware sqrt insn. */
1179 dconst1_4
= dconst1
;
1180 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1181 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1183 if (flag_unsafe_math_optimizations
1185 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1189 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1192 return build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1195 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1196 optimizing for space. Don't do this optimization if we don't have
1197 a hardware sqrt insn. */
1198 real_from_integer (&dconst3_4
, VOIDmode
, 3, SIGNED
);
1199 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1201 if (flag_unsafe_math_optimizations
1203 && optimize_function_for_speed_p (cfun
)
1204 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1208 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1211 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1213 /* sqrt(x) * sqrt(sqrt(x)) */
1214 return build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1215 sqrt_arg0
, sqrt_sqrt
);
1218 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1219 optimizations since 1./3. is not exactly representable. If x
1220 is negative and finite, the correct value of pow(x,1./3.) is
1221 a NaN with the "invalid" exception raised, because the value
1222 of 1./3. actually has an even denominator. The correct value
1223 of cbrt(x) is a negative real value. */
1224 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1225 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1227 if (flag_unsafe_math_optimizations
1229 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1230 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1231 return build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1233 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1234 if we don't have a hardware sqrt insn. */
1235 dconst1_6
= dconst1_3
;
1236 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1238 if (flag_unsafe_math_optimizations
1241 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1242 && optimize_function_for_speed_p (cfun
)
1244 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1247 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1250 return build_and_insert_call (gsi
, loc
, cbrtfn
, sqrt_arg0
);
1253 /* Optimize pow(x,c), where n = 2c for some nonzero integer n
1254 and c not an integer, into
1256 sqrt(x) * powi(x, n/2), n > 0;
1257 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1259 Do not calculate the powi factor when n/2 = 0. */
1260 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1261 n
= real_to_integer (&c2
);
1262 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1263 c2_is_int
= real_identical (&c2
, &cint
);
1265 if (flag_unsafe_math_optimizations
1269 && optimize_function_for_speed_p (cfun
))
1271 tree powi_x_ndiv2
= NULL_TREE
;
1273 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1274 possible or profitable, give up. Skip the degenerate case when
1275 n is 1 or -1, where the result is always 1. */
1276 if (absu_hwi (n
) != 1)
1278 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1284 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1285 result of the optimal multiply sequence just calculated. */
1286 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1288 if (absu_hwi (n
) == 1)
1291 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1292 sqrt_arg0
, powi_x_ndiv2
);
1294 /* If n is negative, reciprocate the result. */
1296 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1297 build_real (type
, dconst1
), result
);
1301 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1303 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1304 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1306 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1307 different from pow(x, 1./3.) due to rounding and behavior with
1308 negative x, we need to constrain this transformation to unsafe
1309 math and positive x or finite math. */
1310 real_from_integer (&dconst3
, VOIDmode
, 3, SIGNED
);
1311 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1312 real_round (&c2
, mode
, &c2
);
1313 n
= real_to_integer (&c2
);
1314 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1315 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1316 real_convert (&c2
, mode
, &c2
);
1318 if (flag_unsafe_math_optimizations
1320 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1321 && real_identical (&c2
, &c
)
1323 && optimize_function_for_speed_p (cfun
)
1324 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1326 tree powi_x_ndiv3
= NULL_TREE
;
1328 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1329 possible or profitable, give up. Skip the degenerate case when
1330 abs(n) < 3, where the result is always 1. */
1331 if (absu_hwi (n
) >= 3)
1333 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1339 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1340 as that creates an unnecessary variable. Instead, just produce
1341 either cbrt(x) or cbrt(x) * cbrt(x). */
1342 cbrt_x
= build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1344 if (absu_hwi (n
) % 3 == 1)
1345 powi_cbrt_x
= cbrt_x
;
1347 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1350 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1351 if (absu_hwi (n
) < 3)
1352 result
= powi_cbrt_x
;
1354 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1355 powi_x_ndiv3
, powi_cbrt_x
);
1357 /* If n is negative, reciprocate the result. */
1359 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1360 build_real (type
, dconst1
), result
);
1365 /* No optimizations succeeded. */
1369 /* ARG is the argument to a cabs builtin call in GSI with location info
1370 LOC. Create a sequence of statements prior to GSI that calculates
1371 sqrt(R*R + I*I), where R and I are the real and imaginary components
1372 of ARG, respectively. Return an expression holding the result. */
1375 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1377 tree real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1378 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1379 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1380 enum machine_mode mode
= TYPE_MODE (type
);
1382 if (!flag_unsafe_math_optimizations
1383 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1385 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1388 real_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1389 REALPART_EXPR
, arg
);
1390 addend1
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1391 real_part
, real_part
);
1392 imag_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1393 IMAGPART_EXPR
, arg
);
1394 addend2
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1395 imag_part
, imag_part
);
1396 sum
= build_and_insert_binop (gsi
, loc
, "cabs", PLUS_EXPR
, addend1
, addend2
);
1397 result
= build_and_insert_call (gsi
, loc
, sqrtfn
, sum
);
1402 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1403 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1404 an optimal number of multiplies, when n is a constant. */
1408 const pass_data pass_data_cse_sincos
=
1410 GIMPLE_PASS
, /* type */
1411 "sincos", /* name */
1412 OPTGROUP_NONE
, /* optinfo_flags */
1413 true, /* has_execute */
1414 TV_NONE
, /* tv_id */
1415 PROP_ssa
, /* properties_required */
1416 0, /* properties_provided */
1417 0, /* properties_destroyed */
1418 0, /* todo_flags_start */
1419 TODO_update_ssa
, /* todo_flags_finish */
1422 class pass_cse_sincos
: public gimple_opt_pass
1425 pass_cse_sincos (gcc::context
*ctxt
)
1426 : gimple_opt_pass (pass_data_cse_sincos
, ctxt
)
1429 /* opt_pass methods: */
1430 virtual bool gate (function
*)
1432 /* We no longer require either sincos or cexp, since powi expansion
1433 piggybacks on this pass. */
1437 virtual unsigned int execute (function
*);
1439 }; // class pass_cse_sincos
1442 pass_cse_sincos::execute (function
*fun
)
1445 bool cfg_changed
= false;
1447 calculate_dominance_info (CDI_DOMINATORS
);
1448 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1450 FOR_EACH_BB_FN (bb
, fun
)
1452 gimple_stmt_iterator gsi
;
1453 bool cleanup_eh
= false;
1455 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1457 gimple stmt
= gsi_stmt (gsi
);
1460 /* Only the last stmt in a bb could throw, no need to call
1461 gimple_purge_dead_eh_edges if we change something in the middle
1462 of a basic block. */
1465 if (is_gimple_call (stmt
)
1466 && gimple_call_lhs (stmt
)
1467 && (fndecl
= gimple_call_fndecl (stmt
))
1468 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1470 tree arg
, arg0
, arg1
, result
;
1474 switch (DECL_FUNCTION_CODE (fndecl
))
1476 CASE_FLT_FN (BUILT_IN_COS
):
1477 CASE_FLT_FN (BUILT_IN_SIN
):
1478 CASE_FLT_FN (BUILT_IN_CEXPI
):
1479 /* Make sure we have either sincos or cexp. */
1480 if (!targetm
.libc_has_function (function_c99_math_complex
)
1481 && !targetm
.libc_has_function (function_sincos
))
1484 arg
= gimple_call_arg (stmt
, 0);
1485 if (TREE_CODE (arg
) == SSA_NAME
)
1486 cfg_changed
|= execute_cse_sincos_1 (arg
);
1489 CASE_FLT_FN (BUILT_IN_POW
):
1490 arg0
= gimple_call_arg (stmt
, 0);
1491 arg1
= gimple_call_arg (stmt
, 1);
1493 loc
= gimple_location (stmt
);
1494 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1498 tree lhs
= gimple_get_lhs (stmt
);
1499 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1500 gimple_set_location (new_stmt
, loc
);
1501 unlink_stmt_vdef (stmt
);
1502 gsi_replace (&gsi
, new_stmt
, true);
1504 if (gimple_vdef (stmt
))
1505 release_ssa_name (gimple_vdef (stmt
));
1509 CASE_FLT_FN (BUILT_IN_POWI
):
1510 arg0
= gimple_call_arg (stmt
, 0);
1511 arg1
= gimple_call_arg (stmt
, 1);
1512 loc
= gimple_location (stmt
);
1514 if (real_minus_onep (arg0
))
1516 tree t0
, t1
, cond
, one
, minus_one
;
1519 t0
= TREE_TYPE (arg0
);
1520 t1
= TREE_TYPE (arg1
);
1521 one
= build_real (t0
, dconst1
);
1522 minus_one
= build_real (t0
, dconstm1
);
1524 cond
= make_temp_ssa_name (t1
, NULL
, "powi_cond");
1525 stmt
= gimple_build_assign_with_ops (BIT_AND_EXPR
, cond
,
1529 gimple_set_location (stmt
, loc
);
1530 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1532 result
= make_temp_ssa_name (t0
, NULL
, "powi");
1533 stmt
= gimple_build_assign_with_ops (COND_EXPR
, result
,
1536 gimple_set_location (stmt
, loc
);
1537 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1541 if (!tree_fits_shwi_p (arg1
))
1544 n
= tree_to_shwi (arg1
);
1545 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1550 tree lhs
= gimple_get_lhs (stmt
);
1551 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1552 gimple_set_location (new_stmt
, loc
);
1553 unlink_stmt_vdef (stmt
);
1554 gsi_replace (&gsi
, new_stmt
, true);
1556 if (gimple_vdef (stmt
))
1557 release_ssa_name (gimple_vdef (stmt
));
1561 CASE_FLT_FN (BUILT_IN_CABS
):
1562 arg0
= gimple_call_arg (stmt
, 0);
1563 loc
= gimple_location (stmt
);
1564 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1568 tree lhs
= gimple_get_lhs (stmt
);
1569 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1570 gimple_set_location (new_stmt
, loc
);
1571 unlink_stmt_vdef (stmt
);
1572 gsi_replace (&gsi
, new_stmt
, true);
1574 if (gimple_vdef (stmt
))
1575 release_ssa_name (gimple_vdef (stmt
));
1584 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
1587 statistics_counter_event (fun
, "sincos statements inserted",
1588 sincos_stats
.inserted
);
1590 free_dominance_info (CDI_DOMINATORS
);
1591 return cfg_changed
? TODO_cleanup_cfg
: 0;
1597 make_pass_cse_sincos (gcc::context
*ctxt
)
1599 return new pass_cse_sincos (ctxt
);
1602 /* A symbolic number is used to detect byte permutation and selection
1603 patterns. Therefore the field N contains an artificial number
1604 consisting of byte size markers:
1606 0 - byte has the value 0
1607 1..size - byte contains the content of the byte
1608 number indexed with that value minus one.
1610 To detect permutations on memory sources (arrays and structures), a symbolic
1611 number is also associated a base address (the array or structure the load is
1612 made from), an offset from the base address and a range which gives the
1613 difference between the highest and lowest accessed memory location to make
1614 such a symbolic number. The range is thus different from size which reflects
1615 the size of the type of current expression. Note that for non memory source,
1616 range holds the same value as size.
1618 For instance, for an array char a[], (short) a[0] | (short) a[3] would have
1619 a size of 2 but a range of 4 while (short) a[0] | ((short) a[0] << 1) would
1620 still have a size of 2 but this time a range of 1. */
1622 struct symbolic_number
{
1623 unsigned HOST_WIDEST_INT n
;
1627 HOST_WIDE_INT bytepos
;
1630 unsigned HOST_WIDE_INT range
;
1633 /* The number which the find_bswap_or_nop_1 result should match in
1634 order to have a nop. The number is masked according to the size of
1635 the symbolic number before using it. */
1636 #define CMPNOP (sizeof (HOST_WIDEST_INT) < 8 ? 0 : \
1637 (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201)
1639 /* The number which the find_bswap_or_nop_1 result should match in
1640 order to have a byte swap. The number is masked according to the
1641 size of the symbolic number before using it. */
1642 #define CMPXCHG (sizeof (HOST_WIDEST_INT) < 8 ? 0 : \
1643 (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708)
1645 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1646 number N. Return false if the requested operation is not permitted
1647 on a symbolic number. */
1650 do_shift_rotate (enum tree_code code
,
1651 struct symbolic_number
*n
,
1657 /* Zero out the extra bits of N in order to avoid them being shifted
1658 into the significant bits. */
1659 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1660 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1671 n
->n
= (n
->n
<< count
) | (n
->n
>> ((n
->size
* BITS_PER_UNIT
) - count
));
1674 n
->n
= (n
->n
>> count
) | (n
->n
<< ((n
->size
* BITS_PER_UNIT
) - count
));
1679 /* Zero unused bits for size. */
1680 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1681 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
1685 /* Perform sanity checking for the symbolic number N and the gimple
1689 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1693 lhs_type
= gimple_expr_type (stmt
);
1695 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1698 if (TYPE_PRECISION (lhs_type
) != n
->size
* BITS_PER_UNIT
)
1704 /* Check if STMT might be a byte swap or a nop from a memory source and returns
1705 the answer. If so, REF is that memory source and the base of the memory area
1706 accessed and the offset of the access from that base are recorded in N. */
1709 find_bswap_or_nop_load (gimple stmt
, tree ref
, struct symbolic_number
*n
)
1711 /* Leaf node is an array or component ref. Memorize its base and
1712 offset from base to compare to other such leaf node. */
1713 HOST_WIDE_INT bitsize
, bitpos
;
1714 enum machine_mode mode
;
1715 int unsignedp
, volatilep
;
1717 if (!gimple_assign_load_p (stmt
) || gimple_has_volatile_ops (stmt
))
1720 n
->base_addr
= get_inner_reference (ref
, &bitsize
, &bitpos
, &n
->offset
,
1721 &mode
, &unsignedp
, &volatilep
, false);
1723 if (TREE_CODE (n
->base_addr
) == MEM_REF
)
1725 offset_int bit_offset
= 0;
1726 tree off
= TREE_OPERAND (n
->base_addr
, 1);
1728 if (!integer_zerop (off
))
1730 offset_int boff
, coff
= mem_ref_offset (n
->base_addr
);
1731 boff
= wi::lshift (coff
, LOG2_BITS_PER_UNIT
);
1735 n
->base_addr
= TREE_OPERAND (n
->base_addr
, 0);
1737 /* Avoid returning a negative bitpos as this may wreak havoc later. */
1738 if (wi::neg_p (bit_offset
))
1740 offset_int mask
= wi::mask
<offset_int
> (LOG2_BITS_PER_UNIT
, false);
1741 offset_int tem
= bit_offset
.and_not (mask
);
1742 /* TEM is the bitpos rounded to BITS_PER_UNIT towards -Inf.
1743 Subtract it to BIT_OFFSET and add it (scaled) to OFFSET. */
1745 tem
= wi::arshift (tem
, LOG2_BITS_PER_UNIT
);
1747 n
->offset
= size_binop (PLUS_EXPR
, n
->offset
,
1748 wide_int_to_tree (sizetype
, tem
));
1750 n
->offset
= wide_int_to_tree (sizetype
, tem
);
1753 bitpos
+= bit_offset
.to_shwi ();
1756 if (bitpos
% BITS_PER_UNIT
)
1758 if (bitsize
% BITS_PER_UNIT
)
1761 n
->bytepos
= bitpos
/ BITS_PER_UNIT
;
1762 n
->alias_set
= reference_alias_ptr_type (ref
);
1763 n
->vuse
= gimple_vuse (stmt
);
1767 /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
1768 the operation given by the rhs of STMT on the result. If the operation
1769 could successfully be executed the function returns the tree expression of
1770 the source operand and NULL otherwise. */
1773 find_bswap_or_nop_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1775 enum tree_code code
;
1776 tree rhs1
, rhs2
= NULL
;
1777 gimple rhs1_stmt
, rhs2_stmt
;
1779 enum gimple_rhs_class rhs_class
;
1781 if (!limit
|| !is_gimple_assign (stmt
))
1784 rhs1
= gimple_assign_rhs1 (stmt
);
1786 if (find_bswap_or_nop_load (stmt
, rhs1
, n
))
1789 if (TREE_CODE (rhs1
) != SSA_NAME
)
1792 code
= gimple_assign_rhs_code (stmt
);
1793 rhs_class
= gimple_assign_rhs_class (stmt
);
1794 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1796 if (rhs_class
== GIMPLE_BINARY_RHS
)
1797 rhs2
= gimple_assign_rhs2 (stmt
);
1799 /* Handle unary rhs and binary rhs with integer constants as second
1802 if (rhs_class
== GIMPLE_UNARY_RHS
1803 || (rhs_class
== GIMPLE_BINARY_RHS
1804 && TREE_CODE (rhs2
) == INTEGER_CST
))
1806 if (code
!= BIT_AND_EXPR
1807 && code
!= LSHIFT_EXPR
1808 && code
!= RSHIFT_EXPR
1809 && code
!= LROTATE_EXPR
1810 && code
!= RROTATE_EXPR
1812 && code
!= CONVERT_EXPR
)
1815 source_expr1
= find_bswap_or_nop_1 (rhs1_stmt
, n
, limit
- 1);
1817 /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
1818 we have to initialize the symbolic number. */
1819 if (!source_expr1
|| gimple_assign_load_p (rhs1_stmt
))
1821 /* Set up the symbolic number N by setting each byte to a
1822 value between 1 and the byte size of rhs1. The highest
1823 order byte is set to n->size and the lowest order
1825 n
->size
= TYPE_PRECISION (TREE_TYPE (rhs1
));
1826 if (n
->size
% BITS_PER_UNIT
!= 0)
1828 n
->size
/= BITS_PER_UNIT
;
1832 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
1833 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 <<
1834 (n
->size
* BITS_PER_UNIT
)) - 1;
1838 n
->base_addr
= n
->offset
= n
->alias_set
= n
->vuse
= NULL_TREE
;
1839 source_expr1
= rhs1
;
1848 unsigned HOST_WIDEST_INT val
= widest_int_cst_value (rhs2
);
1849 unsigned HOST_WIDEST_INT tmp
= val
;
1851 /* Only constants masking full bytes are allowed. */
1852 for (i
= 0; i
< n
->size
; i
++, tmp
>>= BITS_PER_UNIT
)
1853 if ((tmp
& 0xff) != 0 && (tmp
& 0xff) != 0xff)
1863 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1870 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1871 if (type_size
% BITS_PER_UNIT
!= 0)
1874 if (type_size
/ BITS_PER_UNIT
< (int)(sizeof (HOST_WIDEST_INT
)))
1876 /* If STMT casts to a smaller type mask out the bits not
1877 belonging to the target type. */
1878 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << type_size
) - 1;
1880 n
->size
= type_size
/ BITS_PER_UNIT
;
1888 return verify_symbolic_number_p (n
, stmt
) ? source_expr1
: NULL
;
1891 /* Handle binary rhs. */
1893 if (rhs_class
== GIMPLE_BINARY_RHS
)
1896 struct symbolic_number n1
, n2
;
1897 unsigned HOST_WIDEST_INT mask
;
1900 if (code
!= BIT_IOR_EXPR
)
1903 if (TREE_CODE (rhs2
) != SSA_NAME
)
1906 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1911 source_expr1
= find_bswap_or_nop_1 (rhs1_stmt
, &n1
, limit
- 1);
1916 source_expr2
= find_bswap_or_nop_1 (rhs2_stmt
, &n2
, limit
- 1);
1918 if (n1
.size
!= n2
.size
|| !source_expr2
)
1921 if (!n1
.vuse
!= !n2
.vuse
||
1922 (n1
.vuse
&& !operand_equal_p (n1
.vuse
, n2
.vuse
, 0)))
1925 if (source_expr1
!= source_expr2
)
1927 HOST_WIDEST_INT inc
, mask
;
1929 HOST_WIDE_INT off_sub
;
1930 struct symbolic_number
*n_ptr
;
1932 if (!n1
.base_addr
|| !n2
.base_addr
1933 || !operand_equal_p (n1
.base_addr
, n2
.base_addr
, 0))
1935 if (!n1
.offset
!= !n2
.offset
||
1936 (n1
.offset
&& !operand_equal_p (n1
.offset
, n2
.offset
, 0)))
1939 /* We swap n1 with n2 to have n1 < n2. */
1940 if (n2
.bytepos
< n1
.bytepos
)
1942 struct symbolic_number tmpn
;
1947 source_expr1
= source_expr2
;
1950 off_sub
= n2
.bytepos
- n1
.bytepos
;
1952 /* Check that the range of memory covered < biggest int size. */
1953 if (off_sub
+ n2
.range
> (int) sizeof (HOST_WIDEST_INT
))
1955 n
->range
= n2
.range
+ off_sub
;
1957 /* Reinterpret byte marks in symbolic number holding the value of
1958 bigger weight according to host endianness. */
1959 inc
= BYTES_BIG_ENDIAN
? off_sub
+ n2
.range
- n1
.range
: off_sub
;
1961 if (BYTES_BIG_ENDIAN
)
1965 for (i
= 0; i
< sizeof (HOST_WIDEST_INT
); i
++, inc
<<= 8,
1968 if (n_ptr
->n
& mask
)
1973 n
->range
= n1
.range
;
1976 || alias_ptr_types_compatible_p (n1
.alias_set
, n2
.alias_set
))
1977 n
->alias_set
= n1
.alias_set
;
1979 n
->alias_set
= ptr_type_node
;
1981 n
->base_addr
= n1
.base_addr
;
1982 n
->offset
= n1
.offset
;
1983 n
->bytepos
= n1
.bytepos
;
1985 for (i
= 0, mask
= 0xff; i
< n
->size
; i
++, mask
<<= BITS_PER_UNIT
)
1987 unsigned HOST_WIDEST_INT masked1
, masked2
;
1989 masked1
= n1
.n
& mask
;
1990 masked2
= n2
.n
& mask
;
1991 if (masked1
&& masked2
&& masked1
!= masked2
)
1996 if (!verify_symbolic_number_p (n
, stmt
))
2003 return source_expr1
;
2008 /* Check if STMT completes a bswap implementation or a read in a given
2009 endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
2010 accordingly. It also sets N to represent the kind of operations
2011 performed: size of the resulting expression and whether it works on
2012 a memory source, and if so alias-set and vuse. At last, the
2013 function returns the source tree expression. */
2016 find_bswap_or_nop (gimple stmt
, struct symbolic_number
*n
, bool *bswap
)
2018 /* The number which the find_bswap_or_nop_1 result should match in order
2019 to have a full byte swap. The number is shifted to the right
2020 according to the size of the symbolic number before using it. */
2021 unsigned HOST_WIDEST_INT cmpxchg
= CMPXCHG
;
2022 unsigned HOST_WIDEST_INT cmpnop
= CMPNOP
;
2027 /* The last parameter determines the depth search limit. It usually
2028 correlates directly to the number n of bytes to be touched. We
2029 increase that number by log2(n) + 1 here in order to also
2030 cover signed -> unsigned conversions of the src operand as can be seen
2031 in libgcc, and for initial shift/and operation of the src operand. */
2032 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
2033 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
2034 source_expr
= find_bswap_or_nop_1 (stmt
, n
, limit
);
2039 /* Find real size of result (highest non zero byte). */
2043 unsigned HOST_WIDEST_INT tmpn
;
2045 for (tmpn
= n
->n
, rsize
= 0; tmpn
; tmpn
>>= BITS_PER_UNIT
, rsize
++);
2049 /* Zero out the extra bits of N and CMP*. */
2050 if (n
->range
< (int)sizeof (HOST_WIDEST_INT
))
2052 unsigned HOST_WIDEST_INT mask
;
2054 mask
= ((unsigned HOST_WIDEST_INT
)1 << (n
->range
* BITS_PER_UNIT
)) - 1;
2055 cmpxchg
>>= (sizeof (HOST_WIDEST_INT
) - n
->range
) * BITS_PER_UNIT
;
2059 /* A complete byte swap should make the symbolic number to start with
2060 the largest digit in the highest order byte. Unchanged symbolic
2061 number indicates a read with same endianness as host architecture. */
2064 else if (n
->n
== cmpxchg
)
2069 /* Useless bit manipulation performed by code. */
2070 if (!n
->base_addr
&& n
->n
== cmpnop
)
2073 n
->range
*= BITS_PER_UNIT
;
2079 const pass_data pass_data_optimize_bswap
=
2081 GIMPLE_PASS
, /* type */
2083 OPTGROUP_NONE
, /* optinfo_flags */
2084 true, /* has_execute */
2085 TV_NONE
, /* tv_id */
2086 PROP_ssa
, /* properties_required */
2087 0, /* properties_provided */
2088 0, /* properties_destroyed */
2089 0, /* todo_flags_start */
2090 0, /* todo_flags_finish */
2093 class pass_optimize_bswap
: public gimple_opt_pass
2096 pass_optimize_bswap (gcc::context
*ctxt
)
2097 : gimple_opt_pass (pass_data_optimize_bswap
, ctxt
)
2100 /* opt_pass methods: */
2101 virtual bool gate (function
*)
2103 return flag_expensive_optimizations
&& optimize
;
2106 virtual unsigned int execute (function
*);
2108 }; // class pass_optimize_bswap
2110 /* Perform the bswap optimization: replace the statement STMT at GSI
2111 with load type, VUSE and set-alias as described by N if a memory
2112 source is involved (N->base_addr is non null), followed by the
2113 builtin bswap invocation in FNDECL if BSWAP is true. SRC gives
2114 the source on which STMT is operating and N->range gives the
2115 size of the expression involved for maintaining some statistics. */
2118 bswap_replace (gimple stmt
, gimple_stmt_iterator
*gsi
, tree src
, tree fndecl
,
2119 tree bswap_type
, tree load_type
, struct symbolic_number
*n
,
2125 tgt
= gimple_assign_lhs (stmt
);
2127 /* Need to load the value from memory first. */
2130 tree addr_expr
, addr_tmp
, val_expr
, val_tmp
;
2131 tree load_offset_ptr
, aligned_load_type
;
2132 gimple addr_stmt
, load_stmt
;
2135 align
= get_object_alignment (src
);
2136 if (bswap
&& SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type
), align
))
2139 /* Compute address to load from and cast according to the size
2141 addr_expr
= build_fold_addr_expr (unshare_expr (src
));
2142 if (is_gimple_min_invariant (addr_expr
))
2143 addr_tmp
= addr_expr
;
2146 addr_tmp
= make_temp_ssa_name (TREE_TYPE (addr_expr
), NULL
,
2148 addr_stmt
= gimple_build_assign (addr_tmp
, addr_expr
);
2149 gsi_insert_before (gsi
, addr_stmt
, GSI_SAME_STMT
);
2152 /* Perform the load. */
2153 aligned_load_type
= load_type
;
2154 if (align
< TYPE_ALIGN (load_type
))
2155 aligned_load_type
= build_aligned_type (load_type
, align
);
2156 load_offset_ptr
= build_int_cst (n
->alias_set
, 0);
2157 val_expr
= fold_build2 (MEM_REF
, aligned_load_type
, addr_tmp
,
2163 nop_stats
.found_16bit
++;
2164 else if (n
->range
== 32)
2165 nop_stats
.found_32bit
++;
2168 gcc_assert (n
->range
== 64);
2169 nop_stats
.found_64bit
++;
2172 /* Convert the result of load if necessary. */
2173 if (!useless_type_conversion_p (TREE_TYPE (tgt
), load_type
))
2175 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
,
2177 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2178 gimple_set_vuse (load_stmt
, n
->vuse
);
2179 gsi_insert_before (gsi
, load_stmt
, GSI_SAME_STMT
);
2180 gimple_assign_set_rhs_with_ops_1 (gsi
, NOP_EXPR
, val_tmp
,
2181 NULL_TREE
, NULL_TREE
);
2184 gimple_assign_set_rhs_with_ops_1 (gsi
, MEM_REF
, val_expr
,
2185 NULL_TREE
, NULL_TREE
);
2186 update_stmt (gsi_stmt (*gsi
));
2191 "%d bit load in host endianness found at: ",
2193 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2199 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
, "load_dst");
2200 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2201 gimple_set_vuse (load_stmt
, n
->vuse
);
2202 gsi_insert_before (gsi
, load_stmt
, GSI_SAME_STMT
);
2208 bswap_stats
.found_16bit
++;
2209 else if (n
->range
== 32)
2210 bswap_stats
.found_32bit
++;
2213 gcc_assert (n
->range
== 64);
2214 bswap_stats
.found_64bit
++;
2219 /* Convert the src expression if necessary. */
2220 if (!useless_type_conversion_p (TREE_TYPE (tmp
), bswap_type
))
2222 gimple convert_stmt
;
2223 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
2224 convert_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, tmp
, src
, NULL
);
2225 gsi_insert_before (gsi
, convert_stmt
, GSI_SAME_STMT
);
2228 call
= gimple_build_call (fndecl
, 1, tmp
);
2232 /* Convert the result if necessary. */
2233 if (!useless_type_conversion_p (TREE_TYPE (tgt
), bswap_type
))
2235 gimple convert_stmt
;
2236 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapdst");
2237 convert_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, tgt
, tmp
, NULL
);
2238 gsi_insert_after (gsi
, convert_stmt
, GSI_SAME_STMT
);
2241 gimple_call_set_lhs (call
, tmp
);
2245 fprintf (dump_file
, "%d bit bswap implementation found at: ",
2247 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2250 gsi_insert_after (gsi
, call
, GSI_SAME_STMT
);
2251 gsi_remove (gsi
, true);
2255 /* Find manual byte swap implementations as well as load in a given
2256 endianness. Byte swaps are turned into a bswap builtin invokation
2257 while endian loads are converted to bswap builtin invokation or
2258 simple load according to the host endianness. */
2261 pass_optimize_bswap::execute (function
*fun
)
2264 bool bswap16_p
, bswap32_p
, bswap64_p
;
2265 bool changed
= false;
2266 tree bswap16_type
= NULL_TREE
, bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
2268 if (BITS_PER_UNIT
!= 8)
2271 if (sizeof (HOST_WIDEST_INT
) < 8)
2274 bswap16_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP16
)
2275 && optab_handler (bswap_optab
, HImode
) != CODE_FOR_nothing
);
2276 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
2277 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
2278 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
2279 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
2280 || (bswap32_p
&& word_mode
== SImode
)));
2282 /* Determine the argument type of the builtins. The code later on
2283 assumes that the return and argument type are the same. */
2286 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
2287 bswap16_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2292 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2293 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2298 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2299 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2302 memset (&nop_stats
, 0, sizeof (nop_stats
));
2303 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
2305 FOR_EACH_BB_FN (bb
, fun
)
2307 gimple_stmt_iterator gsi
;
2309 /* We do a reverse scan for bswap patterns to make sure we get the
2310 widest match. As bswap pattern matching doesn't handle
2311 previously inserted smaller bswap replacements as sub-
2312 patterns, the wider variant wouldn't be detected. */
2313 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
2315 gimple stmt
= gsi_stmt (gsi
);
2316 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
;
2317 tree src
, load_type
;
2318 struct symbolic_number n
;
2321 if (!is_gimple_assign (stmt
)
2322 || gimple_assign_rhs_code (stmt
) != BIT_IOR_EXPR
)
2325 src
= find_bswap_or_nop (stmt
, &n
, &bswap
);
2333 load_type
= uint16_type_node
;
2336 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
2337 bswap_type
= bswap16_type
;
2341 load_type
= uint32_type_node
;
2344 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2345 bswap_type
= bswap32_type
;
2349 load_type
= uint64_type_node
;
2352 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2353 bswap_type
= bswap64_type
;
2360 if (bswap
&& !fndecl
)
2363 if (bswap_replace (stmt
, &gsi
, src
, fndecl
, bswap_type
, load_type
,
2369 statistics_counter_event (fun
, "16-bit nop implementations found",
2370 nop_stats
.found_16bit
);
2371 statistics_counter_event (fun
, "32-bit nop implementations found",
2372 nop_stats
.found_32bit
);
2373 statistics_counter_event (fun
, "64-bit nop implementations found",
2374 nop_stats
.found_64bit
);
2375 statistics_counter_event (fun
, "16-bit bswap implementations found",
2376 bswap_stats
.found_16bit
);
2377 statistics_counter_event (fun
, "32-bit bswap implementations found",
2378 bswap_stats
.found_32bit
);
2379 statistics_counter_event (fun
, "64-bit bswap implementations found",
2380 bswap_stats
.found_64bit
);
2382 return (changed
? TODO_update_ssa
: 0);
2388 make_pass_optimize_bswap (gcc::context
*ctxt
)
2390 return new pass_optimize_bswap (ctxt
);
2393 /* Return true if stmt is a type conversion operation that can be stripped
2394 when used in a widening multiply operation. */
2396 widening_mult_conversion_strippable_p (tree result_type
, gimple stmt
)
2398 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2400 if (TREE_CODE (result_type
) == INTEGER_TYPE
)
2405 if (!CONVERT_EXPR_CODE_P (rhs_code
))
2408 op_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2410 /* If the type of OP has the same precision as the result, then
2411 we can strip this conversion. The multiply operation will be
2412 selected to create the correct extension as a by-product. */
2413 if (TYPE_PRECISION (result_type
) == TYPE_PRECISION (op_type
))
2416 /* We can also strip a conversion if it preserves the signed-ness of
2417 the operation and doesn't narrow the range. */
2418 inner_op_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
2420 /* If the inner-most type is unsigned, then we can strip any
2421 intermediate widening operation. If it's signed, then the
2422 intermediate widening operation must also be signed. */
2423 if ((TYPE_UNSIGNED (inner_op_type
)
2424 || TYPE_UNSIGNED (op_type
) == TYPE_UNSIGNED (inner_op_type
))
2425 && TYPE_PRECISION (op_type
) > TYPE_PRECISION (inner_op_type
))
2431 return rhs_code
== FIXED_CONVERT_EXPR
;
2434 /* Return true if RHS is a suitable operand for a widening multiplication,
2435 assuming a target type of TYPE.
2436 There are two cases:
2438 - RHS makes some value at least twice as wide. Store that value
2439 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
2441 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
2442 but leave *TYPE_OUT untouched. */
2445 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
2451 if (TREE_CODE (rhs
) == SSA_NAME
)
2453 stmt
= SSA_NAME_DEF_STMT (rhs
);
2454 if (is_gimple_assign (stmt
))
2456 if (! widening_mult_conversion_strippable_p (type
, stmt
))
2460 rhs1
= gimple_assign_rhs1 (stmt
);
2462 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2464 *new_rhs_out
= rhs1
;
2473 type1
= TREE_TYPE (rhs1
);
2475 if (TREE_CODE (type1
) != TREE_CODE (type
)
2476 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2479 *new_rhs_out
= rhs1
;
2484 if (TREE_CODE (rhs
) == INTEGER_CST
)
2494 /* Return true if STMT performs a widening multiplication, assuming the
2495 output type is TYPE. If so, store the unwidened types of the operands
2496 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2497 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2498 and *TYPE2_OUT would give the operands of the multiplication. */
2501 is_widening_mult_p (gimple stmt
,
2502 tree
*type1_out
, tree
*rhs1_out
,
2503 tree
*type2_out
, tree
*rhs2_out
)
2505 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2507 if (TREE_CODE (type
) != INTEGER_TYPE
2508 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2511 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2515 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2519 if (*type1_out
== NULL
)
2521 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2523 *type1_out
= *type2_out
;
2526 if (*type2_out
== NULL
)
2528 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2530 *type2_out
= *type1_out
;
2533 /* Ensure that the larger of the two operands comes first. */
2534 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
2538 *type1_out
= *type2_out
;
2541 *rhs1_out
= *rhs2_out
;
2548 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2549 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2550 value is true iff we converted the statement. */
2553 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
2555 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
2556 enum insn_code handler
;
2557 enum machine_mode to_mode
, from_mode
, actual_mode
;
2559 int actual_precision
;
2560 location_t loc
= gimple_location (stmt
);
2561 bool from_unsigned1
, from_unsigned2
;
2563 lhs
= gimple_assign_lhs (stmt
);
2564 type
= TREE_TYPE (lhs
);
2565 if (TREE_CODE (type
) != INTEGER_TYPE
)
2568 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2571 to_mode
= TYPE_MODE (type
);
2572 from_mode
= TYPE_MODE (type1
);
2573 from_unsigned1
= TYPE_UNSIGNED (type1
);
2574 from_unsigned2
= TYPE_UNSIGNED (type2
);
2576 if (from_unsigned1
&& from_unsigned2
)
2577 op
= umul_widen_optab
;
2578 else if (!from_unsigned1
&& !from_unsigned2
)
2579 op
= smul_widen_optab
;
2581 op
= usmul_widen_optab
;
2583 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
2586 if (handler
== CODE_FOR_nothing
)
2588 if (op
!= smul_widen_optab
)
2590 /* We can use a signed multiply with unsigned types as long as
2591 there is a wider mode to use, or it is the smaller of the two
2592 types that is unsigned. Note that type1 >= type2, always. */
2593 if ((TYPE_UNSIGNED (type1
)
2594 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2595 || (TYPE_UNSIGNED (type2
)
2596 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2598 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2599 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
2603 op
= smul_widen_optab
;
2604 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
2608 if (handler
== CODE_FOR_nothing
)
2611 from_unsigned1
= from_unsigned2
= false;
2617 /* Ensure that the inputs to the handler are in the correct precison
2618 for the opcode. This will be the full mode size. */
2619 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2620 if (2 * actual_precision
> TYPE_PRECISION (type
))
2622 if (actual_precision
!= TYPE_PRECISION (type1
)
2623 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2624 rhs1
= build_and_insert_cast (gsi
, loc
,
2625 build_nonstandard_integer_type
2626 (actual_precision
, from_unsigned1
), rhs1
);
2627 if (actual_precision
!= TYPE_PRECISION (type2
)
2628 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2629 rhs2
= build_and_insert_cast (gsi
, loc
,
2630 build_nonstandard_integer_type
2631 (actual_precision
, from_unsigned2
), rhs2
);
2633 /* Handle constants. */
2634 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2635 rhs1
= fold_convert (type1
, rhs1
);
2636 if (TREE_CODE (rhs2
) == INTEGER_CST
)
2637 rhs2
= fold_convert (type2
, rhs2
);
2639 gimple_assign_set_rhs1 (stmt
, rhs1
);
2640 gimple_assign_set_rhs2 (stmt
, rhs2
);
2641 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2643 widen_mul_stats
.widen_mults_inserted
++;
2647 /* Process a single gimple statement STMT, which is found at the
2648 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2649 rhs (given by CODE), and try to convert it into a
2650 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2651 is true iff we converted the statement. */
2654 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2655 enum tree_code code
)
2657 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2658 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
2659 tree type
, type1
, type2
, optype
;
2660 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2661 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2663 enum tree_code wmult_code
;
2664 enum insn_code handler
;
2665 enum machine_mode to_mode
, from_mode
, actual_mode
;
2666 location_t loc
= gimple_location (stmt
);
2667 int actual_precision
;
2668 bool from_unsigned1
, from_unsigned2
;
2670 lhs
= gimple_assign_lhs (stmt
);
2671 type
= TREE_TYPE (lhs
);
2672 if (TREE_CODE (type
) != INTEGER_TYPE
2673 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2676 if (code
== MINUS_EXPR
)
2677 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2679 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2681 rhs1
= gimple_assign_rhs1 (stmt
);
2682 rhs2
= gimple_assign_rhs2 (stmt
);
2684 if (TREE_CODE (rhs1
) == SSA_NAME
)
2686 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2687 if (is_gimple_assign (rhs1_stmt
))
2688 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2691 if (TREE_CODE (rhs2
) == SSA_NAME
)
2693 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2694 if (is_gimple_assign (rhs2_stmt
))
2695 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2698 /* Allow for one conversion statement between the multiply
2699 and addition/subtraction statement. If there are more than
2700 one conversions then we assume they would invalidate this
2701 transformation. If that's not the case then they should have
2702 been folded before now. */
2703 if (CONVERT_EXPR_CODE_P (rhs1_code
))
2705 conv1_stmt
= rhs1_stmt
;
2706 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2707 if (TREE_CODE (rhs1
) == SSA_NAME
)
2709 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2710 if (is_gimple_assign (rhs1_stmt
))
2711 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2716 if (CONVERT_EXPR_CODE_P (rhs2_code
))
2718 conv2_stmt
= rhs2_stmt
;
2719 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
2720 if (TREE_CODE (rhs2
) == SSA_NAME
)
2722 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2723 if (is_gimple_assign (rhs2_stmt
))
2724 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2730 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
2731 is_widening_mult_p, but we still need the rhs returns.
2733 It might also appear that it would be sufficient to use the existing
2734 operands of the widening multiply, but that would limit the choice of
2735 multiply-and-accumulate instructions.
2737 If the widened-multiplication result has more than one uses, it is
2738 probably wiser not to do the conversion. */
2739 if (code
== PLUS_EXPR
2740 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
2742 if (!has_single_use (rhs1
)
2743 || !is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2744 &type2
, &mult_rhs2
))
2747 conv_stmt
= conv1_stmt
;
2749 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
2751 if (!has_single_use (rhs2
)
2752 || !is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2753 &type2
, &mult_rhs2
))
2756 conv_stmt
= conv2_stmt
;
2761 to_mode
= TYPE_MODE (type
);
2762 from_mode
= TYPE_MODE (type1
);
2763 from_unsigned1
= TYPE_UNSIGNED (type1
);
2764 from_unsigned2
= TYPE_UNSIGNED (type2
);
2767 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
2768 if (from_unsigned1
!= from_unsigned2
)
2770 if (!INTEGRAL_TYPE_P (type
))
2772 /* We can use a signed multiply with unsigned types as long as
2773 there is a wider mode to use, or it is the smaller of the two
2774 types that is unsigned. Note that type1 >= type2, always. */
2776 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2778 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2780 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2781 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
2785 from_unsigned1
= from_unsigned2
= false;
2786 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
2790 /* If there was a conversion between the multiply and addition
2791 then we need to make sure it fits a multiply-and-accumulate.
2792 The should be a single mode change which does not change the
2796 /* We use the original, unmodified data types for this. */
2797 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
2798 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
2799 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
2800 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
2802 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
2804 /* Conversion is a truncate. */
2805 if (TYPE_PRECISION (to_type
) < data_size
)
2808 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
2810 /* Conversion is an extend. Check it's the right sort. */
2811 if (TYPE_UNSIGNED (from_type
) != is_unsigned
2812 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
2815 /* else convert is a no-op for our purposes. */
2818 /* Verify that the machine can perform a widening multiply
2819 accumulate in this mode/signedness combination, otherwise
2820 this transformation is likely to pessimize code. */
2821 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
2822 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
2823 from_mode
, 0, &actual_mode
);
2825 if (handler
== CODE_FOR_nothing
)
2828 /* Ensure that the inputs to the handler are in the correct precison
2829 for the opcode. This will be the full mode size. */
2830 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2831 if (actual_precision
!= TYPE_PRECISION (type1
)
2832 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2833 mult_rhs1
= build_and_insert_cast (gsi
, loc
,
2834 build_nonstandard_integer_type
2835 (actual_precision
, from_unsigned1
),
2837 if (actual_precision
!= TYPE_PRECISION (type2
)
2838 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2839 mult_rhs2
= build_and_insert_cast (gsi
, loc
,
2840 build_nonstandard_integer_type
2841 (actual_precision
, from_unsigned2
),
2844 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
2845 add_rhs
= build_and_insert_cast (gsi
, loc
, type
, add_rhs
);
2847 /* Handle constants. */
2848 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
2849 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
2850 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
2851 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
2853 gimple_assign_set_rhs_with_ops_1 (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
2855 update_stmt (gsi_stmt (*gsi
));
2856 widen_mul_stats
.maccs_inserted
++;
2860 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2861 with uses in additions and subtractions to form fused multiply-add
2862 operations. Returns true if successful and MUL_STMT should be removed. */
2865 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2867 tree mul_result
= gimple_get_lhs (mul_stmt
);
2868 tree type
= TREE_TYPE (mul_result
);
2869 gimple use_stmt
, neguse_stmt
, fma_stmt
;
2870 use_operand_p use_p
;
2871 imm_use_iterator imm_iter
;
2873 if (FLOAT_TYPE_P (type
)
2874 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2877 /* We don't want to do bitfield reduction ops. */
2878 if (INTEGRAL_TYPE_P (type
)
2879 && (TYPE_PRECISION (type
)
2880 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2883 /* If the target doesn't support it, don't generate it. We assume that
2884 if fma isn't available then fms, fnma or fnms are not either. */
2885 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2888 /* If the multiplication has zero uses, it is kept around probably because
2889 of -fnon-call-exceptions. Don't optimize it away in that case,
2891 if (has_zero_uses (mul_result
))
2894 /* Make sure that the multiplication statement becomes dead after
2895 the transformation, thus that all uses are transformed to FMAs.
2896 This means we assume that an FMA operation has the same cost
2898 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
2900 enum tree_code use_code
;
2901 tree result
= mul_result
;
2902 bool negate_p
= false;
2904 use_stmt
= USE_STMT (use_p
);
2906 if (is_gimple_debug (use_stmt
))
2909 /* For now restrict this operations to single basic blocks. In theory
2910 we would want to support sinking the multiplication in
2916 to form a fma in the then block and sink the multiplication to the
2918 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2921 if (!is_gimple_assign (use_stmt
))
2924 use_code
= gimple_assign_rhs_code (use_stmt
);
2926 /* A negate on the multiplication leads to FNMA. */
2927 if (use_code
== NEGATE_EXPR
)
2932 result
= gimple_assign_lhs (use_stmt
);
2934 /* Make sure the negate statement becomes dead with this
2935 single transformation. */
2936 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
2937 &use_p
, &neguse_stmt
))
2940 /* Make sure the multiplication isn't also used on that stmt. */
2941 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
2942 if (USE_FROM_PTR (usep
) == mul_result
)
2946 use_stmt
= neguse_stmt
;
2947 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
2949 if (!is_gimple_assign (use_stmt
))
2952 use_code
= gimple_assign_rhs_code (use_stmt
);
2959 if (gimple_assign_rhs2 (use_stmt
) == result
)
2960 negate_p
= !negate_p
;
2965 /* FMA can only be formed from PLUS and MINUS. */
2969 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
2970 by a MULT_EXPR that we'll visit later, we might be able to
2971 get a more profitable match with fnma.
2972 OTOH, if we don't, a negate / fma pair has likely lower latency
2973 that a mult / subtract pair. */
2974 if (use_code
== MINUS_EXPR
&& !negate_p
2975 && gimple_assign_rhs1 (use_stmt
) == result
2976 && optab_handler (fms_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
2977 && optab_handler (fnma_optab
, TYPE_MODE (type
)) != CODE_FOR_nothing
)
2979 tree rhs2
= gimple_assign_rhs2 (use_stmt
);
2981 if (TREE_CODE (rhs2
) == SSA_NAME
)
2983 gimple stmt2
= SSA_NAME_DEF_STMT (rhs2
);
2984 if (has_single_use (rhs2
)
2985 && is_gimple_assign (stmt2
)
2986 && gimple_assign_rhs_code (stmt2
) == MULT_EXPR
)
2991 /* We can't handle a * b + a * b. */
2992 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
2995 /* While it is possible to validate whether or not the exact form
2996 that we've recognized is available in the backend, the assumption
2997 is that the transformation is never a loss. For instance, suppose
2998 the target only has the plain FMA pattern available. Consider
2999 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
3000 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
3001 still have 3 operations, but in the FMA form the two NEGs are
3002 independent and could be run in parallel. */
3005 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
3007 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
3008 enum tree_code use_code
;
3009 tree addop
, mulop1
= op1
, result
= mul_result
;
3010 bool negate_p
= false;
3012 if (is_gimple_debug (use_stmt
))
3015 use_code
= gimple_assign_rhs_code (use_stmt
);
3016 if (use_code
== NEGATE_EXPR
)
3018 result
= gimple_assign_lhs (use_stmt
);
3019 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
3020 gsi_remove (&gsi
, true);
3021 release_defs (use_stmt
);
3023 use_stmt
= neguse_stmt
;
3024 gsi
= gsi_for_stmt (use_stmt
);
3025 use_code
= gimple_assign_rhs_code (use_stmt
);
3029 if (gimple_assign_rhs1 (use_stmt
) == result
)
3031 addop
= gimple_assign_rhs2 (use_stmt
);
3032 /* a * b - c -> a * b + (-c) */
3033 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3034 addop
= force_gimple_operand_gsi (&gsi
,
3035 build1 (NEGATE_EXPR
,
3037 true, NULL_TREE
, true,
3042 addop
= gimple_assign_rhs1 (use_stmt
);
3043 /* a - b * c -> (-b) * c + a */
3044 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3045 negate_p
= !negate_p
;
3049 mulop1
= force_gimple_operand_gsi (&gsi
,
3050 build1 (NEGATE_EXPR
,
3052 true, NULL_TREE
, true,
3055 fma_stmt
= gimple_build_assign_with_ops (FMA_EXPR
,
3056 gimple_assign_lhs (use_stmt
),
3059 gsi_replace (&gsi
, fma_stmt
, true);
3060 widen_mul_stats
.fmas_inserted
++;
3066 /* Find integer multiplications where the operands are extended from
3067 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
3068 where appropriate. */
3072 const pass_data pass_data_optimize_widening_mul
=
3074 GIMPLE_PASS
, /* type */
3075 "widening_mul", /* name */
3076 OPTGROUP_NONE
, /* optinfo_flags */
3077 true, /* has_execute */
3078 TV_NONE
, /* tv_id */
3079 PROP_ssa
, /* properties_required */
3080 0, /* properties_provided */
3081 0, /* properties_destroyed */
3082 0, /* todo_flags_start */
3083 TODO_update_ssa
, /* todo_flags_finish */
3086 class pass_optimize_widening_mul
: public gimple_opt_pass
3089 pass_optimize_widening_mul (gcc::context
*ctxt
)
3090 : gimple_opt_pass (pass_data_optimize_widening_mul
, ctxt
)
3093 /* opt_pass methods: */
3094 virtual bool gate (function
*)
3096 return flag_expensive_optimizations
&& optimize
;
3099 virtual unsigned int execute (function
*);
3101 }; // class pass_optimize_widening_mul
3104 pass_optimize_widening_mul::execute (function
*fun
)
3107 bool cfg_changed
= false;
3109 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
3111 FOR_EACH_BB_FN (bb
, fun
)
3113 gimple_stmt_iterator gsi
;
3115 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
3117 gimple stmt
= gsi_stmt (gsi
);
3118 enum tree_code code
;
3120 if (is_gimple_assign (stmt
))
3122 code
= gimple_assign_rhs_code (stmt
);
3126 if (!convert_mult_to_widen (stmt
, &gsi
)
3127 && convert_mult_to_fma (stmt
,
3128 gimple_assign_rhs1 (stmt
),
3129 gimple_assign_rhs2 (stmt
)))
3131 gsi_remove (&gsi
, true);
3132 release_defs (stmt
);
3139 convert_plusminus_to_widen (&gsi
, stmt
, code
);
3145 else if (is_gimple_call (stmt
)
3146 && gimple_call_lhs (stmt
))
3148 tree fndecl
= gimple_call_fndecl (stmt
);
3150 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3152 switch (DECL_FUNCTION_CODE (fndecl
))
3157 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
3158 && REAL_VALUES_EQUAL
3159 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
3161 && convert_mult_to_fma (stmt
,
3162 gimple_call_arg (stmt
, 0),
3163 gimple_call_arg (stmt
, 0)))
3165 unlink_stmt_vdef (stmt
);
3166 if (gsi_remove (&gsi
, true)
3167 && gimple_purge_dead_eh_edges (bb
))
3169 release_defs (stmt
);
3182 statistics_counter_event (fun
, "widening multiplications inserted",
3183 widen_mul_stats
.widen_mults_inserted
);
3184 statistics_counter_event (fun
, "widening maccs inserted",
3185 widen_mul_stats
.maccs_inserted
);
3186 statistics_counter_event (fun
, "fused multiply-adds inserted",
3187 widen_mul_stats
.fmas_inserted
);
3189 return cfg_changed
? TODO_cleanup_cfg
: 0;
3195 make_pass_optimize_widening_mul (gcc::context
*ctxt
)
3197 return new pass_optimize_widening_mul (ctxt
);