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;
536 code = DECL_FUNCTION_CODE (fndecl);
537 md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD;
539 fndecl = targetm.builtin_reciprocal (code, md_code, false);
543 gimple_call_set_fndecl (stmt1, fndecl);
546 gimple_assign_set_rhs_code (stmt, MULT_EXPR);
547 fold_stmt_inplace (stmt);
554 free_dominance_info (CDI_DOMINATORS);
555 free_dominance_info (CDI_POST_DOMINATORS);
556 free_alloc_pool (occ_pool);
560 struct gimple_opt_pass pass_cse_reciprocals =
565 gate_cse_reciprocals, /* gate */
566 execute_cse_reciprocals, /* execute */
569 0, /* static_pass_number */
571 PROP_ssa, /* properties_required */
572 0, /* properties_provided */
573 0, /* properties_destroyed */
574 0, /* todo_flags_start */
575 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
576 | TODO_verify_stmts /* todo_flags_finish */
580 /* Records an occurrence at statement USE_STMT in the vector of trees
581 STMTS if it is dominated by *TOP_BB or dominates it or this basic block
582 is not yet initialized. Returns true if the occurrence was pushed on
583 the vector. Adjusts *TOP_BB to be the basic block dominating all
584 statements in the vector. */
587 maybe_record_sincos (VEC(gimple, heap) **stmts,
588 basic_block *top_bb, gimple use_stmt)
590 basic_block use_bb = gimple_bb (use_stmt);
592 && (*top_bb == use_bb
593 || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb)))
594 VEC_safe_push (gimple, heap, *stmts, use_stmt);
596 || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb))
598 VEC_safe_push (gimple, heap, *stmts, use_stmt);
607 /* Look for sin, cos and cexpi calls with the same argument NAME and
608 create a single call to cexpi CSEing the result in this case.
609 We first walk over all immediate uses of the argument collecting
610 statements that we can CSE in a vector and in a second pass replace
611 the statement rhs with a REALPART or IMAGPART expression on the
612 result of the cexpi call we insert before the use statement that
613 dominates all other candidates. */
616 execute_cse_sincos_1 (tree name)
618 gimple_stmt_iterator gsi;
619 imm_use_iterator use_iter;
620 tree fndecl, res, type;
621 gimple def_stmt, use_stmt, stmt;
622 int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
623 VEC(gimple, heap) *stmts = NULL;
624 basic_block top_bb = NULL;
627 type = TREE_TYPE (name);
628 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
630 if (gimple_code (use_stmt) != GIMPLE_CALL
631 || !gimple_call_lhs (use_stmt)
632 || !(fndecl = gimple_call_fndecl (use_stmt))
633 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL)
636 switch (DECL_FUNCTION_CODE (fndecl))
638 CASE_FLT_FN (BUILT_IN_COS):
639 seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
642 CASE_FLT_FN (BUILT_IN_SIN):
643 seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
646 CASE_FLT_FN (BUILT_IN_CEXPI):
647 seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0;
654 if (seen_cos + seen_sin + seen_cexpi <= 1)
656 VEC_free(gimple, heap, stmts);
660 /* Simply insert cexpi at the beginning of top_bb but not earlier than
661 the name def statement. */
662 fndecl = mathfn_built_in (type, BUILT_IN_CEXPI);
665 res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp");
666 stmt = gimple_build_call (fndecl, 1, name);
667 gimple_call_set_lhs (stmt, res);
669 def_stmt = SSA_NAME_DEF_STMT (name);
670 if (!SSA_NAME_IS_DEFAULT_DEF (name)
671 && gimple_code (def_stmt) != GIMPLE_PHI
672 && gimple_bb (def_stmt) == top_bb)
674 gsi = gsi_for_stmt (def_stmt);
675 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
679 gsi = gsi_after_labels (top_bb);
680 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
684 /* And adjust the recorded old call sites. */
685 for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i)
688 fndecl = gimple_call_fndecl (use_stmt);
690 switch (DECL_FUNCTION_CODE (fndecl))
692 CASE_FLT_FN (BUILT_IN_COS):
693 rhs = fold_build1 (REALPART_EXPR, type, res);
696 CASE_FLT_FN (BUILT_IN_SIN):
697 rhs = fold_build1 (IMAGPART_EXPR, type, res);
700 CASE_FLT_FN (BUILT_IN_CEXPI):
708 /* Replace call with a copy. */
709 stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs);
711 gsi = gsi_for_stmt (use_stmt);
712 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT);
713 gsi_remove (&gsi, true);
716 VEC_free(gimple, heap, stmts);
719 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1
720 on the SSA_NAME argument of each of them. */
723 execute_cse_sincos (void)
727 calculate_dominance_info (CDI_DOMINATORS);
731 gimple_stmt_iterator gsi;
733 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
735 gimple stmt = gsi_stmt (gsi);
738 if (is_gimple_call (stmt)
739 && gimple_call_lhs (stmt)
740 && (fndecl = gimple_call_fndecl (stmt))
741 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
745 switch (DECL_FUNCTION_CODE (fndecl))
747 CASE_FLT_FN (BUILT_IN_COS):
748 CASE_FLT_FN (BUILT_IN_SIN):
749 CASE_FLT_FN (BUILT_IN_CEXPI):
750 arg = gimple_call_arg (stmt, 0);
751 if (TREE_CODE (arg) == SSA_NAME)
752 execute_cse_sincos_1 (arg);
761 free_dominance_info (CDI_DOMINATORS);
766 gate_cse_sincos (void)
768 /* Make sure we have either sincos or cexp. */
769 return (TARGET_HAS_SINCOS
770 || TARGET_C99_FUNCTIONS)
774 struct gimple_opt_pass pass_cse_sincos =
779 gate_cse_sincos, /* gate */
780 execute_cse_sincos, /* execute */
783 0, /* static_pass_number */
785 PROP_ssa, /* properties_required */
786 0, /* properties_provided */
787 0, /* properties_destroyed */
788 0, /* todo_flags_start */
789 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
790 | TODO_verify_stmts /* todo_flags_finish */
794 /* A symbolic number is used to detect byte permutation and selection
795 patterns. Therefore the field N contains an artificial number
796 consisting of byte size markers:
798 0 - byte has the value 0
799 1..size - byte contains the content of the byte
800 number indexed with that value minus one */
802 struct symbolic_number {
803 unsigned HOST_WIDEST_INT n;
807 /* Perform a SHIFT or ROTATE operation by COUNT bits on symbolic
808 number N. Return false if the requested operation is not permitted
809 on a symbolic number. */
812 do_shift_rotate (enum tree_code code,
813 struct symbolic_number *n,
819 /* Zero out the extra bits of N in order to avoid them being shifted
820 into the significant bits. */
821 if (n->size < (int)sizeof (HOST_WIDEST_INT))
822 n->n &= ((unsigned HOST_WIDEST_INT)1 << (n->size * BITS_PER_UNIT)) - 1;
833 n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
836 n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
844 /* Perform sanity checking for the symbolic number N and the gimple
848 verify_symbolic_number_p (struct symbolic_number *n, gimple stmt)
852 lhs_type = gimple_expr_type (stmt);
854 if (TREE_CODE (lhs_type) != INTEGER_TYPE)
857 if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
863 /* find_bswap_1 invokes itself recursively with N and tries to perform
864 the operation given by the rhs of STMT on the result. If the
865 operation could successfully be executed the function returns the
866 tree expression of the source operand and NULL otherwise. */
869 find_bswap_1 (gimple stmt, struct symbolic_number *n, int limit)
872 tree rhs1, rhs2 = NULL;
873 gimple rhs1_stmt, rhs2_stmt;
875 enum gimple_rhs_class rhs_class;
877 if (!limit || !is_gimple_assign (stmt))
880 rhs1 = gimple_assign_rhs1 (stmt);
882 if (TREE_CODE (rhs1) != SSA_NAME)
885 code = gimple_assign_rhs_code (stmt);
886 rhs_class = gimple_assign_rhs_class (stmt);
887 rhs1_stmt = SSA_NAME_DEF_STMT (rhs1);
889 if (rhs_class == GIMPLE_BINARY_RHS)
890 rhs2 = gimple_assign_rhs2 (stmt);
892 /* Handle unary rhs and binary rhs with integer constants as second
895 if (rhs_class == GIMPLE_UNARY_RHS
896 || (rhs_class == GIMPLE_BINARY_RHS
897 && TREE_CODE (rhs2) == INTEGER_CST))
899 if (code != BIT_AND_EXPR
900 && code != LSHIFT_EXPR
901 && code != RSHIFT_EXPR
902 && code != LROTATE_EXPR
903 && code != RROTATE_EXPR
905 && code != CONVERT_EXPR)
908 source_expr1 = find_bswap_1 (rhs1_stmt, n, limit - 1);
910 /* If find_bswap_1 returned NULL STMT is a leaf node and we have
911 to initialize the symbolic number. */
914 /* Set up the symbolic number N by setting each byte to a
915 value between 1 and the byte size of rhs1. The highest
916 order byte is set to 1 and the lowest order byte to
918 n->size = TYPE_PRECISION (TREE_TYPE (rhs1));
919 if (n->size % BITS_PER_UNIT != 0)
921 n->size /= BITS_PER_UNIT;
922 n->n = (sizeof (HOST_WIDEST_INT) < 8 ? 0 :
923 (unsigned HOST_WIDEST_INT)0x01020304 << 32 | 0x05060708);
924 n->n >>= (sizeof (HOST_WIDEST_INT) - n->size) * BITS_PER_UNIT;
934 unsigned HOST_WIDEST_INT val = widest_int_cst_value (rhs2);
935 unsigned HOST_WIDEST_INT tmp = val;
937 /* Only constants masking full bytes are allowed. */
938 for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
939 if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
949 if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
956 type_size = TYPE_PRECISION (gimple_expr_type (stmt));
957 if (type_size % BITS_PER_UNIT != 0)
960 if (type_size / BITS_PER_UNIT < (int)(sizeof (HOST_WIDEST_INT)))
962 /* If STMT casts to a smaller type mask out the bits not
963 belonging to the target type. */
964 n->size = type_size / BITS_PER_UNIT;
965 n->n &= ((unsigned HOST_WIDEST_INT)1 << type_size) - 1;
972 return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
975 /* Handle binary rhs. */
977 if (rhs_class == GIMPLE_BINARY_RHS)
979 struct symbolic_number n1, n2;
982 if (code != BIT_IOR_EXPR)
985 if (TREE_CODE (rhs2) != SSA_NAME)
988 rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
993 source_expr1 = find_bswap_1 (rhs1_stmt, &n1, limit - 1);
998 source_expr2 = find_bswap_1 (rhs2_stmt, &n2, limit - 1);
1000 if (source_expr1 != source_expr2
1001 || n1.size != n2.size)
1007 if (!verify_symbolic_number_p (n, stmt))
1014 return source_expr1;
1019 /* Check if STMT completes a bswap implementation consisting of ORs,
1020 SHIFTs and ANDs. Return the source tree expression on which the
1021 byte swap is performed and NULL if no bswap was found. */
1024 find_bswap (gimple stmt)
1026 /* The number which the find_bswap result should match in order to
1027 have a full byte swap. The insignificant bytes are masked out
1029 unsigned HOST_WIDEST_INT cmp =
1030 sizeof (HOST_WIDEST_INT) < 8 ? 0 :
1031 (unsigned HOST_WIDEST_INT)0x08070605 << 32 | 0x04030201;
1033 struct symbolic_number n;
1036 /* The last parameter determines the depth search limit. It usually
1037 correlates directly to the number of bytes to be touched. We
1038 increase that number by one here in order to also cover signed ->
1039 unsigned conversions of the src operand as can be seen in
1041 source_expr = find_bswap_1 (stmt, &n,
1043 TYPE_SIZE_UNIT (gimple_expr_type (stmt))) + 1);
1048 /* Zero out the extra bits of N and CMP. */
1049 if (n.size < (int)sizeof (HOST_WIDEST_INT))
1051 unsigned HOST_WIDEST_INT mask =
1052 ((unsigned HOST_WIDEST_INT)1 << (n.size * BITS_PER_UNIT)) - 1;
1058 /* A complete byte swap should make the symbolic number to start
1059 with the largest digit in the highest order byte. */
1066 /* Find manual byte swap implementations and turn them into a bswap
1067 builtin invokation. */
1070 execute_optimize_bswap (void)
1073 bool bswap32_p, bswap64_p;
1074 bool changed = false;
1075 tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
1077 if (BITS_PER_UNIT != 8)
1080 if (sizeof (HOST_WIDEST_INT) < 8)
1083 bswap32_p = (built_in_decls[BUILT_IN_BSWAP32]
1084 && optab_handler (bswap_optab, SImode)->insn_code !=
1086 bswap64_p = (built_in_decls[BUILT_IN_BSWAP64]
1087 && optab_handler (bswap_optab, DImode)->insn_code !=
1090 if (!bswap32_p && !bswap64_p)
1093 /* Determine the argument type of the builtins. The code later on
1094 assumes that the return and argument type are the same. */
1097 tree fndecl = built_in_decls[BUILT_IN_BSWAP32];
1098 bswap32_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1103 tree fndecl = built_in_decls[BUILT_IN_BSWAP64];
1104 bswap64_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
1109 gimple_stmt_iterator gsi;
1111 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1113 gimple stmt = gsi_stmt (gsi);
1114 tree bswap_src, bswap_type;
1116 tree fndecl = NULL_TREE;
1120 if (!is_gimple_assign (stmt)
1121 || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
1124 type_size = TYPE_PRECISION (gimple_expr_type (stmt));
1131 fndecl = built_in_decls[BUILT_IN_BSWAP32];
1132 bswap_type = bswap32_type;
1138 fndecl = built_in_decls[BUILT_IN_BSWAP64];
1139 bswap_type = bswap64_type;
1149 bswap_src = find_bswap (stmt);
1156 bswap_tmp = bswap_src;
1158 /* Convert the src expression if necessary. */
1159 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1161 gimple convert_stmt;
1163 bswap_tmp = create_tmp_var (bswap_type, "bswapsrc");
1164 add_referenced_var (bswap_tmp);
1165 bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1167 convert_stmt = gimple_build_assign_with_ops (
1168 CONVERT_EXPR, bswap_tmp, bswap_src, NULL);
1169 gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
1172 call = gimple_build_call (fndecl, 1, bswap_tmp);
1174 bswap_tmp = gimple_assign_lhs (stmt);
1176 /* Convert the result if necessary. */
1177 if (!useless_type_conversion_p (TREE_TYPE (bswap_tmp), bswap_type))
1179 gimple convert_stmt;
1181 bswap_tmp = create_tmp_var (bswap_type, "bswapdst");
1182 add_referenced_var (bswap_tmp);
1183 bswap_tmp = make_ssa_name (bswap_tmp, NULL);
1184 convert_stmt = gimple_build_assign_with_ops (
1185 CONVERT_EXPR, gimple_assign_lhs (stmt), bswap_tmp, NULL);
1186 gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
1189 gimple_call_set_lhs (call, bswap_tmp);
1193 fprintf (dump_file, "%d bit bswap implementation found at: ",
1195 print_gimple_stmt (dump_file, stmt, 0, 0);
1198 gsi_insert_after (&gsi, call, GSI_SAME_STMT);
1199 gsi_remove (&gsi, true);
1203 return (changed ? TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
1204 | TODO_verify_stmts : 0);
1208 gate_optimize_bswap (void)
1210 return flag_expensive_optimizations && optimize;
1213 struct gimple_opt_pass pass_optimize_bswap =
1218 gate_optimize_bswap, /* gate */
1219 execute_optimize_bswap, /* execute */
1222 0, /* static_pass_number */
1223 TV_NONE, /* tv_id */
1224 PROP_ssa, /* properties_required */
1225 0, /* properties_provided */
1226 0, /* properties_destroyed */
1227 0, /* todo_flags_start */
1228 0 /* todo_flags_finish */