1 /* Global, SSA-based optimizations using mathematical identities.
2 Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* Currently, the only mini-pass in this file tries to CSE reciprocal
22 operations. These are common in sequences such as this one:
24 modulus = sqrt(x*x + y*y + z*z);
29 that can be optimized to
31 modulus = sqrt(x*x + y*y + z*z);
32 rmodulus = 1.0 / modulus;
37 We do this for loop invariant divisors, and with this pass whenever
38 we notice that a division has the same divisor multiple times.
40 Of course, like in PRE, we don't insert a division if a dominator
41 already has one. However, this cannot be done as an extension of
42 PRE for several reasons.
44 First of all, with some experiments it was found out that the
45 transformation is not always useful if there are only two divisions
46 hy the same divisor. This is probably because modern processors
47 can pipeline the divisions; on older, in-order processors it should
48 still be effective to optimize two divisions by the same number.
49 We make this a param, and it shall be called N in the remainder of
52 Second, if trapping math is active, we have less freedom on where
53 to insert divisions: we can only do so in basic blocks that already
54 contain one. (If divisions don't trap, instead, we can insert
55 divisions elsewhere, which will be in blocks that are common dominators
56 of those that have the division).
58 We really don't want to compute the reciprocal unless a division will
59 be found. To do this, we won't insert the division in a basic block
60 that has less than N divisions *post-dominating* it.
62 The algorithm constructs a subset of the dominator tree, holding the
63 blocks containing the divisions and the common dominators to them,
64 and walk it twice. The first walk is in post-order, and it annotates
65 each block with the number of divisions that post-dominate it: this
66 gives information on where divisions can be inserted profitably.
67 The second walk is in pre-order, and it inserts divisions as explained
68 above, and replaces divisions by multiplications.
70 In the best case, the cost of the pass is O(n_statements). In the
71 worst-case, the cost is due to creating the dominator tree subset,
72 with a cost of O(n_basic_blocks ^ 2); however this can only happen
73 for n_statements / n_basic_blocks statements. So, the amortized cost
74 of creating the dominator tree subset is O(n_basic_blocks) and the
75 worst-case cost of the pass is O(n_statements * n_basic_blocks).
77 More practically, the cost will be small because there are few
78 divisions, and they tend to be in the same basic block, so insert_bb
79 is called very few times.
81 If we did this using domwalk.c, an efficient implementation would have
82 to work on all the variables in a single pass, because we could not
83 work on just a subset of the dominator tree, as we do now, and the
84 cost would also be something like O(n_statements * n_basic_blocks).
85 The data structures would be more complex in order to work on all the
86 variables in a single pass. */
90 #include "coretypes.h"
94 #include "tree-flow.h"
97 #include "tree-pass.h"
98 #include "alloc-pool.h"
99 #include "basic-block.h"
101 #include "diagnostic.h"
106 /* This structure represents one basic block that either computes a
107 division, or is a common dominator for basic block that compute a
110 /* The basic block represented by this structure. */
113 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
117 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that
118 was inserted in BB. */
119 gimple recip_def_stmt;
121 /* Pointer to a list of "struct occurrence"s for blocks dominated
123 struct occurrence *children;
125 /* Pointer to the next "struct occurrence"s in the list of blocks
126 sharing a common dominator. */
127 struct occurrence *next;
129 /* The number of divisions that are in BB before compute_merit. The
130 number of divisions that are in BB or post-dominate it after
134 /* True if the basic block has a division, false if it is a common
135 dominator for basic blocks that do. If it is false and trapping
136 math is active, BB is not a candidate for inserting a reciprocal. */
137 bool bb_has_division;
141 /* The instance of "struct occurrence" representing the highest
142 interesting block in the dominator tree. */
143 static struct occurrence *occ_head;
145 /* Allocation pool for getting instances of "struct occurrence". */
146 static alloc_pool occ_pool;
150 /* Allocate and return a new struct occurrence for basic block BB, and
151 whose children list is headed by CHILDREN. */
152 static struct occurrence *
153 occ_new (basic_block bb, struct occurrence *children)
155 struct occurrence *occ;
157 bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
158 memset (occ, 0, sizeof (struct occurrence));
161 occ->children = children;
166 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a
167 list of "struct occurrence"s, one per basic block, having IDOM as
168 their common dominator.
170 We try to insert NEW_OCC as deep as possible in the tree, and we also
171 insert any other block that is a common dominator for BB and one
172 block already in the tree. */
175 insert_bb (struct occurrence *new_occ, basic_block idom,
176 struct occurrence **p_head)
178 struct occurrence *occ, **p_occ;
180 for (p_occ = p_head; (occ = *p_occ) != NULL; )
182 basic_block bb = new_occ->bb, occ_bb = occ->bb;
183 basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
186 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC
189 occ->next = new_occ->children;
190 new_occ->children = occ;
192 /* Try the next block (it may as well be dominated by BB). */
195 else if (dom == occ_bb)
197 /* OCC_BB dominates BB. Tail recurse to look deeper. */
198 insert_bb (new_occ, dom, &occ->children);
202 else if (dom != idom)
204 gcc_assert (!dom->aux);
206 /* There is a dominator between IDOM and BB, add it and make
207 two children out of NEW_OCC and OCC. First, remove OCC from
213 /* None of the previous blocks has DOM as a dominator: if we tail
214 recursed, we would reexamine them uselessly. Just switch BB with
215 DOM, and go on looking for blocks dominated by DOM. */
216 new_occ = occ_new (dom, new_occ);
221 /* Nothing special, go on with the next element. */
226 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */
227 new_occ->next = *p_head;
231 /* Register that we found a division in BB. */
234 register_division_in (basic_block bb)
236 struct occurrence *occ;
238 occ = (struct occurrence *) bb->aux;
241 occ = occ_new (bb, NULL);
242 insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
245 occ->bb_has_division = true;
246 occ->num_divisions++;
250 /* Compute the number of divisions that postdominate each block in OCC and
254 compute_merit (struct occurrence *occ)
256 struct occurrence *occ_child;
257 basic_block dom = occ->bb;
259 for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
262 if (occ_child->children)
263 compute_merit (occ_child);
266 bb = single_noncomplex_succ (dom);
270 if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
271 occ->num_divisions += occ_child->num_divisions;
276 /* Return whether USE_STMT is a floating-point division by DEF. */
278 is_division_by (gimple use_stmt, tree def)
280 return is_gimple_assign (use_stmt)
281 && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
282 && gimple_assign_rhs2 (use_stmt) == def
283 /* Do not recognize x / x as valid division, as we are getting
284 confused later by replacing all immediate uses x in such
286 && gimple_assign_rhs1 (use_stmt) != def;
289 /* Walk the subset of the dominator tree rooted at OCC, setting the
290 RECIP_DEF field to a definition of 1.0 / DEF that can be used in
291 the given basic block. The field may be left NULL, of course,
292 if it is not possible or profitable to do the optimization.
294 DEF_BSI is an iterator pointing at the statement defining DEF.
295 If RECIP_DEF is set, a dominator already has a computation that can
299 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ,
300 tree def, tree recip_def, int threshold)
304 gimple_stmt_iterator gsi;
305 struct occurrence *occ_child;
308 && (occ->bb_has_division || !flag_trapping_math)
309 && occ->num_divisions >= threshold)
311 /* Make a variable with the replacement and substitute it. */
312 type = TREE_TYPE (def);
313 recip_def = make_rename_temp (type, "reciptmp");
314 new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
315 build_one_cst (type), def);
317 if (occ->bb_has_division)
319 /* Case 1: insert before an existing division. */
320 gsi = gsi_after_labels (occ->bb);
321 while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def))
324 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
326 else if (def_gsi && occ->bb == def_gsi->bb)
328 /* Case 2: insert right after the definition. Note that this will
329 never happen if the definition statement can throw, because in
330 that case the sole successor of the statement's basic block will
331 dominate all the uses as well. */
332 gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
336 /* Case 3: insert in a basic block not containing defs/uses. */
337 gsi = gsi_after_labels (occ->bb);
338 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
341 occ->recip_def_stmt = new_stmt;
344 occ->recip_def = recip_def;
345 for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
346 insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold);
350 /* Replace the division at USE_P with a multiplication by the reciprocal, if
354 replace_reciprocal (use_operand_p use_p)
356 gimple use_stmt = USE_STMT (use_p);
357 basic_block bb = gimple_bb (use_stmt);
358 struct occurrence *occ = (struct occurrence *) bb->aux;
360 if (optimize_bb_for_speed_p (bb)
361 && occ->recip_def && use_stmt != occ->recip_def_stmt)
363 gimple_assign_set_rhs_code (use_stmt, MULT_EXPR);
364 SET_USE (use_p, occ->recip_def);
365 fold_stmt_inplace (use_stmt);
366 update_stmt (use_stmt);
371 /* Free OCC and return one more "struct occurrence" to be freed. */
373 static struct occurrence *
374 free_bb (struct occurrence *occ)
376 struct occurrence *child, *next;
378 /* First get the two pointers hanging off OCC. */
380 child = occ->children;
382 pool_free (occ_pool, occ);
384 /* Now ensure that we don't recurse unless it is necessary. */
390 next = free_bb (next);
397 /* Look for floating-point divisions among DEF's uses, and try to
398 replace them by multiplications with the reciprocal. Add
399 as many statements computing the reciprocal as needed.
401 DEF must be a GIMPLE register of a floating-point type. */
404 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def)
407 imm_use_iterator use_iter;
408 struct occurrence *occ;
409 int count = 0, threshold;
411 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
413 FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
415 gimple use_stmt = USE_STMT (use_p);
416 if (is_division_by (use_stmt, def))
418 register_division_in (gimple_bb (use_stmt));
423 /* Do the expensive part only if we can hope to optimize something. */
424 threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
425 if (count >= threshold)
428 for (occ = occ_head; occ; occ = occ->next)
431 insert_reciprocals (def_gsi, occ, def, NULL, threshold);
434 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def)
436 if (is_division_by (use_stmt, def))
438 FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter)
439 replace_reciprocal (use_p);
444 for (occ = occ_head; occ; )
451 gate_cse_reciprocals (void)
453 return optimize && flag_reciprocal_math;
456 /* Go through all the floating-point SSA_NAMEs, and call
457 execute_cse_reciprocals_1 on each of them. */
459 execute_cse_reciprocals (void)
464 occ_pool = create_alloc_pool ("dominators for recip",
465 sizeof (struct occurrence),
466 n_basic_blocks / 3 + 1);
468 calculate_dominance_info (CDI_DOMINATORS);
469 calculate_dominance_info (CDI_POST_DOMINATORS);
471 #ifdef ENABLE_CHECKING
473 gcc_assert (!bb->aux);
476 for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
477 if (gimple_default_def (cfun, arg)
478 && FLOAT_TYPE_P (TREE_TYPE (arg))
479 && is_gimple_reg (arg))
480 execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg));
484 gimple_stmt_iterator gsi;
488 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
490 phi = gsi_stmt (gsi);
491 def = PHI_RESULT (phi);
492 if (FLOAT_TYPE_P (TREE_TYPE (def))
493 && is_gimple_reg (def))
494 execute_cse_reciprocals_1 (NULL, def);
497 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
499 gimple stmt = gsi_stmt (gsi);
501 if (gimple_has_lhs (stmt)
502 && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
503 && FLOAT_TYPE_P (TREE_TYPE (def))
504 && TREE_CODE (def) == SSA_NAME)
505 execute_cse_reciprocals_1 (&gsi, def);
508 if (optimize_bb_for_size_p (bb))
511 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
512 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
514 gimple stmt = gsi_stmt (gsi);
517 if (is_gimple_assign (stmt)
518 && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
520 tree arg1 = gimple_assign_rhs2 (stmt);
523 if (TREE_CODE (arg1) != SSA_NAME)
526 stmt1 = SSA_NAME_DEF_STMT (arg1);
528 if (is_gimple_call (stmt1)
529 && gimple_call_lhs (stmt1)
530 && (fndecl = gimple_call_fndecl (stmt1))
531 && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
532 || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD))
534 enum built_in_function code;
539 code = DECL_FUNCTION_CODE (fndecl);
540 md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
542 fndecl = targetm.builtin_reciprocal (code, md_code, false);
546 /* Check that all uses of the SSA name are divisions,
547 otherwise replacing the defining statement will do
550 FOR_EACH_IMM_USE_FAST (use_p, ui, arg1)
552 gimple stmt2 = USE_STMT (use_p);
553 if (is_gimple_debug (stmt2))
555 if (!is_gimple_assign (stmt2)
556 || gimple_assign_rhs_code (stmt2) != RDIV_EXPR
557 || gimple_assign_rhs1 (stmt2) == arg1
558 || gimple_assign_rhs2 (stmt2) != arg1)
567 gimple_replace_lhs (stmt1, arg1);
568 gimple_call_set_fndecl (stmt1, fndecl);
571 FOR_EACH_IMM_USE_STMT (stmt, ui, arg1)
573 gimple_assign_set_rhs_code (stmt, MULT_EXPR);
574 fold_stmt_inplace (stmt);
582 free_dominance_info (CDI_DOMINATORS);
583 free_dominance_info (CDI_POST_DOMINATORS);
584 free_alloc_pool (occ_pool);
588 struct gimple_opt_pass pass_cse_reciprocals =
593 gate_cse_reciprocals, /* gate */
594 execute_cse_reciprocals, /* execute */
597 0, /* static_pass_number */
599 PROP_ssa, /* properties_required */
600 0, /* properties_provided */
601 0, /* properties_destroyed */
602 0, /* todo_flags_start */
603 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
604 | TODO_verify_stmts /* todo_flags_finish */
608 /* Records an occurrence at statement USE_STMT in the vector of trees
609 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
610 is not yet initialized. Returns true if the occurrence was pushed on
611 the vector. Adjusts *TOP_BB to be the basic block dominating all
612 statements in the vector. */
615 maybe_record_sincos (VEC(gimple, heap) **stmts,
616 basic_block *top_bb, gimple use_stmt)
618 basic_block use_bb = gimple_bb (use_stmt);
620 && (*top_bb == use_bb
621 || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
622 VEC_safe_push (gimple, heap, *stmts, use_stmt);
624 || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
626 VEC_safe_push (gimple, heap, *stmts, use_stmt);
635 /* Look for sin, cos and cexpi calls with the same argument NAME and
636 create a single call to cexpi CSEing the result in this case.
637 We first walk over all immediate uses of the argument collecting
638 statements that we can CSE in a vector and in a second pass replace
639 the statement rhs with a REALPART or IMAGPART expression on the
640 result of the cexpi call we insert before the use statement that
641 dominates all other candidates. */
644 execute_cse_sincos_1 (tree name)
646 gimple_stmt_iterator gsi;
647 imm_use_iterator use_iter;
648 tree fndecl, res, type;
649 gimple def_stmt, use_stmt, stmt;
650 int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
651 VEC(gimple, heap) *stmts = NULL;
652 basic_block top_bb = NULL;
655 type = TREE_TYPE (name);
656 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
658 if (gimple_code (use_stmt) != GIMPLE_CALL
659 || !gimple_call_lhs (use_stmt)
660 || !(fndecl = gimple_call_fndecl (use_stmt))
661 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
664 switch (DECL_FUNCTION_CODE (fndecl))
666 CASE_FLT_FN (BUILT_IN_COS):
667 seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
670 CASE_FLT_FN (BUILT_IN_SIN):
671 seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
674 CASE_FLT_FN (BUILT_IN_CEXPI):
675 seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
682 if (seen_cos + seen_sin + seen_cexpi <= 1)
684 VEC_free(gimple, heap, stmts);
688 /* Simply insert cexpi at the beginning of top_bb but not earlier than
689 the name def statement. */
690 fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
693 res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
694 stmt = gimple_build_call (fndecl, 1, name);
695 gimple_call_set_lhs (stmt, res);
697 def_stmt = SSA_NAME_DEF_STMT (name);
698 if (!SSA_NAME_IS_DEFAULT_DEF (name)
699 && gimple_code (def_stmt) != GIMPLE_PHI
700 && gimple_bb (def_stmt) == top_bb)
702 gsi = gsi_for_stmt (def_stmt);
703 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
707 gsi = gsi_after_labels (top_bb);
708 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
712 /* And adjust the recorded old call sites. */
713 for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
716 fndecl = gimple_call_fndecl (use_stmt);
718 switch (DECL_FUNCTION_CODE (fndecl))
720 CASE_FLT_FN (BUILT_IN_COS):
721 rhs = fold_build1 (REALPART_EXPR, type, res);
724 CASE_FLT_FN (BUILT_IN_SIN):
725 rhs = fold_build1 (IMAGPART_EXPR, type, res);
728 CASE_FLT_FN (BUILT_IN_CEXPI):
736 /* Replace call with a copy. */
737 stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
739 gsi = gsi_for_stmt (use_stmt);
740 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
741 gsi_remove (&gsi, true);
744 VEC_free(gimple, heap, stmts);
747 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
748 on the SSA_NAME argument of each of them. */
751 execute_cse_sincos (void)
755 calculate_dominance_info (CDI_DOMINATORS);
759 gimple_stmt_iterator gsi;
761 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
763 gimple stmt = gsi_stmt (gsi);
766 if (is_gimple_call (stmt)
767 && gimple_call_lhs (stmt)
768 && (fndecl = gimple_call_fndecl (stmt))
769 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
773 switch (DECL_FUNCTION_CODE (fndecl))
775 CASE_FLT_FN (BUILT_IN_COS):
776 CASE_FLT_FN (BUILT_IN_SIN):
777 CASE_FLT_FN (BUILT_IN_CEXPI):
778 arg = gimple_call_arg (stmt, 0);
779 if (TREE_CODE (arg) == SSA_NAME)
780 execute_cse_sincos_1 (arg);
789 free_dominance_info (CDI_DOMINATORS);
794 gate_cse_sincos (void)
796 /* Make sure we have either sincos or cexp. */
797 return (TARGET_HAS_SINCOS
798 || TARGET_C99_FUNCTIONS)
802 struct gimple_opt_pass pass_cse_sincos =
807 gate_cse_sincos, /* gate */
808 execute_cse_sincos, /* execute */
811 0, /* static_pass_number */
813 PROP_ssa, /* properties_required */
814 0, /* properties_provided */
815 0, /* properties_destroyed */
816 0, /* todo_flags_start */
817 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
818 | TODO_verify_stmts /* todo_flags_finish */
822 /* A symbolic number is used to detect byte permutation and selection
823 patterns. Therefore the field N contains an artificial number
824 consisting of byte size markers:
826 0 - byte has the value 0
827 1..size - byte contains the content of the byte
828 number indexed with that value minus one */
830 struct symbolic_number {
831 unsigned HOST_WIDEST_INT n;
835 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
836 number N. Return false if the requested operation is not permitted
837 on a symbolic number. */
840 do_shift_rotate (enum tree_code code,
841 struct symbolic_number *n,
847 /* Zero out the extra bits of N in order to avoid them being shifted
848 into the significant bits. */
849 if (n->size < (int)sizeof (HOST_WIDEST_INT))
850 n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
861 n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
864 n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
872 /* Perform sanity checking for the symbolic number N and the gimple
876 verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
880 lhs_type = gimple_expr_type (stmt);
882 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
885 if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
891 /* find_bswap_1 invokes itself recursively with N and tries to perform
892 the operation given by the rhs of STMT on the result. If the
893 operation could successfully be executed the function returns the
894 tree expression of the source operand and NULL otherwise. */
897 find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
900 tree rhs1, rhs2 = NULL;
901 gimple rhs1_stmt, rhs2_stmt;
903 enum gimple_rhs_class rhs_class;
905 if (!limit || !is_gimple_assign (stmt))
908 rhs1 = gimple_assign_rhs1 (stmt);
910 if (TREE_CODE (rhs1) != SSA_NAME)
913 code = gimple_assign_rhs_code (stmt);
914 rhs_class = gimple_assign_rhs_class (stmt);
915 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
917 if (rhs_class == GIMPLE_BINARY_RHS)
918 rhs2 = gimple_assign_rhs2 (stmt);
920 /* Handle unary rhs and binary rhs with integer constants as second
923 if (rhs_class == GIMPLE_UNARY_RHS
924 || (rhs_class == GIMPLE_BINARY_RHS
925 && TREE_CODE (rhs2) == INTEGER_CST))
927 if (code != BIT_AND_EXPR
928 && code != LSHIFT_EXPR
929 && code != RSHIFT_EXPR
930 && code != LROTATE_EXPR
931 && code != RROTATE_EXPR
933 && code != CONVERT_EXPR)
936 source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
938 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
939 to initialize the symbolic number. */
942 /* Set up the symbolic number N by setting each byte to a
943 value between 1 and the byte size of rhs1. The highest
944 order byte is set to n->size and the lowest order
946 n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
947 if (n->size % BITS_PER_UNIT != 0)
949 n->size /= BITS_PER_UNIT;
950 n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
951 (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201);
953 if (n->size < (int)sizeof (HOST_WIDEST_INT))
954 n->n &= ((unsigned HOST_WIDEST_INT)1 <<
955 (n->size * BITS_PER_UNIT)) - 1;
965 unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
966 unsigned HOST_WIDEST_INT tmp = val;
968 /* Only constants masking full bytes are allowed. */
969 for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
970 if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
980 if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
987 type_size = TYPE_PRECISION (gimple_expr_type (stmt));
988 if (type_size % BITS_PER_UNIT != 0)
991 if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
993 /* If STMT casts to a smaller type mask out the bits not
994 belonging to the target type. */
995 n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
997 n->size = type_size / BITS_PER_UNIT;
1003 return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
1006 /* Handle binary rhs. */
1008 if (rhs_class == GIMPLE_BINARY_RHS)
1010 struct symbolic_number n1, n2;
1013 if (code != BIT_IOR_EXPR)
1016 if (TREE_CODE (rhs2) != SSA_NAME)
1019 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
1024 source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
1029 source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
1031 if (source_expr1 != source_expr2
1032 || n1.size != n2.size)
1038 if (!verify_symbolic_number_p (n, stmt))
1045 return source_expr1;
1050 /* Check if STMT completes a bswap implementation consisting of ORs,
1051 SHIFTs and ANDs. Return the source tree expression on which the
1052 byte swap is performed and NULL if no bswap was found. */
1055 find_bswap (gimple stmt)
1057 /* The number which the find_bswap result should match in order to
1058 have a full byte swap. The number is shifted to the left according
1059 to the size of the symbolic number before using it. */
1060 unsigned HOST_WIDEST_INT cmp =
1061 sizeof (HOST_WIDEST_INT) < 8 ? 0 :
1062 (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708;
1064 struct symbolic_number n;
1067 /* The last parameter determines the depth search limit. It usually
1068 correlates directly to the number of bytes to be touched. We
1069 increase that number by one here in order to also cover signed ->
1070 unsigned conversions of the src operand as can be seen in
1072 source_expr = find_bswap_1 (stmt, &n,
1074 TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
1079 /* Zero out the extra bits of N and CMP. */
1080 if (n.size < (int)sizeof (HOST_WIDEST_INT))
1082 unsigned HOST_WIDEST_INT mask =
1083 ((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
1086 cmp >>= (sizeof (HOST_WIDEST_INT) - n.size) * BITS_PER_UNIT;
1089 /* A complete byte swap should make the symbolic number to start
1090 with the largest digit in the highest order byte. */
1097 /* Find manual byte swap implementations and turn them into a bswap
1098 builtin invokation. */
1101 execute_optimize_bswap (void)
1104 bool bswap32_p, bswap64_p;
1105 bool changed = false;
1106 tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1108 if (BITS_PER_UNIT != 8)
1111 if (sizeof (HOST_WIDEST_INT) < 8)
1114 bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
1115 && optab_handler (bswap_optab, SImode)->insn_code !=
1117 bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
1118 && (optab_handler (bswap_optab, DImode)->insn_code !=
1120 || (bswap32_p && word_mode == SImode)));
1122 if (!bswap32_p && !bswap64_p)
1125 /* Determine the argument type of the builtins. The code later on
1126 assumes that the return and argument type are the same. */
1129 tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
1130 bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1135 tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
1136 bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1141 gimple_stmt_iterator gsi;
1143 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1145 gimple stmt = gsi_stmt (gsi);
1146 tree bswap_src, bswap_type;
1148 tree fndecl = NULL_TREE;
1152 if (!is_gimple_assign (stmt)
1153 || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
1156 type_size = TYPE_PRECISION (gimple_expr_type (stmt));
1163 fndecl = built_in_decls[BUILT_IN_BSWAP32];
1164 bswap_type = bswap32_type;
1170 fndecl = built_in_decls[BUILT_IN_BSWAP64];
1171 bswap_type = bswap64_type;
1181 bswap_src = find_bswap (stmt);
1188 bswap_tmp = bswap_src;
1190 /* Convert the src expression if necessary. */
1191 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1193 gimple convert_stmt;
1195 bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
1196 add_referenced_var (bswap_tmp);
1197 bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1199 convert_stmt = gimple_build_assign_with_ops (
1200 CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
1201 gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
1204 call = gimple_build_call (fndecl, 1, bswap_tmp);
1206 bswap_tmp = gimple_assign_lhs (stmt);
1208 /* Convert the result if necessary. */
1209 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1211 gimple convert_stmt;
1213 bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
1214 add_referenced_var (bswap_tmp);
1215 bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1216 convert_stmt = gimple_build_assign_with_ops (
1217 CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
1218 gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
1221 gimple_call_set_lhs (call, bswap_tmp);
1225 fprintf (dump_file, "%d bit bswap implementation found at: ",
1227 print_gimple_stmt (dump_file, stmt, 0, 0);
1230 gsi_insert_after (&gsi, call, GSI_SAME_STMT);
1231 gsi_remove (&gsi, true);
1235 return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
1236 | TODO_verify_stmts : 0);
1240 gate_optimize_bswap (void)
1242 return flag_expensive_optimizations && optimize;
1245 struct gimple_opt_pass pass_optimize_bswap =
1250 gate_optimize_bswap, /* gate */
1251 execute_optimize_bswap, /* execute */
1254 0, /* static_pass_number */
1255 TV_NONE, /* tv_id */
1256 PROP_ssa, /* properties_required */
1257 0, /* properties_provided */
1258 0, /* properties_destroyed */
1259 0, /* todo_flags_start */
1260 0 /* todo_flags_finish */