1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
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/>. */
22 #include "coretypes.h"
25 #include "stor-layout.h"
32 #include "hard-reg-set.h"
35 #include "dominance.h"
37 #include "basic-block.h"
38 #include "gimple-pretty-print.h"
39 #include "tree-ssa-alias.h"
40 #include "internal-fn.h"
41 #include "gimple-fold.h"
43 #include "gimple-expr.h"
47 #include "gimple-iterator.h"
48 #include "gimplify-me.h"
49 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "stringpool.h"
54 #include "tree-ssanames.h"
57 #include "tree-pass.h"
58 #include "langhooks.h"
60 #include "diagnostic.h"
63 #include "insn-codes.h"
65 #include "tree-ssa-propagate.h"
66 #include "tree-ssa-dom.h"
68 #include "tree-cfgcleanup.h"
69 #include "tree-into-ssa.h"
72 /* This pass propagates the RHS of assignment statements into use
73 sites of the LHS of the assignment. It's basically a specialized
74 form of tree combination. It is hoped all of this can disappear
75 when we have a generalized tree combiner.
77 One class of common cases we handle is forward propagating a single use
78 variable into a COND_EXPR.
82 if (x) goto ... else goto ...
84 Will be transformed into:
87 if (a COND b) goto ... else goto ...
89 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
91 Or (assuming c1 and c2 are constants):
95 if (x EQ/NEQ c2) goto ... else goto ...
97 Will be transformed into:
100 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
102 Similarly for x = a - c1.
108 if (x) goto ... else goto ...
110 Will be transformed into:
113 if (a == 0) goto ... else goto ...
115 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
116 For these cases, we propagate A into all, possibly more than one,
117 COND_EXPRs that use X.
123 if (x) goto ... else goto ...
125 Will be transformed into:
128 if (a != 0) goto ... else goto ...
130 (Assuming a is an integral type and x is a boolean or x is an
131 integral and a is a boolean.)
133 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
134 For these cases, we propagate A into all, possibly more than one,
135 COND_EXPRs that use X.
137 In addition to eliminating the variable and the statement which assigns
138 a value to the variable, we may be able to later thread the jump without
139 adding insane complexity in the dominator optimizer.
141 Also note these transformations can cascade. We handle this by having
142 a worklist of COND_EXPR statements to examine. As we make a change to
143 a statement, we put it back on the worklist to examine on the next
144 iteration of the main loop.
146 A second class of propagation opportunities arises for ADDR_EXPR
157 ptr = (type1*)&type2var;
160 Will get turned into (if type1 and type2 are the same size
161 and neither have volatile on them):
162 res = VIEW_CONVERT_EXPR<type1>(type2var)
167 ptr2 = ptr + <constant>;
171 ptr2 = &x[constant/elementsize];
176 offset = index * element_size;
177 offset_p = (pointer) offset;
178 ptr2 = ptr + offset_p
180 Will get turned into:
188 Provided that decl has known alignment >= 2, will get turned into
192 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
193 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
196 This will (of course) be extended as other needs arise. */
198 static bool forward_propagate_addr_expr (tree, tree, bool);
200 /* Set to true if we delete dead edges during the optimization. */
201 static bool cfg_changed;
203 static tree rhs_to_tree (tree type, gimple stmt);
205 static bitmap to_purge;
207 /* Const-and-copy lattice. */
208 static vec<tree> lattice;
210 /* Set the lattice entry for NAME to VAL. */
212 fwprop_set_lattice_val (tree name, tree val)
214 if (TREE_CODE (name) == SSA_NAME)
216 if (SSA_NAME_VERSION (name) >= lattice.length ())
218 lattice.reserve (num_ssa_names - lattice.length ());
219 lattice.quick_grow_cleared (num_ssa_names);
221 lattice[SSA_NAME_VERSION (name)] = val;
225 /* Invalidate the lattice entry for NAME, done when releasing SSA names. */
227 fwprop_invalidate_lattice (tree name)
230 && TREE_CODE (name) == SSA_NAME
231 && SSA_NAME_VERSION (name) < lattice.length ())
232 lattice[SSA_NAME_VERSION (name)] = NULL_TREE;
236 /* Get the next statement we can propagate NAME's value into skipping
237 trivial copies. Returns the statement that is suitable as a
238 propagation destination or NULL_TREE if there is no such one.
239 This only returns destinations in a single-use chain. FINAL_NAME_P
240 if non-NULL is written to the ssa name that represents the use. */
243 get_prop_dest_stmt (tree name, tree *final_name_p)
249 /* If name has multiple uses, bail out. */
250 if (!single_imm_use (name, &use, &use_stmt))
253 /* If this is not a trivial copy, we found it. */
254 if (!gimple_assign_ssa_name_copy_p (use_stmt)
255 || gimple_assign_rhs1 (use_stmt) != name)
258 /* Continue searching uses of the copy destination. */
259 name = gimple_assign_lhs (use_stmt);
263 *final_name_p = name;
268 /* Get the statement we can propagate from into NAME skipping
269 trivial copies. Returns the statement which defines the
270 propagation source or NULL_TREE if there is no such one.
271 If SINGLE_USE_ONLY is set considers only sources which have
272 a single use chain up to NAME. If SINGLE_USE_P is non-null,
273 it is set to whether the chain to NAME is a single use chain
274 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
277 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
279 bool single_use = true;
282 gimple def_stmt = SSA_NAME_DEF_STMT (name);
284 if (!has_single_use (name))
291 /* If name is defined by a PHI node or is the default def, bail out. */
292 if (!is_gimple_assign (def_stmt))
295 /* If def_stmt is a simple copy, continue looking. */
296 if (gimple_assign_rhs_code (def_stmt) == SSA_NAME)
297 name = gimple_assign_rhs1 (def_stmt);
300 if (!single_use_only && single_use_p)
301 *single_use_p = single_use;
308 /* Checks if the destination ssa name in DEF_STMT can be used as
309 propagation source. Returns true if so, otherwise false. */
312 can_propagate_from (gimple def_stmt)
314 gcc_assert (is_gimple_assign (def_stmt));
316 /* If the rhs has side-effects we cannot propagate from it. */
317 if (gimple_has_volatile_ops (def_stmt))
320 /* If the rhs is a load we cannot propagate from it. */
321 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
322 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
325 /* Constants can be always propagated. */
326 if (gimple_assign_single_p (def_stmt)
327 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
330 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
331 if (stmt_references_abnormal_ssa_name (def_stmt))
334 /* If the definition is a conversion of a pointer to a function type,
335 then we can not apply optimizations as some targets require
336 function pointers to be canonicalized and in this case this
337 optimization could eliminate a necessary canonicalization. */
338 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
340 tree rhs = gimple_assign_rhs1 (def_stmt);
341 if (POINTER_TYPE_P (TREE_TYPE (rhs))
342 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
349 /* Remove a chain of dead statements starting at the definition of
350 NAME. The chain is linked via the first operand of the defining statements.
351 If NAME was replaced in its only use then this function can be used
352 to clean up dead stmts. The function handles already released SSA
354 Returns true if cleanup-cfg has to run. */
357 remove_prop_source_from_use (tree name)
359 gimple_stmt_iterator gsi;
361 bool cfg_changed = false;
366 if (SSA_NAME_IN_FREE_LIST (name)
367 || SSA_NAME_IS_DEFAULT_DEF (name)
368 || !has_zero_uses (name))
371 stmt = SSA_NAME_DEF_STMT (name);
372 if (gimple_code (stmt) == GIMPLE_PHI
373 || gimple_has_side_effects (stmt))
376 bb = gimple_bb (stmt);
377 gsi = gsi_for_stmt (stmt);
378 unlink_stmt_vdef (stmt);
379 if (gsi_remove (&gsi, true))
380 bitmap_set_bit (to_purge, bb->index);
381 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
384 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
385 } while (name && TREE_CODE (name) == SSA_NAME);
390 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
391 converted to type TYPE.
393 This should disappear, but is needed so we can combine expressions and use
394 the fold() interfaces. Long term, we need to develop folding and combine
395 routines that deal with gimple exclusively . */
398 rhs_to_tree (tree type, gimple stmt)
400 location_t loc = gimple_location (stmt);
401 enum tree_code code = gimple_assign_rhs_code (stmt);
402 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
403 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
404 gimple_assign_rhs2 (stmt),
405 gimple_assign_rhs3 (stmt));
406 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
407 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
408 gimple_assign_rhs2 (stmt));
409 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
410 return build1 (code, type, gimple_assign_rhs1 (stmt));
411 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
412 return gimple_assign_rhs1 (stmt);
417 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
418 the folded result in a form suitable for COND_EXPR_COND or
419 NULL_TREE, if there is no suitable simplified form. If
420 INVARIANT_ONLY is true only gimple_min_invariant results are
421 considered simplified. */
424 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
425 tree op0, tree op1, bool invariant_only)
429 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
431 fold_defer_overflow_warnings ();
432 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
435 fold_undefer_overflow_warnings (false, NULL, 0);
439 /* Require that we got a boolean type out if we put one in. */
440 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
442 /* Canonicalize the combined condition for use in a COND_EXPR. */
443 t = canonicalize_cond_expr_cond (t);
445 /* Bail out if we required an invariant but didn't get one. */
446 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
448 fold_undefer_overflow_warnings (false, NULL, 0);
452 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
457 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
458 of its operand. Return a new comparison tree or NULL_TREE if there
459 were no simplifying combines. */
462 forward_propagate_into_comparison_1 (gimple stmt,
463 enum tree_code code, tree type,
466 tree tmp = NULL_TREE;
467 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
468 bool single_use0_p = false, single_use1_p = false;
470 /* For comparisons use the first operand, that is likely to
471 simplify comparisons against constants. */
472 if (TREE_CODE (op0) == SSA_NAME)
474 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
475 if (def_stmt && can_propagate_from (def_stmt))
477 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
478 tmp = combine_cond_expr_cond (stmt, code, type,
479 rhs0, op1, !single_use0_p);
485 /* If that wasn't successful, try the second operand. */
486 if (TREE_CODE (op1) == SSA_NAME)
488 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
489 if (def_stmt && can_propagate_from (def_stmt))
491 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
492 tmp = combine_cond_expr_cond (stmt, code, type,
493 op0, rhs1, !single_use1_p);
499 /* If that wasn't successful either, try both operands. */
500 if (rhs0 != NULL_TREE
501 && rhs1 != NULL_TREE)
502 tmp = combine_cond_expr_cond (stmt, code, type,
504 !(single_use0_p && single_use1_p));
509 /* Propagate from the ssa name definition statements of the assignment
510 from a comparison at *GSI into the conditional if that simplifies it.
511 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
512 otherwise returns 0. */
515 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
517 gimple stmt = gsi_stmt (*gsi);
519 bool cfg_changed = false;
520 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
521 tree rhs1 = gimple_assign_rhs1 (stmt);
522 tree rhs2 = gimple_assign_rhs2 (stmt);
524 /* Combine the comparison with defining statements. */
525 tmp = forward_propagate_into_comparison_1 (stmt,
526 gimple_assign_rhs_code (stmt),
528 if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
530 gimple_assign_set_rhs_from_tree (gsi, tmp);
532 update_stmt (gsi_stmt (*gsi));
534 if (TREE_CODE (rhs1) == SSA_NAME)
535 cfg_changed |= remove_prop_source_from_use (rhs1);
536 if (TREE_CODE (rhs2) == SSA_NAME)
537 cfg_changed |= remove_prop_source_from_use (rhs2);
538 return cfg_changed ? 2 : 1;
544 /* Propagate from the ssa name definition statements of COND_EXPR
545 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
546 Returns zero if no statement was changed, one if there were
547 changes and two if cfg_cleanup needs to run.
549 This must be kept in sync with forward_propagate_into_cond. */
552 forward_propagate_into_gimple_cond (gimple stmt)
555 enum tree_code code = gimple_cond_code (stmt);
556 bool cfg_changed = false;
557 tree rhs1 = gimple_cond_lhs (stmt);
558 tree rhs2 = gimple_cond_rhs (stmt);
560 /* We can do tree combining on SSA_NAME and comparison expressions. */
561 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
564 tmp = forward_propagate_into_comparison_1 (stmt, code,
569 if (dump_file && tmp)
571 fprintf (dump_file, " Replaced '");
572 print_gimple_expr (dump_file, stmt, 0, 0);
573 fprintf (dump_file, "' with '");
574 print_generic_expr (dump_file, tmp, 0);
575 fprintf (dump_file, "'\n");
578 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
581 if (TREE_CODE (rhs1) == SSA_NAME)
582 cfg_changed |= remove_prop_source_from_use (rhs1);
583 if (TREE_CODE (rhs2) == SSA_NAME)
584 cfg_changed |= remove_prop_source_from_use (rhs2);
585 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
588 /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges. */
589 if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
590 || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
591 && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
593 && integer_zerop (rhs2))
595 && integer_onep (rhs2))))
597 basic_block bb = gimple_bb (stmt);
598 gimple_cond_set_code (stmt, NE_EXPR);
599 gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
600 EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
601 EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
609 /* Propagate from the ssa name definition statements of COND_EXPR
610 in the rhs of statement STMT into the conditional if that simplifies it.
611 Returns true zero if the stmt was changed. */
614 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
616 gimple stmt = gsi_stmt (*gsi_p);
617 tree tmp = NULL_TREE;
618 tree cond = gimple_assign_rhs1 (stmt);
619 enum tree_code code = gimple_assign_rhs_code (stmt);
622 /* We can do tree combining on SSA_NAME and comparison expressions. */
623 if (COMPARISON_CLASS_P (cond))
624 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
626 TREE_OPERAND (cond, 0),
627 TREE_OPERAND (cond, 1));
628 else if (TREE_CODE (cond) == SSA_NAME)
630 enum tree_code def_code;
632 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
633 if (!def_stmt || !can_propagate_from (def_stmt))
636 def_code = gimple_assign_rhs_code (def_stmt);
637 if (TREE_CODE_CLASS (def_code) == tcc_comparison)
638 tmp = fold_build2_loc (gimple_location (def_stmt),
641 gimple_assign_rhs1 (def_stmt),
642 gimple_assign_rhs2 (def_stmt));
643 else if (code == COND_EXPR
644 && ((def_code == BIT_NOT_EXPR
645 && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
646 || (def_code == BIT_XOR_EXPR
647 && integer_onep (gimple_assign_rhs2 (def_stmt)))))
649 tmp = gimple_assign_rhs1 (def_stmt);
655 && is_gimple_condexpr (tmp))
657 if (dump_file && tmp)
659 fprintf (dump_file, " Replaced '");
660 print_generic_expr (dump_file, cond, 0);
661 fprintf (dump_file, "' with '");
662 print_generic_expr (dump_file, tmp, 0);
663 fprintf (dump_file, "'\n");
666 if ((code == VEC_COND_EXPR) ? integer_all_onesp (tmp)
667 : integer_onep (tmp))
668 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
669 else if (integer_zerop (tmp))
670 gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
673 gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
676 tree t = gimple_assign_rhs2 (stmt);
677 gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
678 gimple_assign_set_rhs3 (stmt, t);
681 stmt = gsi_stmt (*gsi_p);
690 /* Propagate from the ssa name definition statements of COND_EXPR
691 values in the rhs of statement STMT into the conditional arms
692 if that simplifies it.
693 Returns true if the stmt was changed. */
696 combine_cond_exprs (gimple_stmt_iterator *gsi_p)
698 gimple stmt = gsi_stmt (*gsi_p);
699 tree cond, val1, val2;
700 bool changed = false;
702 cond = gimple_assign_rhs1 (stmt);
703 val1 = gimple_assign_rhs2 (stmt);
704 if (TREE_CODE (val1) == SSA_NAME)
706 gimple def_stmt = SSA_NAME_DEF_STMT (val1);
707 if (is_gimple_assign (def_stmt)
708 && gimple_assign_rhs_code (def_stmt) == gimple_assign_rhs_code (stmt)
709 && operand_equal_p (gimple_assign_rhs1 (def_stmt), cond, 0))
711 val1 = unshare_expr (gimple_assign_rhs2 (def_stmt));
712 gimple_assign_set_rhs2 (stmt, val1);
716 val2 = gimple_assign_rhs3 (stmt);
717 if (TREE_CODE (val2) == SSA_NAME)
719 gimple def_stmt = SSA_NAME_DEF_STMT (val2);
720 if (is_gimple_assign (def_stmt)
721 && gimple_assign_rhs_code (def_stmt) == gimple_assign_rhs_code (stmt)
722 && operand_equal_p (gimple_assign_rhs1 (def_stmt), cond, 0))
724 val2 = unshare_expr (gimple_assign_rhs3 (def_stmt));
725 gimple_assign_set_rhs3 (stmt, val2);
729 if (operand_equal_p (val1, val2, 0))
731 gimple_assign_set_rhs_from_tree (gsi_p, val1);
732 stmt = gsi_stmt (*gsi_p);
742 /* We've just substituted an ADDR_EXPR into stmt. Update all the
743 relevant data structures to match. */
746 tidy_after_forward_propagate_addr (gimple stmt)
748 /* We may have turned a trapping insn into a non-trapping insn. */
749 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
750 bitmap_set_bit (to_purge, gimple_bb (stmt)->index);
752 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
753 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
756 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
757 ADDR_EXPR <whatever>.
759 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
760 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
761 node or for recovery of array indexing from pointer arithmetic.
763 Return true if the propagation was successful (the propagation can
764 be not totally successful, yet things may have been changed). */
767 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
768 gimple_stmt_iterator *use_stmt_gsi,
771 tree lhs, rhs, rhs2, array_ref;
772 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
773 enum tree_code rhs_code;
776 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
778 lhs = gimple_assign_lhs (use_stmt);
779 rhs_code = gimple_assign_rhs_code (use_stmt);
780 rhs = gimple_assign_rhs1 (use_stmt);
782 /* Do not perform copy-propagation but recurse through copy chains. */
783 if (TREE_CODE (lhs) == SSA_NAME
784 && rhs_code == SSA_NAME)
785 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
787 /* The use statement could be a conversion. Recurse to the uses of the
788 lhs as copyprop does not copy through pointer to integer to pointer
789 conversions and FRE does not catch all cases either.
790 Treat the case of a single-use name and
791 a conversion to def_rhs type separate, though. */
792 if (TREE_CODE (lhs) == SSA_NAME
793 && CONVERT_EXPR_CODE_P (rhs_code))
795 /* If there is a point in a conversion chain where the types match
796 so we can remove a conversion re-materialize the address here
799 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
801 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
802 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
806 /* Else recurse if the conversion preserves the address value. */
807 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
808 || POINTER_TYPE_P (TREE_TYPE (lhs)))
809 && (TYPE_PRECISION (TREE_TYPE (lhs))
810 >= TYPE_PRECISION (TREE_TYPE (def_rhs))))
811 return forward_propagate_addr_expr (lhs, def_rhs, single_use_p);
816 /* If this isn't a conversion chain from this on we only can propagate
817 into compatible pointer contexts. */
818 if (!types_compatible_p (TREE_TYPE (name), TREE_TYPE (def_rhs)))
821 /* Propagate through constant pointer adjustments. */
822 if (TREE_CODE (lhs) == SSA_NAME
823 && rhs_code == POINTER_PLUS_EXPR
825 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
828 /* As we come here with non-invariant addresses in def_rhs we need
829 to make sure we can build a valid constant offsetted address
830 for further propagation. Simply rely on fold building that
831 and check after the fact. */
832 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
834 fold_convert (ptr_type_node,
835 gimple_assign_rhs2 (use_stmt)));
836 if (TREE_CODE (new_def_rhs) == MEM_REF
837 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
839 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
842 /* Recurse. If we could propagate into all uses of lhs do not
843 bother to replace into the current use but just pretend we did. */
844 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
845 && forward_propagate_addr_expr (lhs, new_def_rhs, single_use_p))
848 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
849 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
850 new_def_rhs, NULL_TREE);
851 else if (is_gimple_min_invariant (new_def_rhs))
852 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
853 new_def_rhs, NULL_TREE);
856 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
857 update_stmt (use_stmt);
861 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
862 ADDR_EXPR will not appear on the LHS. */
863 tree *lhsp = gimple_assign_lhs_ptr (use_stmt);
864 while (handled_component_p (*lhsp))
865 lhsp = &TREE_OPERAND (*lhsp, 0);
868 /* Now see if the LHS node is a MEM_REF using NAME. If so,
869 propagate the ADDR_EXPR into the use of NAME and fold the result. */
870 if (TREE_CODE (lhs) == MEM_REF
871 && TREE_OPERAND (lhs, 0) == name)
874 HOST_WIDE_INT def_rhs_offset;
875 /* If the address is invariant we can always fold it. */
876 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
879 offset_int off = mem_ref_offset (lhs);
881 off += def_rhs_offset;
882 if (TREE_CODE (def_rhs_base) == MEM_REF)
884 off += mem_ref_offset (def_rhs_base);
885 new_ptr = TREE_OPERAND (def_rhs_base, 0);
888 new_ptr = build_fold_addr_expr (def_rhs_base);
889 TREE_OPERAND (lhs, 0) = new_ptr;
890 TREE_OPERAND (lhs, 1)
891 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
892 tidy_after_forward_propagate_addr (use_stmt);
893 /* Continue propagating into the RHS if this was not the only use. */
897 /* If the LHS is a plain dereference and the value type is the same as
898 that of the pointed-to type of the address we can put the
899 dereferenced address on the LHS preserving the original alias-type. */
900 else if (integer_zerop (TREE_OPERAND (lhs, 1))
901 && ((gimple_assign_lhs (use_stmt) == lhs
902 && useless_type_conversion_p
903 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
904 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
905 || types_compatible_p (TREE_TYPE (lhs),
906 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
907 /* Don't forward anything into clobber stmts if it would result
908 in the lhs no longer being a MEM_REF. */
909 && (!gimple_clobber_p (use_stmt)
910 || TREE_CODE (TREE_OPERAND (def_rhs, 0)) == MEM_REF))
912 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
913 tree new_offset, new_base, saved, new_lhs;
914 while (handled_component_p (*def_rhs_basep))
915 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
916 saved = *def_rhs_basep;
917 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
919 new_base = TREE_OPERAND (*def_rhs_basep, 0);
920 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (lhs, 1)),
921 TREE_OPERAND (*def_rhs_basep, 1));
925 new_base = build_fold_addr_expr (*def_rhs_basep);
926 new_offset = TREE_OPERAND (lhs, 1);
928 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
929 new_base, new_offset);
930 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
931 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
932 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
933 new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
935 TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
936 TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
937 *def_rhs_basep = saved;
938 tidy_after_forward_propagate_addr (use_stmt);
939 /* Continue propagating into the RHS if this was not the
945 /* We can have a struct assignment dereferencing our name twice.
946 Note that we didn't propagate into the lhs to not falsely
947 claim we did when propagating into the rhs. */
951 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
952 nodes from the RHS. */
953 tree *rhsp = gimple_assign_rhs1_ptr (use_stmt);
954 if (TREE_CODE (*rhsp) == ADDR_EXPR)
955 rhsp = &TREE_OPERAND (*rhsp, 0);
956 while (handled_component_p (*rhsp))
957 rhsp = &TREE_OPERAND (*rhsp, 0);
960 /* Now see if the RHS node is a MEM_REF using NAME. If so,
961 propagate the ADDR_EXPR into the use of NAME and fold the result. */
962 if (TREE_CODE (rhs) == MEM_REF
963 && TREE_OPERAND (rhs, 0) == name)
966 HOST_WIDE_INT def_rhs_offset;
967 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
970 offset_int off = mem_ref_offset (rhs);
972 off += def_rhs_offset;
973 if (TREE_CODE (def_rhs_base) == MEM_REF)
975 off += mem_ref_offset (def_rhs_base);
976 new_ptr = TREE_OPERAND (def_rhs_base, 0);
979 new_ptr = build_fold_addr_expr (def_rhs_base);
980 TREE_OPERAND (rhs, 0) = new_ptr;
981 TREE_OPERAND (rhs, 1)
982 = wide_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
983 fold_stmt_inplace (use_stmt_gsi);
984 tidy_after_forward_propagate_addr (use_stmt);
987 /* If the RHS is a plain dereference and the value type is the same as
988 that of the pointed-to type of the address we can put the
989 dereferenced address on the RHS preserving the original alias-type. */
990 else if (integer_zerop (TREE_OPERAND (rhs, 1))
991 && ((gimple_assign_rhs1 (use_stmt) == rhs
992 && useless_type_conversion_p
993 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
994 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
995 || types_compatible_p (TREE_TYPE (rhs),
996 TREE_TYPE (TREE_OPERAND (def_rhs, 0)))))
998 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
999 tree new_offset, new_base, saved, new_rhs;
1000 while (handled_component_p (*def_rhs_basep))
1001 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
1002 saved = *def_rhs_basep;
1003 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
1005 new_base = TREE_OPERAND (*def_rhs_basep, 0);
1006 new_offset = fold_convert (TREE_TYPE (TREE_OPERAND (rhs, 1)),
1007 TREE_OPERAND (*def_rhs_basep, 1));
1011 new_base = build_fold_addr_expr (*def_rhs_basep);
1012 new_offset = TREE_OPERAND (rhs, 1);
1014 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
1015 new_base, new_offset);
1016 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
1017 TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
1018 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
1019 new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
1021 TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
1022 TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
1023 *def_rhs_basep = saved;
1024 fold_stmt_inplace (use_stmt_gsi);
1025 tidy_after_forward_propagate_addr (use_stmt);
1030 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
1031 is nothing to do. */
1032 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
1033 || gimple_assign_rhs1 (use_stmt) != name)
1036 /* The remaining cases are all for turning pointer arithmetic into
1037 array indexing. They only apply when we have the address of
1038 element zero in an array. If that is not the case then there
1039 is nothing to do. */
1040 array_ref = TREE_OPERAND (def_rhs, 0);
1041 if ((TREE_CODE (array_ref) != ARRAY_REF
1042 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1043 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1044 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1047 rhs2 = gimple_assign_rhs2 (use_stmt);
1048 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
1049 if (TREE_CODE (rhs2) == INTEGER_CST)
1051 tree new_rhs = build1_loc (gimple_location (use_stmt),
1052 ADDR_EXPR, TREE_TYPE (def_rhs),
1053 fold_build2 (MEM_REF,
1054 TREE_TYPE (TREE_TYPE (def_rhs)),
1055 unshare_expr (def_rhs),
1056 fold_convert (ptr_type_node,
1058 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1059 use_stmt = gsi_stmt (*use_stmt_gsi);
1060 update_stmt (use_stmt);
1061 tidy_after_forward_propagate_addr (use_stmt);
1068 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1070 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1071 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1072 node or for recovery of array indexing from pointer arithmetic.
1074 PARENT_SINGLE_USE_P tells if, when in a recursive invocation, NAME was
1075 the single use in the previous invocation. Pass true when calling
1078 Returns true, if all uses have been propagated into. */
1081 forward_propagate_addr_expr (tree name, tree rhs, bool parent_single_use_p)
1083 imm_use_iterator iter;
1086 bool single_use_p = parent_single_use_p && has_single_use (name);
1088 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1093 /* If the use is not in a simple assignment statement, then
1094 there is nothing we can do. */
1095 if (!is_gimple_assign (use_stmt))
1097 if (!is_gimple_debug (use_stmt))
1102 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1103 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1105 /* If the use has moved to a different statement adjust
1106 the update machinery for the old statement too. */
1107 if (use_stmt != gsi_stmt (gsi))
1109 update_stmt (use_stmt);
1110 use_stmt = gsi_stmt (gsi);
1112 update_stmt (use_stmt);
1115 /* Remove intermediate now unused copy and conversion chains. */
1116 use_rhs = gimple_assign_rhs1 (use_stmt);
1118 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1119 && TREE_CODE (use_rhs) == SSA_NAME
1120 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1122 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1123 fwprop_invalidate_lattice (gimple_get_lhs (use_stmt));
1124 release_defs (use_stmt);
1125 gsi_remove (&gsi, true);
1129 return all && has_zero_uses (name);
1133 /* Forward propagate the comparison defined in *DEFGSI like
1134 cond_1 = x CMP y to uses of the form
1138 Returns true if stmt is now unused. Advance DEFGSI to the next
1142 forward_propagate_comparison (gimple_stmt_iterator *defgsi)
1144 gimple stmt = gsi_stmt (*defgsi);
1145 tree name = gimple_assign_lhs (stmt);
1147 tree tmp = NULL_TREE;
1148 gimple_stmt_iterator gsi;
1149 enum tree_code code;
1152 /* Don't propagate ssa names that occur in abnormal phis. */
1153 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1154 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1155 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1156 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1159 /* Do not un-cse comparisons. But propagate through copies. */
1160 use_stmt = get_prop_dest_stmt (name, &name);
1162 || !is_gimple_assign (use_stmt))
1165 code = gimple_assign_rhs_code (use_stmt);
1166 lhs = gimple_assign_lhs (use_stmt);
1167 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1170 /* We can propagate the condition into a statement that
1171 computes the logical negation of the comparison result. */
1172 if ((code == BIT_NOT_EXPR
1173 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1174 || (code == BIT_XOR_EXPR
1175 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1177 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1178 bool nans = HONOR_NANS (TYPE_MODE (type));
1179 enum tree_code inv_code;
1180 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1181 if (inv_code == ERROR_MARK)
1184 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1185 gimple_assign_rhs2 (stmt));
1190 gsi = gsi_for_stmt (use_stmt);
1191 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1192 use_stmt = gsi_stmt (gsi);
1193 update_stmt (use_stmt);
1195 if (dump_file && (dump_flags & TDF_DETAILS))
1197 fprintf (dump_file, " Replaced '");
1198 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1199 fprintf (dump_file, "' with '");
1200 print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1201 fprintf (dump_file, "'\n");
1204 /* When we remove stmt now the iterator defgsi goes off it's current
1205 sequence, hence advance it now. */
1208 /* Remove defining statements. */
1209 return remove_prop_source_from_use (name);
1217 /* Helper function for simplify_gimple_switch. Remove case labels that
1218 have values outside the range of the new type. */
1221 simplify_gimple_switch_label_vec (gimple stmt, tree index_type)
1223 unsigned int branch_num = gimple_switch_num_labels (stmt);
1224 auto_vec<tree> labels (branch_num);
1225 unsigned int i, len;
1227 /* Collect the existing case labels in a VEC, and preprocess it as if
1228 we are gimplifying a GENERIC SWITCH_EXPR. */
1229 for (i = 1; i < branch_num; i++)
1230 labels.quick_push (gimple_switch_label (stmt, i));
1231 preprocess_case_label_vec_for_gimple (labels, index_type, NULL);
1233 /* If any labels were removed, replace the existing case labels
1234 in the GIMPLE_SWITCH statement with the correct ones.
1235 Note that the type updates were done in-place on the case labels,
1236 so we only have to replace the case labels in the GIMPLE_SWITCH
1237 if the number of labels changed. */
1238 len = labels.length ();
1239 if (len < branch_num - 1)
1241 bitmap target_blocks;
1245 /* Corner case: *all* case labels have been removed as being
1246 out-of-range for INDEX_TYPE. Push one label and let the
1247 CFG cleanups deal with this further. */
1252 label = CASE_LABEL (gimple_switch_default_label (stmt));
1253 elt = build_case_label (build_int_cst (index_type, 0), NULL, label);
1254 labels.quick_push (elt);
1258 for (i = 0; i < labels.length (); i++)
1259 gimple_switch_set_label (stmt, i + 1, labels[i]);
1260 for (i++ ; i < branch_num; i++)
1261 gimple_switch_set_label (stmt, i, NULL_TREE);
1262 gimple_switch_set_num_labels (stmt, len + 1);
1264 /* Cleanup any edges that are now dead. */
1265 target_blocks = BITMAP_ALLOC (NULL);
1266 for (i = 0; i < gimple_switch_num_labels (stmt); i++)
1268 tree elt = gimple_switch_label (stmt, i);
1269 basic_block target = label_to_block (CASE_LABEL (elt));
1270 bitmap_set_bit (target_blocks, target->index);
1272 for (ei = ei_start (gimple_bb (stmt)->succs); (e = ei_safe_edge (ei)); )
1274 if (! bitmap_bit_p (target_blocks, e->dest->index))
1278 free_dominance_info (CDI_DOMINATORS);
1283 BITMAP_FREE (target_blocks);
1287 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1288 the condition which we may be able to optimize better. */
1291 simplify_gimple_switch (gimple stmt)
1293 /* The optimization that we really care about is removing unnecessary
1294 casts. That will let us do much better in propagating the inferred
1295 constant at the switch target. */
1296 tree cond = gimple_switch_index (stmt);
1297 if (TREE_CODE (cond) == SSA_NAME)
1299 gimple def_stmt = SSA_NAME_DEF_STMT (cond);
1300 if (gimple_assign_cast_p (def_stmt))
1302 tree def = gimple_assign_rhs1 (def_stmt);
1303 if (TREE_CODE (def) != SSA_NAME)
1306 /* If we have an extension or sign-change that preserves the
1307 values we check against then we can copy the source value into
1309 tree ti = TREE_TYPE (def);
1310 if (INTEGRAL_TYPE_P (ti)
1311 && TYPE_PRECISION (ti) <= TYPE_PRECISION (TREE_TYPE (cond)))
1313 size_t n = gimple_switch_num_labels (stmt);
1314 tree min = NULL_TREE, max = NULL_TREE;
1317 min = CASE_LOW (gimple_switch_label (stmt, 1));
1318 if (CASE_HIGH (gimple_switch_label (stmt, n - 1)))
1319 max = CASE_HIGH (gimple_switch_label (stmt, n - 1));
1321 max = CASE_LOW (gimple_switch_label (stmt, n - 1));
1323 if ((!min || int_fits_type_p (min, ti))
1324 && (!max || int_fits_type_p (max, ti)))
1326 gimple_switch_set_index (stmt, def);
1327 simplify_gimple_switch_label_vec (stmt, ti);
1338 /* For pointers p2 and p1 return p2 - p1 if the
1339 difference is known and constant, otherwise return NULL. */
1342 constant_pointer_difference (tree p1, tree p2)
1345 #define CPD_ITERATIONS 5
1346 tree exps[2][CPD_ITERATIONS];
1347 tree offs[2][CPD_ITERATIONS];
1350 for (i = 0; i < 2; i++)
1352 tree p = i ? p1 : p2;
1353 tree off = size_zero_node;
1355 enum tree_code code;
1357 /* For each of p1 and p2 we need to iterate at least
1358 twice, to handle ADDR_EXPR directly in p1/p2,
1359 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1360 on definition's stmt RHS. Iterate a few extra times. */
1364 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1366 if (TREE_CODE (p) == ADDR_EXPR)
1368 tree q = TREE_OPERAND (p, 0);
1369 HOST_WIDE_INT offset;
1370 tree base = get_addr_base_and_unit_offset (q, &offset);
1375 off = size_binop (PLUS_EXPR, off, size_int (offset));
1377 if (TREE_CODE (q) == MEM_REF
1378 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1380 p = TREE_OPERAND (q, 0);
1381 off = size_binop (PLUS_EXPR, off,
1382 wide_int_to_tree (sizetype,
1383 mem_ref_offset (q)));
1392 if (TREE_CODE (p) != SSA_NAME)
1396 if (j == CPD_ITERATIONS)
1398 stmt = SSA_NAME_DEF_STMT (p);
1399 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1401 code = gimple_assign_rhs_code (stmt);
1402 if (code == POINTER_PLUS_EXPR)
1404 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1406 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1407 p = gimple_assign_rhs1 (stmt);
1409 else if (code == ADDR_EXPR || CONVERT_EXPR_CODE_P (code))
1410 p = gimple_assign_rhs1 (stmt);
1418 for (i = 0; i < cnt[0]; i++)
1419 for (j = 0; j < cnt[1]; j++)
1420 if (exps[0][i] == exps[1][j])
1421 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1426 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1428 memcpy (p, "abcd", 4);
1429 memset (p + 4, ' ', 3);
1431 memcpy (p, "abcd ", 7);
1432 call if the latter can be stored by pieces during expansion. */
1435 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1437 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1438 tree vuse = gimple_vuse (stmt2);
1441 stmt1 = SSA_NAME_DEF_STMT (vuse);
1443 switch (DECL_FUNCTION_CODE (callee2))
1445 case BUILT_IN_MEMSET:
1446 if (gimple_call_num_args (stmt2) != 3
1447 || gimple_call_lhs (stmt2)
1449 || BITS_PER_UNIT != 8)
1454 tree ptr1, src1, str1, off1, len1, lhs1;
1455 tree ptr2 = gimple_call_arg (stmt2, 0);
1456 tree val2 = gimple_call_arg (stmt2, 1);
1457 tree len2 = gimple_call_arg (stmt2, 2);
1458 tree diff, vdef, new_str_cst;
1460 unsigned int ptr1_align;
1461 unsigned HOST_WIDE_INT src_len;
1463 use_operand_p use_p;
1465 if (!tree_fits_shwi_p (val2)
1466 || !tree_fits_uhwi_p (len2))
1468 if (is_gimple_call (stmt1))
1470 /* If first stmt is a call, it needs to be memcpy
1471 or mempcpy, with string literal as second argument and
1473 callee1 = gimple_call_fndecl (stmt1);
1474 if (callee1 == NULL_TREE
1475 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1476 || gimple_call_num_args (stmt1) != 3)
1478 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1479 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1481 ptr1 = gimple_call_arg (stmt1, 0);
1482 src1 = gimple_call_arg (stmt1, 1);
1483 len1 = gimple_call_arg (stmt1, 2);
1484 lhs1 = gimple_call_lhs (stmt1);
1485 if (!tree_fits_uhwi_p (len1))
1487 str1 = string_constant (src1, &off1);
1488 if (str1 == NULL_TREE)
1490 if (!tree_fits_uhwi_p (off1)
1491 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1492 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1493 - tree_to_uhwi (off1)) > 0
1494 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1495 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1496 != TYPE_MODE (char_type_node))
1499 else if (gimple_assign_single_p (stmt1))
1501 /* Otherwise look for length 1 memcpy optimized into
1503 ptr1 = gimple_assign_lhs (stmt1);
1504 src1 = gimple_assign_rhs1 (stmt1);
1505 if (TREE_CODE (ptr1) != MEM_REF
1506 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1507 || !tree_fits_shwi_p (src1))
1509 ptr1 = build_fold_addr_expr (ptr1);
1510 callee1 = NULL_TREE;
1511 len1 = size_one_node;
1513 off1 = size_zero_node;
1519 diff = constant_pointer_difference (ptr1, ptr2);
1520 if (diff == NULL && lhs1 != NULL)
1522 diff = constant_pointer_difference (lhs1, ptr2);
1523 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1525 diff = size_binop (PLUS_EXPR, diff,
1526 fold_convert (sizetype, len1));
1528 /* If the difference between the second and first destination pointer
1529 is not constant, or is bigger than memcpy length, bail out. */
1531 || !tree_fits_uhwi_p (diff)
1532 || tree_int_cst_lt (len1, diff))
1535 /* Use maximum of difference plus memset length and memcpy length
1536 as the new memcpy length, if it is too big, bail out. */
1537 src_len = tree_to_uhwi (diff);
1538 src_len += tree_to_uhwi (len2);
1539 if (src_len < tree_to_uhwi (len1))
1540 src_len = tree_to_uhwi (len1);
1544 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1545 with bigger length will return different result. */
1546 if (lhs1 != NULL_TREE
1547 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1548 && (TREE_CODE (lhs1) != SSA_NAME
1549 || !single_imm_use (lhs1, &use_p, &use_stmt)
1550 || use_stmt != stmt2))
1553 /* If anything reads memory in between memcpy and memset
1554 call, the modified memcpy call might change it. */
1555 vdef = gimple_vdef (stmt1);
1557 && (!single_imm_use (vdef, &use_p, &use_stmt)
1558 || use_stmt != stmt2))
1561 ptr1_align = get_pointer_alignment (ptr1);
1562 /* Construct the new source string literal. */
1563 src_buf = XALLOCAVEC (char, src_len + 1);
1566 TREE_STRING_POINTER (str1) + tree_to_uhwi (off1),
1567 tree_to_uhwi (len1));
1569 src_buf[0] = tree_to_shwi (src1);
1570 memset (src_buf + tree_to_uhwi (diff),
1571 tree_to_shwi (val2), tree_to_uhwi (len2));
1572 src_buf[src_len] = '\0';
1573 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1574 handle embedded '\0's. */
1575 if (strlen (src_buf) != src_len)
1577 rtl_profile_for_bb (gimple_bb (stmt2));
1578 /* If the new memcpy wouldn't be emitted by storing the literal
1579 by pieces, this optimization might enlarge .rodata too much,
1580 as commonly used string literals couldn't be shared any
1582 if (!can_store_by_pieces (src_len,
1583 builtin_strncpy_read_str,
1584 src_buf, ptr1_align, false))
1587 new_str_cst = build_string_literal (src_len, src_buf);
1590 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1592 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1593 gimple_call_set_lhs (stmt1, NULL_TREE);
1594 gimple_call_set_arg (stmt1, 1, new_str_cst);
1595 gimple_call_set_arg (stmt1, 2,
1596 build_int_cst (TREE_TYPE (len1), src_len));
1597 update_stmt (stmt1);
1598 unlink_stmt_vdef (stmt2);
1599 gsi_remove (gsi_p, true);
1600 fwprop_invalidate_lattice (gimple_get_lhs (stmt2));
1601 release_defs (stmt2);
1602 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1604 fwprop_invalidate_lattice (lhs1);
1605 release_ssa_name (lhs1);
1611 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1612 assignment, remove STMT1 and change memset call into
1614 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1616 if (!is_gimple_val (ptr1))
1617 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1618 true, GSI_SAME_STMT);
1619 gimple_call_set_fndecl (stmt2,
1620 builtin_decl_explicit (BUILT_IN_MEMCPY));
1621 gimple_call_set_arg (stmt2, 0, ptr1);
1622 gimple_call_set_arg (stmt2, 1, new_str_cst);
1623 gimple_call_set_arg (stmt2, 2,
1624 build_int_cst (TREE_TYPE (len2), src_len));
1625 unlink_stmt_vdef (stmt1);
1626 gsi_remove (&gsi, true);
1627 fwprop_invalidate_lattice (gimple_get_lhs (stmt1));
1628 release_defs (stmt1);
1629 update_stmt (stmt2);
1640 /* Given a ssa_name in NAME see if it was defined by an assignment and
1641 set CODE to be the code and ARG1 to the first operand on the rhs and ARG2
1642 to the second operand on the rhs. */
1645 defcodefor_name (tree name, enum tree_code *code, tree *arg1, tree *arg2)
1648 enum tree_code code1;
1652 enum gimple_rhs_class grhs_class;
1654 code1 = TREE_CODE (name);
1657 grhs_class = get_gimple_rhs_class (code1);
1659 if (code1 == SSA_NAME)
1661 def = SSA_NAME_DEF_STMT (name);
1663 if (def && is_gimple_assign (def)
1664 && can_propagate_from (def))
1666 code1 = gimple_assign_rhs_code (def);
1667 arg11 = gimple_assign_rhs1 (def);
1668 arg21 = gimple_assign_rhs2 (def);
1669 arg31 = gimple_assign_rhs2 (def);
1672 else if (grhs_class == GIMPLE_TERNARY_RHS
1673 || GIMPLE_BINARY_RHS
1675 || GIMPLE_SINGLE_RHS)
1676 extract_ops_from_tree_1 (name, &code1, &arg11, &arg21, &arg31);
1682 /* Ignore arg3 currently. */
1686 /* Recognize rotation patterns. Return true if a transformation
1687 applied, otherwise return false.
1689 We are looking for X with unsigned type T with bitsize B, OP being
1690 +, | or ^, some type T2 wider than T and
1691 (X << CNT1) OP (X >> CNT2) iff CNT1 + CNT2 == B
1692 ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2)) iff CNT1 + CNT2 == B
1693 (X << Y) OP (X >> (B - Y))
1694 (X << (int) Y) OP (X >> (int) (B - Y))
1695 ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
1696 ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
1697 (X << Y) | (X >> ((-Y) & (B - 1)))
1698 (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
1699 ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
1700 ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
1702 and transform these into:
1706 Note, in the patterns with T2 type, the type of OP operands
1707 might be even a signed type, but should have precision B. */
1710 simplify_rotate (gimple_stmt_iterator *gsi)
1712 gimple stmt = gsi_stmt (*gsi);
1713 tree arg[2], rtype, rotcnt = NULL_TREE;
1714 tree def_arg1[2], def_arg2[2];
1715 enum tree_code def_code[2];
1718 bool swapped_p = false;
1721 arg[0] = gimple_assign_rhs1 (stmt);
1722 arg[1] = gimple_assign_rhs2 (stmt);
1723 rtype = TREE_TYPE (arg[0]);
1725 /* Only create rotates in complete modes. Other cases are not
1726 expanded properly. */
1727 if (!INTEGRAL_TYPE_P (rtype)
1728 || TYPE_PRECISION (rtype) != GET_MODE_PRECISION (TYPE_MODE (rtype)))
1731 for (i = 0; i < 2; i++)
1732 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1734 /* Look through narrowing conversions. */
1735 if (CONVERT_EXPR_CODE_P (def_code[0])
1736 && CONVERT_EXPR_CODE_P (def_code[1])
1737 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[0]))
1738 && INTEGRAL_TYPE_P (TREE_TYPE (def_arg1[1]))
1739 && TYPE_PRECISION (TREE_TYPE (def_arg1[0]))
1740 == TYPE_PRECISION (TREE_TYPE (def_arg1[1]))
1741 && TYPE_PRECISION (TREE_TYPE (def_arg1[0])) > TYPE_PRECISION (rtype)
1742 && has_single_use (arg[0])
1743 && has_single_use (arg[1]))
1745 for (i = 0; i < 2; i++)
1747 arg[i] = def_arg1[i];
1748 defcodefor_name (arg[i], &def_code[i], &def_arg1[i], &def_arg2[i]);
1752 /* One operand has to be LSHIFT_EXPR and one RSHIFT_EXPR. */
1753 for (i = 0; i < 2; i++)
1754 if (def_code[i] != LSHIFT_EXPR && def_code[i] != RSHIFT_EXPR)
1756 else if (!has_single_use (arg[i]))
1758 if (def_code[0] == def_code[1])
1761 /* If we've looked through narrowing conversions before, look through
1762 widening conversions from unsigned type with the same precision
1764 if (TYPE_PRECISION (TREE_TYPE (def_arg1[0])) != TYPE_PRECISION (rtype))
1765 for (i = 0; i < 2; i++)
1768 enum tree_code code;
1769 defcodefor_name (def_arg1[i], &code, &tem, NULL);
1770 if (!CONVERT_EXPR_CODE_P (code)
1771 || !INTEGRAL_TYPE_P (TREE_TYPE (tem))
1772 || TYPE_PRECISION (TREE_TYPE (tem)) != TYPE_PRECISION (rtype))
1776 /* Both shifts have to use the same first operand. */
1777 if (TREE_CODE (def_arg1[0]) != SSA_NAME || def_arg1[0] != def_arg1[1])
1779 if (!TYPE_UNSIGNED (TREE_TYPE (def_arg1[0])))
1782 /* CNT1 + CNT2 == B case above. */
1783 if (tree_fits_uhwi_p (def_arg2[0])
1784 && tree_fits_uhwi_p (def_arg2[1])
1785 && tree_to_uhwi (def_arg2[0])
1786 + tree_to_uhwi (def_arg2[1]) == TYPE_PRECISION (rtype))
1787 rotcnt = def_arg2[0];
1788 else if (TREE_CODE (def_arg2[0]) != SSA_NAME
1789 || TREE_CODE (def_arg2[1]) != SSA_NAME)
1793 tree cdef_arg1[2], cdef_arg2[2], def_arg2_alt[2];
1794 enum tree_code cdef_code[2];
1795 /* Look through conversion of the shift count argument.
1796 The C/C++ FE cast any shift count argument to integer_type_node.
1797 The only problem might be if the shift count type maximum value
1798 is equal or smaller than number of bits in rtype. */
1799 for (i = 0; i < 2; i++)
1801 def_arg2_alt[i] = def_arg2[i];
1802 defcodefor_name (def_arg2[i], &cdef_code[i],
1803 &cdef_arg1[i], &cdef_arg2[i]);
1804 if (CONVERT_EXPR_CODE_P (cdef_code[i])
1805 && INTEGRAL_TYPE_P (TREE_TYPE (cdef_arg1[i]))
1806 && TYPE_PRECISION (TREE_TYPE (cdef_arg1[i]))
1807 > floor_log2 (TYPE_PRECISION (rtype))
1808 && TYPE_PRECISION (TREE_TYPE (cdef_arg1[i]))
1809 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (cdef_arg1[i]))))
1811 def_arg2_alt[i] = cdef_arg1[i];
1812 defcodefor_name (def_arg2_alt[i], &cdef_code[i],
1813 &cdef_arg1[i], &cdef_arg2[i]);
1816 for (i = 0; i < 2; i++)
1817 /* Check for one shift count being Y and the other B - Y,
1818 with optional casts. */
1819 if (cdef_code[i] == MINUS_EXPR
1820 && tree_fits_shwi_p (cdef_arg1[i])
1821 && tree_to_shwi (cdef_arg1[i]) == TYPE_PRECISION (rtype)
1822 && TREE_CODE (cdef_arg2[i]) == SSA_NAME)
1825 enum tree_code code;
1827 if (cdef_arg2[i] == def_arg2[1 - i]
1828 || cdef_arg2[i] == def_arg2_alt[1 - i])
1830 rotcnt = cdef_arg2[i];
1833 defcodefor_name (cdef_arg2[i], &code, &tem, NULL);
1834 if (CONVERT_EXPR_CODE_P (code)
1835 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1836 && TYPE_PRECISION (TREE_TYPE (tem))
1837 > floor_log2 (TYPE_PRECISION (rtype))
1838 && TYPE_PRECISION (TREE_TYPE (tem))
1839 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem)))
1840 && (tem == def_arg2[1 - i]
1841 || tem == def_arg2_alt[1 - i]))
1847 /* The above sequence isn't safe for Y being 0,
1848 because then one of the shifts triggers undefined behavior.
1849 This alternative is safe even for rotation count of 0.
1850 One shift count is Y and the other (-Y) & (B - 1). */
1851 else if (cdef_code[i] == BIT_AND_EXPR
1852 && tree_fits_shwi_p (cdef_arg2[i])
1853 && tree_to_shwi (cdef_arg2[i])
1854 == TYPE_PRECISION (rtype) - 1
1855 && TREE_CODE (cdef_arg1[i]) == SSA_NAME
1856 && gimple_assign_rhs_code (stmt) == BIT_IOR_EXPR)
1859 enum tree_code code;
1861 defcodefor_name (cdef_arg1[i], &code, &tem, NULL);
1862 if (CONVERT_EXPR_CODE_P (code)
1863 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1864 && TYPE_PRECISION (TREE_TYPE (tem))
1865 > floor_log2 (TYPE_PRECISION (rtype))
1866 && TYPE_PRECISION (TREE_TYPE (tem))
1867 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem))))
1868 defcodefor_name (tem, &code, &tem, NULL);
1870 if (code == NEGATE_EXPR)
1872 if (tem == def_arg2[1 - i] || tem == def_arg2_alt[1 - i])
1877 defcodefor_name (tem, &code, &tem, NULL);
1878 if (CONVERT_EXPR_CODE_P (code)
1879 && INTEGRAL_TYPE_P (TREE_TYPE (tem))
1880 && TYPE_PRECISION (TREE_TYPE (tem))
1881 > floor_log2 (TYPE_PRECISION (rtype))
1882 && TYPE_PRECISION (TREE_TYPE (tem))
1883 == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (tem)))
1884 && (tem == def_arg2[1 - i]
1885 || tem == def_arg2_alt[1 - i]))
1892 if (rotcnt == NULL_TREE)
1897 if (!useless_type_conversion_p (TREE_TYPE (def_arg2[0]),
1898 TREE_TYPE (rotcnt)))
1900 g = gimple_build_assign_with_ops (NOP_EXPR,
1901 make_ssa_name (TREE_TYPE (def_arg2[0]),
1904 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1905 rotcnt = gimple_assign_lhs (g);
1907 lhs = gimple_assign_lhs (stmt);
1908 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
1909 lhs = make_ssa_name (TREE_TYPE (def_arg1[0]), NULL);
1910 g = gimple_build_assign_with_ops (((def_code[0] == LSHIFT_EXPR) ^ swapped_p)
1911 ? LROTATE_EXPR : RROTATE_EXPR,
1912 lhs, def_arg1[0], rotcnt);
1913 if (!useless_type_conversion_p (rtype, TREE_TYPE (def_arg1[0])))
1915 gsi_insert_before (gsi, g, GSI_SAME_STMT);
1916 g = gimple_build_assign_with_ops (NOP_EXPR, gimple_assign_lhs (stmt),
1919 gsi_replace (gsi, g, false);
1923 /* Combine an element access with a shuffle. Returns true if there were
1924 any changes made, else it returns false. */
1927 simplify_bitfield_ref (gimple_stmt_iterator *gsi)
1929 gimple stmt = gsi_stmt (*gsi);
1931 tree op, op0, op1, op2;
1933 unsigned idx, n, size;
1934 enum tree_code code;
1936 op = gimple_assign_rhs1 (stmt);
1937 gcc_checking_assert (TREE_CODE (op) == BIT_FIELD_REF);
1939 op0 = TREE_OPERAND (op, 0);
1940 if (TREE_CODE (op0) != SSA_NAME
1941 || TREE_CODE (TREE_TYPE (op0)) != VECTOR_TYPE)
1944 def_stmt = get_prop_source_stmt (op0, false, NULL);
1945 if (!def_stmt || !can_propagate_from (def_stmt))
1948 op1 = TREE_OPERAND (op, 1);
1949 op2 = TREE_OPERAND (op, 2);
1950 code = gimple_assign_rhs_code (def_stmt);
1952 if (code == CONSTRUCTOR)
1954 tree tem = fold_ternary (BIT_FIELD_REF, TREE_TYPE (op),
1955 gimple_assign_rhs1 (def_stmt), op1, op2);
1956 if (!tem || !valid_gimple_rhs_p (tem))
1958 gimple_assign_set_rhs_from_tree (gsi, tem);
1959 update_stmt (gsi_stmt (*gsi));
1963 elem_type = TREE_TYPE (TREE_TYPE (op0));
1964 if (TREE_TYPE (op) != elem_type)
1967 size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
1968 n = TREE_INT_CST_LOW (op1) / size;
1971 idx = TREE_INT_CST_LOW (op2) / size;
1973 if (code == VEC_PERM_EXPR)
1975 tree p, m, index, tem;
1977 m = gimple_assign_rhs3 (def_stmt);
1978 if (TREE_CODE (m) != VECTOR_CST)
1980 nelts = VECTOR_CST_NELTS (m);
1981 idx = TREE_INT_CST_LOW (VECTOR_CST_ELT (m, idx));
1985 p = gimple_assign_rhs1 (def_stmt);
1989 p = gimple_assign_rhs2 (def_stmt);
1992 index = build_int_cst (TREE_TYPE (TREE_TYPE (m)), idx * size);
1993 tem = build3 (BIT_FIELD_REF, TREE_TYPE (op),
1994 unshare_expr (p), op1, index);
1995 gimple_assign_set_rhs1 (stmt, tem);
1997 update_stmt (gsi_stmt (*gsi));
2004 /* Determine whether applying the 2 permutations (mask1 then mask2)
2005 gives back one of the input. */
2008 is_combined_permutation_identity (tree mask1, tree mask2)
2011 unsigned int nelts, i, j;
2012 bool maybe_identity1 = true;
2013 bool maybe_identity2 = true;
2015 gcc_checking_assert (TREE_CODE (mask1) == VECTOR_CST
2016 && TREE_CODE (mask2) == VECTOR_CST);
2017 mask = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (mask1), mask1, mask1, mask2);
2018 gcc_assert (TREE_CODE (mask) == VECTOR_CST);
2020 nelts = VECTOR_CST_NELTS (mask);
2021 for (i = 0; i < nelts; i++)
2023 tree val = VECTOR_CST_ELT (mask, i);
2024 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2025 j = TREE_INT_CST_LOW (val) & (2 * nelts - 1);
2027 maybe_identity2 = false;
2028 else if (j == i + nelts)
2029 maybe_identity1 = false;
2033 return maybe_identity1 ? 1 : maybe_identity2 ? 2 : 0;
2036 /* Combine a shuffle with its arguments. Returns 1 if there were any
2037 changes made, 2 if cfg-cleanup needs to run. Else it returns 0. */
2040 simplify_permutation (gimple_stmt_iterator *gsi)
2042 gimple stmt = gsi_stmt (*gsi);
2044 tree op0, op1, op2, op3, arg0, arg1;
2045 enum tree_code code;
2046 bool single_use_op0 = false;
2048 gcc_checking_assert (gimple_assign_rhs_code (stmt) == VEC_PERM_EXPR);
2050 op0 = gimple_assign_rhs1 (stmt);
2051 op1 = gimple_assign_rhs2 (stmt);
2052 op2 = gimple_assign_rhs3 (stmt);
2054 if (TREE_CODE (op2) != VECTOR_CST)
2057 if (TREE_CODE (op0) == VECTOR_CST)
2062 else if (TREE_CODE (op0) == SSA_NAME)
2064 def_stmt = get_prop_source_stmt (op0, false, &single_use_op0);
2065 if (!def_stmt || !can_propagate_from (def_stmt))
2068 code = gimple_assign_rhs_code (def_stmt);
2069 arg0 = gimple_assign_rhs1 (def_stmt);
2074 /* Two consecutive shuffles. */
2075 if (code == VEC_PERM_EXPR)
2082 op3 = gimple_assign_rhs3 (def_stmt);
2083 if (TREE_CODE (op3) != VECTOR_CST)
2085 ident = is_combined_permutation_identity (op3, op2);
2088 orig = (ident == 1) ? gimple_assign_rhs1 (def_stmt)
2089 : gimple_assign_rhs2 (def_stmt);
2090 gimple_assign_set_rhs1 (stmt, unshare_expr (orig));
2091 gimple_assign_set_rhs_code (stmt, TREE_CODE (orig));
2092 gimple_set_num_ops (stmt, 2);
2094 return remove_prop_source_from_use (op0) ? 2 : 1;
2097 /* Shuffle of a constructor. */
2098 else if (code == CONSTRUCTOR || code == VECTOR_CST)
2104 if (TREE_CODE (op0) == SSA_NAME && !single_use_op0)
2107 if (TREE_CODE (op1) == VECTOR_CST)
2109 else if (TREE_CODE (op1) == SSA_NAME)
2111 enum tree_code code2;
2113 gimple def_stmt2 = get_prop_source_stmt (op1, true, NULL);
2114 if (!def_stmt2 || !can_propagate_from (def_stmt2))
2117 code2 = gimple_assign_rhs_code (def_stmt2);
2118 if (code2 != CONSTRUCTOR && code2 != VECTOR_CST)
2120 arg1 = gimple_assign_rhs1 (def_stmt2);
2127 /* Already used twice in this statement. */
2128 if (TREE_CODE (op0) == SSA_NAME && num_imm_uses (op0) > 2)
2132 opt = fold_ternary (VEC_PERM_EXPR, TREE_TYPE (op0), arg0, arg1, op2);
2134 || (TREE_CODE (opt) != CONSTRUCTOR && TREE_CODE (opt) != VECTOR_CST))
2136 gimple_assign_set_rhs_from_tree (gsi, opt);
2137 update_stmt (gsi_stmt (*gsi));
2138 if (TREE_CODE (op0) == SSA_NAME)
2139 ret = remove_prop_source_from_use (op0);
2140 if (op0 != op1 && TREE_CODE (op1) == SSA_NAME)
2141 ret |= remove_prop_source_from_use (op1);
2148 /* Recognize a VEC_PERM_EXPR. Returns true if there were any changes. */
2151 simplify_vector_constructor (gimple_stmt_iterator *gsi)
2153 gimple stmt = gsi_stmt (*gsi);
2155 tree op, op2, orig, type, elem_type;
2156 unsigned elem_size, nelts, i;
2157 enum tree_code code;
2158 constructor_elt *elt;
2162 gcc_checking_assert (gimple_assign_rhs_code (stmt) == CONSTRUCTOR);
2164 op = gimple_assign_rhs1 (stmt);
2165 type = TREE_TYPE (op);
2166 gcc_checking_assert (TREE_CODE (type) == VECTOR_TYPE);
2168 nelts = TYPE_VECTOR_SUBPARTS (type);
2169 elem_type = TREE_TYPE (type);
2170 elem_size = TREE_INT_CST_LOW (TYPE_SIZE (elem_type));
2172 sel = XALLOCAVEC (unsigned char, nelts);
2175 FOR_EACH_VEC_SAFE_ELT (CONSTRUCTOR_ELTS (op), i, elt)
2182 if (TREE_CODE (elt->value) != SSA_NAME)
2184 def_stmt = get_prop_source_stmt (elt->value, false, NULL);
2187 code = gimple_assign_rhs_code (def_stmt);
2188 if (code != BIT_FIELD_REF)
2190 op1 = gimple_assign_rhs1 (def_stmt);
2191 ref = TREE_OPERAND (op1, 0);
2199 if (TREE_CODE (ref) != SSA_NAME)
2201 if (!useless_type_conversion_p (type, TREE_TYPE (ref)))
2205 if (TREE_INT_CST_LOW (TREE_OPERAND (op1, 1)) != elem_size)
2207 sel[i] = TREE_INT_CST_LOW (TREE_OPERAND (op1, 2)) / elem_size;
2208 if (sel[i] != i) maybe_ident = false;
2214 gimple_assign_set_rhs_from_tree (gsi, orig);
2217 tree mask_type, *mask_elts;
2219 if (!can_vec_perm_p (TYPE_MODE (type), false, sel))
2222 = build_vector_type (build_nonstandard_integer_type (elem_size, 1),
2224 if (GET_MODE_CLASS (TYPE_MODE (mask_type)) != MODE_VECTOR_INT
2225 || GET_MODE_SIZE (TYPE_MODE (mask_type))
2226 != GET_MODE_SIZE (TYPE_MODE (type)))
2228 mask_elts = XALLOCAVEC (tree, nelts);
2229 for (i = 0; i < nelts; i++)
2230 mask_elts[i] = build_int_cst (TREE_TYPE (mask_type), sel[i]);
2231 op2 = build_vector (mask_type, mask_elts);
2232 gimple_assign_set_rhs_with_ops_1 (gsi, VEC_PERM_EXPR, orig, orig, op2);
2234 update_stmt (gsi_stmt (*gsi));
2239 /* Primitive "lattice" function for gimple_simplify. */
2242 fwprop_ssa_val (tree name)
2244 /* First valueize NAME. */
2245 if (TREE_CODE (name) == SSA_NAME
2246 && SSA_NAME_VERSION (name) < lattice.length ())
2248 tree val = lattice[SSA_NAME_VERSION (name)];
2252 /* We continue matching along SSA use-def edges for SSA names
2253 that are not single-use. Currently there are no patterns
2254 that would cause any issues with that. */
2258 /* Main entry point for the forward propagation and statement combine
2263 const pass_data pass_data_forwprop =
2265 GIMPLE_PASS, /* type */
2266 "forwprop", /* name */
2267 OPTGROUP_NONE, /* optinfo_flags */
2268 TV_TREE_FORWPROP, /* tv_id */
2269 ( PROP_cfg | PROP_ssa ), /* properties_required */
2270 0, /* properties_provided */
2271 0, /* properties_destroyed */
2272 0, /* todo_flags_start */
2273 TODO_update_ssa, /* todo_flags_finish */
2276 class pass_forwprop : public gimple_opt_pass
2279 pass_forwprop (gcc::context *ctxt)
2280 : gimple_opt_pass (pass_data_forwprop, ctxt)
2283 /* opt_pass methods: */
2284 opt_pass * clone () { return new pass_forwprop (m_ctxt); }
2285 virtual bool gate (function *) { return flag_tree_forwprop; }
2286 virtual unsigned int execute (function *);
2288 }; // class pass_forwprop
2291 pass_forwprop::execute (function *fun)
2293 unsigned int todoflags = 0;
2295 cfg_changed = false;
2297 /* Combine stmts with the stmts defining their operands. Do that
2298 in an order that guarantees visiting SSA defs before SSA uses. */
2299 lattice.create (num_ssa_names);
2300 lattice.quick_grow_cleared (num_ssa_names);
2301 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (fun));
2302 int postorder_num = inverted_post_order_compute (postorder);
2303 to_purge = BITMAP_ALLOC (NULL);
2304 for (int i = 0; i < postorder_num; ++i)
2306 gimple_stmt_iterator gsi;
2307 basic_block bb = BASIC_BLOCK_FOR_FN (fun, postorder[i]);
2309 /* Apply forward propagation to all stmts in the basic-block.
2310 Note we update GSI within the loop as necessary. */
2311 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2313 gimple stmt = gsi_stmt (gsi);
2315 enum tree_code code;
2317 if (!is_gimple_assign (stmt))
2323 lhs = gimple_assign_lhs (stmt);
2324 rhs = gimple_assign_rhs1 (stmt);
2325 code = gimple_assign_rhs_code (stmt);
2326 if (TREE_CODE (lhs) != SSA_NAME
2327 || has_zero_uses (lhs))
2333 /* If this statement sets an SSA_NAME to an address,
2334 try to propagate the address into the uses of the SSA_NAME. */
2335 if (code == ADDR_EXPR
2336 /* Handle pointer conversions on invariant addresses
2337 as well, as this is valid gimple. */
2338 || (CONVERT_EXPR_CODE_P (code)
2339 && TREE_CODE (rhs) == ADDR_EXPR
2340 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2342 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2345 || decl_address_invariant_p (base))
2346 && !stmt_references_abnormal_ssa_name (stmt)
2347 && forward_propagate_addr_expr (lhs, rhs, true))
2349 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2350 release_defs (stmt);
2351 gsi_remove (&gsi, true);
2356 else if (code == POINTER_PLUS_EXPR)
2358 tree off = gimple_assign_rhs2 (stmt);
2359 if (TREE_CODE (off) == INTEGER_CST
2360 && can_propagate_from (stmt)
2361 && !simple_iv_increment_p (stmt)
2362 /* ??? Better adjust the interface to that function
2363 instead of building new trees here. */
2364 && forward_propagate_addr_expr
2366 build1_loc (gimple_location (stmt),
2367 ADDR_EXPR, TREE_TYPE (rhs),
2368 fold_build2 (MEM_REF,
2369 TREE_TYPE (TREE_TYPE (rhs)),
2371 fold_convert (ptr_type_node,
2374 fwprop_invalidate_lattice (gimple_get_lhs (stmt));
2375 release_defs (stmt);
2376 gsi_remove (&gsi, true);
2378 else if (is_gimple_min_invariant (rhs))
2380 /* Make sure to fold &a[0] + off_1 here. */
2381 fold_stmt_inplace (&gsi);
2383 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2389 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2391 if (forward_propagate_comparison (&gsi))
2398 /* Combine stmts with the stmts defining their operands.
2399 Note we update GSI within the loop as necessary. */
2400 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2402 gimple stmt = gsi_stmt (gsi);
2403 gimple orig_stmt = stmt;
2404 bool changed = false;
2406 /* Mark stmt as potentially needing revisiting. */
2407 gimple_set_plf (stmt, GF_PLF_1, false);
2409 if (fold_stmt (&gsi, fwprop_ssa_val))
2412 stmt = gsi_stmt (gsi);
2413 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
2414 bitmap_set_bit (to_purge, bb->index);
2415 /* Cleanup the CFG if we simplified a condition to
2417 if (gimple_code (stmt) == GIMPLE_COND
2418 && (gimple_cond_true_p (stmt)
2419 || gimple_cond_false_p (stmt)))
2424 switch (gimple_code (stmt))
2428 tree rhs1 = gimple_assign_rhs1 (stmt);
2429 enum tree_code code = gimple_assign_rhs_code (stmt);
2431 if (code == COND_EXPR
2432 || code == VEC_COND_EXPR)
2434 /* In this case the entire COND_EXPR is in rhs1. */
2435 if (forward_propagate_into_cond (&gsi)
2436 || combine_cond_exprs (&gsi))
2439 stmt = gsi_stmt (gsi);
2442 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2445 did_something = forward_propagate_into_comparison (&gsi);
2446 if (did_something == 2)
2448 changed = did_something != 0;
2450 else if ((code == PLUS_EXPR
2451 || code == BIT_IOR_EXPR
2452 || code == BIT_XOR_EXPR)
2453 && simplify_rotate (&gsi))
2455 else if (code == VEC_PERM_EXPR)
2457 int did_something = simplify_permutation (&gsi);
2458 if (did_something == 2)
2460 changed = did_something != 0;
2462 else if (code == BIT_FIELD_REF)
2463 changed = simplify_bitfield_ref (&gsi);
2464 else if (code == CONSTRUCTOR
2465 && TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE)
2466 changed = simplify_vector_constructor (&gsi);
2471 changed = simplify_gimple_switch (stmt);
2477 did_something = forward_propagate_into_gimple_cond (stmt);
2478 if (did_something == 2)
2480 changed = did_something != 0;
2486 tree callee = gimple_call_fndecl (stmt);
2487 if (callee != NULL_TREE
2488 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2489 changed = simplify_builtin_call (&gsi, callee);
2498 /* If the stmt changed then re-visit it and the statements
2499 inserted before it. */
2500 for (; !gsi_end_p (gsi); gsi_prev (&gsi))
2501 if (gimple_plf (gsi_stmt (gsi), GF_PLF_1))
2503 if (gsi_end_p (gsi))
2504 gsi = gsi_start_bb (bb);
2510 /* Stmt no longer needs to be revisited. */
2511 gimple_set_plf (stmt, GF_PLF_1, true);
2513 /* Fill up the lattice. */
2514 if (gimple_assign_single_p (stmt))
2516 tree lhs = gimple_assign_lhs (stmt);
2517 tree rhs = gimple_assign_rhs1 (stmt);
2518 if (TREE_CODE (lhs) == SSA_NAME)
2521 if (TREE_CODE (rhs) == SSA_NAME)
2522 val = fwprop_ssa_val (rhs);
2523 else if (is_gimple_min_invariant (rhs))
2525 fwprop_set_lattice_val (lhs, val);
2536 cfg_changed |= gimple_purge_all_dead_eh_edges (to_purge);
2537 BITMAP_FREE (to_purge);
2540 todoflags |= TODO_cleanup_cfg;
2548 make_pass_forwprop (gcc::context *ctxt)
2550 return new pass_forwprop (ctxt);