1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* Currently, the only mini-pass in this file tries to CSE reciprocal
21 operations. These are common in sequences such as this one:
23 modulus = sqrt(x*x + y*y + z*z);
28 that can be optimized to
30 modulus = sqrt(x*x + y*y + z*z);
31 rmodulus = 1.0 / modulus;
36 We do this for loop invariant divisors, and with this pass whenever
37 we notice that a division has the same divisor multiple times.
39 Of course, like in PRE, we don't insert a division if a dominator
40 already has one. However, this cannot be done as an extension of
41 PRE for several reasons.
43 First of all, with some experiments it was found out that the
44 transformation is not always useful if there are only two divisions
45 hy the same divisor. This is probably because modern processors
46 can pipeline the divisions; on older, in-order processors it should
47 still be effective to optimize two divisions by the same number.
48 We make this a param, and it shall be called N in the remainder of
51 Second, if trapping math is active, we have less freedom on where
52 to insert divisions: we can only do so in basic blocks that already
53 contain one. (If divisions don't trap, instead, we can insert
54 divisions elsewhere, which will be in blocks that are common dominators
55 of those that have the division).
57 We really don't want to compute the reciprocal unless a division will
58 be found. To do this, we won't insert the division in a basic block
59 that has less than N divisions *post-dominating* it.
61 The algorithm constructs a subset of the dominator tree, holding the
62 blocks containing the divisions and the common dominators to them,
63 and walk it twice. The first walk is in post-order, and it annotates
64 each block with the number of divisions that post-dominate it: this
65 gives information on where divisions can be inserted profitably.
66 The second walk is in pre-order, and it inserts divisions as explained
67 above, and replaces divisions by multiplications.
69 In the best case, the cost of the pass is O(n_statements). In the
70 worst-case, the cost is due to creating the dominator tree subset,
71 with a cost of O(n_basic_blocks ^ 2); however this can only happen
72 for n_statements / n_basic_blocks statements. So, the amortized cost
73 of creating the dominator tree subset is O(n_basic_blocks) and the
74 worst-case cost of the pass is O(n_statements * n_basic_blocks).
76 More practically, the cost will be small because there are few
77 divisions, and they tend to be in the same basic block, so insert_bb
78 is called very few times.
80 If we did this using domwalk.c, an efficient implementation would have
81 to work on all the variables in a single pass, because we could not
82 work on just a subset of the dominator tree, as we do now, and the
83 cost would also be something like O(n_statements * n_basic_blocks).
84 The data structures would be more complex in order to work on all the
85 variables in a single pass. */
89 #include "coretypes.h"
93 #include "tree-flow.h"
96 #include "tree-pass.h"
97 #include "alloc-pool.h"
98 #include "basic-block.h"
100 #include "diagnostic.h"
105 /* This structure represents one basic block that either computes a
106 division, or is a common dominator for basic block that compute a
109 /* The basic block represented by this structure. */
112 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
116 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
117 was inserted in BB. */
118 gimple recip_def_stmt
;
120 /* Pointer to a list of "struct occurrence"s for blocks dominated
122 struct occurrence
*children
;
124 /* Pointer to the next "struct occurrence"s in the list of blocks
125 sharing a common dominator. */
126 struct occurrence
*next
;
128 /* The number of divisions that are in BB before compute_merit. The
129 number of divisions that are in BB or post-dominate it after
133 /* True if the basic block has a division, false if it is a common
134 dominator for basic blocks that do. If it is false and trapping
135 math is active, BB is not a candidate for inserting a reciprocal. */
136 bool bb_has_division
;
140 /* The instance of "struct occurrence" representing the highest
141 interesting block in the dominator tree. */
142 static struct occurrence
*occ_head
;
144 /* Allocation pool for getting instances of "struct occurrence". */
145 static alloc_pool occ_pool
;
149 /* Allocate and return a new struct occurrence for basic block BB, and
150 whose children list is headed by CHILDREN. */
151 static struct occurrence
*
152 occ_new (basic_block bb
, struct occurrence
*children
)
154 struct occurrence
*occ
;
156 bb
->aux
= occ
= (struct occurrence
*) pool_alloc (occ_pool
);
157 memset (occ
, 0, sizeof (struct occurrence
));
160 occ
->children
= children
;
165 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
166 list of "struct occurrence"s, one per basic block, having IDOM as
167 their common dominator.
169 We try to insert NEW_OCC as deep as possible in the tree, and we also
170 insert any other block that is a common dominator for BB and one
171 block already in the tree. */
174 insert_bb (struct occurrence
*new_occ
, basic_block idom
,
175 struct occurrence
**p_head
)
177 struct occurrence
*occ
, **p_occ
;
179 for (p_occ
= p_head
; (occ
= *p_occ
) != NULL
; )
181 basic_block bb
= new_occ
->bb
, occ_bb
= occ
->bb
;
182 basic_block dom
= nearest_common_dominator (CDI_DOMINATORS
, occ_bb
, bb
);
185 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
188 occ
->next
= new_occ
->children
;
189 new_occ
->children
= occ
;
191 /* Try the next block (it may as well be dominated by BB). */
194 else if (dom
== occ_bb
)
196 /* OCC_BB dominates BB. Tail recurse to look deeper. */
197 insert_bb (new_occ
, dom
, &occ
->children
);
201 else if (dom
!= idom
)
203 gcc_assert (!dom
->aux
);
205 /* There is a dominator between IDOM and BB, add it and make
206 two children out of NEW_OCC and OCC. First, remove OCC from
212 /* None of the previous blocks has DOM as a dominator: if we tail
213 recursed, we would reexamine them uselessly. Just switch BB with
214 DOM, and go on looking for blocks dominated by DOM. */
215 new_occ
= occ_new (dom
, new_occ
);
220 /* Nothing special, go on with the next element. */
225 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
226 new_occ
->next
= *p_head
;
230 /* Register that we found a division in BB. */
233 register_division_in (basic_block bb
)
235 struct occurrence
*occ
;
237 occ
= (struct occurrence
*) bb
->aux
;
240 occ
= occ_new (bb
, NULL
);
241 insert_bb (occ
, ENTRY_BLOCK_PTR
, &occ_head
);
244 occ
->bb_has_division
= true;
245 occ
->num_divisions
++;
249 /* Compute the number of divisions that postdominate each block in OCC and
253 compute_merit (struct occurrence
*occ
)
255 struct occurrence
*occ_child
;
256 basic_block dom
= occ
->bb
;
258 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
261 if (occ_child
->children
)
262 compute_merit (occ_child
);
265 bb
= single_noncomplex_succ (dom
);
269 if (dominated_by_p (CDI_POST_DOMINATORS
, bb
, occ_child
->bb
))
270 occ
->num_divisions
+= occ_child
->num_divisions
;
275 /* Return whether USE_STMT is a floating-point division by DEF. */
277 is_division_by (gimple use_stmt
, tree def
)
279 return is_gimple_assign (use_stmt
)
280 && gimple_assign_rhs_code (use_stmt
) == RDIV_EXPR
281 && gimple_assign_rhs2 (use_stmt
) == def
282 /* Do not recognize x / x as valid division, as we are getting
283 confused later by replacing all immediate uses x in such
285 && gimple_assign_rhs1 (use_stmt
) != def
;
288 /* Walk the subset of the dominator tree rooted at OCC, setting the
289 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
290 the given basic block. The field may be left NULL, of course,
291 if it is not possible or profitable to do the optimization.
293 DEF_BSI is an iterator pointing at the statement defining DEF.
294 If RECIP_DEF is set, a dominator already has a computation that can
298 insert_reciprocals (gimple_stmt_iterator
*def_gsi
, struct occurrence
*occ
,
299 tree def
, tree recip_def
, int threshold
)
303 gimple_stmt_iterator gsi
;
304 struct occurrence
*occ_child
;
307 && (occ
->bb_has_division
|| !flag_trapping_math
)
308 && occ
->num_divisions
>= threshold
)
310 /* Make a variable with the replacement and substitute it. */
311 type
= TREE_TYPE (def
);
312 recip_def
= make_rename_temp (type
, "reciptmp");
313 new_stmt
= gimple_build_assign_with_ops (RDIV_EXPR
, recip_def
,
314 build_one_cst (type
), def
);
316 if (occ
->bb_has_division
)
318 /* Case 1: insert before an existing division. */
319 gsi
= gsi_after_labels (occ
->bb
);
320 while (!gsi_end_p (gsi
) && !is_division_by (gsi_stmt (gsi
), def
))
323 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
325 else if (def_gsi
&& occ
->bb
== def_gsi
->bb
)
327 /* Case 2: insert right after the definition. Note that this will
328 never happen if the definition statement can throw, because in
329 that case the sole successor of the statement's basic block will
330 dominate all the uses as well. */
331 gsi_insert_after (def_gsi
, new_stmt
, GSI_NEW_STMT
);
335 /* Case 3: insert in a basic block not containing defs/uses. */
336 gsi
= gsi_after_labels (occ
->bb
);
337 gsi_insert_before (&gsi
, new_stmt
, GSI_SAME_STMT
);
340 occ
->recip_def_stmt
= new_stmt
;
343 occ
->recip_def
= recip_def
;
344 for (occ_child
= occ
->children
; occ_child
; occ_child
= occ_child
->next
)
345 insert_reciprocals (def_gsi
, occ_child
, def
, recip_def
, threshold
);
349 /* Replace the division at USE_P with a multiplication by the reciprocal, if
353 replace_reciprocal (use_operand_p use_p
)
355 gimple use_stmt
= USE_STMT (use_p
);
356 basic_block bb
= gimple_bb (use_stmt
);
357 struct occurrence
*occ
= (struct occurrence
*) bb
->aux
;
359 if (optimize_bb_for_speed_p (bb
)
360 && occ
->recip_def
&& use_stmt
!= occ
->recip_def_stmt
)
362 gimple_assign_set_rhs_code (use_stmt
, MULT_EXPR
);
363 SET_USE (use_p
, occ
->recip_def
);
364 fold_stmt_inplace (use_stmt
);
365 update_stmt (use_stmt
);
370 /* Free OCC and return one more "struct occurrence" to be freed. */
372 static struct occurrence
*
373 free_bb (struct occurrence
*occ
)
375 struct occurrence
*child
, *next
;
377 /* First get the two pointers hanging off OCC. */
379 child
= occ
->children
;
381 pool_free (occ_pool
, occ
);
383 /* Now ensure that we don't recurse unless it is necessary. */
389 next
= free_bb (next
);
396 /* Look for floating-point divisions among DEF's uses, and try to
397 replace them by multiplications with the reciprocal. Add
398 as many statements computing the reciprocal as needed.
400 DEF must be a GIMPLE register of a floating-point type. */
403 execute_cse_reciprocals_1 (gimple_stmt_iterator
*def_gsi
, tree def
)
406 imm_use_iterator use_iter
;
407 struct occurrence
*occ
;
408 int count
= 0, threshold
;
410 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def
)) && is_gimple_reg (def
));
412 FOR_EACH_IMM_USE_FAST (use_p
, use_iter
, def
)
414 gimple use_stmt
= USE_STMT (use_p
);
415 if (is_division_by (use_stmt
, def
))
417 register_division_in (gimple_bb (use_stmt
));
422 /* Do the expensive part only if we can hope to optimize something. */
423 threshold
= targetm
.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def
)));
424 if (count
>= threshold
)
427 for (occ
= occ_head
; occ
; occ
= occ
->next
)
430 insert_reciprocals (def_gsi
, occ
, def
, NULL
, threshold
);
433 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, def
)
435 if (is_division_by (use_stmt
, def
))
437 FOR_EACH_IMM_USE_ON_STMT (use_p
, use_iter
)
438 replace_reciprocal (use_p
);
443 for (occ
= occ_head
; occ
; )
450 gate_cse_reciprocals (void)
452 return optimize
&& flag_reciprocal_math
;
455 /* Go through all the floating-point SSA_NAMEs, and call
456 execute_cse_reciprocals_1 on each of them. */
458 execute_cse_reciprocals (void)
463 occ_pool
= create_alloc_pool ("dominators for recip",
464 sizeof (struct occurrence
),
465 n_basic_blocks
/ 3 + 1);
467 calculate_dominance_info (CDI_DOMINATORS
);
468 calculate_dominance_info (CDI_POST_DOMINATORS
);
470 #ifdef ENABLE_CHECKING
472 gcc_assert (!bb
->aux
);
475 for (arg
= DECL_ARGUMENTS (cfun
->decl
); arg
; arg
= TREE_CHAIN (arg
))
476 if (gimple_default_def (cfun
, arg
)
477 && FLOAT_TYPE_P (TREE_TYPE (arg
))
478 && is_gimple_reg (arg
))
479 execute_cse_reciprocals_1 (NULL
, gimple_default_def (cfun
, arg
));
483 gimple_stmt_iterator gsi
;
487 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
489 phi
= gsi_stmt (gsi
);
490 def
= PHI_RESULT (phi
);
491 if (FLOAT_TYPE_P (TREE_TYPE (def
))
492 && is_gimple_reg (def
))
493 execute_cse_reciprocals_1 (NULL
, def
);
496 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
498 gimple stmt
= gsi_stmt (gsi
);
500 if (gimple_has_lhs (stmt
)
501 && (def
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_DEF
)) != NULL
502 && FLOAT_TYPE_P (TREE_TYPE (def
))
503 && TREE_CODE (def
) == SSA_NAME
)
504 execute_cse_reciprocals_1 (&gsi
, def
);
507 if (optimize_bb_for_size_p (bb
))
510 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
511 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
513 gimple stmt
= gsi_stmt (gsi
);
516 if (is_gimple_assign (stmt
)
517 && gimple_assign_rhs_code (stmt
) == RDIV_EXPR
)
519 tree arg1
= gimple_assign_rhs2 (stmt
);
522 if (TREE_CODE (arg1
) != SSA_NAME
)
525 stmt1
= SSA_NAME_DEF_STMT (arg1
);
527 if (is_gimple_call (stmt1
)
528 && gimple_call_lhs (stmt1
)
529 && (fndecl
= gimple_call_fndecl (stmt1
))
530 && (DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
531 || DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
))
533 enum built_in_function code
;
538 code
= DECL_FUNCTION_CODE (fndecl
);
539 md_code
= DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_MD
;
541 fndecl
= targetm
.builtin_reciprocal (code
, md_code
, false);
545 /* Check that all uses of the SSA name are divisions,
546 otherwise replacing the defining statement will do
549 FOR_EACH_IMM_USE_FAST (use_p
, ui
, arg1
)
551 gimple stmt2
= USE_STMT (use_p
);
552 if (is_gimple_debug (stmt2
))
554 if (!is_gimple_assign (stmt2
)
555 || gimple_assign_rhs_code (stmt2
) != RDIV_EXPR
556 || gimple_assign_rhs1 (stmt2
) == arg1
557 || gimple_assign_rhs2 (stmt2
) != arg1
)
566 gimple_call_set_fndecl (stmt1
, fndecl
);
569 FOR_EACH_IMM_USE_STMT (stmt
, ui
, arg1
)
571 gimple_assign_set_rhs_code (stmt
, MULT_EXPR
);
572 fold_stmt_inplace (stmt
);
580 free_dominance_info (CDI_DOMINATORS
);
581 free_dominance_info (CDI_POST_DOMINATORS
);
582 free_alloc_pool (occ_pool
);
586 struct gimple_opt_pass pass_cse_reciprocals
=
591 gate_cse_reciprocals
, /* gate */
592 execute_cse_reciprocals
, /* execute */
595 0, /* static_pass_number */
597 PROP_ssa
, /* properties_required */
598 0, /* properties_provided */
599 0, /* properties_destroyed */
600 0, /* todo_flags_start */
601 TODO_dump_func
| TODO_update_ssa
| TODO_verify_ssa
602 | TODO_verify_stmts
/* todo_flags_finish */
606 /* Records an occurrence at statement USE_STMT in the vector of trees
607 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
608 is not yet initialized. Returns true if the occurrence was pushed on
609 the vector. Adjusts *TOP_BB to be the basic block dominating all
610 statements in the vector. */
613 maybe_record_sincos (VEC(gimple
, heap
) **stmts
,
614 basic_block
*top_bb
, gimple use_stmt
)
616 basic_block use_bb
= gimple_bb (use_stmt
);
618 && (*top_bb
== use_bb
619 || dominated_by_p (CDI_DOMINATORS
, use_bb
, *top_bb
)))
620 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
622 || dominated_by_p (CDI_DOMINATORS
, *top_bb
, use_bb
))
624 VEC_safe_push (gimple
, heap
, *stmts
, use_stmt
);
633 /* Look for sin, cos and cexpi calls with the same argument NAME and
634 create a single call to cexpi CSEing the result in this case.
635 We first walk over all immediate uses of the argument collecting
636 statements that we can CSE in a vector and in a second pass replace
637 the statement rhs with a REALPART or IMAGPART expression on the
638 result of the cexpi call we insert before the use statement that
639 dominates all other candidates. */
642 execute_cse_sincos_1 (tree name
)
644 gimple_stmt_iterator gsi
;
645 imm_use_iterator use_iter
;
646 tree fndecl
, res
, type
;
647 gimple def_stmt
, use_stmt
, stmt
;
648 int seen_cos
= 0, seen_sin
= 0, seen_cexpi
= 0;
649 VEC(gimple
, heap
) *stmts
= NULL
;
650 basic_block top_bb
= NULL
;
653 type
= TREE_TYPE (name
);
654 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, name
)
656 if (gimple_code (use_stmt
) != GIMPLE_CALL
657 || !gimple_call_lhs (use_stmt
)
658 || !(fndecl
= gimple_call_fndecl (use_stmt
))
659 || DECL_BUILT_IN_CLASS (fndecl
) != BUILT_IN_NORMAL
)
662 switch (DECL_FUNCTION_CODE (fndecl
))
664 CASE_FLT_FN (BUILT_IN_COS
):
665 seen_cos
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
668 CASE_FLT_FN (BUILT_IN_SIN
):
669 seen_sin
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
672 CASE_FLT_FN (BUILT_IN_CEXPI
):
673 seen_cexpi
|= maybe_record_sincos (&stmts
, &top_bb
, use_stmt
) ? 1 : 0;
680 if (seen_cos
+ seen_sin
+ seen_cexpi
<= 1)
682 VEC_free(gimple
, heap
, stmts
);
686 /* Simply insert cexpi at the beginning of top_bb but not earlier than
687 the name def statement. */
688 fndecl
= mathfn_built_in (type
, BUILT_IN_CEXPI
);
691 res
= make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl
)), "sincostmp");
692 stmt
= gimple_build_call (fndecl
, 1, name
);
693 gimple_call_set_lhs (stmt
, res
);
695 def_stmt
= SSA_NAME_DEF_STMT (name
);
696 if (!SSA_NAME_IS_DEFAULT_DEF (name
)
697 && gimple_code (def_stmt
) != GIMPLE_PHI
698 && gimple_bb (def_stmt
) == top_bb
)
700 gsi
= gsi_for_stmt (def_stmt
);
701 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
705 gsi
= gsi_after_labels (top_bb
);
706 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
710 /* And adjust the recorded old call sites. */
711 for (i
= 0; VEC_iterate(gimple
, stmts
, i
, use_stmt
); ++i
)
714 fndecl
= gimple_call_fndecl (use_stmt
);
716 switch (DECL_FUNCTION_CODE (fndecl
))
718 CASE_FLT_FN (BUILT_IN_COS
):
719 rhs
= fold_build1 (REALPART_EXPR
, type
, res
);
722 CASE_FLT_FN (BUILT_IN_SIN
):
723 rhs
= fold_build1 (IMAGPART_EXPR
, type
, res
);
726 CASE_FLT_FN (BUILT_IN_CEXPI
):
734 /* Replace call with a copy. */
735 stmt
= gimple_build_assign (gimple_call_lhs (use_stmt
), rhs
);
737 gsi
= gsi_for_stmt (use_stmt
);
738 gsi_insert_after (&gsi
, stmt
, GSI_SAME_STMT
);
739 gsi_remove (&gsi
, true);
742 VEC_free(gimple
, heap
, stmts
);
745 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
746 on the SSA_NAME argument of each of them. */
749 execute_cse_sincos (void)
753 calculate_dominance_info (CDI_DOMINATORS
);
757 gimple_stmt_iterator gsi
;
759 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
761 gimple stmt
= gsi_stmt (gsi
);
764 if (is_gimple_call (stmt
)
765 && gimple_call_lhs (stmt
)
766 && (fndecl
= gimple_call_fndecl (stmt
))
767 && DECL_BUILT_IN_CLASS (fndecl
) == BUILT_IN_NORMAL
)
771 switch (DECL_FUNCTION_CODE (fndecl
))
773 CASE_FLT_FN (BUILT_IN_COS
):
774 CASE_FLT_FN (BUILT_IN_SIN
):
775 CASE_FLT_FN (BUILT_IN_CEXPI
):
776 arg
= gimple_call_arg (stmt
, 0);
777 if (TREE_CODE (arg
) == SSA_NAME
)
778 execute_cse_sincos_1 (arg
);
787 free_dominance_info (CDI_DOMINATORS
);
792 gate_cse_sincos (void)
794 /* Make sure we have either sincos or cexp. */
795 return (TARGET_HAS_SINCOS
796 || TARGET_C99_FUNCTIONS
)
800 struct gimple_opt_pass pass_cse_sincos
=
805 gate_cse_sincos
, /* gate */
806 execute_cse_sincos
, /* execute */
809 0, /* static_pass_number */
811 PROP_ssa
, /* properties_required */
812 0, /* properties_provided */
813 0, /* properties_destroyed */
814 0, /* todo_flags_start */
815 TODO_dump_func
| TODO_update_ssa
| TODO_verify_ssa
816 | TODO_verify_stmts
/* todo_flags_finish */
820 /* A symbolic number is used to detect byte permutation and selection
821 patterns. Therefore the field N contains an artificial number
822 consisting of byte size markers:
824 0 - byte has the value 0
825 1..size - byte contains the content of the byte
826 number indexed with that value minus one */
828 struct symbolic_number
{
829 unsigned HOST_WIDEST_INT n
;
833 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
834 number N. Return false if the requested operation is not permitted
835 on a symbolic number. */
838 do_shift_rotate (enum tree_code code
,
839 struct symbolic_number
*n
,
845 /* Zero out the extra bits of N in order to avoid them being shifted
846 into the significant bits. */
847 if (n
->size
< (int)sizeof (HOST_WIDEST_INT
))
848 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << (n
->size
* BITS_PER_UNIT
)) - 1;
859 n
->n
= (n
->n
<< count
) | (n
->n
>> ((n
->size
* BITS_PER_UNIT
) - count
));
862 n
->n
= (n
->n
>> count
) | (n
->n
<< ((n
->size
* BITS_PER_UNIT
) - count
));
870 /* Perform sanity checking for the symbolic number N and the gimple
874 verify_symbolic_number_p (struct symbolic_number
*n
, gimple stmt
)
878 lhs_type
= gimple_expr_type (stmt
);
880 if (TREE_CODE (lhs_type
) != INTEGER_TYPE
)
883 if (TYPE_PRECISION (lhs_type
) != n
->size
* BITS_PER_UNIT
)
889 /* find_bswap_1 invokes itself recursively with N and tries to perform
890 the operation given by the rhs of STMT on the result. If the
891 operation could successfully be executed the function returns the
892 tree expression of the source operand and NULL otherwise. */
895 find_bswap_1 (gimple stmt
, struct symbolic_number
*n
, int limit
)
898 tree rhs1
, rhs2
= NULL
;
899 gimple rhs1_stmt
, rhs2_stmt
;
901 enum gimple_rhs_class rhs_class
;
903 if (!limit
|| !is_gimple_assign (stmt
))
906 rhs1
= gimple_assign_rhs1 (stmt
);
908 if (TREE_CODE (rhs1
) != SSA_NAME
)
911 code
= gimple_assign_rhs_code (stmt
);
912 rhs_class
= gimple_assign_rhs_class (stmt
);
913 rhs1_stmt
= SSA_NAME_DEF_STMT (rhs1
);
915 if (rhs_class
== GIMPLE_BINARY_RHS
)
916 rhs2
= gimple_assign_rhs2 (stmt
);
918 /* Handle unary rhs and binary rhs with integer constants as second
921 if (rhs_class
== GIMPLE_UNARY_RHS
922 || (rhs_class
== GIMPLE_BINARY_RHS
923 && TREE_CODE (rhs2
) == INTEGER_CST
))
925 if (code
!= BIT_AND_EXPR
926 && code
!= LSHIFT_EXPR
927 && code
!= RSHIFT_EXPR
928 && code
!= LROTATE_EXPR
929 && code
!= RROTATE_EXPR
931 && code
!= CONVERT_EXPR
)
934 source_expr1
= find_bswap_1 (rhs1_stmt
, n
, limit
- 1);
936 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
937 to initialize the symbolic number. */
940 /* Set up the symbolic number N by setting each byte to a
941 value between 1 and the byte size of rhs1. The highest
942 order byte is set to 1 and the lowest order byte to
944 n
->size
= TYPE_PRECISION (TREE_TYPE (rhs1
));
945 if (n
->size
% BITS_PER_UNIT
!= 0)
947 n
->size
/= BITS_PER_UNIT
;
948 n
->n
= (sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
949 (unsigned HOST_WIDEST_INT
)0x01020304 << 32 | 0x05060708);
950 n
->n
>>= (sizeof (HOST_WIDEST_INT
) - n
->size
) * BITS_PER_UNIT
;
960 unsigned HOST_WIDEST_INT val
= widest_int_cst_value (rhs2
);
961 unsigned HOST_WIDEST_INT tmp
= val
;
963 /* Only constants masking full bytes are allowed. */
964 for (i
= 0; i
< n
->size
; i
++, tmp
>>= BITS_PER_UNIT
)
965 if ((tmp
& 0xff) != 0 && (tmp
& 0xff) != 0xff)
975 if (!do_shift_rotate (code
, n
, (int)TREE_INT_CST_LOW (rhs2
)))
982 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
983 if (type_size
% BITS_PER_UNIT
!= 0)
986 if (type_size
/ BITS_PER_UNIT
< (int)(sizeof (HOST_WIDEST_INT
)))
988 /* If STMT casts to a smaller type mask out the bits not
989 belonging to the target type. */
990 n
->size
= type_size
/ BITS_PER_UNIT
;
991 n
->n
&= ((unsigned HOST_WIDEST_INT
)1 << type_size
) - 1;
998 return verify_symbolic_number_p (n
, stmt
) ? source_expr1
: NULL
;
1001 /* Handle binary rhs. */
1003 if (rhs_class
== GIMPLE_BINARY_RHS
)
1005 struct symbolic_number n1
, n2
;
1008 if (code
!= BIT_IOR_EXPR
)
1011 if (TREE_CODE (rhs2
) != SSA_NAME
)
1014 rhs2_stmt
= SSA_NAME_DEF_STMT (rhs2
);
1019 source_expr1
= find_bswap_1 (rhs1_stmt
, &n1
, limit
- 1);
1024 source_expr2
= find_bswap_1 (rhs2_stmt
, &n2
, limit
- 1);
1026 if (source_expr1
!= source_expr2
1027 || n1
.size
!= n2
.size
)
1033 if (!verify_symbolic_number_p (n
, stmt
))
1040 return source_expr1
;
1045 /* Check if STMT completes a bswap implementation consisting of ORs,
1046 SHIFTs and ANDs. Return the source tree expression on which the
1047 byte swap is performed and NULL if no bswap was found. */
1050 find_bswap (gimple stmt
)
1052 /* The number which the find_bswap result should match in order to
1053 have a full byte swap. The insignificant bytes are masked out
1055 unsigned HOST_WIDEST_INT cmp
=
1056 sizeof (HOST_WIDEST_INT
) < 8 ? 0 :
1057 (unsigned HOST_WIDEST_INT
)0x08070605 << 32 | 0x04030201;
1059 struct symbolic_number n
;
1062 /* The last parameter determines the depth search limit. It usually
1063 correlates directly to the number of bytes to be touched. We
1064 increase that number by one here in order to also cover signed ->
1065 unsigned conversions of the src operand as can be seen in
1067 source_expr
= find_bswap_1 (stmt
, &n
,
1069 TYPE_SIZE_UNIT (gimple_expr_type (stmt
))) + 1);
1074 /* Zero out the extra bits of N and CMP. */
1075 if (n
.size
< (int)sizeof (HOST_WIDEST_INT
))
1077 unsigned HOST_WIDEST_INT mask
=
1078 ((unsigned HOST_WIDEST_INT
)1 << (n
.size
* BITS_PER_UNIT
)) - 1;
1084 /* A complete byte swap should make the symbolic number to start
1085 with the largest digit in the highest order byte. */
1092 /* Find manual byte swap implementations and turn them into a bswap
1093 builtin invokation. */
1096 execute_optimize_bswap (void)
1099 bool bswap32_p
, bswap64_p
;
1100 bool changed
= false;
1101 tree bswap32_type
= NULL_TREE
, bswap64_type
= NULL_TREE
;
1103 if (BITS_PER_UNIT
!= 8)
1106 if (sizeof (HOST_WIDEST_INT
) < 8)
1109 bswap32_p
= (built_in_decls
[BUILT_IN_BSWAP32
]
1110 && optab_handler (bswap_optab
, SImode
)->insn_code
!=
1112 bswap64_p
= (built_in_decls
[BUILT_IN_BSWAP64
]
1113 && optab_handler (bswap_optab
, DImode
)->insn_code
!=
1116 if (!bswap32_p
&& !bswap64_p
)
1119 /* Determine the argument type of the builtins. The code later on
1120 assumes that the return and argument type are the same. */
1123 tree fndecl
= built_in_decls
[BUILT_IN_BSWAP32
];
1124 bswap32_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1129 tree fndecl
= built_in_decls
[BUILT_IN_BSWAP64
];
1130 bswap64_type
= TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl
)));
1135 gimple_stmt_iterator gsi
;
1137 for (gsi
= gsi_after_labels (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1139 gimple stmt
= gsi_stmt (gsi
);
1140 tree bswap_src
, bswap_type
;
1142 tree fndecl
= NULL_TREE
;
1146 if (!is_gimple_assign (stmt
)
1147 || gimple_assign_rhs_code (stmt
) != BIT_IOR_EXPR
)
1150 type_size
= TYPE_PRECISION (gimple_expr_type (stmt
));
1157 fndecl
= built_in_decls
[BUILT_IN_BSWAP32
];
1158 bswap_type
= bswap32_type
;
1164 fndecl
= built_in_decls
[BUILT_IN_BSWAP64
];
1165 bswap_type
= bswap64_type
;
1175 bswap_src
= find_bswap (stmt
);
1182 bswap_tmp
= bswap_src
;
1184 /* Convert the src expression if necessary. */
1185 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1187 gimple convert_stmt
;
1189 bswap_tmp
= create_tmp_var (bswap_type
, "bswapsrc");
1190 add_referenced_var (bswap_tmp
);
1191 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1193 convert_stmt
= gimple_build_assign_with_ops (
1194 CONVERT_EXPR
, bswap_tmp
, bswap_src
, NULL
);
1195 gsi_insert_before (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1198 call
= gimple_build_call (fndecl
, 1, bswap_tmp
);
1200 bswap_tmp
= gimple_assign_lhs (stmt
);
1202 /* Convert the result if necessary. */
1203 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp
), bswap_type
))
1205 gimple convert_stmt
;
1207 bswap_tmp
= create_tmp_var (bswap_type
, "bswapdst");
1208 add_referenced_var (bswap_tmp
);
1209 bswap_tmp
= make_ssa_name (bswap_tmp
, NULL
);
1210 convert_stmt
= gimple_build_assign_with_ops (
1211 CONVERT_EXPR
, gimple_assign_lhs (stmt
), bswap_tmp
, NULL
);
1212 gsi_insert_after (&gsi
, convert_stmt
, GSI_SAME_STMT
);
1215 gimple_call_set_lhs (call
, bswap_tmp
);
1219 fprintf (dump_file
, "%d bit bswap implementation found at: ",
1221 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1224 gsi_insert_after (&gsi
, call
, GSI_SAME_STMT
);
1225 gsi_remove (&gsi
, true);
1229 return (changed
? TODO_dump_func
| TODO_update_ssa
| TODO_verify_ssa
1230 | TODO_verify_stmts
: 0);
1234 gate_optimize_bswap (void)
1236 return flag_expensive_optimizations
&& optimize
;
1239 struct gimple_opt_pass pass_optimize_bswap
=
1244 gate_optimize_bswap
, /* gate */
1245 execute_optimize_bswap
, /* execute */
1248 0, /* static_pass_number */
1249 TV_NONE
, /* tv_id */
1250 PROP_ssa
, /* properties_required */
1251 0, /* properties_provided */
1252 0, /* properties_destroyed */
1253 0, /* todo_flags_start */
1254 0 /* todo_flags_finish */