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"
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. */
134 /* This structure represents one basic block that either computes a
135 division, or is a common dominator for basic block that compute a
138 /* The basic block represented by this structure. */
141 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
145 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
146 was inserted in BB. */
147 gimple recip_def_stmt
;
149 /* Pointer to a list of "struct occurrence"s for blocks dominated
151 struct occurrence
*children
;
153 /* Pointer to the next "struct occurrence"s in the list of blocks
154 sharing a common dominator. */
155 struct occurrence
*next
;
157 /* The number of divisions that are in BB before compute_merit. The
158 number of divisions that are in BB or post-dominate it after
162 /* True if the basic block has a division, false if it is a common
163 dominator for basic blocks that do. If it is false and trapping
164 math is active, BB is not a candidate for inserting a reciprocal. */
165 bool bb_has_division
;
170 /* Number of 1.0/X ops inserted. */
173 /* Number of 1.0/FUNC ops inserted. */
179 /* Number of cexpi calls inserted. */
185 /* Number of hand-written 16-bit nop / bswaps found. */
188 /* Number of hand-written 32-bit nop / bswaps found. */
191 /* Number of hand-written 64-bit nop / bswaps found. */
193 } nop_stats
, bswap_stats
;
197 /* Number of widening multiplication ops inserted. */
198 int widen_mults_inserted
;
200 /* Number of integer multiply-and-accumulate ops inserted. */
203 /* Number of fp fused multiply-add ops inserted. */
207 /* The instance of "struct occurrence" representing the highest
208 interesting block in the dominator tree. */
209 static struct occurrence
*occ_head
;
211 /* Allocation pool for getting instances of "struct occurrence". */
212 static alloc_pool occ_pool
;
216 /* Allocate and return a new struct occurrence for basic block BB, and
217 whose children list is headed by CHILDREN. */
218 static struct occurrence
*
219 occ_new (basic_block bb
, struct occurrence
*children
)
221 struct occurrence
*occ
;
223 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
224 memset (occ
, 0, sizeof (struct occurrence
));
227 occ
->children
= children
;
232 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
233 list of "struct occurrence"s, one per basic block, having IDOM as
234 their common dominator.
236 We try to insert NEW_OCC as deep as possible in the tree, and we also
237 insert any other block that is a common dominator for BB and one
238 block already in the tree. */
241 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
242 struct occurrence
**p_head
)
244 struct occurrence
*occ
, **p_occ
;
246 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
248 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
249 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
252 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
255 occ
->next
= new_occ
->children
;
256 new_occ
->children
= occ
;
258 /* Try the next block (it may as well be dominated by BB). */
261 else if (dom
== occ_bb
)
263 /* OCC_BB dominates BB. Tail recurse to look deeper. */
264 insert_bb (new_occ
, dom
, &occ
->children
);
268 else if (dom
!= idom
)
270 gcc_assert (!dom
->aux
);
272 /* There is a dominator between IDOM and BB, add it and make
273 two children out of NEW_OCC and OCC. First, remove OCC from
279 /* None of the previous blocks has DOM as a dominator: if we tail
280 recursed, we would reexamine them uselessly. Just switch BB with
281 DOM, and go on looking for blocks dominated by DOM. */
282 new_occ
= occ_new (dom
, new_occ
);
287 /* Nothing special, go on with the next element. */
292 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
293 new_occ
->next
= *p_head
;
297 /* Register that we found a division in BB. */
300 register_division_in (basic_block bb
)
302 struct occurrence
*occ
;
304 occ
= (struct occurrence
*) bb
->aux
;
307 occ
= occ_new (bb
, NULL
);
308 insert_bb (occ
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), &occ_head
);
311 occ
->bb_has_division
= true;
312 occ
->num_divisions
++;
316 /* Compute the number of divisions that postdominate each block in OCC and
320 compute_merit (struct occurrence
*occ
)
322 struct occurrence
*occ_child
;
323 basic_block dom
= occ
->bb
;
325 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
328 if (occ_child
->children
)
329 compute_merit (occ_child
);
332 bb
= single_noncomplex_succ (dom
);
336 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
337 occ
->num_divisions
+= occ_child
->num_divisions
;
342 /* Return whether USE_STMT is a floating-point division by DEF. */
344 is_division_by (gimple use_stmt
, tree def
)
346 return is_gimple_assign (use_stmt
)
347 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
348 && gimple_assign_rhs2 (use_stmt
) == def
349 /* Do not recognize x / x as valid division, as we are getting
350 confused later by replacing all immediate uses x in such
352 && gimple_assign_rhs1 (use_stmt
) != def
;
355 /* Walk the subset of the dominator tree rooted at OCC, setting the
356 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
357 the given basic block. The field may be left NULL, of course,
358 if it is not possible or profitable to do the optimization.
360 DEF_BSI is an iterator pointing at the statement defining DEF.
361 If RECIP_DEF is set, a dominator already has a computation that can
365 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
366 tree def
, tree recip_def
, int threshold
)
370 gimple_stmt_iterator gsi
;
371 struct occurrence
*occ_child
;
374 && (occ
->bb_has_division
|| !flag_trapping_math
)
375 && occ
->num_divisions
>= threshold
)
377 /* Make a variable with the replacement and substitute it. */
378 type
= TREE_TYPE (def
);
379 recip_def
= create_tmp_reg (type
, "reciptmp");
380 new_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, recip_def
,
381 build_one_cst (type
), def
);
383 if (occ
->bb_has_division
)
385 /* Case 1: insert before an existing division. */
386 gsi
= gsi_after_labels (occ
->bb
);
387 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
390 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
392 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
394 /* Case 2: insert right after the definition. Note that this will
395 never happen if the definition statement can throw, because in
396 that case the sole successor of the statement's basic block will
397 dominate all the uses as well. */
398 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
402 /* Case 3: insert in a basic block not containing defs/uses. */
403 gsi
= gsi_after_labels (occ
->bb
);
404 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
407 reciprocal_stats
.rdivs_inserted
++;
409 occ
->recip_def_stmt
= new_stmt
;
412 occ
->recip_def
= recip_def
;
413 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
414 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
418 /* Replace the division at USE_P with a multiplication by the reciprocal, if
422 replace_reciprocal (use_operand_p use_p
)
424 gimple use_stmt
= USE_STMT (use_p
);
425 basic_block bb
= gimple_bb (use_stmt
);
426 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
428 if (optimize_bb_for_speed_p (bb
)
429 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
431 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
432 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
433 SET_USE (use_p
, occ
->recip_def
);
434 fold_stmt_inplace (&gsi
);
435 update_stmt (use_stmt
);
440 /* Free OCC and return one more "struct occurrence" to be freed. */
442 static struct occurrence
*
443 free_bb (struct occurrence
*occ
)
445 struct occurrence
*child
, *next
;
447 /* First get the two pointers hanging off OCC. */
449 child
= occ
->children
;
451 pool_free (occ_pool
, occ
);
453 /* Now ensure that we don't recurse unless it is necessary. */
459 next
= free_bb (next
);
466 /* Look for floating-point divisions among DEF's uses, and try to
467 replace them by multiplications with the reciprocal. Add
468 as many statements computing the reciprocal as needed.
470 DEF must be a GIMPLE register of a floating-point type. */
473 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
476 imm_use_iterator use_iter
;
477 struct occurrence
*occ
;
478 int count
= 0, threshold
;
480 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
482 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
484 gimple use_stmt
= USE_STMT (use_p
);
485 if (is_division_by (use_stmt
, def
))
487 register_division_in (gimple_bb (use_stmt
));
492 /* Do the expensive part only if we can hope to optimize something. */
493 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
494 if (count
>= threshold
)
497 for (occ
= occ_head
; occ
; occ
= occ
->next
)
500 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
503 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
505 if (is_division_by (use_stmt
, def
))
507 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
508 replace_reciprocal (use_p
);
513 for (occ
= occ_head
; occ
; )
519 /* Go through all the floating-point SSA_NAMEs, and call
520 execute_cse_reciprocals_1 on each of them. */
523 const pass_data pass_data_cse_reciprocals
=
525 GIMPLE_PASS
, /* type */
527 OPTGROUP_NONE
, /* optinfo_flags */
529 PROP_ssa
, /* properties_required */
530 0, /* properties_provided */
531 0, /* properties_destroyed */
532 0, /* todo_flags_start */
533 TODO_update_ssa
, /* todo_flags_finish */
536 class pass_cse_reciprocals
: public gimple_opt_pass
539 pass_cse_reciprocals (gcc::context
*ctxt
)
540 : gimple_opt_pass (pass_data_cse_reciprocals
, ctxt
)
543 /* opt_pass methods: */
544 virtual bool gate (function
*) { return optimize
&& flag_reciprocal_math
; }
545 virtual unsigned int execute (function
*);
547 }; // class pass_cse_reciprocals
550 pass_cse_reciprocals::execute (function
*fun
)
555 occ_pool
= create_alloc_pool ("dominators for recip",
556 sizeof (struct occurrence
),
557 n_basic_blocks_for_fn (fun
) / 3 + 1);
559 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
560 calculate_dominance_info (CDI_DOMINATORS
);
561 calculate_dominance_info (CDI_POST_DOMINATORS
);
563 #ifdef ENABLE_CHECKING
564 FOR_EACH_BB_FN (bb
, fun
)
565 gcc_assert (!bb
->aux
);
568 for (arg
= DECL_ARGUMENTS (fun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
569 if (FLOAT_TYPE_P (TREE_TYPE (arg
))
570 && is_gimple_reg (arg
))
572 tree name
= ssa_default_def (fun
, arg
);
574 execute_cse_reciprocals_1 (NULL
, name
);
577 FOR_EACH_BB_FN (bb
, fun
)
579 gimple_stmt_iterator gsi
;
583 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
585 phi
= gsi_stmt (gsi
);
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 (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
594 gimple stmt
= gsi_stmt (gsi
);
596 if (gimple_has_lhs (stmt
)
597 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
598 && FLOAT_TYPE_P (TREE_TYPE (def
))
599 && TREE_CODE (def
) == SSA_NAME
)
600 execute_cse_reciprocals_1 (&gsi
, def
);
603 if (optimize_bb_for_size_p (bb
))
606 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
607 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
609 gimple stmt
= gsi_stmt (gsi
);
612 if (is_gimple_assign (stmt
)
613 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
615 tree arg1
= gimple_assign_rhs2 (stmt
);
618 if (TREE_CODE (arg1
) != SSA_NAME
)
621 stmt1
= SSA_NAME_DEF_STMT (arg1
);
623 if (is_gimple_call (stmt1
)
624 && gimple_call_lhs (stmt1
)
625 && (fndecl
= gimple_call_fndecl (stmt1
))
626 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
627 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
629 enum built_in_function code
;
634 code
= DECL_FUNCTION_CODE (fndecl
);
635 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
637 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
641 /* Check that all uses of the SSA name are divisions,
642 otherwise replacing the defining statement will do
645 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
647 gimple stmt2
= USE_STMT (use_p
);
648 if (is_gimple_debug (stmt2
))
650 if (!is_gimple_assign (stmt2
)
651 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
652 || gimple_assign_rhs1 (stmt2
) == arg1
653 || gimple_assign_rhs2 (stmt2
) != arg1
)
662 gimple_replace_ssa_lhs (stmt1
, arg1
);
663 gimple_call_set_fndecl (stmt1
, fndecl
);
665 reciprocal_stats
.rfuncs_inserted
++;
667 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
669 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
670 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
671 fold_stmt_inplace (&gsi
);
679 statistics_counter_event (fun
, "reciprocal divs inserted",
680 reciprocal_stats
.rdivs_inserted
);
681 statistics_counter_event (fun
, "reciprocal functions inserted",
682 reciprocal_stats
.rfuncs_inserted
);
684 free_dominance_info (CDI_DOMINATORS
);
685 free_dominance_info (CDI_POST_DOMINATORS
);
686 free_alloc_pool (occ_pool
);
693 make_pass_cse_reciprocals (gcc::context
*ctxt
)
695 return new pass_cse_reciprocals (ctxt
);
698 /* Records an occurrence at statement USE_STMT in the vector of trees
699 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
700 is not yet initialized. Returns true if the occurrence was pushed on
701 the vector. Adjusts *TOP_BB to be the basic block dominating all
702 statements in the vector. */
705 maybe_record_sincos (vec
<gimple
> *stmts
,
706 basic_block
*top_bb
, gimple use_stmt
)
708 basic_block use_bb
= gimple_bb (use_stmt
);
710 && (*top_bb
== use_bb
711 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
712 stmts
->safe_push (use_stmt
);
714 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
716 stmts
->safe_push (use_stmt
);
725 /* Look for sin, cos and cexpi calls with the same argument NAME and
726 create a single call to cexpi CSEing the result in this case.
727 We first walk over all immediate uses of the argument collecting
728 statements that we can CSE in a vector and in a second pass replace
729 the statement rhs with a REALPART or IMAGPART expression on the
730 result of the cexpi call we insert before the use statement that
731 dominates all other candidates. */
734 execute_cse_sincos_1 (tree name
)
736 gimple_stmt_iterator gsi
;
737 imm_use_iterator use_iter
;
738 tree fndecl
, res
, type
;
739 gimple def_stmt
, use_stmt
, stmt
;
740 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
741 vec
<gimple
> stmts
= vNULL
;
742 basic_block top_bb
= NULL
;
744 bool cfg_changed
= false;
746 type
= TREE_TYPE (name
);
747 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
749 if (gimple_code (use_stmt
) != GIMPLE_CALL
750 || !gimple_call_lhs (use_stmt
)
751 || !(fndecl
= gimple_call_fndecl (use_stmt
))
752 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
755 switch (DECL_FUNCTION_CODE (fndecl
))
757 CASE_FLT_FN (BUILT_IN_COS
):
758 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
761 CASE_FLT_FN (BUILT_IN_SIN
):
762 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
765 CASE_FLT_FN (BUILT_IN_CEXPI
):
766 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
773 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
779 /* Simply insert cexpi at the beginning of top_bb but not earlier than
780 the name def statement. */
781 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
784 stmt
= gimple_build_call (fndecl
, 1, name
);
785 res
= make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl
)), stmt
, "sincostmp");
786 gimple_call_set_lhs (stmt
, res
);
788 def_stmt
= SSA_NAME_DEF_STMT (name
);
789 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
790 && gimple_code (def_stmt
) != GIMPLE_PHI
791 && gimple_bb (def_stmt
) == top_bb
)
793 gsi
= gsi_for_stmt (def_stmt
);
794 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
798 gsi
= gsi_after_labels (top_bb
);
799 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
801 sincos_stats
.inserted
++;
803 /* And adjust the recorded old call sites. */
804 for (i
= 0; stmts
.iterate (i
, &use_stmt
); ++i
)
807 fndecl
= gimple_call_fndecl (use_stmt
);
809 switch (DECL_FUNCTION_CODE (fndecl
))
811 CASE_FLT_FN (BUILT_IN_COS
):
812 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
815 CASE_FLT_FN (BUILT_IN_SIN
):
816 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
819 CASE_FLT_FN (BUILT_IN_CEXPI
):
827 /* Replace call with a copy. */
828 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
830 gsi
= gsi_for_stmt (use_stmt
);
831 gsi_replace (&gsi
, stmt
, true);
832 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
841 /* To evaluate powi(x,n), the floating point value x raised to the
842 constant integer exponent n, we use a hybrid algorithm that
843 combines the "window method" with look-up tables. For an
844 introduction to exponentiation algorithms and "addition chains",
845 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
846 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
847 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
848 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
850 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
851 multiplications to inline before calling the system library's pow
852 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
853 so this default never requires calling pow, powf or powl. */
855 #ifndef POWI_MAX_MULTS
856 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
859 /* The size of the "optimal power tree" lookup table. All
860 exponents less than this value are simply looked up in the
861 powi_table below. This threshold is also used to size the
862 cache of pseudo registers that hold intermediate results. */
863 #define POWI_TABLE_SIZE 256
865 /* The size, in bits of the window, used in the "window method"
866 exponentiation algorithm. This is equivalent to a radix of
867 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
868 #define POWI_WINDOW_SIZE 3
870 /* The following table is an efficient representation of an
871 "optimal power tree". For each value, i, the corresponding
872 value, j, in the table states than an optimal evaluation
873 sequence for calculating pow(x,i) can be found by evaluating
874 pow(x,j)*pow(x,i-j). An optimal power tree for the first
875 100 integers is given in Knuth's "Seminumerical algorithms". */
877 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
879 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
880 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
881 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
882 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
883 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
884 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
885 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
886 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
887 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
888 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
889 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
890 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
891 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
892 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
893 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
894 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
895 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
896 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
897 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
898 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
899 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
900 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
901 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
902 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
903 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
904 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
905 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
906 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
907 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
908 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
909 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
910 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
914 /* Return the number of multiplications required to calculate
915 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
916 subroutine of powi_cost. CACHE is an array indicating
917 which exponents have already been calculated. */
920 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
922 /* If we've already calculated this exponent, then this evaluation
923 doesn't require any additional multiplications. */
928 return powi_lookup_cost (n
- powi_table
[n
], cache
)
929 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
932 /* Return the number of multiplications required to calculate
933 powi(x,n) for an arbitrary x, given the exponent N. This
934 function needs to be kept in sync with powi_as_mults below. */
937 powi_cost (HOST_WIDE_INT n
)
939 bool cache
[POWI_TABLE_SIZE
];
940 unsigned HOST_WIDE_INT digit
;
941 unsigned HOST_WIDE_INT val
;
947 /* Ignore the reciprocal when calculating the cost. */
948 val
= (n
< 0) ? -n
: n
;
950 /* Initialize the exponent cache. */
951 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
956 while (val
>= POWI_TABLE_SIZE
)
960 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
961 result
+= powi_lookup_cost (digit
, cache
)
962 + POWI_WINDOW_SIZE
+ 1;
963 val
>>= POWI_WINDOW_SIZE
;
972 return result
+ powi_lookup_cost (val
, cache
);
975 /* Recursive subroutine of powi_as_mults. This function takes the
976 array, CACHE, of already calculated exponents and an exponent N and
977 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
980 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
981 HOST_WIDE_INT n
, tree
*cache
)
983 tree op0
, op1
, ssa_target
;
984 unsigned HOST_WIDE_INT digit
;
987 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
990 ssa_target
= make_temp_ssa_name (type
, NULL
, "powmult");
992 if (n
< POWI_TABLE_SIZE
)
994 cache
[n
] = ssa_target
;
995 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
);
996 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
);
1000 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
1001 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
);
1002 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
);
1006 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
);
1010 mult_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, ssa_target
, op0
, op1
);
1011 gimple_set_location (mult_stmt
, loc
);
1012 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
1017 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
1018 This function needs to be kept in sync with powi_cost above. */
1021 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
1022 tree arg0
, HOST_WIDE_INT n
)
1024 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
);
1029 return build_real (type
, dconst1
);
1031 memset (cache
, 0, sizeof (cache
));
1034 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
);
1038 /* If the original exponent was negative, reciprocate the result. */
1039 target
= make_temp_ssa_name (type
, NULL
, "powmult");
1040 div_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, target
,
1041 build_real (type
, dconst1
),
1043 gimple_set_location (div_stmt
, loc
);
1044 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1049 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1050 location info LOC. If the arguments are appropriate, create an
1051 equivalent sequence of statements prior to GSI using an optimal
1052 number of multiplications, and return an expession holding the
1056 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1057 tree arg0
, HOST_WIDE_INT n
)
1059 /* Avoid largest negative number. */
1061 && ((n
>= -1 && n
<= 2)
1062 || (optimize_function_for_speed_p (cfun
)
1063 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1064 return powi_as_mults (gsi
, loc
, arg0
, n
);
1069 /* Build a gimple call statement that calls FN with argument ARG.
1070 Set the lhs of the call statement to a fresh SSA name. Insert the
1071 statement prior to GSI's current position, and return the fresh
1075 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1081 call_stmt
= gimple_build_call (fn
, 1, arg
);
1082 ssa_target
= make_temp_ssa_name (TREE_TYPE (arg
), NULL
, "powroot");
1083 gimple_set_lhs (call_stmt
, ssa_target
);
1084 gimple_set_location (call_stmt
, loc
);
1085 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1090 /* Build a gimple binary operation with the given CODE and arguments
1091 ARG0, ARG1, assigning the result to a new SSA name for variable
1092 TARGET. Insert the statement prior to GSI's current position, and
1093 return the fresh SSA name.*/
1096 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1097 const char *name
, enum tree_code code
,
1098 tree arg0
, tree arg1
)
1100 tree result
= make_temp_ssa_name (TREE_TYPE (arg0
), NULL
, name
);
1101 gimple stmt
= gimple_build_assign_with_ops (code
, result
, arg0
, arg1
);
1102 gimple_set_location (stmt
, loc
);
1103 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1107 /* Build a gimple reference operation with the given CODE and argument
1108 ARG, assigning the result to a new SSA name of TYPE with NAME.
1109 Insert the statement prior to GSI's current position, and return
1110 the fresh SSA name. */
1113 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1114 const char *name
, enum tree_code code
, tree arg0
)
1116 tree result
= make_temp_ssa_name (type
, NULL
, name
);
1117 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1118 gimple_set_location (stmt
, loc
);
1119 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1123 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement
1124 prior to GSI's current position, and return the fresh SSA name. */
1127 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1128 tree type
, tree val
)
1130 tree result
= make_ssa_name (type
, NULL
);
1131 gimple stmt
= gimple_build_assign_with_ops (NOP_EXPR
, result
, val
, NULL_TREE
);
1132 gimple_set_location (stmt
, loc
);
1133 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1137 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1138 with location info LOC. If possible, create an equivalent and
1139 less expensive sequence of statements prior to GSI, and return an
1140 expession holding the result. */
1143 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1144 tree arg0
, tree arg1
)
1146 REAL_VALUE_TYPE c
, cint
, dconst1_4
, dconst3_4
, dconst1_3
, dconst1_6
;
1147 REAL_VALUE_TYPE c2
, dconst3
;
1149 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, sqrt_sqrt
, result
, cbrt_x
, powi_cbrt_x
;
1151 bool hw_sqrt_exists
, c_is_int
, c2_is_int
;
1153 /* If the exponent isn't a constant, there's nothing of interest
1155 if (TREE_CODE (arg1
) != REAL_CST
)
1158 /* If the exponent is equivalent to an integer, expand to an optimal
1159 multiplication sequence when profitable. */
1160 c
= TREE_REAL_CST (arg1
);
1161 n
= real_to_integer (&c
);
1162 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1163 c_is_int
= real_identical (&c
, &cint
);
1166 && ((n
>= -1 && n
<= 2)
1167 || (flag_unsafe_math_optimizations
1168 && optimize_bb_for_speed_p (gsi_bb (*gsi
))
1169 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1170 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1172 /* Attempt various optimizations using sqrt and cbrt. */
1173 type
= TREE_TYPE (arg0
);
1174 mode
= TYPE_MODE (type
);
1175 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1177 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1178 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1181 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1182 && !HONOR_SIGNED_ZEROS (mode
))
1183 return build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1185 /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
1186 a builtin sqrt instruction is smaller than a call to pow with 0.25,
1187 so do this optimization even if -Os. Don't do this optimization
1188 if we don't have a hardware sqrt insn. */
1189 dconst1_4
= dconst1
;
1190 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1191 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1193 if (flag_unsafe_math_optimizations
1195 && REAL_VALUES_EQUAL (c
, dconst1_4
)
1199 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1202 return build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1205 /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
1206 optimizing for space. Don't do this optimization if we don't have
1207 a hardware sqrt insn. */
1208 real_from_integer (&dconst3_4
, VOIDmode
, 3, SIGNED
);
1209 SET_REAL_EXP (&dconst3_4
, REAL_EXP (&dconst3_4
) - 2);
1211 if (flag_unsafe_math_optimizations
1213 && optimize_function_for_speed_p (cfun
)
1214 && REAL_VALUES_EQUAL (c
, dconst3_4
)
1218 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1221 sqrt_sqrt
= build_and_insert_call (gsi
, loc
, sqrtfn
, sqrt_arg0
);
1223 /* sqrt(x) * sqrt(sqrt(x)) */
1224 return build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1225 sqrt_arg0
, sqrt_sqrt
);
1228 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1229 optimizations since 1./3. is not exactly representable. If x
1230 is negative and finite, the correct value of pow(x,1./3.) is
1231 a NaN with the "invalid" exception raised, because the value
1232 of 1./3. actually has an even denominator. The correct value
1233 of cbrt(x) is a negative real value. */
1234 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1235 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1237 if (flag_unsafe_math_optimizations
1239 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1240 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1241 return build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1243 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1244 if we don't have a hardware sqrt insn. */
1245 dconst1_6
= dconst1_3
;
1246 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1248 if (flag_unsafe_math_optimizations
1251 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1252 && optimize_function_for_speed_p (cfun
)
1254 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1257 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1260 return build_and_insert_call (gsi
, loc
, cbrtfn
, sqrt_arg0
);
1263 /* Optimize pow(x,c), where n = 2c for some nonzero integer n
1264 and c not an integer, into
1266 sqrt(x) * powi(x, n/2), n > 0;
1267 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
1269 Do not calculate the powi factor when n/2 = 0. */
1270 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1271 n
= real_to_integer (&c2
);
1272 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1273 c2_is_int
= real_identical (&c2
, &cint
);
1275 if (flag_unsafe_math_optimizations
1279 && optimize_function_for_speed_p (cfun
))
1281 tree powi_x_ndiv2
= NULL_TREE
;
1283 /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
1284 possible or profitable, give up. Skip the degenerate case when
1285 n is 1 or -1, where the result is always 1. */
1286 if (absu_hwi (n
) != 1)
1288 powi_x_ndiv2
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1294 /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
1295 result of the optimal multiply sequence just calculated. */
1296 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1298 if (absu_hwi (n
) == 1)
1301 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1302 sqrt_arg0
, powi_x_ndiv2
);
1304 /* If n is negative, reciprocate the result. */
1306 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1307 build_real (type
, dconst1
), result
);
1311 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1313 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1314 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1316 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1317 different from pow(x, 1./3.) due to rounding and behavior with
1318 negative x, we need to constrain this transformation to unsafe
1319 math and positive x or finite math. */
1320 real_from_integer (&dconst3
, VOIDmode
, 3, SIGNED
);
1321 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1322 real_round (&c2
, mode
, &c2
);
1323 n
= real_to_integer (&c2
);
1324 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1325 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1326 real_convert (&c2
, mode
, &c2
);
1328 if (flag_unsafe_math_optimizations
1330 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1331 && real_identical (&c2
, &c
)
1333 && optimize_function_for_speed_p (cfun
)
1334 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1336 tree powi_x_ndiv3
= NULL_TREE
;
1338 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1339 possible or profitable, give up. Skip the degenerate case when
1340 abs(n) < 3, where the result is always 1. */
1341 if (absu_hwi (n
) >= 3)
1343 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1349 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1350 as that creates an unnecessary variable. Instead, just produce
1351 either cbrt(x) or cbrt(x) * cbrt(x). */
1352 cbrt_x
= build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1354 if (absu_hwi (n
) % 3 == 1)
1355 powi_cbrt_x
= cbrt_x
;
1357 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1360 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1361 if (absu_hwi (n
) < 3)
1362 result
= powi_cbrt_x
;
1364 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1365 powi_x_ndiv3
, powi_cbrt_x
);
1367 /* If n is negative, reciprocate the result. */
1369 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1370 build_real (type
, dconst1
), result
);
1375 /* No optimizations succeeded. */
1379 /* ARG is the argument to a cabs builtin call in GSI with location info
1380 LOC. Create a sequence of statements prior to GSI that calculates
1381 sqrt(R*R + I*I), where R and I are the real and imaginary components
1382 of ARG, respectively. Return an expression holding the result. */
1385 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1387 tree real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1388 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1389 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1390 machine_mode mode
= TYPE_MODE (type
);
1392 if (!flag_unsafe_math_optimizations
1393 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1395 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1398 real_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1399 REALPART_EXPR
, arg
);
1400 addend1
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1401 real_part
, real_part
);
1402 imag_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1403 IMAGPART_EXPR
, arg
);
1404 addend2
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1405 imag_part
, imag_part
);
1406 sum
= build_and_insert_binop (gsi
, loc
, "cabs", PLUS_EXPR
, addend1
, addend2
);
1407 result
= build_and_insert_call (gsi
, loc
, sqrtfn
, sum
);
1412 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1413 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1414 an optimal number of multiplies, when n is a constant. */
1418 const pass_data pass_data_cse_sincos
=
1420 GIMPLE_PASS
, /* type */
1421 "sincos", /* name */
1422 OPTGROUP_NONE
, /* optinfo_flags */
1423 TV_NONE
, /* tv_id */
1424 PROP_ssa
, /* properties_required */
1425 0, /* properties_provided */
1426 0, /* properties_destroyed */
1427 0, /* todo_flags_start */
1428 TODO_update_ssa
, /* todo_flags_finish */
1431 class pass_cse_sincos
: public gimple_opt_pass
1434 pass_cse_sincos (gcc::context
*ctxt
)
1435 : gimple_opt_pass (pass_data_cse_sincos
, ctxt
)
1438 /* opt_pass methods: */
1439 virtual bool gate (function
*)
1441 /* We no longer require either sincos or cexp, since powi expansion
1442 piggybacks on this pass. */
1446 virtual unsigned int execute (function
*);
1448 }; // class pass_cse_sincos
1451 pass_cse_sincos::execute (function
*fun
)
1454 bool cfg_changed
= false;
1456 calculate_dominance_info (CDI_DOMINATORS
);
1457 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1459 FOR_EACH_BB_FN (bb
, fun
)
1461 gimple_stmt_iterator gsi
;
1462 bool cleanup_eh
= false;
1464 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1466 gimple stmt
= gsi_stmt (gsi
);
1469 /* Only the last stmt in a bb could throw, no need to call
1470 gimple_purge_dead_eh_edges if we change something in the middle
1471 of a basic block. */
1474 if (is_gimple_call (stmt
)
1475 && gimple_call_lhs (stmt
)
1476 && (fndecl
= gimple_call_fndecl (stmt
))
1477 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1479 tree arg
, arg0
, arg1
, result
;
1483 switch (DECL_FUNCTION_CODE (fndecl
))
1485 CASE_FLT_FN (BUILT_IN_COS
):
1486 CASE_FLT_FN (BUILT_IN_SIN
):
1487 CASE_FLT_FN (BUILT_IN_CEXPI
):
1488 /* Make sure we have either sincos or cexp. */
1489 if (!targetm
.libc_has_function (function_c99_math_complex
)
1490 && !targetm
.libc_has_function (function_sincos
))
1493 arg
= gimple_call_arg (stmt
, 0);
1494 if (TREE_CODE (arg
) == SSA_NAME
)
1495 cfg_changed
|= execute_cse_sincos_1 (arg
);
1498 CASE_FLT_FN (BUILT_IN_POW
):
1499 arg0
= gimple_call_arg (stmt
, 0);
1500 arg1
= gimple_call_arg (stmt
, 1);
1502 loc
= gimple_location (stmt
);
1503 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1507 tree lhs
= gimple_get_lhs (stmt
);
1508 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1509 gimple_set_location (new_stmt
, loc
);
1510 unlink_stmt_vdef (stmt
);
1511 gsi_replace (&gsi
, new_stmt
, true);
1513 if (gimple_vdef (stmt
))
1514 release_ssa_name (gimple_vdef (stmt
));
1518 CASE_FLT_FN (BUILT_IN_POWI
):
1519 arg0
= gimple_call_arg (stmt
, 0);
1520 arg1
= gimple_call_arg (stmt
, 1);
1521 loc
= gimple_location (stmt
);
1523 if (real_minus_onep (arg0
))
1525 tree t0
, t1
, cond
, one
, minus_one
;
1528 t0
= TREE_TYPE (arg0
);
1529 t1
= TREE_TYPE (arg1
);
1530 one
= build_real (t0
, dconst1
);
1531 minus_one
= build_real (t0
, dconstm1
);
1533 cond
= make_temp_ssa_name (t1
, NULL
, "powi_cond");
1534 stmt
= gimple_build_assign_with_ops (BIT_AND_EXPR
, cond
,
1538 gimple_set_location (stmt
, loc
);
1539 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1541 result
= make_temp_ssa_name (t0
, NULL
, "powi");
1542 stmt
= gimple_build_assign_with_ops (COND_EXPR
, result
,
1545 gimple_set_location (stmt
, loc
);
1546 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1550 if (!tree_fits_shwi_p (arg1
))
1553 n
= tree_to_shwi (arg1
);
1554 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1559 tree lhs
= gimple_get_lhs (stmt
);
1560 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1561 gimple_set_location (new_stmt
, loc
);
1562 unlink_stmt_vdef (stmt
);
1563 gsi_replace (&gsi
, new_stmt
, true);
1565 if (gimple_vdef (stmt
))
1566 release_ssa_name (gimple_vdef (stmt
));
1570 CASE_FLT_FN (BUILT_IN_CABS
):
1571 arg0
= gimple_call_arg (stmt
, 0);
1572 loc
= gimple_location (stmt
);
1573 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1577 tree lhs
= gimple_get_lhs (stmt
);
1578 gimple new_stmt
= gimple_build_assign (lhs
, result
);
1579 gimple_set_location (new_stmt
, loc
);
1580 unlink_stmt_vdef (stmt
);
1581 gsi_replace (&gsi
, new_stmt
, true);
1583 if (gimple_vdef (stmt
))
1584 release_ssa_name (gimple_vdef (stmt
));
1593 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
1596 statistics_counter_event (fun
, "sincos statements inserted",
1597 sincos_stats
.inserted
);
1599 free_dominance_info (CDI_DOMINATORS
);
1600 return cfg_changed
? TODO_cleanup_cfg
: 0;
1606 make_pass_cse_sincos (gcc::context
*ctxt
)
1608 return new pass_cse_sincos (ctxt
);
1611 /* A symbolic number is used to detect byte permutation and selection
1612 patterns. Therefore the field N contains an artificial number
1613 consisting of octet sized markers:
1615 0 - target byte has the value 0
1616 FF - target byte has an unknown value (eg. due to sign extension)
1617 1..size - marker value is the target byte index minus one.
1619 To detect permutations on memory sources (arrays and structures), a symbolic
1620 number is also associated a base address (the array or structure the load is
1621 made from), an offset from the base address and a range which gives the
1622 difference between the highest and lowest accessed memory location to make
1623 such a symbolic number. The range is thus different from size which reflects
1624 the size of the type of current expression. Note that for non memory source,
1625 range holds the same value as size.
1627 For instance, for an array char a[], (short) a[0] | (short) a[3] would have
1628 a size of 2 but a range of 4 while (short) a[0] | ((short) a[0] << 1) would
1629 still have a size of 2 but this time a range of 1. */
1631 struct symbolic_number
{
1636 HOST_WIDE_INT bytepos
;
1639 unsigned HOST_WIDE_INT range
;
1642 #define BITS_PER_MARKER 8
1643 #define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
1644 #define MARKER_BYTE_UNKNOWN MARKER_MASK
1645 #define HEAD_MARKER(n, size) \
1646 ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
1648 /* The number which the find_bswap_or_nop_1 result should match in
1649 order to have a nop. The number is masked according to the size of
1650 the symbolic number before using it. */
1651 #define CMPNOP (sizeof (int64_t) < 8 ? 0 : \
1652 (uint64_t)0x08070605 << 32 | 0x04030201)
1654 /* The number which the find_bswap_or_nop_1 result should match in
1655 order to have a byte swap. The number is masked according to the
1656 size of the symbolic number before using it. */
1657 #define CMPXCHG (sizeof (int64_t) < 8 ? 0 : \
1658 (uint64_t)0x01020304 << 32 | 0x05060708)
1660 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1661 number N. Return false if the requested operation is not permitted
1662 on a symbolic number. */
1665 do_shift_rotate (enum tree_code code
,
1666 struct symbolic_number
*n
,
1669 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1670 unsigned head_marker
;
1672 if (count
% BITS_PER_UNIT
!= 0)
1674 count
= (count
/ BITS_PER_UNIT
) * BITS_PER_MARKER
;
1676 /* Zero out the extra bits of N in order to avoid them being shifted
1677 into the significant bits. */
1678 if (size
< 64 / BITS_PER_MARKER
)
1679 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1687 head_marker
= HEAD_MARKER (n
->n
, size
);
1689 /* Arithmetic shift of signed type: result is dependent on the value. */
1690 if (!TYPE_UNSIGNED (n
->type
) && head_marker
)
1691 for (i
= 0; i
< count
/ BITS_PER_MARKER
; i
++)
1692 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
1693 << ((size
- 1 - i
) * BITS_PER_MARKER
);
1696 n
->n
= (n
->n
<< count
) | (n
->n
>> ((size
* BITS_PER_MARKER
) - count
));
1699 n
->n
= (n
->n
>> count
) | (n
->n
<< ((size
* BITS_PER_MARKER
) - count
));
1704 /* Zero unused bits for size. */
1705 if (size
< 64 / BITS_PER_MARKER
)
1706 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1710 /* Perform sanity checking for the symbolic number N and the gimple
1714 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
1718 lhs_type
= gimple_expr_type (stmt
);
1720 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
1723 if (TYPE_PRECISION (lhs_type
) != TYPE_PRECISION (n
->type
))
1729 /* Initialize the symbolic number N for the bswap pass from the base element
1730 SRC manipulated by the bitwise OR expression. */
1733 init_symbolic_number (struct symbolic_number
*n
, tree src
)
1737 n
->base_addr
= n
->offset
= n
->alias_set
= n
->vuse
= NULL_TREE
;
1739 /* Set up the symbolic number N by setting each byte to a value between 1 and
1740 the byte size of rhs1. The highest order byte is set to n->size and the
1741 lowest order byte to 1. */
1742 n
->type
= TREE_TYPE (src
);
1743 size
= TYPE_PRECISION (n
->type
);
1744 if (size
% BITS_PER_UNIT
!= 0)
1746 size
/= BITS_PER_UNIT
;
1747 if (size
> 64 / BITS_PER_MARKER
)
1752 if (size
< 64 / BITS_PER_MARKER
)
1753 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1758 /* Check if STMT might be a byte swap or a nop from a memory source and returns
1759 the answer. If so, REF is that memory source and the base of the memory area
1760 accessed and the offset of the access from that base are recorded in N. */
1763 find_bswap_or_nop_load (gimple stmt
, tree ref
, struct symbolic_number
*n
)
1765 /* Leaf node is an array or component ref. Memorize its base and
1766 offset from base to compare to other such leaf node. */
1767 HOST_WIDE_INT bitsize
, bitpos
;
1769 int unsignedp
, volatilep
;
1770 tree offset
, base_addr
;
1772 if (!gimple_assign_load_p (stmt
) || gimple_has_volatile_ops (stmt
))
1775 base_addr
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
1776 &unsignedp
, &volatilep
, false);
1778 if (TREE_CODE (base_addr
) == MEM_REF
)
1780 offset_int bit_offset
= 0;
1781 tree off
= TREE_OPERAND (base_addr
, 1);
1783 if (!integer_zerop (off
))
1785 offset_int boff
, coff
= mem_ref_offset (base_addr
);
1786 boff
= wi::lshift (coff
, LOG2_BITS_PER_UNIT
);
1790 base_addr
= TREE_OPERAND (base_addr
, 0);
1792 /* Avoid returning a negative bitpos as this may wreak havoc later. */
1793 if (wi::neg_p (bit_offset
))
1795 offset_int mask
= wi::mask
<offset_int
> (LOG2_BITS_PER_UNIT
, false);
1796 offset_int tem
= bit_offset
.and_not (mask
);
1797 /* TEM is the bitpos rounded to BITS_PER_UNIT towards -Inf.
1798 Subtract it to BIT_OFFSET and add it (scaled) to OFFSET. */
1800 tem
= wi::arshift (tem
, LOG2_BITS_PER_UNIT
);
1802 offset
= size_binop (PLUS_EXPR
, offset
,
1803 wide_int_to_tree (sizetype
, tem
));
1805 offset
= wide_int_to_tree (sizetype
, tem
);
1808 bitpos
+= bit_offset
.to_shwi ();
1811 if (bitpos
% BITS_PER_UNIT
)
1813 if (bitsize
% BITS_PER_UNIT
)
1816 if (!init_symbolic_number (n
, ref
))
1818 n
->base_addr
= base_addr
;
1820 n
->bytepos
= bitpos
/ BITS_PER_UNIT
;
1821 n
->alias_set
= reference_alias_ptr_type (ref
);
1822 n
->vuse
= gimple_vuse (stmt
);
1826 /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
1827 the operation given by the rhs of STMT on the result. If the operation
1828 could successfully be executed the function returns a gimple stmt whose
1829 rhs's first tree is the expression of the source operand and NULL
1833 find_bswap_or_nop_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
1835 enum tree_code code
;
1836 tree rhs1
, rhs2
= NULL
;
1837 gimple rhs1_stmt
, rhs2_stmt
, source_stmt1
;
1838 enum gimple_rhs_class rhs_class
;
1840 if (!limit
|| !is_gimple_assign (stmt
))
1843 rhs1
= gimple_assign_rhs1 (stmt
);
1845 if (find_bswap_or_nop_load (stmt
, rhs1
, n
))
1848 if (TREE_CODE (rhs1
) != SSA_NAME
)
1851 code
= gimple_assign_rhs_code (stmt
);
1852 rhs_class
= gimple_assign_rhs_class (stmt
);
1853 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
1855 if (rhs_class
== GIMPLE_BINARY_RHS
)
1856 rhs2
= gimple_assign_rhs2 (stmt
);
1858 /* Handle unary rhs and binary rhs with integer constants as second
1861 if (rhs_class
== GIMPLE_UNARY_RHS
1862 || (rhs_class
== GIMPLE_BINARY_RHS
1863 && TREE_CODE (rhs2
) == INTEGER_CST
))
1865 if (code
!= BIT_AND_EXPR
1866 && code
!= LSHIFT_EXPR
1867 && code
!= RSHIFT_EXPR
1868 && code
!= LROTATE_EXPR
1869 && code
!= RROTATE_EXPR
1871 && code
!= CONVERT_EXPR
)
1874 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, n
, limit
- 1);
1876 /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
1877 we have to initialize the symbolic number. */
1880 if (gimple_assign_load_p (stmt
)
1881 || !init_symbolic_number (n
, rhs1
))
1883 source_stmt1
= stmt
;
1890 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1891 uint64_t val
= int_cst_value (rhs2
), mask
= 0;
1892 uint64_t tmp
= (1 << BITS_PER_UNIT
) - 1;
1894 /* Only constants masking full bytes are allowed. */
1895 for (i
= 0; i
< size
; i
++, tmp
<<= BITS_PER_UNIT
)
1896 if ((val
& tmp
) != 0 && (val
& tmp
) != tmp
)
1899 mask
|= (uint64_t) MARKER_MASK
<< (i
* BITS_PER_MARKER
);
1908 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
1913 int i
, type_size
, old_type_size
;
1916 type
= gimple_expr_type (stmt
);
1917 type_size
= TYPE_PRECISION (type
);
1918 if (type_size
% BITS_PER_UNIT
!= 0)
1920 type_size
/= BITS_PER_UNIT
;
1921 if (type_size
> 64 / BITS_PER_MARKER
)
1924 /* Sign extension: result is dependent on the value. */
1925 old_type_size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1926 if (!TYPE_UNSIGNED (n
->type
) && type_size
> old_type_size
1927 && HEAD_MARKER (n
->n
, old_type_size
))
1928 for (i
= 0; i
< type_size
- old_type_size
; i
++)
1929 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
1930 << ((type_size
- 1 - i
) * BITS_PER_MARKER
);
1932 if (type_size
< 64 / BITS_PER_MARKER
)
1934 /* If STMT casts to a smaller type mask out the bits not
1935 belonging to the target type. */
1936 n
->n
&= ((uint64_t) 1 << (type_size
* BITS_PER_MARKER
)) - 1;
1940 n
->range
= type_size
;
1946 return verify_symbolic_number_p (n
, stmt
) ? source_stmt1
: NULL
;
1949 /* Handle binary rhs. */
1951 if (rhs_class
== GIMPLE_BINARY_RHS
)
1954 struct symbolic_number n1
, n2
;
1956 gimple source_stmt2
;
1958 if (code
!= BIT_IOR_EXPR
)
1961 if (TREE_CODE (rhs2
) != SSA_NAME
)
1964 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1969 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, &n1
, limit
- 1);
1974 source_stmt2
= find_bswap_or_nop_1 (rhs2_stmt
, &n2
, limit
- 1);
1979 if (TYPE_PRECISION (n1
.type
) != TYPE_PRECISION (n2
.type
))
1982 if (!n1
.vuse
!= !n2
.vuse
||
1983 (n1
.vuse
&& !operand_equal_p (n1
.vuse
, n2
.vuse
, 0)))
1986 if (gimple_assign_rhs1 (source_stmt1
)
1987 != gimple_assign_rhs1 (source_stmt2
))
1990 HOST_WIDE_INT off_sub
;
1991 struct symbolic_number
*n_ptr
;
1993 if (!n1
.base_addr
|| !n2
.base_addr
1994 || !operand_equal_p (n1
.base_addr
, n2
.base_addr
, 0))
1996 if (!n1
.offset
!= !n2
.offset
||
1997 (n1
.offset
&& !operand_equal_p (n1
.offset
, n2
.offset
, 0)))
2000 /* We swap n1 with n2 to have n1 < n2. */
2001 if (n2
.bytepos
< n1
.bytepos
)
2003 struct symbolic_number tmpn
;
2008 source_stmt1
= source_stmt2
;
2011 off_sub
= n2
.bytepos
- n1
.bytepos
;
2013 /* Check that the range of memory covered can be represented by
2014 a symbolic number. */
2015 if (off_sub
+ n2
.range
> 64 / BITS_PER_MARKER
)
2017 n
->range
= n2
.range
+ off_sub
;
2019 /* Reinterpret byte marks in symbolic number holding the value of
2020 bigger weight according to target endianness. */
2021 inc
= BYTES_BIG_ENDIAN
? off_sub
+ n2
.range
- n1
.range
: off_sub
;
2022 size
= TYPE_PRECISION (n1
.type
) / BITS_PER_UNIT
;
2023 if (BYTES_BIG_ENDIAN
)
2027 for (i
= 0; i
< size
; i
++, inc
<<= BITS_PER_MARKER
)
2030 (n_ptr
->n
>> (i
* BITS_PER_MARKER
)) & MARKER_MASK
;
2031 if (marker
&& marker
!= MARKER_BYTE_UNKNOWN
)
2036 n
->range
= n1
.range
;
2039 || alias_ptr_types_compatible_p (n1
.alias_set
, n2
.alias_set
))
2040 n
->alias_set
= n1
.alias_set
;
2042 n
->alias_set
= ptr_type_node
;
2044 n
->base_addr
= n1
.base_addr
;
2045 n
->offset
= n1
.offset
;
2046 n
->bytepos
= n1
.bytepos
;
2048 size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
2049 for (i
= 0, mask
= MARKER_MASK
; i
< size
;
2050 i
++, mask
<<= BITS_PER_MARKER
)
2052 uint64_t masked1
, masked2
;
2054 masked1
= n1
.n
& mask
;
2055 masked2
= n2
.n
& mask
;
2056 if (masked1
&& masked2
&& masked1
!= masked2
)
2061 if (!verify_symbolic_number_p (n
, stmt
))
2068 return source_stmt1
;
2073 /* Check if STMT completes a bswap implementation or a read in a given
2074 endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
2075 accordingly. It also sets N to represent the kind of operations
2076 performed: size of the resulting expression and whether it works on
2077 a memory source, and if so alias-set and vuse. At last, the
2078 function returns a stmt whose rhs's first tree is the source
2082 find_bswap_or_nop (gimple stmt
, struct symbolic_number
*n
, bool *bswap
)
2084 /* The number which the find_bswap_or_nop_1 result should match in order
2085 to have a full byte swap. The number is shifted to the right
2086 according to the size of the symbolic number before using it. */
2087 uint64_t cmpxchg
= CMPXCHG
;
2088 uint64_t cmpnop
= CMPNOP
;
2093 /* The last parameter determines the depth search limit. It usually
2094 correlates directly to the number n of bytes to be touched. We
2095 increase that number by log2(n) + 1 here in order to also
2096 cover signed -> unsigned conversions of the src operand as can be seen
2097 in libgcc, and for initial shift/and operation of the src operand. */
2098 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
2099 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
2100 source_stmt
= find_bswap_or_nop_1 (stmt
, n
, limit
);
2105 /* Find real size of result (highest non zero byte). */
2111 for (tmpn
= n
->n
, rsize
= 0; tmpn
; tmpn
>>= BITS_PER_MARKER
, rsize
++);
2115 /* Zero out the extra bits of N and CMP*. */
2116 if (n
->range
< (int) sizeof (int64_t))
2120 mask
= ((uint64_t) 1 << (n
->range
* BITS_PER_MARKER
)) - 1;
2121 cmpxchg
>>= (64 / BITS_PER_MARKER
- n
->range
) * BITS_PER_MARKER
;
2125 /* A complete byte swap should make the symbolic number to start with
2126 the largest digit in the highest order byte. Unchanged symbolic
2127 number indicates a read with same endianness as target architecture. */
2130 else if (n
->n
== cmpxchg
)
2135 /* Useless bit manipulation performed by code. */
2136 if (!n
->base_addr
&& n
->n
== cmpnop
)
2139 n
->range
*= BITS_PER_UNIT
;
2145 const pass_data pass_data_optimize_bswap
=
2147 GIMPLE_PASS
, /* type */
2149 OPTGROUP_NONE
, /* optinfo_flags */
2150 TV_NONE
, /* tv_id */
2151 PROP_ssa
, /* properties_required */
2152 0, /* properties_provided */
2153 0, /* properties_destroyed */
2154 0, /* todo_flags_start */
2155 0, /* todo_flags_finish */
2158 class pass_optimize_bswap
: public gimple_opt_pass
2161 pass_optimize_bswap (gcc::context
*ctxt
)
2162 : gimple_opt_pass (pass_data_optimize_bswap
, ctxt
)
2165 /* opt_pass methods: */
2166 virtual bool gate (function
*)
2168 return flag_expensive_optimizations
&& optimize
;
2171 virtual unsigned int execute (function
*);
2173 }; // class pass_optimize_bswap
2175 /* Perform the bswap optimization: replace the statement CUR_STMT at
2176 GSI with a load of type, VUSE and set-alias as described by N if a
2177 memory source is involved (N->base_addr is non null), followed by
2178 the builtin bswap invocation in FNDECL if BSWAP is true. SRC_STMT
2179 gives where should the replacement be made. It also gives the
2180 source on which CUR_STMT is operating via its rhs's first tree nad
2181 N->range gives the size of the expression involved for maintaining
2185 bswap_replace (gimple cur_stmt
, gimple_stmt_iterator gsi
, gimple src_stmt
,
2186 tree fndecl
, tree bswap_type
, tree load_type
,
2187 struct symbolic_number
*n
, bool bswap
)
2192 src
= gimple_assign_rhs1 (src_stmt
);
2193 tgt
= gimple_assign_lhs (cur_stmt
);
2195 /* Need to load the value from memory first. */
2198 gimple_stmt_iterator gsi_ins
= gsi_for_stmt (src_stmt
);
2199 tree addr_expr
, addr_tmp
, val_expr
, val_tmp
;
2200 tree load_offset_ptr
, aligned_load_type
;
2201 gimple addr_stmt
, load_stmt
;
2204 align
= get_object_alignment (src
);
2206 && align
< GET_MODE_ALIGNMENT (TYPE_MODE (load_type
))
2207 && SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type
), align
))
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_1 (&gsi
, NOP_EXPR
, val_tmp
,
2255 NULL_TREE
, NULL_TREE
);
2259 gimple_assign_set_rhs_with_ops_1 (&gsi
, MEM_REF
, val_expr
,
2260 NULL_TREE
, NULL_TREE
);
2261 gimple_set_vuse (cur_stmt
, n
->vuse
);
2263 update_stmt (cur_stmt
);
2268 "%d bit load in target endianness found at: ",
2270 print_gimple_stmt (dump_file
, cur_stmt
, 0, 0);
2276 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
, "load_dst");
2277 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2278 gimple_set_vuse (load_stmt
, n
->vuse
);
2279 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
2285 bswap_stats
.found_16bit
++;
2286 else if (n
->range
== 32)
2287 bswap_stats
.found_32bit
++;
2290 gcc_assert (n
->range
== 64);
2291 bswap_stats
.found_64bit
++;
2296 /* Canonical form for 16 bit bswap is a rotate expression. */
2297 if (bswap
&& n
->range
== 16)
2299 tree count
= build_int_cst (NULL
, BITS_PER_UNIT
);
2300 bswap_type
= TREE_TYPE (src
);
2301 src
= fold_build2 (LROTATE_EXPR
, bswap_type
, src
, count
);
2302 bswap_stmt
= gimple_build_assign (NULL
, src
);
2306 /* Convert the src expression if necessary. */
2307 if (!useless_type_conversion_p (TREE_TYPE (tmp
), bswap_type
))
2309 gimple convert_stmt
;
2310 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
2311 convert_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, tmp
, 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_with_ops (NOP_EXPR
, tgt
, tmp
, NULL
);
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 bswap16_p
, bswap32_p
, bswap64_p
;
2354 bool changed
= false;
2355 tree bswap16_type
= NULL_TREE
, bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
2357 if (BITS_PER_UNIT
!= 8)
2360 bswap16_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP16
)
2361 && optab_handler (bswap_optab
, HImode
) != CODE_FOR_nothing
);
2362 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
2363 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
2364 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
2365 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
2366 || (bswap32_p
&& word_mode
== SImode
)));
2368 /* Determine the argument type of the builtins. The code later on
2369 assumes that the return and argument type are the same. */
2372 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
2373 bswap16_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2378 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2379 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2384 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2385 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2388 memset (&nop_stats
, 0, sizeof (nop_stats
));
2389 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
2391 FOR_EACH_BB_FN (bb
, fun
)
2393 gimple_stmt_iterator gsi
;
2395 /* We do a reverse scan for bswap patterns to make sure we get the
2396 widest match. As bswap pattern matching doesn't handle
2397 previously inserted smaller bswap replacements as sub-
2398 patterns, the wider variant wouldn't be detected. */
2399 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
); gsi_prev (&gsi
))
2401 gimple src_stmt
, cur_stmt
= gsi_stmt (gsi
);
2402 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
, load_type
;
2403 enum tree_code code
;
2404 struct symbolic_number n
;
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 load_type
= uint16_type_node
;
2437 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP16
);
2438 bswap_type
= bswap16_type
;
2442 load_type
= uint32_type_node
;
2445 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2446 bswap_type
= bswap32_type
;
2450 load_type
= uint64_type_node
;
2453 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2454 bswap_type
= bswap64_type
;
2461 if (bswap
&& !fndecl
)
2464 if (bswap_replace (cur_stmt
, gsi
, src_stmt
, fndecl
, bswap_type
,
2465 load_type
, &n
, bswap
))
2470 statistics_counter_event (fun
, "16-bit nop implementations found",
2471 nop_stats
.found_16bit
);
2472 statistics_counter_event (fun
, "32-bit nop implementations found",
2473 nop_stats
.found_32bit
);
2474 statistics_counter_event (fun
, "64-bit nop implementations found",
2475 nop_stats
.found_64bit
);
2476 statistics_counter_event (fun
, "16-bit bswap implementations found",
2477 bswap_stats
.found_16bit
);
2478 statistics_counter_event (fun
, "32-bit bswap implementations found",
2479 bswap_stats
.found_32bit
);
2480 statistics_counter_event (fun
, "64-bit bswap implementations found",
2481 bswap_stats
.found_64bit
);
2483 return (changed
? TODO_update_ssa
: 0);
2489 make_pass_optimize_bswap (gcc::context
*ctxt
)
2491 return new pass_optimize_bswap (ctxt
);
2494 /* Return true if stmt is a type conversion operation that can be stripped
2495 when used in a widening multiply operation. */
2497 widening_mult_conversion_strippable_p (tree result_type
, gimple stmt
)
2499 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2501 if (TREE_CODE (result_type
) == INTEGER_TYPE
)
2506 if (!CONVERT_EXPR_CODE_P (rhs_code
))
2509 op_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2511 /* If the type of OP has the same precision as the result, then
2512 we can strip this conversion. The multiply operation will be
2513 selected to create the correct extension as a by-product. */
2514 if (TYPE_PRECISION (result_type
) == TYPE_PRECISION (op_type
))
2517 /* We can also strip a conversion if it preserves the signed-ness of
2518 the operation and doesn't narrow the range. */
2519 inner_op_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
2521 /* If the inner-most type is unsigned, then we can strip any
2522 intermediate widening operation. If it's signed, then the
2523 intermediate widening operation must also be signed. */
2524 if ((TYPE_UNSIGNED (inner_op_type
)
2525 || TYPE_UNSIGNED (op_type
) == TYPE_UNSIGNED (inner_op_type
))
2526 && TYPE_PRECISION (op_type
) > TYPE_PRECISION (inner_op_type
))
2532 return rhs_code
== FIXED_CONVERT_EXPR
;
2535 /* Return true if RHS is a suitable operand for a widening multiplication,
2536 assuming a target type of TYPE.
2537 There are two cases:
2539 - RHS makes some value at least twice as wide. Store that value
2540 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
2542 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
2543 but leave *TYPE_OUT untouched. */
2546 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
2552 if (TREE_CODE (rhs
) == SSA_NAME
)
2554 stmt
= SSA_NAME_DEF_STMT (rhs
);
2555 if (is_gimple_assign (stmt
))
2557 if (! widening_mult_conversion_strippable_p (type
, stmt
))
2561 rhs1
= gimple_assign_rhs1 (stmt
);
2563 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2565 *new_rhs_out
= rhs1
;
2574 type1
= TREE_TYPE (rhs1
);
2576 if (TREE_CODE (type1
) != TREE_CODE (type
)
2577 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2580 *new_rhs_out
= rhs1
;
2585 if (TREE_CODE (rhs
) == INTEGER_CST
)
2595 /* Return true if STMT performs a widening multiplication, assuming the
2596 output type is TYPE. If so, store the unwidened types of the operands
2597 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2598 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2599 and *TYPE2_OUT would give the operands of the multiplication. */
2602 is_widening_mult_p (gimple stmt
,
2603 tree
*type1_out
, tree
*rhs1_out
,
2604 tree
*type2_out
, tree
*rhs2_out
)
2606 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2608 if (TREE_CODE (type
) != INTEGER_TYPE
2609 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2612 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2616 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2620 if (*type1_out
== NULL
)
2622 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
2624 *type1_out
= *type2_out
;
2627 if (*type2_out
== NULL
)
2629 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
2631 *type2_out
= *type1_out
;
2634 /* Ensure that the larger of the two operands comes first. */
2635 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
2639 *type1_out
= *type2_out
;
2642 *rhs1_out
= *rhs2_out
;
2649 /* Process a single gimple statement STMT, which has a MULT_EXPR as
2650 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
2651 value is true iff we converted the statement. */
2654 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
2656 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
2657 enum insn_code handler
;
2658 machine_mode to_mode
, from_mode
, actual_mode
;
2660 int actual_precision
;
2661 location_t loc
= gimple_location (stmt
);
2662 bool from_unsigned1
, from_unsigned2
;
2664 lhs
= gimple_assign_lhs (stmt
);
2665 type
= TREE_TYPE (lhs
);
2666 if (TREE_CODE (type
) != INTEGER_TYPE
)
2669 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
2672 to_mode
= TYPE_MODE (type
);
2673 from_mode
= TYPE_MODE (type1
);
2674 from_unsigned1
= TYPE_UNSIGNED (type1
);
2675 from_unsigned2
= TYPE_UNSIGNED (type2
);
2677 if (from_unsigned1
&& from_unsigned2
)
2678 op
= umul_widen_optab
;
2679 else if (!from_unsigned1
&& !from_unsigned2
)
2680 op
= smul_widen_optab
;
2682 op
= usmul_widen_optab
;
2684 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
2687 if (handler
== CODE_FOR_nothing
)
2689 if (op
!= smul_widen_optab
)
2691 /* We can use a signed multiply with unsigned types as long as
2692 there is a wider mode to use, or it is the smaller of the two
2693 types that is unsigned. Note that type1 >= type2, always. */
2694 if ((TYPE_UNSIGNED (type1
)
2695 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2696 || (TYPE_UNSIGNED (type2
)
2697 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2699 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2700 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
2704 op
= smul_widen_optab
;
2705 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
2709 if (handler
== CODE_FOR_nothing
)
2712 from_unsigned1
= from_unsigned2
= false;
2718 /* Ensure that the inputs to the handler are in the correct precison
2719 for the opcode. This will be the full mode size. */
2720 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2721 if (2 * actual_precision
> TYPE_PRECISION (type
))
2723 if (actual_precision
!= TYPE_PRECISION (type1
)
2724 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2725 rhs1
= build_and_insert_cast (gsi
, loc
,
2726 build_nonstandard_integer_type
2727 (actual_precision
, from_unsigned1
), rhs1
);
2728 if (actual_precision
!= TYPE_PRECISION (type2
)
2729 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2730 rhs2
= build_and_insert_cast (gsi
, loc
,
2731 build_nonstandard_integer_type
2732 (actual_precision
, from_unsigned2
), rhs2
);
2734 /* Handle constants. */
2735 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2736 rhs1
= fold_convert (type1
, rhs1
);
2737 if (TREE_CODE (rhs2
) == INTEGER_CST
)
2738 rhs2
= fold_convert (type2
, rhs2
);
2740 gimple_assign_set_rhs1 (stmt
, rhs1
);
2741 gimple_assign_set_rhs2 (stmt
, rhs2
);
2742 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
2744 widen_mul_stats
.widen_mults_inserted
++;
2748 /* Process a single gimple statement STMT, which is found at the
2749 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
2750 rhs (given by CODE), and try to convert it into a
2751 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
2752 is true iff we converted the statement. */
2755 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
2756 enum tree_code code
)
2758 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
2759 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
2760 tree type
, type1
, type2
, optype
;
2761 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
2762 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
2764 enum tree_code wmult_code
;
2765 enum insn_code handler
;
2766 machine_mode to_mode
, from_mode
, actual_mode
;
2767 location_t loc
= gimple_location (stmt
);
2768 int actual_precision
;
2769 bool from_unsigned1
, from_unsigned2
;
2771 lhs
= gimple_assign_lhs (stmt
);
2772 type
= TREE_TYPE (lhs
);
2773 if (TREE_CODE (type
) != INTEGER_TYPE
2774 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2777 if (code
== MINUS_EXPR
)
2778 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
2780 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
2782 rhs1
= gimple_assign_rhs1 (stmt
);
2783 rhs2
= gimple_assign_rhs2 (stmt
);
2785 if (TREE_CODE (rhs1
) == SSA_NAME
)
2787 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2788 if (is_gimple_assign (rhs1_stmt
))
2789 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2792 if (TREE_CODE (rhs2
) == SSA_NAME
)
2794 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2795 if (is_gimple_assign (rhs2_stmt
))
2796 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2799 /* Allow for one conversion statement between the multiply
2800 and addition/subtraction statement. If there are more than
2801 one conversions then we assume they would invalidate this
2802 transformation. If that's not the case then they should have
2803 been folded before now. */
2804 if (CONVERT_EXPR_CODE_P (rhs1_code
))
2806 conv1_stmt
= rhs1_stmt
;
2807 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
2808 if (TREE_CODE (rhs1
) == SSA_NAME
)
2810 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2811 if (is_gimple_assign (rhs1_stmt
))
2812 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
2817 if (CONVERT_EXPR_CODE_P (rhs2_code
))
2819 conv2_stmt
= rhs2_stmt
;
2820 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
2821 if (TREE_CODE (rhs2
) == SSA_NAME
)
2823 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2824 if (is_gimple_assign (rhs2_stmt
))
2825 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
2831 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
2832 is_widening_mult_p, but we still need the rhs returns.
2834 It might also appear that it would be sufficient to use the existing
2835 operands of the widening multiply, but that would limit the choice of
2836 multiply-and-accumulate instructions.
2838 If the widened-multiplication result has more than one uses, it is
2839 probably wiser not to do the conversion. */
2840 if (code
== PLUS_EXPR
2841 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
2843 if (!has_single_use (rhs1
)
2844 || !is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
2845 &type2
, &mult_rhs2
))
2848 conv_stmt
= conv1_stmt
;
2850 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
2852 if (!has_single_use (rhs2
)
2853 || !is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
2854 &type2
, &mult_rhs2
))
2857 conv_stmt
= conv2_stmt
;
2862 to_mode
= TYPE_MODE (type
);
2863 from_mode
= TYPE_MODE (type1
);
2864 from_unsigned1
= TYPE_UNSIGNED (type1
);
2865 from_unsigned2
= TYPE_UNSIGNED (type2
);
2868 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
2869 if (from_unsigned1
!= from_unsigned2
)
2871 if (!INTEGRAL_TYPE_P (type
))
2873 /* We can use a signed multiply with unsigned types as long as
2874 there is a wider mode to use, or it is the smaller of the two
2875 types that is unsigned. Note that type1 >= type2, always. */
2877 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
2879 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
2881 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
2882 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
2886 from_unsigned1
= from_unsigned2
= false;
2887 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
2891 /* If there was a conversion between the multiply and addition
2892 then we need to make sure it fits a multiply-and-accumulate.
2893 The should be a single mode change which does not change the
2897 /* We use the original, unmodified data types for this. */
2898 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
2899 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
2900 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
2901 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
2903 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
2905 /* Conversion is a truncate. */
2906 if (TYPE_PRECISION (to_type
) < data_size
)
2909 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
2911 /* Conversion is an extend. Check it's the right sort. */
2912 if (TYPE_UNSIGNED (from_type
) != is_unsigned
2913 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
2916 /* else convert is a no-op for our purposes. */
2919 /* Verify that the machine can perform a widening multiply
2920 accumulate in this mode/signedness combination, otherwise
2921 this transformation is likely to pessimize code. */
2922 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
2923 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
2924 from_mode
, 0, &actual_mode
);
2926 if (handler
== CODE_FOR_nothing
)
2929 /* Ensure that the inputs to the handler are in the correct precison
2930 for the opcode. This will be the full mode size. */
2931 actual_precision
= GET_MODE_PRECISION (actual_mode
);
2932 if (actual_precision
!= TYPE_PRECISION (type1
)
2933 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
2934 mult_rhs1
= build_and_insert_cast (gsi
, loc
,
2935 build_nonstandard_integer_type
2936 (actual_precision
, from_unsigned1
),
2938 if (actual_precision
!= TYPE_PRECISION (type2
)
2939 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
2940 mult_rhs2
= build_and_insert_cast (gsi
, loc
,
2941 build_nonstandard_integer_type
2942 (actual_precision
, from_unsigned2
),
2945 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
2946 add_rhs
= build_and_insert_cast (gsi
, loc
, type
, add_rhs
);
2948 /* Handle constants. */
2949 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
2950 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
2951 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
2952 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
2954 gimple_assign_set_rhs_with_ops_1 (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
2956 update_stmt (gsi_stmt (*gsi
));
2957 widen_mul_stats
.maccs_inserted
++;
2961 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
2962 with uses in additions and subtractions to form fused multiply-add
2963 operations. Returns true if successful and MUL_STMT should be removed. */
2966 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
2968 tree mul_result
= gimple_get_lhs (mul_stmt
);
2969 tree type
= TREE_TYPE (mul_result
);
2970 gimple use_stmt
, neguse_stmt
, fma_stmt
;
2971 use_operand_p use_p
;
2972 imm_use_iterator imm_iter
;
2974 if (FLOAT_TYPE_P (type
)
2975 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
2978 /* We don't want to do bitfield reduction ops. */
2979 if (INTEGRAL_TYPE_P (type
)
2980 && (TYPE_PRECISION (type
)
2981 != GET_MODE_PRECISION (TYPE_MODE (type
))))
2984 /* If the target doesn't support it, don't generate it. We assume that
2985 if fma isn't available then fms, fnma or fnms are not either. */
2986 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
2989 /* If the multiplication has zero uses, it is kept around probably because
2990 of -fnon-call-exceptions. Don't optimize it away in that case,
2992 if (has_zero_uses (mul_result
))
2995 /* Make sure that the multiplication statement becomes dead after
2996 the transformation, thus that all uses are transformed to FMAs.
2997 This means we assume that an FMA operation has the same cost
2999 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
3001 enum tree_code use_code
;
3002 tree result
= mul_result
;
3003 bool negate_p
= false;
3005 use_stmt
= USE_STMT (use_p
);
3007 if (is_gimple_debug (use_stmt
))
3010 /* For now restrict this operations to single basic blocks. In theory
3011 we would want to support sinking the multiplication in
3017 to form a fma in the then block and sink the multiplication to the
3019 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3022 if (!is_gimple_assign (use_stmt
))
3025 use_code
= gimple_assign_rhs_code (use_stmt
);
3027 /* A negate on the multiplication leads to FNMA. */
3028 if (use_code
== NEGATE_EXPR
)
3033 result
= gimple_assign_lhs (use_stmt
);
3035 /* Make sure the negate statement becomes dead with this
3036 single transformation. */
3037 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
3038 &use_p
, &neguse_stmt
))
3041 /* Make sure the multiplication isn't also used on that stmt. */
3042 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
3043 if (USE_FROM_PTR (usep
) == mul_result
)
3047 use_stmt
= neguse_stmt
;
3048 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3050 if (!is_gimple_assign (use_stmt
))
3053 use_code
= gimple_assign_rhs_code (use_stmt
);
3060 if (gimple_assign_rhs2 (use_stmt
) == result
)
3061 negate_p
= !negate_p
;
3066 /* FMA can only be formed from PLUS and MINUS. */
3070 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
3071 by a MULT_EXPR that we'll visit later, we might be able to
3072 get a more profitable match with fnma.
3073 OTOH, if we don't, a negate / fma pair has likely lower latency
3074 that a mult / subtract pair. */
3075 if (use_code
== MINUS_EXPR
&& !negate_p
3076 && gimple_assign_rhs1 (use_stmt
) == result
3077 && optab_handler (fms_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
3078 && optab_handler (fnma_optab
, TYPE_MODE (type
)) != CODE_FOR_nothing
)
3080 tree rhs2
= gimple_assign_rhs2 (use_stmt
);
3082 if (TREE_CODE (rhs2
) == SSA_NAME
)
3084 gimple stmt2
= SSA_NAME_DEF_STMT (rhs2
);
3085 if (has_single_use (rhs2
)
3086 && is_gimple_assign (stmt2
)
3087 && gimple_assign_rhs_code (stmt2
) == MULT_EXPR
)
3092 /* We can't handle a * b + a * b. */
3093 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
3096 /* While it is possible to validate whether or not the exact form
3097 that we've recognized is available in the backend, the assumption
3098 is that the transformation is never a loss. For instance, suppose
3099 the target only has the plain FMA pattern available. Consider
3100 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
3101 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
3102 still have 3 operations, but in the FMA form the two NEGs are
3103 independent and could be run in parallel. */
3106 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
3108 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
3109 enum tree_code use_code
;
3110 tree addop
, mulop1
= op1
, result
= mul_result
;
3111 bool negate_p
= false;
3113 if (is_gimple_debug (use_stmt
))
3116 use_code
= gimple_assign_rhs_code (use_stmt
);
3117 if (use_code
== NEGATE_EXPR
)
3119 result
= gimple_assign_lhs (use_stmt
);
3120 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
3121 gsi_remove (&gsi
, true);
3122 release_defs (use_stmt
);
3124 use_stmt
= neguse_stmt
;
3125 gsi
= gsi_for_stmt (use_stmt
);
3126 use_code
= gimple_assign_rhs_code (use_stmt
);
3130 if (gimple_assign_rhs1 (use_stmt
) == result
)
3132 addop
= gimple_assign_rhs2 (use_stmt
);
3133 /* a * b - c -> a * b + (-c) */
3134 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3135 addop
= force_gimple_operand_gsi (&gsi
,
3136 build1 (NEGATE_EXPR
,
3138 true, NULL_TREE
, true,
3143 addop
= gimple_assign_rhs1 (use_stmt
);
3144 /* a - b * c -> (-b) * c + a */
3145 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3146 negate_p
= !negate_p
;
3150 mulop1
= force_gimple_operand_gsi (&gsi
,
3151 build1 (NEGATE_EXPR
,
3153 true, NULL_TREE
, true,
3156 fma_stmt
= gimple_build_assign_with_ops (FMA_EXPR
,
3157 gimple_assign_lhs (use_stmt
),
3160 gsi_replace (&gsi
, fma_stmt
, true);
3161 widen_mul_stats
.fmas_inserted
++;
3167 /* Find integer multiplications where the operands are extended from
3168 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
3169 where appropriate. */
3173 const pass_data pass_data_optimize_widening_mul
=
3175 GIMPLE_PASS
, /* type */
3176 "widening_mul", /* name */
3177 OPTGROUP_NONE
, /* optinfo_flags */
3178 TV_NONE
, /* tv_id */
3179 PROP_ssa
, /* properties_required */
3180 0, /* properties_provided */
3181 0, /* properties_destroyed */
3182 0, /* todo_flags_start */
3183 TODO_update_ssa
, /* todo_flags_finish */
3186 class pass_optimize_widening_mul
: public gimple_opt_pass
3189 pass_optimize_widening_mul (gcc::context
*ctxt
)
3190 : gimple_opt_pass (pass_data_optimize_widening_mul
, ctxt
)
3193 /* opt_pass methods: */
3194 virtual bool gate (function
*)
3196 return flag_expensive_optimizations
&& optimize
;
3199 virtual unsigned int execute (function
*);
3201 }; // class pass_optimize_widening_mul
3204 pass_optimize_widening_mul::execute (function
*fun
)
3207 bool cfg_changed
= false;
3209 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
3211 FOR_EACH_BB_FN (bb
, fun
)
3213 gimple_stmt_iterator gsi
;
3215 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
3217 gimple stmt
= gsi_stmt (gsi
);
3218 enum tree_code code
;
3220 if (is_gimple_assign (stmt
))
3222 code
= gimple_assign_rhs_code (stmt
);
3226 if (!convert_mult_to_widen (stmt
, &gsi
)
3227 && convert_mult_to_fma (stmt
,
3228 gimple_assign_rhs1 (stmt
),
3229 gimple_assign_rhs2 (stmt
)))
3231 gsi_remove (&gsi
, true);
3232 release_defs (stmt
);
3239 convert_plusminus_to_widen (&gsi
, stmt
, code
);
3245 else if (is_gimple_call (stmt
)
3246 && gimple_call_lhs (stmt
))
3248 tree fndecl
= gimple_call_fndecl (stmt
);
3250 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3252 switch (DECL_FUNCTION_CODE (fndecl
))
3257 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
3258 && REAL_VALUES_EQUAL
3259 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
3261 && convert_mult_to_fma (stmt
,
3262 gimple_call_arg (stmt
, 0),
3263 gimple_call_arg (stmt
, 0)))
3265 unlink_stmt_vdef (stmt
);
3266 if (gsi_remove (&gsi
, true)
3267 && gimple_purge_dead_eh_edges (bb
))
3269 release_defs (stmt
);
3282 statistics_counter_event (fun
, "widening multiplications inserted",
3283 widen_mul_stats
.widen_mults_inserted
);
3284 statistics_counter_event (fun
, "widening maccs inserted",
3285 widen_mul_stats
.maccs_inserted
);
3286 statistics_counter_event (fun
, "fused multiply-adds inserted",
3287 widen_mul_stats
.fmas_inserted
);
3289 return cfg_changed
? TODO_cleanup_cfg
: 0;
3295 make_pass_optimize_widening_mul (gcc::context
*ctxt
)
3297 return new pass_optimize_widening_mul (ctxt
);