1 /* Forward propagation of expressions for single use variables.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "gimple-pretty-print.h"
30 #include "tree-flow.h"
31 #include "tree-pass.h"
32 #include "tree-dump.h"
33 #include "langhooks.h"
38 /* This pass propagates the RHS of assignment statements into use
39 sites of the LHS of the assignment. It's basically a specialized
40 form of tree combination. It is hoped all of this can disappear
41 when we have a generalized tree combiner.
43 One class of common cases we handle is forward propagating a single use
44 variable into a COND_EXPR.
48 if (x) goto ... else goto ...
50 Will be transformed into:
53 if (a COND b) goto ... else goto ...
55 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
57 Or (assuming c1 and c2 are constants):
61 if (x EQ/NEQ c2) goto ... else goto ...
63 Will be transformed into:
66 if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
68 Similarly for x = a - c1.
74 if (x) goto ... else goto ...
76 Will be transformed into:
79 if (a == 0) goto ... else goto ...
81 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
82 For these cases, we propagate A into all, possibly more than one,
83 COND_EXPRs that use X.
89 if (x) goto ... else goto ...
91 Will be transformed into:
94 if (a != 0) goto ... else goto ...
96 (Assuming a is an integral type and x is a boolean or x is an
97 integral and a is a boolean.)
99 Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
100 For these cases, we propagate A into all, possibly more than one,
101 COND_EXPRs that use X.
103 In addition to eliminating the variable and the statement which assigns
104 a value to the variable, we may be able to later thread the jump without
105 adding insane complexity in the dominator optimizer.
107 Also note these transformations can cascade. We handle this by having
108 a worklist of COND_EXPR statements to examine. As we make a change to
109 a statement, we put it back on the worklist to examine on the next
110 iteration of the main loop.
112 A second class of propagation opportunities arises for ADDR_EXPR
123 ptr = (type1*)&type2var;
126 Will get turned into (if type1 and type2 are the same size
127 and neither have volatile on them):
128 res = VIEW_CONVERT_EXPR<type1>(type2var)
133 ptr2 = ptr + <constant>;
137 ptr2 = &x[constant/elementsize];
142 offset = index * element_size;
143 offset_p = (pointer) offset;
144 ptr2 = ptr + offset_p
146 Will get turned into:
154 Provided that decl has known alignment >= 2, will get turned into
158 We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
159 allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
162 This will (of course) be extended as other needs arise. */
164 static bool forward_propagate_addr_expr (tree name, tree rhs);
166 /* Set to true if we delete EH edges during the optimization. */
167 static bool cfg_changed;
169 static tree rhs_to_tree (tree type, gimple stmt);
171 /* Get the next statement we can propagate NAME's value into skipping
172 trivial copies. Returns the statement that is suitable as a
173 propagation destination or NULL_TREE if there is no such one.
174 This only returns destinations in a single-use chain. FINAL_NAME_P
175 if non-NULL is written to the ssa name that represents the use. */
178 get_prop_dest_stmt (tree name, tree *final_name_p)
184 /* If name has multiple uses, bail out. */
185 if (!single_imm_use (name, &use, &use_stmt))
188 /* If this is not a trivial copy, we found it. */
189 if (!gimple_assign_ssa_name_copy_p (use_stmt)
190 || gimple_assign_rhs1 (use_stmt) != name)
193 /* Continue searching uses of the copy destination. */
194 name = gimple_assign_lhs (use_stmt);
198 *final_name_p = name;
203 /* Get the statement we can propagate from into NAME skipping
204 trivial copies. Returns the statement which defines the
205 propagation source or NULL_TREE if there is no such one.
206 If SINGLE_USE_ONLY is set considers only sources which have
207 a single use chain up to NAME. If SINGLE_USE_P is non-null,
208 it is set to whether the chain to NAME is a single use chain
209 or not. SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set. */
212 get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
214 bool single_use = true;
217 gimple def_stmt = SSA_NAME_DEF_STMT (name);
219 if (!has_single_use (name))
226 /* If name is defined by a PHI node or is the default def, bail out. */
227 if (!is_gimple_assign (def_stmt))
230 /* If def_stmt is not a simple copy, we possibly found it. */
231 if (!gimple_assign_ssa_name_copy_p (def_stmt))
235 if (!single_use_only && single_use_p)
236 *single_use_p = single_use;
238 /* We can look through pointer conversions in the search
239 for a useful stmt for the comparison folding. */
240 rhs = gimple_assign_rhs1 (def_stmt);
241 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
242 && TREE_CODE (rhs) == SSA_NAME
243 && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
244 && POINTER_TYPE_P (TREE_TYPE (rhs)))
251 /* Continue searching the def of the copy source name. */
252 name = gimple_assign_rhs1 (def_stmt);
257 /* Checks if the destination ssa name in DEF_STMT can be used as
258 propagation source. Returns true if so, otherwise false. */
261 can_propagate_from (gimple def_stmt)
263 gcc_assert (is_gimple_assign (def_stmt));
265 /* If the rhs has side-effects we cannot propagate from it. */
266 if (gimple_has_volatile_ops (def_stmt))
269 /* If the rhs is a load we cannot propagate from it. */
270 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
271 || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
274 /* Constants can be always propagated. */
275 if (gimple_assign_single_p (def_stmt)
276 && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
279 /* We cannot propagate ssa names that occur in abnormal phi nodes. */
280 if (stmt_references_abnormal_ssa_name (def_stmt))
283 /* If the definition is a conversion of a pointer to a function type,
284 then we can not apply optimizations as some targets require
285 function pointers to be canonicalized and in this case this
286 optimization could eliminate a necessary canonicalization. */
287 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
289 tree rhs = gimple_assign_rhs1 (def_stmt);
290 if (POINTER_TYPE_P (TREE_TYPE (rhs))
291 && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
298 /* Remove a chain of dead statements starting at the definition of
299 NAME. The chain is linked via the first operand of the defining statements.
300 If NAME was replaced in its only use then this function can be used
301 to clean up dead stmts. The function handles already released SSA
303 Returns true if cleanup-cfg has to run. */
306 remove_prop_source_from_use (tree name)
308 gimple_stmt_iterator gsi;
310 bool cfg_changed = false;
315 if (SSA_NAME_IN_FREE_LIST (name)
316 || SSA_NAME_IS_DEFAULT_DEF (name)
317 || !has_zero_uses (name))
320 stmt = SSA_NAME_DEF_STMT (name);
321 if (gimple_code (stmt) == GIMPLE_PHI
322 || gimple_has_side_effects (stmt))
325 bb = gimple_bb (stmt);
326 gsi = gsi_for_stmt (stmt);
327 unlink_stmt_vdef (stmt);
328 gsi_remove (&gsi, true);
330 cfg_changed |= gimple_purge_dead_eh_edges (bb);
332 name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
333 } while (name && TREE_CODE (name) == SSA_NAME);
338 /* Return the rhs of a gimple_assign STMT in a form of a single tree,
339 converted to type TYPE.
341 This should disappear, but is needed so we can combine expressions and use
342 the fold() interfaces. Long term, we need to develop folding and combine
343 routines that deal with gimple exclusively . */
346 rhs_to_tree (tree type, gimple stmt)
348 location_t loc = gimple_location (stmt);
349 enum tree_code code = gimple_assign_rhs_code (stmt);
350 if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
351 return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
352 gimple_assign_rhs2 (stmt),
353 gimple_assign_rhs3 (stmt));
354 else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
355 return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
356 gimple_assign_rhs2 (stmt));
357 else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
358 return build1 (code, type, gimple_assign_rhs1 (stmt));
359 else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
360 return gimple_assign_rhs1 (stmt);
365 /* Combine OP0 CODE OP1 in the context of a COND_EXPR. Returns
366 the folded result in a form suitable for COND_EXPR_COND or
367 NULL_TREE, if there is no suitable simplified form. If
368 INVARIANT_ONLY is true only gimple_min_invariant results are
369 considered simplified. */
372 combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
373 tree op0, tree op1, bool invariant_only)
377 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
379 fold_defer_overflow_warnings ();
380 t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
383 fold_undefer_overflow_warnings (false, NULL, 0);
387 /* Require that we got a boolean type out if we put one in. */
388 gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
390 /* Canonicalize the combined condition for use in a COND_EXPR. */
391 t = canonicalize_cond_expr_cond (t);
393 /* Bail out if we required an invariant but didn't get one. */
394 if (!t || (invariant_only && !is_gimple_min_invariant (t)))
396 fold_undefer_overflow_warnings (false, NULL, 0);
400 fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
405 /* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
406 of its operand. Return a new comparison tree or NULL_TREE if there
407 were no simplifying combines. */
410 forward_propagate_into_comparison_1 (gimple stmt,
411 enum tree_code code, tree type,
414 tree tmp = NULL_TREE;
415 tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
416 bool single_use0_p = false, single_use1_p = false;
418 /* For comparisons use the first operand, that is likely to
419 simplify comparisons against constants. */
420 if (TREE_CODE (op0) == SSA_NAME)
422 gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
423 if (def_stmt && can_propagate_from (def_stmt))
425 rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
426 tmp = combine_cond_expr_cond (stmt, code, type,
427 rhs0, op1, !single_use0_p);
433 /* If that wasn't successful, try the second operand. */
434 if (TREE_CODE (op1) == SSA_NAME)
436 gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
437 if (def_stmt && can_propagate_from (def_stmt))
439 rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
440 tmp = combine_cond_expr_cond (stmt, code, type,
441 op0, rhs1, !single_use1_p);
447 /* If that wasn't successful either, try both operands. */
448 if (rhs0 != NULL_TREE
449 && rhs1 != NULL_TREE)
450 tmp = combine_cond_expr_cond (stmt, code, type,
452 !(single_use0_p && single_use1_p));
457 /* Propagate from the ssa name definition statements of the assignment
458 from a comparison at *GSI into the conditional if that simplifies it.
459 Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
460 otherwise returns 0. */
463 forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
465 gimple stmt = gsi_stmt (*gsi);
467 bool cfg_changed = false;
468 tree rhs1 = gimple_assign_rhs1 (stmt);
469 tree rhs2 = gimple_assign_rhs2 (stmt);
471 /* Combine the comparison with defining statements. */
472 tmp = forward_propagate_into_comparison_1 (stmt,
473 gimple_assign_rhs_code (stmt),
475 (gimple_assign_lhs (stmt)),
479 gimple_assign_set_rhs_from_tree (gsi, tmp);
480 fold_stmt_inplace (stmt);
483 if (TREE_CODE (rhs1) == SSA_NAME)
484 cfg_changed |= remove_prop_source_from_use (rhs1);
485 if (TREE_CODE (rhs2) == SSA_NAME)
486 cfg_changed |= remove_prop_source_from_use (rhs2);
487 return cfg_changed ? 2 : 1;
493 /* Propagate from the ssa name definition statements of COND_EXPR
494 in GIMPLE_COND statement STMT into the conditional if that simplifies it.
495 Returns zero if no statement was changed, one if there were
496 changes and two if cfg_cleanup needs to run.
498 This must be kept in sync with forward_propagate_into_cond. */
501 forward_propagate_into_gimple_cond (gimple stmt)
504 enum tree_code code = gimple_cond_code (stmt);
505 bool cfg_changed = false;
506 tree rhs1 = gimple_cond_lhs (stmt);
507 tree rhs2 = gimple_cond_rhs (stmt);
509 /* We can do tree combining on SSA_NAME and comparison expressions. */
510 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
513 tmp = forward_propagate_into_comparison_1 (stmt, code,
518 if (dump_file && tmp)
520 fprintf (dump_file, " Replaced '");
521 print_gimple_expr (dump_file, stmt, 0, 0);
522 fprintf (dump_file, "' with '");
523 print_generic_expr (dump_file, tmp, 0);
524 fprintf (dump_file, "'\n");
527 gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
530 if (TREE_CODE (rhs1) == SSA_NAME)
531 cfg_changed |= remove_prop_source_from_use (rhs1);
532 if (TREE_CODE (rhs2) == SSA_NAME)
533 cfg_changed |= remove_prop_source_from_use (rhs2);
534 return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
541 /* Propagate from the ssa name definition statements of COND_EXPR
542 in the rhs of statement STMT into the conditional if that simplifies it.
543 Returns zero if no statement was changed, one if there were
544 changes and two if cfg_cleanup needs to run.
546 This must be kept in sync with forward_propagate_into_gimple_cond. */
549 forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
551 gimple stmt = gsi_stmt (*gsi_p);
552 tree tmp = NULL_TREE;
553 tree cond = gimple_assign_rhs1 (stmt);
555 /* We can do tree combining on SSA_NAME and comparison expressions. */
556 if (COMPARISON_CLASS_P (cond))
557 tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
559 TREE_OPERAND (cond, 0),
560 TREE_OPERAND (cond, 1));
561 else if (TREE_CODE (cond) == SSA_NAME)
563 tree name = cond, rhs0;
564 gimple def_stmt = get_prop_source_stmt (name, true, NULL);
565 if (!def_stmt || !can_propagate_from (def_stmt))
568 rhs0 = gimple_assign_rhs1 (def_stmt);
569 tmp = combine_cond_expr_cond (stmt, NE_EXPR, boolean_type_node, rhs0,
570 build_int_cst (TREE_TYPE (rhs0), 0),
576 if (dump_file && tmp)
578 fprintf (dump_file, " Replaced '");
579 print_generic_expr (dump_file, cond, 0);
580 fprintf (dump_file, "' with '");
581 print_generic_expr (dump_file, tmp, 0);
582 fprintf (dump_file, "'\n");
585 gimple_assign_set_rhs_from_tree (gsi_p, unshare_expr (tmp));
586 stmt = gsi_stmt (*gsi_p);
589 return is_gimple_min_invariant (tmp) ? 2 : 1;
595 /* We've just substituted an ADDR_EXPR into stmt. Update all the
596 relevant data structures to match. */
599 tidy_after_forward_propagate_addr (gimple stmt)
601 /* We may have turned a trapping insn into a non-trapping insn. */
602 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
603 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
606 if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
607 recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
610 /* DEF_RHS contains the address of the 0th element in an array.
611 USE_STMT uses type of DEF_RHS to compute the address of an
612 arbitrary element within the array. The (variable) byte offset
613 of the element is contained in OFFSET.
615 We walk back through the use-def chains of OFFSET to verify that
616 it is indeed computing the offset of an element within the array
617 and extract the index corresponding to the given byte offset.
619 We then try to fold the entire address expression into a form
622 If we are successful, we replace the right hand side of USE_STMT
623 with the new address computation. */
626 forward_propagate_addr_into_variable_array_index (tree offset,
628 gimple_stmt_iterator *use_stmt_gsi)
631 gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
634 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
635 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
636 else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
637 tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
640 if (!host_integerp (tunit, 1))
643 /* Get the offset's defining statement. */
644 offset_def = SSA_NAME_DEF_STMT (offset);
646 /* Try to find an expression for a proper index. This is either a
647 multiplication expression by the element size or just the ssa name we came
648 along in case the element size is one. In that case, however, we do not
649 allow multiplications because they can be computing index to a higher
650 level dimension (PR 37861). */
651 if (integer_onep (tunit))
653 if (is_gimple_assign (offset_def)
654 && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
661 /* The statement which defines OFFSET before type conversion
662 must be a simple GIMPLE_ASSIGN. */
663 if (!is_gimple_assign (offset_def))
666 /* The RHS of the statement which defines OFFSET must be a
667 multiplication of an object by the size of the array elements.
668 This implicitly verifies that the size of the array elements
670 if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
671 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
672 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
674 /* The first operand to the MULT_EXPR is the desired index. */
675 index = gimple_assign_rhs1 (offset_def);
677 /* If we have idx * tunit + CST * tunit re-associate that. */
678 else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
679 || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
680 && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
681 && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
682 && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
683 gimple_assign_rhs2 (offset_def),
684 tunit)) != NULL_TREE)
686 gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
687 if (is_gimple_assign (offset_def2)
688 && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
689 && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
690 && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
692 index = fold_build2 (gimple_assign_rhs_code (offset_def),
694 gimple_assign_rhs1 (offset_def2), tmp);
703 /* Replace the pointer addition with array indexing. */
704 index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
705 true, GSI_SAME_STMT);
706 if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
708 new_rhs = unshare_expr (def_rhs);
709 TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
713 new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
714 unshare_expr (TREE_OPERAND (def_rhs, 0)),
715 index, integer_zero_node, NULL_TREE);
716 new_rhs = build_fold_addr_expr (new_rhs);
717 if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
718 TREE_TYPE (new_rhs)))
720 new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
721 NULL_TREE, true, GSI_SAME_STMT);
722 new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
726 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
727 use_stmt = gsi_stmt (*use_stmt_gsi);
729 /* That should have created gimple, so there is no need to
730 record information to undo the propagation. */
731 fold_stmt_inplace (use_stmt);
732 tidy_after_forward_propagate_addr (use_stmt);
736 /* NAME is a SSA_NAME representing DEF_RHS which is of the form
737 ADDR_EXPR <whatever>.
739 Try to forward propagate the ADDR_EXPR into the use USE_STMT.
740 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
741 node or for recovery of array indexing from pointer arithmetic.
743 Return true if the propagation was successful (the propagation can
744 be not totally successful, yet things may have been changed). */
747 forward_propagate_addr_expr_1 (tree name, tree def_rhs,
748 gimple_stmt_iterator *use_stmt_gsi,
751 tree lhs, rhs, rhs2, array_ref;
752 gimple use_stmt = gsi_stmt (*use_stmt_gsi);
753 enum tree_code rhs_code;
756 gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
758 lhs = gimple_assign_lhs (use_stmt);
759 rhs_code = gimple_assign_rhs_code (use_stmt);
760 rhs = gimple_assign_rhs1 (use_stmt);
762 /* Trivial cases. The use statement could be a trivial copy or a
763 useless conversion. Recurse to the uses of the lhs as copyprop does
764 not copy through different variant pointers and FRE does not catch
765 all useless conversions. Treat the case of a single-use name and
766 a conversion to def_rhs type separate, though. */
767 if (TREE_CODE (lhs) == SSA_NAME
768 && ((rhs_code == SSA_NAME && rhs == name)
769 || CONVERT_EXPR_CODE_P (rhs_code)))
771 /* Only recurse if we don't deal with a single use or we cannot
772 do the propagation to the current statement. In particular
773 we can end up with a conversion needed for a non-invariant
774 address which we cannot do in a single statement. */
776 || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
777 && (!is_gimple_min_invariant (def_rhs)
778 || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
779 && POINTER_TYPE_P (TREE_TYPE (def_rhs))
780 && (TYPE_PRECISION (TREE_TYPE (lhs))
781 > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
782 return forward_propagate_addr_expr (lhs, def_rhs);
784 gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
785 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
786 gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
788 gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
792 /* Propagate through constant pointer adjustments. */
793 if (TREE_CODE (lhs) == SSA_NAME
794 && rhs_code == POINTER_PLUS_EXPR
796 && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
799 /* As we come here with non-invariant addresses in def_rhs we need
800 to make sure we can build a valid constant offsetted address
801 for further propagation. Simply rely on fold building that
802 and check after the fact. */
803 new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
805 fold_convert (ptr_type_node,
806 gimple_assign_rhs2 (use_stmt)));
807 if (TREE_CODE (new_def_rhs) == MEM_REF
808 && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
810 new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
813 /* Recurse. If we could propagate into all uses of lhs do not
814 bother to replace into the current use but just pretend we did. */
815 if (TREE_CODE (new_def_rhs) == ADDR_EXPR
816 && forward_propagate_addr_expr (lhs, new_def_rhs))
819 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
820 gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
821 new_def_rhs, NULL_TREE);
822 else if (is_gimple_min_invariant (new_def_rhs))
823 gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
824 new_def_rhs, NULL_TREE);
827 gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
828 update_stmt (use_stmt);
832 /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
833 ADDR_EXPR will not appear on the LHS. */
834 lhs = gimple_assign_lhs (use_stmt);
835 while (handled_component_p (lhs))
836 lhs = TREE_OPERAND (lhs, 0);
838 /* Now see if the LHS node is a MEM_REF using NAME. If so,
839 propagate the ADDR_EXPR into the use of NAME and fold the result. */
840 if (TREE_CODE (lhs) == MEM_REF
841 && TREE_OPERAND (lhs, 0) == name)
844 HOST_WIDE_INT def_rhs_offset;
845 /* If the address is invariant we can always fold it. */
846 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
849 double_int off = mem_ref_offset (lhs);
851 off = double_int_add (off,
852 shwi_to_double_int (def_rhs_offset));
853 if (TREE_CODE (def_rhs_base) == MEM_REF)
855 off = double_int_add (off, mem_ref_offset (def_rhs_base));
856 new_ptr = TREE_OPERAND (def_rhs_base, 0);
859 new_ptr = build_fold_addr_expr (def_rhs_base);
860 TREE_OPERAND (lhs, 0) = new_ptr;
861 TREE_OPERAND (lhs, 1)
862 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
863 tidy_after_forward_propagate_addr (use_stmt);
864 /* Continue propagating into the RHS if this was not the only use. */
868 /* If the LHS is a plain dereference and the value type is the same as
869 that of the pointed-to type of the address we can put the
870 dereferenced address on the LHS preserving the original alias-type. */
871 else if (gimple_assign_lhs (use_stmt) == lhs
872 && useless_type_conversion_p
873 (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
874 TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
876 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
877 tree new_offset, new_base, saved;
878 while (handled_component_p (*def_rhs_basep))
879 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
880 saved = *def_rhs_basep;
881 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
883 new_base = TREE_OPERAND (*def_rhs_basep, 0);
885 = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
886 TREE_OPERAND (*def_rhs_basep, 1));
890 new_base = build_fold_addr_expr (*def_rhs_basep);
891 new_offset = TREE_OPERAND (lhs, 1);
893 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
894 new_base, new_offset);
895 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
896 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
897 gimple_assign_set_lhs (use_stmt,
898 unshare_expr (TREE_OPERAND (def_rhs, 0)));
899 *def_rhs_basep = saved;
900 tidy_after_forward_propagate_addr (use_stmt);
901 /* Continue propagating into the RHS if this was not the
907 /* We can have a struct assignment dereferencing our name twice.
908 Note that we didn't propagate into the lhs to not falsely
909 claim we did when propagating into the rhs. */
913 /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
914 nodes from the RHS. */
915 rhs = gimple_assign_rhs1 (use_stmt);
916 if (TREE_CODE (rhs) == ADDR_EXPR)
917 rhs = TREE_OPERAND (rhs, 0);
918 while (handled_component_p (rhs))
919 rhs = TREE_OPERAND (rhs, 0);
921 /* Now see if the RHS node is a MEM_REF using NAME. If so,
922 propagate the ADDR_EXPR into the use of NAME and fold the result. */
923 if (TREE_CODE (rhs) == MEM_REF
924 && TREE_OPERAND (rhs, 0) == name)
927 HOST_WIDE_INT def_rhs_offset;
928 if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
931 double_int off = mem_ref_offset (rhs);
933 off = double_int_add (off,
934 shwi_to_double_int (def_rhs_offset));
935 if (TREE_CODE (def_rhs_base) == MEM_REF)
937 off = double_int_add (off, mem_ref_offset (def_rhs_base));
938 new_ptr = TREE_OPERAND (def_rhs_base, 0);
941 new_ptr = build_fold_addr_expr (def_rhs_base);
942 TREE_OPERAND (rhs, 0) = new_ptr;
943 TREE_OPERAND (rhs, 1)
944 = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
945 fold_stmt_inplace (use_stmt);
946 tidy_after_forward_propagate_addr (use_stmt);
949 /* If the RHS is a plain dereference and the value type is the same as
950 that of the pointed-to type of the address we can put the
951 dereferenced address on the RHS preserving the original alias-type. */
952 else if (gimple_assign_rhs1 (use_stmt) == rhs
953 && useless_type_conversion_p
954 (TREE_TYPE (gimple_assign_lhs (use_stmt)),
955 TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
957 tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
958 tree new_offset, new_base, saved;
959 while (handled_component_p (*def_rhs_basep))
960 def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
961 saved = *def_rhs_basep;
962 if (TREE_CODE (*def_rhs_basep) == MEM_REF)
964 new_base = TREE_OPERAND (*def_rhs_basep, 0);
966 = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
967 TREE_OPERAND (*def_rhs_basep, 1));
971 new_base = build_fold_addr_expr (*def_rhs_basep);
972 new_offset = TREE_OPERAND (rhs, 1);
974 *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
975 new_base, new_offset);
976 TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
977 TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
978 gimple_assign_set_rhs1 (use_stmt,
979 unshare_expr (TREE_OPERAND (def_rhs, 0)));
980 *def_rhs_basep = saved;
981 fold_stmt_inplace (use_stmt);
982 tidy_after_forward_propagate_addr (use_stmt);
987 /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
989 if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
990 || gimple_assign_rhs1 (use_stmt) != name)
993 /* The remaining cases are all for turning pointer arithmetic into
994 array indexing. They only apply when we have the address of
995 element zero in an array. If that is not the case then there
997 array_ref = TREE_OPERAND (def_rhs, 0);
998 if ((TREE_CODE (array_ref) != ARRAY_REF
999 || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1000 || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1001 && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1004 rhs2 = gimple_assign_rhs2 (use_stmt);
1005 /* Optimize &x[C1] p+ C2 to &x p+ C3 with C3 = C1 * element_size + C2. */
1006 if (TREE_CODE (rhs2) == INTEGER_CST)
1008 tree new_rhs = build1_loc (gimple_location (use_stmt),
1009 ADDR_EXPR, TREE_TYPE (def_rhs),
1010 fold_build2 (MEM_REF,
1011 TREE_TYPE (TREE_TYPE (def_rhs)),
1012 unshare_expr (def_rhs),
1013 fold_convert (ptr_type_node,
1015 gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1016 use_stmt = gsi_stmt (*use_stmt_gsi);
1017 update_stmt (use_stmt);
1018 tidy_after_forward_propagate_addr (use_stmt);
1022 /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1023 converting a multiplication of an index by the size of the
1024 array elements, then the result is converted into the proper
1025 type for the arithmetic. */
1026 if (TREE_CODE (rhs2) == SSA_NAME
1027 && (TREE_CODE (array_ref) != ARRAY_REF
1028 || integer_zerop (TREE_OPERAND (array_ref, 1)))
1029 && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1030 /* Avoid problems with IVopts creating PLUS_EXPRs with a
1031 different type than their operands. */
1032 && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1033 return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1038 /* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1040 Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1041 Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1042 node or for recovery of array indexing from pointer arithmetic.
1043 Returns true, if all uses have been propagated into. */
1046 forward_propagate_addr_expr (tree name, tree rhs)
1048 int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1049 imm_use_iterator iter;
1052 bool single_use_p = has_single_use (name);
1054 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1059 /* If the use is not in a simple assignment statement, then
1060 there is nothing we can do. */
1061 if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1063 if (!is_gimple_debug (use_stmt))
1068 /* If the use is in a deeper loop nest, then we do not want
1069 to propagate non-invariant ADDR_EXPRs into the loop as that
1070 is likely adding expression evaluations into the loop. */
1071 if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1072 && !is_gimple_min_invariant (rhs))
1079 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1080 result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1082 /* If the use has moved to a different statement adjust
1083 the update machinery for the old statement too. */
1084 if (use_stmt != gsi_stmt (gsi))
1086 update_stmt (use_stmt);
1087 use_stmt = gsi_stmt (gsi);
1090 update_stmt (use_stmt);
1094 /* Remove intermediate now unused copy and conversion chains. */
1095 use_rhs = gimple_assign_rhs1 (use_stmt);
1097 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1098 && TREE_CODE (use_rhs) == SSA_NAME
1099 && has_zero_uses (gimple_assign_lhs (use_stmt)))
1101 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1102 release_defs (use_stmt);
1103 gsi_remove (&gsi, true);
1107 return all && has_zero_uses (name);
1111 /* Forward propagate the comparison defined in STMT like
1112 cond_1 = x CMP y to uses of the form
1116 Returns true if stmt is now unused. */
1119 forward_propagate_comparison (gimple stmt)
1121 tree name = gimple_assign_lhs (stmt);
1123 tree tmp = NULL_TREE;
1124 gimple_stmt_iterator gsi;
1125 enum tree_code code;
1128 /* Don't propagate ssa names that occur in abnormal phis. */
1129 if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1130 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1131 || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1132 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1135 /* Do not un-cse comparisons. But propagate through copies. */
1136 use_stmt = get_prop_dest_stmt (name, &name);
1138 || !is_gimple_assign (use_stmt))
1141 code = gimple_assign_rhs_code (use_stmt);
1142 lhs = gimple_assign_lhs (use_stmt);
1143 if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1146 /* We can propagate the condition into a statement that
1147 computes the logical negation of the comparison result. */
1148 if ((code == BIT_NOT_EXPR
1149 && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1150 || (code == BIT_XOR_EXPR
1151 && integer_onep (gimple_assign_rhs2 (use_stmt))))
1153 tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1154 bool nans = HONOR_NANS (TYPE_MODE (type));
1155 enum tree_code inv_code;
1156 inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1157 if (inv_code == ERROR_MARK)
1160 tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1161 gimple_assign_rhs2 (stmt));
1166 gsi = gsi_for_stmt (use_stmt);
1167 gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1168 use_stmt = gsi_stmt (gsi);
1169 update_stmt (use_stmt);
1171 if (dump_file && (dump_flags & TDF_DETAILS))
1173 fprintf (dump_file, " Replaced '");
1174 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1175 fprintf (dump_file, "' with '");
1176 print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1177 fprintf (dump_file, "'\n");
1180 /* Remove defining statements. */
1181 return remove_prop_source_from_use (name);
1185 /* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1186 If so, we can change STMT into lhs = y which can later be copy
1187 propagated. Similarly for negation.
1189 This could trivially be formulated as a forward propagation
1190 to immediate uses. However, we already had an implementation
1191 from DOM which used backward propagation via the use-def links.
1193 It turns out that backward propagation is actually faster as
1194 there's less work to do for each NOT/NEG expression we find.
1195 Backwards propagation needs to look at the statement in a single
1196 backlink. Forward propagation needs to look at potentially more
1197 than one forward link.
1199 Returns true when the statement was changed. */
1202 simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1204 gimple stmt = gsi_stmt (*gsi_p);
1205 tree rhs = gimple_assign_rhs1 (stmt);
1206 gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1208 /* See if the RHS_DEF_STMT has the same form as our statement. */
1209 if (is_gimple_assign (rhs_def_stmt)
1210 && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1212 tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1214 /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME. */
1215 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1216 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1218 gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1219 stmt = gsi_stmt (*gsi_p);
1228 /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1229 the condition which we may be able to optimize better. */
1232 simplify_gimple_switch (gimple stmt)
1234 tree cond = gimple_switch_index (stmt);
1238 /* The optimization that we really care about is removing unnecessary
1239 casts. That will let us do much better in propagating the inferred
1240 constant at the switch target. */
1241 if (TREE_CODE (cond) == SSA_NAME)
1243 def_stmt = SSA_NAME_DEF_STMT (cond);
1244 if (is_gimple_assign (def_stmt))
1246 if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1251 def = gimple_assign_rhs1 (def_stmt);
1253 /* ??? Why was Jeff testing this? We are gimple... */
1254 gcc_checking_assert (is_gimple_val (def));
1256 to = TREE_TYPE (cond);
1257 ti = TREE_TYPE (def);
1259 /* If we have an extension that preserves value, then we
1260 can copy the source value into the switch. */
1262 need_precision = TYPE_PRECISION (ti);
1264 if (! INTEGRAL_TYPE_P (ti))
1266 else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1268 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1269 need_precision += 1;
1270 if (TYPE_PRECISION (to) < need_precision)
1275 gimple_switch_set_index (stmt, def);
1286 /* For pointers p2 and p1 return p2 - p1 if the
1287 difference is known and constant, otherwise return NULL. */
1290 constant_pointer_difference (tree p1, tree p2)
1293 #define CPD_ITERATIONS 5
1294 tree exps[2][CPD_ITERATIONS];
1295 tree offs[2][CPD_ITERATIONS];
1298 for (i = 0; i < 2; i++)
1300 tree p = i ? p1 : p2;
1301 tree off = size_zero_node;
1303 enum tree_code code;
1305 /* For each of p1 and p2 we need to iterate at least
1306 twice, to handle ADDR_EXPR directly in p1/p2,
1307 SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1308 on definition's stmt RHS. Iterate a few extra times. */
1312 if (!POINTER_TYPE_P (TREE_TYPE (p)))
1314 if (TREE_CODE (p) == ADDR_EXPR)
1316 tree q = TREE_OPERAND (p, 0);
1317 HOST_WIDE_INT offset;
1318 tree base = get_addr_base_and_unit_offset (q, &offset);
1323 off = size_binop (PLUS_EXPR, off, size_int (offset));
1325 if (TREE_CODE (q) == MEM_REF
1326 && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1328 p = TREE_OPERAND (q, 0);
1329 off = size_binop (PLUS_EXPR, off,
1330 double_int_to_tree (sizetype,
1331 mem_ref_offset (q)));
1340 if (TREE_CODE (p) != SSA_NAME)
1344 if (j == CPD_ITERATIONS)
1346 stmt = SSA_NAME_DEF_STMT (p);
1347 if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1349 code = gimple_assign_rhs_code (stmt);
1350 if (code == POINTER_PLUS_EXPR)
1352 if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1354 off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1355 p = gimple_assign_rhs1 (stmt);
1357 else if (code == ADDR_EXPR || code == NOP_EXPR)
1358 p = gimple_assign_rhs1 (stmt);
1366 for (i = 0; i < cnt[0]; i++)
1367 for (j = 0; j < cnt[1]; j++)
1368 if (exps[0][i] == exps[1][j])
1369 return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1374 /* *GSI_P is a GIMPLE_CALL to a builtin function.
1376 memcpy (p, "abcd", 4);
1377 memset (p + 4, ' ', 3);
1379 memcpy (p, "abcd ", 7);
1380 call if the latter can be stored by pieces during expansion. */
1383 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1385 gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1386 tree vuse = gimple_vuse (stmt2);
1389 stmt1 = SSA_NAME_DEF_STMT (vuse);
1391 switch (DECL_FUNCTION_CODE (callee2))
1393 case BUILT_IN_MEMSET:
1394 if (gimple_call_num_args (stmt2) != 3
1395 || gimple_call_lhs (stmt2)
1397 || BITS_PER_UNIT != 8)
1402 tree ptr1, src1, str1, off1, len1, lhs1;
1403 tree ptr2 = gimple_call_arg (stmt2, 0);
1404 tree val2 = gimple_call_arg (stmt2, 1);
1405 tree len2 = gimple_call_arg (stmt2, 2);
1406 tree diff, vdef, new_str_cst;
1408 unsigned int ptr1_align;
1409 unsigned HOST_WIDE_INT src_len;
1411 use_operand_p use_p;
1413 if (!host_integerp (val2, 0)
1414 || !host_integerp (len2, 1))
1416 if (is_gimple_call (stmt1))
1418 /* If first stmt is a call, it needs to be memcpy
1419 or mempcpy, with string literal as second argument and
1421 callee1 = gimple_call_fndecl (stmt1);
1422 if (callee1 == NULL_TREE
1423 || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1424 || gimple_call_num_args (stmt1) != 3)
1426 if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1427 && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1429 ptr1 = gimple_call_arg (stmt1, 0);
1430 src1 = gimple_call_arg (stmt1, 1);
1431 len1 = gimple_call_arg (stmt1, 2);
1432 lhs1 = gimple_call_lhs (stmt1);
1433 if (!host_integerp (len1, 1))
1435 str1 = string_constant (src1, &off1);
1436 if (str1 == NULL_TREE)
1438 if (!host_integerp (off1, 1)
1439 || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1440 || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1441 - tree_low_cst (off1, 1)) > 0
1442 || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1443 || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1444 != TYPE_MODE (char_type_node))
1447 else if (gimple_assign_single_p (stmt1))
1449 /* Otherwise look for length 1 memcpy optimized into
1451 ptr1 = gimple_assign_lhs (stmt1);
1452 src1 = gimple_assign_rhs1 (stmt1);
1453 if (TREE_CODE (ptr1) != MEM_REF
1454 || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1455 || !host_integerp (src1, 0))
1457 ptr1 = build_fold_addr_expr (ptr1);
1458 callee1 = NULL_TREE;
1459 len1 = size_one_node;
1461 off1 = size_zero_node;
1467 diff = constant_pointer_difference (ptr1, ptr2);
1468 if (diff == NULL && lhs1 != NULL)
1470 diff = constant_pointer_difference (lhs1, ptr2);
1471 if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1473 diff = size_binop (PLUS_EXPR, diff,
1474 fold_convert (sizetype, len1));
1476 /* If the difference between the second and first destination pointer
1477 is not constant, or is bigger than memcpy length, bail out. */
1479 || !host_integerp (diff, 1)
1480 || tree_int_cst_lt (len1, diff))
1483 /* Use maximum of difference plus memset length and memcpy length
1484 as the new memcpy length, if it is too big, bail out. */
1485 src_len = tree_low_cst (diff, 1);
1486 src_len += tree_low_cst (len2, 1);
1487 if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1488 src_len = tree_low_cst (len1, 1);
1492 /* If mempcpy value is used elsewhere, bail out, as mempcpy
1493 with bigger length will return different result. */
1494 if (lhs1 != NULL_TREE
1495 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1496 && (TREE_CODE (lhs1) != SSA_NAME
1497 || !single_imm_use (lhs1, &use_p, &use_stmt)
1498 || use_stmt != stmt2))
1501 /* If anything reads memory in between memcpy and memset
1502 call, the modified memcpy call might change it. */
1503 vdef = gimple_vdef (stmt1);
1505 && (!single_imm_use (vdef, &use_p, &use_stmt)
1506 || use_stmt != stmt2))
1509 ptr1_align = get_pointer_alignment (ptr1);
1510 /* Construct the new source string literal. */
1511 src_buf = XALLOCAVEC (char, src_len + 1);
1514 TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1515 tree_low_cst (len1, 1));
1517 src_buf[0] = tree_low_cst (src1, 0);
1518 memset (src_buf + tree_low_cst (diff, 1),
1519 tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1520 src_buf[src_len] = '\0';
1521 /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1522 handle embedded '\0's. */
1523 if (strlen (src_buf) != src_len)
1525 rtl_profile_for_bb (gimple_bb (stmt2));
1526 /* If the new memcpy wouldn't be emitted by storing the literal
1527 by pieces, this optimization might enlarge .rodata too much,
1528 as commonly used string literals couldn't be shared any
1530 if (!can_store_by_pieces (src_len,
1531 builtin_strncpy_read_str,
1532 src_buf, ptr1_align, false))
1535 new_str_cst = build_string_literal (src_len, src_buf);
1538 /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1540 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1541 gimple_call_set_lhs (stmt1, NULL_TREE);
1542 gimple_call_set_arg (stmt1, 1, new_str_cst);
1543 gimple_call_set_arg (stmt1, 2,
1544 build_int_cst (TREE_TYPE (len1), src_len));
1545 update_stmt (stmt1);
1546 unlink_stmt_vdef (stmt2);
1547 gsi_remove (gsi_p, true);
1548 release_defs (stmt2);
1549 if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1550 release_ssa_name (lhs1);
1555 /* Otherwise, if STMT1 is length 1 memcpy optimized into
1556 assignment, remove STMT1 and change memset call into
1558 gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1560 if (!is_gimple_val (ptr1))
1561 ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1562 true, GSI_SAME_STMT);
1563 gimple_call_set_fndecl (stmt2, built_in_decls [BUILT_IN_MEMCPY]);
1564 gimple_call_set_arg (stmt2, 0, ptr1);
1565 gimple_call_set_arg (stmt2, 1, new_str_cst);
1566 gimple_call_set_arg (stmt2, 2,
1567 build_int_cst (TREE_TYPE (len2), src_len));
1568 unlink_stmt_vdef (stmt1);
1569 gsi_remove (&gsi, true);
1570 release_defs (stmt1);
1571 update_stmt (stmt2);
1582 /* Checks if expression has type of one-bit precision, or is a known
1583 truth-valued expression. */
1585 truth_valued_ssa_name (tree name)
1588 tree type = TREE_TYPE (name);
1590 if (!INTEGRAL_TYPE_P (type))
1592 /* Don't check here for BOOLEAN_TYPE as the precision isn't
1593 necessarily one and so ~X is not equal to !X. */
1594 if (TYPE_PRECISION (type) == 1)
1596 def = SSA_NAME_DEF_STMT (name);
1597 if (is_gimple_assign (def))
1598 return truth_value_p (gimple_assign_rhs_code (def));
1602 /* Helper routine for simplify_bitwise_binary_1 function.
1603 Return for the SSA name NAME the expression X if it mets condition
1604 NAME = !X. Otherwise return NULL_TREE.
1605 Detected patterns for NAME = !X are:
1606 !X and X == 0 for X with integral type.
1607 X ^ 1, X != 1,or ~X for X with integral type with precision of one. */
1609 lookup_logical_inverted_value (tree name)
1612 enum tree_code code;
1615 /* If name has none-intergal type, or isn't a SSA_NAME, then
1617 if (TREE_CODE (name) != SSA_NAME
1618 || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1620 def = SSA_NAME_DEF_STMT (name);
1621 if (!is_gimple_assign (def))
1624 code = gimple_assign_rhs_code (def);
1625 op1 = gimple_assign_rhs1 (def);
1628 /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1629 If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return. */
1630 if (code == EQ_EXPR || code == NE_EXPR
1631 || code == BIT_XOR_EXPR)
1632 op2 = gimple_assign_rhs2 (def);
1637 if (truth_valued_ssa_name (name))
1641 /* Check if we have X == 0 and X has an integral type. */
1642 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1644 if (integer_zerop (op2))
1648 /* Check if we have X != 1 and X is a truth-valued. */
1649 if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1651 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1655 /* Check if we have X ^ 1 and X is truth valued. */
1656 if (integer_onep (op2) && truth_valued_ssa_name (op1))
1666 /* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1667 operations CODE, if one operand has the logically inverted
1668 value of the other. */
1670 simplify_bitwise_binary_1 (enum tree_code code, tree type,
1671 tree arg1, tree arg2)
1675 /* If CODE isn't a bitwise binary operation, return NULL_TREE. */
1676 if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1677 && code != BIT_XOR_EXPR)
1680 /* First check if operands ARG1 and ARG2 are equal. If so
1681 return NULL_TREE as this optimization is handled fold_stmt. */
1684 /* See if we have in arguments logical-not patterns. */
1685 if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1687 && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1692 if (code == BIT_AND_EXPR)
1693 return fold_convert (type, integer_zero_node);
1694 /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued. */
1695 if (truth_valued_ssa_name (anot))
1696 return fold_convert (type, integer_one_node);
1698 /* ??? Otherwise result is (X != 0 ? X : 1). not handled. */
1702 /* Simplify bitwise binary operations.
1703 Return true if a transformation applied, otherwise return false. */
1706 simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1708 gimple stmt = gsi_stmt (*gsi);
1709 tree arg1 = gimple_assign_rhs1 (stmt);
1710 tree arg2 = gimple_assign_rhs2 (stmt);
1711 enum tree_code code = gimple_assign_rhs_code (stmt);
1713 gimple def1 = NULL, def2 = NULL;
1714 tree def1_arg1, def2_arg1;
1715 enum tree_code def1_code, def2_code;
1717 def1_code = TREE_CODE (arg1);
1719 if (TREE_CODE (arg1) == SSA_NAME)
1721 def1 = SSA_NAME_DEF_STMT (arg1);
1722 if (is_gimple_assign (def1))
1724 def1_code = gimple_assign_rhs_code (def1);
1725 def1_arg1 = gimple_assign_rhs1 (def1);
1729 def2_code = TREE_CODE (arg2);
1731 if (TREE_CODE (arg2) == SSA_NAME)
1733 def2 = SSA_NAME_DEF_STMT (arg2);
1734 if (is_gimple_assign (def2))
1736 def2_code = gimple_assign_rhs_code (def2);
1737 def2_arg1 = gimple_assign_rhs1 (def2);
1741 /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)). */
1742 if (TREE_CODE (arg2) == INTEGER_CST
1743 && CONVERT_EXPR_CODE_P (def1_code)
1744 && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1745 && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1748 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1750 gimple_build_assign_with_ops (code, tem, def1_arg1,
1751 fold_convert_loc (gimple_location (stmt),
1752 TREE_TYPE (def1_arg1),
1754 tem = make_ssa_name (tem, newop);
1755 gimple_assign_set_lhs (newop, tem);
1756 gimple_set_location (newop, gimple_location (stmt));
1757 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1758 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1759 tem, NULL_TREE, NULL_TREE);
1760 update_stmt (gsi_stmt (*gsi));
1764 /* For bitwise binary operations apply operand conversions to the
1765 binary operation result instead of to the operands. This allows
1766 to combine successive conversions and bitwise binary operations. */
1767 if (CONVERT_EXPR_CODE_P (def1_code)
1768 && CONVERT_EXPR_CODE_P (def2_code)
1769 && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1770 /* Make sure that the conversion widens the operands, or has same
1771 precision, or that it changes the operation to a bitfield
1773 && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1774 <= TYPE_PRECISION (TREE_TYPE (arg1)))
1775 || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1777 || (TYPE_PRECISION (TREE_TYPE (arg1))
1778 != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1781 tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1783 newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1784 tem = make_ssa_name (tem, newop);
1785 gimple_assign_set_lhs (newop, tem);
1786 gimple_set_location (newop, gimple_location (stmt));
1787 gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1788 gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1789 tem, NULL_TREE, NULL_TREE);
1790 update_stmt (gsi_stmt (*gsi));
1794 /* (a | CST1) & CST2 -> (a & CST2) | (CST1 & CST2). */
1795 if (code == BIT_AND_EXPR
1796 && def1_code == BIT_IOR_EXPR
1797 && TREE_CODE (arg2) == INTEGER_CST
1798 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1800 tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1801 arg2, gimple_assign_rhs2 (def1));
1804 if (integer_zerop (cst))
1806 gimple_assign_set_rhs1 (stmt, def1_arg1);
1810 tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1811 newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1812 tem, def1_arg1, arg2);
1813 tem = make_ssa_name (tem, newop);
1814 gimple_assign_set_lhs (newop, tem);
1815 gimple_set_location (newop, gimple_location (stmt));
1816 /* Make sure to re-process the new stmt as it's walking upwards. */
1817 gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1818 gimple_assign_set_rhs1 (stmt, tem);
1819 gimple_assign_set_rhs2 (stmt, cst);
1820 gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1825 /* Combine successive equal operations with constants. */
1826 if ((code == BIT_AND_EXPR
1827 || code == BIT_IOR_EXPR
1828 || code == BIT_XOR_EXPR)
1829 && def1_code == code
1830 && TREE_CODE (arg2) == INTEGER_CST
1831 && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1833 tree cst = fold_build2 (code, TREE_TYPE (arg2),
1834 arg2, gimple_assign_rhs2 (def1));
1835 gimple_assign_set_rhs1 (stmt, def1_arg1);
1836 gimple_assign_set_rhs2 (stmt, cst);
1841 /* Canonicalize X ^ ~0 to ~X. */
1842 if (code == BIT_XOR_EXPR
1843 && TREE_CODE (arg2) == INTEGER_CST
1844 && integer_all_onesp (arg2))
1846 gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1847 gcc_assert (gsi_stmt (*gsi) == stmt);
1852 /* Try simple folding for X op !X, and X op X. */
1853 res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1854 if (res != NULL_TREE)
1856 gimple_assign_set_rhs_from_tree (gsi, res);
1857 update_stmt (gsi_stmt (*gsi));
1865 /* Perform re-associations of the plus or minus statement STMT that are
1866 always permitted. Returns true if the CFG was changed. */
1869 associate_plusminus (gimple stmt)
1871 tree rhs1 = gimple_assign_rhs1 (stmt);
1872 tree rhs2 = gimple_assign_rhs2 (stmt);
1873 enum tree_code code = gimple_assign_rhs_code (stmt);
1874 gimple_stmt_iterator gsi;
1877 /* We can't reassociate at all for saturating types. */
1878 if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1881 /* First contract negates. */
1886 /* A +- (-B) -> A -+ B. */
1887 if (TREE_CODE (rhs2) == SSA_NAME)
1889 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1890 if (is_gimple_assign (def_stmt)
1891 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1892 && can_propagate_from (def_stmt))
1894 code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1895 gimple_assign_set_rhs_code (stmt, code);
1896 rhs2 = gimple_assign_rhs1 (def_stmt);
1897 gimple_assign_set_rhs2 (stmt, rhs2);
1898 gimple_set_modified (stmt, true);
1903 /* (-A) + B -> B - A. */
1904 if (TREE_CODE (rhs1) == SSA_NAME
1905 && code == PLUS_EXPR)
1907 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1908 if (is_gimple_assign (def_stmt)
1909 && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1910 && can_propagate_from (def_stmt))
1913 gimple_assign_set_rhs_code (stmt, code);
1915 gimple_assign_set_rhs1 (stmt, rhs1);
1916 rhs2 = gimple_assign_rhs1 (def_stmt);
1917 gimple_assign_set_rhs2 (stmt, rhs2);
1918 gimple_set_modified (stmt, true);
1925 /* We can't reassociate floating-point or fixed-point plus or minus
1926 because of saturation to +-Inf. */
1927 if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1928 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1931 /* Second match patterns that allow contracting a plus-minus pair
1932 irrespective of overflow issues.
1934 (A +- B) - A -> +- B
1936 (CST +- A) +- CST -> CST +- A
1937 (A + CST) +- CST -> A + CST
1940 A - (A +- B) -> -+ B
1941 A +- (B +- A) -> +- B
1942 CST +- (CST +- A) -> CST +- A
1943 CST +- (A +- CST) -> CST +- A
1946 via commutating the addition and contracting operations to zero
1947 by reassociation. */
1949 gsi = gsi_for_stmt (stmt);
1950 if (TREE_CODE (rhs1) == SSA_NAME)
1952 gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1953 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1955 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1956 if (def_code == PLUS_EXPR
1957 || def_code == MINUS_EXPR)
1959 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1960 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
1961 if (operand_equal_p (def_rhs1, rhs2, 0)
1962 && code == MINUS_EXPR)
1964 /* (A +- B) - A -> +- B. */
1965 code = ((def_code == PLUS_EXPR)
1966 ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
1969 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1970 gcc_assert (gsi_stmt (gsi) == stmt);
1971 gimple_set_modified (stmt, true);
1973 else if (operand_equal_p (def_rhs2, rhs2, 0)
1974 && code != def_code)
1976 /* (A +- B) -+ B -> A. */
1977 code = TREE_CODE (def_rhs1);
1980 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
1981 gcc_assert (gsi_stmt (gsi) == stmt);
1982 gimple_set_modified (stmt, true);
1984 else if (TREE_CODE (rhs2) == INTEGER_CST
1985 && TREE_CODE (def_rhs1) == INTEGER_CST)
1987 /* (CST +- A) +- CST -> CST +- A. */
1988 tree cst = fold_binary (code, TREE_TYPE (rhs1),
1990 if (cst && !TREE_OVERFLOW (cst))
1993 gimple_assign_set_rhs_code (stmt, code);
1995 gimple_assign_set_rhs1 (stmt, rhs1);
1997 gimple_assign_set_rhs2 (stmt, rhs2);
1998 gimple_set_modified (stmt, true);
2001 else if (TREE_CODE (rhs2) == INTEGER_CST
2002 && TREE_CODE (def_rhs2) == INTEGER_CST
2003 && def_code == PLUS_EXPR)
2005 /* (A + CST) +- CST -> A + CST. */
2006 tree cst = fold_binary (code, TREE_TYPE (rhs1),
2008 if (cst && !TREE_OVERFLOW (cst))
2011 gimple_assign_set_rhs_code (stmt, code);
2013 gimple_assign_set_rhs1 (stmt, rhs1);
2015 gimple_assign_set_rhs2 (stmt, rhs2);
2016 gimple_set_modified (stmt, true);
2020 else if (def_code == BIT_NOT_EXPR
2021 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2023 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2024 if (code == PLUS_EXPR
2025 && operand_equal_p (def_rhs1, rhs2, 0))
2029 rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2031 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2032 gcc_assert (gsi_stmt (gsi) == stmt);
2033 gimple_set_modified (stmt, true);
2035 else if (code == PLUS_EXPR
2036 && integer_onep (rhs1))
2042 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2043 gcc_assert (gsi_stmt (gsi) == stmt);
2044 gimple_set_modified (stmt, true);
2050 if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2052 gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2053 if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2055 enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2056 if (def_code == PLUS_EXPR
2057 || def_code == MINUS_EXPR)
2059 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2060 tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2061 if (operand_equal_p (def_rhs1, rhs1, 0)
2062 && code == MINUS_EXPR)
2064 /* A - (A +- B) -> -+ B. */
2065 code = ((def_code == PLUS_EXPR)
2066 ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2069 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2070 gcc_assert (gsi_stmt (gsi) == stmt);
2071 gimple_set_modified (stmt, true);
2073 else if (operand_equal_p (def_rhs2, rhs1, 0)
2074 && code != def_code)
2076 /* A +- (B +- A) -> +- B. */
2077 code = ((code == PLUS_EXPR)
2078 ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2081 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2082 gcc_assert (gsi_stmt (gsi) == stmt);
2083 gimple_set_modified (stmt, true);
2085 else if (TREE_CODE (rhs1) == INTEGER_CST
2086 && TREE_CODE (def_rhs1) == INTEGER_CST)
2088 /* CST +- (CST +- A) -> CST +- A. */
2089 tree cst = fold_binary (code, TREE_TYPE (rhs2),
2091 if (cst && !TREE_OVERFLOW (cst))
2093 code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2094 gimple_assign_set_rhs_code (stmt, code);
2096 gimple_assign_set_rhs1 (stmt, rhs1);
2098 gimple_assign_set_rhs2 (stmt, rhs2);
2099 gimple_set_modified (stmt, true);
2102 else if (TREE_CODE (rhs1) == INTEGER_CST
2103 && TREE_CODE (def_rhs2) == INTEGER_CST)
2105 /* CST +- (A +- CST) -> CST +- A. */
2106 tree cst = fold_binary (def_code == code
2107 ? PLUS_EXPR : MINUS_EXPR,
2110 if (cst && !TREE_OVERFLOW (cst))
2113 gimple_assign_set_rhs1 (stmt, rhs1);
2115 gimple_assign_set_rhs2 (stmt, rhs2);
2116 gimple_set_modified (stmt, true);
2120 else if (def_code == BIT_NOT_EXPR
2121 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2123 tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2124 if (code == PLUS_EXPR
2125 && operand_equal_p (def_rhs1, rhs1, 0))
2129 rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2131 gimple_assign_set_rhs_with_ops (&gsi, code, rhs1, NULL_TREE);
2132 gcc_assert (gsi_stmt (gsi) == stmt);
2133 gimple_set_modified (stmt, true);
2140 if (gimple_modified_p (stmt))
2142 fold_stmt_inplace (stmt);
2144 if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2145 && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2152 /* Combine two conversions in a row for the second conversion at *GSI.
2153 Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2154 run. Else it returns 0. */
2157 combine_conversions (gimple_stmt_iterator *gsi)
2159 gimple stmt = gsi_stmt (*gsi);
2162 enum tree_code code = gimple_assign_rhs_code (stmt);
2164 gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2165 || code == FLOAT_EXPR
2166 || code == FIX_TRUNC_EXPR);
2168 lhs = gimple_assign_lhs (stmt);
2169 op0 = gimple_assign_rhs1 (stmt);
2170 if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2172 gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2176 if (TREE_CODE (op0) != SSA_NAME)
2179 def_stmt = SSA_NAME_DEF_STMT (op0);
2180 if (!is_gimple_assign (def_stmt))
2183 if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2185 tree defop0 = gimple_assign_rhs1 (def_stmt);
2186 tree type = TREE_TYPE (lhs);
2187 tree inside_type = TREE_TYPE (defop0);
2188 tree inter_type = TREE_TYPE (op0);
2189 int inside_int = INTEGRAL_TYPE_P (inside_type);
2190 int inside_ptr = POINTER_TYPE_P (inside_type);
2191 int inside_float = FLOAT_TYPE_P (inside_type);
2192 int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2193 unsigned int inside_prec = TYPE_PRECISION (inside_type);
2194 int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2195 int inter_int = INTEGRAL_TYPE_P (inter_type);
2196 int inter_ptr = POINTER_TYPE_P (inter_type);
2197 int inter_float = FLOAT_TYPE_P (inter_type);
2198 int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2199 unsigned int inter_prec = TYPE_PRECISION (inter_type);
2200 int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2201 int final_int = INTEGRAL_TYPE_P (type);
2202 int final_ptr = POINTER_TYPE_P (type);
2203 int final_float = FLOAT_TYPE_P (type);
2204 int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2205 unsigned int final_prec = TYPE_PRECISION (type);
2206 int final_unsignedp = TYPE_UNSIGNED (type);
2208 /* In addition to the cases of two conversions in a row
2209 handled below, if we are converting something to its own
2210 type via an object of identical or wider precision, neither
2211 conversion is needed. */
2212 if (useless_type_conversion_p (type, inside_type)
2213 && (((inter_int || inter_ptr) && final_int)
2214 || (inter_float && final_float))
2215 && inter_prec >= final_prec)
2217 gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2218 gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2220 return remove_prop_source_from_use (op0) ? 2 : 1;
2223 /* Likewise, if the intermediate and initial types are either both
2224 float or both integer, we don't need the middle conversion if the
2225 former is wider than the latter and doesn't change the signedness
2226 (for integers). Avoid this if the final type is a pointer since
2227 then we sometimes need the middle conversion. Likewise if the
2228 final type has a precision not equal to the size of its mode. */
2229 if (((inter_int && inside_int)
2230 || (inter_float && inside_float)
2231 || (inter_vec && inside_vec))
2232 && inter_prec >= inside_prec
2233 && (inter_float || inter_vec
2234 || inter_unsignedp == inside_unsignedp)
2235 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2236 && TYPE_MODE (type) == TYPE_MODE (inter_type))
2238 && (! final_vec || inter_prec == inside_prec))
2240 gimple_assign_set_rhs1 (stmt, defop0);
2242 return remove_prop_source_from_use (op0) ? 2 : 1;
2245 /* If we have a sign-extension of a zero-extended value, we can
2246 replace that by a single zero-extension. */
2247 if (inside_int && inter_int && final_int
2248 && inside_prec < inter_prec && inter_prec < final_prec
2249 && inside_unsignedp && !inter_unsignedp)
2251 gimple_assign_set_rhs1 (stmt, defop0);
2253 return remove_prop_source_from_use (op0) ? 2 : 1;
2256 /* Two conversions in a row are not needed unless:
2257 - some conversion is floating-point (overstrict for now), or
2258 - some conversion is a vector (overstrict for now), or
2259 - the intermediate type is narrower than both initial and
2261 - the intermediate type and innermost type differ in signedness,
2262 and the outermost type is wider than the intermediate, or
2263 - the initial type is a pointer type and the precisions of the
2264 intermediate and final types differ, or
2265 - the final type is a pointer type and the precisions of the
2266 initial and intermediate types differ. */
2267 if (! inside_float && ! inter_float && ! final_float
2268 && ! inside_vec && ! inter_vec && ! final_vec
2269 && (inter_prec >= inside_prec || inter_prec >= final_prec)
2270 && ! (inside_int && inter_int
2271 && inter_unsignedp != inside_unsignedp
2272 && inter_prec < final_prec)
2273 && ((inter_unsignedp && inter_prec > inside_prec)
2274 == (final_unsignedp && final_prec > inter_prec))
2275 && ! (inside_ptr && inter_prec != final_prec)
2276 && ! (final_ptr && inside_prec != inter_prec)
2277 && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2278 && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2280 gimple_assign_set_rhs1 (stmt, defop0);
2282 return remove_prop_source_from_use (op0) ? 2 : 1;
2285 /* A truncation to an unsigned type should be canonicalized as
2286 bitwise and of a mask. */
2287 if (final_int && inter_int && inside_int
2288 && final_prec == inside_prec
2289 && final_prec > inter_prec
2293 tem = fold_build2 (BIT_AND_EXPR, inside_type,
2296 (inside_type, double_int_mask (inter_prec)));
2297 if (!useless_type_conversion_p (type, inside_type))
2299 tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2301 gimple_assign_set_rhs1 (stmt, tem);
2304 gimple_assign_set_rhs_from_tree (gsi, tem);
2305 update_stmt (gsi_stmt (*gsi));
2313 /* Main entry point for the forward propagation and statement combine
2317 ssa_forward_propagate_and_combine (void)
2320 unsigned int todoflags = 0;
2322 cfg_changed = false;
2326 gimple_stmt_iterator gsi, prev;
2327 bool prev_initialized;
2329 /* Apply forward propagation to all stmts in the basic-block.
2330 Note we update GSI within the loop as necessary. */
2331 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2333 gimple stmt = gsi_stmt (gsi);
2335 enum tree_code code;
2337 if (!is_gimple_assign (stmt))
2343 lhs = gimple_assign_lhs (stmt);
2344 rhs = gimple_assign_rhs1 (stmt);
2345 code = gimple_assign_rhs_code (stmt);
2346 if (TREE_CODE (lhs) != SSA_NAME
2347 || has_zero_uses (lhs))
2353 /* If this statement sets an SSA_NAME to an address,
2354 try to propagate the address into the uses of the SSA_NAME. */
2355 if (code == ADDR_EXPR
2356 /* Handle pointer conversions on invariant addresses
2357 as well, as this is valid gimple. */
2358 || (CONVERT_EXPR_CODE_P (code)
2359 && TREE_CODE (rhs) == ADDR_EXPR
2360 && POINTER_TYPE_P (TREE_TYPE (lhs))))
2362 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2365 || decl_address_invariant_p (base))
2366 && !stmt_references_abnormal_ssa_name (stmt)
2367 && forward_propagate_addr_expr (lhs, rhs))
2369 release_defs (stmt);
2370 todoflags |= TODO_remove_unused_locals;
2371 gsi_remove (&gsi, true);
2376 else if (code == POINTER_PLUS_EXPR && can_propagate_from (stmt))
2378 if (TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST
2379 /* ??? Better adjust the interface to that function
2380 instead of building new trees here. */
2381 && forward_propagate_addr_expr
2385 fold_build2 (MEM_REF,
2386 TREE_TYPE (TREE_TYPE (rhs)),
2390 gimple_assign_rhs2 (stmt))))))
2392 release_defs (stmt);
2393 todoflags |= TODO_remove_unused_locals;
2394 gsi_remove (&gsi, true);
2396 else if (is_gimple_min_invariant (rhs))
2398 /* Make sure to fold &a[0] + off_1 here. */
2399 fold_stmt_inplace (stmt);
2401 if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2407 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2409 if (forward_propagate_comparison (stmt))
2417 /* Combine stmts with the stmts defining their operands.
2418 Note we update GSI within the loop as necessary. */
2419 prev_initialized = false;
2420 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2422 gimple stmt = gsi_stmt (gsi);
2423 bool changed = false;
2425 switch (gimple_code (stmt))
2429 tree rhs1 = gimple_assign_rhs1 (stmt);
2430 enum tree_code code = gimple_assign_rhs_code (stmt);
2432 if ((code == BIT_NOT_EXPR
2433 || code == NEGATE_EXPR)
2434 && TREE_CODE (rhs1) == SSA_NAME)
2435 changed = simplify_not_neg_expr (&gsi);
2436 else if (code == COND_EXPR)
2438 /* In this case the entire COND_EXPR is in rhs1. */
2440 did_something = forward_propagate_into_cond (&gsi);
2441 stmt = gsi_stmt (gsi);
2442 if (did_something == 2)
2444 changed = did_something != 0;
2446 else if (TREE_CODE_CLASS (code) == tcc_comparison)
2449 did_something = forward_propagate_into_comparison (&gsi);
2450 if (did_something == 2)
2452 changed = did_something != 0;
2454 else if (code == BIT_AND_EXPR
2455 || code == BIT_IOR_EXPR
2456 || code == BIT_XOR_EXPR)
2457 changed = simplify_bitwise_binary (&gsi);
2458 else if (code == PLUS_EXPR
2459 || code == MINUS_EXPR)
2460 changed = associate_plusminus (stmt);
2461 else if (CONVERT_EXPR_CODE_P (code)
2462 || code == FLOAT_EXPR
2463 || code == FIX_TRUNC_EXPR)
2465 int did_something = combine_conversions (&gsi);
2466 if (did_something == 2)
2468 changed = did_something != 0;
2474 changed = simplify_gimple_switch (stmt);
2480 did_something = forward_propagate_into_gimple_cond (stmt);
2481 if (did_something == 2)
2483 changed = did_something != 0;
2489 tree callee = gimple_call_fndecl (stmt);
2490 if (callee != NULL_TREE
2491 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2492 changed = simplify_builtin_call (&gsi, callee);
2501 /* If the stmt changed then re-visit it and the statements
2502 inserted before it. */
2503 if (!prev_initialized)
2504 gsi = gsi_start_bb (bb);
2514 prev_initialized = true;
2521 todoflags |= TODO_cleanup_cfg;
2528 gate_forwprop (void)
2530 return flag_tree_forwprop;
2533 struct gimple_opt_pass pass_forwprop =
2537 "forwprop", /* name */
2538 gate_forwprop, /* gate */
2539 ssa_forward_propagate_and_combine, /* execute */
2542 0, /* static_pass_number */
2543 TV_TREE_FORWPROP, /* tv_id */
2544 PROP_cfg | PROP_ssa, /* properties_required */
2545 0, /* properties_provided */
2546 0, /* properties_destroyed */
2547 0, /* todo_flags_start */
2550 | TODO_verify_ssa /* todo_flags_finish */