1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* Currently, the only mini-pass in this file tries to CSE reciprocal
21 operations. These are common in sequences such as this one:
23 modulus = sqrt(x*x + y*y + z*z);
28 that can be optimized to
30 modulus = sqrt(x*x + y*y + z*z);
31 rmodulus = 1.0 / modulus;
36 We do this for loop invariant divisors, and with this pass whenever
37 we notice that a division has the same divisor multiple times.
39 Of course, like in PRE, we don't insert a division if a dominator
40 already has one. However, this cannot be done as an extension of
41 PRE for several reasons.
43 First of all, with some experiments it was found out that the
44 transformation is not always useful if there are only two divisions
45 hy the same divisor. This is probably because modern processors
46 can pipeline the divisions; on older, in-order processors it should
47 still be effective to optimize two divisions by the same number.
48 We make this a param, and it shall be called N in the remainder of
51 Second, if trapping math is active, we have less freedom on where
52 to insert divisions: we can only do so in basic blocks that already
53 contain one. (If divisions don't trap, instead, we can insert
54 divisions elsewhere, which will be in blocks that are common dominators
55 of those that have the division).
57 We really don't want to compute the reciprocal unless a division will
58 be found. To do this, we won't insert the division in a basic block
59 that has less than N divisions *post-dominating* it.
61 The algorithm constructs a subset of the dominator tree, holding the
62 blocks containing the divisions and the common dominators to them,
63 and walk it twice. The first walk is in post-order, and it annotates
64 each block with the number of divisions that post-dominate it: this
65 gives information on where divisions can be inserted profitably.
66 The second walk is in pre-order, and it inserts divisions as explained
67 above, and replaces divisions by multiplications.
69 In the best case, the cost of the pass is O(n_statements). In the
70 worst-case, the cost is due to creating the dominator tree subset,
71 with a cost of O(n_basic_blocks ^ 2); however this can only happen
72 for n_statements / n_basic_blocks statements. So, the amortized cost
73 of creating the dominator tree subset is O(n_basic_blocks) and the
74 worst-case cost of the pass is O(n_statements * n_basic_blocks).
76 More practically, the cost will be small because there are few
77 divisions, and they tend to be in the same basic block, so insert_bb
78 is called very few times.
80 If we did this using domwalk.c, an efficient implementation would have
81 to work on all the variables in a single pass, because we could not
82 work on just a subset of the dominator tree, as we do now, and the
83 cost would also be something like O(n_statements * n_basic_blocks).
84 The data structures would be more complex in order to work on all the
85 variables in a single pass. */
89 #include "coretypes.h"
95 #include "double-int.h"
102 #include "fold-const.h"
104 #include "hard-reg-set.h"
105 #include "function.h"
106 #include "dominance.h"
108 #include "basic-block.h"
109 #include "tree-ssa-alias.h"
110 #include "internal-fn.h"
111 #include "gimple-fold.h"
112 #include "gimple-expr.h"
115 #include "gimple-iterator.h"
116 #include "gimplify.h"
117 #include "gimplify-me.h"
118 #include "stor-layout.h"
119 #include "gimple-ssa.h"
120 #include "tree-cfg.h"
121 #include "tree-phinodes.h"
122 #include "ssa-iterators.h"
123 #include "stringpool.h"
124 #include "tree-ssanames.h"
127 #include "statistics.h"
129 #include "fixed-value.h"
130 #include "insn-config.h"
135 #include "emit-rtl.h"
139 #include "tree-dfa.h"
140 #include "tree-ssa.h"
141 #include "tree-pass.h"
142 #include "alloc-pool.h"
144 #include "gimple-pretty-print.h"
145 #include "builtins.h"
148 /* FIXME: RTL headers have to be included here for optabs. */
149 #include "rtl.h" /* Because optabs.h wants enum rtx_code. */
150 #include "expr.h" /* Because optabs.h wants sepops. */
151 #include "insn-codes.h"
154 /* This structure represents one basic block that either computes a
155 division, or is a common dominator for basic block that compute a
158 /* The basic block represented by this structure. */
161 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
165 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
166 was inserted in BB. */
167 gimple recip_def_stmt
;
169 /* Pointer to a list of "struct occurrence"s for blocks dominated
171 struct occurrence
*children
;
173 /* Pointer to the next "struct occurrence"s in the list of blocks
174 sharing a common dominator. */
175 struct occurrence
*next
;
177 /* The number of divisions that are in BB before compute_merit. The
178 number of divisions that are in BB or post-dominate it after
182 /* True if the basic block has a division, false if it is a common
183 dominator for basic blocks that do. If it is false and trapping
184 math is active, BB is not a candidate for inserting a reciprocal. */
185 bool bb_has_division
;
190 /* Number of 1.0/X ops inserted. */
193 /* Number of 1.0/FUNC ops inserted. */
199 /* Number of cexpi calls inserted. */
205 /* Number of hand-written 16-bit nop / bswaps found. */
208 /* Number of hand-written 32-bit nop / bswaps found. */
211 /* Number of hand-written 64-bit nop / bswaps found. */
213 } nop_stats
, bswap_stats
;
217 /* Number of widening multiplication ops inserted. */
218 int widen_mults_inserted
;
220 /* Number of integer multiply-and-accumulate ops inserted. */
223 /* Number of fp fused multiply-add ops inserted. */
227 /* The instance of "struct occurrence" representing the highest
228 interesting block in the dominator tree. */
229 static struct occurrence
*occ_head
;
231 /* Allocation pool for getting instances of "struct occurrence". */
232 static pool_allocator
<occurrence
> *occ_pool
;
236 /* Allocate and return a new struct occurrence for basic block BB, and
237 whose children list is headed by CHILDREN. */
238 static struct occurrence
*
239 occ_new (basic_block bb
, struct occurrence
*children
)
241 struct occurrence
*occ
;
243 bb
->aux
= occ
= occ_pool
->allocate ();
244 memset (occ
, 0, sizeof (struct occurrence
));
247 occ
->children
= children
;
252 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
253 list of "struct occurrence"s, one per basic block, having IDOM as
254 their common dominator.
256 We try to insert NEW_OCC as deep as possible in the tree, and we also
257 insert any other block that is a common dominator for BB and one
258 block already in the tree. */
261 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
262 struct occurrence
**p_head
)
264 struct occurrence
*occ
, **p_occ
;
266 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
268 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
269 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
272 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
275 occ
->next
= new_occ
->children
;
276 new_occ
->children
= occ
;
278 /* Try the next block (it may as well be dominated by BB). */
281 else if (dom
== occ_bb
)
283 /* OCC_BB dominates BB. Tail recurse to look deeper. */
284 insert_bb (new_occ
, dom
, &occ
->children
);
288 else if (dom
!= idom
)
290 gcc_assert (!dom
->aux
);
292 /* There is a dominator between IDOM and BB, add it and make
293 two children out of NEW_OCC and OCC. First, remove OCC from
299 /* None of the previous blocks has DOM as a dominator: if we tail
300 recursed, we would reexamine them uselessly. Just switch BB with
301 DOM, and go on looking for blocks dominated by DOM. */
302 new_occ
= occ_new (dom
, new_occ
);
307 /* Nothing special, go on with the next element. */
312 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
313 new_occ
->next
= *p_head
;
317 /* Register that we found a division in BB. */
320 register_division_in (basic_block bb
)
322 struct occurrence
*occ
;
324 occ
= (struct occurrence
*) bb
->aux
;
327 occ
= occ_new (bb
, NULL
);
328 insert_bb (occ
, ENTRY_BLOCK_PTR_FOR_FN (cfun
), &occ_head
);
331 occ
->bb_has_division
= true;
332 occ
->num_divisions
++;
336 /* Compute the number of divisions that postdominate each block in OCC and
340 compute_merit (struct occurrence
*occ
)
342 struct occurrence
*occ_child
;
343 basic_block dom
= occ
->bb
;
345 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
348 if (occ_child
->children
)
349 compute_merit (occ_child
);
352 bb
= single_noncomplex_succ (dom
);
356 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
357 occ
->num_divisions
+= occ_child
->num_divisions
;
362 /* Return whether USE_STMT is a floating-point division by DEF. */
364 is_division_by (gimple use_stmt
, tree def
)
366 return is_gimple_assign (use_stmt
)
367 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
368 && gimple_assign_rhs2 (use_stmt
) == def
369 /* Do not recognize x / x as valid division, as we are getting
370 confused later by replacing all immediate uses x in such
372 && gimple_assign_rhs1 (use_stmt
) != def
;
375 /* Walk the subset of the dominator tree rooted at OCC, setting the
376 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
377 the given basic block. The field may be left NULL, of course,
378 if it is not possible or profitable to do the optimization.
380 DEF_BSI is an iterator pointing at the statement defining DEF.
381 If RECIP_DEF is set, a dominator already has a computation that can
385 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
386 tree def
, tree recip_def
, int threshold
)
390 gimple_stmt_iterator gsi
;
391 struct occurrence
*occ_child
;
394 && (occ
->bb_has_division
|| !flag_trapping_math
)
395 && occ
->num_divisions
>= threshold
)
397 /* Make a variable with the replacement and substitute it. */
398 type
= TREE_TYPE (def
);
399 recip_def
= create_tmp_reg (type
, "reciptmp");
400 new_stmt
= gimple_build_assign (recip_def
, RDIV_EXPR
,
401 build_one_cst (type
), def
);
403 if (occ
->bb_has_division
)
405 /* Case 1: insert before an existing division. */
406 gsi
= gsi_after_labels (occ
->bb
);
407 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
410 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
412 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
414 /* Case 2: insert right after the definition. Note that this will
415 never happen if the definition statement can throw, because in
416 that case the sole successor of the statement's basic block will
417 dominate all the uses as well. */
418 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
422 /* Case 3: insert in a basic block not containing defs/uses. */
423 gsi
= gsi_after_labels (occ
->bb
);
424 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
427 reciprocal_stats
.rdivs_inserted
++;
429 occ
->recip_def_stmt
= new_stmt
;
432 occ
->recip_def
= recip_def
;
433 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
434 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
438 /* Replace the division at USE_P with a multiplication by the reciprocal, if
442 replace_reciprocal (use_operand_p use_p
)
444 gimple use_stmt
= USE_STMT (use_p
);
445 basic_block bb
= gimple_bb (use_stmt
);
446 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
448 if (optimize_bb_for_speed_p (bb
)
449 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
451 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
452 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
453 SET_USE (use_p
, occ
->recip_def
);
454 fold_stmt_inplace (&gsi
);
455 update_stmt (use_stmt
);
460 /* Free OCC and return one more "struct occurrence" to be freed. */
462 static struct occurrence
*
463 free_bb (struct occurrence
*occ
)
465 struct occurrence
*child
, *next
;
467 /* First get the two pointers hanging off OCC. */
469 child
= occ
->children
;
471 occ_pool
->remove (occ
);
473 /* Now ensure that we don't recurse unless it is necessary. */
479 next
= free_bb (next
);
486 /* Look for floating-point divisions among DEF's uses, and try to
487 replace them by multiplications with the reciprocal. Add
488 as many statements computing the reciprocal as needed.
490 DEF must be a GIMPLE register of a floating-point type. */
493 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
496 imm_use_iterator use_iter
;
497 struct occurrence
*occ
;
498 int count
= 0, threshold
;
500 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
502 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
504 gimple use_stmt
= USE_STMT (use_p
);
505 if (is_division_by (use_stmt
, def
))
507 register_division_in (gimple_bb (use_stmt
));
512 /* Do the expensive part only if we can hope to optimize something. */
513 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
514 if (count
>= threshold
)
517 for (occ
= occ_head
; occ
; occ
= occ
->next
)
520 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
523 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
525 if (is_division_by (use_stmt
, def
))
527 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
528 replace_reciprocal (use_p
);
533 for (occ
= occ_head
; occ
; )
539 /* Go through all the floating-point SSA_NAMEs, and call
540 execute_cse_reciprocals_1 on each of them. */
543 const pass_data pass_data_cse_reciprocals
=
545 GIMPLE_PASS
, /* type */
547 OPTGROUP_NONE
, /* optinfo_flags */
549 PROP_ssa
, /* properties_required */
550 0, /* properties_provided */
551 0, /* properties_destroyed */
552 0, /* todo_flags_start */
553 TODO_update_ssa
, /* todo_flags_finish */
556 class pass_cse_reciprocals
: public gimple_opt_pass
559 pass_cse_reciprocals (gcc::context
*ctxt
)
560 : gimple_opt_pass (pass_data_cse_reciprocals
, ctxt
)
563 /* opt_pass methods: */
564 virtual bool gate (function
*) { return optimize
&& flag_reciprocal_math
; }
565 virtual unsigned int execute (function
*);
567 }; // class pass_cse_reciprocals
570 pass_cse_reciprocals::execute (function
*fun
)
575 occ_pool
= new pool_allocator
<occurrence
>
576 ("dominators for recip", n_basic_blocks_for_fn (fun
) / 3 + 1);
578 memset (&reciprocal_stats
, 0, sizeof (reciprocal_stats
));
579 calculate_dominance_info (CDI_DOMINATORS
);
580 calculate_dominance_info (CDI_POST_DOMINATORS
);
582 #ifdef ENABLE_CHECKING
583 FOR_EACH_BB_FN (bb
, fun
)
584 gcc_assert (!bb
->aux
);
587 for (arg
= DECL_ARGUMENTS (fun
->decl
); arg
; arg
= DECL_CHAIN (arg
))
588 if (FLOAT_TYPE_P (TREE_TYPE (arg
))
589 && is_gimple_reg (arg
))
591 tree name
= ssa_default_def (fun
, arg
);
593 execute_cse_reciprocals_1 (NULL
, name
);
596 FOR_EACH_BB_FN (bb
, fun
)
600 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
603 gphi
*phi
= gsi
.phi ();
604 def
= PHI_RESULT (phi
);
605 if (! virtual_operand_p (def
)
606 && FLOAT_TYPE_P (TREE_TYPE (def
)))
607 execute_cse_reciprocals_1 (NULL
, def
);
610 for (gimple_stmt_iterator gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);
613 gimple stmt
= gsi_stmt (gsi
);
615 if (gimple_has_lhs (stmt
)
616 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
617 && FLOAT_TYPE_P (TREE_TYPE (def
))
618 && TREE_CODE (def
) == SSA_NAME
)
619 execute_cse_reciprocals_1 (&gsi
, def
);
622 if (optimize_bb_for_size_p (bb
))
625 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
626 for (gimple_stmt_iterator gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);
629 gimple stmt
= gsi_stmt (gsi
);
632 if (is_gimple_assign (stmt
)
633 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
635 tree arg1
= gimple_assign_rhs2 (stmt
);
638 if (TREE_CODE (arg1
) != SSA_NAME
)
641 stmt1
= SSA_NAME_DEF_STMT (arg1
);
643 if (is_gimple_call (stmt1
)
644 && gimple_call_lhs (stmt1
)
645 && (fndecl
= gimple_call_fndecl (stmt1
))
646 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
647 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
649 enum built_in_function code
;
654 code
= DECL_FUNCTION_CODE (fndecl
);
655 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
657 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
661 /* Check that all uses of the SSA name are divisions,
662 otherwise replacing the defining statement will do
665 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
667 gimple stmt2
= USE_STMT (use_p
);
668 if (is_gimple_debug (stmt2
))
670 if (!is_gimple_assign (stmt2
)
671 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
672 || gimple_assign_rhs1 (stmt2
) == arg1
673 || gimple_assign_rhs2 (stmt2
) != arg1
)
682 gimple_replace_ssa_lhs (stmt1
, arg1
);
683 gimple_call_set_fndecl (stmt1
, fndecl
);
685 reciprocal_stats
.rfuncs_inserted
++;
687 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
689 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
690 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
691 fold_stmt_inplace (&gsi
);
699 statistics_counter_event (fun
, "reciprocal divs inserted",
700 reciprocal_stats
.rdivs_inserted
);
701 statistics_counter_event (fun
, "reciprocal functions inserted",
702 reciprocal_stats
.rfuncs_inserted
);
704 free_dominance_info (CDI_DOMINATORS
);
705 free_dominance_info (CDI_POST_DOMINATORS
);
713 make_pass_cse_reciprocals (gcc::context
*ctxt
)
715 return new pass_cse_reciprocals (ctxt
);
718 /* Records an occurrence at statement USE_STMT in the vector of trees
719 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
720 is not yet initialized. Returns true if the occurrence was pushed on
721 the vector. Adjusts *TOP_BB to be the basic block dominating all
722 statements in the vector. */
725 maybe_record_sincos (vec
<gimple
> *stmts
,
726 basic_block
*top_bb
, gimple use_stmt
)
728 basic_block use_bb
= gimple_bb (use_stmt
);
730 && (*top_bb
== use_bb
731 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
732 stmts
->safe_push (use_stmt
);
734 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
736 stmts
->safe_push (use_stmt
);
745 /* Look for sin, cos and cexpi calls with the same argument NAME and
746 create a single call to cexpi CSEing the result in this case.
747 We first walk over all immediate uses of the argument collecting
748 statements that we can CSE in a vector and in a second pass replace
749 the statement rhs with a REALPART or IMAGPART expression on the
750 result of the cexpi call we insert before the use statement that
751 dominates all other candidates. */
754 execute_cse_sincos_1 (tree name
)
756 gimple_stmt_iterator gsi
;
757 imm_use_iterator use_iter
;
758 tree fndecl
, res
, type
;
759 gimple def_stmt
, use_stmt
, stmt
;
760 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
761 auto_vec
<gimple
> stmts
;
762 basic_block top_bb
= NULL
;
764 bool cfg_changed
= false;
766 type
= TREE_TYPE (name
);
767 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
769 if (gimple_code (use_stmt
) != GIMPLE_CALL
770 || !gimple_call_lhs (use_stmt
)
771 || !(fndecl
= gimple_call_fndecl (use_stmt
))
772 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
775 switch (DECL_FUNCTION_CODE (fndecl
))
777 CASE_FLT_FN (BUILT_IN_COS
):
778 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
781 CASE_FLT_FN (BUILT_IN_SIN
):
782 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
785 CASE_FLT_FN (BUILT_IN_CEXPI
):
786 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
793 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
796 /* Simply insert cexpi at the beginning of top_bb but not earlier than
797 the name def statement. */
798 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
801 stmt
= gimple_build_call (fndecl
, 1, name
);
802 res
= make_temp_ssa_name (TREE_TYPE (TREE_TYPE (fndecl
)), stmt
, "sincostmp");
803 gimple_call_set_lhs (stmt
, res
);
805 def_stmt
= SSA_NAME_DEF_STMT (name
);
806 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
807 && gimple_code (def_stmt
) != GIMPLE_PHI
808 && gimple_bb (def_stmt
) == top_bb
)
810 gsi
= gsi_for_stmt (def_stmt
);
811 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
815 gsi
= gsi_after_labels (top_bb
);
816 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
818 sincos_stats
.inserted
++;
820 /* And adjust the recorded old call sites. */
821 for (i
= 0; stmts
.iterate (i
, &use_stmt
); ++i
)
824 fndecl
= gimple_call_fndecl (use_stmt
);
826 switch (DECL_FUNCTION_CODE (fndecl
))
828 CASE_FLT_FN (BUILT_IN_COS
):
829 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
832 CASE_FLT_FN (BUILT_IN_SIN
):
833 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
836 CASE_FLT_FN (BUILT_IN_CEXPI
):
844 /* Replace call with a copy. */
845 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
847 gsi
= gsi_for_stmt (use_stmt
);
848 gsi_replace (&gsi
, stmt
, true);
849 if (gimple_purge_dead_eh_edges (gimple_bb (stmt
)))
856 /* To evaluate powi(x,n), the floating point value x raised to the
857 constant integer exponent n, we use a hybrid algorithm that
858 combines the "window method" with look-up tables. For an
859 introduction to exponentiation algorithms and "addition chains",
860 see section 4.6.3, "Evaluation of Powers" of Donald E. Knuth,
861 "Seminumerical Algorithms", Vol. 2, "The Art of Computer Programming",
862 3rd Edition, 1998, and Daniel M. Gordon, "A Survey of Fast Exponentiation
863 Methods", Journal of Algorithms, Vol. 27, pp. 129-146, 1998. */
865 /* Provide a default value for POWI_MAX_MULTS, the maximum number of
866 multiplications to inline before calling the system library's pow
867 function. powi(x,n) requires at worst 2*bits(n)-2 multiplications,
868 so this default never requires calling pow, powf or powl. */
870 #ifndef POWI_MAX_MULTS
871 #define POWI_MAX_MULTS (2*HOST_BITS_PER_WIDE_INT-2)
874 /* The size of the "optimal power tree" lookup table. All
875 exponents less than this value are simply looked up in the
876 powi_table below. This threshold is also used to size the
877 cache of pseudo registers that hold intermediate results. */
878 #define POWI_TABLE_SIZE 256
880 /* The size, in bits of the window, used in the "window method"
881 exponentiation algorithm. This is equivalent to a radix of
882 (1<<POWI_WINDOW_SIZE) in the corresponding "m-ary method". */
883 #define POWI_WINDOW_SIZE 3
885 /* The following table is an efficient representation of an
886 "optimal power tree". For each value, i, the corresponding
887 value, j, in the table states than an optimal evaluation
888 sequence for calculating pow(x,i) can be found by evaluating
889 pow(x,j)*pow(x,i-j). An optimal power tree for the first
890 100 integers is given in Knuth's "Seminumerical algorithms". */
892 static const unsigned char powi_table
[POWI_TABLE_SIZE
] =
894 0, 1, 1, 2, 2, 3, 3, 4, /* 0 - 7 */
895 4, 6, 5, 6, 6, 10, 7, 9, /* 8 - 15 */
896 8, 16, 9, 16, 10, 12, 11, 13, /* 16 - 23 */
897 12, 17, 13, 18, 14, 24, 15, 26, /* 24 - 31 */
898 16, 17, 17, 19, 18, 33, 19, 26, /* 32 - 39 */
899 20, 25, 21, 40, 22, 27, 23, 44, /* 40 - 47 */
900 24, 32, 25, 34, 26, 29, 27, 44, /* 48 - 55 */
901 28, 31, 29, 34, 30, 60, 31, 36, /* 56 - 63 */
902 32, 64, 33, 34, 34, 46, 35, 37, /* 64 - 71 */
903 36, 65, 37, 50, 38, 48, 39, 69, /* 72 - 79 */
904 40, 49, 41, 43, 42, 51, 43, 58, /* 80 - 87 */
905 44, 64, 45, 47, 46, 59, 47, 76, /* 88 - 95 */
906 48, 65, 49, 66, 50, 67, 51, 66, /* 96 - 103 */
907 52, 70, 53, 74, 54, 104, 55, 74, /* 104 - 111 */
908 56, 64, 57, 69, 58, 78, 59, 68, /* 112 - 119 */
909 60, 61, 61, 80, 62, 75, 63, 68, /* 120 - 127 */
910 64, 65, 65, 128, 66, 129, 67, 90, /* 128 - 135 */
911 68, 73, 69, 131, 70, 94, 71, 88, /* 136 - 143 */
912 72, 128, 73, 98, 74, 132, 75, 121, /* 144 - 151 */
913 76, 102, 77, 124, 78, 132, 79, 106, /* 152 - 159 */
914 80, 97, 81, 160, 82, 99, 83, 134, /* 160 - 167 */
915 84, 86, 85, 95, 86, 160, 87, 100, /* 168 - 175 */
916 88, 113, 89, 98, 90, 107, 91, 122, /* 176 - 183 */
917 92, 111, 93, 102, 94, 126, 95, 150, /* 184 - 191 */
918 96, 128, 97, 130, 98, 133, 99, 195, /* 192 - 199 */
919 100, 128, 101, 123, 102, 164, 103, 138, /* 200 - 207 */
920 104, 145, 105, 146, 106, 109, 107, 149, /* 208 - 215 */
921 108, 200, 109, 146, 110, 170, 111, 157, /* 216 - 223 */
922 112, 128, 113, 130, 114, 182, 115, 132, /* 224 - 231 */
923 116, 200, 117, 132, 118, 158, 119, 206, /* 232 - 239 */
924 120, 240, 121, 162, 122, 147, 123, 152, /* 240 - 247 */
925 124, 166, 125, 214, 126, 138, 127, 153, /* 248 - 255 */
929 /* Return the number of multiplications required to calculate
930 powi(x,n) where n is less than POWI_TABLE_SIZE. This is a
931 subroutine of powi_cost. CACHE is an array indicating
932 which exponents have already been calculated. */
935 powi_lookup_cost (unsigned HOST_WIDE_INT n
, bool *cache
)
937 /* If we've already calculated this exponent, then this evaluation
938 doesn't require any additional multiplications. */
943 return powi_lookup_cost (n
- powi_table
[n
], cache
)
944 + powi_lookup_cost (powi_table
[n
], cache
) + 1;
947 /* Return the number of multiplications required to calculate
948 powi(x,n) for an arbitrary x, given the exponent N. This
949 function needs to be kept in sync with powi_as_mults below. */
952 powi_cost (HOST_WIDE_INT n
)
954 bool cache
[POWI_TABLE_SIZE
];
955 unsigned HOST_WIDE_INT digit
;
956 unsigned HOST_WIDE_INT val
;
962 /* Ignore the reciprocal when calculating the cost. */
963 val
= (n
< 0) ? -n
: n
;
965 /* Initialize the exponent cache. */
966 memset (cache
, 0, POWI_TABLE_SIZE
* sizeof (bool));
971 while (val
>= POWI_TABLE_SIZE
)
975 digit
= val
& ((1 << POWI_WINDOW_SIZE
) - 1);
976 result
+= powi_lookup_cost (digit
, cache
)
977 + POWI_WINDOW_SIZE
+ 1;
978 val
>>= POWI_WINDOW_SIZE
;
987 return result
+ powi_lookup_cost (val
, cache
);
990 /* Recursive subroutine of powi_as_mults. This function takes the
991 array, CACHE, of already calculated exponents and an exponent N and
992 returns a tree that corresponds to CACHE[1]**N, with type TYPE. */
995 powi_as_mults_1 (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
996 HOST_WIDE_INT n
, tree
*cache
)
998 tree op0
, op1
, ssa_target
;
999 unsigned HOST_WIDE_INT digit
;
1002 if (n
< POWI_TABLE_SIZE
&& cache
[n
])
1005 ssa_target
= make_temp_ssa_name (type
, NULL
, "powmult");
1007 if (n
< POWI_TABLE_SIZE
)
1009 cache
[n
] = ssa_target
;
1010 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- powi_table
[n
], cache
);
1011 op1
= powi_as_mults_1 (gsi
, loc
, type
, powi_table
[n
], cache
);
1015 digit
= n
& ((1 << POWI_WINDOW_SIZE
) - 1);
1016 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
- digit
, cache
);
1017 op1
= powi_as_mults_1 (gsi
, loc
, type
, digit
, cache
);
1021 op0
= powi_as_mults_1 (gsi
, loc
, type
, n
>> 1, cache
);
1025 mult_stmt
= gimple_build_assign (ssa_target
, MULT_EXPR
, op0
, op1
);
1026 gimple_set_location (mult_stmt
, loc
);
1027 gsi_insert_before (gsi
, mult_stmt
, GSI_SAME_STMT
);
1032 /* Convert ARG0**N to a tree of multiplications of ARG0 with itself.
1033 This function needs to be kept in sync with powi_cost above. */
1036 powi_as_mults (gimple_stmt_iterator
*gsi
, location_t loc
,
1037 tree arg0
, HOST_WIDE_INT n
)
1039 tree cache
[POWI_TABLE_SIZE
], result
, type
= TREE_TYPE (arg0
);
1044 return build_real (type
, dconst1
);
1046 memset (cache
, 0, sizeof (cache
));
1049 result
= powi_as_mults_1 (gsi
, loc
, type
, (n
< 0) ? -n
: n
, cache
);
1053 /* If the original exponent was negative, reciprocate the result. */
1054 target
= make_temp_ssa_name (type
, NULL
, "powmult");
1055 div_stmt
= gimple_build_assign (target
, RDIV_EXPR
,
1056 build_real (type
, dconst1
), result
);
1057 gimple_set_location (div_stmt
, loc
);
1058 gsi_insert_before (gsi
, div_stmt
, GSI_SAME_STMT
);
1063 /* ARG0 and N are the two arguments to a powi builtin in GSI with
1064 location info LOC. If the arguments are appropriate, create an
1065 equivalent sequence of statements prior to GSI using an optimal
1066 number of multiplications, and return an expession holding the
1070 gimple_expand_builtin_powi (gimple_stmt_iterator
*gsi
, location_t loc
,
1071 tree arg0
, HOST_WIDE_INT n
)
1073 /* Avoid largest negative number. */
1075 && ((n
>= -1 && n
<= 2)
1076 || (optimize_function_for_speed_p (cfun
)
1077 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1078 return powi_as_mults (gsi
, loc
, arg0
, n
);
1083 /* Build a gimple call statement that calls FN with argument ARG.
1084 Set the lhs of the call statement to a fresh SSA name. Insert the
1085 statement prior to GSI's current position, and return the fresh
1089 build_and_insert_call (gimple_stmt_iterator
*gsi
, location_t loc
,
1095 call_stmt
= gimple_build_call (fn
, 1, arg
);
1096 ssa_target
= make_temp_ssa_name (TREE_TYPE (arg
), NULL
, "powroot");
1097 gimple_set_lhs (call_stmt
, ssa_target
);
1098 gimple_set_location (call_stmt
, loc
);
1099 gsi_insert_before (gsi
, call_stmt
, GSI_SAME_STMT
);
1104 /* Build a gimple binary operation with the given CODE and arguments
1105 ARG0, ARG1, assigning the result to a new SSA name for variable
1106 TARGET. Insert the statement prior to GSI's current position, and
1107 return the fresh SSA name.*/
1110 build_and_insert_binop (gimple_stmt_iterator
*gsi
, location_t loc
,
1111 const char *name
, enum tree_code code
,
1112 tree arg0
, tree arg1
)
1114 tree result
= make_temp_ssa_name (TREE_TYPE (arg0
), NULL
, name
);
1115 gassign
*stmt
= gimple_build_assign (result
, code
, arg0
, arg1
);
1116 gimple_set_location (stmt
, loc
);
1117 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1121 /* Build a gimple reference operation with the given CODE and argument
1122 ARG, assigning the result to a new SSA name of TYPE with NAME.
1123 Insert the statement prior to GSI's current position, and return
1124 the fresh SSA name. */
1127 build_and_insert_ref (gimple_stmt_iterator
*gsi
, location_t loc
, tree type
,
1128 const char *name
, enum tree_code code
, tree arg0
)
1130 tree result
= make_temp_ssa_name (type
, NULL
, name
);
1131 gimple stmt
= gimple_build_assign (result
, build1 (code
, type
, arg0
));
1132 gimple_set_location (stmt
, loc
);
1133 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1137 /* Build a gimple assignment to cast VAL to TYPE. Insert the statement
1138 prior to GSI's current position, and return the fresh SSA name. */
1141 build_and_insert_cast (gimple_stmt_iterator
*gsi
, location_t loc
,
1142 tree type
, tree val
)
1144 tree result
= make_ssa_name (type
);
1145 gassign
*stmt
= gimple_build_assign (result
, NOP_EXPR
, val
);
1146 gimple_set_location (stmt
, loc
);
1147 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
1151 struct pow_synth_sqrt_info
1154 unsigned int deepest
;
1155 unsigned int num_mults
;
1158 /* Return true iff the real value C can be represented as a
1159 sum of powers of 0.5 up to N. That is:
1160 C == SUM<i from 1..N> (a[i]*(0.5**i)) where a[i] is either 0 or 1.
1161 Record in INFO the various parameters of the synthesis algorithm such
1162 as the factors a[i], the maximum 0.5 power and the number of
1163 multiplications that will be required. */
1166 representable_as_half_series_p (REAL_VALUE_TYPE c
, unsigned n
,
1167 struct pow_synth_sqrt_info
*info
)
1169 REAL_VALUE_TYPE factor
= dconsthalf
;
1170 REAL_VALUE_TYPE remainder
= c
;
1173 info
->num_mults
= 0;
1174 memset (info
->factors
, 0, n
* sizeof (bool));
1176 for (unsigned i
= 0; i
< n
; i
++)
1178 REAL_VALUE_TYPE res
;
1180 /* If something inexact happened bail out now. */
1181 if (REAL_ARITHMETIC (res
, MINUS_EXPR
, remainder
, factor
))
1184 /* We have hit zero. The number is representable as a sum
1185 of powers of 0.5. */
1186 if (REAL_VALUES_EQUAL (res
, dconst0
))
1188 info
->factors
[i
] = true;
1189 info
->deepest
= i
+ 1;
1192 else if (!REAL_VALUE_NEGATIVE (res
))
1195 info
->factors
[i
] = true;
1199 info
->factors
[i
] = false;
1201 REAL_ARITHMETIC (factor
, MULT_EXPR
, factor
, dconsthalf
);
1206 /* Return the tree corresponding to FN being applied
1207 to ARG N times at GSI and LOC.
1208 Look up previous results from CACHE if need be.
1209 cache[0] should contain just plain ARG i.e. FN applied to ARG 0 times. */
1212 get_fn_chain (tree arg
, unsigned int n
, gimple_stmt_iterator
*gsi
,
1213 tree fn
, location_t loc
, tree
*cache
)
1215 tree res
= cache
[n
];
1218 tree prev
= get_fn_chain (arg
, n
- 1, gsi
, fn
, loc
, cache
);
1219 res
= build_and_insert_call (gsi
, loc
, fn
, prev
);
1226 /* Print to STREAM the repeated application of function FNAME to ARG
1227 N times. So, for FNAME = "foo", ARG = "x", N = 2 it would print:
1231 print_nested_fn (FILE* stream
, const char *fname
, const char* arg
,
1235 fprintf (stream
, "%s", arg
);
1238 fprintf (stream
, "%s (", fname
);
1239 print_nested_fn (stream
, fname
, arg
, n
- 1);
1240 fprintf (stream
, ")");
1244 /* Print to STREAM the fractional sequence of sqrt chains
1245 applied to ARG, described by INFO. Used for the dump file. */
1248 dump_fractional_sqrt_sequence (FILE *stream
, const char *arg
,
1249 struct pow_synth_sqrt_info
*info
)
1251 for (unsigned int i
= 0; i
< info
->deepest
; i
++)
1253 bool is_set
= info
->factors
[i
];
1256 print_nested_fn (stream
, "sqrt", arg
, i
+ 1);
1257 if (i
!= info
->deepest
- 1)
1258 fprintf (stream
, " * ");
1263 /* Print to STREAM a representation of raising ARG to an integer
1264 power N. Used for the dump file. */
1267 dump_integer_part (FILE *stream
, const char* arg
, HOST_WIDE_INT n
)
1270 fprintf (stream
, "powi (%s, " HOST_WIDE_INT_PRINT_DEC
")", arg
, n
);
1272 fprintf (stream
, "%s", arg
);
1275 /* Attempt to synthesize a POW[F] (ARG0, ARG1) call using chains of
1276 square roots. Place at GSI and LOC. Limit the maximum depth
1277 of the sqrt chains to MAX_DEPTH. Return the tree holding the
1278 result of the expanded sequence or NULL_TREE if the expansion failed.
1280 This routine assumes that ARG1 is a real number with a fractional part
1281 (the integer exponent case will have been handled earlier in
1282 gimple_expand_builtin_pow).
1285 * For ARG1 composed of a whole part WHOLE_PART and a fractional part
1286 FRAC_PART i.e. WHOLE_PART == floor (ARG1) and
1287 FRAC_PART == ARG1 - WHOLE_PART:
1288 Produce POWI (ARG0, WHOLE_PART) * POW (ARG0, FRAC_PART) where
1289 POW (ARG0, FRAC_PART) is expanded as a product of square root chains
1290 if it can be expressed as such, that is if FRAC_PART satisfies:
1291 FRAC_PART == <SUM from i = 1 until MAX_DEPTH> (a[i] * (0.5**i))
1292 where integer a[i] is either 0 or 1.
1295 POW (x, 3.625) == POWI (x, 3) * POW (x, 0.625)
1296 --> POWI (x, 3) * SQRT (x) * SQRT (SQRT (SQRT (x)))
1298 For ARG1 < 0.0 there are two approaches:
1299 * (A) Expand to 1.0 / POW (ARG0, -ARG1) where POW (ARG0, -ARG1)
1300 is calculated as above.
1303 POW (x, -5.625) == 1.0 / POW (x, 5.625)
1304 --> 1.0 / (POWI (x, 5) * SQRT (x) * SQRT (SQRT (SQRT (x))))
1306 * (B) : WHOLE_PART := - ceil (abs (ARG1))
1307 FRAC_PART := ARG1 - WHOLE_PART
1308 and expand to POW (x, FRAC_PART) / POWI (x, WHOLE_PART).
1310 POW (x, -5.875) == POW (x, 0.125) / POWI (X, 6)
1311 --> SQRT (SQRT (SQRT (x))) / (POWI (x, 6))
1313 For ARG1 < 0.0 we choose between (A) and (B) depending on
1314 how many multiplications we'd have to do.
1315 So, for the example in (B): POW (x, -5.875), if we were to
1316 follow algorithm (A) we would produce:
1317 1.0 / POWI (X, 5) * SQRT (X) * SQRT (SQRT (X)) * SQRT (SQRT (SQRT (X)))
1318 which contains more multiplications than approach (B).
1320 Hopefully, this approach will eliminate potentially expensive POW library
1321 calls when unsafe floating point math is enabled and allow the compiler to
1322 further optimise the multiplies, square roots and divides produced by this
1326 expand_pow_as_sqrts (gimple_stmt_iterator
*gsi
, location_t loc
,
1327 tree arg0
, tree arg1
, HOST_WIDE_INT max_depth
)
1329 tree type
= TREE_TYPE (arg0
);
1330 machine_mode mode
= TYPE_MODE (type
);
1331 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1332 bool one_over
= true;
1337 if (TREE_CODE (arg1
) != REAL_CST
)
1340 REAL_VALUE_TYPE exp_init
= TREE_REAL_CST (arg1
);
1342 gcc_assert (max_depth
> 0);
1343 tree
*cache
= XALLOCAVEC (tree
, max_depth
+ 1);
1345 struct pow_synth_sqrt_info synth_info
;
1346 synth_info
.factors
= XALLOCAVEC (bool, max_depth
+ 1);
1347 synth_info
.deepest
= 0;
1348 synth_info
.num_mults
= 0;
1350 bool neg_exp
= REAL_VALUE_NEGATIVE (exp_init
);
1351 REAL_VALUE_TYPE exp
= real_value_abs (&exp_init
);
1353 /* The whole and fractional parts of exp. */
1354 REAL_VALUE_TYPE whole_part
;
1355 REAL_VALUE_TYPE frac_part
;
1357 real_floor (&whole_part
, mode
, &exp
);
1358 REAL_ARITHMETIC (frac_part
, MINUS_EXPR
, exp
, whole_part
);
1361 REAL_VALUE_TYPE ceil_whole
= dconst0
;
1362 REAL_VALUE_TYPE ceil_fract
= dconst0
;
1366 real_ceil (&ceil_whole
, mode
, &exp
);
1367 REAL_ARITHMETIC (ceil_fract
, MINUS_EXPR
, ceil_whole
, exp
);
1370 if (!representable_as_half_series_p (frac_part
, max_depth
, &synth_info
))
1373 /* Check whether it's more profitable to not use 1.0 / ... */
1376 struct pow_synth_sqrt_info alt_synth_info
;
1377 alt_synth_info
.factors
= XALLOCAVEC (bool, max_depth
+ 1);
1378 alt_synth_info
.deepest
= 0;
1379 alt_synth_info
.num_mults
= 0;
1381 if (representable_as_half_series_p (ceil_fract
, max_depth
,
1383 && alt_synth_info
.deepest
<= synth_info
.deepest
1384 && alt_synth_info
.num_mults
< synth_info
.num_mults
)
1386 whole_part
= ceil_whole
;
1387 frac_part
= ceil_fract
;
1388 synth_info
.deepest
= alt_synth_info
.deepest
;
1389 synth_info
.num_mults
= alt_synth_info
.num_mults
;
1390 memcpy (synth_info
.factors
, alt_synth_info
.factors
,
1391 (max_depth
+ 1) * sizeof (bool));
1396 HOST_WIDE_INT n
= real_to_integer (&whole_part
);
1397 REAL_VALUE_TYPE cint
;
1398 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1400 if (!real_identical (&whole_part
, &cint
))
1403 if (powi_cost (n
) + synth_info
.num_mults
> POWI_MAX_MULTS
)
1406 memset (cache
, 0, (max_depth
+ 1) * sizeof (tree
));
1408 tree integer_res
= n
== 0 ? build_real (type
, dconst1
) : arg0
;
1410 /* Calculate the integer part of the exponent. */
1413 integer_res
= gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1422 real_to_decimal (string
, &exp_init
, sizeof (string
), 0, 1);
1423 fprintf (dump_file
, "synthesizing pow (x, %s) as:\n", string
);
1429 fprintf (dump_file
, "1.0 / (");
1430 dump_integer_part (dump_file
, "x", n
);
1432 fprintf (dump_file
, " * ");
1433 dump_fractional_sqrt_sequence (dump_file
, "x", &synth_info
);
1434 fprintf (dump_file
, ")");
1438 dump_fractional_sqrt_sequence (dump_file
, "x", &synth_info
);
1439 fprintf (dump_file
, " / (");
1440 dump_integer_part (dump_file
, "x", n
);
1441 fprintf (dump_file
, ")");
1446 dump_fractional_sqrt_sequence (dump_file
, "x", &synth_info
);
1448 fprintf (dump_file
, " * ");
1449 dump_integer_part (dump_file
, "x", n
);
1452 fprintf (dump_file
, "\ndeepest sqrt chain: %d\n", synth_info
.deepest
);
1456 tree fract_res
= NULL_TREE
;
1459 /* Calculate the fractional part of the exponent. */
1460 for (unsigned i
= 0; i
< synth_info
.deepest
; i
++)
1462 if (synth_info
.factors
[i
])
1464 tree sqrt_chain
= get_fn_chain (arg0
, i
+ 1, gsi
, sqrtfn
, loc
, cache
);
1467 fract_res
= sqrt_chain
;
1470 fract_res
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1471 fract_res
, sqrt_chain
);
1475 tree res
= NULL_TREE
;
1482 res
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1483 fract_res
, integer_res
);
1487 res
= build_and_insert_binop (gsi
, loc
, "powrootrecip", RDIV_EXPR
,
1488 build_real (type
, dconst1
), res
);
1492 res
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1493 fract_res
, integer_res
);
1497 res
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1498 fract_res
, integer_res
);
1502 /* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
1503 with location info LOC. If possible, create an equivalent and
1504 less expensive sequence of statements prior to GSI, and return an
1505 expession holding the result. */
1508 gimple_expand_builtin_pow (gimple_stmt_iterator
*gsi
, location_t loc
,
1509 tree arg0
, tree arg1
)
1511 REAL_VALUE_TYPE c
, cint
, dconst1_3
, dconst1_4
, dconst1_6
;
1512 REAL_VALUE_TYPE c2
, dconst3
;
1514 tree type
, sqrtfn
, cbrtfn
, sqrt_arg0
, result
, cbrt_x
, powi_cbrt_x
;
1516 bool speed_p
= optimize_bb_for_speed_p (gsi_bb (*gsi
));
1517 bool hw_sqrt_exists
, c_is_int
, c2_is_int
;
1519 dconst1_4
= dconst1
;
1520 SET_REAL_EXP (&dconst1_4
, REAL_EXP (&dconst1_4
) - 2);
1522 /* If the exponent isn't a constant, there's nothing of interest
1524 if (TREE_CODE (arg1
) != REAL_CST
)
1527 /* If the exponent is equivalent to an integer, expand to an optimal
1528 multiplication sequence when profitable. */
1529 c
= TREE_REAL_CST (arg1
);
1530 n
= real_to_integer (&c
);
1531 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1532 c_is_int
= real_identical (&c
, &cint
);
1535 && ((n
>= -1 && n
<= 2)
1536 || (flag_unsafe_math_optimizations
1538 && powi_cost (n
) <= POWI_MAX_MULTS
)))
1539 return gimple_expand_builtin_powi (gsi
, loc
, arg0
, n
);
1541 /* Attempt various optimizations using sqrt and cbrt. */
1542 type
= TREE_TYPE (arg0
);
1543 mode
= TYPE_MODE (type
);
1544 sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1546 /* Optimize pow(x,0.5) = sqrt(x). This replacement is always safe
1547 unless signed zeros must be maintained. pow(-0,0.5) = +0, while
1550 && REAL_VALUES_EQUAL (c
, dconsthalf
)
1551 && !HONOR_SIGNED_ZEROS (mode
))
1552 return build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1554 hw_sqrt_exists
= optab_handler (sqrt_optab
, mode
) != CODE_FOR_nothing
;
1556 /* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
1557 optimizations since 1./3. is not exactly representable. If x
1558 is negative and finite, the correct value of pow(x,1./3.) is
1559 a NaN with the "invalid" exception raised, because the value
1560 of 1./3. actually has an even denominator. The correct value
1561 of cbrt(x) is a negative real value. */
1562 cbrtfn
= mathfn_built_in (type
, BUILT_IN_CBRT
);
1563 dconst1_3
= real_value_truncate (mode
, dconst_third ());
1565 if (flag_unsafe_math_optimizations
1567 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1568 && REAL_VALUES_EQUAL (c
, dconst1_3
))
1569 return build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1571 /* Optimize pow(x,1./6.) = cbrt(sqrt(x)). Don't do this optimization
1572 if we don't have a hardware sqrt insn. */
1573 dconst1_6
= dconst1_3
;
1574 SET_REAL_EXP (&dconst1_6
, REAL_EXP (&dconst1_6
) - 1);
1576 if (flag_unsafe_math_optimizations
1579 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1582 && REAL_VALUES_EQUAL (c
, dconst1_6
))
1585 sqrt_arg0
= build_and_insert_call (gsi
, loc
, sqrtfn
, arg0
);
1588 return build_and_insert_call (gsi
, loc
, cbrtfn
, sqrt_arg0
);
1592 /* Attempt to expand the POW as a product of square root chains.
1593 Expand the 0.25 case even when otpimising for size. */
1594 if (flag_unsafe_math_optimizations
1597 && (speed_p
|| REAL_VALUES_EQUAL (c
, dconst1_4
))
1598 && !HONOR_SIGNED_ZEROS (mode
))
1600 unsigned int max_depth
= speed_p
1601 ? PARAM_VALUE (PARAM_MAX_POW_SQRT_DEPTH
)
1604 tree expand_with_sqrts
1605 = expand_pow_as_sqrts (gsi
, loc
, arg0
, arg1
, max_depth
);
1607 if (expand_with_sqrts
)
1608 return expand_with_sqrts
;
1611 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst2
);
1612 n
= real_to_integer (&c2
);
1613 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1614 c2_is_int
= real_identical (&c2
, &cint
);
1616 /* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
1618 powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
1619 1.0 / (powi(x, abs(n)/3) * powi(cbrt(x), abs(n)%3)), n < 0.
1621 Do not calculate the first factor when n/3 = 0. As cbrt(x) is
1622 different from pow(x, 1./3.) due to rounding and behavior with
1623 negative x, we need to constrain this transformation to unsafe
1624 math and positive x or finite math. */
1625 real_from_integer (&dconst3
, VOIDmode
, 3, SIGNED
);
1626 real_arithmetic (&c2
, MULT_EXPR
, &c
, &dconst3
);
1627 real_round (&c2
, mode
, &c2
);
1628 n
= real_to_integer (&c2
);
1629 real_from_integer (&cint
, VOIDmode
, n
, SIGNED
);
1630 real_arithmetic (&c2
, RDIV_EXPR
, &cint
, &dconst3
);
1631 real_convert (&c2
, mode
, &c2
);
1633 if (flag_unsafe_math_optimizations
1635 && (gimple_val_nonnegative_real_p (arg0
) || !HONOR_NANS (mode
))
1636 && real_identical (&c2
, &c
)
1638 && optimize_function_for_speed_p (cfun
)
1639 && powi_cost (n
/ 3) <= POWI_MAX_MULTS
)
1641 tree powi_x_ndiv3
= NULL_TREE
;
1643 /* Attempt to fold powi(arg0, abs(n/3)) into multiplies. If not
1644 possible or profitable, give up. Skip the degenerate case when
1645 abs(n) < 3, where the result is always 1. */
1646 if (absu_hwi (n
) >= 3)
1648 powi_x_ndiv3
= gimple_expand_builtin_powi (gsi
, loc
, arg0
,
1654 /* Calculate powi(cbrt(x), n%3). Don't use gimple_expand_builtin_powi
1655 as that creates an unnecessary variable. Instead, just produce
1656 either cbrt(x) or cbrt(x) * cbrt(x). */
1657 cbrt_x
= build_and_insert_call (gsi
, loc
, cbrtfn
, arg0
);
1659 if (absu_hwi (n
) % 3 == 1)
1660 powi_cbrt_x
= cbrt_x
;
1662 powi_cbrt_x
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1665 /* Multiply the two subexpressions, unless powi(x,abs(n)/3) = 1. */
1666 if (absu_hwi (n
) < 3)
1667 result
= powi_cbrt_x
;
1669 result
= build_and_insert_binop (gsi
, loc
, "powroot", MULT_EXPR
,
1670 powi_x_ndiv3
, powi_cbrt_x
);
1672 /* If n is negative, reciprocate the result. */
1674 result
= build_and_insert_binop (gsi
, loc
, "powroot", RDIV_EXPR
,
1675 build_real (type
, dconst1
), result
);
1680 /* No optimizations succeeded. */
1684 /* ARG is the argument to a cabs builtin call in GSI with location info
1685 LOC. Create a sequence of statements prior to GSI that calculates
1686 sqrt(R*R + I*I), where R and I are the real and imaginary components
1687 of ARG, respectively. Return an expression holding the result. */
1690 gimple_expand_builtin_cabs (gimple_stmt_iterator
*gsi
, location_t loc
, tree arg
)
1692 tree real_part
, imag_part
, addend1
, addend2
, sum
, result
;
1693 tree type
= TREE_TYPE (TREE_TYPE (arg
));
1694 tree sqrtfn
= mathfn_built_in (type
, BUILT_IN_SQRT
);
1695 machine_mode mode
= TYPE_MODE (type
);
1697 if (!flag_unsafe_math_optimizations
1698 || !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi
)))
1700 || optab_handler (sqrt_optab
, mode
) == CODE_FOR_nothing
)
1703 real_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1704 REALPART_EXPR
, arg
);
1705 addend1
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1706 real_part
, real_part
);
1707 imag_part
= build_and_insert_ref (gsi
, loc
, type
, "cabs",
1708 IMAGPART_EXPR
, arg
);
1709 addend2
= build_and_insert_binop (gsi
, loc
, "cabs", MULT_EXPR
,
1710 imag_part
, imag_part
);
1711 sum
= build_and_insert_binop (gsi
, loc
, "cabs", PLUS_EXPR
, addend1
, addend2
);
1712 result
= build_and_insert_call (gsi
, loc
, sqrtfn
, sum
);
1717 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
1718 on the SSA_NAME argument of each of them. Also expand powi(x,n) into
1719 an optimal number of multiplies, when n is a constant. */
1723 const pass_data pass_data_cse_sincos
=
1725 GIMPLE_PASS
, /* type */
1726 "sincos", /* name */
1727 OPTGROUP_NONE
, /* optinfo_flags */
1728 TV_NONE
, /* tv_id */
1729 PROP_ssa
, /* properties_required */
1730 0, /* properties_provided */
1731 0, /* properties_destroyed */
1732 0, /* todo_flags_start */
1733 TODO_update_ssa
, /* todo_flags_finish */
1736 class pass_cse_sincos
: public gimple_opt_pass
1739 pass_cse_sincos (gcc::context
*ctxt
)
1740 : gimple_opt_pass (pass_data_cse_sincos
, ctxt
)
1743 /* opt_pass methods: */
1744 virtual bool gate (function
*)
1746 /* We no longer require either sincos or cexp, since powi expansion
1747 piggybacks on this pass. */
1751 virtual unsigned int execute (function
*);
1753 }; // class pass_cse_sincos
1756 pass_cse_sincos::execute (function
*fun
)
1759 bool cfg_changed
= false;
1761 calculate_dominance_info (CDI_DOMINATORS
);
1762 memset (&sincos_stats
, 0, sizeof (sincos_stats
));
1764 FOR_EACH_BB_FN (bb
, fun
)
1766 gimple_stmt_iterator gsi
;
1767 bool cleanup_eh
= false;
1769 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1771 gimple stmt
= gsi_stmt (gsi
);
1774 /* Only the last stmt in a bb could throw, no need to call
1775 gimple_purge_dead_eh_edges if we change something in the middle
1776 of a basic block. */
1779 if (is_gimple_call (stmt
)
1780 && gimple_call_lhs (stmt
)
1781 && (fndecl
= gimple_call_fndecl (stmt
))
1782 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
1784 tree arg
, arg0
, arg1
, result
;
1788 switch (DECL_FUNCTION_CODE (fndecl
))
1790 CASE_FLT_FN (BUILT_IN_COS
):
1791 CASE_FLT_FN (BUILT_IN_SIN
):
1792 CASE_FLT_FN (BUILT_IN_CEXPI
):
1793 /* Make sure we have either sincos or cexp. */
1794 if (!targetm
.libc_has_function (function_c99_math_complex
)
1795 && !targetm
.libc_has_function (function_sincos
))
1798 arg
= gimple_call_arg (stmt
, 0);
1799 if (TREE_CODE (arg
) == SSA_NAME
)
1800 cfg_changed
|= execute_cse_sincos_1 (arg
);
1803 CASE_FLT_FN (BUILT_IN_POW
):
1804 arg0
= gimple_call_arg (stmt
, 0);
1805 arg1
= gimple_call_arg (stmt
, 1);
1807 loc
= gimple_location (stmt
);
1808 result
= gimple_expand_builtin_pow (&gsi
, loc
, arg0
, arg1
);
1812 tree lhs
= gimple_get_lhs (stmt
);
1813 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1814 gimple_set_location (new_stmt
, loc
);
1815 unlink_stmt_vdef (stmt
);
1816 gsi_replace (&gsi
, new_stmt
, true);
1818 if (gimple_vdef (stmt
))
1819 release_ssa_name (gimple_vdef (stmt
));
1823 CASE_FLT_FN (BUILT_IN_POWI
):
1824 arg0
= gimple_call_arg (stmt
, 0);
1825 arg1
= gimple_call_arg (stmt
, 1);
1826 loc
= gimple_location (stmt
);
1828 if (real_minus_onep (arg0
))
1830 tree t0
, t1
, cond
, one
, minus_one
;
1833 t0
= TREE_TYPE (arg0
);
1834 t1
= TREE_TYPE (arg1
);
1835 one
= build_real (t0
, dconst1
);
1836 minus_one
= build_real (t0
, dconstm1
);
1838 cond
= make_temp_ssa_name (t1
, NULL
, "powi_cond");
1839 stmt
= gimple_build_assign (cond
, BIT_AND_EXPR
,
1840 arg1
, build_int_cst (t1
, 1));
1841 gimple_set_location (stmt
, loc
);
1842 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1844 result
= make_temp_ssa_name (t0
, NULL
, "powi");
1845 stmt
= gimple_build_assign (result
, COND_EXPR
, cond
,
1847 gimple_set_location (stmt
, loc
);
1848 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1852 if (!tree_fits_shwi_p (arg1
))
1855 n
= tree_to_shwi (arg1
);
1856 result
= gimple_expand_builtin_powi (&gsi
, loc
, arg0
, n
);
1861 tree lhs
= gimple_get_lhs (stmt
);
1862 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1863 gimple_set_location (new_stmt
, loc
);
1864 unlink_stmt_vdef (stmt
);
1865 gsi_replace (&gsi
, new_stmt
, true);
1867 if (gimple_vdef (stmt
))
1868 release_ssa_name (gimple_vdef (stmt
));
1872 CASE_FLT_FN (BUILT_IN_CABS
):
1873 arg0
= gimple_call_arg (stmt
, 0);
1874 loc
= gimple_location (stmt
);
1875 result
= gimple_expand_builtin_cabs (&gsi
, loc
, arg0
);
1879 tree lhs
= gimple_get_lhs (stmt
);
1880 gassign
*new_stmt
= gimple_build_assign (lhs
, result
);
1881 gimple_set_location (new_stmt
, loc
);
1882 unlink_stmt_vdef (stmt
);
1883 gsi_replace (&gsi
, new_stmt
, true);
1885 if (gimple_vdef (stmt
))
1886 release_ssa_name (gimple_vdef (stmt
));
1895 cfg_changed
|= gimple_purge_dead_eh_edges (bb
);
1898 statistics_counter_event (fun
, "sincos statements inserted",
1899 sincos_stats
.inserted
);
1901 free_dominance_info (CDI_DOMINATORS
);
1902 return cfg_changed
? TODO_cleanup_cfg
: 0;
1908 make_pass_cse_sincos (gcc::context
*ctxt
)
1910 return new pass_cse_sincos (ctxt
);
1913 /* A symbolic number is used to detect byte permutation and selection
1914 patterns. Therefore the field N contains an artificial number
1915 consisting of octet sized markers:
1917 0 - target byte has the value 0
1918 FF - target byte has an unknown value (eg. due to sign extension)
1919 1..size - marker value is the target byte index minus one.
1921 To detect permutations on memory sources (arrays and structures), a symbolic
1922 number is also associated a base address (the array or structure the load is
1923 made from), an offset from the base address and a range which gives the
1924 difference between the highest and lowest accessed memory location to make
1925 such a symbolic number. The range is thus different from size which reflects
1926 the size of the type of current expression. Note that for non memory source,
1927 range holds the same value as size.
1929 For instance, for an array char a[], (short) a[0] | (short) a[3] would have
1930 a size of 2 but a range of 4 while (short) a[0] | ((short) a[0] << 1) would
1931 still have a size of 2 but this time a range of 1. */
1933 struct symbolic_number
{
1938 HOST_WIDE_INT bytepos
;
1941 unsigned HOST_WIDE_INT range
;
1944 #define BITS_PER_MARKER 8
1945 #define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
1946 #define MARKER_BYTE_UNKNOWN MARKER_MASK
1947 #define HEAD_MARKER(n, size) \
1948 ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
1950 /* The number which the find_bswap_or_nop_1 result should match in
1951 order to have a nop. The number is masked according to the size of
1952 the symbolic number before using it. */
1953 #define CMPNOP (sizeof (int64_t) < 8 ? 0 : \
1954 (uint64_t)0x08070605 << 32 | 0x04030201)
1956 /* The number which the find_bswap_or_nop_1 result should match in
1957 order to have a byte swap. The number is masked according to the
1958 size of the symbolic number before using it. */
1959 #define CMPXCHG (sizeof (int64_t) < 8 ? 0 : \
1960 (uint64_t)0x01020304 << 32 | 0x05060708)
1962 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
1963 number N. Return false if the requested operation is not permitted
1964 on a symbolic number. */
1967 do_shift_rotate (enum tree_code code
,
1968 struct symbolic_number
*n
,
1971 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
1972 unsigned head_marker
;
1974 if (count
% BITS_PER_UNIT
!= 0)
1976 count
= (count
/ BITS_PER_UNIT
) * BITS_PER_MARKER
;
1978 /* Zero out the extra bits of N in order to avoid them being shifted
1979 into the significant bits. */
1980 if (size
< 64 / BITS_PER_MARKER
)
1981 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
1989 head_marker
= HEAD_MARKER (n
->n
, size
);
1991 /* Arithmetic shift of signed type: result is dependent on the value. */
1992 if (!TYPE_UNSIGNED (n
->type
) && head_marker
)
1993 for (i
= 0; i
< count
/ BITS_PER_MARKER
; i
++)
1994 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
1995 << ((size
- 1 - i
) * BITS_PER_MARKER
);
1998 n
->n
= (n
->n
<< count
) | (n
->n
>> ((size
* BITS_PER_MARKER
) - count
));
2001 n
->n
= (n
->n
>> count
) | (n
->n
<< ((size
* BITS_PER_MARKER
) - count
));
2006 /* Zero unused bits for size. */
2007 if (size
< 64 / BITS_PER_MARKER
)
2008 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
2012 /* Perform sanity checking for the symbolic number N and the gimple
2016 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
2020 lhs_type
= gimple_expr_type (stmt
);
2022 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
2025 if (TYPE_PRECISION (lhs_type
) != TYPE_PRECISION (n
->type
))
2031 /* Initialize the symbolic number N for the bswap pass from the base element
2032 SRC manipulated by the bitwise OR expression. */
2035 init_symbolic_number (struct symbolic_number
*n
, tree src
)
2039 n
->base_addr
= n
->offset
= n
->alias_set
= n
->vuse
= NULL_TREE
;
2041 /* Set up the symbolic number N by setting each byte to a value between 1 and
2042 the byte size of rhs1. The highest order byte is set to n->size and the
2043 lowest order byte to 1. */
2044 n
->type
= TREE_TYPE (src
);
2045 size
= TYPE_PRECISION (n
->type
);
2046 if (size
% BITS_PER_UNIT
!= 0)
2048 size
/= BITS_PER_UNIT
;
2049 if (size
> 64 / BITS_PER_MARKER
)
2054 if (size
< 64 / BITS_PER_MARKER
)
2055 n
->n
&= ((uint64_t) 1 << (size
* BITS_PER_MARKER
)) - 1;
2060 /* Check if STMT might be a byte swap or a nop from a memory source and returns
2061 the answer. If so, REF is that memory source and the base of the memory area
2062 accessed and the offset of the access from that base are recorded in N. */
2065 find_bswap_or_nop_load (gimple stmt
, tree ref
, struct symbolic_number
*n
)
2067 /* Leaf node is an array or component ref. Memorize its base and
2068 offset from base to compare to other such leaf node. */
2069 HOST_WIDE_INT bitsize
, bitpos
;
2071 int unsignedp
, volatilep
;
2072 tree offset
, base_addr
;
2074 /* Not prepared to handle PDP endian. */
2075 if (BYTES_BIG_ENDIAN
!= WORDS_BIG_ENDIAN
)
2078 if (!gimple_assign_load_p (stmt
) || gimple_has_volatile_ops (stmt
))
2081 base_addr
= get_inner_reference (ref
, &bitsize
, &bitpos
, &offset
, &mode
,
2082 &unsignedp
, &volatilep
, false);
2084 if (TREE_CODE (base_addr
) == MEM_REF
)
2086 offset_int bit_offset
= 0;
2087 tree off
= TREE_OPERAND (base_addr
, 1);
2089 if (!integer_zerop (off
))
2091 offset_int boff
, coff
= mem_ref_offset (base_addr
);
2092 boff
= wi::lshift (coff
, LOG2_BITS_PER_UNIT
);
2096 base_addr
= TREE_OPERAND (base_addr
, 0);
2098 /* Avoid returning a negative bitpos as this may wreak havoc later. */
2099 if (wi::neg_p (bit_offset
))
2101 offset_int mask
= wi::mask
<offset_int
> (LOG2_BITS_PER_UNIT
, false);
2102 offset_int tem
= bit_offset
.and_not (mask
);
2103 /* TEM is the bitpos rounded to BITS_PER_UNIT towards -Inf.
2104 Subtract it to BIT_OFFSET and add it (scaled) to OFFSET. */
2106 tem
= wi::arshift (tem
, LOG2_BITS_PER_UNIT
);
2108 offset
= size_binop (PLUS_EXPR
, offset
,
2109 wide_int_to_tree (sizetype
, tem
));
2111 offset
= wide_int_to_tree (sizetype
, tem
);
2114 bitpos
+= bit_offset
.to_shwi ();
2117 if (bitpos
% BITS_PER_UNIT
)
2119 if (bitsize
% BITS_PER_UNIT
)
2122 if (!init_symbolic_number (n
, ref
))
2124 n
->base_addr
= base_addr
;
2126 n
->bytepos
= bitpos
/ BITS_PER_UNIT
;
2127 n
->alias_set
= reference_alias_ptr_type (ref
);
2128 n
->vuse
= gimple_vuse (stmt
);
2132 /* Compute the symbolic number N representing the result of a bitwise OR on 2
2133 symbolic number N1 and N2 whose source statements are respectively
2134 SOURCE_STMT1 and SOURCE_STMT2. */
2137 perform_symbolic_merge (gimple source_stmt1
, struct symbolic_number
*n1
,
2138 gimple source_stmt2
, struct symbolic_number
*n2
,
2139 struct symbolic_number
*n
)
2144 struct symbolic_number
*n_start
;
2146 /* Sources are different, cancel bswap if they are not memory location with
2147 the same base (array, structure, ...). */
2148 if (gimple_assign_rhs1 (source_stmt1
) != gimple_assign_rhs1 (source_stmt2
))
2151 HOST_WIDE_INT start_sub
, end_sub
, end1
, end2
, end
;
2152 struct symbolic_number
*toinc_n_ptr
, *n_end
;
2154 if (!n1
->base_addr
|| !n2
->base_addr
2155 || !operand_equal_p (n1
->base_addr
, n2
->base_addr
, 0))
2158 if (!n1
->offset
!= !n2
->offset
2159 || (n1
->offset
&& !operand_equal_p (n1
->offset
, n2
->offset
, 0)))
2162 if (n1
->bytepos
< n2
->bytepos
)
2165 start_sub
= n2
->bytepos
- n1
->bytepos
;
2166 source_stmt
= source_stmt1
;
2171 start_sub
= n1
->bytepos
- n2
->bytepos
;
2172 source_stmt
= source_stmt2
;
2175 /* Find the highest address at which a load is performed and
2176 compute related info. */
2177 end1
= n1
->bytepos
+ (n1
->range
- 1);
2178 end2
= n2
->bytepos
+ (n2
->range
- 1);
2182 end_sub
= end2
- end1
;
2187 end_sub
= end1
- end2
;
2189 n_end
= (end2
> end1
) ? n2
: n1
;
2191 /* Find symbolic number whose lsb is the most significant. */
2192 if (BYTES_BIG_ENDIAN
)
2193 toinc_n_ptr
= (n_end
== n1
) ? n2
: n1
;
2195 toinc_n_ptr
= (n_start
== n1
) ? n2
: n1
;
2197 n
->range
= end
- n_start
->bytepos
+ 1;
2199 /* Check that the range of memory covered can be represented by
2200 a symbolic number. */
2201 if (n
->range
> 64 / BITS_PER_MARKER
)
2204 /* Reinterpret byte marks in symbolic number holding the value of
2205 bigger weight according to target endianness. */
2206 inc
= BYTES_BIG_ENDIAN
? end_sub
: start_sub
;
2207 size
= TYPE_PRECISION (n1
->type
) / BITS_PER_UNIT
;
2208 for (i
= 0; i
< size
; i
++, inc
<<= BITS_PER_MARKER
)
2211 = (toinc_n_ptr
->n
>> (i
* BITS_PER_MARKER
)) & MARKER_MASK
;
2212 if (marker
&& marker
!= MARKER_BYTE_UNKNOWN
)
2213 toinc_n_ptr
->n
+= inc
;
2218 n
->range
= n1
->range
;
2220 source_stmt
= source_stmt1
;
2224 || alias_ptr_types_compatible_p (n1
->alias_set
, n2
->alias_set
))
2225 n
->alias_set
= n1
->alias_set
;
2227 n
->alias_set
= ptr_type_node
;
2228 n
->vuse
= n_start
->vuse
;
2229 n
->base_addr
= n_start
->base_addr
;
2230 n
->offset
= n_start
->offset
;
2231 n
->bytepos
= n_start
->bytepos
;
2232 n
->type
= n_start
->type
;
2233 size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
2235 for (i
= 0, mask
= MARKER_MASK
; i
< size
; i
++, mask
<<= BITS_PER_MARKER
)
2237 uint64_t masked1
, masked2
;
2239 masked1
= n1
->n
& mask
;
2240 masked2
= n2
->n
& mask
;
2241 if (masked1
&& masked2
&& masked1
!= masked2
)
2244 n
->n
= n1
->n
| n2
->n
;
2249 /* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
2250 the operation given by the rhs of STMT on the result. If the operation
2251 could successfully be executed the function returns a gimple stmt whose
2252 rhs's first tree is the expression of the source operand and NULL
2256 find_bswap_or_nop_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
2258 enum tree_code code
;
2259 tree rhs1
, rhs2
= NULL
;
2260 gimple rhs1_stmt
, rhs2_stmt
, source_stmt1
;
2261 enum gimple_rhs_class rhs_class
;
2263 if (!limit
|| !is_gimple_assign (stmt
))
2266 rhs1
= gimple_assign_rhs1 (stmt
);
2268 if (find_bswap_or_nop_load (stmt
, rhs1
, n
))
2271 if (TREE_CODE (rhs1
) != SSA_NAME
)
2274 code
= gimple_assign_rhs_code (stmt
);
2275 rhs_class
= gimple_assign_rhs_class (stmt
);
2276 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
2278 if (rhs_class
== GIMPLE_BINARY_RHS
)
2279 rhs2
= gimple_assign_rhs2 (stmt
);
2281 /* Handle unary rhs and binary rhs with integer constants as second
2284 if (rhs_class
== GIMPLE_UNARY_RHS
2285 || (rhs_class
== GIMPLE_BINARY_RHS
2286 && TREE_CODE (rhs2
) == INTEGER_CST
))
2288 if (code
!= BIT_AND_EXPR
2289 && code
!= LSHIFT_EXPR
2290 && code
!= RSHIFT_EXPR
2291 && code
!= LROTATE_EXPR
2292 && code
!= RROTATE_EXPR
2293 && !CONVERT_EXPR_CODE_P (code
))
2296 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, n
, limit
- 1);
2298 /* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
2299 we have to initialize the symbolic number. */
2302 if (gimple_assign_load_p (stmt
)
2303 || !init_symbolic_number (n
, rhs1
))
2305 source_stmt1
= stmt
;
2312 int i
, size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
2313 uint64_t val
= int_cst_value (rhs2
), mask
= 0;
2314 uint64_t tmp
= (1 << BITS_PER_UNIT
) - 1;
2316 /* Only constants masking full bytes are allowed. */
2317 for (i
= 0; i
< size
; i
++, tmp
<<= BITS_PER_UNIT
)
2318 if ((val
& tmp
) != 0 && (val
& tmp
) != tmp
)
2321 mask
|= (uint64_t) MARKER_MASK
<< (i
* BITS_PER_MARKER
);
2330 if (!do_shift_rotate (code
, n
, (int) TREE_INT_CST_LOW (rhs2
)))
2335 int i
, type_size
, old_type_size
;
2338 type
= gimple_expr_type (stmt
);
2339 type_size
= TYPE_PRECISION (type
);
2340 if (type_size
% BITS_PER_UNIT
!= 0)
2342 type_size
/= BITS_PER_UNIT
;
2343 if (type_size
> 64 / BITS_PER_MARKER
)
2346 /* Sign extension: result is dependent on the value. */
2347 old_type_size
= TYPE_PRECISION (n
->type
) / BITS_PER_UNIT
;
2348 if (!TYPE_UNSIGNED (n
->type
) && type_size
> old_type_size
2349 && HEAD_MARKER (n
->n
, old_type_size
))
2350 for (i
= 0; i
< type_size
- old_type_size
; i
++)
2351 n
->n
|= (uint64_t) MARKER_BYTE_UNKNOWN
2352 << ((type_size
- 1 - i
) * BITS_PER_MARKER
);
2354 if (type_size
< 64 / BITS_PER_MARKER
)
2356 /* If STMT casts to a smaller type mask out the bits not
2357 belonging to the target type. */
2358 n
->n
&= ((uint64_t) 1 << (type_size
* BITS_PER_MARKER
)) - 1;
2362 n
->range
= type_size
;
2368 return verify_symbolic_number_p (n
, stmt
) ? source_stmt1
: NULL
;
2371 /* Handle binary rhs. */
2373 if (rhs_class
== GIMPLE_BINARY_RHS
)
2375 struct symbolic_number n1
, n2
;
2376 gimple source_stmt
, source_stmt2
;
2378 if (code
!= BIT_IOR_EXPR
)
2381 if (TREE_CODE (rhs2
) != SSA_NAME
)
2384 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
2389 source_stmt1
= find_bswap_or_nop_1 (rhs1_stmt
, &n1
, limit
- 1);
2394 source_stmt2
= find_bswap_or_nop_1 (rhs2_stmt
, &n2
, limit
- 1);
2399 if (TYPE_PRECISION (n1
.type
) != TYPE_PRECISION (n2
.type
))
2402 if (!n1
.vuse
!= !n2
.vuse
2403 || (n1
.vuse
&& !operand_equal_p (n1
.vuse
, n2
.vuse
, 0)))
2407 = perform_symbolic_merge (source_stmt1
, &n1
, source_stmt2
, &n2
, n
);
2412 if (!verify_symbolic_number_p (n
, stmt
))
2424 /* Check if STMT completes a bswap implementation or a read in a given
2425 endianness consisting of ORs, SHIFTs and ANDs and sets *BSWAP
2426 accordingly. It also sets N to represent the kind of operations
2427 performed: size of the resulting expression and whether it works on
2428 a memory source, and if so alias-set and vuse. At last, the
2429 function returns a stmt whose rhs's first tree is the source
2433 find_bswap_or_nop (gimple stmt
, struct symbolic_number
*n
, bool *bswap
)
2435 /* The number which the find_bswap_or_nop_1 result should match in order
2436 to have a full byte swap. The number is shifted to the right
2437 according to the size of the symbolic number before using it. */
2438 uint64_t cmpxchg
= CMPXCHG
;
2439 uint64_t cmpnop
= CMPNOP
;
2444 /* The last parameter determines the depth search limit. It usually
2445 correlates directly to the number n of bytes to be touched. We
2446 increase that number by log2(n) + 1 here in order to also
2447 cover signed -> unsigned conversions of the src operand as can be seen
2448 in libgcc, and for initial shift/and operation of the src operand. */
2449 limit
= TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt
)));
2450 limit
+= 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT
) limit
);
2451 source_stmt
= find_bswap_or_nop_1 (stmt
, n
, limit
);
2456 /* Find real size of result (highest non-zero byte). */
2462 for (tmpn
= n
->n
, rsize
= 0; tmpn
; tmpn
>>= BITS_PER_MARKER
, rsize
++);
2466 /* Zero out the extra bits of N and CMP*. */
2467 if (n
->range
< (int) sizeof (int64_t))
2471 mask
= ((uint64_t) 1 << (n
->range
* BITS_PER_MARKER
)) - 1;
2472 cmpxchg
>>= (64 / BITS_PER_MARKER
- n
->range
) * BITS_PER_MARKER
;
2476 /* A complete byte swap should make the symbolic number to start with
2477 the largest digit in the highest order byte. Unchanged symbolic
2478 number indicates a read with same endianness as target architecture. */
2481 else if (n
->n
== cmpxchg
)
2486 /* Useless bit manipulation performed by code. */
2487 if (!n
->base_addr
&& n
->n
== cmpnop
)
2490 n
->range
*= BITS_PER_UNIT
;
2496 const pass_data pass_data_optimize_bswap
=
2498 GIMPLE_PASS
, /* type */
2500 OPTGROUP_NONE
, /* optinfo_flags */
2501 TV_NONE
, /* tv_id */
2502 PROP_ssa
, /* properties_required */
2503 0, /* properties_provided */
2504 0, /* properties_destroyed */
2505 0, /* todo_flags_start */
2506 0, /* todo_flags_finish */
2509 class pass_optimize_bswap
: public gimple_opt_pass
2512 pass_optimize_bswap (gcc::context
*ctxt
)
2513 : gimple_opt_pass (pass_data_optimize_bswap
, ctxt
)
2516 /* opt_pass methods: */
2517 virtual bool gate (function
*)
2519 return flag_expensive_optimizations
&& optimize
;
2522 virtual unsigned int execute (function
*);
2524 }; // class pass_optimize_bswap
2526 /* Perform the bswap optimization: replace the expression computed in the rhs
2527 of CUR_STMT by an equivalent bswap, load or load + bswap expression.
2528 Which of these alternatives replace the rhs is given by N->base_addr (non
2529 null if a load is needed) and BSWAP. The type, VUSE and set-alias of the
2530 load to perform are also given in N while the builtin bswap invoke is given
2531 in FNDEL. Finally, if a load is involved, SRC_STMT refers to one of the
2532 load statements involved to construct the rhs in CUR_STMT and N->range gives
2533 the size of the rhs expression for maintaining some statistics.
2535 Note that if the replacement involve a load, CUR_STMT is moved just after
2536 SRC_STMT to do the load with the same VUSE which can lead to CUR_STMT
2537 changing of basic block. */
2540 bswap_replace (gimple cur_stmt
, gimple src_stmt
, tree fndecl
, tree bswap_type
,
2541 tree load_type
, struct symbolic_number
*n
, bool bswap
)
2543 gimple_stmt_iterator gsi
;
2547 gsi
= gsi_for_stmt (cur_stmt
);
2548 src
= gimple_assign_rhs1 (src_stmt
);
2549 tgt
= gimple_assign_lhs (cur_stmt
);
2551 /* Need to load the value from memory first. */
2554 gimple_stmt_iterator gsi_ins
= gsi_for_stmt (src_stmt
);
2555 tree addr_expr
, addr_tmp
, val_expr
, val_tmp
;
2556 tree load_offset_ptr
, aligned_load_type
;
2557 gimple addr_stmt
, load_stmt
;
2559 HOST_WIDE_INT load_offset
= 0;
2561 align
= get_object_alignment (src
);
2562 /* If the new access is smaller than the original one, we need
2563 to perform big endian adjustment. */
2564 if (BYTES_BIG_ENDIAN
)
2566 HOST_WIDE_INT bitsize
, bitpos
;
2568 int unsignedp
, volatilep
;
2571 get_inner_reference (src
, &bitsize
, &bitpos
, &offset
, &mode
,
2572 &unsignedp
, &volatilep
, false);
2573 if (n
->range
< (unsigned HOST_WIDE_INT
) bitsize
)
2575 load_offset
= (bitsize
- n
->range
) / BITS_PER_UNIT
;
2576 unsigned HOST_WIDE_INT l
2577 = (load_offset
* BITS_PER_UNIT
) & (align
- 1);
2584 && align
< GET_MODE_ALIGNMENT (TYPE_MODE (load_type
))
2585 && SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type
), align
))
2588 /* Move cur_stmt just before one of the load of the original
2589 to ensure it has the same VUSE. See PR61517 for what could
2591 gsi_move_before (&gsi
, &gsi_ins
);
2592 gsi
= gsi_for_stmt (cur_stmt
);
2594 /* Compute address to load from and cast according to the size
2596 addr_expr
= build_fold_addr_expr (unshare_expr (src
));
2597 if (is_gimple_mem_ref_addr (addr_expr
))
2598 addr_tmp
= addr_expr
;
2601 addr_tmp
= make_temp_ssa_name (TREE_TYPE (addr_expr
), NULL
,
2603 addr_stmt
= gimple_build_assign (addr_tmp
, addr_expr
);
2604 gsi_insert_before (&gsi
, addr_stmt
, GSI_SAME_STMT
);
2607 /* Perform the load. */
2608 aligned_load_type
= load_type
;
2609 if (align
< TYPE_ALIGN (load_type
))
2610 aligned_load_type
= build_aligned_type (load_type
, align
);
2611 load_offset_ptr
= build_int_cst (n
->alias_set
, load_offset
);
2612 val_expr
= fold_build2 (MEM_REF
, aligned_load_type
, addr_tmp
,
2618 nop_stats
.found_16bit
++;
2619 else if (n
->range
== 32)
2620 nop_stats
.found_32bit
++;
2623 gcc_assert (n
->range
== 64);
2624 nop_stats
.found_64bit
++;
2627 /* Convert the result of load if necessary. */
2628 if (!useless_type_conversion_p (TREE_TYPE (tgt
), load_type
))
2630 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
,
2632 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2633 gimple_set_vuse (load_stmt
, n
->vuse
);
2634 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
2635 gimple_assign_set_rhs_with_ops (&gsi
, NOP_EXPR
, val_tmp
);
2639 gimple_assign_set_rhs_with_ops (&gsi
, MEM_REF
, val_expr
);
2640 gimple_set_vuse (cur_stmt
, n
->vuse
);
2642 update_stmt (cur_stmt
);
2647 "%d bit load in target endianness found at: ",
2649 print_gimple_stmt (dump_file
, cur_stmt
, 0, 0);
2655 val_tmp
= make_temp_ssa_name (aligned_load_type
, NULL
, "load_dst");
2656 load_stmt
= gimple_build_assign (val_tmp
, val_expr
);
2657 gimple_set_vuse (load_stmt
, n
->vuse
);
2658 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
2664 bswap_stats
.found_16bit
++;
2665 else if (n
->range
== 32)
2666 bswap_stats
.found_32bit
++;
2669 gcc_assert (n
->range
== 64);
2670 bswap_stats
.found_64bit
++;
2675 /* Convert the src expression if necessary. */
2676 if (!useless_type_conversion_p (TREE_TYPE (tmp
), bswap_type
))
2678 gimple convert_stmt
;
2680 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapsrc");
2681 convert_stmt
= gimple_build_assign (tmp
, NOP_EXPR
, src
);
2682 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
2685 /* Canonical form for 16 bit bswap is a rotate expression. Only 16bit values
2686 are considered as rotation of 2N bit values by N bits is generally not
2687 equivalent to a bswap. Consider for instance 0x01020304 r>> 16 which
2688 gives 0x03040102 while a bswap for that value is 0x04030201. */
2689 if (bswap
&& n
->range
== 16)
2691 tree count
= build_int_cst (NULL
, BITS_PER_UNIT
);
2692 src
= fold_build2 (LROTATE_EXPR
, bswap_type
, tmp
, count
);
2693 bswap_stmt
= gimple_build_assign (NULL
, src
);
2696 bswap_stmt
= gimple_build_call (fndecl
, 1, tmp
);
2700 /* Convert the result if necessary. */
2701 if (!useless_type_conversion_p (TREE_TYPE (tgt
), bswap_type
))
2703 gimple convert_stmt
;
2705 tmp
= make_temp_ssa_name (bswap_type
, NULL
, "bswapdst");
2706 convert_stmt
= gimple_build_assign (tgt
, NOP_EXPR
, tmp
);
2707 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
2710 gimple_set_lhs (bswap_stmt
, tmp
);
2714 fprintf (dump_file
, "%d bit bswap implementation found at: ",
2716 print_gimple_stmt (dump_file
, cur_stmt
, 0, 0);
2719 gsi_insert_after (&gsi
, bswap_stmt
, GSI_SAME_STMT
);
2720 gsi_remove (&gsi
, true);
2724 /* Find manual byte swap implementations as well as load in a given
2725 endianness. Byte swaps are turned into a bswap builtin invokation
2726 while endian loads are converted to bswap builtin invokation or
2727 simple load according to the target endianness. */
2730 pass_optimize_bswap::execute (function
*fun
)
2733 bool bswap32_p
, bswap64_p
;
2734 bool changed
= false;
2735 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
2737 if (BITS_PER_UNIT
!= 8)
2740 bswap32_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP32
)
2741 && optab_handler (bswap_optab
, SImode
) != CODE_FOR_nothing
);
2742 bswap64_p
= (builtin_decl_explicit_p (BUILT_IN_BSWAP64
)
2743 && (optab_handler (bswap_optab
, DImode
) != CODE_FOR_nothing
2744 || (bswap32_p
&& word_mode
== SImode
)));
2746 /* Determine the argument type of the builtins. The code later on
2747 assumes that the return and argument type are the same. */
2750 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2751 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2756 tree fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2757 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
2760 memset (&nop_stats
, 0, sizeof (nop_stats
));
2761 memset (&bswap_stats
, 0, sizeof (bswap_stats
));
2763 FOR_EACH_BB_FN (bb
, fun
)
2765 gimple_stmt_iterator gsi
;
2767 /* We do a reverse scan for bswap patterns to make sure we get the
2768 widest match. As bswap pattern matching doesn't handle previously
2769 inserted smaller bswap replacements as sub-patterns, the wider
2770 variant wouldn't be detected. */
2771 for (gsi
= gsi_last_bb (bb
); !gsi_end_p (gsi
);)
2773 gimple src_stmt
, cur_stmt
= gsi_stmt (gsi
);
2774 tree fndecl
= NULL_TREE
, bswap_type
= NULL_TREE
, load_type
;
2775 enum tree_code code
;
2776 struct symbolic_number n
;
2779 /* This gsi_prev (&gsi) is not part of the for loop because cur_stmt
2780 might be moved to a different basic block by bswap_replace and gsi
2781 must not points to it if that's the case. Moving the gsi_prev
2782 there make sure that gsi points to the statement previous to
2783 cur_stmt while still making sure that all statements are
2784 considered in this basic block. */
2787 if (!is_gimple_assign (cur_stmt
))
2790 code
= gimple_assign_rhs_code (cur_stmt
);
2795 if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt
))
2796 || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt
))
2806 src_stmt
= find_bswap_or_nop (cur_stmt
, &n
, &bswap
);
2814 /* Already in canonical form, nothing to do. */
2815 if (code
== LROTATE_EXPR
|| code
== RROTATE_EXPR
)
2817 load_type
= bswap_type
= uint16_type_node
;
2820 load_type
= uint32_type_node
;
2823 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP32
);
2824 bswap_type
= bswap32_type
;
2828 load_type
= uint64_type_node
;
2831 fndecl
= builtin_decl_explicit (BUILT_IN_BSWAP64
);
2832 bswap_type
= bswap64_type
;
2839 if (bswap
&& !fndecl
&& n
.range
!= 16)
2842 if (bswap_replace (cur_stmt
, src_stmt
, fndecl
, bswap_type
, load_type
,
2848 statistics_counter_event (fun
, "16-bit nop implementations found",
2849 nop_stats
.found_16bit
);
2850 statistics_counter_event (fun
, "32-bit nop implementations found",
2851 nop_stats
.found_32bit
);
2852 statistics_counter_event (fun
, "64-bit nop implementations found",
2853 nop_stats
.found_64bit
);
2854 statistics_counter_event (fun
, "16-bit bswap implementations found",
2855 bswap_stats
.found_16bit
);
2856 statistics_counter_event (fun
, "32-bit bswap implementations found",
2857 bswap_stats
.found_32bit
);
2858 statistics_counter_event (fun
, "64-bit bswap implementations found",
2859 bswap_stats
.found_64bit
);
2861 return (changed
? TODO_update_ssa
: 0);
2867 make_pass_optimize_bswap (gcc::context
*ctxt
)
2869 return new pass_optimize_bswap (ctxt
);
2872 /* Return true if stmt is a type conversion operation that can be stripped
2873 when used in a widening multiply operation. */
2875 widening_mult_conversion_strippable_p (tree result_type
, gimple stmt
)
2877 enum tree_code rhs_code
= gimple_assign_rhs_code (stmt
);
2879 if (TREE_CODE (result_type
) == INTEGER_TYPE
)
2884 if (!CONVERT_EXPR_CODE_P (rhs_code
))
2887 op_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2889 /* If the type of OP has the same precision as the result, then
2890 we can strip this conversion. The multiply operation will be
2891 selected to create the correct extension as a by-product. */
2892 if (TYPE_PRECISION (result_type
) == TYPE_PRECISION (op_type
))
2895 /* We can also strip a conversion if it preserves the signed-ness of
2896 the operation and doesn't narrow the range. */
2897 inner_op_type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
2899 /* If the inner-most type is unsigned, then we can strip any
2900 intermediate widening operation. If it's signed, then the
2901 intermediate widening operation must also be signed. */
2902 if ((TYPE_UNSIGNED (inner_op_type
)
2903 || TYPE_UNSIGNED (op_type
) == TYPE_UNSIGNED (inner_op_type
))
2904 && TYPE_PRECISION (op_type
) > TYPE_PRECISION (inner_op_type
))
2910 return rhs_code
== FIXED_CONVERT_EXPR
;
2913 /* Return true if RHS is a suitable operand for a widening multiplication,
2914 assuming a target type of TYPE.
2915 There are two cases:
2917 - RHS makes some value at least twice as wide. Store that value
2918 in *NEW_RHS_OUT if so, and store its type in *TYPE_OUT.
2920 - RHS is an integer constant. Store that value in *NEW_RHS_OUT if so,
2921 but leave *TYPE_OUT untouched. */
2924 is_widening_mult_rhs_p (tree type
, tree rhs
, tree
*type_out
,
2930 if (TREE_CODE (rhs
) == SSA_NAME
)
2932 stmt
= SSA_NAME_DEF_STMT (rhs
);
2933 if (is_gimple_assign (stmt
))
2935 if (! widening_mult_conversion_strippable_p (type
, stmt
))
2939 rhs1
= gimple_assign_rhs1 (stmt
);
2941 if (TREE_CODE (rhs1
) == INTEGER_CST
)
2943 *new_rhs_out
= rhs1
;
2952 type1
= TREE_TYPE (rhs1
);
2954 if (TREE_CODE (type1
) != TREE_CODE (type
)
2955 || TYPE_PRECISION (type1
) * 2 > TYPE_PRECISION (type
))
2958 *new_rhs_out
= rhs1
;
2963 if (TREE_CODE (rhs
) == INTEGER_CST
)
2973 /* Return true if STMT performs a widening multiplication, assuming the
2974 output type is TYPE. If so, store the unwidened types of the operands
2975 in *TYPE1_OUT and *TYPE2_OUT respectively. Also fill *RHS1_OUT and
2976 *RHS2_OUT such that converting those operands to types *TYPE1_OUT
2977 and *TYPE2_OUT would give the operands of the multiplication. */
2980 is_widening_mult_p (gimple stmt
,
2981 tree
*type1_out
, tree
*rhs1_out
,
2982 tree
*type2_out
, tree
*rhs2_out
)
2984 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2986 if (TREE_CODE (type
) != INTEGER_TYPE
2987 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
2990 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs1 (stmt
), type1_out
,
2994 if (!is_widening_mult_rhs_p (type
, gimple_assign_rhs2 (stmt
), type2_out
,
2998 if (*type1_out
== NULL
)
3000 if (*type2_out
== NULL
|| !int_fits_type_p (*rhs1_out
, *type2_out
))
3002 *type1_out
= *type2_out
;
3005 if (*type2_out
== NULL
)
3007 if (!int_fits_type_p (*rhs2_out
, *type1_out
))
3009 *type2_out
= *type1_out
;
3012 /* Ensure that the larger of the two operands comes first. */
3013 if (TYPE_PRECISION (*type1_out
) < TYPE_PRECISION (*type2_out
))
3015 std::swap (*type1_out
, *type2_out
);
3016 std::swap (*rhs1_out
, *rhs2_out
);
3022 /* Process a single gimple statement STMT, which has a MULT_EXPR as
3023 its rhs, and try to convert it into a WIDEN_MULT_EXPR. The return
3024 value is true iff we converted the statement. */
3027 convert_mult_to_widen (gimple stmt
, gimple_stmt_iterator
*gsi
)
3029 tree lhs
, rhs1
, rhs2
, type
, type1
, type2
;
3030 enum insn_code handler
;
3031 machine_mode to_mode
, from_mode
, actual_mode
;
3033 int actual_precision
;
3034 location_t loc
= gimple_location (stmt
);
3035 bool from_unsigned1
, from_unsigned2
;
3037 lhs
= gimple_assign_lhs (stmt
);
3038 type
= TREE_TYPE (lhs
);
3039 if (TREE_CODE (type
) != INTEGER_TYPE
)
3042 if (!is_widening_mult_p (stmt
, &type1
, &rhs1
, &type2
, &rhs2
))
3045 to_mode
= TYPE_MODE (type
);
3046 from_mode
= TYPE_MODE (type1
);
3047 from_unsigned1
= TYPE_UNSIGNED (type1
);
3048 from_unsigned2
= TYPE_UNSIGNED (type2
);
3050 if (from_unsigned1
&& from_unsigned2
)
3051 op
= umul_widen_optab
;
3052 else if (!from_unsigned1
&& !from_unsigned2
)
3053 op
= smul_widen_optab
;
3055 op
= usmul_widen_optab
;
3057 handler
= find_widening_optab_handler_and_mode (op
, to_mode
, from_mode
,
3060 if (handler
== CODE_FOR_nothing
)
3062 if (op
!= smul_widen_optab
)
3064 /* We can use a signed multiply with unsigned types as long as
3065 there is a wider mode to use, or it is the smaller of the two
3066 types that is unsigned. Note that type1 >= type2, always. */
3067 if ((TYPE_UNSIGNED (type1
)
3068 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
3069 || (TYPE_UNSIGNED (type2
)
3070 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
3072 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
3073 if (GET_MODE_SIZE (to_mode
) <= GET_MODE_SIZE (from_mode
))
3077 op
= smul_widen_optab
;
3078 handler
= find_widening_optab_handler_and_mode (op
, to_mode
,
3082 if (handler
== CODE_FOR_nothing
)
3085 from_unsigned1
= from_unsigned2
= false;
3091 /* Ensure that the inputs to the handler are in the correct precison
3092 for the opcode. This will be the full mode size. */
3093 actual_precision
= GET_MODE_PRECISION (actual_mode
);
3094 if (2 * actual_precision
> TYPE_PRECISION (type
))
3096 if (actual_precision
!= TYPE_PRECISION (type1
)
3097 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
3098 rhs1
= build_and_insert_cast (gsi
, loc
,
3099 build_nonstandard_integer_type
3100 (actual_precision
, from_unsigned1
), rhs1
);
3101 if (actual_precision
!= TYPE_PRECISION (type2
)
3102 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
3103 rhs2
= build_and_insert_cast (gsi
, loc
,
3104 build_nonstandard_integer_type
3105 (actual_precision
, from_unsigned2
), rhs2
);
3107 /* Handle constants. */
3108 if (TREE_CODE (rhs1
) == INTEGER_CST
)
3109 rhs1
= fold_convert (type1
, rhs1
);
3110 if (TREE_CODE (rhs2
) == INTEGER_CST
)
3111 rhs2
= fold_convert (type2
, rhs2
);
3113 gimple_assign_set_rhs1 (stmt
, rhs1
);
3114 gimple_assign_set_rhs2 (stmt
, rhs2
);
3115 gimple_assign_set_rhs_code (stmt
, WIDEN_MULT_EXPR
);
3117 widen_mul_stats
.widen_mults_inserted
++;
3121 /* Process a single gimple statement STMT, which is found at the
3122 iterator GSI and has a either a PLUS_EXPR or a MINUS_EXPR as its
3123 rhs (given by CODE), and try to convert it into a
3124 WIDEN_MULT_PLUS_EXPR or a WIDEN_MULT_MINUS_EXPR. The return value
3125 is true iff we converted the statement. */
3128 convert_plusminus_to_widen (gimple_stmt_iterator
*gsi
, gimple stmt
,
3129 enum tree_code code
)
3131 gimple rhs1_stmt
= NULL
, rhs2_stmt
= NULL
;
3132 gimple conv1_stmt
= NULL
, conv2_stmt
= NULL
, conv_stmt
;
3133 tree type
, type1
, type2
, optype
;
3134 tree lhs
, rhs1
, rhs2
, mult_rhs1
, mult_rhs2
, add_rhs
;
3135 enum tree_code rhs1_code
= ERROR_MARK
, rhs2_code
= ERROR_MARK
;
3137 enum tree_code wmult_code
;
3138 enum insn_code handler
;
3139 machine_mode to_mode
, from_mode
, actual_mode
;
3140 location_t loc
= gimple_location (stmt
);
3141 int actual_precision
;
3142 bool from_unsigned1
, from_unsigned2
;
3144 lhs
= gimple_assign_lhs (stmt
);
3145 type
= TREE_TYPE (lhs
);
3146 if (TREE_CODE (type
) != INTEGER_TYPE
3147 && TREE_CODE (type
) != FIXED_POINT_TYPE
)
3150 if (code
== MINUS_EXPR
)
3151 wmult_code
= WIDEN_MULT_MINUS_EXPR
;
3153 wmult_code
= WIDEN_MULT_PLUS_EXPR
;
3155 rhs1
= gimple_assign_rhs1 (stmt
);
3156 rhs2
= gimple_assign_rhs2 (stmt
);
3158 if (TREE_CODE (rhs1
) == SSA_NAME
)
3160 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
3161 if (is_gimple_assign (rhs1_stmt
))
3162 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
3165 if (TREE_CODE (rhs2
) == SSA_NAME
)
3167 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
3168 if (is_gimple_assign (rhs2_stmt
))
3169 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
3172 /* Allow for one conversion statement between the multiply
3173 and addition/subtraction statement. If there are more than
3174 one conversions then we assume they would invalidate this
3175 transformation. If that's not the case then they should have
3176 been folded before now. */
3177 if (CONVERT_EXPR_CODE_P (rhs1_code
))
3179 conv1_stmt
= rhs1_stmt
;
3180 rhs1
= gimple_assign_rhs1 (rhs1_stmt
);
3181 if (TREE_CODE (rhs1
) == SSA_NAME
)
3183 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
3184 if (is_gimple_assign (rhs1_stmt
))
3185 rhs1_code
= gimple_assign_rhs_code (rhs1_stmt
);
3190 if (CONVERT_EXPR_CODE_P (rhs2_code
))
3192 conv2_stmt
= rhs2_stmt
;
3193 rhs2
= gimple_assign_rhs1 (rhs2_stmt
);
3194 if (TREE_CODE (rhs2
) == SSA_NAME
)
3196 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
3197 if (is_gimple_assign (rhs2_stmt
))
3198 rhs2_code
= gimple_assign_rhs_code (rhs2_stmt
);
3204 /* If code is WIDEN_MULT_EXPR then it would seem unnecessary to call
3205 is_widening_mult_p, but we still need the rhs returns.
3207 It might also appear that it would be sufficient to use the existing
3208 operands of the widening multiply, but that would limit the choice of
3209 multiply-and-accumulate instructions.
3211 If the widened-multiplication result has more than one uses, it is
3212 probably wiser not to do the conversion. */
3213 if (code
== PLUS_EXPR
3214 && (rhs1_code
== MULT_EXPR
|| rhs1_code
== WIDEN_MULT_EXPR
))
3216 if (!has_single_use (rhs1
)
3217 || !is_widening_mult_p (rhs1_stmt
, &type1
, &mult_rhs1
,
3218 &type2
, &mult_rhs2
))
3221 conv_stmt
= conv1_stmt
;
3223 else if (rhs2_code
== MULT_EXPR
|| rhs2_code
== WIDEN_MULT_EXPR
)
3225 if (!has_single_use (rhs2
)
3226 || !is_widening_mult_p (rhs2_stmt
, &type1
, &mult_rhs1
,
3227 &type2
, &mult_rhs2
))
3230 conv_stmt
= conv2_stmt
;
3235 to_mode
= TYPE_MODE (type
);
3236 from_mode
= TYPE_MODE (type1
);
3237 from_unsigned1
= TYPE_UNSIGNED (type1
);
3238 from_unsigned2
= TYPE_UNSIGNED (type2
);
3241 /* There's no such thing as a mixed sign madd yet, so use a wider mode. */
3242 if (from_unsigned1
!= from_unsigned2
)
3244 if (!INTEGRAL_TYPE_P (type
))
3246 /* We can use a signed multiply with unsigned types as long as
3247 there is a wider mode to use, or it is the smaller of the two
3248 types that is unsigned. Note that type1 >= type2, always. */
3250 && TYPE_PRECISION (type1
) == GET_MODE_PRECISION (from_mode
))
3252 && TYPE_PRECISION (type2
) == GET_MODE_PRECISION (from_mode
)))
3254 from_mode
= GET_MODE_WIDER_MODE (from_mode
);
3255 if (GET_MODE_SIZE (from_mode
) >= GET_MODE_SIZE (to_mode
))
3259 from_unsigned1
= from_unsigned2
= false;
3260 optype
= build_nonstandard_integer_type (GET_MODE_PRECISION (from_mode
),
3264 /* If there was a conversion between the multiply and addition
3265 then we need to make sure it fits a multiply-and-accumulate.
3266 The should be a single mode change which does not change the
3270 /* We use the original, unmodified data types for this. */
3271 tree from_type
= TREE_TYPE (gimple_assign_rhs1 (conv_stmt
));
3272 tree to_type
= TREE_TYPE (gimple_assign_lhs (conv_stmt
));
3273 int data_size
= TYPE_PRECISION (type1
) + TYPE_PRECISION (type2
);
3274 bool is_unsigned
= TYPE_UNSIGNED (type1
) && TYPE_UNSIGNED (type2
);
3276 if (TYPE_PRECISION (from_type
) > TYPE_PRECISION (to_type
))
3278 /* Conversion is a truncate. */
3279 if (TYPE_PRECISION (to_type
) < data_size
)
3282 else if (TYPE_PRECISION (from_type
) < TYPE_PRECISION (to_type
))
3284 /* Conversion is an extend. Check it's the right sort. */
3285 if (TYPE_UNSIGNED (from_type
) != is_unsigned
3286 && !(is_unsigned
&& TYPE_PRECISION (from_type
) > data_size
))
3289 /* else convert is a no-op for our purposes. */
3292 /* Verify that the machine can perform a widening multiply
3293 accumulate in this mode/signedness combination, otherwise
3294 this transformation is likely to pessimize code. */
3295 this_optab
= optab_for_tree_code (wmult_code
, optype
, optab_default
);
3296 handler
= find_widening_optab_handler_and_mode (this_optab
, to_mode
,
3297 from_mode
, 0, &actual_mode
);
3299 if (handler
== CODE_FOR_nothing
)
3302 /* Ensure that the inputs to the handler are in the correct precison
3303 for the opcode. This will be the full mode size. */
3304 actual_precision
= GET_MODE_PRECISION (actual_mode
);
3305 if (actual_precision
!= TYPE_PRECISION (type1
)
3306 || from_unsigned1
!= TYPE_UNSIGNED (type1
))
3307 mult_rhs1
= build_and_insert_cast (gsi
, loc
,
3308 build_nonstandard_integer_type
3309 (actual_precision
, from_unsigned1
),
3311 if (actual_precision
!= TYPE_PRECISION (type2
)
3312 || from_unsigned2
!= TYPE_UNSIGNED (type2
))
3313 mult_rhs2
= build_and_insert_cast (gsi
, loc
,
3314 build_nonstandard_integer_type
3315 (actual_precision
, from_unsigned2
),
3318 if (!useless_type_conversion_p (type
, TREE_TYPE (add_rhs
)))
3319 add_rhs
= build_and_insert_cast (gsi
, loc
, type
, add_rhs
);
3321 /* Handle constants. */
3322 if (TREE_CODE (mult_rhs1
) == INTEGER_CST
)
3323 mult_rhs1
= fold_convert (type1
, mult_rhs1
);
3324 if (TREE_CODE (mult_rhs2
) == INTEGER_CST
)
3325 mult_rhs2
= fold_convert (type2
, mult_rhs2
);
3327 gimple_assign_set_rhs_with_ops (gsi
, wmult_code
, mult_rhs1
, mult_rhs2
,
3329 update_stmt (gsi_stmt (*gsi
));
3330 widen_mul_stats
.maccs_inserted
++;
3334 /* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
3335 with uses in additions and subtractions to form fused multiply-add
3336 operations. Returns true if successful and MUL_STMT should be removed. */
3339 convert_mult_to_fma (gimple mul_stmt
, tree op1
, tree op2
)
3341 tree mul_result
= gimple_get_lhs (mul_stmt
);
3342 tree type
= TREE_TYPE (mul_result
);
3343 gimple use_stmt
, neguse_stmt
;
3345 use_operand_p use_p
;
3346 imm_use_iterator imm_iter
;
3348 if (FLOAT_TYPE_P (type
)
3349 && flag_fp_contract_mode
== FP_CONTRACT_OFF
)
3352 /* We don't want to do bitfield reduction ops. */
3353 if (INTEGRAL_TYPE_P (type
)
3354 && (TYPE_PRECISION (type
)
3355 != GET_MODE_PRECISION (TYPE_MODE (type
))))
3358 /* If the target doesn't support it, don't generate it. We assume that
3359 if fma isn't available then fms, fnma or fnms are not either. */
3360 if (optab_handler (fma_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
)
3363 /* If the multiplication has zero uses, it is kept around probably because
3364 of -fnon-call-exceptions. Don't optimize it away in that case,
3366 if (has_zero_uses (mul_result
))
3369 /* Make sure that the multiplication statement becomes dead after
3370 the transformation, thus that all uses are transformed to FMAs.
3371 This means we assume that an FMA operation has the same cost
3373 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, mul_result
)
3375 enum tree_code use_code
;
3376 tree result
= mul_result
;
3377 bool negate_p
= false;
3379 use_stmt
= USE_STMT (use_p
);
3381 if (is_gimple_debug (use_stmt
))
3384 /* For now restrict this operations to single basic blocks. In theory
3385 we would want to support sinking the multiplication in
3391 to form a fma in the then block and sink the multiplication to the
3393 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3396 if (!is_gimple_assign (use_stmt
))
3399 use_code
= gimple_assign_rhs_code (use_stmt
);
3401 /* A negate on the multiplication leads to FNMA. */
3402 if (use_code
== NEGATE_EXPR
)
3407 result
= gimple_assign_lhs (use_stmt
);
3409 /* Make sure the negate statement becomes dead with this
3410 single transformation. */
3411 if (!single_imm_use (gimple_assign_lhs (use_stmt
),
3412 &use_p
, &neguse_stmt
))
3415 /* Make sure the multiplication isn't also used on that stmt. */
3416 FOR_EACH_PHI_OR_STMT_USE (usep
, neguse_stmt
, iter
, SSA_OP_USE
)
3417 if (USE_FROM_PTR (usep
) == mul_result
)
3421 use_stmt
= neguse_stmt
;
3422 if (gimple_bb (use_stmt
) != gimple_bb (mul_stmt
))
3424 if (!is_gimple_assign (use_stmt
))
3427 use_code
= gimple_assign_rhs_code (use_stmt
);
3434 if (gimple_assign_rhs2 (use_stmt
) == result
)
3435 negate_p
= !negate_p
;
3440 /* FMA can only be formed from PLUS and MINUS. */
3444 /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
3445 by a MULT_EXPR that we'll visit later, we might be able to
3446 get a more profitable match with fnma.
3447 OTOH, if we don't, a negate / fma pair has likely lower latency
3448 that a mult / subtract pair. */
3449 if (use_code
== MINUS_EXPR
&& !negate_p
3450 && gimple_assign_rhs1 (use_stmt
) == result
3451 && optab_handler (fms_optab
, TYPE_MODE (type
)) == CODE_FOR_nothing
3452 && optab_handler (fnma_optab
, TYPE_MODE (type
)) != CODE_FOR_nothing
)
3454 tree rhs2
= gimple_assign_rhs2 (use_stmt
);
3456 if (TREE_CODE (rhs2
) == SSA_NAME
)
3458 gimple stmt2
= SSA_NAME_DEF_STMT (rhs2
);
3459 if (has_single_use (rhs2
)
3460 && is_gimple_assign (stmt2
)
3461 && gimple_assign_rhs_code (stmt2
) == MULT_EXPR
)
3466 /* We can't handle a * b + a * b. */
3467 if (gimple_assign_rhs1 (use_stmt
) == gimple_assign_rhs2 (use_stmt
))
3470 /* While it is possible to validate whether or not the exact form
3471 that we've recognized is available in the backend, the assumption
3472 is that the transformation is never a loss. For instance, suppose
3473 the target only has the plain FMA pattern available. Consider
3474 a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
3475 is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
3476 still have 3 operations, but in the FMA form the two NEGs are
3477 independent and could be run in parallel. */
3480 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, mul_result
)
3482 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
3483 enum tree_code use_code
;
3484 tree addop
, mulop1
= op1
, result
= mul_result
;
3485 bool negate_p
= false;
3487 if (is_gimple_debug (use_stmt
))
3490 use_code
= gimple_assign_rhs_code (use_stmt
);
3491 if (use_code
== NEGATE_EXPR
)
3493 result
= gimple_assign_lhs (use_stmt
);
3494 single_imm_use (gimple_assign_lhs (use_stmt
), &use_p
, &neguse_stmt
);
3495 gsi_remove (&gsi
, true);
3496 release_defs (use_stmt
);
3498 use_stmt
= neguse_stmt
;
3499 gsi
= gsi_for_stmt (use_stmt
);
3500 use_code
= gimple_assign_rhs_code (use_stmt
);
3504 if (gimple_assign_rhs1 (use_stmt
) == result
)
3506 addop
= gimple_assign_rhs2 (use_stmt
);
3507 /* a * b - c -> a * b + (-c) */
3508 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3509 addop
= force_gimple_operand_gsi (&gsi
,
3510 build1 (NEGATE_EXPR
,
3512 true, NULL_TREE
, true,
3517 addop
= gimple_assign_rhs1 (use_stmt
);
3518 /* a - b * c -> (-b) * c + a */
3519 if (gimple_assign_rhs_code (use_stmt
) == MINUS_EXPR
)
3520 negate_p
= !negate_p
;
3524 mulop1
= force_gimple_operand_gsi (&gsi
,
3525 build1 (NEGATE_EXPR
,
3527 true, NULL_TREE
, true,
3530 fma_stmt
= gimple_build_assign (gimple_assign_lhs (use_stmt
),
3531 FMA_EXPR
, mulop1
, op2
, addop
);
3532 gsi_replace (&gsi
, fma_stmt
, true);
3533 widen_mul_stats
.fmas_inserted
++;
3539 /* Find integer multiplications where the operands are extended from
3540 smaller types, and replace the MULT_EXPR with a WIDEN_MULT_EXPR
3541 where appropriate. */
3545 const pass_data pass_data_optimize_widening_mul
=
3547 GIMPLE_PASS
, /* type */
3548 "widening_mul", /* name */
3549 OPTGROUP_NONE
, /* optinfo_flags */
3550 TV_NONE
, /* tv_id */
3551 PROP_ssa
, /* properties_required */
3552 0, /* properties_provided */
3553 0, /* properties_destroyed */
3554 0, /* todo_flags_start */
3555 TODO_update_ssa
, /* todo_flags_finish */
3558 class pass_optimize_widening_mul
: public gimple_opt_pass
3561 pass_optimize_widening_mul (gcc::context
*ctxt
)
3562 : gimple_opt_pass (pass_data_optimize_widening_mul
, ctxt
)
3565 /* opt_pass methods: */
3566 virtual bool gate (function
*)
3568 return flag_expensive_optimizations
&& optimize
;
3571 virtual unsigned int execute (function
*);
3573 }; // class pass_optimize_widening_mul
3576 pass_optimize_widening_mul::execute (function
*fun
)
3579 bool cfg_changed
= false;
3581 memset (&widen_mul_stats
, 0, sizeof (widen_mul_stats
));
3583 FOR_EACH_BB_FN (bb
, fun
)
3585 gimple_stmt_iterator gsi
;
3587 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
);)
3589 gimple stmt
= gsi_stmt (gsi
);
3590 enum tree_code code
;
3592 if (is_gimple_assign (stmt
))
3594 code
= gimple_assign_rhs_code (stmt
);
3598 if (!convert_mult_to_widen (stmt
, &gsi
)
3599 && convert_mult_to_fma (stmt
,
3600 gimple_assign_rhs1 (stmt
),
3601 gimple_assign_rhs2 (stmt
)))
3603 gsi_remove (&gsi
, true);
3604 release_defs (stmt
);
3611 convert_plusminus_to_widen (&gsi
, stmt
, code
);
3617 else if (is_gimple_call (stmt
)
3618 && gimple_call_lhs (stmt
))
3620 tree fndecl
= gimple_call_fndecl (stmt
);
3622 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
3624 switch (DECL_FUNCTION_CODE (fndecl
))
3629 if (TREE_CODE (gimple_call_arg (stmt
, 1)) == REAL_CST
3630 && REAL_VALUES_EQUAL
3631 (TREE_REAL_CST (gimple_call_arg (stmt
, 1)),
3633 && convert_mult_to_fma (stmt
,
3634 gimple_call_arg (stmt
, 0),
3635 gimple_call_arg (stmt
, 0)))
3637 unlink_stmt_vdef (stmt
);
3638 if (gsi_remove (&gsi
, true)
3639 && gimple_purge_dead_eh_edges (bb
))
3641 release_defs (stmt
);
3654 statistics_counter_event (fun
, "widening multiplications inserted",
3655 widen_mul_stats
.widen_mults_inserted
);
3656 statistics_counter_event (fun
, "widening maccs inserted",
3657 widen_mul_stats
.maccs_inserted
);
3658 statistics_counter_event (fun
, "fused multiply-adds inserted",
3659 widen_mul_stats
.fmas_inserted
);
3661 return cfg_changed
? TODO_cleanup_cfg
: 0;
3667 make_pass_optimize_widening_mul (gcc::context
*ctxt
)
3669 return new pass_optimize_widening_mul (ctxt
);